Cracking claves RSA cortos

Question

Dada la siguiente claves RSA, ¿cómo hace uno para determinar cuáles son los valores de p y q son?

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

Answer 1

Tu maestro te dio:

  

Clave Pública: (10142789312725007, 5)

que medios

n = 10142789312725007
e = 5 

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

Además, se le ofrece

  

Clave Privada: (10142789312725007, 8114231289041741)

lo que significa que

 d = 8114231289041741

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

Se puede "romper" RSA por saber cómo el factor "n" en su "p" y "q factores primos":

n = p * q

La forma más sencilla es probablemente para comprobar todos los números impares a partir justo por debajo de la raíz cuadrada de n:

Floor[Sqrt[10142789312725007]] = 100711415

Se obtendría el primer factor de 4 intentos:

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

Así que tenemos

 p = 100711409

Ahora,

 q = n / p 
   = 10142789312725007 / 100711409
   = 100711423

¿Por qué es importante esto? Es porque d es un número especial de tal manera que

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

Podemos comprobar esto

d * e = 40571156445208705 = 1 mod 10142789111302176

Esto es importante porque si usted tiene un mensaje de texto sin formato m a continuación, el texto cifrado es

c = m^e mod n

y se descifra por

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

Por ejemplo, yo puedo "cifrar" el mensaje 123456789 utilizando la clave pública de su maestro:

m = 123456789

Esto me dará el siguiente texto cifrado:

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

(Tenga en cuenta que la "e" debe ser mucho mayor en la práctica porque para pequeños valores de "m" que ni siquiera supera n)

De todas formas, ahora tenemos "c" y se puede revertir con "d"

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

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

En el "mundo real", n es, obviamente, mucho más grande. Si desea ver un ejemplo real de cómo HTTPS utiliza RSA bajo las sábanas con un 617 dígitos n y un e de 65.537, ver mi blog "< a href = "http://www.moserware.com/2009/06/first-few-milliseconds-of-https.html" rel = ""> noreferrer los primeros milisegundos de una conexión HTTPS ."

Answer 2

Esta es una forma relativamente sencilla de verlo (y uno que es factible con la mano). Si se va a factor de la serie por completo, entonces el factor más alto que se necesita para tener en cuenta es sqrt (N):

sqrt(10142789312725007) = 100711415.9999997567

El primer primer debajo de este es 100711409, a sólo 6 por debajo de la sqrt (N).

10142789312725007 / 100711409 = 100711423 

Por lo tanto, se trata de dos factores de N. Su profesor hace que sea muy fácil - el truco es reconocer que nadie escogería un pequeña p o q lo que a partir de su cheque de la parte inferior (como en la otra secuencia de comandos Python publicado) es una mala idea. Si va a ser práctico con la mano, la gran p y q deben estar cerca de sqrt (N).

Answer 3

Existen varios algoritmos rápidos para resolver el problema de la factorización n dado n, e y d. Puede encontrar una descripción bien de un tal algoritmo en el Handbook of Applied Cryptography, Capítulo 8 , sección 8.2.2. Puede encontrar estos capítulos en línea para su descarga gratuita aquí . El algoritmo es esencialmente una elaboración cuidadosa de la Henno Brandsma respuesta a esta misma pregunta.

Actualización 25 de Sep, 2019

En el comentario debajo , el usuario Imperishable Noche sugiere un método alternativo que debe ser al menos conceptualmente más fácil de entender.

Se observa que por lo general e es pequeño. De hecho e es casi siempre 65537. En el caso de que e es pequeño se puede desarrollar una ecuación de segundo grado en el primer p desconocida y por lo tanto fácilmente para resolver usando, por ejemplo, la fórmula cuadrática . Para continuar, vamos conjunto x = p y resuelve para x, sólo para seguir con la convención. Sabemos que ed = 1 mod phi(n), o equivalentemente ed - 1 = k * (p-1)*(q-1). Ahora el establecimiento x=p, y por lo tanto n/x=q, multiplicando ambos lados por x y reordenando los términos tenemos
k * x ² + (d * e - k * n - k - 1) * x + k * n = 0.
 Ahora tenemos una ecuación de la forma ax ² + bx + c = 0 y podemos resolver para x usando la fórmula cuadrática. Así podemos tratar valores de k en un pequeño rango de alrededor de e y no debe haber sólo una solución entera a la cuadrática, la solución para el k correcta.

Notas:

1. Todo debe ser un número entero, por lo que el discriminante debe ser un cuadrado perfecto o podemos descartar k y tratar el siguiente. Además, el numerador debe ser divisible por 2*k.
2. A veces la función lambda Carmichael se utiliza en lugar de la función phi de Euler. Esto complica las cosas un poco porque ahora debemos también adivinar la g = gcd(p-1, q-1). g es siempre, incluso, a menudo es 2, y por lo demás casi siempre un pequeño múltiplo de 2.

ACTUALIZACIÓN 26 de septiembre 2019:

