Comment fonctionne le RSA ?

[Yarflam]

Bonjour à tous.
J'ai beau lire et relire des tutoriels sur le RSA, je n'arrive à rien.
Comme ici.

Par exemple :
Je choisi p et q deux nombres premiers.
p=3
q=47

Le calcul de n est n=p*q.
n=141

Le calcul de f est f=(p-1)(q-1)
f=92

Je choisi un nombre premier e.
e=7

Petit calcul inverse 7 mod 92.
7*d=1 % 92 ==> résultat : 79

La clef publique = x^7 % 141
La clef privée = y^79 % 141

Je choisi une valeur x inférieur à n.
x=10

Chiffrement avec la clef publique x^7 % 141
y=139

Déchiffrement avec la clef privée y^79 % 141
z=16
Edit: z=10

X est censé être égale à Z . Ce n'est pas le cas.
A mon avis je n'ai pas bien compris la valeur e ("e premier avec f" ?).

Quelqu'un peut m'expliquer ?
Merci d'avance

[MadHatter]

Ta valeur de e est bonne. "e premier avec f" signifie qu'il faut trouver une valeur de e de manière à ce que e et f soient copremiers, c'est à dire que e et f n'aient aucun autre dénominateur commun que 1 ou -1.

Tu te trompes dans tes calculs finaux.

Reprenons à partir du calcul de d. On utilise :

ed mod (p-1)(q-1) = 1 <=> ed mod f = 1

Avec tes valeurs on obtient bien d = 79.

On a donc :
Clé privée = (d,n) = (79,141).
Clé publique = (e,n) = (7,141).

On chiffre 'HACK' :
HACK = 72656775 en (ASCII).

Ensuite, on passe à l'étape de slicing. Il faut segmenter la séquence en blocs comportant moins de chiffres que n. Ici on a n = 141, du coup on segmentera par des blocs de deux chiffres en complétant par des zéros si nécessaire :
72 65 67 75

On passe au chiffrement avec la clé publique :
On utilise la formule bloc^e mod n .

• 72^7 mod 141 = 27
• 65^7 mod 141 = 53
• 67^7 mod 141 = 73
• 75^7 mod 141 = 111

Notre message 'HACK' chiffré est donc 275373111.

On le déchiffre avec la clé privée :
On utilise la formule bloc^d mod n.

• 27^79 mod 141 = 72
• 53^79 mod 141 = 65
• 73^79 mod 141 = 67
• 111^79 mod 141 = 75

On obtient donc la séquence 72 65 67 75. Ce qui en ASCII nous donne bien 'HACK'.

[Yarflam]

Merci beaucoup !
J'ai tout compris.
Le calcul "139^79 mod 141" vaut bien 10.
Python m'a mal interprété la sortie "math.pow(139,79) % 141".

Par contre, Comment puis-je faire pour calculer une grande puissance ?

[Yarflam]

Chouette j'ai réussi à faire fonctionner mon script python.
Et pour répondre à ma question : pour calculer une grande puissance, il faut utiliser pow() et pas math.pow().

#!/usr/bin/python
#RSA cryptographic system by Yarflam vBeta
import math, random

def yrs_p(yrsv_a,yrsv_b):
yrsv_r=[]
while yrsv_a < yrsv_b:
yrsv_s=2
yrsv_t=1
while yrsv_s < yrsv_a:
yrsv_tmp=float(yrsv_a)/float(yrsv_s)
yrsv_tmp=yrsv_tmp-int(yrsv_tmp)
if yrsv_tmp == 0:
yrsv_t=0
yrsv_s=yrsv_s+1
if yrsv_t == 1:
yrsv_r.append(yrsv_a)
yrsv_a=yrsv_a+1
return yrsv_r

def yrs_mi(yrsv_a,yrsv_n):
yrsv_r=-1
yrsv_i=1
yrsv_t=0
while yrsv_t == 0 and yrsv_i < yrsv_a:
yrsv_i=yrsv_i+1
yrsv_temp=float(1+yrsv_n*yrsv_i)/float(yrsv_a)
yrsv_temp=yrsv_temp-int(yrsv_temp)
if yrsv_temp == 0:
yrsv_t=1
yrsv_r=(1+yrsv_n*yrsv_i)/yrsv_a
return yrsv_r

d=-1
while d == -1:
ga=yrs_p(2,20)
gb=yrs_p(20,50)
p=ga[int(random.random()*len(ga))]
q=gb[int(random.random()*len(gb))]
n=p*q
f=(p-1)*(q-1)
e=ga[int(random.random()*len(ga))]
d=yrs_mi(e,f)

print "p=",p
print "q=",q
print "n=",n
print "f=",f
print "e=",e
print "Modulation inverse = "+str(e)+"*d=1 % "+str(f)+"; R="+str(d)
print "Public key = x^"+str(e)+" % "+str(n)
print "Private key = y^"+str(d)+" % "+str(n)

x=int(raw_input('x < '+str(n)+'; x = '))
y=int(pow(x,e) % n)
z=int(pow(y,d) % n)
print "X="+str(x)
print "Y="+str(int(y))
print "Z="+str(int(z))

http://pastebin.com/J4BdnhsB

Je me demande quand même si dans ma fonction yrs_mi (fonction de modulation inverse), j'ai bien fait d'ajouter une limite (i < a). Si quelqu'un sait reconnaître une modulation inverse sans résultat, comme 3 mod 12, ce serai vraiment sympas

C'est passionnant le RSA !

[Yarflam]

Bonjour.
Je suis en train de programmer une application de cryptage RSA.
Pas publiable pour le moment, je compte l'affiner.

Par contre je partage une application de reverse qui devrait vous intéresser pour des petites clefs publiques.
http://pastebin.com/mdX1b3Qy

Vous indiquez 'n' et il vous trouve p & q. E vous le connaissez déjà avec la clef publique. Y a plus qu'à calculer
NB : Ce script est provisoire et je compte bien augmenter la vitesse de déchiffrage d'une clef publique RSA.

[@luther]

Il est cool ton explication MadHatter, simple et rapide, comme je les aimes

[skophiz]

Par contre, Comment puis-je faire pour calculer une grande puissance ?

Ceci peut aider pour calculer des puissances avec de grand nombre A et B, modulo N ((A^B)%N).


En esperant t'aider !

[fred]

Ceci peut aider pour calculer des puissances avec de grand nombre A et B, modulo N ((A^B)%N).


En esperant t'aider !

Je ne pense pas, déjà c'est un grand déterrage, ensuite il a trouvé la solution, et elle devait être en python (langage de programmation)

Je ferme le topic !