[Python] Créer paire de clé Rsa

Résolu/Fermé
kilian
Messages postés
8731
Date d'inscription
vendredi 19 septembre 2003
Statut
Modérateur
Dernière intervention
20 août 2016
- 2 avril 2005 à 15:07
 pacificator - 21 déc. 2006 à 12:26
Bonjour,

J'aimerais reproduire l'algo décris ici:
http://sebsauvage.net/comprendre/encryptage/crypto_rsa.html (voir "créer une paire de clé")

Mais je fais face à un problème. Je me retrouve devant:
On choisit d tel que 71*d mod 1008 = 1

C'est l'exemple du lien , le soucis est que je dois trouver d en tant que nombre aléatoire. Le seul truc que j'ai trouvé c'est de doner une nouvelle valeur aléatoire à d jusqu'à ce qu'il vérifie la condition donnée au dessus.
Je crois que ça fonctionne chez moi mais ça donne un algo très très lent.

Je vous donne mon bout de code au cas où vous auriez une autre idée (j'ai laissé la correspondance des noms de variable entre l'algo et le code:
class keygen:
	def __init__(self,len_premiers,premiers):  # premiers est une liste de nombres premiers
		ref_p=random.choice(range(0,len_premiers))
		ref_q=random.choice(range(0,len_premiers))
		
		p=premiers[ref_p]
		q=premiers[ref_q]
		
		self.n=p*q
		
		
		test=(p-1)*(q-1)
		self.e=test  #Cette valeur permettra de lancer la boucle en dessous pour trouver la vraie valeur de e
		
		while (test%self.e==0):
			self.e=random.choice(range(0,test))
		
		self.d=0.3333   #Idem, cette valeur sert à lancer la boucle en dessous pour trouver d, c'est pas très élégant mais j'ai pas trouvé mieux
		
		while (self.d)==0.3333 or (self.e*self.d)%test!=1:
			self.d=random.choice(range(len(premiers),1000)) # Et voilà c'est ici que ça coince je crois, ça rend le code très lent


Si vous avez juste une astuce pour trouver d d'une façon plus rapide, faite m'en part.
Merci d'avance :-)

3 réponses

kilian
Messages postés
8731
Date d'inscription
vendredi 19 septembre 2003
Statut
Modérateur
Dernière intervention
20 août 2016
1 523
2 avril 2005 à 15:49
Aaah ça y est j'ai trouvé.
Finalement, j'ai plutôt vérifié tous les nombres (dans une certaine portion d'entiers) qui vérifient:
self.e*x%test==1
où x sont les entiers à vérifier.
Puis j'ai posé une boucle au cas ou cette expression ne marcherais pas avec la valeur la valeur de e dans une certaine plage de x.

Ca donne:
class keygen:
	def __init__(self,len_premiers,premiers):
		ref_p=random.choice(range(0,len_premiers))
		ref_q=random.choice(range(0,len_premiers))
		
		p=premiers[ref_p]
		q=premiers[ref_q]
		
		self.n=p*q
		
		self.d=0
		while not self.d:
			test=(p-1)*(q-1)
			self.e=test
		
			while (test%self.e==0):
				self.e=random.choice(range(2,test))
		
		
			liste=range(len(premiers),len(premiers)+1000)
			liste_d=[]
		
			for nb in liste:
				if ((self.e*nb)%test==1):
					liste_d.append(nb)
		
			try:
				self.d=random.choice(liste_d)
			except:
				pass	


Bon ça génère bien trois nombres, maintenant à savoir si ça génère des clés rsa valides, rien n'est moins sûr :-)
1
Il existe une librairie C qui convient parfaitement pour s'amuser avec RSA: gmp.h (https://www.swox.com/

Elle permet notament de
- travailler avec des nombre de tres grande taille (512, 1024, 2048 bits...)
- trouver facilement des nombres premiers (p et q)
- generer des nombres aleatoires (e)
- faire une inversion avec modulo (d)
- calculer une puissance avec modulo (encryption/decryption RSA)

Avec cette librairie, la generation des cles devient simplissime...
1
kilian
Messages postés
8731
Date d'inscription
vendredi 19 septembre 2003
Statut
Modérateur
Dernière intervention
20 août 2016
1 523
3 nov. 2006 à 22:40
Même si ma question date d'il ya un an, je te remercie, car ma curiosité sur ce sujet est toujours d'actualité :-)
0
Il existe la lib pyCrypto et ezPyCrypto qui l'interface de maniere plus pythonique.
1