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
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:
 \cdot (r-d)=n)
donde
y
. Si vemos más alla nos damos cuenta que
\cdot (x-y)=x^2-y^2=n)
, 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 FaseEn 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
\cdot (x-y) \mid N)
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
, \beta=(\beta_1,\ldots,\beta_b))
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
_b)
.
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
 \leq n)
por lo tanto
=n)
y
-rk(A)=n-r=Dim(Ker(A)))
.
Por lo tanto la matriz que representa el kernel de
tiene dimension
)
. Si el rango de
no baja de
)
la única solución es
_k)
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 FaseAhora, vamos a encontrar los valores
tal que
(a-b)=N)
. 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
 \mid N)
.
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 SieveVamos 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
 = 0)
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
=\gcd(22089375 %2B 1949878,N)=3581)
y
=\gcd(22089375-1949878,N)=4633)
.
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.
bsmooth[x_] := (
exps = Array
[0 &,
Length[plist
]];
found = False;
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];
];
];
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,
x2 = PowerMod[x, 2, n];
bx2 = FactorInteger[x2];
bx2 = bsmooth[bx2];
If[bx2 != {},
xlist[[ctr]] = x;
ylist[[ctr]] = x2;
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
]}];
,
];
)
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.
Mostrar Mensajes
