1

CryptographieCryptographie

A. Bonnecaze

Polytech/IML

Une introductionUne introduction

2

Alice, Bob et les autres...

Alice, étudiante 20 ans, aime la musique, Les sorties, le shopping

Bob, copain d'Alice, étudiant, 20 ansAime le foot, la musique

Iwan, amoureux d'Alice, étudiant, 20 ansAime la crypto, les réseaux, l'informatique

Alice et Bob n'étudient pas dans la même université

3

Alice et Bob désirent communiquer d'unemanière sûre

Ils vont à l'université pour en savoir plus

Professeur Rivest leur explique :Cryptologie = cryptographie + cryptanalyse

Cryptographie : Permet de communiquer au travers d’un canal peu sûr

Cryptanalyse : l'art de trouver des failles dans les techniques cryptographiques.

4

La cryptographie est un ensemble de mécanismes permettant d'assurer les services suivants

La confidentialité

L'intégrité des données

L'authentification

Le contrôle d'accès

La non répudiation

Alice et Bob décident d'utiliser lacryptographie pour communiquer

5

Alice et Bob veulent s'envoyer desmessages électroniques

Mais Iwan peut intercepter les messages• Alice et Bob décident de chiffrer leurs

messages pour plus de confidentialité• La crypto est une science ancienne mais

tous les algorithmes de chiffrementsérieux sont récents

La sécurité des S.I. 7

y = Ek(x) = x + k mod 26

Dk (y) = y - k mod 26

Chiffrement de César : k = 3

Exemple : BONJOUR est chiffré par ERQMRXU

Cryptanalyse : Recherche exhaustive (l’espace des clefs est petit)

Chiffrement par décalage : César

La sécurité des S.I. 8

Pour qu’un système cryptographique soit pratique,Les fonctions de chiffrement Ek et de déchiffrement Dk doivent être calculables efficacement

Cryptanalyse : Attention, si on chiffre du français, certaines lettres reviennent plus souvent que d’autres dans le texte :

…0.028C

0.127E0.015B

0.043D0.082A

probabilitélettreprobabilitélettre

La sécurité des S.I. 9

10

Comment casser un chiffrementpar substitution ?

Utiliser la fréquence des lettres

« a », « e », ...

Utiliser la fréquence des pairs de lettres(digrams)

« un », « de », « le »,...

11

La cryptographie moderne

• Les travaux– d'Auguste Kerckhoffs de 1883

– de Claude Shannon de 1949 sur la théorie del'information

Ont profondément influencé la conception de lacryptographie moderne

12

Principes d’Auguste Kerckhoffs1883

• Le système doit être matériellement, sinon mathématiquement,

indéchiffrable ;

• Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient

tomber entre les mains de l’ennemi ;

• La clé doit pouvoir être communiquée et retenue sans le secours denotes écrites, et être changée ou modifiée au gré des correspondants ;

• Il faut qu’il soit applicable à la correspondance télégraphique ;

• Il faut qu’il soit portatif, et que son maniement ou sonfonctionnement n’exige pas le concours de plusieurs personnes ;

• Enfin il est nécessaire, vu les circonstances qui en commandentl’application, que le système soit d’un usage facile, ne demandant nitension d’esprit, ni la connaissance d’une longue série de règles à

observer.

13

Terminologie

texte en clair

Chiffrement

décryptement

Déchiffrement Texte en clair

Canal sûr

Générateur de clefs

Texte chiffré oucryptogramme

Texte en clair et/ou clef

Cryptographie (cryptos logos : « mot caché » en grec)

14

Chiffrement symétrique

• Alice et Bob partagent la même clé (secrète)

• Personne d'autre ne doit connaître la clé

• Le schéma de chiffrement consiste en

• Une fonction de chiffrement publique E

• Une fonction de déchiffrement publique D

• Une clé secrète

• ...et des messages à chiffrer

15

Schéma de chiffrement

• Si est le message à chiffrer

• Si est la clé secrète

Alice chiffre en utilisant la fonction dechiffrement et la clé

• Elle envoie le chiffré à Bob

• Bob déchiffre en utilisant la fonction etla clé

c = E (k,m )

mk

mE

kD

c

m = D (k,c )

k

16

Chiffrement symétrique

• Si on note

– pour

– pour

• Alors on a

• Les fonctions et sont secrètes

E (k, . )

D (k, .)

E k

D k

Ek °Dk =IdE k D k

17

Communication par chiffrement symétrique

Génération declé

Chiffrement

Adversaire

Alice Bob

Texte clair(plaintext)

