42
Cryptographie symétrique 1 MGR850 Automne 2014 École de technologie supérieure (ÉTS) Département de génie électrique

MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

  • Upload
    dodat

  • View
    221

  • Download
    0

Embed Size (px)

Citation preview

Page 1: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Cryptographie symétrique

1

MGR850 – Automne 2014

École de technologie supérieure (ÉTS) Département de génie électrique

Page 2: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Plan

2

• Introduction

• Histoire

• Concepts de base

• Cryptographie classique

• Cryptographie moderne

• Conclusion

Page 3: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• La cryptologie est la science des messages secrets et des codes chiffrés utilisés traditionnellement par les militaires et les gouvernements.

• Depuis l’avènement des transactions électroniques, la cryptologie c’est démocratisée. – Banques

– Internet

– …

Introduction

3

Cryptologie

Page 4: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• Développer des procédés permettant à deux personnes de communiquer tout en protégeant leurs messages.

– Préserver la confidentialité des messages.

– Vérifier l’intégrité des messages.

Introduction

4

Objectif de la cryptographie

Page 5: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Histoire

5

Environ 1900

avant J.-C.

Un égyptien a employé des hiéroglyphes non conformes à la langue.

487 avant J.-

C. (La cité

de Sparte)

Les grecs emploient un dispositif appelé la "scytale" - un bâton autour

duquel une bande longue et mince de cuir était enveloppée et sur

laquelle on écrivait le message. Le cuir était ensuite porté comme

une ceinture par le messager. Le destinataire avait un bâton identique

permettant d'enrouler le cuir afin de déchiffrer le message.

Environ 150

avant J.-C.

L'historien grec Polybe (env. 200-125 av. J.-C.) invente le carré de

Polybe, dont s'inspireront plus tard bien des cryptosystèmes.

Source: http://www.apprendre-en-ligne.net/crypto/histoire/index.html

Page 6: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Histoire

6

60-50

avant J.-C.

Jules César employait une substitution simple avec l'alphabet

normal (il s'agissait simplement de décaler les lettres de

l'alphabet d'une quantité fixe) dans les communications du

gouvernement. César écrivait aussi parfois en remplaçant les

lettres latines par les lettres grecques.

9e siècle Abu Yusuf Ya'qub ibn Is-haq ibn as-Sabbah Oòmran ibn

Ismaïl al-Kindi rédige le plus ancien texte connu décrivant la

technique de cryptanalyse appelée analyse des fréquences.

Source: http://www.apprendre-en-ligne.net/crypto/histoire/index.html

• Tatouage sur la tête rasée d'un esclave. Secret caché par les cheveux repoussés!

Page 7: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• Texte en clair (Plaintext): – Données à protéger: message, information, plan de

bataille, décision, programme, …

– Différents langages: langues naturelles, langage de programmation, code binaire, …

– immédiatement intelligible

• Chiffrement (Encryption): – Transformation: Processus, opération, ou algorithme

générant un cryptogramme à partir du texte en clair

– Complexe et basé sur une clé secrète

Concepts de base

7

Texte en clair Cryptogramme Texte en clair Chiffrement Déchiffrement

Page 8: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• Cryptogramme (Ciphertext): – Inintelligible pour une personne ne possédant pas la

clé de déchiffrement

– Assure la confidentialité des données

• Déchiffrement (Decryption): – Transformation: Processus, opération, ou algorithme

générant un texte en clair à partir du cryptogramme

– Complexe et basé sur une clé secrète

Concepts de base

8

Texte en clair Cryptogramme Texte en clair Chiffrement Déchiffrement

Page 9: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• Cryptographie: – Principes, méthodes et outils permettant le

chiffrement et le déchiffrement des données

– Objectifs : assurer la confidentialité et l’intégrité

• Cryptanalyse: – Principes, méthodes et outils permettant de

découvrir le maximum d’informations secrètes appartenant au domaine de la cryptographie

– Clés, textes en clair, langues utilisées, algorithmes de chiffrement, …

Concepts de base

9

Cryptologie

Page 10: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Cryptanalyse

• Mode passif: – Écoute des communications (messages échangés).

