MATHÉMATIQUES ET INFORMATIQUE

Gilles Dubertret informatique Gilles Dubertret

BTS – DUT – LICENCE
MATHÉMATIQUES ET INFORMATIQUE
INITIATION

BTS – DUT – LICENCE

À LA CRYPTOGRAPHIE INITIATION
À LA CRYPTOGRAPHIE
La cryptographie, appelée science du secret, a vu ses possibilités décuplées au cours des siècles.
Elle fait partie de notre quotidien, que ce soit sur l’Internet ou avec l’apparition des nouvelles
puces RFID présentes dans nos cartes bancaires. Riche de multiples possibilités et méthodes, cette
2e édition

Initiation à la cryptographie
discipline, servant à assurer la sécurité et la confidentialité des communications et des données,
s’impose à tous.
Cette nouvelle édition, revue et augmentée pour prendre en compte les technologies actuelles et
les développements futurs en matière de sécurité, est destinée aux étudiants en premier cycle des
études supérieures des cursus mathématiques et informatique.
On y trouve, dans chaque chapitre, un cours complet et de nombreux exercices corrigés
(actualisés), pour comprendre et maîtriser les mécanismes à l’œuvre dans les échanges de
données. L'ouvrage intègre également toutes les nouvelles méthodes de cryptographie (AES,
chiffrement homomorphe, etc.)
SOMMAIRE
1. Les nombres premiers 10. Courbes elliptiques
2. Éléments d’arithmétique 11. Fonction de Hachage
3. L’algorithme d’Euclide étendu 12. Protocole ZK : Zero Knowledge
4. Le logarithme discret
5. Cryptosystèmes
13. Identification, Authentification, Signature ➔ Cours complet
14. Horodatage et Blockchain
6. Fonctions à sens unique 15. Exemples d’applications à la cryptographie ➔ Plus de 100 exercices
7. Le RSA et le chiffrement Elgamal
8. Le DES
16. Cryptanalyse
17. La cryptographie à travers l’Histoire
d’application corrigés
9. Advanced Encryption Standard (AES)
➔ Programmation avec Maple
Professeur certifié de mathématiques, Gilles Dubertret a enseigné de nombreuses années les mathématiques
et l'informatique au lycée de Sèvres et à l'IUT de Paris (université Paris V / René Descartes).

ISBN : 978-2-311-40615-3

www. .fr

[Link] Toutes les pages 27/07/2018 11:10

 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page i — #1

✐ ✐

Initiation
à la cryptographie

Gilles Dubertret

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page ii — #2

✐ ✐

En couverture : Adobe Stock © weerapart1003

Maquette intérieure et mise en page : Sébastien Mengin - Edilibre
Couverture : Les PAOistes

ISBN : 978-2-311-40615-3

La loi du 11 mars 1957 n’autorisant aux termes des alinéas 2 et 3 de l’article 41, d’une part, que
les « copies ou reproductions strictement réservées à l’usage privé du copiste et non destinées à
une utilisation collective » et, d’autre part, que les analyses et les courtes citations dans un but
d’exemple et d’illustration, « toute représentation ou reproduction intégrale, ou partielle, faite sans
le consentement de l’auteur ou de ses ayants droit ou ayants cause, est illicite » (alinéa 1er de l’article
40). Cette représentation ou reproduction, par quelque procédé que ce soit, constituerait donc une
contrefaçon sanctionnée par les articles 425 et suivants du Code pénal. Le « photocopillage », c’est
l’usage abusif et collectif de la photocopie sans autorisation des auteurs et des éditeurs. Largement
répandu dans les établissements d’enseignement, le « photocopillage » menace l’avenir du livre, car
il met en danger son équilibre économique. Il prive les auteurs d’une juste rémunération. En dehors
de l’usage privé du copiste, toute reproduction totale ou partielle de cet ouvrage est interdite. Des
photocopies payantes peuvent être réalisées avec l’accord de l’éditeur.
S’adresser au Centre français d’exploitation du droit de copie : 20, rue des Grands Augustins, F-75006
Paris. Tél. : 01 44 07 47 70

© Magnard-Vuibert – Août 2018 – 5, allée de la 2e DB, 75015 Paris

Site Internet : [Link]

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page iii — #3

✐ ✐

Table des matières

Introduction xi

1 Les nombres premiers 1

1.1 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Crible d’Ératosthène . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Facteurs premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Complexité, liste des nombres premiers, spirale d’Ulam . . . . . . . . . 4
1.4.1 Notion de complexité algorithmique . . . . . . . . . . . . . . . 4
1.4.2 Liste des nombres premiers . . . . . . . . . . . . . . . . . . . . 7
1.4.3 La spirale d’Ulam . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Décomposition en facteurs premiers . . . . . . . . . . . . . . . . . . . . 9
1.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Éléments d’arithmétique 13
2.1 Congruences dans Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.2 Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.3 Ensemble quotient Z/nZ . . . . . . . . . . . . . . . . . . . . . . 17
2.1.4 Structure algébrique de Z/nZ . . . . . . . . . . . . . . . . . . . 17
2.1.5 Groupe, anneau et corps . . . . . . . . . . . . . . . . . . . . . . 18
2.1.6 Relation d’équivalence . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Cryptographie : César, Vigenère, permutation (Programmation) . . . 20
2.2.1 Système de cryptographie de César . . . . . . . . . . . . . . . . 20
2.2.2 Système cryptographique de Vigenère . . . . . . . . . . . . . . 22
2.2.3 Permutations alphabétiques . . . . . . . . . . . . . . . . . . . . 23
2.3 Divisibilité dans Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.1 Idéal des multiples de a : (a) . . . . . . . . . . . . . . . . . . . 24
2.3.2 Divisibilité et idéaux de Z . . . . . . . . . . . . . . . . . . . . . 25
2.3.3 PPCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.4 PGCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.5 Le Théorème de Gauss . . . . . . . . . . . . . . . . . . . . . . . 27
2.4 PGCD, PPCM et Maple (Programmation) . . . . . . . . . . . . . . . . 29
2.5 Retour aux nombres premiers . . . . . . . . . . . . . . . . . . . . . . . 30
2.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.7 Éléments inversibles de Z/nZ . . . . . . . . . . . . . . . . . . . . . . . 35

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page iv — #4

✐ ✐

iv Table des matières

2.7.1 Indicateur d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.7.2 Petit Théorème de Fermat . . . . . . . . . . . . . . . . . . . . . 37
2.8 Applications et pratique . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.8.1 Cryptographie et algèbre linéaire . . . . . . . . . . . . . . . . . 37
2.8.2 Calcul de ax mod n et le théorème de Fermat . . . . . . . . . . 38
2.8.3 Test de non primalité . . . . . . . . . . . . . . . . . . . . . . . 39
2.8.4 Calcul de ax « à la main ». Notion de cycle . . . . . . . . . . . 39

3 L’algorithme d’Euclide étendu 41

3.1 Présentation de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2 Euclide étendu, inverse de a dans Z/nZ (Programmation) . . . . . . . 43
3.2.1 Euclide étendu . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2.2 Inverse de a dans Z/nZ . . . . . . . . . . . . . . . . . . . . . . 43
3.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4 Le logarithme discret 47
4.1 Racine primitive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2 Critère de primalité de Lehmer . . . . . . . . . . . . . . . . . . . . . . 48
4.3 Racine primitive, grands nombres premiers (Programmation) . . . . . 49
4.3.1 Recherche de racine primitive . . . . . . . . . . . . . . . . . . . 49
4.3.2 Recherche de grands nombres premiers . . . . . . . . . . . . . . 50

5 Cryptosystèmes 53
5.1 Exemples de cryptosystèmes classiques . . . . . . . . . . . . . . . . . . 54
5.1.1 Trois exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.1.2 N-gramme substitution . . . . . . . . . . . . . . . . . . . . . . 54
5.1.3 Permutation d’ordre d . . . . . . . . . . . . . . . . . . . . . . . 54
5.1.4 Playfair Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.1.5 Transformation linéaire . . . . . . . . . . . . . . . . . . . . . . 55
5.1.6 La machine Enigma . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2 Casser un cryptosystème . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.3 Différents niveaux d’attaque . . . . . . . . . . . . . . . . . . . . . . . . 62
5.4 Masque jetable, Vernam (One time pad) . . . . . . . . . . . . . . . . . 63
5.5 Cryptographie quantique . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.6 La Cryptographie militaire (1883), Kerckhoffs . . . . . . . . . . . . . . 64
5.7 Communication Theory of Secrecy Systems, Shannon . . . . . . . . . . 65
5.8 Convertir du texte en nombre (Programmation) . . . . . . . . . . . . . 66

