CodeS-SourceS est hébergé par Frontier.fr

Ce site au démarrage

begin process at 2012 05 24 00:24:54

Accueil Codes Tutoriels Forum Livres Emploi Services Connexion

Trouver un code source :

dans

[ Dernières recherches ]

Accueil >

Math & Algorithmes

> GENERATEUR DE CLEF RSA, TRÈS EFFICACE !

GENERATEUR DE CLEF RSA, TRÈS EFFICACE !

Information sur la source

Note :

7,00 / 10

Catégorie :Math & Algorithmes Classé sous :prime number, RSA, nombre premier, Miler Rabin Niveau :Expert Date de création :16/06/2009 Date de mise à jour :12/11/2009 22:49:32 Vu :8 791

Auteur : xeolin

Ecrire un message privé

Site perso

Commentaire sur cette source (37)

Ajouter un commentaire et/ou une note

Description

Cliquez pour voir la capture en taille normale

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

THE GAME OF LIFE, AVEC IMPLÉMENTATION GRAPHIQUE

CALCULATRICE, INTRODUCTION AU LAMBDA

SERVEUR WEB EN PYTHON.

SERVEUR HTTP PYTHON

SPAMMEUR, PYTHON

Toutes les sources de xeolin

Sources de la même categorie

MISE EN EVIDENCE DE L'ALGORITHME A STAR GRAPHIQUEMENT par Mints

BASE64 ENCRYPT/DECRYPT PYTHON BY MAXOU56800 par Maxou56800

TRIANGULATION par mecrosoft

COURBE DE BEZIER par mecrosoft

CALCUL D'AIRE D'UN TRIANGLE [INTERFACE GRAPHIQUE] par SeventhSon

Toutes les sources de la catégorie Math & Algorithmes

Sources en rapport avec celle ci

HIDS EN PYTHON par KimbleMandel

NOMBRES PREMIERS, LISTES, NOMBRES PREMIERS JUMEAUX, CONJECTU... par Julien39

Commentaires et avis

Commentaire de OlivierH le 18/06/2009 10:57:32

Merci beaucoup.

Depuis un moment, je voulais me pencher sur python, voici la bonne occasion.
Je vais donc regarder ce code avec beaucoup d'intérêt, et c'est vrai, merci beaucoup pour ce code et pou megaupload.. ;)

Commentaire de xeolin le 19/06/2009 18:45:01

Je te conseil d'aller sur Wikipédia et de voir comment on fait pour avoir une clef RSA. Tu pourras comparer si tu veux.

