Fondements de la Cryptographie

• Cryptage et décryptage: Des données susceptibles d’être lues

et comprises sont appelées texte clair (plaintext), la méthode
de masquage du texte claire en texte chiffré (Ciphertext) ou
codé de sorte qu’il soit illisible et incompréhensible est dite
cryptage ou chiffrement. Le processus inverse d’obtention du
texte original à partir du texte chiffré est désigné par
décryptage ou déchiffrement.
• Cryptographie: Technique à base des mathématiques destinée
à crypter (coder) ou décrypter des données. Elle permet de
stocker ou transmettre des informations sensibles à travers un
réseau non sécurisé de sorte qu’elles ne soient lisibles que
pour l’unique récepteur destinataire.
1
 Cryptographie
• Cryptanalyse: Technique d’analyse et de décodage
(brisement) des communications sûres.
• Cryptanalyste: attaquants ou intrus (intruder)
• Cryptologie: Science du secret = Cryptographie +
cryptanalyse
• Cryptographie forte et faible
La puissance d’une cryptographie est mesurée en
termes de temps et ressources nécessaires pour
retrouver (recouvrer) le texte clair. Le texte chiffré via
une cryptographie forte est très difficile à déchiffrer
sans les outils de décodage appropriés.
2
 Emploi de la cryptographie
 Un algorithme cryptographique est une
fonction mathématique permettant le
cryptage et décryptage de l’information à
l’aide d’une clé.
 La sécurité des données cryptées dépend
entièrement de la puissance de l’algorithme
de cryptage et du secret de la clé.
Crypto système = algorithme cryptographique
+ ensemble des clés possibles + ensemble de
ses protocoles. Exemple: PGP (Pretty Good Privacy).
3
 Principe de Kerckhoffs
En 1883, Auguste Kerckhoffs (1835-1903) posa les
principes de la cryptographie moderne, en particulier
celui stipulant que la sécurité d’un crypto-système
ne doit pas reposer sur le secret de l’algorithme de
codage mais qu’elle doit uniquement reposer sur la
clef secrète du crypto-système qui est un paramètre
facile à changer, de taille réduite (actuellement de 64
à 2048 bits suivant le type de code et la sécurité
demandée) et donc assez facile à transmettre
secrètement.
Ce principe a été très exactement respecté pour le choix
du dernier standard de chiffrement, l’algorithme
symétrique AES, par le NIST. Ce dernier a été choisi à la
suite d’un appel d’offre international et tous les détails
de conception sont publics. Ce principe n’est que la
transposition des remarques de bon sens suivantes: 4
 Principe de Kerckhoffs (suite)
• Un crypto-système sera d’autant plus résistant et sûr qu’il
aurait été conçu, choisi et implémenté avec la plus
grande transparence et soumis ainsi à l’analyse de
l’ensemble de la communauté cryptographique.
• Si un algorithme est supposé être secret, il finira un jour
par perdre cette confidentialité et on découvrira ses
faiblesses (même ignorées de ses concepteurs). Ainsi,
c’est tout le crypto-système qui est à changer et pas
seulement la clé.
Les systèmes conçus dans le secret révèlent souvent
rapidement des défauts de sécurité qui n’avaient pas été
envisagés par les concepteurs.
5
 Qualités d’un Crypto-système
 Confidentialité: seules les entités autorisées
ont accès au contenu du message.
 Intégrité: le contenu d’un message ne peut
être falsifié sans qu’on s’en aperçoive.
 Authentification:
˗ L’ émetteur est sûr de l’identité du destinataire qui,
seul pourra prendre connaissance du message, car il
possède légalement la clef de déchiffrement.
˗ Le receveur est également sûr de l’identité de son
émetteur.

6
 Qualités d’un Cryptosystème (Suite)
 Non-répudiation:
˗ Non-répudiation d’origine: l’émetteur ne peut nier
avoir écrit le message et si tel est le cas, il peut
effectivement le prouver.
˗ Non-répudiation de réception: le receveur ne peut
nier avoir reçu le message et il peut prouver qu’il ne
l’a pas reçu si c’est effectivement le cas.
˗ Non-répudiation de transmission: l’émetteur du
message ne peut nier avoir envoyé le message et il
peut prouver qu’il ne l’a pas fait si c’est réellement le
cas.
7
Bases de la Cryptographie

8
Base de la Cryptographie

9
 Cryptographie à Clé symétrique
• Dans la cryptographie conventionnelle ou cryptographie à clé
privée ou encore cryptographie à clé symétrique (CCS), une
clé unique est utilisée lors du processus de cryptage ou
décryptage: L’émetteur et le récepteur des données
disposent d’une même clé. Exemple de crypto système
conventionnel : Data Encryption Standard (DES).
• Toute modification de message crypté en transit sera
détectée par l’incapacité du décryptage à restaurer le
message originel au niveau du récepteur. La CCS n’assure pas
l’authentification: Tout émetteur possédant la clé est capable
de créer, de crypter et transmettre un message valide.

10
 Cryptographie à Clé Symétrique

Texte en clair cryptage Texte crypté Décryptage Texte en clair

Chiffrement par substitution

La plus ancienne forme de chiffrement

11
 Cryptographie à Clé Symétrique (suite)

• Traces dans l’Egypte antique, l’exemple récent connu, le