Déchiffrement

Message de destination

m

k

c

Gestion des clés?

E k (m )D k (c )

18

Types de chiffrement

• Chiffrement par blocs (DES, AES,...)– Blocks de 64 bits, 128 bits

• Chiffrement par flots (one time pad, RC4,...)

– Bit à bit

– Octets par octets

19

Chiffrement par blocs• La transformation s'applique sur des blocs (de textes

clairs) de taille fixe

• DES : adopté comme standard en 1977 (FIPS-46)

– Clé de 56 bits, blocs de 64 bits

• 3-DES (triple DES) standard 1985. Se compose de 3circuits de DES et 2 clés DES.

– On chiffre le clair avec k1, on déchiffre la sortieavec k2, on chiffre la nouvelle sortie avec k1

– On a donc 112 bits de clé, une entrée et unesortie de 64 bits

Chercher sur internet : NIST et FIPS-PUB

20

Chiffrement par blocs

• AES : Advanced Encryption Standard

• Par J. Daemen et V. Rijmen

• Standard américain qui remplace DES

• Standard FIPS-197 en 2001

• Blocs de 128 bits

• clés de 128, 196 ou 256 bits (suivantsécurité voulue)

21

Authentification

• je veux être sûre que le message estbien celui de Bob

• Puisque la clé n'est connue que de Bobet moi, si j'arrive à déchiffrer, je sais quele message provient de Bob

• Je peux donc authentifier le message

• Mais un tiers ne peut pas authentifier lemessage

22

Clé publique clé privée

• Lorsque je suis en déplacement, jeveux pouvoir chiffrer sans avoir de clésecrète sur moi

• Je veux aussi que tout le mondepuisse authentifier mes messages

Pour cela il faut utiliser le concept de clé publiquequi date de la fin des années 70

23

Clé publique/privée

• Chacun de vous dispose d'une paire declés (publique/privée)

• La clé privée d n'est connue que devous

• La clé publique e est publiée et doncconnue de tous

• Il doit être impossible de calculer d àpartir de e (problème de math...)

24

Clé publique/privée

• 1976 : Diffie et Hellman : concept decryptosystème à clé publique

• 1977 : RSA (Rivest Shamir Adleman)

• Repose sur des fonctions mathématiques

• Beaucoup plus lent que le chiffrementsymétrique : On ne peut pas chiffrer de longsmessages, seulement des clés (< 10 000 bits)

25

En pratique

• J'ai une paire de clés

• Bob a une paire de clés

• et les fonctions de chiffrement sont connuesde tous

• Je veux envoyer m à Bob

• J'envoie

• Bob utilise sa clé privée pour déchiffrer

• Pour chiffrer, je n'ai besoin que de la clé publiquede Bob!

(A s ,A p)( Bs ,B p )

A p ,B p

c=E ( Bp ,m )

m=D (B s ,c )

26

Communication par chiffrement asymétrique

Génération declé

Chiffrement

Adversairepassif

Alice Bob

Texte clair(plaintext)

Déchiffrement

Message de destination

m

c

Gestion des clés?

c=E ( Bp ,m ) m=D (B s ,c )

B pBs

27

La théorie

• Comment construire des paires defonctions réciproques l'une de l'autre?

• Existence de fonctions difficiles àinverser

• Exemple simple : RSA

• Avantage : pas de clés à échanger

• Désavantage : calculs lourds pourmessages courts

28

Pour chiffrer un fichier

• Je choisis une clé secrète s

• Je chiffre (algo symétrique) mon message aveccette clé

• Je chiffre (algo asymétrique) s avec la clépublique de Bob

• J'envoie à Bob les 2 chiffrés

• Bob retrouve s grâce à sa clé privée et déchiffre lemessage

• Pas besoin de partager une clé secrète !

29

Exemples d'algo de chiffrementasymétrique

• RSA (pb de factorisation)

• ElGamal (pb du log discret)

• PSEC (Provable Secure Elliptic Curve Encryption)

• Rabin (extraire une racine carrée)

• McEliece (pb de décodage)

• ...

30

Authentification

