Pour chiffr un message M par RSA avec une cl priv (e,n) on doit calculer: C=Me mod n Ce qui est une exponentiation modulaire. Le calcul de Me est trs couteux en temps de calcul car lexposant e doit tre sur 1024 bits pour assur une scurit maximale

La solution est lutilisation dun algorithme dexponentiation modulaire qui va simplifier cette opration.

On peut reprsenter lexposant e en binaire (base 2) Sur k bits alors : e = (ek-1 ek-2 e1 e0)2 pour tout 0 i k-1, ei ={0,1}. Donc C=Me = (ek-1 ek-2 e1 e0) mod n

Entre : M,e,n Sortie : C = Me (mod n) 1. Si ek-1 = 1 alors C = M Sinon C=1 2. Pour i = k-2 jusqu 0 faire 2a. C = C . C (mod N) 2b. Si ei = 1 alors C = C . M (mod N) 3. Retourner C

Cette mthode ncessite Pour un exposant e sur k-bits, avec ek-1 = 1 (Etape 2a) : k-1 Multiplications (Etape 2b) : elle dpend aux bits ei 1 de e. Ce qui signifie que le nombre maximale des multiplications quon peut avoir est: (k-1)+(k-1) = 2(k-1) multiplications

Avec la mthode binaire on peut rduire le nombre de multiplications ncessaires pour lexponentiation de (e-1) jusqu 2(k-1) si touts les bits de e sont 1.

MUX C2 MM

1 0

C*MMM

e

M

On peut dire que la mthode m-aires est une mthode binaire amlior le m est un puissance de 2 donc on peut reprsent e dans la base m partir de son criture en binaire en faisant s blocs de r bits o sr = k, tell que k reprsente le nombre de bits de e . Le principe de la mthode m-aire est que lon doit dabord calculer les Mw pour w = 2,3,,m-1 que lon va stocker car on devra les utiliser continuellement pour les multiplications.

Entre : M,e,n, m=2r Sortie : C = Me (mod n) 1. Calculer et stocker Mw (mod N) pour tout w= 2,3,,m-1 2. Dcomposer e en s mot de r bits Fi 3. C = MFs-1 (mod n) 4. Pour i = s-2 0 4a. C = Cm (mod n) 4b. si Fi 0 alors C = C . MFi (mod N) 5. Retourner C

Pour la mthode m-aire quelconque avec m = 2r Le nombre de pr-calculs effectu est de : m-2 = 2r -2 Le nombre de carrs (Etape 4a) est de : ((k-1)/r).r si touts les bits de fi sont 1 Le nombre de multiplication (Etape 4b) est de : ( (k-1)/r au maximum Donc en gnral la mthode m-aire requiert en moyenne: (k-1)/r .r carrs+ 2r -2 + (k-1)/r multiplications. = (k-1)/r .(r +1) + 2r -2

Cm Fi=?0 e r C*Mfi

Mfs-1

Mf0

C r carres MM(C,C)

Cm

m= 32=25 => r= 5Pour un exposant e =2451 =(100110010011)

K=12 S=3 les multiplications ncessaires sont donc

2 =(00010 01100 10011)

(k-1)/r .(r +1) + 2r -2 =3.6+30=48 multiplications qui est trs infrieur 2451

Les multiplication doit tre excut en srie donc on doit implmenter une multiplication modulaire ddie cet algorithme

le calcul de lexponentiation modulaire nest autre quun calcul itratif de la multiplication modulaire. La multiplication modulaire consiste effectuer la multiplication de deux nombre A et B et de prendre le reste S obtenu de la division du produit (A*B) par un troisime nombre M, appel modulo cette opration est donne par lexpression suivante S=(A*B)mod M

Dune manire gnrale, lexcution de la multiplication modulaire ncessite deux phases, une phase de multiplication suivit dune phase de rduction (division).

On peut classs les algorithmes du la multiplication modulaire en deux catgories : Les algorithmes intgrs : sont des algorithmes qui intgrent la rduction la multiplication ellemme. Ex : Lalgorithme de Taylor avec mmorisation Les algorithmes rduction : sont des algorithmes qui dcomposent la multiplication modulaire en une multiplication suivie dune rduction modulaire. Ex : lalgorithme de Montgomery

entre : a, b, M avec 0 a, b < M donne : M avec (M)*M = 1 mod R,R=n >M sortie : S tel que S =( A*B*R-1) mod M avec R*R-1 = 1 mod M dbut C