chiffre de Jules César dont les variantes Rot13 ou Rot47
• Substituer une information par une autre. Effectuer un
décalage dans l’alphabet. algorithme = décalage dans
l’alphabet, clé = nombre de décalages. Pour une clé de 3:
ABCDEFGHI J K LMNOPQR ST UVWXYZ
DEFGHI J KLMNOPQR ST UVWXY Z ABC
avec D=A, E=B, F=C … SECURITE  VHFXULWH
• Rotate by 13 places = variante du chiffrement césarien
Avantage: appliquer 2 fois le chiffrement donne le texte
en clair (considérer alphabet circulaire AZA)

12
 Cryptographie à Clé Symétrique (suite)
• Si on représente chaque lettre de l’alphabet par un entier
correspondant à sa position dans l’alphabet, la formule
de remplacement de chaque caractère ‘P’ du texte clair
avec un caractère ‘C’ du texte chiffré, on peut obtenir
l’expression: C = E( 3, p ) = (p + 3) mod 26.
La formule générale pour tout décalage peut être:
C = E( k, p ) = (p + k) mod 26
La formule de déchiffrement serait:
p = D( k, C ) = (C - k) mod 26
Dans ces formules, ’k’ serait la clé secrète (Secret key).
Les symboles ’E’ and ’D’ represent le chiffrement
(Encryption) et le déchiffrement (Decryption).
13
 Cryptographie à clé Symétrique (suite)
• Inconvénients: chiffrement favorable aux lettres seules
d’où ROT47 se basant sur le code ascii.
• Espace des clés très limité: 26 décalages possibles 
déchiffrement très accessible (même manuellement).
Approche de recherche exhaustive des clés (brute force
approach) dans cet espace de clés on peut recouvrer la
clé en un temps insignifiant. Quel serait alors l’espace
des clés adéquat ? Un espace de taille 256 peut être
épuisé en 18h à l’aide d’une machine essayant 240 clés
par seconde. Pour améliorer la sécurité, il est possible
de ne pas se limiter à un simple décalage de n.

14
 Cryptographie à Clé Symétrique (suite)
• Toute permutation des 26 lettres peut largement suffire car
l’espace des clés devient égal à 26! > 4*1026 ≈ 288 et avec
une machine testant 240 clés par seconde, l’épuisement de
l’espace demanderait ≈ 4450 millénaires. Peut-on alors
conclure qu’un chiffrement par substitution est sécurisant?
La réponse est non car la cryptanalyse d’une simple
substitution est en mesure de décrypter un message crypté.
Elle se base sur la fréquence d’occurrence des lettres dans le
texte chiffré comparée à la fréquence d’apparition des lettres
dans une langue donnée (voir paragraphe cryptanalyse ci-
après). De proche en proche cette corrélation convergera vers
la détermination du texte en clair.
15
 Cryptographie à Clé Symétrique (suite)
• Malgré un espace de clés suffisamment large, la cryptanalyse
rend le chiffrement par substitution non sécurisé.
• Chiffrement sûr ?
Idéalement, c’est de prouver mathématiquement qu’un
système est résistant à une attaque. Compte tenu de l’absence
(actuelle) de preuve de la puissance d’un chiffrement, on
exigerait seulement qu’une attaque bien connue serait
impraticable, ce qui semblerait être la propriété la plus
souhaitable. A défaut, un crypto système est sûr si l’attaque la
plus connue nécessiterait autant d’efforts qu’une attaque
exhaustive de clés (essai systématique de toutes les clés) 
sécurité calculatoire qui dépend du temps et des ressources
disponibles.

16
 Cryptographie à Clé Symétrique
• Les performances des moyens de calcul en croissante
évolution soumettent un système de chiffrement à une
adversité toujours plus forte (Le message chiffré reste
invariable). Exemple de Data Encryption Standard devenu
obsolète à cause de l’espace des clés utilisables: 2 56 mais
de son temps 1977, cet espace était sûr. Advanced
Encryption Standard: dernier standard choisi par les USA
(12-2001) utilise des clés de taille au moins 128 bits, soit
2128 ≈ 3.4 1038 clés possibles. Si 1012 clés sont susceptibles
d’être testées par seconde, soit 3.210 19 clés par an, soit ≈
1019 années  algorithme raisonnablement sûr.

17
 Cryptographie à Clé Symétrique
• Hypothèse forte de l’algorithme: seule possibilité de le
casser c’est de mener une attaque exhaustive. Sans tenir
compte de nombreuses failles d’un algorithme ou encore
plus nombreuses sont ses mauvaises utilisations.
• Sécurité calculatoire  sécurité absolue ? Un seul cas
possible prouvé parfaitement sûr (C. Shannon) ajouter
au message en clair une clé de même longueur, ce qui est
pratiquement inutilisable pour textes longs.
• Inconvénient: chiffrer un message de n bits  échanger
au préalable avec le destinataire, par voie sûre, une clé
de n bits parfaitement aléatoire et utilisée une seule fois.

18
 Chiffrement par Fonctions Affines
Le chiffrement par décalage est un cas particulier du chiffrement
par substitution qui considère 26 permutations possibles parmi
les 26! possibles. Un autre cas spécial du chiffrement par
substitution est le chiffrement affine.
Dans le chiffrement affine, les fonctions de codage sont des
fonctions affines de la forme: e(x)= ax + b mod 26, avec a, b є Z26.
Lorsque a=1, on obtient le chiffrement par décalage. Pour que le
décodage soit possible, il est nécessaire que la fonction affine soit
injective c’est-à-dire : y є Z26 la congruence ax + b ≡ y (mod 26)
doit avoir une solution unique pour x. Cette congruence est
équivalente à : ax ≡ y – b (mod 26). Cette congruence a une
solution unique pour tout y si et seulement si PGCD(a,26)=1

