CRYPTOGRAPHIE APPLIQUÉE

Module 1 Mathématiques pour la cryptologie

Théorie des grands nombres

YOUR SECURITY, OUR BUSINESS

Nelson SAHO

Facililateur

SecuriGate

11 décembre 2023
 Contenu

1 Introduction à la sécurité des données

2 Outils mathématiques pour la cryptographie

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 1

 Contenu

1 Introduction à la sécurité des données

2 Outils mathématiques pour la cryptographie

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 2

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 3
 Les différents niveaux d’implémentation de mesures de sécurité
informatique.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 4

 La sécurité des données : ensemble des techniques informatiques
permettant d’empêcher les fuites et altération de données ou de
détérioration des services.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 5

 Plusieurs modèles sont utilisés pour atteindre ces objectifs. Le premier,
Le Triangle CIA est un modèle de base pour les autres.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 6

 Les 4 types de menaces susceptibles d’être rencontrées dans un SI.

Figure – Les types de menaces actives [Dumont, 2009].

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 7

 Figure – Le principe basique de la cryptographie.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 8

 Deux familles de cryptographie de par l’utilisation de la clef.

La cryptographie symétrique : Son avantage réside dans la rapidité du

calcul et l’utilisation aisée [Erritali et al., 2012].

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 9

 Al-Shabi a discuté des algorithmes les plus importants utilisés pour le
processus de chiffrement et de déchiffrement.

Des résultats de Al-Shabi, nous identifions les principaux algorithmes

asymétriques envisagés, comme d’autres auteurs.

Les principaux cryptosystèmes asymétriques

RSA [Rivest et al., 1978]

Diffie Hellman [Diffie and Hellman, 1976]

ECC [Koblitz, 1987; Miller, 1985]

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 10

 Le cryptosystème Diffie Hellman effectue beaucoup de calcul qui
épuise la batterie. Ce défaut, cumulé avec les attaques de type
man-in-middle, constituent une contre-performance.
Dès lors, notre attention s’est plutôt portée sur les algorithmes RSA et
ECC.
Les cryptosystèmes se doivent d’être performants face à des attaques
de plus en plus nombreuses.
La sécurité de l’algorithme RSA repose sur la difficulté à factoriser un
grand nombre n en deux facteurs premiers p et q.
Ce problème était jugé impossible à résoudre mais aujourd’hui on dit
plutôt qu’il est difficile à résoudre calculatoirement à cause par
exemple de l’algorithme de Shor [Shor, 1997].

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 11

 Contenu

1 Introduction à la sécurité des données

2 Outils mathématiques pour la cryptographie

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 12

 Contenu

Dans cette session, nous présenterons les notions suivantes :

Les fonctions,

Les substitutions, les transpositions

Les matrices

Nombres premiers

Plus Grand Commun Diviseur

Algorithme d’Euclide et algorithme d’Euclide étendu

Théorème de Fermat

Théorème des restes Chinois

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 13

 Injection/Surjection/Bijection

Soit f une application de A dans B.

Injection
f est injective ssi ∀x1 , x2 ∈ A, f (x1 ) = f (x2 ) −→ x1 = x2
(ou encore x1 ̸= x2 −→ f (x1 ) ̸= f (x2 ))

Surjection
f est surjective ssi ∀y ∈ B, ∃x ∈ A tel que y = f (x)

