Los primos en la criptografía
Cuando se estudia teoría de números o criptografía vemos que para que el sistema criptográfico RSA funcione bien se necesitan dos números primos grandes (de más de 100 cifras), lo curioso es que los algoritmos que hay para ver si un número es o no primo, son algoritmos «muy lentos» (pueden tardar mucho tiempo para algún número, sobre todo si el número es grande, como es este el caso); así pues nos podemos imaginar como de lento será un algoritmo que deba encontrar primos, éste será mucho más lento, pues puede que el primo sea el siguiente número que se selecciona o no serlo que es lo más probable, pues según crecen los números disminuyen los primos que hay entre ellos; esto es debido a la ley asintótica de distribución de los números primos; si pi(x)= número de primos no superior a x, entonces pi(x) es aproximadamente igual a:
= x/Ln(x).
= x/(Ln(x)-1).
= Integral[dt/Ln(t),{t=2,x}].
Además hay teoremas que afirma la aleatoriedad en la distancia de los primos, es decir, hay primos consecutivos separados más de la cantidad que fijemos de antemano.
En vista a esto podemos ver que en 1000 números consecutivos de 200 cifras hay aproximadamente 2 números primos, pero claro, no se pueden coger los número primos con poca diferencia entre ellos por que entonces el sistema es vulnerable por ataque de número cercamos a la raíz cuadrada. Por tanto es necesario que tomemos dos número grandes y lo más aleatorio posible y desde ellos buscar números primos. Como ya he dicho cuando los números son grandes tenemos la posibilidad de no encontrarlos en tiempo razonable.
Esto quiere decir que los programas que generan sus propias claves de cifrado y descifrado, como deberían de ser todos los programas criptográficos, tienen la posibilidad de tardar mucho para encontrar ese par de primos. Todo esto causa un gran problema a un programador y a la empresa con la que trabaja, intentando buscar otro método para conseguir ese par de números. Lo peor es que este problema parece insalvable. (En contradicción con lo que mucha gente cree, los cuales dicen que se pueden tomar números pseudo primos fuertes en lugar de primos «puros»).
Hay varias formas de atajar este problema:
Generar los números en la empresa y distribuirlos en cada copia del programa haciendo que el número n sea el mismo y cambiando sólo los números e y d de cifrado y descifrado, o alguna de sus variantes como guardar varios número primos (generados en la empresa) y elegir al azar dos de entre ellos. En cualquier caso esta opción es altamente desaconsejable a no ser que queramos que nuestro sistema criptográfico sólo sea un engaña bobos, (al fin y al cabo, cuantos estudiarán los muchos Mb de código que tiene el programa).
La forma más fiable de generar los números primos, p y q; y los dos números de cifrado y descifrado, e y d; es hacerlo en el ordenador del cliente cuando instala el programa o cuando el quiera hacerlo y tener la filosofía de decir que si alguna vez tarda mucho lo sentimos pero no podemos hacer otra cosa.
Y la última que se me ocurre es la que comentaba más arriba, usar pseudo primos. Aunque esta idea ya me ha sido comentado por varias personas, supuestamente entendidas del tema, lo cierto es que no podemos hacer esto. Para ellos vamos a ver algunos ejemplos curiosos en los que se muestra algunos casos posibles que se pueden dar si no usamos primos «puros».
Caso 1.
p = 5×7 = 35.
q = 11×13 = 143.
n = p q = 5005.
fi = ( p-1 )( q-1 ) = 4828. (la supuesta fi de Euler)
Fi( n ) = 2880. (la auténtica Fi de Euler)
d = 13. ( ( n,e ) es la clave pública)
e = 1857. ( ( n,d ) es la clave privada)
Y con estos podemos ver que para el mensaje m = 13, resulta el mensaje cifrado c =1833 y descifrando éste, nm = 13.
Hasta aquí todo parece indicar que las cosas funcionan, pero si tomamos otro número, que tiene que ser menor que n = 5005, vemos que «no todo el monte es orégano». Por ejemplo para m = 25, c =1065, nm = 2885 distinto de m = 25.
Este ejemplo nos dice que hay números que se cifran y descifran correctamente pero no son todos los menores que n, haciendo de este criptosistema algo inservible.
Caso 2.
p = 3×5=15.
q = 7×11=77.
n = p q = 1155.
fi = ( p-1 )( q-1 ) = 1064.
Fi( n ) = 480.
d = 11.
e = 387.
m = 25, c = 295, nm = 295.
En este caso es sistema también produce errores, lo curioso de este es que en el 60% de los casos el mensaje descifrado es igual al cifrado.
Caso 3.
p = 7×11=77.
q = 13×17=221.
n = p q = 17017.
fi = ( p-1 )( q-1 ) = 16720.
Fi( n ) = 13260.
d = 17.
e = 14753.
m = 680, c = 1037, nm = 680.
En esta ocasión es sistema funciona bien y se puede utilizar para criptografía.
Caso 4.
p = 3×5=15.
q = 7.
n = p q = 105.
fi = ( p-1 )( q-1 ) = 84.
Fi( n ) = 48.
d = 41.
e = 41.
m = 60, c = 30, nm = 60.
Esta sistema también funciona bien lo curioso de él es que la clave para cifrar es la misma que para descifrar poniendo una gran herramienta de análisis a quien quiera romperlo, la misma clave pública puede descifrar el mensaje.
Caso 5.
p = 7×11=77.
q = 13.
n = p q = 1001.
fi = ( p-1 )( q-1 ) = 912.
Fi( n ) = 720.
d = 73.
e = 25.
m = 100, c = 100, nm = 100.
En esta ocasión es sistema da como resultado o los tres número iguales m=c=nm o los dos últimos iguales c=nm, tampoco sirve para criptografía.
Como se puede ver hay toda una gran diversidad, algunas muy curiosas. con los ejemplos arriba indicados es más que suficiente para ver que no tenemos ninguna garantía de que el RSA funciones con números que no son primos, por muy pseudo primos fuertes que sean. Todo ésto es consecuencia de que no se puede garantizar el
Teorema de Euler:
«Si m>1 y MCD(a , m)=1, se tiene que: a^(Fi(n))=1 (mod m)»
Pues la Fi(n) no es la que se utiliza sino la fi. Este teorema se utiliza en el paso que descifra el mensaje.
c^(d)=(m^(e))^(d)=m^(e d)= m^(Fi(n)+1)=m^(Fi(n)) m^1=(utilizando el teorema)=1 m=m
Conclusión: Si algún programa tarda mucho puede ser que hayamos tenido mala suerte por haber topado con el primo lento de descubrir o por que el programa o el S. O. se hayan colgado, esto es algo con lo que tenemos que vivir. Pero peor es que confiemos en un sistema criptográfico que es rápido y muy sencillo de utilizar y luego resulte que nuestros documento más preciado puedan ser ojeado por todo el mundo.
Habría que ver el código fuente de los sistemas criptográficos que circulan por Internet para ver si son realmente fiables.