19
Chiffrement par Fonctions Affines (suite)

- En supposant que pgcd(a, 26) = d >1, alors la congruence ax ≡

0 (mod 26) a (au moins) deux solutions distinctes dans Z26 : x =
0 et x = 26/d. Dans ce cas, e(x) = ax + b mod 26 n’est pas une
fonction injective et donc invalide pour un chiffrement.
- Par exemple, puisque pgcd(4, 26) = 2, alors 4x + 7 ne convient
pas comme fonction de codage: x et x + 13 coderont la même
valeur, for any pour tout x є Z26 .
˗ Puisque 26=2*13, les valeurs de a є Z26 tel que pgcd (a,26)=1
sont: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 et 25. Comme b є Z26
alors le nombre total de clés du chiffrement affine est: 12*26=
312, très peu pour être sécurisant.

20
Chiffrement par Fonctions Affines (suite)
 Théorème: La congruence ax ≡ b (mod m) a une solution unique
x є Zm pour tout b є Zm si et seulement si pgcd(a, m) = 1.
 Définition: Supposons a ≥ 1 and m ≥ 2 sont entiers ; si pgcd(a, m)
= 1, alors a et m sont premiers entre eux. Le nombre d’entiers
dans Zm premiers avec m est noté par Ф (m) (génératrice
d’Euler).
• Tout nombre intier m > 1 peut être factorisé en un produit de
puissance de nombres premiers de manière unique. Exemple,
60 = 22 ×3 × 5 et 98 = 2 × 72.
 Théorème:

21
Chiffrement par Fonctions Affines (suite)

Supposons où p sont des nombres premiers distincts et ei >

0, 1 ≤ i ≤ n

alors

Le
e(x)nombre
= ax + [Link] choix pour b est m, celui de a est Ф (m) et la fonction de cryptage est

 Déchiffrement
Le déchiffrement implique solutionner y ≡ ax + b (mod 26), pour cela, on a
besoin de de l’inverse multiplicatif de a є Zm noté a-1 є Zm tel que aa-1 ≡ a-1
a≡1 (mod m)
Les inverses multiplificatifs des nombres premiers dans Z26 : 1-1 = 1, 3-1 = 9, 5-1 = 21,
7-1 = 15, 11-1 = 19, 17-1 = 23 et 25-1 = 25 Par exemple, 7 × 15 = 105 ≡ 1 mod 26, d’ou 7-
1
=15.
Le déchiffrement implique solutionner l’équation y ≡ ax + b (mod 26).
22
 Déchiffrement selon les Fonctions Affines
La congruence y ≡ ax + b (mod 26). Ce qui est équivalent à:
ax ≡ y – b (mod 26)
Puisque pgcd(a, 26) = 1, a possède un inverse multiplicatif
modulo 26. En multipliant les deux membres de la congruence
par a-1, on obtient a-1 ax ≡ a-1 (y-b) mod 26 = (a-1 a)x ≡ 1x ≡ x
Conséquemment, x ≡ a-1(y - b) (mod 26). D’où la fonction de
déchiffrement: d(y) = a-1(y - b) (mod 26)
Exemple: Supposons que K = (7, 3). Comme noté avant, 7-1 mod
26 = 15 la fonction de codage est: ek(x)= 7x+3 et la fonction de
déchiffrement correspondante est: dk(x)= 15(y-3)=15y-19.

23
 Chiffrement de Vigenère
Dans les chiffrements par décalage et substitution, une fois la clé
choisie chaque caractère alphabétique correspond à un caractère
unique de l’alphabet. Cest pour cela que ces crypto-systèmes sont
appelés monoalphabétiques. Le crypto-système de Vigenère est dit
polyalphabétique.
En utilisant la correspondence A ↔ 0, B↔ 1, . . ., Z↔ 25 on peut
associer à chaque clé K, une chaine de caractère alphabétique
nommé mot-clé. Le chiffrement de Vigenère code m caracère
alphabétiques à la fois.
Exemple: Prenons m = 6 et le mot clé CIPHER, cela correspond à
un équivalent numerique K = (2, 8, 15, 7, 4, 17). Soit le texte clair:
thiscryptosystemisnotsecure.
On convertit les elements du plaintext en restes modulo 26, et
assemblés en groupe de 6 puis ajouter le mot clé modulo 26 comme
suit:

24
 Chiffrement de Vigenère (suite)

L’équivalent alphabétique du texte chiffré serait la chaine

suivante: VPXZGIAXIVWPUBTTMJPWIZITWZT. Pour déchiffrer,
on peut utiliser le même mot clé en effectuant un soustraction
modulo 26 au lieu d’une addition.
25
 Chiffrement de Vigenère (suite)

 On remarque que le nombre de mots clés possibles de longeur m

dans un chiffrement de Vigenère est de 26 m, même pour une
valeur relativement faible de m, une recherche exhaustive de clés
nécessiterait un temps long. Par exemple, pour m=5, l’espace des
clés dépasse 1.1 × 107.
 Dans un chiffrement de Vigenère de mot-clé de longeur m, un
