Casser des clés RSA courtes

StackOverflow https://stackoverflow.com/questions/4078902

Question

Étant donné les clés RSA suivantes, comment déterminer quelles sont les valeurs de p et q sont?

Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)
Était-ce utile?

La solution

Votre professeur vous a donné:

  

clé publique: (10142789312725007, 5)

lequel des moyens 

n = 10142789312725007
e = 5

où n est le module et e est l'exposant public.

En outre, vous êtes donné

  

clé privée: (10142789312725007, 8114231289041741)

ce qui signifie que 

 d = 8114231289041741

où d est l'exposant de déchiffrement qui doit rester secret.

Vous pouvez « casser » RSA en sachant comment le facteur « n » dans son « p » et « q » facteurs premiers: 

n = p * q

Le plus simple est sans doute de vérifier tous les numéros impairs à partir juste en dessous de la racine carrée de n: 

Floor[Sqrt[10142789312725007]] = 100711415

vous obtiendrez le premier facteur dans 4 essais: 

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

Nous avons donc 

 p = 100711409


 q = n / p 
   = 10142789312725007 / 100711409
   = 100711423

Pourquoi est-ce important? Il est parce que d est un numéro spécial tel que 

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

Nous pouvons vérifier 

d * e = 40571156445208705 = 1 mod 10142789111302176

Ceci est important parce que si vous avez un message clair m puis le cryptogramme est 

c = m^e mod n

et vous décryptez par 

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

Par exemple, je peux « crypter » le message 123456789 utilisant la clé publique de votre professeur: 

m = 123456789

Cela me donnera le texte chiffré suivant: 

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

(Notez que « e » devrait être beaucoup plus grande dans la pratique, car pour les petites valeurs de « m » vous ne même pas dépasser n)

Quoi qu'il en soit, maintenant que nous avons "c" et peut inverser avec "d" 

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

De toute évidence, vous ne pouvez pas calculer "7487844069764171 8114231289041741 ^" directement parce qu'il a 128,808,202,574,088,302 chiffres, vous devez donc utiliser le n est évidemment beaucoup plus grande. Si vous souhaitez voir un exemple réel de la façon dont HTTPS utilise RSA sous les couvertures avec un 617 chiffres n et e de 65537, voir mon blog « < a href = "http://www.moserware.com/2009/06/first-few-milliseconds-of-https.html" rel = "noreferrer"> Les premiers millisecondes d'un HTTPS de connexion « .

Autres conseils

Voici un moyen relativement simple à regarder (et qui est faisable à la main). Si vous deviez facteur le nombre complètement, le plus grand facteur que vous devez considérer est sqrt (N): 

sqrt(10142789312725007) = 100711415.9999997567

La première prime est inférieure à cette 100.711.409, juste en dessous de la 6 sqrt (N). 

10142789312725007 / 100711409 = 100711423

Ce sont donc deux facteurs de N. Votre professeur a rendu assez facile - l'astuce est de reconnaître que personne ne choisirait un petit p ou q afin de commencer votre chèque à partir du bas (comme dans quelqu'un script python affiché) est une mauvaise idée. Si ça va être pratique à la main, le grand p et q doivent se trouver à proximité sqrt (N).

Il existe différents algorithmes rapides pour résoudre le problème de la factorisation n donné n, e, et d.Vous pouvez trouver une bonne description d'un de ces algorithmes dans le Handbook of Applied Cryptography, Chapitre 8, article 8.2.2.Vous pouvez trouver ces chapitres en ligne en téléchargement gratuit ici.L'algorithme est essentiellement une élaboration minutieuse de Réponse de Henno Brandsma à cette même question.

MISE À JOUR le 25 septembre 2019 :

Dans le commentaires ci-dessous, utilisateur Nuit impérissable suggère une méthode alternative qui devrait être au moins conceptuellement plus facile à comprendre.

Il note qu'habituellement e est petite.En fait e est presque toujours 65537.Dans le cas où e est petit, vous pouvez développer une équation quadratique dans le nombre premier inconnu p et ainsi le résoudre facilement en utilisant par ex. la formule quadratique.Pour continuer, définissons x = p et résolvons x, juste pour respecter les conventions.Nous savons que ed = 1 mod phi(n), ou équivalented - 1 = k * (p-1)*(q-1).Maintenant, réglage x=p, et donc n/x=q, en multipliant les deux côtés par x et réorganiser les termes que nous avons
k*x2 + (d*e - k*n - k - 1)*x + k*n = 0.
Maintenant, nous avons une équation de la hache de forme2 + bx + c = 0 et nous pouvons résoudre x en utilisant la formule quadratique.On peut donc essayer les valeurs de k dans une petite zone autour e et il ne devrait y avoir qu'une seule solution entière au quadratique, la solution du k correct.

Remarques:

  1. Tout doit être un entier, donc le discriminant doit être un carré parfait ou nous pouvons rejeter k et essayer le suivant.De plus, le numérateur doit être divisible par 2*k.
  2. Parfois, la fonction Carmichael lambda est utilisée à la place de la fonction Euler phi.Cela complique un peu les choses car il faut maintenant aussi deviner le g = gcd(p-1, q-1). g est toujours pair, vaut souvent 2 et est par ailleurs presque toujours un petit multiple de 2.

