Introducción a la Factorización De Semiprimos (RSA)
(1/1)
kub0x:
Normalmente, en este foro hablamos de la criptografía estándar, aquella que corre en nuestros dispositivos. Muchos sabreís que algunos de los esquemas criptográficos basados en clave pública o en una única clave (simétricos) sufrirán debilidades cuando el cuántico se torne realidad.
Esto es debido a que problemas como la factorización de enteros, el cálculo del logaritmo discreto, ya sea el aplicado a curvas elípticas o en finite fields podrán ser resueltos. Una respuesta obvia sería aumentar el tamaño de clave en la parametrización de estos esquemas, pero implicaría hacerlo cada vez que la computación cuántica avance.
Hoy vamos a explicar una forma de factorizar números compuestos por dos primos, es decir, semiprimos. Es un problema conocido pues nos daría la habilidad de romper esquemas como RSA. Nótese que RSA también presenta el RSA Problem y está basado en calcular raices e-ésimas mod n.
Antes de empezar, quiero decir que el lector tiene que tener un buen conocimiento en matemáticas: tanto en teoría de números como en algebra lineal.
Factorización De Fermat (Punto Medio)
Sea tal que es un producto de dos primos, por lo tanto es semiprimo.
Queremos encontrar los factores que componen el módulo utilizado por una clave pública RSA. Esto nos permitiría generar firmas digitales válidas, además de intervenir en el TLS Handshake bien en falsificando valores cuando RSA se usa para firma, o bien, descifrando la PMK (Pre Master Key) lo cual nos permitiría hacer un Man In The Middle en plano, como antiguamente :D
Hace unos años, cuando empecé en esto, mi problema favorito era el de la factorización de enteros, curiosamente, la de semiprimos. Resulta que reinventé la rueda al descubrir que entre dos primos siempre existe un punto medio el cual equidista con misma distancia sobre los primos . Si traducimos a cristiano esto sería:
donde y . Si vemos más alla nos damos cuenta que , lo que nos da la expresión . ¿Bonito verdad? ¿Pero cómo aplicarlo?
Un ejemplo sería entonces y . Si nos imáginamos los enteros positivos alineados en una línea horizontal, vemos que equidista posiciones de .
Para usarlo, al saber que hacemos desde hasta dar con una solución entera. Pena que a Pierre de Fermat, se le ocurriera hace casi 400 años, conociéndose este método por Fermat Factorization.
En el mundo real nunca sabremos de antemano, sólo y nuestro interés se centra en encontrar los valores mediante una técnica llamada Quadratic Sieve o Criba Cuadrática.
Quadratic Sieve : Primera Fase
En teoría de números un número b-smooth es aquel que tiene factores primos menores o iguales que , por ejemplo es 5-smooth pero no 3-smooth. Establecemos como primo y seguimos nuestro análisis.
Si tomamos la congruencia entonces (divide a N) por lo tanto y tanto como son factores de .
Empezamos tomando valores de la congruencia . Para eso vamos generando valores . Expresamos en la base prima b-smooth .
Guardamos y reducimos mod 2 los exponentes de la base prima de cada residuo en una matriz de exponentes , donde indica el número de congruencias que hemos obtenido de la criba. En cada columna guardamos los exponentes de cada congruencia . Entonces vemos como:
Segunda Fase
¿Por qué hemos reducidos los exponentes modulo 2 y encima en columnas? Tened en cuenta que si multiplicamos dos números, sus exponentes se suman. Si tras realizar la multiplicación todos los exponentes son pares/even, entonces tiene raíz cuadrada entera. Si los exponentes de son entonces la multiplicación resulta en , si cada sumando es par, la tupla modulo 2 resultado de daría en cada posición.
De esta forma, encontramos residuos b-smooth cuyo producto resulta en una tupla de exponentes enteramente par, y como estamos en , obtenemos una tupla que consiste de 0's y de longitud por lo tanto .
Si revisaís los apuntes de Álgebra Lineal, el rango de una matriz nos indica la dimensión de la imagen. Una matriz se toma como una transformación lineal, cuenta con dominio y codominio. Como nuestra matriz tiene dimensión entonces el sistema nos daría en el vector la ansiada combinación lineal, puesto que una matriz por un vector, no es más que la suma de una combinación lineal de sus columnas. Las ecuaciones de tipo se resuelven calculando el kernel o nullspace de la matriz . Si tenemos una matriz , con entonces por lo tanto y .
Por lo tanto la matriz que representa el kernel de tiene dimension . Si el rango de no baja de la única solución es llamada solución trivial. Para hallar soluciones no triviales el rango ha de ser inferior a y para esto, como las columnas de corresponden a los exponentes de cada residuo, si el rango baja sabemos que existe un producto de residuos que tiene raíz entera. De esta forma, encontramos una combinación lineal sobre las columnas que representan los exponentes, es decir, una suma finita de estas columnas (modulo 2) que da como solución una tupla de longitud con todos los elementos a . Entonces tal y como deseabamos.
Tercera Fase
Ahora, vamos a encontrar los valores tal que . Como hemos guardado todos los valores tal que , haciendo uso de la tupla calculamos el producto de los valores en . Lo mismo para los valores de y lo hacemos en . Entonces y .
La fase de criba finalizaría al dar con el kernel de . Como podeís ver es una fase muy amplía, donde necesitamos muchas congruencias para encontrar una combinación lineal de los exponentes que sea par. Además es necesario en todo momento almacenar las listas de las congruencias, tanto los como los . Todo ello mediante una representación matricial, donde cada columna corresponde a los exponentes de cada termino en la base b-smooth. Para concluir, vemos como el kernel nos permite extraer valores para los cuales existe una combinación lineas de las tuplas de exponentes que da cero. De esta forma sabemos que valores forman un cuadrado mediante su producto o multiplicación.
Ejemplo Quadratic Sieve
Vamos a poner un pequeño ejemplo para ilustrar la teoŕia anteriormente expuesta.
Tomamos la base está compuesta de los 50 primeros primos entonces es 229-smooth es decir . Todos los valores que tratemos tienen que ser 229-smooth, es decir, factorizables entre productos de los primos en la base B.
Si empezamos con , tras iteracciones, tenemos la lista y la de residuos cuadraticos .
La matriz de exponentes tiene dimensión porque cada columna tiene longitud por lo tanto 50 filas y al haber 11 congruencias, de ahí sale. Nos enfrentamos al sistema . Queremos una suma de columnas en que nos de completamente cero, y de esta forma sabremos que productos dan un cuadrado mod N. La matriz se muestra a continuación:
\
La matriz tiene rango modulo 2. Por lo tanto, su kernel o nullspace tiene dimensión 1 y es representable mediante una matriz en este caso . Entonces, la ecuación tiene dos soluciones (una de ellas la trivial) porque la dimensión es 1, por lo tanto una tupla en tiene valores, en este caso 0 ó 1. Por lo tanto fijamos y . Comprobad vosotros mismos que la tercera columna y la onceava columna de la matriz suman 0 mod 2 en cada coordenada/posición.
Por lo tanto, sabemos que de la lista X multiplicamos los valores 3º y el 11º, esto es, y lo mismo con la lista Y, nos queda . Calculamos . Entonces y .
Aquí os dejo el código del algoritmo en Mathematica. Sé que lo puedo mejorar, lo he hecho en un par de horas para colgarlo junto a este tuto. En C++ utilizando la lib de GMP es igual de sencillo, mientras tengas las matemáticas de tu lado, todo va bien. El code es lenguaje de Mathematica aunque ponga el GeShI en MatLab, recuérdenlo.
Código
bsmooth[x_] := (
exps = Array[0 &, Length[plist]];
found = False;
i = 1;
While[found == False && i <= Length[x],
pos = Position[plist, x[[i]][[1]]] ;
If[pos == {},
found = True;
,
pos = pos[[1]];
exps[[pos]] = Mod[x[[i]][[2]], 2];
];
i++;
];
If[found == True,
Return[{}];
,
Return[exps];
];
);
ComputeFactors[list_] := (
k = 1;
Do[If[list[[i]] != 0, k = k*list[[i]]], {i, 1, Length[list]}];
Return[k];
)
QSieve[n_, blen_, limit_] := (
ctr = 1;
xlist = Array[0 &, limit];
ylist = Array[0 &, limit];
plist = Table[Prime[i], {i, 1, blen}];
A = ConstantArray[0, {blen, limit}];
k = 1;
While[ctr <= limit && k <= n,
x = Floor[Sqrt[n] + k++];
x2 = PowerMod[x, 2, n];
bx2 = FactorInteger[x2];
bx2 = bsmooth[bx2];
If[bx2 != {},
xlist[[ctr]] = x;
ylist[[ctr]] = x2;
A[[All, ctr]] = bx2;
ctr++;
];
];
If[MatrixRank[A, Modulus -> 2] < Min[limit, blen],
nsM = NullSpace[A, Modulus -> 2] // Transpose;
inNS = Mod[nsM.RandomInteger[{0, 1}, Dimensions[nsM][[2]]], 2];
factorsX = inNS*xlist;
factorsY = inNS*ylist;
a = ComputeFactors[factorsX];
b = Sqrt[ComputeFactors[factorsY]];
Return[{GCD[a + b, n], GCD[a - b, n]}];
,
Print[-1];
];
)
Para llamar a la función, se necesita el semiprimo n, un número blen que indica la longitud de la base de primos b-smooth y un límite, cuantas congruencias ha de recolectar. Después de recolectar, intenta obtener una solución en la transpuesta del nullspace de la matriz de exponentes. El resto es componer los factores y hacer el GCD.
He capturado un .GIF para mostrar un ejemplo del algoritmo corriendo en Mathematica:
Vemos que el nullspace aquí ya no es sino . Obviamente, el ejemplo que he puesto, era facilito pero el código trabaja para valores más altos.
Y nada, ha quedado demostrado que la criba cuadrática encuentra una solución mientras que seamos capaces de factorizar números en una base b-smooth. Además de necesitar una combinación lineal válida que nos asegure la obtención de un cuadrado mediante producto de residuos cuadráticos.
KMALIGNO:
Muy buena la informacion, soy nuevo por aqui, gracias por el aporte, espero poder tambien dar mi aporte
Navegación