Cryptographie

Introduction

Depuis fort longtemps, les hommes ont tenté de rendre sécuritaires

leurs communications confidentielles. Différentes techniques ont été
utilisées.

Au début, il s’agissait seulement de cacher l’existence du message.

Cette technique s’appelle la stéganographie.

Puis, des techniques de plus en plus sophistiquées furent utilisées pour

rendre les messages compréhensibles seulement par leurs destinataires
légitimes.

Tout au cour de l’histoire, une difficile bataille eut lieu entre les
constructeurs de code (cryptographes) et ceux qui essayaient de les
briser (les cryptanalystes). Il n’est toujours pas clair, même aujourd’hui,
qui sera le vainqueur.
 Chiffrement de César
Cette technique simple de chiffrement effectuant un
décalage est appelé chiffrement de César.
Par exemple, avec un décalage de trois, mon nom
devient
ALAIN TAPP = DODLQCWDSS
(On décale aussi les espaces…)

Cette technique de chiffrement est-elle sécuritaire?

 Chiffrement de César
On intercepte le message
FAGEMYREMPURZV_EMZR_R FMNMDAZR
Essayons différents décalages…

1: E_FDLXQDLOTQYUZDLYQZQZELMLC_YQ
2: DZECKWPCKNSPXTYCKXPYPYDKLKBZXP
3… 4… 5… 6… 7… 8… 9… 10… 11… 12…
13: TOUS_LES_CHEMINS_MENENT_A_ROME

Clairement, le chiffrement de César n’est pas

sécuritaire.
 Substitution mono-alphabétique
Essayons autre chose.
_ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
R D O H X A M T C _ B K P E Z Q I W N J F L G V Y U S

TOUS_LES_CHEMINS_MENENT_A_ROME devient
FQLJRPAJRHCAE_ZJREAZAZFRDRNQEA

Le décodage devrait être plus difficile. Peut-on

essayer tous les décodages possibles?
La substitution mono-alphabétique apparaît déjà dans le
kàma-sùtra qui fut écrit au 5ième siècle mais qui est basé
sur des écrits datant du 4ième siècle av. J.-C.

Le premier usage révélé de chiffrement par substitution

dans un usage militaire est rapporté par Jules César dans La
guerre des Gaules. César utilisait fréquemment le
chiffrement et en particulier le décalage de trois caractères.

La substitution mono-alphabétique fut la technique de

chiffrement la plus utilisée durant le premier millénaire.
Nombreux savants de l’antiquité tenaient cette technique
pour inviolable.

Ce sont les Arabes qui réussirent à briser ce code et qui

inventèrent la cryptanalyse au 9ième siècle.
 Exemple
BQPSNRSJXJNJXLDPCLDLPQBE_QRKJXHNKPKSJPJIKSPUNBDKIQRBKP
QPBQPZITEJQDQBTSKPELNIUNPHNKPBKPCKSSQWKPSLXJPSNVVXSQCC
KDJPBLDWPXBPSNVVXJPGKPJKDXIPZLCEJKPGKSPSJQJXSJXHNKSPGP
LZZNIIKDZKPGKSPGXVVKIKDJKSPBKJJIKS

Comment déchiffrer ce message?

Chaque lettre est chiffrée de la même façon…

Certaines lettres sont utilisées plus souvent.
 Occurrence des lettres
En français Dans le cryptogramme

_ 19.3 L 4.7 H 0.8 P 14.3 D 4.6 W 1.0

E 13.9 O 4.1 G 0.8 K 12.8 L 4.1 U 1.0
A 6.7 D 2.9 B 0.6 S 9.2 V 3.1 T 1.0
S 6.3 P 2.5 X 0.4 J 9.2 Z 2.6 _ 0.5
I 6.1 C 2.4 Y 0.3 X 5.6 G 2.6 O 0.0
T 6.1 M 2.1 J 0.3 Q 5.6 C 2.6 M 0.0
N 5.6 V 1.3 Z 0.1 N 5.6 E 2.0 F 0.0
R 5.3 Q 1.3 K 0.0 B 5.1 R 1.5 A 0.0
U 5.2 F 0.9 W 0.0 I 4.6 H 1.5 Y 0.0
 Remplaçons P par _ et K par E

