Cryptographie, préliminaires mathématiques

Chap. 1. PRELIMINAIRES MATHEMATIQUES

[pic 1]

C.SALOUM

[pic 2]

La cryptographie moderne est basee sur des faits mathematiques bien etablis qu'il est indispensable de conna^tre. Nous avons choisi de rappeler quinze notions tres frequentes tout au long de ce module. On se referera aux livres de mathematiques de Deug et de licence pour approfondir tel ou tel autre point particulier. On rappellera notamment les questions suivantes :

1. Algorithme d'Euclide

[pic 3]

Tres utilise en cryptographie, il sert au calcul du plus grand diviseur commun (pgcd) entre deux entiers naturels a et b. Puisque pgcd(a; b) = pgcd(b; a), on peut supposer que a b > 0 et que la division euclidienne de a par b est : a = bq + r ou 0 r < b. L'algorithme d'Euclide consiste a utiliser la relation de recurrence pgcd(a; b) = pgcd(b; r) jusqu'a ce qu'on obtienne un reste r nul. Le dernier reste non nul est alors le pgcd de a et de b.

Exemple 1 : pgcd(120; 80) = pgcd(80; 40) = pgcd(40; 0) = 40 ;

[pic 4]

1

Cryptographie        Ann. Univ. 2016-17

[pic 5]

pgcd(810; 100) = pgcd(100; 10) = pgcd(10; 0) = 10.

A retenir : Pour tout a; b; c 2 N ;        pgcd(a; 0) = a et pgcd(c a; c b) = c pgcd(a; b).

L'algorithme d'Euclide est tres rapide : contrairement a d'autres algorithmes en cryp-tographie, il ne pose aucun probleme aux ordinateurs m^eme si les nombres a et b sont composes de plusieurs centaines de chi res decimaux. On demontre que le nombre d'etapes executees est toujours majore par cinq fois le nombre de chi res decimaux du plus petit des deux nombres a et b (Theoreme de Lame, vers 1830).

Exemple 2 : Le pgcd(1234567890; 1980) sera calcule en moins de 5 4 = 20 etapes. Veri ons :

[pic 6]

pgcd(1234567890; 1980) = pgcd(1980; 270) = pgcd(270; 90) = pgcd(90; 0) = 90.

Maple ! igcd(a; b) (integer great common divisor)

[pic 7][pic 8][pic 9][pic 10][pic 11]

2. Algorithme etendu d'Euclide

[pic 12]

Il permet de calculer des coe cients entiers u et v tels que au+bv = d ou d est le pgcd des deux entiers naturels a et b. En particulier lorsque les entiers naturels a et b sont premiers entre eux.

Le reste de la division euclidienne de l'entier u par l'entier v est note u mod v.

On commence par la liste ( ; 1; 0; a; 0; 1; b; ) et l'on poursuit, jusqu'a obtenir v3 = 0, avec les a ectations suivantes :

(q; u1; u2; u3; v1; v2; v3) (bu3=v3c; v1; v2; v3; u1 qv1; u2 qv2; u3 mod v3) bxc designe la partie entiere du reel x.

Exemple 3 : Trouvons des entiers u et v tels que 110u + 21v = 1.

[pic 13]

D'ou u =        4; v = 21 et l'on veri e que 110(  4) + 21(21) = 1

Exemple 4 : Determinons le pgcd d de 1140 et de 360 ainsi que les entier u et v tels que

[pic 14]

2

Cryptographie        Ann. Univ. 2016-17

[pic 15]

1140u + 360v = d.

D'ou d = 60; u =        3; v = 60 et l'on veri e que 1140(1) + 360(  3) = 60

La complexit de l'algorithme d'Euclide etendu est la m^eme que celle du calcul du pgcd puisque la derniere colonne du tableau calcule ce pgcd.

Application : On se sert de l'algorithme etendu d'Euclide dans l'application du theoreme chinois des restes et dans le calcul des inverses dans l'anneaux (nZZ; +; :).