mise à jour: 2016

Une introduction élémentaireà la Cryptographie

Théorie des Nombres et Cryptographie
en France
École Polytechnique
INRIA Rocquencourt
École Normale Supérieure
Université de Bordeaux
ENST Télécom Bretagne
Université de Caen + France Télécom R&D
Université de Grenoble
Université de Limoges
Université de Marseille
Université de Toulon
Université de Toulouse

Michel Waldschmidt
Université P. et M. Curie - Paris VI

http://www.math.jussieu.fr/~miw/

http://www.math.jussieu.fr/~miw/

http://www.lix.polytechnique.fr/

ENS

Caen

INRIA
Brest

École PolytechniqueLaboratoire d’Informatique LIX

X

Limoges
Grenoble

Bordeaux

Toulouse

ToulonMarseille

http://www.lix.polytechnique.fr/english/us-presentation.pdf

http://www-rocq.inria.fr/codes/

Institut National de Recherche en
Informatique et en Automatique

http://www.math.u-bordeaux1.fr/maths/

Institut de Mathématiques de
Bordeaux

http://www.di.ens.fr/CryptoRecherche.html

École Normale Supérieure

http://departements.enst-bretagne.fr/sc/recherche/turbo/

École Nationale Supérieure desTélécommunications de Bretagne
Turbocodes

Réseaux etcombinatoirehttp://www-fourier.ujf-grenoble.fr/

Cryptologie à Grenoble

Cryptologie à Caen
http://www.math.unicaen.fr/lmno/

GREYC Groupe de Recherche en Informatique,
Image, Automatique et Instrumentation de Caen

http://www.grey.unicaen.fr/! ACI (Action concertée
incitative)! CNRS (Centre National dela Recherche Scientifique)! Ministère délégué àl’Enseignement Supérieuret à la Recherche! ANR (Agence Nationale
pour la Recherche)

France Télécom R&D Caen

LIMOGES

Marseille: Institut de Mathématiquesde Luminy

Arithmetic and Information Theory
Algebraic geometry over finite fields

http://www.xlim.fr/

http://www.univ-tln.fr/

Université du Sud Toulon-Var

Université de Toulouse

http://www.laas.fr/laas/

IRIT: Institut de Recherche en
Informatique de Toulouse

LILAC: Logic, Interaction,
Language, and Computation
http://www.irit.fr/

IMT: Institut de Mathématiques de Toulouse
http://www.univ-tlse2.fr/grimm/algo

http://www.ias.ac.in/resonance/

A sketch of Modern Cryptology
by Palash Sarkar

Volume 5 Number 9 (september 2000), p. 22-40

Crypter pour la sécurité

Larry Landweber's International Connectivity maps

Larry Landweber's International Connectivity maps

1997

Sécurité des communications: téléphones,
télécommunications, télévision cryptée,…

1994

Mathématiques en cryptographie• Algèbre
• Arithmétique, théorie
des nombres• Géométrie
• Topologie, tresses• Probabilités

Le protocole• Alice ferme la valise avec son cadenas et sa clé etl’envoie à Bob.
• Bob y met son propre cadenas et renvoie à Alice lavalise avec les deux cadenas.
• Alice enlève son cadenas grâce à sa clé et renvoie lavalise à Bob.
• Finalement Bob peut ouvrir la valise grâce à sa clé.
• But: en donner une traduction mathématique.

Échange de valises• Alice a une valise, un cadenas et une clé; elle veut
envoyer la valise à Bob sans que Charlie ne puisse
savoir ce qu’il y a dedans.
• Bob possède aussi un cadenas et une clé, mais qui nesont pas compatibles avec ceux d’Alice.

Cartes à puce

ATM: AutomatedTeller MachineLa carte à puce a été inventée par deux ingénieurs
français,
Roland Moreno (1974) et Michel Ugon (1977)• La sécurité des cartes à puces fait intervenir trois
processus différents; le code PIN, le protocole RSA etle code DES.

Code secret d’une carte bancaire• Vous devez vous identifier auprès de la banque. Vousavez deux clés: une publique que tout le mondeconnaît, une secrète (le code PIN) que personne d’autre
que vous ne connaît.

http://www.cartes-bancaires.com