6 Fonctions à sens unique 69

6.1 Fonctions à sens unique . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.2 Sac à dos, Protocole DH, ..., chiffre de Rabin . . . . . . . . . . . . . . 71
6.2.1 Partage de clés : protocole DH . . . . . . . . . . . . . . . . . . 71
6.2.2 Un cryptosystème sans clé . . . . . . . . . . . . . . . . . . . . . 72
6.2.3 Algorithme du sac à dos . . . . . . . . . . . . . . . . . . . . . . 72
6.2.4 Le chiffre de Rabin . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.3 Implémentation avec Maple (Programmation) . . . . . . . . . . . . . . 73

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page v — #5

✐ ✐

Table des matières v

6.3.1 Le sac à dos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.3.2 Partage de clés . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.3.3 Cryptosystème sans clé . . . . . . . . . . . . . . . . . . . . . . 76
6.4 Le théorème du reste chinois et le chiffre de Rabin . . . . . . . . . . . 78
6.4.1 Le théorème du reste chinois . . . . . . . . . . . . . . . . . . . 78
6.4.2 Le chiffre de Rabin . . . . . . . . . . . . . . . . . . . . . . . . . 79

7 Le RSA et le chiffrement Elgamal 81

7.1 Le système RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.2 RSA et Maple (Programmation) . . . . . . . . . . . . . . . . . . . . . 83
7.3 Chiffrement Elgamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

8 Le DES 85
8.1 L’algorithme LUCIFER : notion de ronde . . . . . . . . . . . . . . . . 85
8.2 Le DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
8.3 IDEA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
8.4 Modes de chiffrement par bloc. Mode ECB, CBC, CFB, OFB . . . . . 91
8.5 Ou exclusif et addition modulo 2 (Programmation) . . . . . . . . . . . 93
8.6 Addition modulo 216 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

9 Advanced Encryption Standard (AES) 95

9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
9.2 Les corps finis (Théorie) . . . . . . . . . . . . . . . . . . . . . . . . . . 95
9.2.1 Construction de GF (28 ) . . . . . . . . . . . . . . . . . . . . . . 97
9.2.2 L’anneau GF (28 )[x]/(x4 + 1) . . . . . . . . . . . . . . . . . . . 99
9.3 AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
9.3.1 Les rondes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
9.3.2 La génération des clés de rondes (Key Expansion) . . . . . . . 101
9.3.3 Déchiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
9.4 Maple et le corps de Galois GF (28 ) (Programmation) . . . . . . . . . 102
9.5 Implémentation de l’AES (Programmation) . . . . . . . . . . . . . . . 104
9.5.1 Le corps de Galois GF(28 ) . . . . . . . . . . . . . . . . . . . . . 104
9.5.2 Les routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
9.5.3 KeyExpansion . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
9.5.4 Le chiffrement . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

10 Courbes elliptiques 113

10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
10.2 Courbes elliptiques sur Z/pZ (p premier) . . . . . . . . . . . . . . . . . 115
10.3 Courbes elliptiques sur Z/nZ (n composé) . . . . . . . . . . . . . . . . 116
10.4 Application à la cryptographie . . . . . . . . . . . . . . . . . . . . . . 116
10.5 Application à la décomposition des grands nombres . . . . . . . . . . . 117
10.6 Courbes elliptiques et MAPLE (Programmation) . . . . . . . . . . . . 118
10.6.1 Courbes elliptiques sur R . . . . . . . . . . . . . . . . . . . . . 118
10.6.2 Racine carrée dans Z/pZ . . . . . . . . . . . . . . . . . . . . . . 119
10.6.3 Courbes elliptiques sur Z/pZ (p premier) . . . . . . . . . . . . 120

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page vi — #6

✐ ✐

vi Table des matières

10.6.4 Courbe symétrique par rapport à l’axe Ox . . . . . . . . . . . . 123

10.6.5 Courbes sur Z/nZ (n composé) . . . . . . . . . . . . . . . . . . 123

11 Fonction de hachage 127

11.1 Protocole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
11.2 Empreinte (Hash Code) . . . . . . . . . . . . . . . . . . . . . . . . . . 128
11.3 KECCAK ou SHA-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
11.4 Preuve de travail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
11.5 Générateur Pseudo-aléatoire . . . . . . . . . . . . . . . . . . . . . . . . 131

12 Protocole ZK : Zero Knowledge 133

12.1 Le démon de Quisquater et Guillou . . . . . . . . . . . . . . . . . . . . 133
12.2 Protocole de Fiat-Shamir . . . . . . . . . . . . . . . . . . . . . . . . . 134
12.3 Graphes et cryptographie . . . . . . . . . . . . . . . . . . . . . . . . . 135
12.4 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

13 Identification, Authentification, Signature 139

13.1 Authentification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
13.2 Identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
13.3 Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
13.4 Signature Elgamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
13.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

14 Horodatage et Blockchain 147

14.1 Horodatage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
14.2 Blockchain et le Bitcoin . . . . . . . . . . . . . . . . . . . . . . . . . . 149

15 Exemples d’applications de la cryptographie 153

15.1 PKI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
15.2 L’argent n’a pas d’odeur . . . . . . . . . . . . . . . . . . . . . . . . . . 155
15.3 Organiser une partie de poker sur internet . . . . . . . . . . . . . . . . 155
15.4 HTTPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
15.5 Carte bancaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
15.6 PGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
15.7 Voter via Internet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
15.8 Chiffrement homomorphe . . . . . . . . . . . . . . . . . . . . . . . . . 160
15.9 Secret partagé, Clé partagée . . . . . . . . . . . . . . . . . . . . . . . . 162
15.10 Le WIFI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
15.11 Chiffrement par flot . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
15.12 La lettre recommandée avec AR . . . . . . . . . . . . . . . . . . . . . 164
15.13 Tatouage numérique . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
15.14 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

16 Cryptanalyse 169

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page vii — #7

✐ ✐

Table des matières vii

17 La cryptographie à travers l’Histoire 171

17.1 L’Antiquité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
17.2 La mécanisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
17.3 Systèmes symétriques . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
17.4 Systèmes à clé publique (asymétriques) . . . . . . . . . . . . . . . . . . 172
17.5 Mars 2000 : la signature numérique a valeur légale en France . . . . . 173

Bibliographie 175

Index 177

Les nombres entre crochets, tels que [13], présents dans le texte, renvoient à la biblio-
graphie, en fin d’ouvrage.

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page viii — #8

✐ ✐

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page ix — #9

✐ ✐

Introduction

Contrairement à une idée fort répandue, la cryptographie n’a pas pour seule finalité
la confidentialité des communications, même si cet aspect est absolument essentiel.
Le tableau suivant copié de [14], paru en 1996, le montre bien.

Remarquons tout de suite que les protocoles de preuve à divulgation nulle n’y
apparaissent pas : les développements récents ont conduit la cryptologie vers des
considérations mathématiques très théoriques.
Cette science est un beau mélange de :
— pratiques souvent empiriques ;
— mathématiques élémentaires utilisées avec les systèmes à clé publique ;
— mathématiques au plus haut niveau théorique avec la théorie des langages et
la complexité ;
— informatique tout ce qu’il y a de plus pratique afin d’implémenter correctement
les primitives utilisées ;

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page x — #10

✐ ✐

x Introduction

— informatique théorique, en particulier pour la validation des primitives utili-

sées ;
— probabilité, par exemple avec le problème des générateurs pseudo-aléatoires ;
— ...
À l’origine, cet ouvrage n’était qu’un prétexte pour faire un peu d’arithmétique avec
les étudiants en informatique de l’IUT de Paris. Au fil des ré-éditions, il a grossi,
s’est complété, mais il fallait garder à l’esprit ce qui a fait son succès : un ouvrage
d’initiation, présentant quelques résultats intéressants, mais surtout proposant au
lecteur des idées d’approfondissement et d’exploration.
Et peut-être de se lancer dans des études plus complètes de ce domaine vraiment
pluri-disciplinaire.
[8] propose une première approche, moins technique, de la cryptographie.

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 1 — #11