• Si je chiffre un message en utilisant ma cléprivée, tout le monde peut savoir que lemessage vient de moi (RSA à l'envers)

• Il s'agit d'une signature électronique

E(As ,m)

• Mais que faire si le message est long?

• Le chiffrement asymétrique prend trop detemps...

31

Signature

• Primitive fondamentale pour l'authentification,l'autorisation et la non répudiation

• Ensemble des messages M, des signatures S

• SA : M ---> S : transformation de signature

• SA est gardée secrète par A

• VA : M x S ---> {Vrai, Faux}

• VA est publique et permet à tout le monde de vérifier lasignature de A

• SA et VA produisent un schéma de signature

32

J'ai écrit un programme de 150 000 lignes en c++Je veux l'envoyer à BobJe veux être sûre que le fichier ne sera pasmodifié lors du transfert

• Il 'agit d'assurer l'intégrité du fichier

• Pour cela, utiliser des fonctions dehachage

• Une fonction de hachage produitune empreinte du fichier

33

Fonction de hachage H

• Elle prend en entrée n'importe quel fichier

• Donne en sortie un condensé de taille fixe

• SHA-1 donne des sorties de 160 bits

• SHA-256 donne 256 bits...

• H(m) = h

• H est une fonction à sens unique

• Connaissant h, il est calculatoirement impossiblede trouver m' tel que H(m') = h

34

Intégrité d'une donnée

• Je publie sur ma page web le haché d'unedonnée M

• Alice utilise cette donnée et veut s'assurer qu'ellen'a pas été modifiée par un tiers

• Alice hache la donnée et compare l'empreinteavec la valeur que j'ai publiée sur ma page

• Alice est alors sûre que la donnée ne contient pasde virus

• Je peux aussi signer le haché et envoyer lasignature à Alice

35

Je peux utiliser une fonction de hachage pour signer !!

• Je hache mon message H(m) = h

• Je signe h avec ma clé privée

• J'envoie le message concaténé avec lasignature

• Tout le monde peut vérifier, en utilisant ma clépublique que c'est bien moi qui ai signé.

• Comment ?

36

Exemples d'algo de Signature

• RSA

• DSS (FIPS PUB 186-3)

• ECDSA

• BLS

• …

Lire la page

• http://csrc.nist.gov/groups/ST/toolkit/digital_signatures.html

37

Non répudiation

• Attention : Si Bob reçoit un messagesigné d'Alice, celle-ci ne pourra pas direqu'elle ne l'a pas signé

• Si Iwan vole la clé privée d'Alice, il peutse faire passer pour Alice (Mascarade)

• Les clés privées sont des donnéessensibles

38

veulent partager un secretsans utiliser leurs cléspubliques

• Bob publie les valeurs g et n

• Bob choisit au hasard une valeur b et envoie à Alice

• Alice choisit au hasard une valeur a et envoie à Bob

• Alice et Bob partage le secret

peut-il obtenir le secret à partir des communications entre Alice et Bob?

et

gbmod n

ga mod ngabmod n

39

Quelques applications de lacrypto

Communications anonymes

Digital cash anonyme

- peut-on acheter anonymement ?

- comment empêcher de dépenser plusieursfois le même argent ?

Elections

Calculs multi-partie

Calculs privés sur un serveur externe

Zero knowledge (N=p.q)

40

Protocoles connus

Communications sûres :Web trafic : HTTPS

Wireless trafic : 802.11i WPA2, GSM, Bluetooth

Chiffrement de fichiers :EFS, TrueCrypt

Protection de contenu :DVD : CSS, Blue-ray : AACS

...

41

La crypto en 3 étapes

- Définir le modèle des menaces (threatmodel)

- Proposer une construction

- Prouver que casser cette constructionsous ce modèle de menaces résout unproblème difficile

42

Techniques de cryptanalyse

• Hypothèse : Oscar connaît le systèmecryptographique utilisé (principe de Kerkhoff)

• Texte chiffré connu : Oscar ne connaît que le messagechiffré

• Texte clair connu : Oscar dispose d’un texte clair et deson chiffré

• Texte clair choisi : Oscar choisi un texte clair et a lapossibilité d’obtenir son chiffrement

• Texte chiffré choisi : Oscar a temporairement accès àune machine déchiffrante. Il peut donc obtenir le texteclair du chiffré choisi.

Qui est l'adversaire ?

L'attaquant est

Le plus intelligent possible ; il peut fairetoutes les opérations qu'il veut.

Il dispose d'un temps « raisonnable » quidépend de l'application

Il ne doit pas pouvoir énumérer toutes lesclefs (attaque par force brute)

47

Résumé

• Chiffrement (assure la confidentialité)– De données : symétrique (bloc ou flot)

– De clés : asymétrique

• Fonction de hachage (à sens unique)– Intégrité des données

– Très utile dans les protocoles crypto

• Signature (assure l'authentification)– Utilise une fonction de hachage

– Crypto asymétrique

– Assure la non répudiation