De plus la fonction de la ligne 88 à 98 sert a trouver le plus grand dénominateur commun (ce code n'est pas de moi), chose que j'ai fait de la ligne 58 à 98, mais de manière beaucoup moins efficace, tellement, que lorsque j'ai voulu l'implémenter pour trouver d, le procédé était beaucoup trop lent.

De plus je ne comprend pas ce bout de code (88 98), mais je l'ai tout de même mis pour des raisons d'optimisation.

De plus ne prend pas ce code comme référence, il à été fait un gamin de 17 ans qui ne comprend pas totalement les mathématiques derrière le RSA. De plus ce code ne sert qu'à la génération des code et pas à leur utilisation...

Enfin si tu veux apprendre le python, je te conseille l'excellent livre de Gérard Swimen "apprendre a programmer avec python, quoi que si tu programme déjà tu le trouveras surement longuet...

En tout cas si tu veux me contacter, fait le par mp...

Commentaire de Julien39 le 27/06/2009 07:50:42 administrateur CS 5/10

Pour le code des lignes (88 98), il n'y a rien à comprendre, c'est un algorithme mathématique, si tu cherches sur google calcul du PGCD, tu le trouvera certainement. Il a un nom cet algo mais il m'échappe por le moment.

Juste une remarque, ce code n'est vraiment pas à ranger dans la catégorie expert, mais ce n'est pas très grave.

Je vais te mettre un 5/10, j'aurais mis plus si tu avais f'avantage commenté

Commentaire de xeolin le 28/06/2009 20:08:47

Julien39, donnerais sérieusement ce code à un débutant ?? Le fait est que s'il est rangé dans la section expert, c'est à cause de la complexité de l'algorithme RSA. Il est inutile de le classer dans une catégorie inférieure puisque les codeur de cette catégories ne comprendront pas le code.lllll

Et ensuite ta remarque est inutile sur mon script du PGDC et pas PGCD : "plus grand dénominateur commun" puisque je l'ai déjà dit, je ne le comprend pas et je ne veut pas le comprendre parce que j'ai fait l'équivalent plus tôt, je ne l'est utilisé seulement pour des raisons d'optimisation.

Et finalement ton "il n'y a rien à comprendre" est pitoyable, ce n'est pas parce que c'est des math que c'est inutile : il y a une démarche d'optimisation mathématique très intéressante derrière ce script, et puis, ne me prend pas pour un idiot je sais très bien comment l'utiliser.

S'il te plait, à l'avenir évite d'avoir des commentaires si inutiles. A tu vraiment lu mes commentaire plus haut, puisque tout ce que je vient de dire était déjà écrit...

N3Ar

Commentaire de Julien39 le 07/07/2009 13:39:16 administrateur CS

Je ne pensais pas avoir été agressif, si je t'ai blessé, je m'en excuse.
Et je ne t'avais pas pris pour un idiot, je savais très bien que tu maitrisais ton code. C'est juste que les démonstration mathématiques ne sont pas nécéssaires à la compréhension.

et PGCD c'est "plus grand commun diviseur" (question de notation) :)

Et pour le "reverse ingeniering" ce n'est pas que c'est impossible mais que personne n'a encore trouvé le moyen de le faire, c'est peut être impossible mais personne n'a démontré non plus que ca l'était.

Voilà tout.

Commentaire de xeolin le 17/07/2009 14:18:39

En fait il a été démontré que c'était impossible..
Mais bon c'est pas grave...

Commentaire de thilp le 25/08/2009 14:04:29

Xeolin, deux choses : d'abord, tu écris :
"Mes clef sont de l'ordre de 50 bits. Les vraies clef sont au minimum 128 bits... Voir 256 pour le top secret Américain... C'est pas comparable..."
Mais une clef RSA "normale" est bien plus grande, au minimum, aujourd'hui, 1024 bits ! Il se trouve que tu confonds les deux types de clefs : les clefs utilisées par RSA (et, de façon générale, en cryptographie à clef publique) et celles utilisées par les algorithmes à clef secrète (DES, AES et compagnie). Les agences américaines, qui utilisent AES, le font effectivement avec des clefs de 128 ou 256 bits ; mais une clef secrète de 256 bits est nettement plus sûre qu'une clef publique de 1024 bits ! C'est parce qu'on ne les casse pas de la même manière : pour casser des algorithmes de type AES, on se sert de méthodes complexes comme cryptanalyses linéaire et différentielle, alors qu'il suffit de factoriser une clef publique pour découvrir le message chiffré avec RSA. Alors oui, une clef publique de 50 bits est très, très faible (moins d'une seconde suffit à la casser avec mon vieil ordi), mais 128 bits ne résistent qu'un peu moins de 30 secondes sur la même machine. En revanche, on a jamais factorisé rapidement du 1024 bits.
J'ai déjà parlé de la deuxième chose : les agences américaines n'utilisent pas d'algorithme à clef publique (comme RSA) pour protéger leurs données, car ces systèmes ne sont vraiment utiles que lorsqu'il doit y avoir transmission des données, ce qui n'est pas le cas avec les informations classées "top secret".
Et dernière chose :
"Par contre il faut savoir que python n'est pas du tout fait pour ce genre de calculs ! Ca va être über lent ! "
Python calcule aussi bien que le C ou le Java, c'est juste que des calculs du type "élévation à une puissance puis modulo" sont très lourds dès que les nombres grossissent un peu, quel que soit le langage de programmation. Pour contourner ce problème, on utilise des algorithmes particuliers, dont la page "Exponentiation modulaire" de Wikipédia donne un bon aperçu. Avec ces méthodes, mes programmes chiffrent presqu'instantanément un gros volume de données avec RSA ;)
(PS : mais c'était déjà mentionné dans le code :
#we could use : nm=(TC**e)%n, there are some performances issues
#example 65**86273651277423 is quite long to execute... Realy long
#we are going to use the Exponentiation_by_squaring see :
#http://en.wikipedia.org/wiki/Exponentiation_by_squaring
#it still freaking long... )

Commentaire de xeolin le 27/08/2009 18:26:17

Merci pour cet éclaircissement, j'ai effectivement mélanger le AES avec cet article : http://fr.wikipedia.org/wiki/RSA-704...
:p Wikipedia donne tellement d'informations... Il était tard quand j'ai fait les modifications, et puis l'erreur est humaine...

"Python calcule aussi bien que le C ou le Java"
Depuis quand un langage interprété à les même performances qu'un compilé ??? Je suis pas du tout d'accort avec toi...

Perso, (c'est pas du tout la même chose) j'utilise C++ et CUDA de NVDIA. Ça change, au lieu d'un dual core de 1,6GHz j'ai 12 c½ur de 625MHz (8400m GS environ 30¤)...

Éclaire ma lanterne, quel algorithme utilises-tu pour avoir de telle efficacité ??? J'utilise la puissance par exponentiation, mais ca prend toujours une plombe...

Et puis j'ai besoin d'un regard extérieur sur mon bout de code qui génère un coprime, j'ai peur de m'y être trompé...

Commentaire de thilp le 29/08/2009 09:55:39

Hi,
Pour la vitesse, excuse-moi, j'ai sans doute tort ; je pensais en fait surtout au "système de calcul" de Python qui est semblable à celui du C, mais j'avais complètement zappé qu'il était ralenti par l'interprétation !

Bon, je suis quand même plutôt débutant en Python, donc il va falloir m'expliquer ce qu'est un "coprime" (jamais entendu parler) ! ;)

Je te copie la fonction que j'utilise pour l'exponentiation modulaire (c'est une adaptation Python hypersimple du code en C# du cryptologue Bruce Schneier via Wikipédia) :

def exponentiationModulaire(base, exposant, module):
        "Cette fonction effectue l'exponentiation modulaire avec \
        les trois nombres (type int) en entrée, et renvoie le \
        résultat (type int).
resultat = 1
while exposant > 0:
if exposant & 1 > 0:
resultat = (resultat * base) % module
exposant >>= 1
base = (base * base) % module
return resultat

Heureusement que Wikipédia est en GFDL =D

Commentaire de thilp le 29/08/2009 09:58:13

(mais où est passée l'indentation ??)
Je recommence :
def exponentiationModulaire(base, exposant, module):
    resultat = 1
    while exposant > 0:
        if exposant & 1 > 0:
            resultat = (resultat * base) % module
        exposant >>= 1
        base = (base * base) % module
    return resultat

Commentaire de xeolin le 29/08/2009 10:50:52

ohhhh !!!

Pas bête d'utiliser des décalages binaires !!

Sinon, les coprime n'on rien à voir avec le python ce sont des pures mathématiques, (et complexes), c'est pour cela que je demande un second avis, car je n'ai aucune façon de savoir si ce qui arrive en sortie est cohérent, (c'est pas comme si je pouvais le faire de tête...). Tu peux trouver des info sur :
http://en.wikipedia.org/wiki/Coprime
http://fr.wikipedia.org/wiki/Nombres_premiers_entre_eux

... Je te peut être embrouiller avec le nom, en francais c'est "Nombres premiers entre eux"

mais bon...

Thilp, as tu déjà fait su cuda ? Mon idée était de faire marcher ce code en python puis le porter sous cuda pour plus de performances... Mais bon je suis un peut bloqué à cause du fait que ma carte graphique n'aime pas les int, mais juste les "string", que je n'ai jamais utiliser...

Commentaire de xeolin le 29/08/2009 10:59:31

WOOOOOOOOOOOOOOOOOOOOOOOW !!!
c'est ridiculement rapide !!
je pensait que ca allait prendre au moin une ou deux minutes ! Mais la c'est de l'ordre de la seconde ! Je suis impressionné !!

bravo Thilp, tu m'impressionnes !

Je vais ajouter la fonction de décryptage aussi.

Commentaire de thilp le 29/08/2009 11:44:56

Mais c'est Bruce Schneier qui a tout fait, pas moi ^^

Ah, je vois : on utilise pas du tout les même notations, d'où l'embrouille ! "Nombres premiers entre eux", ça me va =) Pareil, "totient", j'appelle ça "?(n)". Mais peu importe.

J'ai du mal à comprendre certains bouts de code (comme le fonctionnement de invMOD), mais je sais ce qu'ils sont censés retourner (je suis bien moins bon programmeur que cryptologue, on dirait), donc je m'en sors, mais j'ai une question : pourquoi te compliquer autant la tâche lors de la génération de e ? Si j'ai bien compris (je suis un peu mort), tu décomposes PRIME_totient (mon ?(n)) en produit de nombres premiers, puis tu en pioches dans ta base de données au hasard, et tu ne gardes que ceux qui ne sont pas facteurs premiers de PRIME_totient ?
Je comprends que cela permette d'obtenir un grand e et donc, par conséquent, un "pas trop grand" d, histoire de ne pas griller le processeur lors du décryptage avec des calculs du type 2527**179846482958165 % 899232474998239 (calcul-type de décryptage avec, justement, une clef de 50 bits et un petit e, en l'occurence 5). Mais grâce à l'algo d'exponentiation modulaire, on n'a plus peur de ces calculs, et on peut donc prendre des e égaux à 3, 5, 7 ou 11 ! Ce que je fais généralement, c'est donc un petit test PGCD(?(n),e) avec un e valant 3, puis 5, puis 7, ... etc dans la liste des nombres premiers ; en général, même pas besoin d'aller jusqu'à 13 !
Voilà comment je calcule mes "coprime", c'est peut-être un peu simple, mais rapide et efficace =)