MISE À JOUR le 26 septembre 2019 :

Découverte k est en fait très facile quand e est petite.En prenant l'équationed - 1 = k * (p-1)*(q-1) et en divisant les deux côtés par n c'est assez facile de voir que floor((ed-1)/n) + 1 == k.Utilisant maintenant les équations 31 et 32 ​​de M.J."Cryptanalyse des exposants secrets RSA courts" de Wiener on peut récupérer directement p et q.

WolframAlpha me dit que les facteurs sont 100711409 et 100711423

Je viens d'écrire un script Python naïf de bruteforcer il. Comme amdfan a souligné, en partant du haut est une meilleure approche: 

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

Cela pourrait être fortement améliorée, mais il fonctionne toujours sans problème. Vous pouvez l'améliorer en tout essai primfactors, mais pour les petites valeurs comme la vôtre cela devrait être suffisant.

La définition de RSA vous indique que le n = pq module. Vous savez n si vous avez juste besoin de trouver deux nombres p et q qui se multiplient à produire n. Vous savez que p et q sont premiers, donc ce problème est le premier factoriel.

Vous pouvez résoudre ce par la force brutale pour un nombre relativement faible, mais la sécurité globale du RSA dépend du fait que ce problème est intraitable en général.

Voici une implémentation Java de la méthode d'affacturage rapide du Manuel de Cryptographie appliquée

Ces deux documents pourraient éventuellement venir utiles

Nous sommes tombés sur eux quand je faisais des recherches de base sur les fractions continues.

L'algorithme de le faire est (et cela fonctionnera pour tout exemple, non seulement ce petit qui peut être facilement pris en compte par tout ordinateur):

ed - 1 est un multiple de phi(n) = (p-1)(q-1), est donc au moins un multiple de 4.
ed - 1 peut être calculée comme 40571156445208704 qui est égal à 2^7 * 316962159728193, et nous appelons s=7 et t = 316962159728193. (En général: tout nombre pair est une puissance de 2 fois un nombre impair). Maintenant choisir un en [2,n-1) au hasard, et calculer (par élévation au carré modulo successive n) la séquence a^t (mod n), a^(2t) (mod n), a^(4t) (mod n).. jusqu'à au plus a^((2^7)*t) (mod n), où le dernier est assuré d'être 1, par la construction de e et d.

Nous attendons maintenant la première 1 dans cet ordre. Celui avant qu'il ne soit +1 ou -1     (Une racine triviale de 1, mod n) et nous refaisons avec un autre un ou un nombre x qui ne correspond pas à +1 ou -1 mod n.     Dans ce dernier cas gcd(x-1, n) est un diviseur non trivial de n, et ainsi p ou q, et nous fait. On peut montrer qu'un hasard un fonctionnera avec une probabilité d'environ 0,5, donc nous avons besoin de quelques essais, mais pas beaucoup en général.

Désolé pour la nécromancie, mais un ami m'a demandé à ce sujet, et après le montrant du doigt ici, je compris que je ne l'ai pas vraiment comme l'une des réponses. Après prise en compte du module et obtenir les nombres premiers (p et q), vous devez trouver le totient, qui est (p-1)*(q-1).

Maintenant, pour trouver l'exposant privé, vous trouvez l'inverse de l'exposant public mod le totient. 

public_exponent * private_exponent = 1 mod totient

Et maintenant que vous avez votre clé privée, facile. Tout cela, sauf pour la factorisation peut se faire presque instantanément pour les entiers énormes.

J'ai écrit un code: 

// 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);

}

L'algorithme de factorisation j'est bête, mais concise, de sorte que le grain de sel là. Dans cet exemple particulier le code fonctionne presque instantanément, mais qui est en grande partie parce que l'instructeur en question a donné un exemple qui utilise deux nombres premiers dans une rangée, ce qui est pas vraiment réaliste pour RSA.

Si vous vouliez découper ma recherche itérative stupide, vous pouvez mettre dans un algorithme de factorisation réel, et les clés de facteurs susceptibles jusqu'à environ 256 bits dans un laps de temps raisonnable.

Vous devez factoriser le module, qui est le premier paramètre de la clé publique, 10142789312725007. Brute force fera (vérifier chaque nombre impair de 3 à sqrt (n) si elle est un facteur), bien que des algorithmes plus sophistiqués / rapides existent .

Étant donné que le nombre est trop grand pour entrer dans un entier classique (même 64 bits), vous pouvez une bibliothèque numérique qui supports entiers-lenth arbitraires. C, il y a GMP et MRIP (plus Windows convivial). Pour PHP, il y a Bignum. Python est livré avec un haut-one -. Le haut-type de données entier est déjà longueur arbitraire

Il y a beaucoup de mauvaises spéculations sur factorisation de grands nombres premiers demi qui vont en force brute ou tamiser ni qui est nécessaire pour factoriser les demi prime. 64 bits prend 1 - 2 secondes sur mon pc, et 256 bits généralement moins de 2 jours

Non affilié à StackOverflow
scroll top