✐ ✐

CHAPITRE 1

Les nombres premiers

1.1 Nombres premiers

Dans ce chapitre, on ne considère que l’ensemble N des entiers naturels.

Définition 1.1 Un nombre p est premier s’il admet exactement deux diviseurs, 1 et
lui-même.

Remarque : cette définition exclut 1 de la liste des nombres premiers.

Il est facile de vérifier de tête que 7, 13 ou 31 sont des nombres premiers. Quelle
méthode adopter pour montrer que 4999 est premier ?
Premier algorithme
Essayer toutes les divisions de 4999 par D, pour D allant de 2 à 4998.
Si aucune division ne tombe juste, alors on peut affirmer que 4999 est premier.
Deuxième algorithme
En général, l’idée vient assez rapidement de s’arrêter à la moitié de 4999 (le lecteur
est invité à vérifier cette affirmation sur son entourage).
En effet, les quotients pour des diviseurs au delà de 2500 sont inférieurs à 1, et ne
peuvent donc pas être entiers.
Mais il y a mieux : examinons la suite des quotients successifs des divisions de 29 (29
pour simplifier le tableau).

Diviseur 2 3 4 5 6
Quotient 14.5 9.6 7.2 5.8 4.8

Le tableau ci-dessus nous indique que les quotients vont en décroissant. À partir de 6,
les quotients sont plus petits que le diviseur. Aucun de ces quotients pour un diviseur
supérieur à 6 ne peut être entier puisque cela signifierait que 4999 est divisible par
ce quotient. Mais aucune division par un nombre inférieur à 6 n’a donné de quotient
entier. D’où la simplification suivante : √
Essayer toutes les divisions de 29 par D,√pour D allant de 2 à 29
(Plus précisément à la partie entière de 29 + 1)
Avec 4999, on est passé de 4 997 divisions à 70 divisions, ce qui est un gain appréciable
de temps.

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 2 — #12

✐ ✐

2 Chapitre 1. Les nombres premiers

Proposition 1.2 Pour vérifier que√N est premier, il suffit de tester toutes les divisions
de N par D, avec D allant de 2 à N + 1
Cela donne le programme suivant avec MAPLE :

prime1 := proc(n)
local d, t;
t := time() ;
for d from 2 while d2 < n + 1 do
if irem(n, d) = 0 then RETURN(false) fi
od;
RETURN(true, time() − t)
end
Remarque : La variable t n’est utilisée ici que pour connaître le temps de calcul de
cet algorithme, et sera supprimée par la suite.
Troisième algorithme
On peut même encore améliorer √ la méthode en n’essayant que les divisions par les
nombres premiers inférieurs à N + 1, à condition de disposer d’une liste des nombres
premiers.
En effet, si la division par 2 ne tombe pas juste, il est inutile d’essayer les divisions
par les multiples de 2. On les raie tous de la liste des divisions à tester.
Si la division par 3 ne tombe pas juste, il est inutile d’essayer les divisions par les
multiples de 3... √
Il ne reste plus qu’à essayer les divisions par les nombres premiers inférieurs à N +1
Si vous avez une telle liste jusqu’à 1000, cela permet de tester rapidement si un nombre
inférieur à 10002 est premier.
Avec 4999, il ne reste plus que 20 divisions à tester.
Ces considérations nous amènent tout naturellement au crible d’Ératosthène.

1.2 Crible d’Ératosthène

Comment créer une liste des nombres premiers ?
La méthode proposée par Ératosthène 1 , connue sous le nom de « Crible d’Ératos-
thène », donne une solution.
Écrire tous les nombres de 2 à 1000. 2 est premier, on le souligne et on raie tous les
multiples de 2. Le premier nombre non rayé est 3. Il est donc premier, on le souligne
et on raie tous ses multiples. Etc.
Arrivé à 32, qui est supérieur à la racine carrée de 1000, on a terminé : tous les
nombres qui n’ont pas été rayés sont premiers.
La méthode peut paraître efficace, mais elle devient inutilisable pour une table des
nombres premiers jusqu’à 10 000 000 par exemple.

1 Ératosthène : astronome, mathématicien grec (Cyrène, v. 284 - Alexandrie, v. 192).

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 3 — #13

✐ ✐

1.3 Facteurs premiers 3

On peut aussi utiliser le programme ci-dessous qui renvoie le résultat dans

la variable globale l :

listprim1 := proc(n)
local i;
global l;
l := [] ;
for i from 2 to n do if prime1(i) then l := [op(l), op(i)] fi od ;
RETURN(l)
end
Remarque : les procédures présentées dans cet ouvrage sont rédigées avec MAPLE,
mais n’utilisent pratiquement que les boucles classiques « for », « repeat » et « while ».
La seule exception se trouve dans la manière particulière à MAPLE de manipuler les
listes. La ligne 4 de la procédure ci-dessus doit donc être expliquée.
l est une liste. op(l) est la suite des éléments de la liste l. op(l),op(i) est la suite des
éléments de la liste l, suite à laquelle on a ajouté l’élément i. Le tout est remis entre
crochets pour reconstituer une liste.
Cependant, on constate vite que les calculs, rapides au début, deviennent
de plus en plus lents.
Toutes ces méthodes deviennent inefficaces avec des nombres très grands. Estimons
par exemple le nombre de divisions à effectuer pour tester 267 − 1, qui vaut approxi-
mativement 1.47 × 1020 , c’est-à-dire qui s’écrit avec 21 chiffres. Sa racine carrée vaut
approximativement [Link]. Il faudra donc un peu plus d’un milliard de divi-
sions, certaines à dix chiffres ! Bon courage !
(F. Cole a calculé en 1903 que 267 − 1 = 193707721 × 761838257287)
Le package numtheory de MAPLE fournit la procédure isprime(n) qu’il convient de
tester maintenant. Si elle semble être plus rapide pour des nombres de moins de 15
chiffres, ce n’est plus le cas pour des nombres plus grands.
En bref, toutes ces méthodes ne permettent pas de traiter les « grands » nombres pre-
miers. Si on dispose aujourd’hui de tests rapides de primalité, ces tests ne fournissent
pas de diviseurs des nombres qui ne sont pas premiers : la décomposition en facteurs
premiers reste un problème difficile. Nous y reviendrons (voir 4.2 et 4.3.2).

1.3 Facteurs premiers

Existe-t-il de grands nombres premiers ?
La réponse a été fournie par Euclide 2 .

Théorème 1.3 Tout nombre N admet au moins un facteur premier (sauf 0 et 1,

bien sûr).

2 Euclide : mathématicien grec du troisième siècle av. J-C.

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 4 — #14

✐ ✐

4 Chapitre 1. Les nombres premiers

(C’est-à-dire que tout nombre N est divisible par un nombre premier.)

En effet, soit N est premier et il est divisible par lui-même, soit N n’est pas premier
et il admet un certain nombre de diviseurs. Appelons P le plus petit de ces diviseurs.
P est premier car sinon P aurait un diviseur D, plus petit que P , et qui diviserait N .

Théorème 1.4 L’ensemble des nombres premiers est infini.

En effet, si on suppose que cet ensemble est fini, il est composé de n nombres
p1 , p2 , ...pn , alors N = p1 × p2 × . . . × pn + 1 est aussi premier puisqu’il n’est di-
visible par aucun des p1 , p2 , . . . pn . Comme il est plus grand que chacun des nombres
p1 , p2 , . . . pn , il y a contradiction.
On peut donc trouver des nombres premiers aussi grands que l’on veut.
En 1983, le record du nombre premier le plus grand était : 286243 −1, soit un nombre de
trente mille chiffres. Le record a été battu depuis avec un nombre premier comportant
un million de chiffres décimaux.