Commentaire de thilp le 29/08/2009 11:46:16

***, on lit "?" à la place de la lettre "phi". C'est "phi(n)", et non "?(n)"

Commentaire de thilp le 29/08/2009 11:55:09

Sinon, non, connais pas le cuda ; je suis en train d'apprendre ce que c'est ;)

Commentaire de xeolin le 29/08/2009 12:19:46

invMOD permet de trouver le plus grand dénominateur commun entre deux chiffre. Pour la formule mathématique, ce n'est pas de moi, mais elle est terriblement efficace !

sinon pour créer e, je bidouille un peut, voila :

Etape 1 :

PRIME_totient_factors=better_crack(PRIME_totient)

je récupère tout les nombres premiers dans PRIME_totient.

Etape 2 :

PRIME_totient_factors_unique=[]
for a in PRIME_totient_factors :
    if a not in PRIME_totient_factors_unique :
       PRIME_totient_factors_unique.append(a)

je retire tout les nombre premiers en "double" de la liste, pourait être plus efficace

Etape 3 :

PRIME_e_list=[]
n=PRIME_totient/4
while len(PRIME_e_list)<750 :
   n+=1
   iscorprime=True
   for num in PRIME_totient_factors_unique :
      if not n%num :
         iscorprime=False
         break
   if iscorprime :
      PRIME_e_list.append(n)