Bijection
f est bijective si et seulement si elle est à la fois injective et surjective.
(ou encore ∀y ∈ B, ∃!x ∈ A tel que y = f (x)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 14

 Exemples

Soient X = {a, b, c} et Y = {1, 2, 3}. On definit l’application

f : X → Y par f (a) = 1, f (b) = 3, f (c) = 2. Alors f est une bijection.
Soient X = {a, b, c}, Y = {1, 2, 3} et g : X → Y telle que g (a) = 1,
g (b) = g (c) = 2. Alors g n’est pas une bijection. Pourquoi ?.

Conséquence
Si f est une bijection de A dans B, alors A et B ont le même nombre
d’éléments appelé cardinal.

Soient X = {a, b, c, d} et Y = {1, 2, 3}. Il n’existe aucune bijection

de X sur Y .

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 15

 Inverse d’une bijection

Si f : X → Y est une bijection, alors il existe une fonction

g : Y → X (qui est elle-même également une bijection) telle que
∀x ∈ X , g (f (x)) = x et ∀y ∈ Y , f (g (y )) = y .
On dit que g est la fonction inverse (ou réciproque) de f , et on la
note parfois f −1 .
En reprenant X = {a, b, c}, Y = {1, 2, 3} et f : X → Y définie par
f (a) = 1, f (b) = 3 et f (c) = 2. Quelle est la fonction inverse de f ?

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 16

 Inverse d’une bijection

Si f : X → Y est une bijection, alors il existe une fonction

g : Y → X (qui est elle-même également une bijection) telle que
∀x ∈ X , g (f (x)) = x et ∀y ∈ Y , f (g (y )) = y .
On dit que g est la fonction inverse (ou réciproque) de f , et on la
note parfois f −1 .
En reprenant X = {a, b, c}, Y = {1, 2, 3} et f : X → Y définie par
f (a) = 1, f (b) = 3 et f (c) = 2. Quelle est la fonction inverse de f ?
C’est la fonction g : Y → X definie par g (1) = a, g (2) = c et
g (3) = b.

Intérêt de l’inverse
L’interêt cryptographique des bijections repose sur leur propriété
d’inversibilité.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 16

 Substitution

Définition
Une substitution est une bijection qui consiste à remplacer chaque lettre
d’un message par une autre lettre. Attention : partout où une lettre donnée
apparaît, elle est toujours remplacée par la même lettre.

On considère l’application suivante qui à chaque symbole de M associe un

symbole de C tel que :

M=messagesecret
C=bxvvgoxvxulxe

justifier qu’il s’agit d’une bijection

Justifiez qu’il s’agit d’une substitution.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 17

 Remarque

Dans les substitutions on peut transformer des lettres en d’autres

symboles et non necessairement d’autres lettres du même alphabet.

Une substitution ne change pas l’ordre des lettres dans un message

mais seulement les lettres elles-mêmes figurant dans le message.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 18

 Transposition

Définition
Dans une transposition, on ne modifie pas l’écriture des lettres mais leur
ordre dans un message.

On considère l’application définie par :

M=messagesecret
C=emeasgsecsrte

Justifier qu’il s’agit d’une bijection.

S’agit-il d’une transposition ?

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 19

 Remarque

Une transposition opère de façon identique quel que soit le message.

Cela signifie que la transposition ne depend que de l’ordre des lettres
dans un message et non des lettres elles-mêmes.
En reprenant l’exemple précédent, on peut représenter de façon
graphique la transposition :
1 2 3 4 5 6 7 8 9 10 11 12 13 14
2 1 7 5 3 6 4 8 13 11 9 12 14 10

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 20

 Arithmétique modulaire

De nombreux systèmes cryptographiques sont en partie basés sur

l’arithmetique modulaire. En terme d’artihmétique modulaire, nous
parlerons des opérations :
l’addition
la soustraction
l’opposé d’un entier
la multiplication
l’inverse d’un entier

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 21

 Le modulo

Définition
Soient trois entiers a, b et n et n > 0. On dit que a est égal b modulo n et
on écrit a = b modulo n ou encore a = b ≡ n si, et seulement si, n divise
a − b ou encore a − b est un multiple de n. En d’autres termes :
a = b (modulo n) ⇐⇒ ∃ k ∈ N tel que a − b = kn
L’entier n est parfois appelé le modulus.

Par exemple :
10 = 1 ≡ 3
155 = 0 ≡ 5
102 = 2 ≡ 10

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 22

 Calcul pratique du modulo

Supposons que l’on effectue une division euclidienne de a et de b par n.

On obtient des quotients et des restes, ceux-ci étant compris entre 0
et n − 1. Précisément, on a a = q1 n + r1 et b = q2 n + r2 avec
0 ≤ r 1 ≤ n − 1 et 0 ≤ r2 ≤ n − 1.
Ainsi il est facile de voir que a = b modulo n) si, et seulement si,
r1 = r2 , c’est-a-dire que a et b ont le même reste dans la division
entière par n.
On note également a modulo n le reste de la division euclidienne de a
par n.
Si on remplace a par a modulo n), on dit que l’on réduit a modulo n.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 23

 Addition