Théorème 1.5 Tout entier peut se décomposer en produit de facteurs premiers (sauf
0 et 1, bien sûr) : n = pa1 1 × pa2 2 × ... × par r .
(L’unicité de cette décomposition sera démontrée plus tard.)
En effet, si n est premier, la décomposition est toute trouvée.
Sinon, n admet un facteur premier p1 , et un quotient q1 : n = p1 × q1 avec q1 < n.
On recommence avec q1 jusqu’à obtenir un quotient premier.
Conclusion : tout entier n peut s’écrire n = pa1 1 × pa2 2 × ... × par r .

Un autre problème qui s’est posé très tôt est celui de la répartition des nombres
premiers. S’ils apparaissent régulièrement dans la suite des entiers, il sera facile de
déterminer si N est premier ou pas. Hélas...
Par exemple, on montre facilement que la suite des nombres premiers comporte des
« trous » de longueur aussi grande que l’on veut : si on note P le produit des n premiers
nombres premiers, alors tous les nombres P + 2, P + 3, P + 4, ..., P + n sont composés.

1.4 Complexité, liste des nombres premiers, spirale d’Ulam

1.4.1 Notion de complexité algorithmique
La procédure prime1(n) donnée ci-dessus permet de connaître le temps de calcul pour
vérifier que n est premier. Sur l’ordinateur de l’auteur 3 , les essais ont donné le tableau
page suivante :
Quelle est la nature de la relation entre le nombre de chiffres de n et le
temps de calcul ?
Traçons le nuage de points correspondant à ces données, en prenant le logarithme
népérien du temps de calcul (les trois premiers résultats on été exclus). Le package
STATS va nous y aider.

3 En 1998, mais cela ne change rien au problème posé !

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 5 — #15

✐ ✐

1.4 Complexité, liste des nombres premiers, spirale d’Ulam 5

Nombre Nombre de chiffres Temps de calcul en ms

13 2 0
1009 4 0
10007 5 0
100003 6 55
1000003 7 164
10000019 8 494
100000007 9 1922
1000000007 10 6536
10000000019 11 22464
100000000003 12 72116
1000000000039 13 225689
100000000000031 15 2397419

(Ce livre n’ayant pas pour objet le calcul statistique, le deux calculs ci-dessous ne
seront pas détaillés.)
>with ( s t a t s ) :
>Xdata : = [ 6 , 7 , 8 , 9 , 1 0 , 1 1 , 1 2 , 1 3 ] : # nombre de c h i f f r e s
>Ydata := [ 5 5 , 1 6 5 , 5 4 9 , 2 0 3 2 , 6 5 3 6 , 2 2 4 6 4 , 7 2 1 1 6 , 2 2 5 6 8 9 ] :
>LYdata : = [ 4 , 5 . 1 , 6 . 2 , 7 . 6 , 8 . 7 , 1 0 , 1 1 . 2 , 1 2 . 3 ] : #Logarithme
du temps de c a l c u l
>p l o t s [ d i s p l a y ]
> s t a t p l o t s [ s c a t t e r 2 d ] ( Xdata , LYdata ) , # s c a t t e r p l o t
view = [ 0 . . 1 3 , 0 . . 1 3 ] , a x e s = FRAME) ;
Le graphique obtenu est le suivant :

On est frappé par l’alignement des points.

Un ajustement linéaire s’impose.
>fit[leastsquare[[x,y],y=a*x+b]]([Xdata,LYdata]) ;#Calcul de la droite de régression
du nuage
On obtient : y = 1.192419355 x - 3.201129032
y est le logarithme népérien du temps de calcul en fonction du nombre de chiffres de
n. On en déduit facilement la relation suivante entre le temps de calcul et le nombre
de chiffres du nombre premier :
T emps = e(1.2×nombre de chiffres−3.2)

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 6 — #16

✐ ✐

6 Chapitre 1. Les nombres premiers

Cela signifie, en supposant que cette relation reste exacte pour d’autres valeurs que
celles testées, que, pour vérifier par cette méthode qu’un nombre de 100 chiffres est
premier, il faudrait environ 5 × 1050 secondes, soit environ 1, 5 × 1043 années, ce qui
rend la méthode totalement inutilisable.
Même en supposant que l’utilisateur se lance dans la course à l’ordinateur le plus
performant, équipé du dernier modèle de processeur . . . , le temps de calcul restera
rédhibitoire.
Un tel algorithme pour lequel le temps de calcul s’exprime comme une fonction expo-
nentielle de la taille des données est dit de complexité exponentielle.
Par contre, si le temps de calcul s’exprime comme une fonction linéaire de la taille
des données, l’algorithme sera dit de complexité linéaire.
Et, bien sûr, de complexité en n2 si le temps de calcul est une fonction de degré 2 de
la taille des données. (Exemple : l’élévation au carré d’un nombre est de complexité
en n2 , où n est le nombre de chiffres du nombre à élever au carré).
Exercice 1.1. Écrire une procédure qui calcule le carré de 1.000 nombres de 100,
1.000, 10.000 ... chiffres (utiliser la boucle « do ... n2 ... od »), et vérifier cette affirma-
tion avec les méthodes exposées ci-dessus.
Résumé
Un algorithme de complexité exponentielle est en pratique inutilisable.
Des algorithmes de complexité linéaire, en n × Log(n) ou en n2 sont consi-
dérés comme « rapides ».
Pour terminer, signalons que MAPLE fournit la procédure « isprime(n) » qui teste
avec une rapidité surprenante si n est premier. La documentation indique que le test
est « probabiliste ».
Quelle est la signification de cette indication ?
Pour y répondre, supposons que vous soyez candidat à un jeu télévisé et qu’on vous
propose un nombre de 3 chiffres. Question : est-il premier ? Si vous répondez au ha-
sard, vous avez une probabilité faible de répondre juste.
Le test de divisibilité par 2 est immédiat. Si vous l’utilisez, votre probabilité de ré-
pondre juste va augmenter.
Si vous avez le temps, vous appliquerez les tests de divisibilité par 3, puis 5, puis 11...
en augmentant à chaque fois vos chances de réussite.
Si votre nombre n’est divisible ni par 2 ni par 3 ni par 5, vous affirmerez très sérieu-
sement que le nombre est premier.
Bien sûr, les tests utilisés par « isprime(n) » sont plus sophistiqués que ceux décrits
ci-dessus (voir 2.8.3), et donnent de très bons résultats. On n’obtient cependant pas
une certitude mathématique de primalité. Certains auteurs parlent de nombres pre-
miers industriels pour de tels nombres. Leur utilisation en cryptographie est am-
plement satisfaisante.
Insistons : s’il est rapide de vérifier avec une probabilité très proche de 1 qu’un nombre
de 100 chiffres est premier, ou mieux encore si on peut trouver rapidement des nombres
premiers de 200 chiffres en disposant d’une preuve mathématique que le nombre trouvé
est bien premier (voir 4.3.2), il est par contre pratiquement impossible de trou-
ver les diviseurs de n = p × q, avec p et q premiers, p et q s’écrivant avec
100 chiffres.

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 7 — #17

✐ ✐

1.4 Complexité, liste des nombres premiers, spirale d’Ulam 7

1.4.2 Liste des nombres premiers

La liste des nombres premiers (jusqu’à n) peut s’obtenir à la main par le crible d’Era-
tosthène. Pour pouvoir disposer de listes plus complètes, on pourra utiliser l’une ou
l’autre des deux procédures qui suivent. La première utilise prim1(n), la deuxième
crée la liste des nombres premiers et l’utilise pour minimiser le nombre de divisions à
effectuer pour trouver le nombre premier suivant.
Sur l’ordinateur de l’auteur, la première a fourni la liste des nombres premiers infé-
rieurs à 100.000 en 621 secondes, la deuxième en 196 secondes.

listprim1 := proc(n)
local i;
global l;
l := [] ;
for i from 2 to n do if prime1(i) then l := [op(l), op(i)] fi od ;
RETURN(l)
end
listprim2 := proc(N )
local l, n, d, premier ;
l := [2] ;
for n from 3 to N do
premier := true ;
for d in l while d2 < n + 1 do
if irem(n, d) = 0 then premier := false ; break fi
od;
if premier then l := [op(l), op(n)] fi
od;
RETURN(l)
end

1.4.3 La spirale d’Ulam