BQ_SNRSJXJNJXLD_CLDL_QBE_QREJXHNE_ESJ_JIES_UNBDEIQRBE_
Q_BQ_ZITEJQDQBTSE_ELNIUN_HNE_BE_CESSQWE_SLXJ_SNVVXSQCC
EDJ_BLDW_XB_SNVVXJ_GE_JEDXI_ZLCEJE_GES_SJQJXSJXHNES_G_
LZZNIIEDZE_GES_GXVVEIEDJES_BEJJIES

Remplaçons Q par A et B par L

LA_SNRSJXJNJXLD_CLDL_ALE_AREJXHNE_ESJ_JIES_UNLDEIARLE_
A_LA_ZITEJADALTSE_ELNIUN_HNE_LE_CESSAWE_SLXJ_SNVVXSACC
EDJ_LLDW_XL_SNVVXJ_GE_JEDXI_ZLCEJE_GES_SJAJXSJXHNES_G_
LZZNIIEDZE_GES_GXVVEIEDJES_LEJJIES
 Remplaçons S par S et G par D

LA_SNRSJXJNJXLD_CLDL_ALE_AREJXHNE_ESJ_JIES_UNLDEIARLE_
A_LA_ZITEJADALTSE_ELNIUN_HNE_LE_CESSAWE_SLXJ_SNVVXSACC
EDJ_LLDW_XL_SNVVXJ_DE_JEDXI_ZLCEJE_DES_SJAJXSJXHNES_D_
LZZNIIEDZE_DES_DXVVEIEDJES_LEJJIES

Remplaçons J par T et I par R

LA_SNRSTXTNTXLD_CLDL_ALE_ARETXHNE_EST_TRES_UNLDERARLE_
A_LA_ZRTETADALTSE_ELNRUN_HNE_LE_CESSAWE_SLXT_SNVVXSACC
EDT_LLDW_XL_SNVVXT_DE_TEDXR_ZLCETE_DES_STATXSTXHNES_D_
LZZNRREDZE_DES_DXVVEREDTES_LETTRES
 Remplaçons X par I, H par Q et N par U

LA_SURSTITUTILD_CLDL_ALE_ARETIQUE_EST_TRES_UULDERARLE_
A_LA_ZRTETADALTSE_ELURUU_QUE_LE_CESSAWE_SLIT_SUVVISACC
EDT_LLDW_IL_SUVVIT_DE_TEDIR_ZLCETE_DES_STATISTIQUES_D_
LZZURREDZE_DES_DIVVEREDTES_LETTRES

Remplaçons V par F et D par N

LA_SURSTITUTILN_CLNL_ALE_ARETIQUE_EST_TRES_UULNERARLE_
A_LA_ZRTETANALTSE_ELURUU_QUE_LE_CESSAWE_SLIT_SUFFISACC
ENT_LLNW_IL_SUFFIT_DE_TENIR_ZLCETE_DES_STATISTIQUES_D_
LZZURRENZE_DES_DIFFERENTES_LETTRES
 Remplaçons R par B et L par O

LA_SUBSTITUTION_CONO_ALE_ARETIQUE_EST_TRES_UULNERABLE_
A_LA_ZRTETANALTSE_EOURUU_QUE_LE_CESSAWE_SOIT_SUFFISACC
ENT_LONW_IL_SUFFIT_DE_TENIR_ZOCETE_DES_STATISTIQUES_D_
OZZURRENZE_DES_DIFFERENTES_LETTRES

Finalement

LA_SUBSTITUTION_MONO_ALPHABETIQUE_EST_TRES_VULNERABLE_A
_LA_CRYPTANALYSE_POURVU_QUE_LE_MESSAGE_SOIT_SUFFISAMMEN
T_LONG_IL_SUFFIT_DE_TENIR_COMPTE_DES_STATISTIQUES_D_OCC
URRENCE_DES_DIFFERENTES_LETTRES
 Substitution+
Au lieu de faire la substitution mono-alphabétique, on
peut rendre le code plus difficile à briser en faisant une
substitution de mots. Chaque mot est remplacé par un
nombre, d’où la nécessité d’un dictionnaire. On peut
utiliser des synonymes.