On note Zn = {0, ..., n − 1} l’ensemble des entiers modulo n.

Addition
L’addition dans Zn fonctionne exactement comme l’addition usuelle
excepté le fait que tous les résultats sont réduits modulo n.

Effectuer les opérations suivantes dans Z16 :

122 + 45
11 + 134
Calculer
3+7≡2
3+7≡5
3+7≡6
3 + 7 ≡ 11.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 24

 Multiplication

On note Zn = {0, ..., n − 1} l’ensemble des entiers modulo n.

Multiplication
La multiplication dans Zn fonctionne exactement comme la multiplication
usuelle excepté le fait que tous les résultats sont réduits modulo n.

Effectuer les opérations suivantes dans Z16 :

22 × 45
15 × 34
Calculer
3×7≡2
3×8≡5
3×9≡6
3 × 10 ≡ 11.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 25

 Soustraction modulaire

Définition
Etant donnés deux entiers a et b tels que a ≥ b, la soustraction modulo n
de a et b est (a − b) modulo n. En d’autres termes, le reste modulo n de
a − b.

Pour effectuer cette soustraction, on commence par calculer a − b de

façon usuelle,
On réduit le résultat obtenu modulo n.
Effectuer les opérations suivantes :
7 − 3 ≡ 2;
7 − 2 ≡ 3.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 26

 Opposé modulaire d’un entier

Définition
Soit a ∈ Zn . Alors n − a satisfait la propriété a + (n − a) = 0 = (n − a) + a
(additions modulo n). L’entier n − a est l’opposé modulo n de a, qui est
noté −a.

Remarquons que si a = 0, alors n − a = n = 0 modulo n).

−3 ≡ 5 = 2 car on a 3 + 2 = 0 (modulo 5) ;
−4 ≡ 8 = 4 car on a 4 + 4 = 0 (modulo 8).

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 27

 Propriétés

L’addition et la multiplication dans Zn satisfont la plupart des règles

familières en artithmétique classique. Soient a, b, c ∈ Zn .
1 L’addition est commutative : a + b = b + a
2 L’addition est associative : (a + b) + c = a + (b + c)
3 0 est neutre pour + : a + 0 = a = 0 + a
4 L’opposé −a de a est −a = n − a. En particulier l’opposé de 0 est 0 ;
5 La multiplication est commutative : ab = ba
6 La multiplication est associative : a(bc) = (ab)c
7 1 est neutre pour la multiplication : a1 = a = 1a ;
8 La multiplication est distributive sur l’addition : (a + b)c = ac + bc et
a(b + c) = ab + ac.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 28

 Groupe en cryptographie

Définition d’un groupe

Les propriétés (2), (3) et (4) précisent que Zn possède une structure
algebrique de groupe.

De façon générale, un groupe G est un ensemble non vide muni d’une loi
de composition interne notée ⋆ : G × G → G telle que
la loi ⋆ est associative : ∀g1 , g2 , g3 ∈ G , (g1 ⋆ g2 ) ⋆ g3 = g1 ⋆ (g2 ⋆ g3 )
Il existe un unique élément e tel e ⋆ g = g ⋆ e = g pour tout élément
g ∈ G . L’élément e est appelé l’élément neutre de G .
Quel que soit g ∈ G , il existe un unique élément g ′ ∈ G appelé
opposé de g ou inverse de g selon le cas tel que g ⋆ g ′ = g ′ ⋆ g = e.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 29

 Importance des groupes en cryptographie