L’idée due à Stanislaw Ulam 4 est de représenter la suite des nombres premiers en
spirale. On « enroule » la demi droite [0, +∞[ autour de 0. L’option coords=polar
de la procédure plot nous permet de faire cela facilement : on fait correspondre à un
nombre premier p le point du plan de coordonnées polaires (p, p/100).
Les points correspondant à des nombres premiers seront marqués d’une
croix.

4 Stanislaw Ulam : mathématicien américain d’origine polonaise (1909-1984).

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 8 — #18

✐ ✐

8 Chapitre 1. Les nombres premiers

ulam0 := proc(n)
local i, points;
points := [] ;
for i from 2 to n do
if isprime(i) then points := [op(points), [i, 1/100 × i]] fi
od;
plot([points, [t, 1/100 × t, t = 0..n]], style = [point, line],
color = [red, blue], coords = polar , axes = none, symbol = CROSS)
end
La même spirale, sur laquelle ne sont tracés que les nombres premiers jusqu’à 100.000
permet de deviner certaines régularités.
Bien sûr, d’autres façons de construire la spirale sont possibles et permettent de trou-
ver des idées intéressantes sur les nombres premiers.
Signalons enfin un résultat trèsQimportant sur le nombre de nombres premiers infé-
rieurs à n, noté habituellement (n), Q et démontré par des méthodes analytiques qu’il
n’est pas question de développer ici : (n) ≈ n/Log(n) pour n « grand ».

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 9 — #19

✐ ✐

1.5 Décomposition en facteurs premiers 9

Exercice 1.2. Le lecteur est invité à vérifier expérimentalement ce résultat à l’aide

de son ordinateur.

1.5 Décomposition en facteurs premiers

On part de l’idée qu’un nombre est soit premier, soit admet un diviseur premier.
S’il admet un diviseur premier, on effectue la division et on recommence avec le
quotient obtenu.
Ce qui donne la procédure suivante :

facteurs_premiers := proc(n)
local l, d, N ;
l := [] ;
N := n ;
while not isprime(N ) dofor d from 2 while d2 < N + 1 do
if irem(N, d) = 0 then l := [op(l), op(d)] ; N := iquo(N, d) ;
break fi
od
od;
l := [op(l), op(N )]
end
>f a c t e u r s _ p r e m i e r s ( 5 5 5 5 2 5 ) ;
[3 , 3 , 3 , 5 , 5 , 823]
MAPLE p r o p o s e :
>i f a c t o r (555525);
3 2
(3) (5) (823)

1.6 Exercices
Exercices pour programmer
Exercice 1.3. Écrire une procédure vérifiant, pour les entiers inférieurs à 1 000,
10 000..., la conjecture de Goldbach 5 : « Tout entier pair supérieur à 3 peut s’écrire
comme somme de deux nombres premiers ».

Exercice 1.4. De la même façon que dans 1), vérifier que tout entier supérieur à 12
est la somme de deux entiers composés.

5 Christian Goldbach : mathématicien allemand (1690-1764).

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 10 — #20

✐ ✐

10 Chapitre 1. Les nombres premiers

n
Exercice 1.5. On note Fer(n) le nombre 22 + 1, c’est-à-dire le ne nombre de
Fermat 6 . Fermat pensait que Fer(n) était premier pour tout n. Utilisez l’ordinateur
pour montrer qu’il se trompait.

Exercice 1.6. On pose A=101 !+1. Montrer que les 100 nombres consécutifs A+1,
A+2...,A+100 ne sont pas premiers. Pouvez-vous trouver, à l’aide de MAPLE, la plus
petite série de 100 nombres consécutifs dont aucun n’est premier ?

Exercice 1.7. Le schéma de Hörner 7 .

En calcul machine, comme pour un humain, l’addition est une opération rapide, né-
gligeable par rapport à la multiplication.
Combien de temps faut-il pour calculer P (a), où P (x) est un polynôme de degré n et
a un nombre quelconque ?
Transformons l’écriture de P (x) :
P (x) = an xn + an−1 xn−1 + ... + a0 = (...((an x + an−1 )x + an−2 )x + ...) = +a0
Soit a quelconque. On pose :
h n = an
hn−1 = an−1 + a × hn
hn−2 = an−2 + a × hn−1
...
h 0 = a0 + a × h 1
Vérifier que P (a) = h0 . Comparer le nombre de multiplications effectuées pour ce
calcul avec le nombre de multiplications nécessaires pour le calcul direct de P (a).
Programmer les deux algorithmes et tester leurs rapidités relatives.
Exercices mathématiques
Exercice 1.8. Les nombres de Mersenne 8 .
On utilisera la relation xn − 1 = (x − 1) × (xn−1 + xn−2 + ... + x + 1), et 1 + x + x2 +
n+1
x2 + ... + xn = 1−x
1−x (avec x 6= 1)
a) Montrer que, si an−1 est premier, alors a = 2.
b) Montrer que 2p×q − 1 est divisible par 2p−1 . En déduire que 2n − 1 ne peut être
premier que si n est premier.
c) Vérifier que 211 − 1 n’est pas premier.

Exercice 1.9. Vrai/faux : la somme de deux entiers impairs consécutifs est composée.

Exercice 1.10. Vrai/faux : si p est premier, avec p > 5, alors 24 divise p2 − 1.

Exercice 1.11. Vrai/faux : si p et q sont premiers strictement supérieurs à 7 alors

2 903 040 divise (p2 − 1)(q 2 − 1)(p6 − q 6 ).

Exercice 1.12. Est-il possible que N = x2 − y 2 soit premier ?

6 Pierre de Fermat : mathématicien français (Beaumont de Lomagne, 1601 - Castres, 1665). On lui
doit de nombreux résultats en arithmétique, certains utilisés dans ce livre. Le grand théorème de
Fermat n’a été démontré qu’en 1998.
7 William George Horner : mathématicien britannique (1786-1837).
8 L’abbé Marin Mersenne : philosophe et savant français (1588-1648).

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 11 — #21

✐ ✐

1.6 Exercices 11

Solutions des exercices

8 a) Si a 6= 2, alors an − 1 admet comme diviseur a − 1.

b) Utiliser 2p×q − 1 = (2p )q − 1 = (2p − 1) × ((2p )q−1 + ... + 2p + 1)
c) À vérifier avec la calculette.
9 La somme de deux entiers impairs est paire.
10 Utiliser p2 − 1 = (p + 1)(p − 1)
p premier supérieur à 5 est impair donc p − 1 et p + 1 sont pairs.
p − 1, p et p + 1 sont consécutifs. Donc l’un des trois est un multiple de 3, et ce n’est
pas p.
De même, l’un des trois est un multiple de 4 car sinon p − 2 est un multiple de 4 et
p = (p − 2) + 2 = 4x + 2 est pair.
11 Utiliser les mêmes idées. Il reste à vérifier que 5 040 divise p6 − q 6 .
12 Comme x2 − y 2 = (x + y)(x − y), x2 − y 2 ne peut être premier que si (x + y) ou
(x − y) est égal à 1.

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 12 — #22

✐ ✐

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 13 — #23

✐ ✐

CHAPITRE 2

Éléments d’arithmétique

2.1 Congruences dans Z

2.1.1 Introduction

Chacun sait que, s’il est 3 heures, dans 2 heures il sera 5 heures. Normal, puisque
3+2=5.
De même, s’il est 11 heures, dans 2 heures il sera 1 heure. Normal, puisque 11+2=1.
Comment arrive-t-on à ce résultat surprenant ?
En fait, le reste de la division de 13 par 12 est 1 : les calculs d’heure se font modulo
12. On devrait, en fait, écrire 11+2=1 Mod(12) ou encore 11+2=1 [12].
On peut, bien sûr, généraliser et faire des calculs modulo n, n étant un entier quel-
conque.
Si, avec les heures, on travaille avec douze nombres de 0 à 11, dans les calculs modulo
n, on travaille avec n nombres, de 0 a n − 1.
On trouvera ci-après les tables de multiplications modulo 12 et modulo 31.
(Les lignes et colonnes 0 n’ont pas été représentées pour des raisons évidentes.)
Exercice 2.1. Le lecteur est invité à dresser d’autres tables semblables sur son
tableur préféré, en utilisant la fonction Mod : cela représente déjà un petit exercice
intéressant de manipulation d’un tableur.
L’observation des tables modulo 31 et 12 nous réserve quelques surprises.
Par exemple, on constate que :
4 × 3 = 0 [12] Un produit de deux nombres non nuls peut être nul.
8 = 4 × 2 = 4 × 5 [12] On ne peut pas simplifier le 4 dans l’égalité 4×2=4×5
En revanche, ces problèmes n’apparaissent pas dans la table de multiplication modulo
31 (à condition de ne pas inclure le 0).
Dans chaque ligne et chaque colonne on trouve une et une seule fois chaque nombre
de 1 à 30.
En particulier, on trouve une seule fois par ligne ou par colonne le nombre 1.
Par exemple, 14×20=1 [31], ce qui signifie que l’inverse, pour la multiplication modulo
31, de 14 est 20, de la même façon que l’inverse de 5 pour la multiplication ordinaire
est 15 puisque 5 × 15 = 1.
1
Ce résultat peut s’écrire Inv(14)=20 [31] ou encore 14 = 20 [31] ou encore 14−1 =

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 14 — #24

