Forum de mathématiques - Bibm@th.net

Golgup

Membre actif

Inscription : 09-07-2008

Messages : 574

Petite incompréhension sur le rsa.

Bonjour,

Je vous avoue être un peu perdu.. oui, un site qui parle de RSA montre l'exemple si dessous;

Prenons 2 nombres premiers au hasard: p = 29, q = 37

On calcul n = pq = 29 * 37 = 1073

On doit choisir e au hasard tel que e n'ai aucun facteur en commun avec (p-1)(q-1):

(p-1)(q-1) = (29-1)(37-1) = 1008

On prend e = 71

On choisit d tel que 71*d mod 1008 = 1

On trouve d = 1079

On a maintenant nos clés :

La clé publique est (e,n) = (71,1073)   (=clé d'encryptage)
La clé privée est (d,n) = (1079,1073)   (=clé de décryptage)

On va encrypter le message 'HELLO'. On va prendre le code ASCII de chaque caractère et on les met bout à bout:

m = 7269767679

Ensuite, il faut découper le message en blocs qui comportent moins de chiffres que n. n comporte 4 chiffres, on va donc découper notre message en blocs de 3 chiffres:

726 976 767 900
(on complète avec des zéros)

Ensuite on encrypte chacun de ces blocs:

726^71 mod 1073 = 436
976^71 mod 1073 = 822
767^71 mod 1073 = 825
900^71 mod 1073 = 552

Le message encrypté est 436 822 825 552. On peut le décrypter avec d:

436^1079 mod 1073 = 726
822^1079 mod 1073 = 976
825^1079 mod 1073 = 767
552^1079 mod 1073 = 900

C'est à dire la suite de chiffre 726976767900.
On retrouve notre message en clair 72 69 76 76 79 : 'HELLO'.

Pouvez-vous me dire pourquoi en appliquant :[tex]M=C^e(mod N)[/tex]  je peut ici retrouver le message initial?! (j'ai testé avec l'exemple si dessus et pu reconstituer le message HELLO, par contre j'ai éssayé avec les clés suggérées par l'applet de BibM@th, et là sa marche plus). Ainsi pour l'exemple si dessus:

[tex]436^{71} mod 1073 = 726[/tex]

[tex]822^{71} mod 1073 = 976[/tex]

[tex]825^{71} mod 1073 = 767[/tex]

[tex]552^{71} mod 1073 = 900[/tex]

PS: J'ai remarqué que certaines clés fabriquées par l'applet de BibM@th ne répondaient pas à: ed mod (p-1)(q-1)=1, quelques fois il met  ed mod (p-1)(q-1)=(p-1)(q-1)-1. Est-ce normal?

@+

Dernière modification par Golgup (21-09-2008 21:03:45)

Golgup

Membre actif

Inscription : 09-07-2008

Messages : 574

Re : Petite incompréhension sur le rsa.

Re,

c'est bon, je sais pourquoi.., on peut décoder avec [tex]M=C^e(mod N)[/tex] tous message encoder. Le probléme c'est que il faut appliquer [tex]M=C^e(mod N)[/tex] plusieurs fois à chaque fois sur le message trouvé jusque à tomber sur le vrai message. Dans l'exemple au dessus, il suffisait de décoder une seule fois! Merci quand même.

++

Dernière modification par Golgup (21-09-2008 21:04:58)

Golgup

Membre actif

Inscription : 09-07-2008

Messages : 574

Re : Petite incompréhension sur le rsa.

Bonjour,

Alors, est-ce normal pour les clés fabriquées? Si oui, c'est qu'il ya une régle de création des clés que j'ignore..or..j'aimerai bien être á jour..: )

++