Le plus important dans un groupe est l’existence d’un inverse (ou

oppose) de chaque élémént.

Les groupes fournissent donc des fonctions qui peuvent etre utilisées
dans des algorithmes de chiffrement car elles sont inversibles et
permettent donc de realiser le déchiffrement.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 30

 Les entiers en informatique

Les entiers en informatique ne sont pas les entiers en mathématiques.

En effet :
Un entier en informatique est toujours fini et tient compte compte de
la machine. Ce n’est pas le cas en mathématiques.
La notion d’entier en informatique fait référence à un sous-ensemble de
Z.
En mathématiques, on parle d’entier naturel en considérant N et
d’entier relatifs en considérant Z.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 31

 Notion de diviseur

Définition
Etant donnés deux entiers a et b, on dit que b divise a ssi

∃ k ∈ Z tel que a = kb

On dit aussi que b est un diviseur de a ou que a est un multiple de b.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 32

 Nombre premier

Définition
Un nombre entier naturel est premier lorsqu’il n’admet que deux diviseurs.

Les nombres suivants sont-ils premiers ?

3324, 123, 51, 19 151
Il existe plusieurs méthodes pour reconnaitre un nombre premier dont :
le crible d’Erastosthène.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 33

 Plus Grand Commun Diviseur et Plus Petit Commun
Diviseur

PGCD
Etant donnés deux entiers a et b, on dit que d est le plus grand commun
diviseur de a et b si et seulement si d divise à la fois a et b et apparaît
comme le plus grand de leurs diviseurs communs.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 34

 Plus Grand Commun Diviseur et Plus Petit Commun
Diviseur

PGCD
Etant donnés deux entiers a et b, on dit que d est le plus grand commun
diviseur de a et b si et seulement si d divise à la fois a et b et apparaît
comme le plus grand de leurs diviseurs communs.

PPCM
Etant donnés deux entiers a et b, on dit que m est le plus petit commun
multiple si et seulement si m est un mutiple à la fois de a et b et m apparait
comme le plus petit mutliple commun aux deux entiers entiers a et b.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 34

 Plus Grand Commun Diviseur et Plus Petit Commun
Diviseur

PGCD
Etant donnés deux entiers a et b, on dit que d est le plus grand commun
diviseur de a et b si et seulement si d divise à la fois a et b et apparaît
comme le plus grand de leurs diviseurs communs.

PPCM
Etant donnés deux entiers a et b, on dit que m est le plus petit commun
multiple si et seulement si m est un mutiple à la fois de a et b et m apparait
comme le plus petit mutliple commun aux deux entiers entiers a et b.

Entiers premiers entre eux

Si le plus grand commun diviseur de deux entiers a et b est égal à 1, on dit
que les entiers a et b sont premiers entre eux.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 34

 Exemples

Calculer
pgcd(120,45)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 35

 Exemples

Calculer
pgcd(120,45)

pgcd(100,460)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 35

 Exemples

Calculer
pgcd(120,45)

pgcd(100,460)

pgcd(122345,45030)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 35

 Exemples

Calculer
pgcd(120,45)

pgcd(100,460)

pgcd(122345,45030)

pgcd(19,17)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 35

 Exemples

Calculer
pgcd(120,45)

pgcd(100,460)

pgcd(122345,45030)

pgcd(19,17)

ppcm(13,11)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 35

 Exemples

Calculer
pgcd(120,45)

pgcd(100,460)

pgcd(122345,45030)

pgcd(19,17)

ppcm(13,11)

ppcm(120,110)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 35

 Exemples

Calculer
pgcd(120,45)

pgcd(100,460)

pgcd(122345,45030)

pgcd(19,17)

ppcm(13,11)