Ici je vais commencer avec n=PRIME_totient/4
car si n<PRIME_totient/4 alors la clef est crackable
ensuite je vais chercher un coprime, et je vais attendre d'en avoir une bonne quantité afin de ne pas avoir un e prévisible, il est vrai que un suffit, mais si on en a plusieurs, cela nous permet :
-de ne jamais tomber deux fois sur la même clef.
-éviter d'avoir sa clef cracké (rumeurs...)

finalement je prend un des e au hasard.

PRIME_e=PRIME_e_list[randrange(0,len(PRIME_e_list)-1)]

Si tu as une manière d'optimiser mon code, dit le, je suis ouvert à toutes propositions.

Commentaire de thilp le 29/08/2009 15:05:03

invMOD(), c'est donc PGCD() !

Ce n'est pas moi qui pourrait optimiser ton code, débutant comme je suis ;) D'autant qu'il m'a l'air particulièrement efficace.

Efficace, oui, mais je suis effaré par les précautions tout-à-fait inutiles que tu prends - ou comment se compliquer la vie. Quel intérêt de porter un programme dans un langage adapté au calcul massivement parallèle (si j'ai tout suivi) s'il est rempli d'algorithmes inutiles ? "Ne pas avoir un e prévisible" ... e est connu de tous, il est fourni avec la clef publique ! De même, n < PRIME_totient/4 ne change rien : e n'a rien à voir avec la sécurité de la clef. Mais ce "divisé par 4" me rappelle quelque chose : tu dois faire une confusion sur la base de l'attaque de Wiener. Il se trouve qu'une clef ne craint rien du côté de e, mais plutôt de d, l'exposant de déchiffrement, s'il est plus petit que la racine quatrième de n. C'est aussi pour cela qu'on prend e petit : pour s'assurer que d, grand par conséquent, sera plus grand que n^(1/4) (n : module de chiffrement).

Sinon, je ne vois rien d'autre, du point de vue algorithmique (parce que du point de vue programmation, il ne faut pas trop compter sur moi) ; mis à part la détermination de e via PGCD des "premiers" nombres premiers et de phi(n), qui me semble plus rapide (mais seulement comme ça, au feeling) que ta méthode de décomposition en facteurs premiers de phi(n), d'élimination et de choix aléatoire. Dans la génération de clef, celle de e est le seul truc qui me chagrine, le reste de ton algorithme doit te donner de bonnes clefs !

Commentaire de xeolin le 29/08/2009 17:47:03

oh ok!
c'est plus logique maintenant!

mais e, quand je prend le premier, il est tout petit... Et donc d est grand... Très grand...

Cependant je trouve bizarre de finir avec un e=5... Normal ?

Je vais mettre cette mise a jour...

Commentaire de xeolin le 29/08/2009 17:58:25

voila comment j'ai fait :
je génère un coprime, le plus petit possible :
ensuite je vais directement trouver d et vérifier que d est supérieur à n^(1/4).

        n=1
        while 1 :
            n+=1
            iscorprime=True
            for num in PRIME_totient_factors_unique :
                if not n%num :
                    iscorprime=False
                    break
            if iscorprime :
                PRIME_e=n
                PRIME_d=invMOD(PRIME_e,PRIME_totient)
                if PRIME_d>(n**(1/4)):
                    break

Je pense que ca va faire l'affaire...
Sinon, merci beaucoup Thilp :p

Tu ferais comment pour décomposer phi(n)(on parle bien du PRIME_totient ici ?), parce que je vois pas trop comment on peut utiliser le pgcd pour cela...
avec qui faut-il utiliser le pgcd???

Commentaire de thilp le 29/08/2009 18:01:03 8/10

Tout-à-fait normal :)