caractère alphabétique peut lui correspondre un caractère parmi
m. C’est à dire, au cours du chiffrement, un caractère en clair peut
lui correspondre différents caractère de l’alphabet du cipher text
et cela en fonction de l’occurrence du caractère dans le plaintext.
Un tel crypto-système est appelé polyalphabétique.
 En général, la cryptanalyse est plus difficile pour les crypto-
systèmes polyalphabétiques que monoalphabétiques.

26
 Chiffrement de Hill

Ce chiffrement dit de Hill est un autre crypto système

poly alphabétique. Inventé par Lester S. Hill en 1929.
Soit m un entier positif, et considérons P=C= (Z26)m .
L’idée est de prendre m combinaisons linéaires de m
caractères alphabétiques d’un élément du texte en clair
(Plaintext), pour produire m caractères alpha-bétiques
d’un élément du texte chiffré (Ciphertext).
Par exemple, si m = 2, on pourra écrire un élément du
plaintext x = (x1, x2) et a élément du ciphertext y = (y1,
y2). Ici, y1 serait une combinaison linéaire de x1 et x2
de y2. Ainsi, on aura:
27
 Chiffrement de Hill (suite)

Ce qui peut être écrit en notation matricielle comme suit:

En général, on utilise une matrice K m × m comme clé, K =

(ki,j). Pour x = (x1, . . . , xm) є P et pour K є Қ on calcule y =
e(x) = (y1, . . . , ym) comme suit:

Autrement dit, y = xK.

28
 Chiffrement de Hill (suite)
Le ciphertext est donc obtenu à partir du plaintext au moyen
d’une transformation linéaire. Comment doit être réalisé le
déchiffrement? C’est à dire comment obtenir x à partir de y? On
doit utiliser la matrice inverse K-1 pour le déchiffrement en
employant la relation x = yK-1. Si A = (ai,j) est une matrice l × m
et B = (bj,k) est une matrice m × n, alors la matrice produit AB =
(ci,k) par la formule :

Pour 1 ≤ i ≤ l et 1 ≤ k ≤ n. AB est une matrice de dimension l×m.

29
 Chiffrement de Hill (suite)
La matrice identité de dimension m × m notée Im, est
la matrice formée de la diagonal principale contenant
des 1 et 0 ailleurs. Donc la matrice I2

Im est appelée matrice identité puisque AIm = ImA  A

et Im. L’inverse d’une matrice A de dimension m × m
(si elle existe) est la matrice A-1 telle que AA-1 = A-1 A =
Im. Il existe des matrices n’ayant pas d’inverses mais s’il
existe, il est unique. Ainsi, on a:
30
 Chiffrement de Hill (suite)
Im est appelée matrice identité puisque AIm = ImA  A
et Im. L’inverse d’une matrice A de dimension m × m
(si elle existe) est la matrice A-1 telle que AA-1 = A-1 A =
Im. Il existe des matrices n’ayant pas d’inverses mais s’il
existe, il est unique. Ainsi, on a:

Supposons que la clé K est : ( 11 8)

(3 7)

( 7 -8) (7 -8) ( 7 18)

alors K-1= 1/detK (-3 11) = 1/53 (-3 11) = 1(23 11)

31
 Chiffrement de Hill (suite)
Supposons qu’on veuille chiffrer le texte en clair EURO.
17, 14). Puisque la matrice de chiffrement est de
dimension 2x2, on décompose le plaintext en deux
digrammes EU et RO correspondant respectivement à
(4, 20) et (17, 14).
(11 8)
(4,20)(3 7) = (44+60, 32+140) = (0, 16) → (A, Q) et
(11 8)
(17, 14) ( 3 7) = (187 + 42, 136 + 98) = (21, 0) → (V,A)
D’où le texte chiffré correspondant au texte en clair
EURO est AQNA
32
 Chiffrement de Hill (suite)
Pour déchiffrer AQVA, on procède comme suit:
(7 18)
(0, 16)(23 11) = (16*23, 16*11) = (4, 20) → (E, U) et
(7 18)
(21, 0)(23 11) = (147, 378) ≡ (17, 14) → (R, O)
Le texte en clair est bien obtenu.
Le déchiffrement n’est possible que si K est inversible.
L’inversion d’une matrice (carrée) dépend de la valeur
de son déterminant. Une matrice réelle K est inversible
si et seulement si son déterminant est différent de 0.
Comme on travail dans Z26 K a une matrice inverse
modulo 26 ssi pgcd (det K, 26) = 1.
33
 Cryptographie à Clé Symétrique
• Techniques Modernes
Avènement numérique  changement des paradigmes du
chiffrement symétrique. Formalisation de la discipline mais
la conception des systèmes de chiffrement garde son
aspect artisanal.
• Deux type d’algorithmes de chiffrement:
 Algorithmes à blocs recevant en entrée des données
découpées en blocs de taille fixe de n bits (entre 32 et
512 bits) et en génèrent des blocs chiffrés en sortie selon
une transformation invariable.
DES: ancêtre (bloc de taille 64 bits), devenu obsolète et
remplacé par AES (128 bits) Blowfish, Towofish
alternatives à AES.
34
 Cryptographie à Clé Symétrique
 Algorithmes par flots (flux): traitent des données de
