Cryptographie - Introduction à RSA

---

le système RSA

Le premier algorithme de chiffrement à clé publique (chiffrement asymétrique) a été développé par R.Merckle et M.Hellman en 1977. Il fut vite rendu obsolète grâce aux travaux de Shamir, Zippel et Herlestman, de célèbres cryptanalistes.

En 1978, l'algorithme à clé publique de Rivest, Shamir, et Adelman (d'où son nom RSA) apparaît. Cet algorithme servait encore en 2002 à protéger les codes nucléaires de l'armée américaine et russe.

fonctionnement de RSA

Le fonctionnement du cryptosystème RSA est basé sur la difficulté de factoriser de grands entiers.

Soit deux nombres premiers p et q, et d un entier tel que d soit premier avec (p-1)*(q-1)). Le triplet (p,q,d) constitue ainsi la clé privée.

La clé publique est alors le doublet (n,e) créé à l'aide de la clé privée par les transformations suivantes :

n = p * q
e = 1/d mod((p-1)(q-1))

Soit M, le message à envoyer. Il faut que le message M soit premier avec la clé n. En effet, le déchiffrement repose sur le théorème d'Euler stipulant que si M et n sont premiers entre eux, alors :

Mphi(n) = 1 mod(n)

Phi(n) étant l'indicateur d'euler, et valant dans le cas présent (p-1)*(q-1).

Il est donc nécessaire que M ne soit pas un multiple de p, de q , ou de n. Une solution consiste à découper le message M en morceaux M_i tels que le nombre de chiffres de chaque M_i soit strictement inférieur à celui de p et de q. Cela suppose donc que p et q soient grand, ce qui est le cas en pratique puisque tout le principe de RSA réside dans la difficulté à trouver dans un temps raisonnable p et q connaissant n, ce qui suppose p et q grands.

En pratique...

Supposons qu'un utilisateur (nommé Bob) désire envoyer un message M à une personne (nommons-là Alice), il lui suffit de se procurer la clé publique (n,e) de cette dernière puis de calculer le message chiffré c :

c = Me mod(n)

Bob envoie ensuite le message chiffré c à Alice, qui est capable de le déchiffrer à l'aide de sa clé privée (p,q,d) :

M =  Me*d mod(n) = cd mod(n)

Discussions pertinentes trouvées dans le forum

02/04 15h07	[Python] Créer paire de clé Rsa	Développement	21/12 12h26->pacificator	4
12/04 03h57	DES RSA quelles combinaisons?	Développement	15/04 12h37->Pascal	12
31/10 16h16	Explication a RSA	Développement	03/11 22h42->cryptoman	9
20/05 11h36	je cherche un programme de cryptage RSA	Développement	02/12 17h50->BOYER	8
30/07 15h05	Intégrité du système RSA	Windows	31/07 13h48->sebsauvage	7
16/04 16h28	"mod" dans l'article sur le RSA ? mod(n)	Windows	16/04 17h30->castor	4
19/07 19h40	rsa problem	Développement	20/07 19h52->lamiah	3
14/07 15h13	recherche l'annuaire pour rsa	Windows	15/07 15h46->bcroitor	2
04/05 17h54	RSA	Développement	05/05 13h16->leosqual	2
22/10 23h57	RSA	Windows	23/10 09h10->Tittom	1
Discussion fermée Problème résolu		Plus de discussions sur « RSA »

Ce document intitulé « Cryptographie - Introduction à RSA » issu de l'encyclopédie informatique Comment Ça Marche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.