Je l'ai suggéré tout à l'heure : pas besoin de tester le PGCD avec des nombres plus grands que 13, en général ! e vaut effectivement couramment 3, 5, 7, 11 ...
Et ce n'est pas gênant si ça entraîne un grand grand nombre pour d, avec notre génial algorithme d'exponentiation modulaire qui nous résout ça très vite !

Exemple de clef RSA (50 bits, donc ridiculement faible) : (645341527261181 ; 5) pour la clef publique, (645341527261181 ; 258136589826125) pour la clef privée. Tu vois que finir avec e = 5 n'est pas si bizarre ... ;)

Bonne chance pour les modifs !

Commentaire de thilp le 29/08/2009 18:02:02

[conflit d'édit, comme on dit sur Wikipédia]

Commentaire de xeolin le 29/08/2009 18:10:30

ok je pensait pas que les clef publiques avais de si petit e...
Quand je me suis lancé dans ce code, la seule chose que je connaissait, c'était le nom (RSA) et que c'était très utilisé :p

Je savait pas ce qu'était "Indicatrice d'Euler", ce que j'appèle totient à cause de son nom anglais : "Euler's totient function"
ni ce qu'était un coprime (Nombres premiers entre eux) et encore moins ce qu'était "Inverse modulaire".

Mais maintenant je commence à vraiment bien comprendre le principe, en partie grâce à toi Thilp, et mon script commence à avoir une belle tête :p

Commentaire de xeolin le 29/08/2009 18:17:51

Si je veux rendre mon code "utilisable", il me faudrait beaucoup plus de nombres premiers dans ma base de donnée, connais-tu un endroit où je pourrait en télécharger, ou mieux encore, connais-tu une manière de les générer efficacement ??

Commentaire de thilp le 29/08/2009 18:52:38

Je recouds un bouton à ma veste en même temps que je tape, excuse donc la lenteur de ce message ... ;)
En plus, tu poses plein de questions ! Va falloir y répondre ! =D Je plaisante, ça me rappelle moi il y a 2 ans et des poussières, lorsque j'ai aussi découvert RSA, grâce à un exposé en Seconde ; j'avais la tête pleine d'idées complètement contradictoires, mais j'étais ébloui par l'idée du chiffrement inviolable !