La carte à puce.
• Les messages que vous envoyez ou que vous recevez
ne doivent pas révéler votre code secret.
• Tout le monde (y compris la banque) ayant accès aux
messages échangés peut vérifier que vous connaissez
ce code secret, mais cela ne leur permet pas de leconnaître.
• La banque vous envoit un message aléatoire.
• Votre réponse dépend de ce message et de votre code
secret.

Cryptographie:aperçu historique
Transpositions alphabétiques et substitutions• Jules César: remplacer une lettre par une autre dansle même ordre (décalage)• Exemple: (décaler de 3) remplacer
ABCDEFGHIJKLMNOPQRSTUVWXYZpar
DEFGHIJKLMNOPQRSTUVWXYZABC• Exemple:
CRYPTOGRAPHIE devient FUBSWRJUDSKLH• Exemples plus sophistiqués: prendre une permutationquelconque (ne respectant pas forcément l’ordre).

• 800-873, Abu Youssouf Ya qub Ishaq Al
Kindi
Manuscrit sur le décryptage desmessages.
Vérification de l’ authenticité des textes
sacrés de l’Islam.
• XIIIè siècle, Roger Bacon: sept méthodes
pour chiffrer des messages.

Frequency of lettersin english texts•1586, Blaise de Vigenère(clé: «table of Vigenère»)Cryptographe, alchimiste, écrivain, diplomate• 1850, Charles Babbage (fréquencelettres)
Machine de Babbage (ancêtre de l’ordinateur)
Ada, comtesse de Lovelace: premier programmeof desAlphabet
International deMorse

Déchiffrage des hiéroglyphes• Jean-François
Champollion(1790-1832)• Pierre de Rosette (1799)

Samuel Morse,
1791-1872

Transmission des données• Pigeons voyageurs : première croisade –Siège de Tyr, Sultan de Damas• Guerre franco-allemande de 1870, siège de Paris• Centres militaires pour l’étude despigeons voyageurs : Coëtquidan et Montoire.

Transmission des données• James C. Maxwell(1831-1879)• Électromagnétisme
Herz, Bose: radioAuguste Kerckhoffs«La cryptographie militaire»,
Journal des sciences militaires, vol. IX,
pp. 5–38, Janvier 1883,
pp. 161–191, Février 1883 .

Toute méthode de chiffrement doit être supposée
connue par l'ennemi: la sécurité du système doit
dépendre uniquement du choix de clés, qui doiventêtre changées régulièrement.

Alan Turing
Déchiffre les messages dela machine Enigma

1917, Gilbert Vernam (masque jetable)
Exemple: le téléphone rouge entre le Kremlin et la
Maison Blanche
Message Original:
Clé
Message envoyé

011000101…
0 0 1 1 0 1 0 0 1…
0 1 0 1 0 1 1 0 0…

=
+
+
=

1950, Claude Shannon pour garantir la sécurité, il faut uneclé secrète au moins aussi longue que le message à
envoyer.

Colossus
Max Newman,
premier ordinateur électronique programmable(Bletchley Park, avant1945)

Début de l’informatiqueThéorie de l’information
Claude Shannon
A mathematical theory of communication
Bell System Technical Journal, 1948.

SécuritéSécurité inconditionnelle: le message codé ne révèle
aucune information sur le message source, la seuleméthode est d’essayer toutes les clés possibles.
En pratique, aucun système utilisé dans la réalité nesatisfait cette condition.
Sécurité pratique: le message codé ne donne aucune
information sur le message source en un temps
raisonnable.

Claude E. Shannon" Communication Theory of Secrecy Systems ",Bell System Technical Journal ,28-4 (1949), 656 - 715.

DES:
Data Encryption Standard
En 1970, le NBS (National Board of Standards)
lance un appel d’offre au Federal Register pour définir
un algorithme de cryptage• ayant un niveau de sécurité élevé qui ne dépend pas dela confidentialité de l’algorithme mais seulement desclés secrètes,• qui fait intervenir des clés secrètes pas trop grandes,• rapide, robuste, bon marché,• facile à implémenter.
Le DES a été approuvé en 1978 par le NBS

L’algorithme DES:
combinaisons, substitutions et permutations entre
le texte et la clé• Le texte est découpé en blocs de 64 bits
• Les blocs sont permutés• Ils sont coupés en deux: droite et gauche• On effectue 16 fois un cycle de permutations et desubstitutions faisant intervenir la clé secrète• On regroupe les parties gauche et droite puis on
effectue les permutations inverses.

