Cryptage - système RSA

NOMBRES - Curiosités, théorie et usages Accueil / Dictionnaire / Rubriques / Index / Atlas / Références / Nouveautés ORIENTATION GÉNÉRALE - *M'écrire* - Édition du: 18/12/2009
Débutants Général	THÉORIE DES NOMBRES Cryptographie				Glossaire Général
	CLASSIQUES
	Message	Lettres	Clé publique	RSA
	Codage	Bureau 47	Pig Pen
Sommaire de cette page >>> BASES >>> EXEMPLE >>> THÉORIE

CHIFFREMENT RSA

ou codage ou cryptage RSA

Pourquoi ça marche

- Un fonction non réversible: puissance

- Difficulté à factoriser les grands nombres

Voir principes en Clé publique

BASES

Tu veux me transmettre la valeur x

Je te transmets sans précaution la clé publique (e et n).

Tu t'en sers pour crypter le message.

Tu me le transmets: y

Je suis le seul à pouvoir décrypter car j'ai la clé privée.

· x est la valeur que tu veux coder (tu découpes le message de façon que
x < n).

· e et n sont les deux éléments de la clé publique.

· Tu enfouis x dans un calcul qui donne y.

· y est la valeur transmise.

· Je calcule z

en utilisant ma clé privé d.

· Après ce tour de passe-passe mathématique.

· Il se trouve que z est égal à x.

En effet

z =

y^d mod n

(x^e mod f)^d mod n

x^ed mod n
x¹ mod n
x

<= Voici le calcul

· La justification précise est un peu plus compliquée.

· Tout tient dans le choix de e et f.

· Voir l'exemple ci-dessous.

Voir Théorie du modulo

EXEMPLE

*Ma sauce à moi* *(préparation des clés)*
· Deux nombres premiers tenus secrets	p et q	3 et 7
· Son produit n est diffusé	n = p.q	n = 21
· On calcule f	f = (p-1) (q-1)	f = 2x6 = 12
· Un nombre e est, lui aussi, diffusé	e premier avec f	e = 5
· Je calcule d, inverse de e mod f	e.d = 1 mod f	5d = 1 mod 12 5x5 = 1 mod 12 d = 5
*Préparation du message*
· Le message est converti en chiffres · On va coder chaque chiffre	x₁ … x_i … avec x_i < n	x = 2, par exemple
*Codage du message*
· Chaque x est codé par y	y = x^e mod n	y = 2⁵ mod 21 y = 32 mod 21 y = 11
· Les valeurs de y sont transmises	y est transmis	11 est transmis
*Déchiffrage*
· Je calcule z	z = y^d mod n	z = 11⁵ mod 21 z = 11 x121x121 mod 21 z = 11 x 16 x 16 mod 21 z = 11 x 256 mod 21 z = 11 x 4 mod 21 z = 44 mod 21
· Car en fait	z = x mod n	z = 2 mod 21

THÉORIE

Quelques rappels théoriques

· La fonction phi (n) est la quantité d'entiers strictement positifs inférieurs à n et premier avec n

Théorème de Fermat-Euler

Si a est premier avec m, alors

La notation ci-dessus est la plus formelle; on peut se permettre de simplifier lorsqu'il n'y a pas confusion. Ce sera le cas ci-dessous.

· La démonstration ci-dessous est valable pour le cas général où x est premier avec n. On peut montrer que le procédé reste valable même dans les autres cas

RSA - Raisonnement

· Il s'agit de prouver le raisonnement suivant:

z =

y^d mod n

x^ed mod n
x

*Quelques calculs préalables*
· On se souvient que	f =		(p - 1) (q - 1)
· C'est l'indicateur d'Euler ou fonction phi de n	f =		(n)
· On a également	e.d= =		1 mod f 1 mod (n)
· Ce qui veut dire que e.d - 1 est un multiple de phi	e.d - 1 =		k . (n)
*Expression de z*
· Si on revient à z	z =	y^d mod n (x^e )^d mod n x^{e . d} mod n
· On ajoute un facteur en x que l'on retire dans l'exposant	z =	x . x^{e . d - 1} mod n
· On connaît la valeur de cet exposant	z =
· Il est temps d'appliquer le théorème de Fermat-Euler	z =	x . (1) mod n x . mod n
· Or on a choisit x < n	z =	x