Desde el punto de vista matemático, siempre puede suponerse que el mensaje quiere transmitir es un número. Internamente, las computadoras representan todos los caracteres (letras, números o símbolos especiales) como números binarios de acuerdo al código ASCII.
Los algoritmos de clave rápida se basan en el hecho de que existen operaciones matemáticas que se pueden realizar rápidamente en una computadora. Para ellas, las operaciones inversas aunque teóricamente son posibles, en realidad demandan un tiempo de procesamiento que las hacen prácticamente imposible de realizar. Por ejemplo, dados dos números primos grandes que llamaremos P y Q, es muy fácil calcular N = PQ. Sin embargo, conociendo N, es prácticamente imposible calcular P y Q si son suficientemente grandes.
Los algoritmos de clave pública también pueden usarse para la autentificación como la firma pública. El algoritmo de clave pública más utilizado es el RSA, que junto al algoritmo de Diffie-Hellman, emplean varias herramientas de la teoría de números. Ambos utilizan como función de una sola vía, la función exponencial modular (f(x)=a^x). Con ello es posible calcular a^x de una forma muy eficiente usando el método de cuadrados repetidos.
Si P es un número primo, decimos que g es una raíz primitiva módulo P, si g^n módulo P recorre los valores 1, 2, …, P-1 cuando n recorre esos mismos valores. Por ejemplo si elegimos P = 23 , g = 5 es una raíz primitiva ya que tenemos la siguiente tabla de valores:
Para todo primo P, existen raíces primitivas.
Algoritmo RSA.
Inventado por Ron Rivest, Adi Shamir y Len Adleman en 1977. Vamos a explicar rápidamente su funcionamiento con un ejemplo:
Alicia elige al azar dos números primos grandes y distintos que llamaremos P y Q, y calculo N = PQ, por ejemplo elige P = 17 y Q = 41 por lo que N = 697. También elige al azar un número E que no tenga factores en común con F = (P-1)(Q-1), como por ejemplo E = 231, F = 640.
La clave pública de Alicia es el par (
El máximo común divisor entre F y E siempre se puede escribir como: aF + dE, siendo a y d dos números enteros. En el caso de Alicia a = 61, d = -169.
Por lo tanto podemos calcular un entero d tal que dE = 1 con módulo F. Alicia mantendrá d en secreto ya que es su clave privada, que en su caso será d = 471.
Por lo tanto es posible pensar en el conjunto de números {0, 1, 2, …, N-1} como un alfabeto, y representar el mensaje como uno o varios números de dicho alfabeto. Por lo tanto podemos pensar que el mensaje a transmitir es un número m de la aritmética modular módulo N.
Cuando otro usuario quiere enviarle un mensaje m a Alicia, busca su clave pública (E, N), y calcula c = m^e con módulo N (siendo c el mensaje cifrado).
Alicia quiere desencriptar el mensaje y para utilizará el siguiente teorema:
(m^e)^d = m (Con módulo N)
La seguridad del algoritmo RSA depende de que aun conociendo N, no sea posible calcular los factores P y Q y por lo tanto, F.
Actualmente no se conoce ningún algoritmo eficiente para factorizar números grandes, y se conjetura que tal algoritmo no existe. Sin embargo, si existe un algoritmo para ver si un número es primo o no en tiempo polinomial (sin calcular sus factores).
En la práctica que un programa de criptografía sea seguro o no, no depende solo del algoritmo matemático que emplea, sino de muchos detalles que hacen su implementación. Solo pueden considerarse seguras las implementaciones de los algoritmos criptográficos para las que está disponible el código fuente, porque sin él no es posible auditar el código para verificar que el programa no tenga puertas traseras, u otros defectos que lo hagan inseguro.