✐ ✐

14 Chapitre 2. Éléments d’arithmétique

20 [31] (le langage MAPLE utilise la notation 1/14 mod(31)).

Finalement, tout nombre, sauf 0, a un inverse modulo 31, et cet inverse peut être
trouvé facilement à l’aide du tableau.
Par contre, seuls 1, 7 et 11 ont un inverse modulo 12.
On arrive ainsi à résoudre l’équation :
14x =5 [31] :
Inv(14)*14x =Inv(14)*5 [31]
x =20*5 [31]
x =7 [31]
Par contre, il n’est pas question de résoudre par cette méthode 9x = 10 [12] puisque
9 n’a pas d’inverse modulo 12. (Vérifier, avec la table de multiplication, que cette
équation n’a pas de solution, mais que 9x = 3 [12] a bien trois solutions).
Les chapitres suivants nous permettrons de clarifier tous ces problèmes.
En chemin, il faudra aborder les notions algébriques de groupes, anneaux et corps, ce
qui obligera à une révision complète des mécanismes de calcul appris à l’école.
La théorie des congruences a, par ailleurs, d’autres applications. Nous verrons com-
ment on peut l’utiliser en cryptographie, c’est-à-dire l’art d’envoyer des messages
secrets.
Exercice 2.2. La table de multiplication modulo 13 a-t-elle les mêmes propriétés
que la table de multiplication modulo 31 ? Quelles autres tables vous donnent des
résultats similaires ?
Table de multiplication modulo 13 (13 est premier).

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 15 — #25

✐ ✐

2.1 Congruences dans Z 15

Table de multiplication modulo 12 (12 est composé).

La table de multiplication modulo 31 nous sera utile dans de nombreux exercices.

Table de multiplication modulo 31.

2.1.2 Congruence
Depuis l’école primaire, chacun sait faire une division : par exemple 7 divisé par 3. Il
y va 2 fois et il reste 1.
Une écriture plus formalisée de ce calcul est : 7 = 3*2+1.
2 est le quotient, et 1 est le reste de la division de 7 par 3.
Cette division est appelée la division euclidienne, et une structure algébrique dans
laquelle une telle division est possible est appelée Anneau euclidien.

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 16 — #26

✐ ✐

16 Chapitre 2. Éléments d’arithmétique

Théorème 2.1 Z est un anneau euclidien, c’est-à-dire que, pour a et b entiers don-
nés, il existe q et r uniques tels que a = bq + r avec 0 ≤ r < |b|.

Remarque : Z est l’ensemble des entiers relatifs. |b| est la valeur absolue de b.
Attention : le reste de la division de −7 par 3 est 2, puisque −7 = 3 × (−3) + 2.

Exercice 2.3. Effectuer la division euclidienne avec a = 7 et b = −3, ou a = −7 et

b = 3, ou a = −7 et b = −3
Trouver sur votre calculatrice, ou tout autre instrument de calcul, les fonctions per-
mettant d’effectuer des divisions euclidiennes.

Définition 2.2 a et b sont congrus modulo n s’ils ont le même reste par la division
par n.
Par exemple, 10 et 1 sont congrus modulo 9.
On écrit 10 ≡ 1 [9] ou 10 ≡ 1 mod(9) ou, plus simplement, 10=1 [9] s’il n’y a pas
d’ambiguïté.
On a de même −8 = 1 [9].
On a vite fait de remarquer que tous les nombres congrus à 1 mod(9) sont de la
forme : (multiple de 9) + 1. Ce qui fait que deux nombres sont congrus modulo 9 si
leur différence est un multiple de 9.
D’où la seconde définition possible :

Définition 2.3 a et b sont congrus modulo n si b − a est un multiple de n, ou encore

si b − a = k × n (k entier).
Le choix dans les exemples ci-dessus de la congruence modulo 9 n’est pas fortuit :
pourquoi, dans la preuve par 9, se permet-on de remplacer 5 734 par 5+7+3+4=19
puis par 1 ?
La première réponse est que 5 734=1 [9] comme on peut le vérifier en effectuant la
division. Il reste cependant à expliquer cette règle d’addition des chiffres de 5 734.
Or, 5 734 = 5*1 000+7*100+3*30+4
Mais 1000=1 [9], 100= 1 [9] et 10=1 1[9].

5 734 = 5*1 000+7*100+3*30+4

On peut donc écrire : = 5*1 +7*1 +3*1 +4 [9]
= 19 [9]
=1 [9]
Voilà donc l’explication de cette règle que tout écolier sérieux se doit de connaître.
Une autre application moins connue est la preuve par onze.
Après avoir remarqué que 10 = −1 [11], 100 = 1 [11], 1 000 = −1 [11], etc., on
remplacera 5 734 par −5 + 7 − 3 + 4 = 3 pour effectuer la preuve par 11. D’autres
preuves peuvent être construites, mais elles risquent d’être moins faciles à mettre en
œuvre. Revenons au calcul ci-dessus. On a constaté que 1 000 = 1 [9], et on en a
déduit que 5*1 000 = 5*1 [9]. Cela mérite d’être prouvé. De même, 10 = 1 [9] et 9 =0
[9] donc 19 = 1 + 0 [9].
Ces calculs sont justifiés par le Théorème suivant :

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 17 — #27

✐ ✐

2.1 Congruences dans Z 17

Théorème 2.4 Si x = x′ [n] et y = y ′ [n] Alors x + y = x′ + y ′ [n] et x ∗ y = x′ ∗ y ′ [n]

Démonstration.
Si x = x′ [n] et y = y ′ [n], c’est-à-dire x − x′ = k × n et y − y ′ = k ′ × n (x − x′ et y − y ′
multiples de n)
alors (x − x′ ) + (y − y ′ ) = (x + y) − (x′ + y ′ ) = k × n + k ′ × n = (k + k ′ ) × n.
Pour la multiplication, la démonstration est similaire après avoir écrit : x×y−x′ ×y ′ =
(x − x′ ) × y + (y − y ′ ) × x′ .
Pour terminer, signalons la fonction Mod de nombreux logiciels : Mod(25,9)=7.
Avec MAPLE : irem(25,9)=7.

2.1.3 Ensemble quotient Z/nZ

On traitera toujours l’exemple de la congruence modulo 9. Classons les entiers selon
. . . -9 =0 =9 =18 =27 . . .
. . . -8 =1 =10 =19 =28 . . .
. . . -7 =2 =11 =20 =28 . . .
la règle de congruence : et c’est tout.
... ... ... ... ...
. . . -2 =7 =16 =25 =34 . . .
. . . -1 =8 =17 =26 =35 . . .
On a construit 9 classes, la classe de 0 notée parfois 0̇, la classe de 1 notée 1̇,... la
classe de 8 notée 8̇.
L’ensemble de ces 9 classes est noté Z/9Z, ensemble quotient de Z par la congruence
modulo 9.
Z/9Z peut être, de manière évidente, muni d’une addition et d’une multiplication :
˙ ou 3*4=12=3 [9] ou enfin 3*4=12 dans Z/9Z (puisque la classe de 12 est
3̇ ∗ 4̇ = 12
3̇). On construit de même l’addition.
Il est important de se familiariser avec ces différentes notations. La dernière est celle
que l’on utilisera lorsque le contexte le permettra.
Les tables données plus haut ne sont rien d’autre que les tables de multiplications
modulo 12, 13 et 31.
Le lecteur est invité à remplir les tables d’addition et de multiplication modulo 9.
+ 0 1 2 3 4 5 6 7 8 * 0 1 2 3 4 5 6 7 8
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8