D'abord, oui, phi(n) = PRIME_totient - c'est juste une notation, mais je garde la mienne, je la trouve plus jolie, plus pratique, plus claire et plus mathématique.

Histoire de décomposition : on est en train de se mélanger les pinceaux ;)
Le fait est que, si tu poursuis avec ta méthode de décomposition de phi(n), tu n'as pas besoin du PGCD.
Je l'utilise, moi, pour tester si les nombres premiers tirés successivement (3, 5, 7, 11, ...) sont premiers avec phi(n). Si c'est le cas, le PGCD de phi(n) et du e est 1 (= 1 est le plus grand commun diviseur à phi(n) et à e, et c'est ce que l'on veut).
Pour décomposer un nombre, j'utilise un banal algorithme de décomposition en facteurs premiers, que je te copierai si tu veux.

Génération des nombres premiers : comme je suis un grand parano (ça explique mon attirance pour la cryptologie ? :) ), en plus de générer des nombres premiers, je les faisais pseudo-aléatoires, c'était superfacile : génération d'un nombre pseudo-aléatoire (avec random.randrange()), que je rendais encore plus aléatoire (en le "mixant", par des opérations genre multiplication-division entière-modulo, avec d'autres nombres pseudo-aléatoires), puis un bête test de primalité trouvé dans le manuel de ma calculatrice Casio, et s'il était premier, je le gardais.
Mais, à force, je me suis, disons, "amélioré" : et maintenant, je génère toujours un nombre pseudo-aléatoire, mais je le rends "presque" aléatoire en le faisant passer à travers une fonction de hachage (ah, quel morceau passionnant de cryptologie, toi qui ne connais peut-être pas !), et pas n'importe laquelle : la meilleure (selon moi), Whirlpool. Ainsi, j'ai quelque chose de bien plus aléatoire, et donc de bien plus sûr ! Un petit test de primalité là-dessus et, si c'est bon, le tour est joué =)
Mais les nombres premiers aléatoires ne me servent que pour p et q, c'est pourquoi Whirlpool, qui renvoie de grands nombres (2048 bits ou 4096 bits), me convient. Si tu les utilisais pour ta génération de e, tu aurais besoin d'un coup de modulo, pour limiter leur taille.
Mais, pour conclure ce paragraphe, pour générer efficacement des nombres premiers, pas de recette miracle (Wikipédia donne des pistes, mais elles me fatiguent). Génère un grand nombre pseudo-aléatoire, teste-le et utilise-le s'il est premier (ça arrive plus souvent qu'on pense, sauf si tu demandes beaucoup de chiffres).

Bon, c'est tout pour ce soir : je vais à une fête. Bon courage !

Commentaire de xeolin le 29/08/2009 22:15:59

"D'abord, oui, phi(n) = PRIME_totient - c'est juste une notation, mais je garde la mienne, je la trouve plus jolie, plus pratique, plus claire et plus mathématique."
Moi je préfère totient, ca fait plus "anglais" et donc international :p Au cas ou il y aurais un petit zetazunien qui viendrait jeter un coup d'oeuil :p

oh, je vois ce que tu veux dire ! pour e. ok!

je connais pas Mr Whirlpool mais j'ai déjà utiliser son algorithme (sans trop m'en soucier) lorsque j'ai installer truecrypt pour encrypter entièrement mon disque dur principal à travers Twofish (j'aime pas AES parce que il est trop utilisé, et si on essayait de bruteforce mon disque dur ils essayeraient forcément avec AES) avec un mot de passe de 21 caractères. Moi aussi je suis parano :p

Certain appèleraient cela folie car cela (soit disant) ralentirait mes performances disque mais c'est faut !

Truecrypt remplace le vieu bidule de windows par le tout récent driver de Mr Linus Torvald (linux) pour disque dur. Un beau pied de nez à Mr Gate.
Je conseille infiniment à tout les paranos du monde. Hak5 à fait un épisode la dessus. (il y a même une méthode, si tu te fais extorqué et voler ton mot de passe, ca les amènes sur une fausse partition, deux mot de passe)

