Generateur de clef rsa, très efficace !

Soyez le premier à donner votre avis sur cette source.

Snippet vu 17 212 fois - Téléchargée 17 fois

Contenu du snippet

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 / Exemple :


# -*- 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)

A voir également

Ajouter un commentaire

Commentaires

Messages postés
2
Date d'inscription
vendredi 19 janvier 2007
Statut
Membre
Dernière intervention
14 novembre 2009

cool
Messages postés
336
Date d'inscription
samedi 26 novembre 2005
Statut
Membre
Dernière intervention
8 novembre 2011
1
>> correspond au décalage binaire.

en faisant : a>>1
ca revient à : a/2

mais on a pas de virgule, mais c'est beaucoup plus rapide...

et psyco c'est une librairie qui boost les performances de ton code, en utilisant c++ et en le compilant on the fly

J'ai fait un véritable effort d'optimisation...

en faisant : exposant&1
ca revient à : exposant%2
Messages postés
382
Date d'inscription
mercredi 23 août 2006
Statut
Membre
Dernière intervention
8 novembre 2010
11
Need help pour comprendre ....

C'est quoi cette opérateur que l'on retrouve partout ">>" (comme ici ligne 32 : d=(n-1)>>1 ou ici ligne 9 : exposant >>= 1) ?
What's psyco ?
Enfin, la méthode du pgcd est jolie, c'est celle des division euclidienne successive ....

ciao
Messages postés
336
Date d'inscription
samedi 26 novembre 2005
Statut
Membre
Dernière intervention
8 novembre 2011
1
no comment ?
Messages postés
336
Date d'inscription
samedi 26 novembre 2005
Statut
Membre
Dernière intervention
8 novembre 2011
1
voila une grosse mise à jour !

Heureusement je me débrouille bien avec les décalage binaires!
Et j'ai trouver le while not d&1 :
Efin avec toutes ces petites optimisation j'ai gagner 25% sur le temps !

(il y a un pourcentage de "chance" puisqu'on tire des chiffres au hasard jusqu'à en trouver un de premier)

avec mon ordi pouris je peut faire :
256 bits RSA en 0.26s
512 bits RSA en 3.2s
768 bits RSA en 3.9s
1024 bits RSA en 18s
1280 bits RSA en 16s
1536 bits RSA en 2min16s
Afficher les 37 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.