2.1.4 Structure algébrique de Z/nZ

On montre, et nous y reviendrons, que l’addition conserve toutes les propriétés habi-
tuelles de l’addition de nombres réels : commutativité, associativité, élément neutre
0, et existence d’un opposé.

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 18 — #28

✐ ✐

18 Chapitre 2. Éléments d’arithmétique

Par exemple, l’opposé de 3 dans Z/9Z, noté Opp(3) ou plus simplement −3 vaut 6
(−3 = 6 dans Z/9Z).
La multiplication est commutative, associative, possède un élément neutre 1, et est
distributive par rapport à l’addition (a*(b+c)=a*b+a*c)). On dit que Z/9Z est un
anneau commutatif unitaire.
Par contre, la multiplication nous réserve quelques surprises : si 2 a un inverse,
inv(2)=5 comme on le voit immédiatement sur le tableau puisque 2*5=1 dans Z/9Z,
par contre 0, 3, 6 n’ont pas d’inverse (il n’y a pas de 1 dans les lignes ou colonnes 3
ou 6).
Remarque : La notation inv(2) mod 9 n’est pas jolie ; 1/2 mod(9) est celle utilisée
par MAPLE ; on pourra préférer 2−1 mod(9).
Mieux : 3*6=0 et pourtant 3 et 6 sont différents de 0. Z/9Z possède des diviseurs de 0.

Enfin, notons que la simplification habituelle « si ka = kb alors a = b » est fausse ici

puisque 3 ∗ 2 = 3 ∗ 8 mais 2 différent de 8.
L’examen attentif de la table de multiplication de Z/31Z montre que ces problèmes
ne se posent pas : Z/31Z est un corps.
Ce résultat important est dû au fait que 31 est un nombre premier, et sera démontré
plus tard.

Théorème 2.5 Z/nZ est un corps ⇔ n est premier.

2.1.5 Groupe, anneau et corps

Il est temps de donner des définitions précises de ces trois termes.
1) Un groupe est un ensemble G sur lequel est défini une addition + (ou une multi-
plication ×) vérifiant les propriétés suivantes :
— l’addition est commutative : ∀x ∈ G et ∀y ∈ Gx + y = y + x (Cette propriété
est facultative) ;
— l’addition est associative : ∀x ∈ G , ∀y ∈ G ,∀z ∈ G(x + y) + z = x + (y + z) ;
— il existe un élément neutre 0 vérifiant : ∀x ∈ Gx + 0 = 0 + x = x ;
— tout élément x possède un opposé noté Opp(x) vérifiant x + Opp(x) = 0.
Il s’agit ni plus ni moins des propriétés habituelles de l’addition (sauf si le groupe
n’est pas commutatif).
2) Un anneau est un ensemble A sur lequel sont définies deux opérations + et *
vérifiant :
— A muni de son addition est un groupe commutatif ;
— la multiplication est associative : ∀x ∈ G, ∀y ∈ G, ∀z ∈ Gx∗ (y ∗ z) = (x∗ y)∗ z ;
— la multiplication est distributive par rapport à l’addition : ∀x ∈ G, ∀y ∈ G,
∀z ∈ Gx ∗ (y + z) = x ∗ y + x ∗ z.
Si la multiplication est commutative, l’anneau est dit commutatif.
Si la multiplication possède un élément neutre noté 1, l’anneau est dit unitaire.
Noter que, dans un anneau, un élément x n’a pas nécessairement d’inverse x−1 .
3) Un corps est un anneau unitaire dans lequel tout élément non nul a un inverse.
Sur un corps, toutes les opérations habituelles (sauf peut-être la commutativité de

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 19 — #29

✐ ✐

2.1 Congruences dans Z 19

l’addition) sont valables.

Remarquer cependant que (a+b)2 = a2 +ab+ba+b2 peut être différent de a2 +2ab+b2
si le corps n’est pas commutatif.
Exercice 2.4.
1) Résoudre dans Z/9Z les équations 5x+7=0, et 3x+2=0.
2) Même question dans Z/31Z.
Pour traiter ces exercices, on détaillera tous les mécanismes du calcul.
3) Chercher ce qui caractérise les éléments inversibles de Z/nZ. La démonstration de
ce résultat important sera l’objet d’un chapitre spécial.
Solutions des exercices
1) 5x + 7 = 0 a pour solution x = Inv(5) × 2 = 2 × 2 = 4.
3x + 2 = 0 n’a pas de solution.
2) 5x + 7 = 0 a pour solution x = Inv(5) × 24 = 25 × 24 = 11.
3x + 2 = 0 a pour solution x = Inv(3) × 29 = 21 × 29 = 20.
3) x est inversible dans Z/nZ si, et seulement si, x et n n’ont pas de facteurs premiers
communs.

2.1.6 Relation d’équivalence

Définition 2.6 Une relation R définie sur un ensemble E est une relation d’équiva-
lence si elle est réflexive, symétrique et transitive.

La relation d’équivalence est souvent notée ≡ comme pour la congruence, plutôt

que R.
— Symétrique signifie que si a est en relation avec b(aRb), alors b est en relation
avec a(bRa).
Plus rigoureusement : aRb ⇒ bRa
— Réflexive signifie : ∀a ∈ EaRa
— Transitive signifie : ∀a ∈ E , ∀b ∈ E ∀c ∈ EaRb et bRc ⇒ aRc
Il est important de vérifier immédiatement que la congruence modulo n est une rela-
tion d’équivalence.
Une relation d’équivalence réalise une partition de l’ensemble E : prenons un élément
a et tous les éléments de E qui sont en relation avec a.
On obtient un ensemble noté ȧ dans lequel tous les éléments sont en relation les uns
avec les autres. C’est la classe de a, ȧ.
Recommençons avec un élément b n’appartenant pas à ȧ.
On obtient la classe de b, ḃ.
On continue jusqu’à épuisement de E.
L’ensemble des classes ainsi obtenu est appelé l’ensemble quotient de E par R, et est
noté E/R.
On définit alors l’application surjective ϕ qui à x associe la classe de x, ẋ.
Par exemple ϕ(25) = 7̇ pour la congruence modulo 9.
L’intérêt de la fonction ϕ est d’être parfois un homomorphisme, c’est-à-dire d’être
compatible avec les opérations algébriques.
Par exemple, pour la congruence modulo n, on a ϕ(a × b) = ϕ(a) × ϕ(b) et ϕ(a + b) =

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 20 — #30

✐ ✐

20 Chapitre 2. Éléments d’arithmétique

ϕ(a) + ϕ(b) comme on l’a montré plus haut.

Cela explique le principe de la preuve par 9 : soit à multiplier a = 435 par b = 723.
On obtient a × b = 312 336, opération compliquée que l’on veut vérifier (en fait
435 × 723 = 314 505, ce qui montre que la preuve par 9 n’est pas une preuve car elle
ne détecte pas toutes les erreurs).
D’après ϕ(a × b) = ϕ(a) × ϕ(b), on doit avoir 0 = 3 × 3[9], ce qui est bien le cas. (Pour
détecter plus d’erreurs, faire la preuve par 9, puis par 11, ce qui revient à faire une
preuve par 99).
Exercice 2.5. Démontrer cette dernière affirmation
N.B. ϕ n’est un homomorphisme que si la relation d’équivalence est compatible avec
les opérations définies sur E. C’est-à-dire que, pour une addition par exemple, x ≡ x′
et y ≡ y ′ =⇒ x + y ≡ x′ + y ′ .
Dans Z, la congruence modulo n est une relation d’équivalence, et l’ensemble quotient
de Z par cette relation d’équivalence est Z/nZ.

2.2 Cryptographie : César, Vigenère, permutation (Programmation)