longueur quelconque sans découpage, par exemple:
 A5/1 algorithme (1994), utilisé pour chiffrer les
communications radio entre mobile et station relais la
plus proche (GSM);
 RC4, plus répandu (1987), utilisé dans WEP du Wifi
 E0, utilisé dans Bluetooth
Chiffrement par flot : générateur de nombres pseudo
aléatoires + XOR entre un bit en sortie du générateur
et un bit de données. Les bits du texte en clair sont
chiffrés un à un et la transformation varie durant le
cryptage. Ce dernier ne dépend que de l’état courant.
35
 Cryptographie à Clé Symétrique
Chiffrement par blocs peut être converti en chiffrement
par flots en chiffrant les blocs indépendamment les uns
des autres ou en effectuant XOR entre résultats successifs
chainés. Il peut être utilisé comme fonction de hachage.
• Le chiffrement à flot est plus rapide que le chiffrement à
blocs et présente moins de complexité hard. Toutefois,
lorsqu’il est mal utilisé, le chiffrement à flot peut être
confronté à de sérieux problèmes de sécurité:
• Chiffrement et déchiffrement avec XOR
Soit l’opérateur booléen XOR
Chiffrement du msg M avec clé K: M  K = C
Déchiffrement du msg C avec la clé K:
C  K = (M  K)  K = M  (K  K) = M
36
 Cryptographie à Clé Symétrique
• Différents types de chiffrements par flux
Les chiffrements par flots (CPF) peuvent être vus comme
approximation du chiffrement incassable théorique de
Shannon préconisant une clé (keystream) de taille au
moins égale à celle du texte en clair et complètement
générée de manière aléatoire  système pratiquement
très encombrant à implémenter.
Un CPF génère des éléments successifs de la séquence
de clé sur la base de l’état interne. Cet état est mis à jour
de deux manières: Si l’état change indépendamment du
message en clair ou chiffré, le chiffrement est classé
comme Synchrone. Le chiffrement est dit auto-
synchronisant si la mise à jour de son état dépend du
texte chiffré antérieur. 37
 Cryptographie à Clé Symétrique
• CPF synchrone
Un flux de chiffres pseudo-aléatoires est généré indépen-
demment des messages en clair et messages chiffrés, puis
combinés avec le texte en clair (chiffrement) ou le texte
chiffré (déchiffrement). Dans la plupart des schémas, des
chiffres binaires (keystream) sont combinés (XOR) avec le
texte en clair. Ce processus est appelé CPF binaire additif.
Dans pareil cas, l’émetteur et récepteur doivent être
synchronisés pour assurer un déchiffrement correct.
Une modification lors de la transmission (ajout ou retrait)
invalide la synchronisation.

38
 Cryptographie à Clé Symétrique
Si un chiffre est corrompu lors de la transmission, seul un
chiffre affecte le texte en clair et l’erreur n’est pas
propagée à d’autres parties du message. Cette propriété
est utile lorsque le taux d’erreurs est important.
• CPF auto-synchronisant ou asynchrone
Approche utilisant N chiffres du texte chiffré précédent
pour calculer la clé keystream
Avantage: Le récepteur se synchronise automatiquement
sur le générateur de clés après réception de N chiffres,
permettant ainsi de recouvrer facilement si des chiffres ont
été ajoutés ou supprimés du flux de messages. Les erreurs
affectant un chiffre ne peuvent se propager au delà de N
chiffres du texte en clair  difficulté de réaliser des
39
attaques actives.
 Cryptographie à Clé Symétrique
• Chiffrement par flux à base de registre à décalage linéaire
Les registres à décalages linéaires sont très utilisés dans les CPF
binaires car leur implémentation hard est peu couteuse et leurs
propriétés sont bien maitrisées. Leur utilisation tel quel (Linear
Feedback Shift Register) présente des insuffisances sécuritaires.
Des configurations variées ont été proposées par améliorer leur
sécurité en particulier: combinaison non linéaire de fonctions où
n LFSRs sont utilisés en parallèle avec leurs sorties combinées aux
n entrées d’une fonction booléenne.
Ce procédé permet de détruire leur linéarité par la fonction
booléenne non linéaire afin de former un générateur de
combinaisons  Ce qui assure l’évitement d’attaques corrélées.

40
 Cryptographie à Clé Symétrique

Linear Feedback Shift Register (LFSR)

Combinaison de LFSRs avec Fonction Non linéaire

41
 Cryptographie à Clé Symétrique
• Sécurité des CPF
Pour qu’un CPF soit sûr, sa clé (keystream) doit avoir une
large période et qu’il soit impossible de retrouver la clé
du chiffrement ou l’état interne à partir de keystream.
• Usage des CPF
Ils sont utilisés dans des applications où le texte en clair
arrive en taille inconnue, par exemple connections sans
fil sûres.

42
 Cryptographie à clé symétrique
 La CCS est rapide: Cryptage et décryptage
 Peut être facilement implantée aussi bien de manière
hard ou soft
 Difficile à casser analytiquement
 Sensible à l’attaque de force brute
 Les machines devenant de + en + rapides  accroître
le nombre de rounds et la longueur des clés.
 Problème majeur: distribution sure des clés.

43
 Cryptographie Asymétrique