Bases de données cumulées avec le temps

– Traitement « hors ligne »: artillerie lourde d’algorithmes + vaste armée de pirates

• Mode actif: – Participation aux échanges: suppression, insertion,

usurpation, … protocoles cryptographiques.

Concepts de base

10

Page 11: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Cryptographie à clé secrète

• Chiffrement et déchiffrement de données en se basant sur une clé secrète partagée entre les parties impliquées dans l’échange de données

• Cryptanalyse: • Sans connaissance préalable de la clé, le

cryptogramme est « indéchiffrable » • MAIS si le nombre de clés possibles est modeste!

… • L’algorithme de chiffrement doit être « robuste »

Cryptographie symétrique

11

Page 12: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• Transposition – Construire des anagrammes en changeant l'ordre

des lettres.

– Connue depuis l'Antiquité (scytale des Spartes)

– L'ordonnancement des lettres doit suivre un

système rigoureux sur lequel d'expéditeur et

l'envoyeur se sont préalablement entendus

– Exemple :

• Permutation avec clé (2, 4, 1, 3)

• Cryptanalyse possible:

– Analyse des fréquences de lettres => langue utilisée

– Test des permutations possibles

12

Crypto classique

TEST ETTS

Page 13: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• Algorithme de Jules César (1/3) – Consiste simplement à décaler les lettres de l'alphabet

de quelques crans vers la droite ou la gauche

– Exemple: Clé= 3 (D) => décalage de 3 positions

– Code(A)=0, Code(B) =1, …, Code(Z)=25

– Voir la démo sur Cryptool

13

Crypto classique

Page 14: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• Algorithme de Jules César (2/3)

Crypto classique

14

This is a secret

information!

Uijt jt b tfdsfu

jogpsnbujpo!

Vjku ku c ugetgv

kphqtocvkqp! Wklv lv d vhfuhw

lqirupdwlrq!

Texte en clair Cryptogramme

Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010

Clé= 1 (B) => décalage de 1 positions Clé= 2 (C) => décalage de 2 positions Clé= 3 (D) => décalage de 3 positions

y = (x + n) modulo 26

n=3

Page 15: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• Algorithme de Jules César (3/3) – Cryptanalyse

• Nombre de clés possibles: 25

• Très facile de retrouver le texte en clair à partir du cryptogramme!

– Exemple d’un cryptogramme: • Quel est le texte en clair correspondant au

cryptogramme?

• Quelle est la clé utilisée pour le chiffrement?

GERF SNPVYR QR ERGEBHIRE YR GRKGR RA

PYNVE N CNEGVE QH PELCGBTENZZR

Crypto classique

15

Page 16: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Substitution monoalphabétique (1/4)

• Clé: permutation des 26 lettres de l’alphabet

• Exemple d’une clé:

• Nombre de clés possibles: 26! -1 =

403291461126605635583999999

• Et si l’alphabet de la clé n’est pas limité aux 26 lettres?

• Le nombre de clés possibles? Cryptanalyse?

Crypto classique

16

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

l f g i w y d x e b s n t c q u h z v r m k j a o p

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

t ? g ! w y d & e [ s ) l c / u h ] $ z m * < = o >

Page 17: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Substitution monoalphabétique (2/4)

• Cryptanalyse

– L’algorithme de chiffrement associe à toutes les

occurrences d’une lettre donnée, `A’ par exemple, la

même lettre, `M’ par exemple:

• "A PARTIR DE LA" => "M *M***** ** *M"

– L’analyse des fréquences des lettres dans le

cryptogramme peut révéler le texte en clair!

– Les statistiques sont toujours utiles

Crypto classique

17

Page 18: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Substitution monoalphabétique (3/4)

• Cryptanalyse: Langue Française

Fréquences des lettres

Crypto classique

18

E 17.76 O 5.34 B 0.80

S 8.23 D 3.60 H 0.64

A 7.68 C 3.32 X 0.54

N 7.61 P 3.24 Y 0.21

T 7.30 M 2.72 J 0.19

I 7.23 Q 1.34 Z 0.07

