Accueil > > > GENERATEUR DE CLEF RSA, TRÈS EFFICACE !
 GENERATEUR DE CLEF RSA, TRÈS EFFICACE !
 Information sur la source
 Description
Bonjour, Voila une petite pièce de code qui vous permettra de générer la clef privée et public, pour du RSA. J'utilise l'algorithme de Miler et Rabin afin de générer d'énorme clef en un rien de temps (chance d'erreur de 2^(-80) (sur 1) pour un nombre premier de de 1024 bits. Ensuite on crée la clef RSA.
 Source
- # -*- coding: cp1252 -*-
- from random import randrange
- import time
-
- def ModularExponantiation_old(base, exposant, module):
- resultat = 1
- while exposant:
- if exposant&1:
- resultat = (resultat * base) % module
- exposant >>= 1 #petit changement de ma part, je remplace "exposant/=2" : plus efficace
- base = (base*base) % module
- return resultat
- def ModularExponantiation(base, exposant, module):
- return pow(base, exposant, module)
-
- def invMOD(N,D):
- x=0; y=1;
- u=1; v=0;
- a=N; b=D;
- while (0 != a):
- q = int(b/a);
- r = b%a;
- m = x - u*q;
- n = y - v*q;
- b=a; a=r; x=u; y=v; u=m; v=n;
- return b == 1 and ((x+D)%D) or None
-
-
- def gcd(a,b): #revoit le plus grand dénominateur commun !
- if not b: return a
- else: return gcd(b,a%b) #Plus compliqué qu'il en à l'air :p
-
- def Miller_Rabin_Optimized (n,k):#ATTENTION !! n doit être impaire ! Je n'ai pas mis de verification pour des raisons d'optimisation
- d=(n-1)>>1 # Ici, on met n-1 sous la forme de "d*2^S" ou d est impair
- s=1 #et puisque n-1 est pair on commence directement aves S=1 et d/2 (performance)
- while not d&1 : # on verifie si d est paire ; plus efficace que d%2
- s+=1 #
- d>>=1 # on divise d par deux ; plus efficace que d/=2
- while k : #on verifie autant de fois que k
- k-=1
- a=randrange(1,n) #on genere un chiffre entre 1 et n !!!!! BESOIN d'optimisation !!!!
- if ModularExponantiation(a,d,n)!=1: #si a^d%n!=1 alors n est peut être composé (!=premier)
- while s: #on verifie avec tout les possibilités entre 0 et s-1 compris
- s-=1
- if ModularExponantiation(a,d<<s,n)!=n-1: # si a^(d*2^r)%n!=n-1 alors, n est composé !
- return True
-
- return False # si n passe tout les test on le considère comme premier (voir exception sur wikipedia)(ca n'arrive jamais !)
-
- def generate (e,p,a=1) :
- pre=1<<e
- pre2=pre>>a
- pre2+=1
- r1=True
- while r1 : #on essais jusqu'à ce que ca marche !
- t=randrange(pre2,pre,2)
- r1=Miller_Rabin_Optimized(t,p) #chance d'erreur : 2**-80
- return t
-
-
- def generate_key(lengh=1024,nombredetest=44,marge=1): #generation de la clef
- PRIME_p,PRIME_q=generate(lengh/2,nombredetest,marge),generate(lengh/2,nombredetest,marge)
- PRIME_n=PRIME_p*PRIME_q
- PRIME_totient=(PRIME_p-1)*(PRIME_q-1)
- PRIME_e=1
- while 1 :
- PRIME_e+=1
- if gcd(PRIME_totient,PRIME_e) == 1: #utilise le pgdc pour verifier si le totient et e sont coprimes
- break
- PRIME_d=invMOD(PRIME_e,PRIME_totient)
- return ((PRIME_n,PRIME_e),(PRIME_n,PRIME_d))#renvoie les couples de clef privée et clef publique :p
-
- def crypt(m,PRIME_n,PRIME_e):
- "m,PRIME_n,PRIME_e | send c"
- return ModularExponantiation(m,PRIME_n,PRIME_e)
-
- def decrypt(m,PRIME_n,PRIME_d):
- "c,PRIME_n,PRIME_d | send c"
- return ModularExponantiation(m,PRIME_n,PRIME_d)
-
- #psyco boost les performances, je gagne au moins 40%
- try :import psyco
- except :print "Installez Psyco pour un boost de performance"
- else :
- psyco.bind(generate_key)
- psyco.bind(generate)
- psyco.bind(randrange)
- psyco.bind(Miller_Rabin_Optimized)
- psyco.bind(gcd)
- psyco.bind(ModularExponantiation)
- psyco.bind(invMOD)
- print "import psyco OK...",
-
-
- if __name__ == "__main__": #benchmark
- uo=generate_key(512,72,1024)
- print "\nn=%s\ne=%s\nd=%s"%(uo[0][0],uo[0][1],uo[1][1])
- input()
# -*- coding: cp1252 -*-
from random import randrange
import time
def ModularExponantiation_old(base, exposant, module):
resultat = 1
while exposant:
if exposant&1:
resultat = (resultat * base) % module
exposant >>= 1 #petit changement de ma part, je remplace "exposant/=2" : plus efficace
base = (base*base) % module
return resultat
def ModularExponantiation(base, exposant, module):
return pow(base, exposant, module)
def invMOD(N,D):
x=0; y=1;
u=1; v=0;
a=N; b=D;
while (0 != a):
q = int(b/a);
r = b%a;
m = x - u*q;
n = y - v*q;
b=a; a=r; x=u; y=v; u=m; v=n;
return b == 1 and ((x+D)%D) or None
def gcd(a,b): #revoit le plus grand dénominateur commun !
if not b: return a
else: return gcd(b,a%b) #Plus compliqué qu'il en à l'air :p
def Miller_Rabin_Optimized (n,k):#ATTENTION !! n doit être impaire ! Je n'ai pas mis de verification pour des raisons d'optimisation
d=(n-1)>>1 # Ici, on met n-1 sous la forme de "d*2^S" ou d est impair
s=1 #et puisque n-1 est pair on commence directement aves S=1 et d/2 (performance)
while not d&1 : # on verifie si d est paire ; plus efficace que d%2
s+=1 #
d>>=1 # on divise d par deux ; plus efficace que d/=2
while k : #on verifie autant de fois que k
k-=1
a=randrange(1,n) #on genere un chiffre entre 1 et n !!!!! BESOIN d'optimisation !!!!
if ModularExponantiation(a,d,n)!=1: #si a^d%n!=1 alors n est peut être composé (!=premier)
while s: #on verifie avec tout les possibilités entre 0 et s-1 compris
s-=1
if ModularExponantiation(a,d<<s,n)!=n-1: # si a^(d*2^r)%n!=n-1 alors, n est composé !
return True
return False # si n passe tout les test on le considère comme premier (voir exception sur wikipedia)(ca n'arrive jamais !)
def generate (e,p,a=1) :
pre=1<<e
pre2=pre>>a
pre2+=1
r1=True
while r1 : #on essais jusqu'à ce que ca marche !
t=randrange(pre2,pre,2)
r1=Miller_Rabin_Optimized(t,p) #chance d'erreur : 2**-80
return t
def generate_key(lengh=1024,nombredetest=44,marge=1): #generation de la clef
PRIME_p,PRIME_q=generate(lengh/2,nombredetest,marge),generate(lengh/2,nombredetest,marge)
PRIME_n=PRIME_p*PRIME_q
PRIME_totient=(PRIME_p-1)*(PRIME_q-1)
PRIME_e=1
while 1 :
PRIME_e+=1
if gcd(PRIME_totient,PRIME_e) == 1: #utilise le pgdc pour verifier si le totient et e sont coprimes
break
PRIME_d=invMOD(PRIME_e,PRIME_totient)
return ((PRIME_n,PRIME_e),(PRIME_n,PRIME_d))#renvoie les couples de clef privée et clef publique :p
def crypt(m,PRIME_n,PRIME_e):
"m,PRIME_n,PRIME_e | send c"
return ModularExponantiation(m,PRIME_n,PRIME_e)
def decrypt(m,PRIME_n,PRIME_d):
"c,PRIME_n,PRIME_d | send c"
return ModularExponantiation(m,PRIME_n,PRIME_d)
#psyco boost les performances, je gagne au moins 40%
try :import psyco
except :print "Installez Psyco pour un boost de performance"
else :
psyco.bind(generate_key)
psyco.bind(generate)
psyco.bind(randrange)
psyco.bind(Miller_Rabin_Optimized)
psyco.bind(gcd)
psyco.bind(ModularExponantiation)
psyco.bind(invMOD)
print "import psyco OK...",
if __name__ == "__main__": #benchmark
uo=generate_key(512,72,1024)
print "\nn=%s\ne=%s\nd=%s"%(uo[0][0],uo[0][1],uo[1][1])
input()
 Conclusion