• La cryptographie asymétrique ou à clé publique utilise
une pair de clé pour chaque pair de partenaires en
communication. Une des clés est publique et accessible
à tous et l’autre est privée: confidentielle connue de son
seul détenteur. Les deux clés doivent être protégées
contre toute modification.
• Il existe une multitude de crypto systèmes dont le
premier est RSA pouvant fournir différents services de
sécurité.
• Crypto Systèmes hybrides
La cryptographie symétrique et publique possèdent des
avantages et inconvénients relatifs. La CCP offre plus de
sécurité mais elle requiert un temps de calcul important.
44
 Cryptographie asymétrique
La différence en terme de temps de calcul peut varier d’un
facteur de 1000 à 10000.  Tirer meilleur parti des deux
en les combinant  hybridation: Crypter volume
important de données à l’aide de CCS et utiliser CCP pour
crypter des données nécessitant peu de ressources telles:
authentification des message et la distribution de clés
dans CCS.

45
 Cryptographie Asymétrique

• Functions Asymétrique (sens unique)

• Etant donnée une fonction f, il est aisé d’évaluer y =
f(x)
• Mais connaissant y il n’est pas possible de trouver x
• Exemple trivial de fonction asymétrique
• Cryptage: y = x2
• Décryptage : x = Y
• Défi: Trouver une fonction avec des propriétés de
sécurité fortes avec cryptage et décryptage efficace.

46
 Protocole d’échange de clé Diffie-Hellman
• L’échange de clé D-H (1976) est un protocole permettant
à deux parties n’ayant à priori aucune connaissance l’une
de l’autre d’établir une clé secrète partagée à travers un
canal de communication non sécurisé. Cette clé peut
être utilisée par la suite pour crypter les communications
à l’aide du chiffrement à clé symétrique.
• Bien que le protocole D-H key exchange est en lui-même
un protocole anonyme, il fournit une base pour une
variété de protocoles authentifiés.
• Le protocole a été suivi juste après (1977) par RSA,
autre protocole de cryptographie asymétrique.

47
 Protocole d’échange de clé Diffie-Hellman
• Description
AB BA

b
a, g, p
B=gb mod p
A=ga mod p g, p, A

K=Ba mod p B K=Ab mod p

K=Ab mod p = (ga mod p)b mod p = gab mod p = (gb mod p)a mod p = Ba mod p

48
 Protocole d’échange de clé Diffie-Hellman
AB BA
Secret calculé calculé secret

p, g p, g
a b
g a
mod p gb mod p
(gb mod p)a (g a
mod p)b
mod p mod p

K = (ga mod p)b mod p = gab mod p = (gb mod p)a mod p = gba mod p

49
 Diffie- Hellman Protocol
• Protocole
1. Les partenaires choisissent un groupe cyclique G fini et
un élément g  G
2. AB choisi un entier aléatoire a et envoie ga à BA
3. BA tire un entier aléatoire b et envoie gb à AB
4. AB calcule (gb)a
5. BA calcule (ga)b
Les partenaires AB et BA possèdent tous deux l’élément
gab  G pouvant servir comme clé secrète partagée.

50
 Diffie-Hellman Protocol (suite)
Exemple:
- A et B décident de choisir 23 comme nombre premier et g=5
comme base.
- A choisit a=6 comme entier secret et envoie à B le nombre
- (ga mod p) = 56mod 23 = 8
- B choisit l’entier secret b=15 et envoie à A 19= (gb mod p)
- A calcule (gb mod p)a mod p = 196 mod 23 = 2
- B calcule (ga mod p)b mod p = 815 mod 23 = 2
A et B sont arrivés à calculer la même valeur 2 car gab = gba
Seuls a, b, gab = gba sont maintenus secrets, les autres valeurs :
p, g, ga mod p et gb mod p sont transmis en clair;

51
 Diffie-Hellman Protocol (suite)
• Pour pouvoir réaliser un processus de chiffrement sûr, il est
indispensable de choisir des valeurs de a, b, p très grandes en
particulier p. Avec p codé sur 300 bits et a et b sur 100 bits, il
n’est pas possible de déterminer a en connaissant seulement g,
p et ga mod p. Pratiquement g n’est pas important souvent
égal à 2 ou 5.
 Sécurity du protocole
DH est considéré suffisamment sûr vis-à-vis des écoutes
(espionnage) à condition de choisir un facteur premier assez
large.
 Athentification
DH originel ne permet pas l’authentification des parties
communicantes , donc vulnérable à l’attaque man-in-the-middle:
attaquant entre les deux parties pouvant établir deux
échanges de clés DH distincts: Se déguisant en partenaire de
52
 Diffie-Hellman Protocol
L’un vis-à-vis de l’autre. Toutefois, il est possible de rendre le
protocole DH résistant à l’attaque de l’homme du milieu.

53
 Rivest Shamir Adelman (1977)
Agorithme asymétrique de cryptographie à clé publique, très
utilisé dans e-commerce pour échange de données (avec sites
web commerciaux: cartes bancaires) confidentielles sur Internet.
• Fonctionnement
Deux clés sont nécessaires: une publique pour chiffrer
(respectivement vérifier) et une privée pour déchiffrer
(respectivement signer) des informations confidentielles. Clé
publique accessible à toute personne désirant chiffrer des
données, clé privée réservée à celui ou celle ayant créé la paire
de clés.
Soient A, B, C souhaitant échanger des informations
confidentielles, par convention, A prend en charge la création de
la paire de clés, envoie sa clé publique à B et C qui enverront des
données chiffrées par cette clé à A. A peut les