Sinon, quel algorithme de test de primarité utilises-tu ? (je suis même étonné que ca existe, ca m'évitera de tous les calculer)

Je vais essayer ta méthode pour trouver e...

Commentaire de xeolin le 29/08/2009 23:08:21

j'ai essayé ta méthode pour e, ca marche pas... (j'ai du faire des zerreur sémantiques...) mais la trop fatigué pour réfléchir, donc on verra ca demain :p

Commentaire de thilp le 29/08/2009 23:55:13

Oui, j'adore TrueCrypt ! Tu utilises Twofish et Whirlpool ? Comme je suis entièrement sous Linux, AES-Twofish-Serpent + Whirlpool m'ont semblé le plus sûr, mon iPod contient donc une double partition (dont une cachée) =D
À demain donc.

Commentaire de thilp le 30/08/2009 18:31:54

Des tests de primalité ? Il en existe des tonnes ! Wikipédia est ton amie : http://fr.wikipedia.org/wiki/Test_de_primalité. Je vais essayer d'adapter en Python mon code en CasioBasic (je n'en avais pas besoin, mes quelques programmes ne généraient pas de clef), mais je ne garantis rien ;)

À propos de TrueCrypt, tu peux utiliser AES en toute sécurité : il n'a jamais été cassé, même avec de petites clefs ; et il a été préféré à Serpent et Twofish pour devenir le standard mondial de chiffrement à clef secrète, il est donc plus efficace.

Commentaire de xeolin le 30/08/2009 19:24:04

C'est un choix personnel, c'est vrai que AES est un peu plus sur mais j'ai une couche de protection "sécurité par l'obscurité". Choix purement personnel, et je pense que AES se fera cracker plus vite (même si il est plus résistant) que Twofish car il est sur-utilisé :p

Oui mais wikipedia est vaste et je préfère avoir ton avis, cela m'évitera surement de patauger pendant des heures...

Commentaire de thilp le 05/09/2009 14:45:00

Hum, excuse-moi pour ce retard de réponse ... Du 31 août à hier soir, j'étais à Paris : ma rentrée était le 2, et je ne rentre chez moi qu'en fin de semaine ! :s

J'ai justement commencé à écrire (sur papier) un petit logiciel Python dont je te mets une partie de l'en-tête (je te passe la licence et les remerciements =) ) :

"À l'origine, Libertas est écrit de telle sorte qu'il permet d'exécuter les opérations suivantes :
  - signature électronique d'un texte via les fonctions de hachage MD5, SHA-1, SHA-512 et Whirlpool (pour l'utilisation de cette dernière, le fichier whirlpool.py, fourni à l'origine avec ce programme, est nécessaire)
  - génération de nombres premiers de taille choisissable
  - test de primalité d'un nombre (deux tests sont proposés, qui sont utilisés en fonction de la taille du nombre à tester : test de primalité par divisions successives et test de primalité probabiliste de Miller-Rabin)
  - génération de nombres aléatoires (utilisation de Whirlpool, et donc du fichier whirlpool.py)
  - chiffrement et déchiffrement de données entrées (comme un texte) par Rivest Shamir Adleman (RSA)
  - génération de paires clef publique / clef privée destinées à une utilisation par RSA.

  Dans une version prochaine de Libertas :
  - chiffrement par masque jetable
  - chiffrement de type Pretty Good Privacy (PGP) utilisant Advanced Encryption Standard (AES) et RSA
  - possibilité de chiffrer un fichier entier
  - algorithme de décomposition en facteurs premiers (cassage d'un trousseau de clefs RSA de faible taille)."

Si je le termine, ce qui n'est pas gagné - je me connais assez bien pour savoir que nombre de projets commencés n'ont jamais vu le jour ;) -, c'est sur ce site que je le posterai, tu aura donc tout loisir de voir à quoi ressemblent les tests de primalité utilisés (et de les réutiliser, je n'aime pas les licences propriétaires).

Mais patauge un peu quand même, c'est comme ça que l'on se dépasse ;) Bon courage pour la suite !

Commentaire de xeolin le 05/09/2009 14:55:14

Je suis impacient de voir ce que ca va donner :p

J'ai fait mes petites recherches sur internet et j'ai trouvé un algorithme qui permet de casser n'importe quelle clef RSA.
1500 bits en moin de quelques minutes.

