TARDÍGRADOS

Ciencia en español -ʟᴀ ʀᴀᴢóɴ ᴇsᴛá ᴀʜí ғᴜᴇʀᴀ-

Archive for November, 2016

Cómo romper los códigos criptográficos RSA: factorizacion de semiprimos y las raices rectangulares

Posted by Albert Zotkin on November 18, 2016

riemann-estela
En la actualidad, usamos algunas de las propiedades de los números primos para codificar mensajes, de modo que ningún intruso pueda leer fácilmente nuestras comunicaciones. Para ello usamos la propiedad siguiente de los número semiprimos: Elegimos dos números primos suficientemente grandes, y obtenemos el semiprimo multiplicándolos. El número semiprimo será parte de la llave pública para nuestro método de encriptación, y con los dos números primos se construyen las llaves privadas. Dado un semiprimo suficientemente grande, es prácticamente imposible hallar en tiempo razonablemente corto, sus dos factores primos. Eso es incluso casi intratable usando supercomputadores. esta dificultad se llama Problema RSA.
Si estás interesado en desencriptar los códigos que protegen el acceso a tarjetas de crédito bancarias o a páginas web seguras, quizás estés interesado en participar en esta clase de Competición de factorización RSA. Veamos un semiprimo catalogado por la RSA y que tiene un premio de 100.000 dólares para quien halle sus dos factores primos. Este semiprimo es el RSA1024, es decir, posee 1024 cifras binarias (309 cifras decimales):

\displaystyle \text{RSA}_{1024} = \\ 13506641086599522334960321627880596993888147560566702752448514385152651060 \\ 48595338339402871505719094417982072821644715513736804197039641917430464965 \\ 89274256239341020864383202110372958725762358509643110564073501508187510676 \\ 59462920556368552947521350085287941637732853390610975054433499981115005697 \\ 7236890927563
Si queremos factorizar con éxito un número semiprimo de la RSA, lo primero que debemos hacer es estimar lo grande que serán sus dos factores primos. Así, para ese RSA1024, los dos factores primos estarán muy cerca relativamente de su raíz cuadrada, es decir, números primos cercanos a las 154 cifras decimales, o lo que es lo mismo, números primos de entre 100 y 200 cifras decimales. Por ejemplo, si uno de los primos resulta tener 120 cifras decimales, el otro estaría muy próximo a las 188. Pero, veamos, ¿cuántos números primos hay que tengan entre 100 y 200 cifras decimables?. Usemos la función contador de números primos, p(x), aproximémosla a x/log(x), porque según Gauss, esa es una buena aproximación para un x suficientemente grande. Así los números primos que tienen entre 100 y 200 cifras decimales son aproximadamente :

\displaystyle 2.17 \times 10^{197}
Supongamos que disponemos del superordenador más potente del mundo, el reciente Sunway TaihuLight, capaz de operar a máximo rendimiento, que es de 125.43 petaFLOPS. Conseguiría resolver el número RSA1024 1 petaFlop es 1 opración de coma flotando por cada femtosegundo. 10¹5 femtosegundos son 1 segundo. En total tardaríamos un maximo de :

\displaystyle 2.17 \times 10^{197} \times 10^{-15} = 2.17 \times 10^{182} \; \text{segundos,}
un tiempo demasiado largo como para tener alguna esperanza de llegar en vida hasta el final del cálculo y verlo con nuestros propios ojos 😛

Veamos ahora qué es una raíz rectangular. Cuando calculamos una raíz cuadrada en realidad estamos calculando dos números, pero como ambos son iguales, no nos damos cuenta que en realidad es un par de números. Por ejemplo, la raices cuadradas de 64 son el par (8, 8):

\displaystyle \sqrt{64}=(8,8)
Podemos calcular para 64 su raices rectangulares, ya que si nos fijamos 64 puede escribirse como 2 elevado a diferentes exponentes, es decir:

\displaystyle 64 = 2^6 = 2^3 \times 2^3 = 2^2 \times 2^4 = 2^1 \times 2^5
Es decir, el número 64 posee dos pares de raíces rectangulares y un par de raíces cuadradas:

\displaystyle 64 = (8,8) = (4,16) = (2,32)
Así, para entendernos, pondremos el par de exponentes de las raices rectangulares entre corchetes, de modo que siempre tendremos la equivalencia:

\displaystyle 1 = \left[\frac{3}{6}, \frac{3}{6}\right] = \left[\frac{2}{6}, \frac{4}{6}\right] = \left[\frac{1}{6}, \frac{5}{6}\right]
Con esto, lo único que estamos haciendo es dividir la unidad en dos partes, de modo que su suma sea esa misma unidad. ¿Por qué el número 64 posee esas raices rectangulare y no otras?. En realidad posee muchas más, pero las que he escrito arriba son las que dan raices enteras. Veamos estos casos:

\displaystyle 64 = 64^{\tfrac{1}{4}}\times 64^{\tfrac{3}{4}}= (2\sqrt{2}) (16\sqrt{2}) \\ 64 = 64^{\tfrac{1}{5}}\times 64^{\tfrac{4}{5}}= (2\sqrt[5]{2}) (16\sqrt[5]{2^4}) \\
en general, para cualquier par de número enteros m y n, que sean coprimos,tendremos las raices rectangulares de un número N:

\displaystyle N= N^{\tfrac{m}{n}}\times N^{1-\tfrac{m}{n}}
Veamos ahora cómo aplicamos esto a la factorizaación de números RSA: sean los números primos p = 486023 y q = 598727, por lo que su producto es N = 290995092721. Empezaremos nuestros cálculos con su raíz cuadrada:

\displaystyle \sqrt{N}=539439.60989252541168458987732327730802813682656081\ldots
Igualmente sabemos que ha de ser:

\displaystyle p= N^{\tfrac{m}{n}} \\ q= N^{1-\tfrac{m}{n}}

y puesto que sabemos los valores de p y q, es fácil resolver m y n:

\displaystyle \frac{m}{n}=\frac{\log p}{\log(pq)} \\ \\ \\ 1-\frac{m}{n}=1-\frac{\log p}{\log(pq)}=\frac{\log q}{\log(N)}
Por otro lado, si pensamos un poquito, nos daremos cuenta de que factorizar un número RSA no es muy difícil en principio, la dificultad reside en que los números primos, p y q, que forman el semiprimo N, sean muy grandes. Así, es incluso posible presentar una ecuación matemática con la que podemos resolver cualquier número RSA, y es esta:

\displaystyle \mathrm{mcd} (N, \lfloor\sqrt{N}\rfloor !)=\min (p,q) (1)
Aquí N es producto de los dos primos p y q, mcd es el máximo común divisor de dos números, \lfloor\ r\rfloor ! es el factorial de la parte entera del número real r. Podemos incluso optimizar un poco esa ecuación (1) si usamos el primorial en lugar del factorial,

\displaystyle \mathrm{mcd} (N, \lfloor\sqrt{N}\rfloor \#)=\min (p,q) (2)
Si N ya es en principio un número muy grande (más de 1024 digitos binarios), el factorial (o el primorial) de la parte entera de su raíz cuadrada será incluso más grande aún, prácticamente intratable. De ahí que las fórmulas (1) y (2) aunque sean correctas, no son muy útiles para el cálculo. En realidad, para calcular un mcd de dos números primero hay que factorizar esos dos números. Es evidente que factorizar N es más fácil que factorizar el primorial de la parte entera de su raíz cuadrada.

Posted in informática, Matemáticas | Tagged: , , , , , , , , , , , , , , , , , , , | Leave a Comment »