54
 Rivest Shamir Adelman (suite)
Les déchiffrer à l’aide de sa clé privée.
 Création des clés
Choisir 2 nombres premiers p et q tels que p ≠ q
1. Calculer n = pq
2. Calculer l’indicatrice d’Euler de n: φ(n) = (p-1)(q-1)
3. Choisir e: entier premier avec φ(n) : appelé « exposant de
chiffrement », 1  e  φ(n)
4. Comme e est premier avec φ(n) , il est inversible mod φ(n)
cad il existe d є N tel que ed = 1 (mod φ(n) ). d est l’exposant
du déchiffrement. Calculer donc d= 1/e (mod φ(n)
Le couple (n, e) est appelé clé publique et (n,d) est la clé privée
Chiffrement d’un message
Si M est un entier < n (représentant un message), le msg chiffré
sera représenté par C= Me (mod n) 55
 Rivest Shamir Adelman (suite)
• Déchiffrement d’un message
Pour déchiffrer C, on utilise d: inverse de e mod φ(n) et on
calcule Cd (mod n) = (Me )d (mod n) = Med (mod n)
Comme ed= 1 (mod φ(n)) (par déf de modulo), on a
ed = 1 + K φ(n) = 1 + K(p-1)(q-1), avec k entier or pour tout
entier M, M1+k(p-1)(q-1) = M (mod p) et
M1+k(p-1)(q-1) = M (mod q)
En effet:
• Si M est premier avec alors
Mp-1 = 1 (mod q) (théoreme de Fermat) donc
Mk(p-1)(q-1) = 1 (mod q) puis Mk(p-1)(q-1) = M (mod q)
• Si M n’est pas premier avec P, et comme P est premier  M

56
 Rivest Shamir Adelman
est multiple de P d’où M1+k(p-1)(q-1) = 0 = M (mod n). On prouvera
de la même manière la congruence modulo q.
M1+k(p-1)(q-1) – M est donc multiple de p et de q. Comme p et q
sont premiers et premiers entre eux, d’après le lemme de
Gauss, M1+k(p-1)(q-1) – M est multiple de pq=n, on a donc:
Cd = Med = M1+k(p-1)(q-1) = M (mod n), ainsi:
• Pour chiffrer un message, il suffit de connaître e et n, et pour
déchiffrer il faut connaître d et n
• Pour calculer d à l’aide de e et n, il faut trouver l’inverse de
e modulo (p-1)(q-1) cad décomposer n en facteurs premiers
 Implémentation
En pratique, deux difficultés surgissent:

57
 Rivest Shamir Adelman (suite)
• Choisir un nombre premier e de grande taille
• Calculer M = Ce mod n  couteux en temps.

58
 Rivest Shamir Adelman
 Sécurité de l’algorithme
Casser RSA nécessite la factorisation de n  problème difficile
car il n’existe pas actuellement d’algorithme à complexité
temporelle polynomiale donnant les facteurs premiers d’un
nombre quelconque. Si on disposerait d’un moyen rapide de
factorisation alors tous les algorithmes de chiffrement basés
sur ce principe seront mis en cause.
Le plus grand nombre factorisé (2005) était long de 663 bits.
Les clés RSA sont habituellement comprises entre 1024 et
2048 bits. RSA est donc considéré sûr si la taille de la clé est
suffisamment grande.

59
 Rivest Shamir Adelman
 Application
 Authentification des parties communicantes dans l’échange
d’informations chiffrées avec signature numérique.
 Chiffrement des clés symétriques: RSA permet la
communication d’une clé symétrique de manière sûre.
Ainsi, A voulant communiquer confidentiellement avec B, A
choisit une clé symétrique et la transmet à B en utilisant RSA
cad chiffrer la clé symétrique avec la clé publique de B.
 Attaques de RSA
• Attaque de Wiener: exploitable si exposant secret d  N1/4
Dans ce cas on peut retrouver d à l’aide du développement en
fractions continues de e/N.

60
 Revest Shamir Adelman
 Attaque de Hastad
Découverte en 1985, elle exploite une valeur de e
suffisamment petite et l’interception d’un même message à
plusieurs destinations pour pouvoir retrouver le message
originel à l’aide du théorème des restes chinois.
 Attaque par chronométrage (timing attacks)
Décrite par Kocher (1995), exploite le temps nécessaire au
déchiffrement de plusieurs documents chiffrés pour en
déduire rapidement la clé de déchiffrement; il en serait de
même pour la signature.
Boneh et Brumley (2003) ont révélé une attaque plus pratique
permettant de retrouver la factorisation RSA sur une connexion
réseau SSL en s’appuyant sur les informations provenant de
certaines optimisations appliquées au théorèmes des restes
chinois.
61
 Revest Shamir Adelman
• Une manière de contrecarrer ces attaques consiste à
assurer que l’opération de déchiffrement prenne un temps
constant  réduction significative des performances.
Utiliser alors une technique différente: aveuglement
cryptographique
Mettre en échec l’attaque par chronométrage  utiliser la
technique de l’aveuglement pour que le temps de
déchiffrement ne soit pas corrélé aux données à chiffrer:

62
 Signatures numériques
Les signatures numériques jouent un rôle fondamental pour
l’authentification, l’identification d’entité, l’autorisation et la
non-répudiation.
• Fonctionnement général
Inverse du système à clé publique: Pour se faire authentifier
par le destinataire, l’émetteur chiffrera un message avec sa clé
privée et le destinataire déchiffrera le message (chiffré) avec
la clé publique de l’expéditeur.

63
 Chiffrement ElGamal
Génération de clé:
 On travaille sur un groupe cyclique d’ordre Zp avec un générateur g (non
secret)
 Un receveur A tire au hasard un nombre x entre 0 et p-1. A calcule ensuite
y = gx[p].
 x est la clé secrète, (p, g, y) la clé publique.
0 < x < p-1
y ≡ gx mod (p)
Chiffrement:
 Un émetteur B chiffre avec la clé publique du destinataire A (p, g, y)
 B convertit le message m vers m’, un élément du groupe Zp
 Il tire un nombre aléatoire h et calcule s=yh (dans Zp)
 Il calcule ensuite c1= gh et c2=m’.(yh)
 Le chiffré est le couple (c1, c2)
64
 Chiffrement ElGamal (Suite)
m → m’, m’є Zp, h є Zp s ≡ yh mod(p)
c1 ≡ gh mod(p) c2 ≡ m’yh mod(p)
 Déchiffrement
 Le chiffré est constitué du couple (c1, c2)
 A reçoit (c1, c2), c’est à dire (gh, m’. ((gx)h))
 A retrouve m’ en calculant c2 / (c1x) car A connaît x
 On applique la transformation inverse à m’ pour obtenir m

C1 ≡ gh mod(p), C2 ≡ m’.yh mod(p)

C1 ≡ gh mod(p), C2 ≡ m’. (gx) h mod(p)
C2/C1x = m’.gx.h/gh.x C2/C1x = m’

65
 Chiffrement ElGamal (Suite)
 Problèmes pratiques:
 Passage de m à m’
 Temps de calcul des exponentiations (2
exponentiations et une seule dans RSA)
 Augmentation de la taille du groupe == augmentation
de la sécurité mais aussi augmentation du temps de
calcul
 En pratique, cela ne permet pas de chiffrer des
volumes importants d’informations
 ElGamal est un chiffrement malléable: en connaissant
(c1, c2) on peut générer un chiffré valide (c1, 2.c2)
correspondant au “message” 2.m’
 Sécurité:
 Actuellement, GPG génère des clés de 2048 bits, des
clés de 1024 bits sont encore “raisonnables” de nos
jours ... 66
 Chiffrement ElGamal (Suite)
Exemple : Soit Zp (p=11) un groupe cyclique et g=2 (a=2) un
élément générateur de Zp
Clé privée x = 5
Calculer d = 25 mod 11 = 10, la clé publique est = (11 ,2 ,10)
Soit le texte en clair (Plaintext) = ’age’ représenté par sa valeur
numérique P = (1 7 5) a=1 ..
Chiffrement (émetteur): y = ak mod p, z = (dk * m ) mod p
Choisir un entier aléatoire k = 6, ya = 26 mod 11 = 9, za = (106*1)
mod 11 = 1
Choisir un entier aléatoire k = 4, yg = 24 mod 11 = 5, zg = (104*7)
mod 11 = 7
Choisir un entier aléatoire k = 7, ye = 27 mod 11 = 7, ze = (107*5)
mod 11 = 6
67
 Chiffrement ElGamal (Suite)

Ciphertext = (9,1) (5,7) (7,6)

L’émetteur B envoie le texte chiffré au receveur A :
Le receveur décrypte le ciphertext comme suit :
Calculer (r) et (m) où
r = yp-1-x mod p, m = ( r * z ) mod p
r1= 911-1-5 mod 11 = 1, m1= (1*1) mod 11= 1
r1= 511-1-5 mod 11 = 1, m2 = (1 * 7) mod 11 = 7
r1= 711-1-5 mod 11 = 10, m3 = (10 * 6) mod 11 = 5
Le receveur détermine le texte en clair P = (1 7 5)
qui correspond au texte alphabétique : age
68
 Chiffrement ElGamal (Suite)

 Signature ElGamal
Soit p un nombre premier, et g un générateur de F*p
- Clé privée : Un entier 0 < a < p - 1 premier avec Ф(n)
- Clé publique : (p, g, y = ga).
Le schéma de signature El Gamal est le suivant :
- Signature d'un message m : (r, s) = (gk mod p, k-1
(h(m) - ar) mod p - 1). h= fonction de hashing
- Vérification : Tester si yr rs = g h(m).

69
 Chiffrement ElGamal (Suite)
Exemple
p = 11, g = 2, x = 8
y = gx mod p = 28 mod 11 = 3 PK = (3, 2, 11)
Authentification : M = 5 , k= 9 (9,10) =1 (ok)
a = gk mod p = 29 mod 11 = 6
Par Euclide :
M = (ax + bk) mod (p-1)
5 = (8*6 + 9*b) mod 10
b = 3 → signature = (a,b) = (6,3)
Vérification :
yaab mod p = gM mod p
3663 mod 11 = 25 mod 11
70
Chiffrement ElGamal (Suite)

71
Signatures Electroniques

72
Signatures Electroniques (Suite)

73
Signatures Electroniques (Suite)

74
Signatures Electroniques (Suite)

75
Courbes Elliptiques (suite)

76
Courbes Elliptiques (suite)

77
Courbes Elliptiques (suite)

78
79
80