Embed Size (px)
Citation preview
Des mathématiques pour protéger les communications
2
Certains messages ne doivent pas tomber dans les mains de n'importe qui. Voilà des millénaires que les hommes tentent de sécuriser les messages qu’ils s’envoient…
Hérodote (Ve s. av. J.-C.) raconte comment Demaratus informa Sparte que Xerxès rassemblait la plus grande armée jamais connue pour envahir la Grèce. Il gratta la cire de deux tablettes de bois pliantes et grava le texte directement sur le bois, puis recouvrit d’une couche de cire vierge. Son messager pu avertir Sparte, et les Grecs eurent le temps de construire 200 navires de guerre pour remporter la bataille de Salamine.
3
Dans La Poliorcétique (IVe s. av. J.-C) Enée donne des conseils pour défendre une ville ou la conquérir. Il explique plusieurs procédés destinés à camoufler les messages, comme :
Ecrire un texte sur les boucles d'oreille d'une femme élégante qui n'éveillera aucun soupçon,
Ecrire un message sous une image pieuse que le destinataire grattera,
Percer un dé autant de fois qu'il y a de lettres de l'alphabet, retenir la lettre correspondant à chaque trou, puis faire passer un fil d'un trou à l'autre en suivant l'ordre des lettres du message,
Ou écrire au fer rouge sur la tête d’un esclave et attendre que ses cheveux repoussent (ruse d'Histiæus pour avertir le roi de Milet).
4
Texte extrait d'un polycopié de logique combinatoire sur le problème des ponts de Königsberg, tapé par un mathématicien de RDA et expédié à un collègue d'Allemagne de l'Ouest.
Ce texte anodin a traversé la censure. Pourtant…
5
Des lettres ont été décalées pour former le message : « nieder mit dem sowjetimperialismus »
« A bas l'impérialisme soviétique ».
6
Stéganos = couvert Graphein = écriture
James Bond : technique des micro-points (espions soviétiques et allemands première moitié du XXe s.),
Encre sympathique (jus de citron),
Coquilles d’œufs durs (encre vinaigre/alun),
Message dans un clou enfoncé dans une planche,
Fichier jpeg envoyé par mél…
7
La stéganographie cache l'existence d'un message.
La cryptographie rend un message inintelligible.
Stéganos = couvert Kruptos = caché
8
CryptographieCodes
Chiffres
9
Le code le plus connu en France au XIXe s.
Utilisé pour la télégraphie et les messages personnels dans les journaux.
Clé : un dictionnaire et des pages numérotées comme on le désirait.
Messages : 8264 pour texte n°64 à la page 82 (ou autres combinaisons possibles).
10
Grèce
Ve s. av. J.-C.
Siècle de Périclès
L’un des premiers exemples de chiffrement
11
Utilisé jusqu’au XIXe siècle car très pratique
Pigpen = parc à cochons
12
A B C
D E F
G H I
J K L
M N O
P Q R
S
T
U
V X
Y
Z
W
RASSEMBLEMENT
Chiffrement
à clé secrète
à clé révélée
13
14
15
Pendant la guerre des Gaules, Jules César (101-44 av. J.-C.) envoyait des messages chiffrés à Cicéron qui était resté au sénat à Rome. Il envoyait des messages où les lettres étaient décalées de 3 places dans l'alphabet.
16
Solide jusqu’aux années 800.
Pour étudier des textes et savoir s’ils émanent du prophète, les arabes initient l’analyse de fréquences (Al-Kindi 801-873).
En Français, les 4 lettres les plus fréquentes sont e, a, s, i. On peut aussi relever la fréquence d’apparition des digrammes, et la façon dont les lettres sont le plus susceptibles de se suivre…
17
Voici une analyse de fréquences sur le texte de l'Education sentimentale de Gustave Flaubert :
18
19
Pour tester la sécurité d'un chiffre, il est habituel de faire les hypothèses de Kerckhoff :
L'adversaire peut accéder à toute l'information chiffrée : il peut lire autant de messages chiffrés qu'il désire.
L'adversaire connait les détails de la méthode de cryptographie employée, à l'exception de la clé.
Trois attaques sont efficaces sur le code de Vigenère.
20
Exemple de cryptanalyse : méthode de Kasiski
On essaie de trouver la longueur de la clé en cherchant les répétitions dans le message chiffré. Ces répétitions existent puisque des mots courants comme « de », « les » ou « que » finiront par être traduits de la même façon.
Si des répétitions sont repérées avec des intervalles de longueurs 42, 63 et 105, on déduit que la longueur de la clé est un diviseur de pgcd(42, 63, 105) = 21.
On débute une analyse de fréquences pour chacune des longueurs de clés possibles (ici 1, 3, 7 et 21).
21
Les diplomates et les militaires considéraient Vigenère comme trop long à mettre en œuvre.
Ils préféraient utiliser des chiffres de sécurité intermédiaire, comme des tableaux de substitutions homophoniques…
22
23
24
25
26
27
Voici un tableau extrait d’un exercice du BAC S de Pondichéry 2012 qui satisfait certainement aux exigences du programme de spécialitéde terminale S après la très pénible et abracadabrante réforme Chatelde 2010 qui minimise l'importance des sciences dans la voie scientifique :
L’exercice portait sur un chiffrement de Hill,un cas particulier d’un chiffrement affine.
Impératifs stratégiques d’un chiffre militaire : Facile d'emploi. Permet d'envoyer de nombreux messages chaque jour. Assure la confidentialité pendant un laps de temps relativement court.
En 1914-18, les procédés manuels devaient obéir à la règle :« Un message doit pouvoir être chiffré ou déchiffré
manuellement en moins d'une heure ».
Procédés cryptographiques utilisés en 1914-18 : Substitution = principe du remplacement Transposition = principe du mélange (anagrammes)
L'intérêt du chiffrement par transpositions est de coder un caractère de façon différente dans chaque bloc, et ainsi de détruire les liens entre des caractères qui se suivent. La faiblesse de ce chiffrement est de rester vulnérable à une attaque par analyse de fréquences, car les fréquences d'apparition des caractères restent les mêmes.
28
29
1918 : Gilbert Vernam(ingénieur AT&T) et Joseph Mauborgne
(major de l‘US Army).
Vernam = Vigenèreavec clé à usage
unique de longueur égale au texte à
expédier.
Sécurité absolue ! Un livre de 100 pages est donné à
l'expéditeur et au destinataire. Chaque page contient une clé aléatoire de 100 lettres. L'expéditeur et le destinataire
utilisent une page par message à transmettre. Chaque message est chiffré
par la méthode de Vigenère.
Utilisé pour faire fonctionner le téléphone rouge entre Washington
et Moscou pendant la guerre froide !
Inventé par Charles Wheatstone en 1854,
mais ce fut Lord Playfair qui en fit une promotion effrénée…
Wheatstone proposa ce chiffrement au British Foreign Office qui le jugea extrêmement
complexe !
30
31
1
•On mémorise une phrase-clé :DANSEZ MAINTENANT JULES
2
•On supprime les lettres répétées :DANSEZMITUL
3•On complète dans l'ordre alphabétique (sans le J) :
DANSEZMITULBCFGHKOPQRVWXY
4•On dispose ces lettres dans une matrice 5×5 :
32
1•Substitution des digrammes. Si 2 lettres se suivent, intercaler un X.
2•M = DEMANDE RENFORTS IMMEDIATEMENT
3•DE-MA-ND-ER-EN-FO-RT-SI-MX-XM-ED-IA-TE-ME-NT
4•M’ = AD-BM-SA-YD-DS-PC-ZX-TN-VT-TV-DA-NM-SU-AU-IS
Invulnérable à une attaque basée sur les fréquences d'apparition des caractères, mais pas si l’on étudieles fréquences d'apparition des digrammes.
Utilisé par l'armée allemande dès le 5 mars 1918 pour l'offensive générale sur
Paris
Inventé par le colonel Fritz Nebel pour reprendre l'avantage après les échecs du chiffre allemand depuis 1914 (UBCHI,
ABC, KRU...).
1. SUBSTITUTION
Chaque caractère est remplacé par le digramme correspondant à la ligne et la colonne où il se trouve dans le tableau.
Exemple : U donne DG
2 étapes
33
34
2. TRANSPOSITION
mot-clé = BRUTE
Exemple
Décrypté en avril 1918 par le lieutenant français Georges Painvin
35
Arthur Scherbius (1918)
Machine à trois rotors
Armée allemande : seconde guerre mondiale
ENIGMA ressemblait à une machine à écrire. Appuyer sur une touche du clavier faisait allumer une lampe qui
éclairait la lettre à employer dans le message chiffré.
36
• 3 rotors pouvaient prendre 26 positions différentes et fonctionnaient comme des compteurs kilométriques de voiture.
• Le réflecteur permettait de déchiffrer les messages avec la même position des rotors.• Un tableau de connexions à fiches à la sortie du clavier permettait de relier 6×2=12
lettres entre elles L à l’aide de 6 câbles.
4×1018 clés Film U571
Le Data Encryption Standard est le plus connu des chiffres à blocs et à clé symétrique. Il a été retenu en 1977 par le U.S. National Bureau of Standards.
Dérivé du chiffrement Lucifer.
Successeurs : Triple DES, G-DES, DES-X, LOKI et ICE qui reprennent la même idée en augmentant la complexité.
37
Schéma de Feistel
16 rondes
Clé de 64 bits utilisée pour obtenir 16 clés partielles
Expansions et réductions
38
Claude Shannon définit deux principes généraux concernant les chiffrements à clé secrète
La confusion doit cacher les structures algébriques et statistiques.
La diffusion doit permettre à un bit d'information d'avoir une influence sur une grande partie du texte chiffré.
Le DES est construit pour qu’un seul caractère du texte influe sur de nombreux caractères du message chiffré.
39Un remplaçant : l’AES (Advanced Encryption Standard) adopté par le NIST en 2001.
40
Entrée bloc de 128 bits
K = Clé de 128 bits
A
Sortie bloc de 128 bits
Message de 128 bits
S
B
D
C B D
K
Transformation nonlinéaire d’octets
Décalagede lignes
Brouillage descolonnes
Addition de laclé de tour
Tour suivant(10 tours)
KT = Clé de tour
Le successeur du DES
41
Multiplication des clés - Pour sécuriser une information entre deux partenaires, ceux-ci doivent posséder la même clé. n abonnés auront besoin de n² clés distinctes pour communiquer entre eux.
Communication des clés - Comment se communiquer des clés de chiffrement sur internet ?
Signature – Comment certifier qu’un message crypté avec une clé donnée provient bien du titulaire de cette clé ?
42
Diffie et Hellman (1976)
Cryptosystème classique : l'émetteur E et le récepteur R connaissent tous les deux la clé qui permet de chiffrer et de déchiffrer.
Cryptosystème à clé révélée : le récepteur connaît la clé C de chiffrement et la clé D de déchiffrement. Il conserve D secrète mais donne C à tout le monde.
43
C = clé publiqueou clé révélée
D = clé secrète
44
L'utilisation d'une fonction trappe C résout les problèmes de la multiplication des clés et de leur communication.
45
46
47
Toute la mathématiquedu RSA est contenuedans ce résultat :
Rivest, Shamir, Adleman 1978
48
Pour chiffrer un message
Choisir 2 nombres premiers p, q.
n = pq.
m = (p-1)(q-1)
Utiliser l’algorithme d’Euclide
Choisir c premier avec m
Choisir d et k tels que cd = km+1.
Calculer les clés
49
Sécurité du système RSA : Facilité d'obtenir des nombres premiers très grands. Impossibilité de calculer la décomposition d'un grand nombre en
produit de facteurs premiers en un temps raisonnable.
Adleman 1978
Pomerance 1981
50
RSA-792 bits implémenté sur les CB dès l'an 2000. Il aurait fallu immédiatement passer au RSA-1024, mais cela posait trop de problème : augmentation du temps d'attente aux caisses de 10 sec pour la procédure d'authentification, renouvellement du parc des machines électroniques de vérification…
En 2014 : protection suffisante pour des clés de 1024 à 2048 bits.
RSA-2048 = nombre pq de l'ordre de 3×10616.
Les transactions par CB sont protégées par un chiffrement à clé publique (RSA) et un chiffrement à clé secrète (à l'origine un DES, puis Triple DES et AES).
Le protocole de paiement comporte 3 vérifications :
51
fff
52
Authentification
de la carte
CC = clé publique de la carteDC = clé secrète de la carteCR = clé publique de référenceDR = la clé secrète de référence
I = valeur d'authentification
Terminal
Centre de contrôle à distance
CB
Calcul dey = f(x,K)
Envoide x
Envoi de x
Débuter laprocédure
Calcul dey = f(x,K)
Envoide y
Envoi de y
54
Problème de la pile :• n boîtes de hauteurs respectives a1, a2, …, an.• Inconnues x1, x2, …, xn qui ne peuvent prendre que les valeurs 0 ou 1.• Pour une hauteur donnée h, quelles boîtes ont été utilisées ?
Il faut résoudre l’équation : a1 x1 + a2 x2 + …+ an xn = h
Ce problème est très difficile à résoudre : si l’on emploie la force brute, il faut réaliser 2n tests. Il s’agit donc d’un problème NP (non résoluble en temps polynomial).
Un cas particulier va nous sauver. Si l’on suppose que pour tout entier k les hauteurs des boîtes vérifient :
b1+ b2+ …+ bk-1 < bk
alors on sait résoudre ce problème en utilisant seulement n tests !
55
k n
h>=bk
xk 1 xk 0
h h-bk
k k-1
k=0
oui non
ouiFIN
Print xk
non
h
bn
56
Comment passer du problème facile à celui non résoluble en temps polynomial ?
En utilisant l'arithmétique des congruences, bien sûr !
57
Message
Chiffrer
Déchiffrer
Equation facile
58
Problème du logarithme discret = calcul de r connaissant gr
r gr
facile
difficile
Fonction trappe
59
Fonction trappe :
r donne gr
Construction de cryptosystèmes : exponentiation, El Gamal, courbe elliptique, courbe algébrique…
Signature des clés en se référant à une
autorité tierce (DSA)
Echange de clés sur un réseau (schéma de
Diffie-Hellman)
60
Echange de clés : schéma de Diffie-Hellman
Anatolechoisit g et h
Bernadettechoisit k
Clé secrètecommune = ghk
g, gh
gk
1976
61
62
Les maths, c’est pour le pl isir