ppcm(120,110)

ppcm(1468,1120)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 35

 Exemples

Calculer
pgcd(120,45)

pgcd(100,460)

pgcd(122345,45030)

pgcd(19,17)

ppcm(13,11)

ppcm(120,110)

ppcm(1468,1120)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 35

 Algorithme d’Euclide

Théorème
Etant donnés deux entiersa etb (on peut supposer a >b), le plus grand
commun diviseur de a et b est le plus grand commun diviseur de b et de r
où r désigne le reste de la division entière de a par b.

Calculer
pgcd(12,45)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 36

 Algorithme d’Euclide

Théorème
Etant donnés deux entiersa etb (on peut supposer a >b), le plus grand
commun diviseur de a et b est le plus grand commun diviseur de b et de r
où r désigne le reste de la division entière de a par b.

Calculer
pgcd(12,45)

pgcd(130,460)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 36

 Algorithme d’Euclide

Théorème
Etant donnés deux entiersa etb (on peut supposer a >b), le plus grand
commun diviseur de a et b est le plus grand commun diviseur de b et de r
où r désigne le reste de la division entière de a par b.

Calculer
pgcd(12,45)

pgcd(130,460)

pgcd(122345,450300)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 36

 Algorithme d’Euclide

Théorème
Etant donnés deux entiersa etb (on peut supposer a >b), le plus grand
commun diviseur de a et b est le plus grand commun diviseur de b et de r
où r désigne le reste de la division entière de a par b.

Calculer
pgcd(12,45)

pgcd(130,460)

pgcd(122345,450300)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 36

 Algorithme d’Euclide étendu

Algorithme d’Euclide étendu

Le plus grand commun diviseur de deux entiers a et b est un entier d si et
seulement s’il existe deux entiers u et v tels que d = u a + b v .

Les entiers u et v sont appelés les coefficients de Bezout.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 37

 Exercices d’application

Exercice
Déterminez les coefficients de Bezout dans la recherche du plus grand
commun diviseur de 255 et 141.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 38

 Exercices d’application

Exercice
Déterminez les coefficients de Bezout dans la recherche du plus grand
commun diviseur de 255 et 141.
Cela revient à :
trouver u et v tels que 255u + 141v = d où d = pgcd(255, 141).

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 38

 Exercices d’application

Exercice
Déterminez les coefficients de Bezout dans la recherche du plus grand
commun diviseur de 255 et 141.
Cela revient à :
trouver u et v tels que 255u + 141v = d où d = pgcd(255, 141).
puis remonter le calcul pour trouver les coefficients de Bezout.

Exercice 2
Déterminez les coefficients de Bezout dans la recherche du plus grand
commun diviseur de 71 et 131.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 38

 Indicatrice d’Euler

Définition
L’indicatrice d’Euler est la fonction φ, de l’ensemble N⋆ des entiers
strictement positifs dans lui-même, définie par :
φ : N⋆ −→ N⋆
n 7−→ card{m ∈ N⋆ tel que m ≤ n et m premier avec n.}

Propriété
Soit n = pq où p et q sont des entiers naturels premiers. Alors
φ(n) = (p − 1)(q − 1)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 39

 Autres propriétés

Si a divise b alors φ(a) divise φ(b).

Un entier p > 0 est premier si et seulement si φ(p) = p˘1.
Si n a q diviseurs premiers impairs distincts, φ(n) est divisible par 2q.
Pour tout entier n > 2, φ(n) est pair.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 40

 Remarques importantes

La cryptographie utilise largement la fonction d’Euler notamment :

L’échange de clés du cryptosystème de Diffie-Hellman
le chiffrement RSA,

Théorème d’Euler
Si n est un entier strictement positif et a un entier premier avec n, alors
aφ(n) = 1 ( modulo n)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 41

 Exercices

Calculer
φ(8)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 42

 Exercices

Calculer
φ(8)
φ(17)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 42

 Exercices

