Posez votre question Signaler

[Python] Créer paire de clé Rsa [Résolu]

kilian 8802Messages postés 19 septembre 2003Date d'inscription 2 juillet 2011Dernière intervention - Dernière réponse le 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 :-)
Lire la suite 

[Python] Créer paire de clé Rsa »

4 réponses
Réponse
+0
moins plus
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 :-)
Ajouter un commentaire
Réponse
+0
moins plus
Il existe une librairie C qui convient parfaitement pour s'amuser avec RSA: gmp.h (http://www.swox.com/gmp/)

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...
kilian- 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é :-)
Ajouter un commentaire
Réponse
+0
moins plus
Il existe la lib pyCrypto et ezPyCrypto qui l'interface de maniere plus pythonique.
Ajouter un commentaire
Ce document intitulé « [Python] Créer paire de clé Rsa » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.
Dossier à la une
Passage au tout numérique : quel coût pour les particuliers ?