This material is available only on bibliotequer
20 Apr 2021 
admin 
Supposons que nous avons un r utilisateurs A_1,…….., A_r aient comme clé publique (e, n_1) ,……. , (e, n_r) dont nous supposerons que les n_i sont premiers entre eux deux-à-deux. Si un message µ commun leur est envoyé par un expéditeur donné, et qu’on observe les r messages chiffrés C_1,..,〖C 〗_r , il est alors possible de retrouver 〖µ 〗^e [ n ] où n =n_1 .n_2……n_r.
Proposition 1: Si µ < 〖min〗_(1≤i≤r) n_i (c’est l’hypothèse que l’on a fait à l’origine sur l’encodage du message), et si e ≤ r , on peut retrouver µ à partir de C_1,..,〖C 〗_r en effectuant un nombre d’opérations polynomial en log(n).
Démonstration :
Selon l’hypothèse, on a r utilisateursA_1,…….., A_r aient comme clé publique (e, n_1) ,……. , (e, n_r) avec le même message µ, donc ce message µ est chiffré r par fois et on :
C_i≡ µ^e [n_i ], pour 1≤i≤r
On a : n =∏_(i=1)^r▒n_i , et puisque les n_i sont premiers entre eux deux-à-deux, on peut appliquer le théorème de Chinois pour résoudre le système d’équations :
x=C_1 [n_1 ]
x=C_2 [n_2 ]
.
. x≡ C_i [n_i ] , pour 1≤i≤r et x < n
.
.
x=C_r [n_r ]
On a µ < 〖min〗_(1≤i≤r) n_i b et e ≤ r, donc µ^e1, supposons que l’on sache calculer, pour chaque réel x, toutes les puissances x^k de x, pour tout k, tel que 1 ≤ k < n :
Si n est pair, donc x^n=(〖x^2)〗^(n/2) , dans ce cas il suffit de calculer (〖y)〗^(n/2) pour y=x^2
Si n est impair, donc x^n=x(〖x^2)〗^(((n-1))/2) , dans ce cas il suffit de calculer (〖y)〗^(((n-1))/2) pour y=x^2 et
Cette méthode nous amène à l’algorithme récursif suivant qui calcule x^n pour un entier strictement positif n :
x si n=1
Puissance (x,n) Puissance (x^2,n/2) si n est pair
Puissance (x^2,((n-1))/2) si n est impair
Complexité :
Pour évaluer le coût de cet algorithme en nombre d’appels à des opérations “primitives”. On décompose les appels récursifs et on compte le nombre d’appels récursifs opérations “primitives” on décompose les appels récursifs et on compte le nombre d’appels récursifs. Notons R(n) le nombre d’appels récursifs, la structure de l’algorithme montre que R(n) ≤ R(n/2) .
On en déduit que R(n) ≤〖log〗_2 (n). Comme un appel récursif fait 0 (cas de base), ou 1 (cas n pair) ou 2 (cas n impair) opérations. On en déduit que le nombre d’opérations C(n) est majoré par 2 〖log〗_2 (n).
Et comme l’algorithme fait toujours au moins log2 n appels, C(n) est minoré par 〖log〗_2 (n) , alors : C(n)=O(log(n)).
Donc, on déduit que le cas optimal est de 〖log〗_2 (n) lorsqu’on a n une puissance de 2.
Exemple SageMath :
Exponentiation rapide et RSA :
Dans RSA, il y a deux parties : le chiffrement et le déchiffrement :
Le chiffrement : l’émetteur a besoin de calculer le messager crypté C≡ 〖µ 〗^e [ n ] qui représente une puissance de base µ et d’exposant e.
Le chiffrement : le récepteur a besoin de calculer le messager décrypté µ ≡ 〖C 〗^d [ n ] qui représente une puissance de base C et d’exposant d.
Dans les cas, on a besoin de calculer une puissance et puisque il est nécessaire de choisir e grand pour se protéger contre l’attaque de l’algorithme par un pirate, l’algorithme de l’exponentiation rapide permet de minimiser le coût de chiffrement et de déchiffrement en optimisant le nombre d’opérations de calculs.
Pour l’exemple de e= 257 et e= 65537, on remarque :
e=257=256+1= 2^8+1
e=65537=65536+1= 2^16+1
Les deux exemples de e représentent un nombre premier de Fermat F_(n ) telle que :
F_(n )=2^(2^n )+1
En revenant à notre calcul de chiffrement d’un message µ, on aura besoin de calculer le message crypté C≡ 〖µ 〗^e [ n ] :
〖µ 〗^e=〖µ 〗^257= µ* 〖µ 〗^(2^8 )
〖µ 〗^e=〖µ 〗^257= µ* 〖µ 〗^(2^16 )
Selon la complexité de l’exponentiation rapide, le nombre d’opération des calculs de 〖µ 〗^(2^16 ) et 〖µ 〗^(2^8 ) sera minimal puisque les deux exposants sont une puissance de 2.
Finalement, le calcul de 〖µ 〗^257 et 〖µ 〗^257 sera plus simple. Dans ce cas, le coût de chiffrement du message sera optimal tout en protégeant du risque de l’attaque de l’algorithme par un pirate.
Exemple d’un calcul sur SageMath