math rsa encryption-asymmetric public-key-encryption

math - Agrietando llaves cortas de RSA



encryption-asymmetric public-key-encryption (12)

Aquí hay una implementación de Java del método de factoraje rápido del Handbook of Applied Cryptography capítulo 8 sección 8.2.2 (gracias a GregS por encontrarlo):

/** * Computes the factors of n given d and e. * Given are the public RSA key (n,d) * and the corresponding private RSA key (n,e). */ public class ComputeRsaFactors { /** * Executes the program. * * @param args The command line arguments. */ public static void main(String[] args) { final BigInteger n = BigInteger.valueOf(10142789312725007L); final BigInteger d = BigInteger.valueOf(5); final BigInteger e = BigInteger.valueOf(8114231289041741L); final long t0 = System.currentTimeMillis(); final BigInteger kTheta = d.multiply(e).subtract(BigInteger.ONE); final int exponentOfTwo = kTheta.getLowestSetBit(); final Random random = new Random(); BigInteger factor = BigInteger.ONE; do { final BigInteger a = nextA(n, random); for (int i = 1; i <= exponentOfTwo; i++) { final BigInteger exponent = kTheta.shiftRight(i); final BigInteger power = a.modPow(exponent, n); final BigInteger gcd = n.gcd(power.subtract(BigInteger.ONE)); if (!factor.equals(BigInteger.ONE)) { break; } } } while (factor.equals(BigInteger.ONE)); final long t1 = System.currentTimeMillis(); System.out.printf("%s %s (%dms)/n", factor, n.divide(factor), t1 - t0); } private static BigInteger nextA(final BigInteger n, final Random random) { BigInteger r; do { r = new BigInteger(n.bitLength(), random); } while (r.signum() == 0 || r.compareTo(n) >= 0); return r; } }

Un resultado típico es

100711423 100711409 (3ms)

Dadas las siguientes claves RSA, ¿cómo se puede determinar cuáles son los valores de pyq ?

Public Key: (10142789312725007, 5) Private Key: (10142789312725007, 8114231289041741)

Aquí hay una manera relativamente simple de verlo (y uno que es factible a mano). Si tuvieras que factorizar el número completamente, entonces el factor más alto que necesitarías considerar es sqrt (N):

sqrt(10142789312725007) = 100711415.9999997567

El primer primo debajo de esto es 100711409, solo 6 debajo del sqrt (N).

10142789312725007 / 100711409 = 100711423

por lo tanto, estos son dos factores de N. Su profesor lo hizo bastante fácil - el truco es reconocer que nadie elegiría una pequeña oq, por lo que comenzar su cheque desde abajo (como en el guión python que alguien publicó) es una mala idea . Si va a ser práctico a mano, la gran pyq deben estar cerca de sqrt (N).

El algoritmo para hacer esto es (y esto funcionará para cualquier ejemplo, no solo este pequeño que puede ser factorizado fácilmente por cualquier computadora):

ed - 1 es un múltiplo de phi(n) = (p-1)(q-1) , por lo que es al menos un múltiplo de 4.
ed - 1 se puede calcular como 40571156445208704 que equivale a 2^7 * 316962159728193 , y llamamos s=7 t = 316962159728193 . (en general: cualquier número par es una potencia de 2 veces un número impar). Ahora escoja a en [2,n-1) al azar, y calcule (por sucesivo módulo de cuadratura n ) la secuencia a^t (mod n), a^(2t) (mod n), a^(4t) (mod n).. hasta como máximo a^((2^7)*t) (mod n) , donde se garantiza que el último es 1, por la construcción de e y d .

Ahora buscamos el primer 1 en esa secuencia. El anterior será +1 o -1 (una raíz trivial de 1, mod n ) y rehacemos con una a diferente, o un número x que no es igual a +1 o -1 mod n . En el último caso, gcd(x-1, n) es un divisor no trivial de n , y entonces p o q , y hemos terminado. Uno puede mostrar que un azar a funcionará con una probabilidad de 0.5, por lo que necesitamos algunos intentos, pero no muchos en general.

Existen varios algoritmos rápidos para resolver el problema de factorizar n dado n , e y d . Puede encontrar una buena descripción de uno de estos algoritmos en el Manual de Criptografía Aplicada, Capítulo 8 , sección 8.2.2. Puede encontrar estos capítulos en línea para su descarga gratuita here .

Hay una gran cantidad de especulaciones negativas sobre la factorización de grandes semi-primos que entran en la fuerza bruta o el tamizado, ninguno de los cuales es necesario para factorizar la semi-prima. 64 bits demoran de 1 a 2 segundos en mi PC y 256 bits generalmente menos de 2 días

La definición de RSA te dice que el módulo n = pq . Sabes n así que solo necesitas encontrar dos números q que se multipliquen para producir n . Usted sabe que p y q son primos, entonces este es el problema principal de la factorización.

Puede resolver esto por la fuerza bruta para números relativamente pequeños, pero la seguridad general de RSA depende del hecho de que este problema es intratable en general.

Necesita factorizar el módulo, ese es el primer parámetro de la clave pública, 10142789312725007. La fuerza bruta será suficiente (compruebe cada número impar de 3 a sqrt (n) si es un factor), aunque existen algoritmos más sofisticados / rápidos.

Dado que el número es demasiado grande para caber en un entero convencional (incluso de 64 bits), es posible que desee una biblioteca numérica que admita enteros arbitrarios de lenth. Para C, hay GMP y MPIR (más amigables para Windows). Para PHP, está Bignum. Python viene con una función incorporada: el tipo de datos entero integrado ya es de longitud arbitraria.