Cette technique n’est pas vraiment pratique. La

construction du dictionnaire est fastidieuse. Il faut se
déplacer avec le dictionnaire qui pourrait être intercepté. Il
est difficile de changer le code.
 Le chiffre indéchiffrable
Au 16ième siècle, on brisait les codes de façon routinière. La balle était
dans le camp des cryptographes. Vigenère inventa un code simple et
subtile. Il s'agit d’une amélioration du chiffre par décalage. On choisit un
mot de code par exemple ALAIN et on l’utilise pour chiffrer.

ALAIN=1,12,1,9,14
ALAINALAINALAINALAINALAINALAINALAINALAINA
LE_CODE_DE_VIGENERE_EST_IL_INDECHIFFRABLE
MQALBEQAMSAGJPSOQSNNFDUIWMLJWRFOIRTGCBKZF

Clairement, une attaque statistique simple ne fonctionnera pas. Si le mot

de code est suffisamment long (une phrase), essayer toutes les clefs est
aussi impossible.

Le chiffre de Vigenère est-il indéchiffrable?

 Masque jetable
Peut-on avoir un cryptosystème ayant une
confidentialité absolue et qui soit impossible à briser?

Qu’arrive-t-il si on utilise le chiffre de Vigenère avec

une clef aussi longue que le message?

Avec une clef aléatoire, on obtient le masque jetable.

Pour être inconditionnellement sécuritaire, la clef doit

être choisie aléatoirement et être utilisée une seule
fois.
 Sécurité du masque jetable

Si la clef est: 12,7,24,3,26,11,5,21,0,25

ALAIN_TAPP devient MSYLMKYVPN
Pour toute interprétation du message, il existe une clef la
justifiant.
Avec la clef: 11,4,11,2,25,22,20,22,16,14

BONJOUR___ devient MSYLMKYVPN

C’est Shannon en 1949 qui a démontré formellement que
le masque jetable est inconditionnellement sécuritaire.
L’inconvénient du masque jetable est la taille nécessaire
de la clef.
 Cryptographie Actuelle
• Symétrique
– La même clé est utilisée pour crypter et
décrypter
– Rapide
– Problème d’échange de clés
• Asymétrique
– Une clé pour crypter Kp et une autre clé pour
décrypter Ks
– Trop lent et consomme excessivement les
ressources de calcul
• Hybride
 Cryptage Hybride
• Génération d’une clé de session Kss
symétrique valable pour une session
d’échange
• Chiffrement asymétrique de la clé de session
par la clé publique Kp
• Échange sécurisé par chiffrement
asymétrique de la clé de session
• Déchiffrement de la clé Kss
• Échange sécurisé et rapide des données par
chiffrement symétrique en utilisant Kss
Cryptage symètrique
 DES

En 1973, le National Bureau of Standards des États-Unis

lance un appel d’offre pour un système de
cryptographie.

En 1975 DES, développé par IBM est adopté.

Cryptosystème le plus utilisé dans le monde.

Chiffrement de blocs de 64 bits.

Clef de 56 bits (72 057 594 037 927 936 clefs).

DES
 Briser DES
De nos jours, une machine comportant 1024
processeurs de 1 GHz, spécialisée pour le problème
peut explorer toutes les clefs en moins d’une journée.

DES n’est plus considéré sécuritaire mais est toujours

utilisé. Certains utilisent triple DES, qui paraît plus sûr.

Plusieurs autres cryptosystèmes à clef privée sont aussi

utilisés.

BLOWFISH IDEA SEAL RC4

 Cryptage asymétrique (à clé publique)
• Utilisation d’une paire de clés:
– Publique: Connue par tout le monde, utilisée généralement pour
crypter ou vérifier la signature des messages.
– Privée: Connue uniquement par le détenteur, utilisée pour décrypter
et signer des messages.
• Impossible de trouver la clé privée à partir de la clé publique.
• Exemples: RSA, Diffie-Hellman, El Gamal.
• Généralement dix fois plus lent que le cryptage symétrique.
• Utilisé généralement pour
– Cryptage / décryptage: assurer la confidentialité.
– Signature numérique: assurer l’authentification et la non répudiation.
– Distribution de clés: se mettre d’accord sur une clé de session.
• Clés à grande taille (ex: RSA: 1024-2048-…)
27
Cryptage asymétrique

