Arithmétique modulaire et nombres premiers

La cryptographie repose sur des fondations mathématiques solides.

1. Arithmétique modulaire

L’ensemble des entiers relatifs, noté images/02eq1.png

, est l’ensemble de tous les nombres entiers, qu’ils soient positifs, négatifs ou nuls

et l’ensemble des entiers naturels (ou positifs) images/02eq3.png

est un sous-ensemble de images/02eq1.png

.

L’ensemble images/02eq1.png

est muni des opérations d’addition (+) et de multiplication (x), vérifiant les propriétés suivantes :

Soient a, b, et c trois entiers relatifs.

Propriété 1 : l’associativité de l’addition dans

Propriété 2 : la commutativité de l’addition

Propriété 3 : l’élément neutre 0 pour l’addition

Propriété 4 : pour chaque entier relatif a

il existe un symétrique (opposé) de a noté (-a)

tel que :

Propriété 5 : la distributivité de la multiplication sur l’addition

Propriété 6 : l’associativité de la multiplication

Propriété 7 : la commutativité de la multiplication

Propriété 8 : l’élément neutre 1 pour la multiplication

Avec ces huit propriétés, images/02eq1.png

forme un anneau commutatif unitaire.

Nous reviendrons sur ce terme dans la sous-section Anneaux et corps de ce chapitre.

La soustraction peut être définie comme une addition de l’opposé.

Absence de division générale

La division d’un entier par un autre n’aboutit pas toujours à un entier.

Par exemple :

5 ÷ 2 = 2.5

qui n’est pas un entier relatif. C’est précisément là que le concept de division euclidienne (avec un quotient et un reste) devient crucial, et par extension, l’arithmétique modulaire.

Pour le reste du livre, l’expression "un entier" désigne toujours un entier relatif.

a. Division euclidienne

La division euclidienne, également appelée division entière, est l’opération qui, étant donné deux nombres entiers, un dividende et un diviseur, permet de trouver un quotient et un reste. C’est la forme de division que nous apprenons dès le primaire....

Groupes, anneaux et corps finis

Dans cette section, nous allons voir les notions de groupe, de sous-groupe, d’anneaux et de corps.

1. Groupes

Nous allons commencer par définir une loi de composition interne sur un ensemble E.

a. Loi de composition interne

Soit E un ensemble non vide. Une loi de composition interne (souvent notée *) sur E est une application :

qui, à deux éléments images/02eq64.png

, associe un élément images/02eq65.png

.

« Interne » signifie que le résultat reste dans le même ensemble.

Exemple 1 :

Sur : + (addition) est une loi de composition interne, car la somme de deux entiers (relatifs) est toujours un entier (relatif).
Sur * ( privé de 0) : + n’est pas une loi de composition interne, car .

b. Groupe

Un groupe est un couple (G,*), où G est un ensemble non vide et * une loi de composition interne sur G, vérifiant les quatre propriétés suivantes :

Associativité : .
Élément neutre : il existe un élément tel que .
Inverse : il existe tel que .

Si en plus images/02eq73.png

,

alors le groupe G est dit commutatif (abélien).

Exemple 2 : ( images/02eq1.png

,+) est un groupe abélien.

Associativité : l’addition est associative : .
Élément neutre : l’élément neutre pour l’addition est 0.
Inverse : l’inverse de a est -a (on parle de l’opposé de a).
Commutativité : a + b = b + a.

On dit qu’un groupe G est fini s’il n’a qu’un nombre fini d’éléments. Dans ce cas, le cardinal (ou ordre) de G est le nombre d’éléments qu’il contient. On le note généralement images/02eq76.png

.

Il existe un type particulier de groupe en algèbre dont tous les éléments peuvent être générés par un seul élément, appelé générateur (ou élément générateur). En d’autres termes, tous les éléments du groupe sont des puissances entières (ou des multiples, si l’opération du groupe est notée additivement) de ce générateur.

Groupe monogène, groupe cyclique

Soit (G, x) un groupe. (G, x) est dit monogène s’il existe un élément...

Algorithmes mathématiques utiles

Dans cette section, nous allons voir quelques algorithmes utiles pour la cryptographie asymétrique.

1. L’algorithme exponentiation modulaire

L’exponentiation modulaire rapide, souvent implémentée avec la méthode Square and Multiply (carré et multiplier), nous permet de calculer efficacement a^d mod n même lorsque d est un très grand nombre.

Une approche naïve pour calculer a^d mod n consisterait à multiplier a par lui-même d fois, puis à prendre le modulo à la fin ou après chaque multiplication. Cette méthode est beaucoup trop lente : si d a 1024 bits, cela représente 2¹⁰²⁴ multiplications, ce qui est astronomique.

a. Principe

La méthode « Square and Multiply » exploite la représentation binaire de l’exposant d.

Soit l’opération à calculer : r = a^d mod n

Représentation binaire de d : convertir l’exposant d en sa représentation binaire.

Si avec ,

alors .

Stratégie : l’algorithme parcourt les bits de d (généralement de gauche à droite, du bit de poids fort au bit de poids faible). À chaque pas, il effectue une opération de « carré » (multiplication du résultat courant par lui-même) et, si le bit courant est un ’1’ (i-e. d_i = 1), une opération de « multiplication » par a est faite.
Pourquoi le résultat est correct :

b. Algorithme « Square and Multiply »

Dans cette sous-section, nous décrivons l’algorithme « Square and Multiply » selon une approche de gauche à droite, consistant à traiter les bits de l’exposant du plus significatif au moins significatif.

Cet algorithme nous permet de calculer efficacement r = a^d mod n.

def exponentiation_modulaire(a...

Les bases mathématiques essentielles