[ Yolin | 2003 | Sommaire ]

1.4.2.4.1.4 Principe du théorème d'Euler:

Soient 2 nombres premiers A et B et M leur produit : M=A*B

Alors le produit (A-1)*(B-1) que nous appellerons K a la propriété suivante: quel que soit le nombre X, si on multiplie celui-ci K fois par lui-même (on "l'élève à la puissance K") le résultat est égal à 1 + un nombre multiple de M

(pour les mathématiciens "XK= 1 modulo M"). en fait cette propriété n'est vraie que si X n'est multiple ni de A ni de B mais la probabilité en est quasi nulle puisqu'il s'agit de nombres comportant plusieurs centaines de chiffres décimaux (typiquement M est un nombre qui nécessite 300 chiffres pour l'écrire)

Pour calculer une paire de clé opérationnelle on commence donc par choisir 2 nombres premiers A et B,

Puis on prend 2 nombres S et P (les clés secrètes et publiques) tels que S*P-1 soit un multiple de K donc S*P=nK+1. Les clés S et P sont des nombres gigantesques nécessitant 150 à 300 chiffres pour les écrire (il suffit de 31 chiffres pour numéroter les grains de sable du Sahara [5], un milliard de milliards de Saharas ne nécessiteraient encore que moins de 50 chiffres pour en numéroter les grains de sable...)

Albert publie alors les nombres M et P

Il crypte son texte T (rappelons que tout texte "numérisé" est représenté par un nombre binaire)en le multipliant S fois par lui-même (TS) et il obtient un résultat T' qu'il transmet à Bertrand

Bertrand lors de la réception va à son tour multiplier T' P fois par lui même et il obtient T" qui est égal au message initial multiplié (S*P) fois par lui même soit (T"= TS*P)

Mais nous avons choisi S et P tels que S*P= nK+1 : or le théorème d'Euler nous dit que lorsque nous multiplions un nombre quelconque K fois par lui même on obtient 1 + un multiple de M, donc le message T" est égal au message initial + un multiple de M,

Il suffit donc de diviser T" par M et le reste de cette division est le message initial T

Pour les mathématiciens : T"= TS*P = TnK+1 = T * TnK or TnK = 1 modulo M donc T" = T modulo M

Une des techniques les plus connues est dite RSA (Du nom de ses inventeurs: Rivest, Shamir et Adelman).

sur Evariste sur le Web
nous écrire
Evariste ©1996-2007
URL : http://www.evariste.org/new/index.html

(Last update : Fri, 9 Feb 2007)