normallement la différence entre 1000 et 2000 bit est exponancielle, mais avec cet algorithme c'est seulement le double. Un petit example :

Normalement :
1000 bits fait en A heures
1500 bits fait en A*2^500 heures.

Avec cet algorithme :
1000 bits fait en A heures
2000 bits fait en A*1.5 heures.

http://fr.wikipedia.org/wiki/Algorithme_de_Shor

Seul problême c'est heu... J'ai pas d'ordinateur quantique à la maison... Mais sinon c'est effrayant !

Xeolin

Commentaire de thilp le 05/09/2009 15:05:48

C'est vrai, on peut, avec ce type de machines, casser RSA ... Sauf que pour le moment, personne n'a d'ordinateur quantique à la maison ! :p

Et ceux qui sont dans les laboratoires de recherche, tu as dû le lire, n'ont été capables de factoriser que 15, car, pour l'heure, ils ne sont pas suffisamment puissants pour faire mieux. Mais c'est un domaine qui se développe bien (au vu des applications envisagées, naturellement), bien que basé sur la physique quantique, et donc effroyablement compliqué ;)

Commentaire de xeolin le 09/09/2009 14:27:39

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

Commentaire de xeolin le 16/10/2009 20:27:41

no comment ?

Commentaire de aera group le 03/11/2009 09:36:52

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

Commentaire de xeolin le 03/11/2009 14:51:07

>> 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

Commentaire de tatitscheff75 le 11/11/2009 21:10:22 8/10

cool

Ajouter un commentaire

Discussions en rapport avec ce code source dans le forum

[Programme Python] Cryptage RSA (cherche codeur) [ par GelH ] Bonjour, Je recherche un codeur Python capable de réaliser un programme de cryptage/décryptage d'une chaine de caractère utilisant l'algorithme RSA.

Nos sponsors

Derniers Blogs

IMAGINE CUP 2012, MAKE A SIGN EN FINALE par junarnoalg

KINECT 1.5 IS OUT ! par Vko

LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) par richardc

REACTIVE EXTENSIONS : CONSOMMER DES SERVICES AVEC RX PARTIE 3, LES PIèGES à éVITER par Groc

SHAREPOINT BLOG SITE, PROBLèME D'ARCHIVES par junarnoalg

Forum

SCRAPING, PYV8 ET JS par makrook

PROGRAMMATION DSK6416 par amounhan

RE : PROBLèME D'APPEL DE VARIABLE DANS UNE FONCTION par AlexOnAir

PROBLèME D'APPEL DE VARIABLE DANS UNE FONCTION par AlexOnAir

RE : SE LOGUER AUTOMATIQUEMENT AVEC SCRIPT PYTHON par Bastien981

Côté IT

Offres d'emploi

Formations Video

Appels d'offres

Creation d-un site ecommerce de vente en ligne de chaussures femmes
Budget : 5 000€
URGENT - Recherche d-un webmaster
Budget : 4 800€
Creation d-un site web ancien etudiant avec Job board
Budget : 1 800€

Logiciels

974 Application Server (12.2.4.0)
974 APPLICATION SERVER (12.2.4.0)

Développez de puissantes applications dans un environnement de 'cloud computing', clusterisé, séc...

Cliquez pour télécharger 974 Application Server
vPicture (1.4.2.1)
VPICTURE (1.4.2.1)

Avec vPicture, hébergez vos images facilement et rapidement. vPicture est un utilitaire simple, ...

Cliquez pour télécharger vPicture
Easy-Planning (2.2.1.6)
EASY-PLANNING (2.2.1.6)

Easy-Planning permet de créer des plannings sous la représentation de diagrammes et est adapté au...

Cliquez pour télécharger Easy-Planning
COM-BACKUP (2.0)
COM-BACKUP (2.0)

COM-BACKUP est un logiciel de sauvegarde qui permet de planifier les sauvegardes de vos dossiers ...

Cliquez pour télécharger COM-BACKUP
mySongBook Player (1.0.0)
MYSONGBOOK PLAYER (1.0.0)

mySongBook Player est un logiciel gratuit permettant l'accès à une archive de tablatures/partitio...

Cliquez pour télécharger mySongBook Player