Finding k en realidad es muy fácil cuando e es pequeño. Al tomar la ecuación ed - 1 = k * (p-1)*(q-1) y dividiendo ambos lados por n es bastante fácil ver que floor((ed-1)/n) + 1 == k. Ahora, utilizando las ecuaciones 31 y 32 de M.J. de Wiener "criptoanálisis de corto RSA secreta exponentes" uno puede recuperarse directamente p y q.

Answer 4

WolframAlpha me dice que los factores son 100711409 y 100711423

Me acaba de escribir un script en Python ingenuo fuerza bruta ella. Como amdfan señaló, a partir de la parte superior 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 ser muy mejorado, pero todavía funciona sin ningún problema. Se podría mejorarlo por primfactors haciendo una prueba, pero para pequeños valores como la suya Esto debería ser suficiente.

Answer 5

La definición de RSA le indica que el módulo de n = pq. Ya sabes n por lo que sólo tiene que encontrar dos números p y q que se multiplican a n productos. Usted sabe que p y q son primos, por lo que este es el problema de la factorización prima.

Se puede resolver este por la fuerza bruta de un número relativamente pequeño, pero la seguridad general de RSA depende del hecho de que este problema es insoluble en general.

Answer 6

Esta es una implementación de Java del método de factorización rápida del manual de Applied Cryptography sección del capítulo 8 8.2.2 (gracias a gregs para 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;
    }
}

A salida típica es

100711423 100711409 (3ms)

Answer 7

Estos dos documentos, posiblemente, podría resultar muy útil

• Andrej Dujella - una variante del ataque de Wiener RSA
• Andrej Dujella - fracciones continuas y RSA con exponente secreto pequeño

Se encontró con ellos, cuando yo estaba haciendo una investigación básica sobre las fracciones continuas.

Answer 8

El algoritmo de hacerlo es (y esto va a funcionar para cualquier ejemplo, no sólo esta pequeña que se puede factorizar fácilmente por cualquier equipo):

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 puede calcularse como 40571156445208704 lo que equivale a 2^7 * 316962159728193, y que llamamos s=7 y t = 316962159728193. (En general: cualquier número par es una potencia de 2 veces un número impar). Ahora recoger una en [2,n-1) al azar, y calcular (por sucesivas n cuadratura módulo) 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 el último se garantiza que sea 1, por la construcción de e y d.

Ahora busca el primer 1 en esa secuencia. La anterior o bien será +1 o -1     (Una raíz trivial de 1, mod n) y rehacer con una diferente, o algún x número que no es igual a +1 o -1 mod n.     En este último caso gcd(x-1, n) es un divisor no trivial de n, y así p o q, y hemos terminado. Se puede demostrar que una forma aleatoria trabajará con una probabilidad de aproximadamente 0,5, por lo que necesitamos un par de intentos, pero no muchos en general.

Answer 9

Le sugiero que lea acerca de la criba cuadrática . Si implementa uno usted mismo, este es sin duda vale la pena el crédito. Si usted entiende los principios, que ya ganado algo.

Answer 10

Lo siento por la nigromancia, pero un amigo me preguntó acerca de esto, y después de él señalando aquí, me di cuenta de que realmente no me gusta ninguna de las respuestas. Después de tener el módulo y obtener los números primos (P y Q), es necesario encontrar el totient, que es (p-1)*(q-1).

Ahora, para encontrar el exponente privado, a encontrar la inversa de la exponente público mod del totient.

public_exponent * private_exponent = 1 mod totient

Y ahora usted tiene su clave privada, así de fácil. Todo ello con excepción de la factorización se puede hacer casi instantáneamente para grandes números enteros.

Me escribió algo de 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úpida, pero concisa, de modo grano de sal allí. En este ejemplo particular, el código se ejecuta casi al instante, pero eso es en gran parte porque el instructor en cuestión proporciona un ejemplo que utiliza dos números primos en una fila, que no es muy realista para RSA.

Si quería cortar mi estúpida búsqueda iterativa, que podría poner en un cierto algoritmo de factorización real, y teclas de factor probable hasta alrededor de 256 bits en una cantidad razonable de tiempo.

Answer 11

Es necesario que factorizar el módulo, que es el primer parámetro de la clave pública, 10142789312725007. fuerza bruta hará (comprobar cada número impar de 3 a sqrt (n) si se trata de un factor), aunque existen más sofisticados algoritmos / rápido .

Dado que el número es demasiado grande para caber en un entero convencional (incluso de 64 bits), puede que desee una biblioteca numérica que los apoyos arbitraria-lenth enteros. Para C, hay GMP y MPIR (más de Windows de usar). Para PHP, hay Bignum. Python viene con una incorporada en uno -. La incorporada en el tipo de datos entero ya es arbitraria de longitud

Answer 12

Hay un montón de mala especulación acerca de factorización de números primos grandes semi que entran en la fuerza bruta o tamizado ninguno de los cuales se requiere para factorizar el primer semi. 64 bits tiene 1 - 2 segundos en mi pc, y 256 bits por lo general menos de 2 días