28
RSA

29
 RSA
• Développé par Rivest, Shamir & Adleman à MIT en
1977, publié en 1978
• Le plus connu et le plus utilisé comme algorithme de
cryptage asymétrique.
• Breveté par RSA, et cette patente a expiré en 2000.
• Utilise des entiers très larges 1024+ bits
• Le fonctionnement du cryptosystème RSA est basé sur la
difficulté de factoriser de grands entiers.

30
 Rappel
• A mod B est le reste de la division entière de A par B
• La multiplication et le modulo
(A mod B) (C mod B) = A * C mod B
• L'exponentielle et le modulo
an mod m = (a mod m)n mod m
• Pierre Fermat :
Si on utilise un nombre premier comme module, alors quand on
élève un nombre à la puissance (nombre premier -1), on obtient 1
– Pour n'importe quel nombre m et pour p premier :
m( p – 1 ) mod p = 1
– Exemple : 7 10 mod 11 = 1 …pas besoin de calcul car 11 est
premier

31
 Rappel
• Leonhard Euler :
– Lorsqu'on utilise un module comme étant le produit de deux
nombres premiers on a :
Soit n = p * q, avec p et q premiers, et quelque soit m
m( p – 1 ) ( q – 1 ) mod n = 1
– Exemple : soit p = 11 et q = 5, n = 55 et (p – 1)(q – 1) = 10 * 4 =
40
38 40 mod 55 = 1
– Si on manipule le résultat d'Euler en multipliant par m l'équation :
m * m( p – 1 ) ( q – 1 ) mod n = m
m( p – 1 ) ( q – 1 ) + 1 mod n = m

32
 RSA: Algorithme
• Étapes
1. Sélectionner deux entiers premiers entre eux « p » et « q »
2. Calculer n = p x q
3. Calculer φ(n)=(p-1)(q-1)
4. Sélectionner « e » tel que: pgcd(φ(n),e)=1 ; 1<e<φ(n)
En général « e » est un entier de petite taille.
5. Calculer d=e-1 mod φ(n). En d’autre terme: d.e = 1 mod (φ(n))
6. Clé publique: Kpu={e,n}
7. Clé privée Kpr = {d,n}
• Pour crypter un message M < n, l’émetteur:
– Obtient une clé publique du récepteur et calcule « C= Me mod n »
• Pour décrypter un message crypté C le récepteur
– Utilise sa clé privée et calcule « M = Cd mod n »

33
 RSA: Algorithme
RSA: Exemple
Cryptage Décryptage
Texte
Texte clair Texte clair
crypté

p = 17, q = 11, n = p x q= 187

Φ(n) = 16 x 10 =160,
Choisir e = 7,
d.e =1 (mod Φ(n)) d = 23
34
 Preuve de RSA
• D(E(M)) = (Me mod n)d mod n
= Me.d mod n
• On a: e.d = 1 (mod φ(n) )
= z x φ(n) + 1
• Me.d = M z x φ(n) + 1
= (Mz)φ(n) x M
= 1 x M (mod n)
• Par hypothèse RSA crypte des blocks de données de taille
inférieure à n (décomposition en blocks)
D(E(M)) = M
35
 Exemple d'utilisation de
•
RSA
Chiffrement du message 'HELLO'.
• On prend le code ASCII de chaque caractère et on les met
bout à bout:
m = 7269767679
• Il faut découper le message en blocs qui comportent moins de
chiffres que n.
• n comporte 4 chiffres, on découpe notre message en blocs de
3 chiffres:
726 976 767 900 (on complète avec des zéros)
• On chiffre chacun de ces blocs :
– 726^71 mod 1073 = 436
– 976^71 mod 1073 = 822
– 767^71 mod 1073 = 825
– 900^71 mod 1073 = 552
• Le message chiffré est 436 822 825 552.
36
 Problèmes de RSA