2.2.1 Système de cryptographie de César
Jules César 1 utilisait le système suivant pour communiquer secrètement : chaque
lettre de l’alphabet était décalée de 3 unités. a donnait d, b donnait e, ..., x donnait
a, y donnait b, z donnait c.
Ajoutons à l’alphabet quelques caractères de ponctuation : ’espace’, virgule, point,
’ ?’ et ’ :’ pour disposer d’un alphabet de 31 caractères (31 est magique puisqu’il est
premier).
Avec ces 31 caractères
a devient d
............
z devient ’.’
’Espace’ devient ’ ?’
’,’ devient ’ :’
’.’ devient a
’ ?’ devient b
’ :’ devient c
On reconnaît là une congruence modulo 31 : on commence par remplacer a par 1, b
par 2 ... z par 26 ... ’espace’ par 27, ’,’ par 28, ’.’ par 29, ’ ?’ par 30 et ’ :’ par 0.
Cette convention permet alors d’effectuer des calculs sur le texte.
Le système de César consiste simplement à effectuer une addition de 3 modulo 31 : a
est remplacé par 1, on ajoute 3 pour obtenir 4, et 4 correspond à d. De même, ’.’ Est
remplacé par 29, 29+3 = 1 [31] et 1 correspond à la lettre a.
Ce principe est programmé dans la procédure ci-dessous :
c e s a r := pr o c ( s t )

1 Jules César : homme d’État romain (101 av. J.C. - 44 av. J.C.)

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 21 — #31

✐ ✐

2.2 Cryptographie : César, Vigenère, permutation (Programmation) 21

l o c a l t a b l e 1 , t a b l e 2 , l l , i i , nb , s e c r e t ;
#ne pas u t i l i s e r l a v a r i a b l e i q u i s e r a i t co nfo ndue
a vec l a l e t t r e i
t a b l e 1 := t a b l e ( [ ’ a ’ = 1 , ’ b ’ = 2 , ’ c ’ = 3 , ’ d ’ = 4 , ’ e ’ = 5 , ’ f ’ = 6 , ’ g ’= 7 ,
’ h ’ = 8 , ’ i ’ = 9 , ’ j ’ = 1 0 , ’ k ’ = 1 1 , ’ l ’ = 1 2 , ’m’ = 1 3 , ’ n ’ = 1 4 , ’ o ’=1 5 ,
’ p ’ = 1 6 , ’ q ’ = 1 7 , ’ r ’ = 1 8 , ’ s ’ = 1 9 , ’ t ’ = 2 0 , ’ u ’ = 2 1 , ’ v ’ = 2 2 , ’w’= 2 3 ,
’x ’=24 , ’y ’=25 , ’ z ’=26 , ‘ ‘=27 , ‘ , ‘=28 , ‘. ‘=29 , ‘? ‘=30 , ‘: ‘=0]):
t a b l e 2 := t a b l e ( [ 1 = ’ a ’ , 2 = ’ b ’ , 3 = ’ c ’ , 4 = ’ d ’ , 5 = ’ e ’ , 6 = ’ f ’ , 7 = ’ g ’ ,
8= ’h ’ ,9 = i ,10= j ,11=k ,12= l ,13=m,14=n,15=o ,16=p,17=q ,18= r ,
19=s ,20= t ,21=u,22=v ,23=w,24=x ,25=y ,26= z ,2 7 = ‘ ‘ , 2 8 = ‘ , ‘ ,
29= ‘. ‘ ,30= ‘? ‘ ,0= ‘: ‘]):
l l := l e n g t h ( s t ) ; i f l l =0 then RETURN f i ;
secret := ‘ ‘;
f o r i i from 1 t o l l do
nb:= t a b l e 1 [ s u b s t r i n g ( s t , i i ) ] ;
# l a l e t t r e e s t t r a n s f o r m é e en nombre
nb:=nb+3 mod 3 1 ; #D é c a l a g e de 3 u n i t é s .
#Mettre i c i l a t r a n s f o r m a t i o n de v o t r e c h o i x
s e c r e t := c a t ( s e c r e t , t a b l e 2 [ nb ] ) ;
od ;
RETURN( s e c r e t ) ;
end :
Exemple :
> c e s a r ( ‘ b o n j o u r mo nsieur l e p r e s i d e n t ,
comment a l l e z vous ? ‘ ) ;
erqmrxu ? pr qvlhxu ? oh ? suhvlghqw : ? frpphqw ? dooh . ? yrxvb
Explication : avec table1, la procédure convertit chaque lettre en nombre ; ce nombre
est augmenté de 3 modulo 31 à la ligne 16. Table2 restitue la lettre correspondant au
résultat.
Pour déchiffrer le message il suffit de remplacer la ligne 16 par :
>nb :=nb-3 mod 31 ;
La ligne (>nb :=nb+3 mod 31) peut être modifiée à la convenance du lecteur (sous
réserve que la fonction obtenue réalise une bijection de Z/31Z, sinon le déchiffrage du
message risque d’être compromis), par exemple >nb :=15*nb+13. Avec cette nouvelle
règle de calcul, on obtient, par exemple, pour les lettres a et b :
a -> 1 -> 15*1+13 = 28 [31] -> ’,’
b -> 2 -> 15*2+13 = 12 [31] -> l
Pour déchiffrer un message obtenu avec cette règle, il conviendra de remplacer la
ligne (nb :=nb+3 mod 31 ;) par : 29*(nb-13) ; Que vient faire ce 29 ? l’explication sera
donnée en 2.7.1.
Exercice 2.6.
— Sauriez-vous déchiffrer le message suivant (obtenu avec la procédure cesar()) :
‘xqh ?urfkh ?hvw ?glwh ?shuphdeoh ?oruvtx ?hooh ?flufxohu
?gh ?o ?hdx ?gdqv ?vhv ?sruhv ?rx ?vhv ?ilvvxuhv‘

✐ ✐

✐ ✐
 ✐ ✐

“InitCrypto” — 2018/7/31 — 17:48 — page 182 — #192

✐ ✐

✐ ✐

✐ ✐
 MATHÉMATIQUES ET INFORMATIQUE
Gilles Dubertret informatique Gilles Dubertret
BTS – DUT – LICENCE
MATHÉMATIQUES ET INFORMATIQUE
INITIATION

BTS – DUT – LICENCE

À LA CRYPTOGRAPHIE INITIATION
À LA CRYPTOGRAPHIE
La cryptographie, appelée science du secret, a vu ses possibilités décuplées au cours des siècles.
Elle fait partie de notre quotidien, que ce soit sur l’Internet ou avec l’apparition des nouvelles
puces RFID présentes dans nos cartes bancaires. Riche de multiples possibilités et méthodes, cette
2e édition

Initiation à la cryptographie
discipline, servant à assurer la sécurité et la confidentialité des communications et des données,
s’impose à tous.
Cette nouvelle édition, revue et augmentée pour prendre en compte les technologies actuelles et
les développements futurs en matière de sécurité, est destinée aux étudiants en premier cycle des
études supérieures des cursus mathématiques et informatique.
On y trouve, dans chaque chapitre, un cours complet et de nombreux exercices corrigés
(actualisés), pour comprendre et maîtriser les mécanismes à l’œuvre dans les échanges de
données. L'ouvrage intègre également toutes les nouvelles méthodes de cryptographie (AES,
chiffrement homomorphe, etc.)
SOMMAIRE
1. Les nombres premiers 10. Courbes elliptiques
2. Éléments d’arithmétique 11. Fonction de Hachage
3. L’algorithme d’Euclide étendu 12. Protocole ZK : Zero Knowledge
4. Le logarithme discret
5. Cryptosystèmes
13. Identification, Authentification, Signature ➔ Cours complet
14. Horodatage et Blockchain
6. Fonctions à sens unique 15. Exemples d’applications à la cryptographie ➔ Plus de 100 exercices
7. Le RSA et le chiffrement Elgamal
8. Le DES
16. Cryptanalyse
17. La cryptographie à travers l’Histoire
d’application corrigés
9. Advanced Encryption Standard (AES)
➔ Programmation avec Maple
Professeur certifié de mathématiques, Gilles Dubertret a enseigné de nombreuses années les mathématiques
et l'informatique au lycée de Sèvres et à l'IUT de Paris (université Paris V / René Descartes).

ISBN : 978-2-311-40615-3

www. .fr

[Link] Toutes les pages 27/07/2018 11:10