Calculer
φ(8)
φ(17)
φ(77)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 42

 Exercices

Calculer
φ(8)
φ(17)
φ(77)
φ(100)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 42

 Exercices

Calculer
φ(8)
φ(17)
φ(77)
φ(100)
φ(143)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 42

 Exercices

Calculer
φ(8)
φ(17)
φ(77)
φ(100)
φ(143)

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 42

 Théorème de Fermat

L’expression théorème de Fermat peut désigner plusieurs résultats

d’arithmétique ou de géométrie, dont la démonstration ou la conjecture
sont attribuées à Pierre de Fermat.
Petit théorème de Fermat
Pour tout entier a, tout nombre premier p divise la différence ap − a.

Dernier théorème de Fermat

Pour tout entier n strictement supérieur à 2, il n’y a pas de nombres entiers
positifs non nuls x, y , z tels que x n + y n = z n .

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 43

 Théorème des reste chinois

Théorème
Etant donnés n entiers m1 , m2 , · · · mn supérieurs ou égaux à 2 et deux à
deux premiers entre eux et a1 , a2 , · · · an n autres entiers, alors le système
suivant : 

 x = a1 ≡ m1
x = a2 ≡ m2


 ··· ··· ··· ··· ···
x = an ≡ mn


admet une seule solution donnée par la formule

x = a1 M1 y1 + a2 M2 y2 + · · · + an Mn yn
Qi=n
M
où Mi = mi
, M = i=1 mi , yi = Mi−1 ≡ mi

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 44

 Exercice d’application

Enoncé
Une bande de 17 pirates s’est emparée d’un butin composé de pièces d’or
d’égale valeur. Ils décident de se les partager équitablement et de donner le
reste au cuisiner chinois. Ce dernier recevrait alors 3 pièces. Mais les pirates
se querellent et six d’entre eux sont sont tués. Le cuisinier recevrait dans ce
cas 4 pièces. Dans un naufrage ultérieur, seul le butin, six pirates et le
cuisinier sont sauvés. Et le partage donnerait alors 5 pièces d’or à ce
dernier. Quelle est la fortune minimale que peut espérer le cuisinier s’il
décide d’empoisonner le reste des pirates ?

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 45

 Solution

Soit x le nombre de pi‘eces d’or dans le butin.

La phrase Ils décident de se les partager équitablement et de donner le
reste au cuisinier chinois. Ce dernier recevrait alors 3 pi‘eces se traduit
par
x = 3 ≡ 17.
La phrase Mais les pirates se querellent et six d’entre eux sont tués. Le
cuisinier recevrait dans ce cas 4 pièces se traduit par

x = 4 ≡ 11.

La phrase Dans un naufrage ultiéerieur, seul le butin, six pirates et le

cuisinier sont sauvés. Et le partage donnerait alors 5 pièces d’or à ce
dernier se traduit par
x = 5 ≡ 6.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 46

 Solution (suite)

Nous avons donc le système


 x = 3 ≡ 7
x = 4 ≡ 11
x = 5 ≡ 6.


Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 47

 Solution (suite)

Nous avons donc le système


 x = 3 ≡ 7
x = 4 ≡ 11
x = 5 ≡ 6.


On vérifie aisément les hypothèses du théorème des restes chinois. En

effet m1 = 17, m2 = 11, m3 = 6 sont premiers deux à deux et tous
sont supérieurs à 2.
On a M = m1 × m2 × m3 = 1122.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 47

 Solution (suite)

Nous avons donc le système


 x = 3 ≡ 7
x = 4 ≡ 11
x = 5 ≡ 6.


On vérifie aisément les hypothèses du théorème des restes chinois. En

effet m1 = 17, m2 = 11, m3 = 6 sont premiers deux à deux et tous
sont supérieurs à 2.
On a M = m1 × m2 × m3 = 1122.
1122 1122
Le calcul des Mi donne M1 = 17 = 66, M2 = 11 = 102,
M3 = 11226 = 187.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 47

 Solution (suite)

