Leninot escribió:y esto ke hablais de petar la firma,como se hace?(no tengo intencion de hacerlo
,pero es curiosidad!)
Si es un RSA, la clave pública se compondrá de dos números: n, e.
El número n es el grande de 2048 bits o los que sean. Este número es un semiprimo, resultante del producto de dos primos que llamaremos p y q (n = p * q) que normalmente serán cada uno de la mitad de bits que n.
El número e es el exponente que se utiliza para la encriptación con la clave pública y requiere ser relativamente primo (que no tengan divisores comunes) al phi de Euler del número n, que en este caso se define como phi = (p - 1) * (q - 1) o que si lo preferís es la cantidad de números relativamente primos a n menores que n.
Para encriptar un mensaje m en un texto cifrado c lo haríamos de la forma c = m^e mod n.
La clave privada RSA se compone de otro par de números: n, d. El número n aquí es el mismo que en anterior. En cambio, el número d se define como la multiplicativa inversa del número e módulo phi (ya se que esto puede ser difícil de entender, pero es que el RSA se basa en la aritmética modular...). Este cálculo se puede hacer rápidamente mediante el algoritmo extendido de Euclides si tenemos los valores de e y de phi.
Para desencriptar un mensaje cifrado c en el mensaje original m lo haríamos de la forma m = c^d mod n. También podríamos haber usado c = m^d mod n para cifrar y m = c^e mod n para descifrar logrando así una firma digital en vez de una encriptación (ya que para descifrarlo sólo hace falta el par público e, n y para cifrarlo el par privado d, n).
Vale, pero ¿cómo se obtiene la clave privada de la pública? Pues tenemos n y tenemos e. Podemos calcular d (lo que nos falta) si conseguimos phi, y phi lo podemos conseguir si factorizamos n en p y q. ¿Qué problema hay? Pues que n es un número realmente grande (de unos 616 ó 617 dígitos decimales) y factorizarlo resulta simplemente intratable desde el punto de vista computacional actual. Como ya decía Fr0Gt, factorizar el número n en sus dos primos p y q necesitaría millones de años de esfuerzo computacional para lograrse. De hecho, hay unos retos presentados por RSA Security que consisten en factorizar una serie de números n en sus factores primos y te pagan si lo consigues. Por si os interesa, los restos podéis encontrarlos aquí:
The RSA Challenge Numbers. Sólo por el dinero que ofrecen y lo que parece costar que saquen uno podréis imaginaros que no es ninguna tontería romper un RSA. Es más, esos retos llevan años ya y todavía andan muy lejos de lograr romper, ni siquiera con un ataque distribuido y con años de cálculo con ordenadores muy potentes, un RSA de 2048 bits.
No obstante, y como curiosidad, existen un par de posibilidades que hacen que esto se tambalee. La primera de ellas es que no ha podido demostrarse, mediante la teoría de la complejidad, que exista o no un algoritmo capaz de resolver en tiempo polinómico (de forma más o menos tratable) el problema de la factorización de un número cualquiera. Eso significa que cabría la posibilidad, aunque al parecer bastante remota, de que alguien descubriese un algoritmo que fuese capaz de factorizar esos números en un tiempo razonable con ordenadores "convencionales".
La segunda posibilidad está relacionada con los llamados ordenadores cuánticos. La controversia aquí viene dada porque existe un algoritmo llamado el
algoritmo de Shor que es capaz de factorizar números de gran tamaño en un tiempo razonable (posiblemente unos cuantos minutos en lugar de millones de años). El problema está en que se trata de un algoritmo cuántico y requiere de un ordenador cuántico con el doble de qubits que el número de bits del número a factorizar. En este caso se necesitaría un ordenador cuántico de 4096 qubits, pero me da que nadie de por aquí tiene ninguno. Además, para echarle más leña al fuego, hace poco leí que pretendían restringir en USA la exportación de este tipo de computadores por motivos de seguridad (y con razón).
Si a pesar de todo esto alguien todavía piensa que puede romper la clave y quiere perder el tiempo inútilmente, le diré que el algoritmo de factorización más rápido para números grandes a fecha de escribir este post es el llamado
General number field sieve y que hay alguna que otra
implementación opensource. No obstante, ni con esas lograréis algo.
![[oki]](/images/smilies/net_thumbsup.gif "Ok!")