Cryptographie
Symétrique versus Asymétrique• Symétrique (clé secrète):• Asymétrique (clé publique)• Alice et Bob ont chacun une • Alice trouve l’adresse de Bob
clé de la boîte aux lettres.
dans un annuaire public, elle
Alice utilise sa clé pourenvoie sa lettre à Bob, qui
déposer sa lettre dans lautilise sa clé secrète pour laboîte. Bob utilise sa clé pourlire.
récupérer la lettre.
• Alice et Bob sont les seuls à • Tout le monde peut envoyer
pouvoir ouvrir la boîte aux
un message à Bob, lui seullettres.
peut les lire.

Diffie-Hellman:
Cryptographie à clé publique• Whit Diffie andMartin E. Hellman,
New directions incryptography,
IEEE Transactions
on Information Theory,22 (1976), 644-654

RSA(Rivest, Shamir, Adleman - 1978)

R.L. Rivest, A. Shamir,
et L.M. Adleman
A method for obtaining digital signatures and publickey cryptosystems,
Communications of the ACM(2) 21 (1978), 120-126.

Fonction trappex→ y
est une fonction trappe – à sens unique si! Étant donné x, il est facile de calculer y! Étant donné y , il est difficile de trouver x, sauf si on
connaît une clé.
Les exemples font intervenir des problèmes
mathématiques connus pour être difficiles.

Exemple d’une
fonction trappe:
le logarithme discret(version simplifiée)
On part d’un nombre à trois chiffres x.
On calcule le cube de x, à savoir : x× x× x = x3.
On ne conserve que les trois derniers chiffres = reste dela division par 1000: c’est y.
• Partant de x, trouver y est facile.
• Connaissant y, retrouver x est difficile.

Le logarithme discretmodulo 1000
• Exemple: sachant que les trois derniers chiffres de x3 sont631, ce que l’on écrit x3 ≡ 631 modulo 1000, trouver x.
• Solution brutale: essayer toutes les valeurs de x=001,
002, …
on trouve ainsi x=111 – c’est la seule solution.
• Vérification: 111 × 111 = 12 321• On ne garde que les trois derniers chiffres:1112 ≡ 321 modulo 1000
• Puis 111 × 321 = 35 631

Racine cubique modulo 1000
Racine 7ème modulo 1000
Résoudre x3 ≡ 631 modulo 1000.
• Autre méthode: utiliser une clé secrète.
La clé publique est 3, car on calcule x3.
Une clé secrète est 67.
• Cela signifie que si on calcule la puissance 67 de 631,
on trouve x:
63167 ≡ x modulo 1000.
• (x3)67 ≡ x modulo 1000

• Pour une clé publique 3, une clé secrète est 67.
• Autre exemple: clé publique 7, clé secrète 43.
• Sachant x7 ≡ 871 modulo 1000
• on calcule 87143 ≡ 111 modulo 1000
• donc x = 111.

Protocole de l’échange de valises

Échange de valises• Alice a une valise, un cadenas et une clé; elle veut
envoyer la valise à Bob sans que Charlie ne puisse
savoir ce qu’il y a dedans.
• Bob possède aussi un cadenas et une clé, mais qui nesont pas compatibles avec ceux d’Alice.

111

7

3

1117 ≡ 871

43

6731143 ≡ 631

8713 ≡ 311

63167 ≡ 111

111

ATM

Cartes à puce
messagealéatoire

Code
Pin

Clé
Publique

631

67

3

63167 ≡ 111

1113 ≡ 631

Connaissant la clé publique 3 et le message 631
envoyé par la banque, on vérifie que la réponse 111
est correcte, mais cela ne permet pas de deviner lecode secret 67.

Message modulo n• On choisit un entier n (à la place of 1000): c’est la
taille des messages qui seront échangés.
• Tous les calculs seront faits modulo n : on remplacechaque entier par le reste de sa division par n.
• n sera un entier avec environ 300 chiffres.

Il est plus facile de vérifier unedémonstration que de la trouver
Multiplier deux nombres, même un peu grands,
est facile.
Si on sait qu’un nombre donné est le produit dedeux nombres, trouver les facteurs peut êtredifficile.
2047 est-il le produit de deux nombres plus
petits?
Réponse: oui 2047=23×89

Exemple
p=111395432514882798792549017547702484
4070922844843
q=191748170252450443937578626823086218
0696934189293
pq=21359870359209100823950227049996287
9705109534182641740644252416500858395
7746445088405009430865999

