76
Science de la sécurité du système d’information
Deuxième partie
seuls pourraient déduire le secret. Les caractéristiques souhaitées d’une telle fonction sont la relative facilité de calcul dans le sens direct, et la quasi-impossibilité
de calculer la fonction réciproque. Ainsi, si s est le secret en clair, F la fonction
de chiffrement, c le secret chiffré, D la fonction de déchiffrement, il faut que
c = F (s) soit facile à calculer, mais s = D(c) pratiquement impossible à calculer
pour tout autre que les participants — au prix de quel stratagème, c’est ce que
nous allons voir.
Fondements mathématiques de l’algorithme Diffie-Hellman
La solution au problème que se posaient Diffie et Hellman repose sur un chapitre
de l’arithmétique très utilisé par les informaticiens, l’arithmétique modulaire, soit
l’arithmétique fondée sur les classes d’équivalence modulo n.
Considérons l’ensemble des entiers relatifs Z muni de l’addition et de la multiplication. La division entière de a par b que nous avons apprise à l’école primaire y
est définie ainsi :
a ÷ b → a = b × q + r
où q est le quotient et r le reste de la division. Ainsi :
13 ÷ 3 → 13 = 3 × 4 + 1
Intéressons-nous maintenant à tous les nombres qui, divisés par un nombre donné
n, par exemple 3, donnent le même reste r. Nous avons déjà trouvé un nombre,
13, pour lequel r = 1 ; donnons-en quelques autres :
1 ÷ 3 → 3 × 0 + 1
4 ÷ 3 → 3 × 1 + 1
7 ÷ 3 → 3 × 2 + 1
10 ÷ 3 → 3 × 3 + 1
13 ÷ 3 → 3 × 4 + 1
16 ÷ 3 → 3 × 5 + 1
On dit que ces nombres constituent une classe d’équivalence, et qu’ils sont tous
équivalents à 1 mod 3 (prononcer « un modulo trois »), ce qui s’écrit :
Science de la sécurité du système d’information
Deuxième partie
seuls pourraient déduire le secret. Les caractéristiques souhaitées d’une telle fonction sont la relative facilité de calcul dans le sens direct, et la quasi-impossibilité
de calculer la fonction réciproque. Ainsi, si s est le secret en clair, F la fonction
de chiffrement, c le secret chiffré, D la fonction de déchiffrement, il faut que
c = F (s) soit facile à calculer, mais s = D(c) pratiquement impossible à calculer
pour tout autre que les participants — au prix de quel stratagème, c’est ce que
nous allons voir.
Fondements mathématiques de l’algorithme Diffie-Hellman
La solution au problème que se posaient Diffie et Hellman repose sur un chapitre
de l’arithmétique très utilisé par les informaticiens, l’arithmétique modulaire, soit
l’arithmétique fondée sur les classes d’équivalence modulo n.
Considérons l’ensemble des entiers relatifs Z muni de l’addition et de la multiplication. La division entière de a par b que nous avons apprise à l’école primaire y
est définie ainsi :
a ÷ b → a = b × q + r
où q est le quotient et r le reste de la division. Ainsi :
13 ÷ 3 → 13 = 3 × 4 + 1
Intéressons-nous maintenant à tous les nombres qui, divisés par un nombre donné
n, par exemple 3, donnent le même reste r. Nous avons déjà trouvé un nombre,
13, pour lequel r = 1 ; donnons-en quelques autres :
1 ÷ 3 → 3 × 0 + 1
4 ÷ 3 → 3 × 1 + 1
7 ÷ 3 → 3 × 2 + 1
10 ÷ 3 → 3 × 3 + 1
13 ÷ 3 → 3 × 4 + 1
16 ÷ 3 → 3 × 5 + 1
On dit que ces nombres constituent une classe d’équivalence, et qu’ils sont tous
équivalents à 1 mod 3 (prononcer « un modulo trois »), ce qui s’écrit :