Perdón por la nigromancia, pero un amigo me preguntó acerca de esto, y después de señalarlo aquí, me di cuenta de que realmente no me gustaban ninguna de las respuestas. Después de factorizar el módulo y obtener los números primos (pyq), necesita encontrar el totient, que es (p-1)*(q-1) .

Ahora, para encontrar el exponente privado, se encuentra que el inverso del exponente público modifica el totient.

public_exponent * private_exponent = 1 mod totient

Y ahora tienes tu clave privada, así de fácil. Todo esto, excepto la factorización, se puede hacer casi instantáneamente para enteros enormes.

Escribí un código:

// tinyrsa.c // // apt-get install libgmp-dev // yum install gmp-devel // // gcc tinyrsa.c -o tinyrsa -lm -lgmp #include<stdio.h> #include<gmp.h> int main() { // declare some multi-precision integers mpz_t pub_exp, priv_exp, modulus, totient, fac_p, fac_q, next_prime; mpz_init_set_str(pub_exp,"5",10); mpz_init_set_str(modulus,"10142789312725007",10); mpz_init(priv_exp); mpz_init(totient); mpz_init(fac_p); mpz_init(fac_q); // now we factor the modulus (the hard part) mpz_init(next_prime); mpz_sqrt(next_prime,modulus); unsigned long removed=0; while(!removed) { mpz_nextprime(next_prime,next_prime); removed=mpz_remove(fac_p,modulus,next_prime); } mpz_remove(fac_q,modulus,fac_p); // we now have p and q // the totient is (p-1)*(q-1) mpz_t psub, qsub; mpz_init(psub); mpz_init(qsub); mpz_sub_ui(psub,fac_p,1); mpz_sub_ui(qsub,fac_q,1); mpz_mul(totient,psub,qsub); // inverse of the public key, mod the totient.. mpz_invert(priv_exp,pub_exp,totient); gmp_printf("private exponent:/n%Zd/n",priv_exp); }

El algoritmo de factorización que utilicé es estúpido, pero conciso, por lo tanto, grano de sal. En este ejemplo particular, el código se ejecuta casi al instante, pero eso se debe en gran parte a que el instructor en cuestión proporcionó un ejemplo que usa dos números primos en una fila, lo que no es realmente realista para RSA.

Si quisiera cortar mi estúpida búsqueda iterativa, podría poner algún algoritmo de factorización real, y claves de factor probablemente hasta alrededor de 256 bits en un período de tiempo razonable.

Te sugiero que leas sobre el Tamiz Cuadrático . Si implementa uno usted mismo, seguramente vale la pena el crédito. Si entiendes los principios, ya has ganado algo.

Tu maestra te dio:

Clave pública: (10142789312725007, 5)

lo que significa

n = 10142789312725007 e = 5

donde n es el módulo y e es el exponente público.

Además, te dan

Clave privada: (10142789312725007, 8114231289041741)

significa que

d = 8114231289041741

donde d es el exponente de descifrado que debe permanecer en secreto.

Puede "romper" RSA sabiendo cómo factorizar "n" en sus factores primos "p" y "q":

n = p * q

La forma más fácil es, probablemente, verificar todos los números impares comenzando justo debajo de la raíz cuadrada de n:

Floor[Sqrt[10142789312725007]] = 100711415

Obtendrás el primer factor en 4 intentos:

10142789312725007 mod 100711415 = 100711367 10142789312725007 mod 100711413 = 100711373 10142789312725007 mod 100711411 = 100711387 10142789312725007 mod 100711409 = 0 <-- Winner since it evenly divides n

Entonces tenemos

p = 100711409

Ahora,

q = n / p = 10142789312725007 / 100711409 = 100711423

¿Porque es esto importante? Es porque d es un número especial tal que

d = e^-1 mod phi(n) = e^-1 mod (p-1)*(q-1)

Podemos verificar esto

d * e = 40571156445208705 = 1 mod 10142789111302176

Esto es importante porque si tiene un mensaje de texto claro m, entonces el texto cifrado es

c = m^e mod n

y lo descifras por

m = c^d = (m^e)^d = (m^(e*d)) = (m^(e*e^-1)) = m^1 (mod n)

Por ejemplo, puedo "encriptar" el mensaje 123456789 usando la clave pública de tu profesor:

m = 123456789

Esto me dará el siguiente texto cifrado:

c = m^e mod n = 123456789^5 mod 10142789312725007 = 7487844069764171

(Tenga en cuenta que "e" debería ser mucho más grande en la práctica porque para valores pequeños de "m" ni siquiera excede n)

De todos modos, ahora tenemos "c" y podemos revertirlo con "d"

m = c^d mod n = 7487844069764171^8114231289041741 mod 10142789312725007 = 123456789

Obviamente, no puede calcular "7487844069764171 ^ 8114231289041741" directamente porque tiene 128,808,202,574,088,302 dígitos, por lo que debe usar el truco de exponenciación modular .

En el "mundo real", n es obviamente mucho más grande. Si desea ver un ejemplo real de cómo HTTPS usa RSA bajo las carátulas con una n de 617 dígitos y una e de 65537, consulte la publicación de mi blog " Los primeros pocos milisegundos de una conexión HTTPS ".

Wolframalpha me dice que los factores son 100711409 y 100711423

Acabo de escribir una secuencia de comandos ingenua de Python para reforzarla. Como amdfan señaló, comenzar desde arriba es un mejor enfoque:

p = 10142789312725007 for i in xrange(int(p**0.5+2), 3, -2): if p%i == 0: print i print p/i break

Esto podría mejorarse mucho, pero aún funciona sin problemas. Puedes mejorarlo simplemente probando los factores primarios, pero para valores pequeños como el tuyo esto debería ser suficiente.