Cherchons dès à présent les yi = Mi−1 = mi .

On cherche donc u tel que u × Mi = 1 ≡ mi ∀i ∈ {17, 11, 6}.
On obtient y1 = 8, y2 = 4, y3 = 1.
La solution est donc :
x = (a1 M1 y1 + a2 M2 y2 + a3 M3 y3 ) ≡ 1122
= 4151 ≡ 1122
= 785
Il faut donc un butin de 785 pièces d’or.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 48

 Matrice

Soit (a1 , a2 , · · · , an ) une famille de n objets. On utilisera la notation

(ai )1≤i≤n pour désigner cette famille.

Définition
Une matrice est la donnée d’une famille (aij )1≤i≤n,1≤j≤p de nombres réels
ou de complexes.

n représente le nombre de lignes

p désigne le nombre de colonnes
Les éléments aij sont les coefficients ou les éléments de la matrice
La taille de la matrice est n × p.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 49

 Représentation d’une matrice

Une matrice M = (aij )1≤i≤n,1≤j≤p est notée par

 
a11 a12 · · · a1p
 a21 a22 · · · a2p 
M= . .. .. ..
 
 ..

. . . 
an1 an2 · · · anp

Si n = p, on parle de matrice carrée d’ordre n.

Si n = 1, il s’agit d’un vecteur ligne ou d’une matrice ligne.
Si p = 1, il s’agit d’un vecteur colonne ou d’une matrice colonne.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 50

 Opérations sur les matrices

Nous nous intéresserons par la suite aux opérations :

addition

soustraction

multiplication

déterminant d’une matrice carrée.

inverse d’une matrice carrée.

Nous les rappelons rapidement !

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 51

 Addition de deux matrices

Soient A = (aij )1≤i≤n,1≤j≤p et B = (bij )1≤i≤n,1≤j≤p deux matrices de

même taille. La somme de A et de B est une matrice donnée par :
 
a11 + b11 a12 + b12 · · · a1p + b1p
 a21 + b21 a22 + b22 · · · a2p + b2p 
A+B = .. .. .. ..
 

 . . . . 
an1 + bn1 an2 + bn2 · · · anp + bnp

La somme s’obtient par l’addition des éléménts correspondant des deux

matrices.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 52

 Soustraction de deux matrices

Soient A = (aij )1≤i≤n,1≤j≤p et B = (bij )1≤i≤n,1≤j≤p deux matrices de

même taille. La soustraction de B de A est une matrice donnée par :
 
a11 − b11 a12 − b12 · · · a1p − b1p
 a21 − b21 a22 − b22 · · · a2p − b2p 
A−B = .. .. .. ..
 

 . . . . 
an1 − bn1 an2 − bn2 · · · anp − bnp

La soustraction s’obtient par la soustraction des éléménts correspondant

des deux matrices.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 53

 Produit de deux matrices

Soient A = (aij )1≤i≤n,1≤j≤p une matrice de taille n × p et

B = (bij )1≤i≤p,1≤j≤m une matrice de taille p × m. Le produit de A par B
est la matrice C de taille n × m dont les éléments sont données par :
p
X
∀i, j, cij = aik bkj
k=1

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 54

 Exemples

Effectuer les calculs suivants :

 
  5 1
1 2 0  2 3 
4 3 −1
3 4

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 55

 Exemples

Effectuer les calculs suivants :

 
  5 1
1 2 0  2 3 
4 3 −1
3 4
 
5 1  
 2 3  1 2 0
4 3 −1
3 4

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 55

 Exemples

Effectuer les calculs suivants :

 
  5 1
1 2 0  2 3 
4 3 −1
3 4
 
5 1  
 2 3  1 2 0
4 3 −1
3 4
  
1 2 0 3 −1 1
 4 3 −1   2 5 0 
2 −2 1 1 −2 3

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 55

 Matrice inversible