Tests de primalitéetalgorithmes de factorisation• Étant donné un entier, déterminer s’il est premier ou
non (test de primalité).
• Étant donné un nombre composé, trouver sa
décomposition en facteurs premiers (algorithme defactorisation).

Choix de n
On prend pour n le produit de deux nombres
premiers de 150 chiffres chacun
Le produit a environ 300 chiffres: les ordinateurs
ne peuvent pas actuellement trouver les
facteurs.

Tests de primalité• Étant donné un entier, déterminer s’il est premier ou
nonLimite actuelle: environ 1000 chiffres

Algorithmes de factorisation• Étant donné un nombre composé, trouver sa
décomposition en facteurs premiers
Limite actuelle: environ 150 chiffres

Agrawal-Kayal-Saxena• Manindra Agrawal,
Neeraj Kayal and Nitin
Saxena, PRIMES is in
P(July 2002)

Nombres premiers industriels• « Tests » probabilistes: ne garantissent pas qu’unnombre est premier: un faible taux d’erreur est toléré.

http://www.cse.iitk.ac.in/news/primality.html

Les quatre plus grands
nombres premiers explicites
7 janvier 2016274 207 281 -1
22 338 618 chiffres décimaux

8 février 2013

257885161 -1
17 425 170 chiffres

23 août 2008

243 112 609 -1
12 978 189 chiffres

12 avril 2009242 643 801 -1

Through the EFF Cooperative Computing Awards,
EFF will confer prizes of:* $50 000 to the first individual or group who discovers a prime number
with at least 1 000 000 decimal digits (6 avril 2000)* $100 000 to the first individual or group who discovers a prime number
with at least 10 000 000 decimal digits (6 septembre 2008)* $150 000 to the first individual or group who discovers a prime number
with at least 100 000 000 decimal digits.
* $250 000 to the first individual or group who discovers a prime number
with at least 1 000 000 000 decimal digits.

12 837 064 chiffres
http://primes.utm.edu/largest.html

http://www.eff.org/awards/coop.php

Grands nombres premiers• Les 11 plus grands nombres premiers connus sont de laforme 2p -1 (on en connaît 49)• On connaît
170 nombres premiers ayant plus de 1 000 000 chiffres
1498 nombres premiers ayant plus de 500 000 chiffres.
• Liste des 5 000 plus grands nombres premiers connus :http://primes.utm.edu/primes/

Mise à jour: 9 mai 2016

Nombres de Mersenne(1588-1648)• Nombres de la forme Mp=2p -1 avec p premier.
• On en connaît seulement 49 , les plus petits sont
3, 7, 31, 127•
3= M2= 22 -1, 7= M3= 23 -1,
31=5
7
M5= 2 -1, 127= M7= 2 -1
• 1536, Hudalricus Regius: M11= 211 -1 n’est
pas premier: 2047= 23× 89.

Nombres parfaits
Marin Mersenne (1588-1648), préface deCogitata Physica-Mathematica (1644): les nombres
2n -1 sont premiers pourn = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 et 257
et ils sont composés pour toutes les autres valeurs den < 257.
Liste corrigée:
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 et 127.
http://www.mersenne.org/• Un entier n est parfait s’il est égal à la somme
de ses diviseurs en omettant n.
• Les diviseurs de 6 sont 1, 2, 3 et 6=1+2+3.
• Remarque: 6=2 × 3 et 3=M2=22-1.
• 6 est un nombre parfait.

Nombres parfaits• Les diviseurs de 28 sont 1, 2, 4, 7, 14 et
28=1+2+4+7+14.
• Remarque: 28=4 × 7 et 7=M3=23-1.
• Autres nombres parfaits:
496=16 × 31=24M5 et M5=25-1,
8128=64 × 127=26M7 et M7=27-1,…

Nombres de Fermat(1601-1665)• Un nombre de Fermat est un nombre de la formen
Fn=22 +1.
• Construction à la règle et au compas de polygones
réguliers.
• F1=5, F2 =17, F3=257, F4=65537 sont desnombres premiers• Fermat a suggéré en1650 que tous les Fn seraient
premiers.

Nombres parfaits pairs (Euclide)• Les nombres parfaits pairs sont les nombres dela forme 2p-1 × Mp avec Mp = 2p -1 nombre
premier de Mersenne (donc p est premier).
• Y a-t-il une infinité de nombres parfaits?
• Existe-t-il des nombres parfaits impairs?