• Complexité algorithmique de la méthode:
– recherche de nombres premiers de grande taille, et choix
de clés très longue
– Réalisation des opérations modulo n.
• Problème d’implémentation sur les équipements disposants
de faible puissance de calcul (ex: cartes bancaire, stations
mobiles, etc.)
• La méthode est officiellement sûre si des contraintes de
longueur des clés et d’usage sont respectées.
• Solution: Utilisation de RSA pour l’échange des clés
secrètes de session d'un algorithme symétrique à clés
privées.

37
 Comparaisons entre RSA et
• RSA DES
— clé de 40 bits
— chiffrement matériel : 300 Kbits/sec
— chiffrement logiciel : 21,6 Kbits/sec
— Inconvénient majeur : un pirate substitue sa propre clé publique à
celle du destinataire, il peut alors intercepter et décrypter le message
pour le recoder ensuite avec la vraie clé publique et le renvoyer sur le
réseau. «L’attaque» ne sera pas décelée.
— usage : on ne les emploiera que pour transmettre des données
courtes telles que les clés privées et les signatures électroniques.
• DES
— clé de 56 bits
— chiffrement matériel : 300 Mbits/sec
— chiffrement logiciel : 2,1 Mbits/sec
— Inconvénient majeur : attaque «brute force» rendue possible par la
puissance des machines.
— Usage : chiffrement rapide, adapté aux échanges de données de tous
les protocoles de communication sécurisés.
38
Échange sécurisé : la méthode Diffie - Hellman

39
Vulnérabilité
 Signature utilisant RSA
Le problème de la signature est l’inverse du problème
du chiffrement à clef publique. Seul le signataire doit
avoir la capacité de signer mais tous peuvent vérifier la
signature.

Avec RSA, on a que

D(E(m))=m mais aussi E(D(M))=m.

Pour signer un document, on applique l’algorithme de

déchiffrement au message et tout ceux qui connaissent
l’algorithme publique de chiffrement peuvent vérifier la
signature.

Pour signer un document, il faut connaître la clef

privée!
 Condensé (hash)

Fonction de résumé

Texte en clair Condensé (sceau)

 Condensé (fonction de hachage)
• Associe à toute suite de bits, un nombre de bits
prédéterminé via une fonction publique non
inversible; « presque injective »
• Caractéristiques :
– Facilité de calcul : étant donné une suite de bits, il est
facile de calculer le condensé
– Irréversible : étant donné le condensé, il est difficile
de calculer la suite de bits
– Sans collisions : étant donné un suite de bits donnée,
il est difficile de trouver une autre suite de bits
différente ayant le même condensé (donc la fonction
n’est pas injective mais s’en approche)
• Utilisé pour assurer l’intégrité de messages, de
fichiers, de données transmises, de
programmes
 Algorithmes de hachage courants
• MD4 (Message Digest 4)
– 128 bits (16 octets), très rapide, approprié pour des
usages de sécurité moyens
– RFC 1320
• MD5 (Message Digest 5)
– 128 bits (16 octets), rapide, plus sécurisé que MD4,
très utilisé
– RFC 1321
– Attention : collisions détectées en 2004
• SHA-1 (Secure Hash Algorithm, standard du
NIST)
– 160 bits (20 octets), plus lent que MD5
– FIPS 180-1
 Condensé
• Problème : comment assurer l’authenticité
d’un condensé ?
– Le stocker dans un endroit protégé
– Le signer
 Signature numérique
• Pour signer un document, on chiffre
seulement son hash (il n’est pas
nécessaire de chiffrer tout le document !),
avec sa clé privée
• Attention à la résistance aux collisions de
la fonction de condensé pour garantir avec
un niveau de confiance élevé que c’est
bien ce document qui a été signé
 Signatures
3
numériquesFonction
Condensé de résumé
chiffré

Clé privée de l'Utilisateur1

5

Clé publique de l'Utilisateur1

2

Condensé
4
Fonction
1
de résumé

Texte brut

6 Comparaison

Utilisateur1 (émetteur) Utilisateur2 (destinataire)

 Confiance en la clé publique
• Web of trust (PGP)
• PKI
– Notion de certificat numérique X509v3
– Autorités de certification racines