Définition
Une matrice carrée A d’ordre n est dite inversible ou régulière ou encore
non singulière s’il existe une matrice carrée B d’ordre n, appelée matrice
inverse de A et notée B = A−1 ,telle que

AB = BA = In

où In désigne la matrice identité d’ordre n i.e. dont les éléments de la

diagonale principale valent 1 et tout le reste 0.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 56

 Matrice carrée d’ordre 2

Définition
Une matrice carrée d’ordre 2 se présente sous la forme
 
a b
M=
c d

Le déterminant d’une matrice carrée d’ordre 2 est det(M) = ad − bc

Si det(M) ̸= 0, on dit que la matrice est inversible et son inverse
notée M −1 est donnée par :
 
−1 d −b
M = inverse(det(M)) ×
−c a

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 57

 Que retenir ?

Nous retiendrons que :

les mathématiques notamment l’arithmétique, l’algèbre sont présentes
en cryptographie

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 58

 Que retenir ?

Nous retiendrons que :

les mathématiques notamment l’arithmétique, l’algèbre sont présentes
en cryptographie

l’informatique est présente en cryptographie

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 58

 Que retenir ?

Nous retiendrons que :

les mathématiques notamment l’arithmétique, l’algèbre sont présentes
en cryptographie

l’informatique est présente en cryptographie

la programmation est nécessaire en cryptographie

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 58

 Que retenir ?

Nous retiendrons que :

les mathématiques notamment l’arithmétique, l’algèbre sont présentes
en cryptographie

l’informatique est présente en cryptographie

la programmation est nécessaire en cryptographie

la théorie des codes est présente en cryptographie

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 58

 Que retenir ?

Nous retiendrons que :

les mathématiques notamment l’arithmétique, l’algèbre sont présentes
en cryptographie

l’informatique est présente en cryptographie

la programmation est nécessaire en cryptographie

la théorie des codes est présente en cryptographie

la théorie des nombres notamment la manipulation des nombres est

présente en cryptographie.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 58

 Que retenir ?

Nous retiendrons que :

les mathématiques notamment l’arithmétique, l’algèbre sont présentes
en cryptographie

l’informatique est présente en cryptographie

la programmation est nécessaire en cryptographie

la théorie des codes est présente en cryptographie

la théorie des nombres notamment la manipulation des nombres est

présente en cryptographie.

etc.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 58

 Merci pour votre attention.

Nelson SAHO Facililateur (SecuriGate) Cryptographie appliquée 11 décembre 2023 59

 MA Al-Shabi. A survey on symmetric and asymmetric cryptography
algorithms in information security. International Journal of Scientific and
Research Publications, 9(3) :576–589, 2019.
Whitfield Diffie and Martin Hellman. New directions in cryptography. IEEE
transactions on Information Theory, 22(6) :644–654, 1976.
Renaud Dumont. Cryptographie et sécurité informatique. Eyrolles, 2010,
2009.
Mohammed Erritali, Oussama Mohamed Reda, and Bouabid El Ouahidi.
Contribution à la sécurisation du protocole de routage ‘’greedy perimeter
stateless routing ‘’à l’aide de l’algorithme aes et du hachage md5. Revue
Méditerranéenne des Télécommunications, 2(1), 2012.
Neal Koblitz. Elliptic curve cryptosystems. Mathematics of computation,
48(177) :203–209, 1987.
Victor S Miller. Use of elliptic curves in cryptography. In Conference on the
theory and application of cryptographic techniques, pages 417–426.
Springer, 1985.
Ronald L Rivest, Adi Shamir, and Leonard Adleman. A method for
obtaining digital signatures and public-key cryptosystems.
Communications of the ACM, 21(2) :120–126, 1978.
Peter
Nelson W.
SAHO Shor. (SecuriGate)
Facililateur Polynomial-time algorithms
Cryptographie for prime factorization
appliquée and
11 décembre 2023 60