Les clef en sortie peuvent être utilisés. Je m'impressionne moi-même, je ne pensait pas arriver à quelque chose comme ca :p
Je conseille d'installer psyco qui optimise le code (pour le 1536 RSA, je passe de 256s à 116s)
 Historique
- 21 août 2009 18:49:16 :
- optimisation du code et clarification. (de beaucoup)
- 21 août 2009 19:00:22 :
- Supression d'un petit problème qui rendait le code facillement crackable en utilisant l'attaque de Wiener.
- 21 août 2009 21:56:51 :
- changement radical d'architecture +plein de commentaires !
- 27 août 2009 18:15:38 :
- Petite correction grâce au commentaire de THILP
- 29 août 2009 11:13:50 :
- Ajout de la fonction "cryptage" et "décryptage", Très rapide grâce à la fonction de THILP.
- 29 août 2009 17:49:37 :
- modification, voir la discussion ci dessous pour plus d'information..
- 09 septembre 2009 13:59:06 :
- Ajout d'un nouvel algorithme pour la génération des nombre premiers !
Tout est plus simple !!
- 09 septembre 2009 15:04:21 :
- ajout de commentaire + psyco !
- 12 novembre 2009 22:49:32 :
- optimisation
 Sources du même auteur
CALCULATRICE, INTRODUCTION AU LAMBDACALCULATRICE, INTRODUCTION AU LAMBDA
Ca fait plusieurs fois que je voix que des personnes ne savent pas utiliser le lambda en python.
c'est pourtant très important ! Je vais donc vous ...
SERVEUR WEB EN PYTHON.SERVEUR WEB EN PYTHON.Voila j'ai deja poster un ptit serveur en carton :(
mais bon la j'ai fait quelque chose d'un peut plus "interessant" (je crois), j'ai essayer de ga...
SERVEUR HTTP PYTHONSERVEUR HTTP PYTHON
Je me suis amusé, à creer un semblant de serveur "http".
Le programme ouvre le port 80,
il attent que le WebBroswer utilise ce port,
il recupère ...
SPAMMEUR, PYTHONSPAMMEUR, PYTHONBon, ce logiciel ne doit pas être utilisé, il montre seulement comment utiliser smtplib pour envoyer de multiples messages, j'ai essayer, et cela marc...
INTERFACE GRAPHIQUE POUR EN CREER D'AUTRE....INTERFACE GRAPHIQUE POUR EN CREER D'AUTRE....
Essenciel :
je vous explique les utilitaires (même si il n'y en pas besoin...) :
Onglet apparence :
couleur relief :
1 couleur de la p...
 Sources de la même categorie
 Commentaires et avis
|
Derniers Blogs
 NDEPEND V3. J'ADORE SON INTéGRATION AVEC VS2010NDEPEND V3. J'ADORE SON INTéGRATION AVEC VS2010 par tja
Après une petite introduction à son utilisation que vous pouvez lire ici j'ai également eu envie d'installer ma copie et de jouer un peu avec. Après les premières minutes de son utilisation. J'ai tout de suite ADORE. L'utilisation intuitive sans besoi...
Cliquez pour lire la suite de l'article par tja XNA 4.0 POUR CRéER DES JEUX 3D SOUS WINDOWS PHONE 7 SERIESXNA 4.0 POUR CRéER DES JEUX 3D SOUS WINDOWS PHONE 7 SERIES par RaptorXP
On savait déjà que le développement d'applications pour Windows Phone 7 Series se ferait par l'intermediaire de Silverlight et XNA. Les détails, et outils de développement (selon cetaines rumeurs) sont attendus pour le MIX10 la semaine prochaine à Las...
Cliquez pour lire la suite de l'article par RaptorXP [TOOLS] NDEPEND 3 DANS VISUAL STUDIO, WAAAAAAAOU!!![TOOLS] NDEPEND 3 DANS VISUAL STUDIO, WAAAAAAAOU!!! par JeremyJeanson
NDepend passé en version 3. Comme pour toute version majeur, la version 3 a son lots de nouveautés : performances, fonctionnalités accrues . etc . Mais dans tout cela il y a la fonctionnalité qui dénote. Le petit truc qui fait que NDepend me fait dire Waa...
Cliquez pour lire la suite de l'article par JeremyJeanson [WF4] GROSSES MéPRISES EN PERSPECTIVE SUR LE KIT DE MIGRATION WF3->WF4[WF4] GROSSES MéPRISES EN PERSPECTIVE SUR LE KIT DE MIGRATION WF3->WF4 par JeremyJeanson
Comme un certain nombre de fanatiques des flux RSS, je suis avec grand intérêt les articles de la team WCF/WF et forcément l'annonce d'hier concernant un kit de migration WF3->WF4 m'a fait chaud au c½ur ;) (pour rappel, mon post au sujet de la migratio...
Cliquez pour lire la suite de l'article par JeremyJeanson RéUNION DU CLUB MOSS PARISRéUNION DU CLUB MOSS PARIS par VANNESTE Xavier
Bonjour à tous la réunion du club moss aura lieu le 15 mars 2010 à 14 heures:
14:00 - 14:05 Paris, EROL GIRAUDY + Gaetan BOUVERET + Nicolas Georgeault intro Présentateur : Pierre Erol GIRAUDY14:05 - 14:30 Paris, Worflow - visio Services - We...
Cliquez pour lire la suite de l'article par VANNESTE Xavier
Forum
 MCD LYCéMCD LYCé par Wiliam123
Cliquez pour lire la suite par Wiliam123
Logiciels
 Rigs of Rods (63.3)RIGS OF RODS (63.3)c'est un jeu de multi-simulation camions,autobus voitures, avions, bateaux, hélicoptère avec défo... Cliquez pour télécharger Rigs of Rods Konvertor (4.00)KONVERTOR (4.00)Le logiciel est un gestionnaire multimedia affichant, jouant et convertissant plus de 2000 format... Cliquez pour télécharger Konvertor Xlite (v 3.0 build 41150)XLITE (V 3.0 BUILD 41150)c'est un logiciel qui permet de téléphoner par Internet à l'aide d'un compte SIP pratique pour le... Cliquez pour télécharger Xlite Academy System (10.9.3.0)ACADEMY SYSTEM (10.9.3.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System
|