R 6.81 V 1.27 K 0.00

U 6.05 G 1.10 W 0.00

L 5.89 F 1.06

Page 19: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Substitution monoalphabétique (4/4)

• Cryptanalyse: Langue Française

Fréquences des bigrammes sur 10 000 bigrammes

Crypto classique

19

ES 305 TE 163 OU 118 EC 100 EU 89 EP 82

LE 246 SE 155 AI 117 TI 98 UR 88 ND 80

EN 242 ET 143 EM 113 CE 98 CO 87 NS 79

DE 215 EL 141 IT 112 ED 96 AR 86 PA 78

RE 209 QU 134 ME 104 IE 94 TR 86 US 76

NT 197 AN 30 IS 103 RA 92 UE 85 SA 75

ON 164 NE 124 LA 101 IN 90 TA 85 SS 73

ER 163

SS 73 M

M 20 AA 3

EE 66 RR 17 UU 3

LL 66 PP 16 II 2

TT 29 FF 10 GG 1

NN 24 CC 8

Page 22: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Substitution polyalphabétique-Vigenère (3/4)

• Cryptanalyse

– L’algorithme de chiffrement N’associe PAS à toutes les

occurrences d’une lettre donnée, `A’ par exemple, la

même lettre:

• "A PARTIR DE LA" => "M *K***** ** *S"

– L’analyse des fréquences des lettres dans le

cryptogramme n’est plus utile?

– Cependant, les statistiques sont toujours utiles

• Comment?

Crypto classique

22

Page 23: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Substitution polyalphabétique-Vigenère (4/4)

• Cryptanalyse

– Pour une clé de taille 3:

• les lettres du texte en clair qui sont aux positions: 0, 3, 6, .. Sont

chiffrées de la même façon: même décalage.

• les lettres du texte en clair qui sont aux positions: 1, 4, 7, .. Sont

chiffrées de la même façon: même décalage.

• les lettres du texte en clair qui sont aux positions: 2, 5, 8, .. Sont

chiffrées de la même façon: même décalage.

– Les statistiques peuvent être utilisées sur les lettres qui

sont chiffrées de la même façon

Crypto classique

23

Page 24: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Algorithme de Nihilist (1/4) • Surchiffrement

• 1ère clé secrète: EXAMPLE

• Matrice de chiffrement: 5 X 5

• Construction de la matrice

Crypto classique

24

Page 25: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Algorithme de Nihilist (2/4) • Construction de la matrice (suite)

Crypto classique

25

Page 26: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Algorithme de Nihilist (3/4) • Construction de la matrice (suite)

• Cas particulier: I & J ont le même code!

Crypto classique

26

Page 28: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• Faiblesses des systèmes classiques:

– Taille de la clé

– Réutilisation de la clé

• Principes de la solution (Masque Jetable ou One-

time pad):

– Les caractères composant la clé doivent être choisis de

façon totalement aléatoire.

– Une nouvelle clé pour chaque message à chiffrer

– La taille de la clé est égale à la taille du message

• MAIS comment échanger les clés?

• Confidentialité des messages vs confidentialité des clés

Crypto classique

28

KMC

Page 29: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Principes de Kerckhoffs 1883

• Séparation algorithme / clé: – Chiffrement de César:

• Algorithme: "Décalage d’une lettre de X positions"

• Clé: "La valeur de X"

• Principe de Kerckhoff: "Le secret réside dans la clé et non pas dans l'algorithme"

Crypto moderne

29

Page 30: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Principe de Shannon / Vernam (1945)

• Masque jetable:

– Théoriquement-complètement incassable,

– Très peu pratique : téléphone rouge

• Clés transportées par valise diplomatique

• Nouvelle clé pour chaque nouvelle communication

Crypto moderne

31

Page 31: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Principes de Shannon (1945)

• Confusion et diffusion

– Relation aussi complexe que possible entre M, C, K

• M : message

• C : cryptogramme

• K : clé

• La confusion cache les relations entre le texte clair et le texte

chiffré pour éviter les attaques par analyse statistique.

• un changement d’un seul bit dans le texte clair doit affecter un

grand nombre de bits (tous) du texte chiffré.

• Effet avalanche: petite modification, grand impact

• La diffusion disperse la redondance du texte clair dans le texte

chiffré, par exemple deux lettres doublées ne doivent pas

rester côte à côte après cryptage.

Crypto moderne

32

Page 32: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• En 1976, l’agence de normalisation américaine

développait un algorithme de chiffrement qui a été

grandement utilisé depuis:

– DES (Data Encryption Standard)

• En 2002, l’agence de normalisation américaine

récidivait avec un nouvel algorithme:

– AES (Advanced Encryption Standard)

Crypto moderne

35

Page 33: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• DES - Data Encryption Standard – Crypto à clés secrètes

– En 1979, le premier ATMs (automatic teller

machines) a exploité le chiffrement DES pour les

PINs.

– Basé sur un schéma de Feistel

– Utilisée pour

• Chiffrement

• Authentification

– Règle Importante:

• Une clé pour chaque fonctionnalité.

– Il est à la base d’autres crypto systèmes plus récents

comme IDEA, FEAL, CAST, RC5, BLOW-FISH.

Crypto moderne

36

Page 34: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• Chiffrement DES - Algorithme

Crypto moderne

37

Cryptogramme - 64 bits

Texte - 64 bits

Algorithme DES Clé - 56 bits

Page 35: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Chiffrement par bloc • ECB : Electronic Code Book

– Chiffrement

– Déchiffrement

Crypto moderne

38

Page 36: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Chiffrement par bloc • CBC : Cipher Block Chaining

– Chiffrement

– Déchiffrement

Crypto moderne

39

Page 37: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• Authentification DES - Algorithme

Crypto moderne

40

Code d’authentification – 32 bits

Texte – sans restriction

Algorithme DES Clé - 56 bits

Chamseddine Talhi, ÉTS

Page 38: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• DES vulnérable aux attaques par force brute.

• Triple DES !!!

– Pour chaque bloc de 64 bits de message, trois

itérations:

• Clé de 112 bits (K1K2) :

– Chiffrer avec K1,

– Déchiffrer avec K2,

– Chiffrer avec K1

• Clé de 168 bits (K1K2K3) :

– Chiffrer avec K1,

– Déchiffrer avec K2,

– Chiffrer avec K3

Crypto moderne

41

Chamseddine Talhi, ÉTS

Page 39: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Crypto moderne

42

Source: http://fr.wikipedia.org/wiki/Triple_DES

Triple DES

Chiffrer Déchiffrer Chiffrer

64 bits

64 bits

Page 40: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

• AES : Advanced Encryption Standard • Crypto à clés secrètes

• Candidat retenu en 2002: Rijndael:

• Trois versions: – Chiffrement de blocs de 128 bits avec une clé de 128 bits

• 10 itérations

– Chiffrement de blocs de 192 bits avec une clé de 192 bits

• 12 itérations

– Chiffrement de blocs de 256 bits avec une clé de 256 bits

• 14 itérations

• Voir démo sur CrypTool

Crypto moderne

43

Page 41: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Problème des clés secrètes

44

• 2 personnes => 1 clé

• n personnes => n * (n-1)/2 clés

• 100 personnes => 4,950 clés

• 1,000personnes => 499,500 clés

• Pour chaque 10 personnes en

plus on a besoin de 100 clés en

plus!

Adapté de: http://www.cryptool-online.org/

Page 42: MGR850 Automne 2014 - cours.etsmtl.ca · Adapté de: Introductory example: Caesar cipher. CrypTool Team, novembre 2010 ... Algorithme de Nihilist (4/4) • 2ème clé secrète: NEXT

Conclusion

45

• La cryptographie est essentielle pour assurer la

confidentialité et l’intégrité des données

• Complexité n’est pas toujours synonyme de

robustesse

• La confidentialité des clés est le maillon faible de

la cryptographie symétrique

• L’algorithme adopté est déjà entre les mains de

l’ennemi.

• Problèmes:

– Nombre de clé: Une nouvelle clé pour chaque paire de

personnes

– Confidentialité des clés: Échange des clés