Euler(1707-1783)• F5 = 232+1 est divisible par 641
4 294 967 297= 641 × 6 700 417

F5=232 +1 est divisible par 641
641= 625 + 16 = 54 + 24•
• 641=5×128 + 1= 5 × 27 + 1• 641 divise x= 228 × (54 + 24)=54×228 + 232• t4-1=(t+1)(t-1)(t2+1)
t=5 × 27=640
641 divise y=(5 × 27) 4- 1= 54×228 – 1• Donc 641 divise x-y=232 + 1

Nombres premiers de Fermat• Factorisés: F5, F6, F7, F8, F9, F10, F11• F11 = 319489 · 974849 · 167988556341760475137 ·
3560841906445833920513 · P564

Nombres premiers de Fermat• Y a-t-il une infinité de nombres premiers de Fermat?
• On en connaît seulement cinq
F0=3, F1=5, F2 =17, F3=257, F4=65537.
• The On-Line Encyclopedia of Integer Sequences
http://oeis.org/A000215

Algorithmes de factorisation• Décomposer un entier en facteurs premiers• Limite actuelle: environ 150 chiffres décimaux pour unentier au hasard• Algorithme le plus efficace pour les grands nombres:
number field sieve (crible de théorie des nombres)

http://www.prothsearch.net/fermat.html

http://www.crypto-world.com/FactorWorld.html

Challenge Number Prize $US• RSA-576 $10,000 Factorisé en Décembre 2003
• RSA-640 $20,000 Factorisé en Novembre 2005
• RSA-704 $30,000 Non Factorisé• RSA-768 $50,000 Factorisé en Novembre 2009
• RSA-896 $75,000 Non Factorisé• RSA-1024 $100,000 Non Factorisé• RSA-1536 $150,000 Non Factorisé• RSA-2048 $200,000 Non Factorisé
http://www.rsasecurity.com/rsalabs/Fermé en 2007

RSA-704 Prize: $30,000
Status: Not Factored
Decimal Digits: 212• 74037563479561712828046796097429573142593188
88923128908493623263897276503402826627689199
64196251178439958943305021275853701189680982
86733173273108930900552505116877063299072396
380786710086096962537934650563796359• Digit Sum: 1009

RSA-768
Status: Factored December 12, 2009
Decimal Digits: 232 Digit sum 1018
1230186684530117755130494958384962720772853569595334792197322452151726400
5072636575187452021997864693899564749427740638459251925573263034537315
4826850791702612214291346167042921431160222124047927473779408066535141
9597459856902143413=
3347807169895689878604416984821269081770479498371376856891243138898288379
3878002287614711652531743087737814467999489*
3674604366679959042824463379962795263227915816434308764267603228381573966
6511279233373417143396810270092798736308917

http://www.crypto-world.com/announcements/rsa768.txt

Autres problèmes de sécurité dans lemonde industriel moderne• Signatures digitales• Identification• Partage de secrets• Zero knowledge proofs

Tendances actuelles
en cryptographie• Calculer modulo n signifie travailler dans le groupe
multiplicatif des entiers modulo n• Des groupes de grande taille sont nécessaires.
• On peut remplacer ce groupe par un autre dans lequelon calcule facilement, et dans lequel le logarithme
discret est un problème difficile.
• Pour les cartes à puce, les téléphones portables … il
faut un objet mathématique petit.
• Les courbes elliptiques sur les corps finis sont de bons
candidats.

Directions de recherche
Calculer efficacement le groupe despoints d’une courbe elliptiquerationnels sur un corps fini
Vérifier la vulnérabilité aux attaques connues
Trouver de nouveaux invariants pour développer denouvelles attaques
Genre supérieur: logarithme discret sur la jacobienne decourbes algébriques

Cryptographie quantique• Peter Shor – résonnance magnétique nucléaire

Quizz: How to become a hacker?
Answer: Learn mathematics !

•http://www.catb.org/~esr/faqs/hacker-howto.html

27 juin 2013
Université de Pau et des Pays de l'Adour
Laboratoire de Mathématiques et de leurs applications
Colloquium de mathématiques

Introduction à la
Cryptographie
Michel Waldschmidt
Université P. et M. Curie - Paris VI
http://www.math.jussieu.fr/~miw/