Chapitre 2 Cryptographie

Chapitre 2: La cryptographie
2021-2022
Plan
 Généralités
 La cryptographie symétrique
• Opérations de base
• Le protocole DES
• Le protocole AES
 La cryptographie asymétrique
• RSA
• Diffie Hellman
• ECC
 La signature numérique
• Signature RSA
• DSA
• ECDSA
Fondements de sécurité, 2021 2

Plan
 Généralités
• RSA
• Diffie Hellman
• ECC
• Signature RSA
• DSA
• ECDSA
Introduction
 Cryptographie: Science mathématique permettant
d’effectuer des opérations sur un texte intelligible afin
d’assurer une ou plusieurs propriétés de la sécurité de
l’information
 Cryptanalyse : la science permettant d’étudier les systèmes
cryptographiques en vue de les tester ou de les casser
 Cryptologie : la science qui regroupe la cryptographie et la
cryptanalyse

Introduction
Un crypto-système est décrit par cinq uplets (P,C,K,E,D),
satisfaisant ces conditions:
 «P» est un ensemble fini de textes clairs (plain text)
 «C» est un ensemble fini de textes cryptés (cypher text)
 «K» est l’espace de clés (key space), représente un
ensemble fini de clés possibles.
 Pour chaque k € K, il existe une fonction cryptage ek € E, et
une fonction de décryptage correspondante dk’ € D
• Les fonctions ek : PC et dk’ : CP doivent satisfaire:
dk’(ek(x))=x pour chaque x € P
 Crypto-système
• Les crypto-systèmes symétriques
• Les crypto-systèmes asymétriques
• Les fonctions de hachage
Introduction
Un algorithme cryptographique doit assurer ces
principaux objectifs:
• Le texte clair ne doit pas être facilement obtenu à
partir d’un texte crypté.
• Les clés ne doivent pas être facilement obtenu à
partir d’un texte crypté.
• L’espace des clés doit être assez large pour résister
aux attaques brute-force.
• Confusion: le processus modifie radicalement les
données du texte clair par rapport à ceux du texte
chiffré.
• Diffusion: un petit changement dans le texte clair doit
avoir un effet sur une large partie du texte crypté.

Caractéristiques d’un cryptosystème
Les systèmes cryptographiques sont caractérisés par trois
dimensions:
1. Type de l’opération utilisée pour transformer un texte clair
en un texte crypté
 Substitution: replacement de chaque élément (bit,
lettre, groupe de bits ou de lettres) dans le texte clair
par un autre élément.
 Transposition: réarrangement des éléments du texte
clair.
- La plupart des systèmes utilisent plusieurs étapes de
transposition et de substitution.

2. Nombre de clés utilisées
 Modèle de cryptage symétrique: M=D(E(M,K),K)
Canal non sécurisé
Canal sécurisé
 Modèle de cryptage asymétrique: M=D(E(M,K),K-1) avec
K-1 ≠ K en général
Canal non sécurisé
Canal sécurisé

3. La méthode par laquelle le texte clair est traité
 Stream Cipher: traite les éléments d’entrée de façon
continue, produisant un élément de sortie (crypté), à la
fois.
• La clé est aussi longue que le stream de données.
• Étapes:
• Définition de l’état initial du key stream
• Définition de la fonction état suivant: next-state function
• Combinaison du key stream courant avec la clé K et les
caractères précédent. La fonction de sortie doit aussi
modifier l’état interne.
• Crypte chaque caractère xi du texte clair avec un caractère
zi du key stream (exemple xor)
Stream Cipher
 Pour un texte clair P=x1x2x3x4x5… et une clé l=l1l2l3l4l5… il
existe une fonction de cryptage El et des algorithmes de
cryptage E l tel que:
• C = El ( P)
i
• C = El1 ( x1 ) El2 ( x2 )...

• li = f (k , x1, x2 , xi −1 )
 Les valeurs l1 , l2 , l3, l4 , … sont appelées key streams
 Syncronous cypher: Le key stream ne dépends pas du texte
clair. La période du key stream est égale à d tel que: li+d=li
 Self-synchronizing: le key stream dépends de n caractères
clairs précédents.
10
Block Cipher
 Block Cipher: Le texte clair est divisé en différents
blocks P1, P2, P3 … de taille fixe (64, 128, …octets).
 Un block Pi est traité à la fois, produisant un block de
données crypté Ci.
 Si la longueur du message n’est pas un multiple de la
longueur d’un bloc, on le complète : c’est le bourrage
(padding).
 NIST définit plusieurs modes d’opérations:

• Electronic codebook mode (ECB)
• Cipher block chaining mode (CBC) – le plus connu
• Cipher feedback mode (CFB)
• Output feedback mode (OFB)
• Counter mode (CTR)
Cryptanalyse
 Principes et méthodes permettant de trouver un message

clair à partir d’un message crypté sans connaissance de la
clé.
 Attaques classifiées selon le type de connaissance
disponible pour l’intrus (cryptanalyste).
 Connaissant C=E(P,K) mais pas K, l’objectif est de trouver P
ou K.
 Types d’attaques de cryptanalyse:
• Texte chiffré uniquement: uniquement C et E sont connus par
l’intrus
• Texte clair connu: Uniquement E, C, et quelques paires de
messages clairs/cryptés avec K, sont connus par l’intrus
• Texte clair choisi: E, C, sont connu, et P a été choisi par
l’intrus.
• …

Plan
 Généralités
• RSA
• Diffie Hellman
• ECC
• DSA
• ECDSA
La cryptographie symétrique
 Les deux parties communicantes utilisent un algorithme symétrique et une
même clé pour crypter et décrypter les données
 Une clé symétrique appelée aussi clé de session est une séquence binaire
aléatoire dont la longueur dépend de l’algorithme
 Un algorithme est une séquence de transformations sur les données et la clé
Clé Texte crypté= Clé

01010000111 cryptogramme 01010000111
Texte clair Texte clair

Cryptage Internet Décryptage
Voici le Voici le
numéro numéro
de ma de ma
carte de ☺☼♀☻ carte de
crédit crédit
111111, ♠♣▼╫◊ 111111,
♫◙◘€£
Émetteur ¥₪Ω‫٭‬ Récepteur

Chiffrement symétrique
 Cryptage par flux (stream cipher)
• Opère sur un flux continu de données
• Mode adapté pour la communication en temps réel
• Implémentation matérielle en général
• Exemple: RC4 (longueur de clé variable, généralement 128 bits)
 Cryptage par bloc
• Opère sur des blocs de données de taille fixe (généralement 64 bits)
• Implémentation logicielle en générale
• Exemples: DES (Clé: 56 bits codée sur 64 bits); 3DES (EDE (Encrypt-
Decrypt-Encrypt), Trois clés distincts ou seulement deux); IDEA (128
bits); AES longueur de clé variable: 128, 192, 256)
Opérations de base
 Substitution
 Transposition
 Opérations algébriques simples

Chiffrement par substitution
 Cette méthode correspond à substituer un caractère ou un groupe de
caractères par un autre dans le texte à chiffrer.
 Plusieurs types de crypto-systèmes par substitution :
• monoalphabétique (code César) consiste à remplacer chaque lettre
du message par une autre lettre de l'alphabet
• homophonique permet de faire correspondre à chaque lettre du
message en clair un ensemble possible d'autres caractères
• polyalphabétique (code Vigenère) consiste à utiliser une suite de
chiffrement, monoalphabétique réutilisée périodiquement ;
• polygrammes consiste à substituer un groupe de caractères
(polygramme) dans le message par un autre groupe de caractères.
Chiffrement par substitution simple

 Chaque symbole du plaintext est remplacé par un autre de
manière unique
plaintext: abcdefghijklmnopqrstuvwxyz
ciphertext: mnbvcxzasdfghjklpoiuytrewq
E.g.: Plaintext: bob. how are you. alice

ciphertext: nkn. akr moc wky. mgsbc

Exemple de cryptage par substitution simple
 Caesar's cipher
• Remplacer chaque lettre par celle qui la succède de trois.
• a devient d, b devient e, …, y devient b, z devient c
• L’algorithme peut être décrit comme suit:
• C = E(p) = (p+3) mod (26)
 La distribution fréquentielle des symboles est préservée dans le ciphertext
 Vulnérabilité aux attaques de cryptanalyse statistique : il suffit de calculer
la fréquence d’apparition de chaque symbole dans le ciphertext et de le
comparer aux fréquences d’apparition des lettres de l’alphabet dans une
langue particulière.
• Algorithme de cryptage et de décryptage connu.
• Seulement 25 clés à essayer.
• Le langage du message clair est connu et facilement identifiable.
Exemple de cryptage par substitution simple
 Exercice
Retrouver le clair du message codé à l’aide de
l’algorithme de César (La clé est 3)
«FRGDJHGHFHVDU ».
 Solution
• L’algorithme à translation de César correspond à
une translation de 3 lettres (clé) pour passer du
message original au message crypté.
• Ainsi, la lettre F d’un message crypté

correspondra à la lettre C du message clair.
• Le texte clair est « CODAGE DE CESAR »
Chiffrement par substitution polyalphabétique
 Idée d'amélioration : Substitution polyalphabétique:
utilisation de deux ou plusieurs alphabets de chiffrement.
 Cette méthode opère sur des blocs de taille t
 A chaque symbole du bloc on applique une substitution
simple différente
Exemple:

• Vignère cipher (exemple):
- Il opère sur des blocs de taille 3
- Le premier symbole du bloc est remplacé par le troisième symbole à droite
- Le deuxième symbole du bloc est remplacé par le septième symbole à
droite
- Le troisième symbole du bloc est remplacé par le dixième symbole à droite
THIS CIPHER IS NOT CERTAINLY SECURE

THI SCI PHE RIS NOT CER TAI NLY SEC URE
Vignère Cipher
WOS VJS SOO UPC QVD FLB WHS QSI VLM XYO

 Le chiffre de Vigenère
 Le carré de Vigenère :
• 26 alphabets : chiffrement de César
 Clé de chiffrement : un mot clé identifiant les alphabets à
utiliser

 L'idée de Vigenère est d'utiliser un code de César, mais où le

décalage utilisé change de lettres en lettres.
 Pour coder un message,
• on choisit une clé qui sera un mot de longueur arbitraire.
• On écrit ensuite cette clé sous le message à coder, en la
répétant aussi souvent que nécessaire pour que sous
chaque lettre du message à coder, on trouve une lettre de
la clé.
• On remplace les lettres par leur rang dans l’alphabet
(attention on commence à 0).
• A chaque lettre on additionne les deux rangs et on prend le

reste de cette somme dans la division euclidienne par 26 et
on trouve ainsi la lettre codée correspondante.
Exemple

Substitution homophonique
 Au lieu d'associer un seul caractère

crypté à un caractère en clair on dispose
d'un ensemble de possibilités de
substitution de caractères dans laquelle
on choisit aléatoirement.
Transposition: Principe
 La transposition représente la
permutation des symboles d’un plaintext
 Conserve la distribution des symboles
 La cryptanalyse statistique est possible

Exemple de cryptage par transposition
Rail fence technique

 Le texte clair est réécrit comme une séquence
de lignes, puis réordonnée comme une
séquence de colonnes
Key: 4 3 1 2 5 6 7
Plaintext: a t t a c k p
o s t p o n e
d u n t i l t
w o a m x y z
Ciphertext: TTNA APTM TSUO AODW COIX KNLY PETZ
Opérations algébriques simples

 Composition des fonctions (fog)
 XOR
 Remarque:
• La substitution ajoute du désordre (confusion) au
processus de cryptage. L’objectif est de rendre la
relation entre le ciphertext et la clé la plus compliquée
que possible
• La transposition ajoute de la diffusion au processus
de cryptage. L’objectif est de réarranger les bits du
plaintext afin de détruire toute forme de redondance

Algorithmes de chiffrement symétriques
Fondements de sécurité, 2021 31 31
DES
Principe de Kerkhoffs:
La sécurité d’un système cryptographique ne doit pas reposer sur

la non divulgation des fonctions de chiffrement et de
déchiffrement utilisées mais sur la non divulgation des clés
utilisées pour le paramétrer.

DES
 DES: Data Encryption Standard
 Algorithme de cryptage par block(Block cipher) a clés
symétriques
DES
 L'algorithme DES est un algorithme de cryptographie en bloc
• Il opère généralement sur des blocs de 64 bits
• La clé est sur 64bits dont 8 sont utilisés comme calcul de l'intégrité des 56
autres (parité).
• La clé sera transformée en 16 sous-clés de 48 bits chacune.
 En effet, certains calculs ont montrés qu'il était possible d'effectuer une
recherche exhaustive de clé, en 256 essais. Ces calculs sont réalisables en
un temps limité et avec un coût relativement raisonnable.

L'algorithme DES
 Les grandes lignes de l'algorithme sont les suivantes :

1. Fractionnement du texte en blocs de 64 bits (8 octets) ;
2. Permutation initiale des blocs (IP);
3. Découpage des blocs en deux parties: gauche et droite,
nommées G et D ;
4. Étapes de permutation et de substitution répétées 16 fois
(appelées rondes) ;
5. Recollement des parties gauche et droite puis permutation
initiale inverse (IP-1).
L'algorithme DES
1. Fractionnement du texte
2. Permutation initiale des blocs (IP)
Bloc de 64 bits
3. Découpage des blocs en deux parties: gauche et droite

L'algorithme DES
4. Étapes de permutation et de substitution répétées 16 fois
(appelées rondes ou rounds) ;
L'algorithme DES
5. Recollement des parties gauche et droite puis
permutation initiale inverse (IP-1).
32 bits 32 bits
64 bits

L'algorithme DES
Limites de DES
 Les progrès en cryptanalyse et en électronique a fait que la
longueur 56 des clés est devenu un problème pour DES
 La taille de l’ensemble : {0,1}56 permet de retrouver la clé à
partir d’un texte clair connu en faisant du brute force.
 3-DES (triple DES) a été lancé comme un nouveau standard en
1999.
• Utilise 2 ou 3 clés.
• Niveau de sécurité satisfaisant.
• Permet de continuer l’utilisation des boites S-Box et P-Box matériel
et logiciel.
K3
DES
Cryptage décryptage Cryptage Cryptage Cryptage Cryptage

3-DES (triple DES)
 Le triple DES
 Pour palier à la faiblesse du DES concernant sa longueur de clé (56 bits),
on utilise souvent une version renforcée appelée triple DES ou 3DES. Ce
n’est pas la solution car cette version est trop lente, comparée à un AES
par exemple.
 Si EK, DK sont les fonctions de chiffrement et de déchiffrement du DES,
on chiffre par: x = EK1(DK2(EK1(x))), ce qui double la longueur de la clé.
Le protocole AES
• AES: Advanced Encryption Standard
• En 1997 le NIST (National Institute of Standards and Technology) lança
un nouvel appel à projet pour élaborer l'AES (Advanced Encryption
Standard), un algorithme de chiffrement destiné à remplacer le DES

42
Etapes de AES
• Il s’agit d’une
succession de fonction
à appliquer en 10 (clé
128 bits), 12 (clé 192
bits) ou 14 itérations (clé
256 bits).
• Les données et la clé
sont codés en 128 bits
pour AES 128.

43
Représentation des données

AddRoundKey
1 octet
Il s’agit d’une addition
binaire des octets (bytes)
de la donnée avec les
octets de la clé par
l’application de l’opérateur
XOR

45
SubBytes
• Il s’agit d’une étape de substitutions des octets des
données selon une matrice S-Box prédéfinie.

46
Table de substitution (S-box)
SubBytes: Principe
• Interprète chaque octet comme deux
chiffres hexadécimaux x et y
S1,1 = xy16
Chaque octet de la matrice état est remplacé par l’octet situé à

la ligne x (4 bits de gauche) et colonne y (4 bits de droite)
Exemple: l’octet {95} est remplacé par l’octet situé dans la
ligne 9 et la colonne 5 don’t la valeur est {2A}

Table de substitution Inverse
ShiftRows
• Décalage circulaire à gauche des lignes li par i-1 bytes
• InvShiftrows: décalage circulaire à droite des lignes li

par i-1 bytes
50
MixColumns

20/10/2021 LAABIDI Mounira 51
MixColumns
 Chaque colonne est traitée indépandemment des autres
 Chaque octet de la colonne est remplacée par une valeur qui
dépend des 4 octets de la colonne
 Cette valeur est obtenue en multipliant la colonne par la matrice
suivante

Matrice de MixColumns et son inverse
Génération de la clé
 La clé codée sur 128-bits (16-octets) est étendue à un
tableau de 44 mots
 Chaque mot est de taille 32 bits

Key Expansion Scheme
 RotWord fait un décalage circulaire à gauche d’un octet

pour chaque mot:
RotWord[b0,b1,b2,b3] = [b1,b2,b3,b0]
 SubWord permet de substituer chaque octet du mot en

entrée en utilisant la matrice S-box
 SubWord(RotWord(temp)) effectue l’opérateur XOR

avec RCon[j] ( une constante à chaque ronde)

Plan
 Généralités
• RSA
• Diffie Hellman
• ECC
• Signature RSA
• DSA
• ECDSA

Cryptage symétrique
 Limitation: Pas d'intégrité et d'identification de l'auteur
 Si Alice, Bob et Cédric partage le même lien de communication alors ils
partagent la même clé de chiffrement symétrique.
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, ECC
 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-…)

Cryptage asymétrique: confidentialité
Clé publique Clé privée

du récepteur du récepteur
Texte clair Cryptage Décryptage Texte clair

Internet
Voici le Voici le
numéro numéro
de ma de ma
crédit crédit
111111, ♠♣▼╫◊ 111111,
♫◙◘€£
¥₪Ω‫٭‬
Texte crypté
Emetteur Récepteur

61
Cryptage asymétrique: Authentification et non

répudiation
Clé privée Clé publique

de l’émetteur de l’émetteur
Texte clair Cryptage Décryptage Texte clair

Internet
Voici le Voici le
numéro numéro
de ma de ma
crédit crédit
111111, ♠♣▼╫◊ 111111,
♫◙◘€£
¥₪Ω‫٭‬
Texte crypté
Emetteur Récepteur

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

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 »
RSA: Algorithme
Cryptage Décryptage
RSA: Exemple Texte
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

Exemple d'utilisation de RSA
 Création de la paire de clés:
• Soient deux nombres premiers au hasard: p = 29, q = 37, on
calcule n = pq = 29 * 37 = 1073.
• On doit choisir e au hasard tel que e n'ai aucun facteur en
commun avec (p-1)(q-1):
(p-1)(q-1) = (29-1)(37-1) = 1008
• On prend e = 71
• On choisit d tel que 71*d mod 1008 = 1, on trouve d = 1079.
• On a maintenant les clés :

- la clé publique est (e,n) = (71,1073) (=clé de chiffrement)
- la clé privée est (d,n) = (1079,1073) (=clé de déchiffrement)
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.

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.
La méthode Diffie - Hellman
• Le protocole de Diffie Hellman est basé sur le problème

de logarithme discret (Discrete Logarithm Problem
DLP):
DLP: Soit G un groupe cyclique d’ordre n engendré

par g.
Pour y∈G, trouver ℓ∈Z tel que gℓ=y est le problème du
logarithme discret.


Déroulement de l’algorithme

La cryptographie sur les courbes elliptique
 Les systèmes à base de courbes elliptiques appliqués à la

cryptographie ont été proposés pour la première fois en
1985 par Neal Koblitz et Victor Miller.
 La cryptographie à courbe elliptique (Elliptic curve

cryptography [ECC]) est un système cryptographique à clé
publique, tout comme RSA, El gamal, …
 Chaque utilisateur possède une clé publique et une clé

privée:
• La clé publique est utilisée pour le chiffrement/ la
vérification de la signature.
• La clé privée est utilisée pour le déchiffrement / la
génération de la signature.
Fondements de sécurité, 2021

 Les deux parties se mettent d’accord sur des données
publiques:
• L’équation de la courbe elliptique en choisissant les valeurs de a
et b :
y2 = x3 + ax + b
où: 4a3 + 27b2 ≠ 0
• Un nombre premier p
• Le groupe associé à une courbe elliptique est calculé à partir de
l’équation de la courbe elliptique
• Un point, G, choisi à partir du groupe associé à la courbe
elliptique (Comme le générateur utilisé dans DH)
 Chaque utilisateur génère sa paire de clés publique/privée

• Clé privée= un entier x appartenant à l’interval [1, p-1]
• Clé publique= le produit, Q, de la clé privée par le point G
(Q = x*G)

La cryptographie sur les courbes elliptiques
Exemples de courbes elliptiques:

• La sécurité de ECC dépend de la difficulté de résoudre
le problème de logarithme discret.
• Le problème de logarithme discret :
DLP: Soient G et Q deux points sur la courbe elliptique tel que
Q = xG, où x est une valeur scalaire.
DLP: Étant donné Q et G, trouvez x? Si x est très grand, il devient
impossible de le calculer.
• Le probleme de logarithme discret défini sur un groupe

associé à une courbe elliptique est considéré plus
difficile que celui défini sur un groupe fini (muni de
l’opération de multiplication).
• L'opération principale dans ECC est la multiplication de

points
Les courbes elliptiques sont utilisées comme une

extension à d'autres cryptosystèmes actuels:
• Elliptic Curve Diffie-Hellman Key Exchange
• Elliptic Curve Digital Signature Algorithm
 ECDH – Elliptic Curve Diffie Hellman

A (QA,dA) – Paire de clé publique privée
B (QB,dB) – Paire de clé publique privée
1. Soit (QA,dA) la paire de clés d'Alice et (QB,dB) celle de
Bob
2. Alice calcule (xk,yk)=dAQB et Bob calcule (xk,yk)=dBQA
3. La clé partagée est xk (l’abscisse x du point).
La clé partagée secrète calculée par Bob et Alice est égale,

car dAQB=dAdBG=dBdAG=dBQA.

Échange sécurisé
 Résolution du problème de l'échange des clés secrètes :
utilisation d'une méthode hybride combinant à la fois chiffrement
symétrique et asymétrique.
 Avantages :
• on démarre l'échange avec l'utilisation d'un algorithme
asymétrique qui possède l'avantage d'offrir un moyen
d'identifier les interlocuteurs.
• la clé secrète est chiffrée et échangée ;
• après l'échange on bascule le chiffrement en utilisant un
algorithme symétrique plus rapide ;
RSA vs ECC
 Pour protéger une clé
AES de 128 bits, il faut:
• Taille de clé RSA: 3072
bits
• Taille de clé ECC: 256 bits
 Comment peut-on
augmenter le niveau de
sécurité de RSA?
• Augmentez la
longueur de la clé
Avantages de ECC
 Mêmes avantages que les autres crypto-systèmes

asymétriques: confidentialité, authentification et non-
répudiation
 Longueurs de clé plus courtes

- Chiffrement, déchiffrement et vérification de signature
accélérés
- Économie de stockage et de bande passante
Plan
 Généralités
• RSA
• Diffie Hellman
• ECC
• Signature RSA
• DSA
• ECDSA

Fonction de hachage
 Entrée: message M avec contenu et taille arbitraire.
 Sortie: message de taille fixe h=H(M).
 H(M) est appelé condensât, ou empreinte, ou fingerprint, ou
message digest
 Irréversible:
• Étant donnée h, il est difficile de trouver x tel que: h = H(x)
• Complexité de l’ordre de 2n, n est le nombre de bits du digest.
 Résistance forte à la collision:
• Étant donné x, il est impossible de trouver y avec H(x) = H(y)
• Il est impossible de trouver une paire x, y tel que H(x) = H(y)
 Calcul facile et rapide (plus rapide que le cryptage symétrique).
Fonction de hachage
Internet
Hashage =? Hashage
Empreinte Empreinte Empreinte
reçue recalculée
1) = Le texte reçu est intègre

Empreinte Empreinte
reçue recalculée
2) ≠ Le texte reçu est altéré

Empreinte Empreinte
reçue recalculée
84
Fonction de hachage
 Famille MD (Message Digest)
• Développé par Ron Rivest
• Plusieurs versions: MD4, MD5
• Génère une empreinte de taille 128 bits
 Famille SHA (Secure Hash Algorithm)
• Développé par NIST en collaboration avec NSA
• Plusieurs versions SHA1, SHA2, SHA3
• SHA1 Génère une empreinte de taille 160 bits
• Exemple
Introduction à la Cryptographie
5aa769e719f153611c3d0dbb4bb02e23
Introduction à la cryptographie
af575f3a9216b4158bdcd2c4201d6527
Signature numérique
 Idée clé:
• L’empreinte (résultat de la fonction de hachage) d’un
message est crypté avec la clé privée de l’émetteur.
• La clé publique est utilisée pour la vérification de la
signature
 Soit:
• M: message à signer, H: fonction de hachage
• Kpr, Kpu: paire de clés privée / publique de l’émetteur.
• E / D: fonction de cryptage / Décryptage en utilisant
Kpu / Kpr.
 En recevant (M, EKpr(H(M))), le récepteur
vérifie si: H(M)=DKpu(EKpr(H(M)))

Signature numérique: Création
Clé privée
du signataire
Texte clair Signature

Hashage Cryptage
Électronique
Empreinte
Processus de Création de la Signature

Électronique
87
Signature numérique: Vérification
Texte clair Hashage

Empreinte
recalculée
Clé publique
=?
de l’émetteur
Signature Décryptage
Electronique
Empreinte
reçue
1) = La signature reçue est correcte

Empreinte Empreinte
reçue recalculée
2) ≠ La signature reçue est incorrecte

Empreinte Empreinte
reçue recalculée
88
89
• La signature permet de mettre en œuvre

les services:
• Intégrité du message
• Authentification
• Non-répudiation
• Génération d’une clé de chiffrement
symétrique pour le service de Confidentialité

Exemples d’algorithmes:
 Signature RSA
 Digital signature Algorithm (DSA)
 Elliptic Curve Digital signature Algorithm

(ECDSA)
Signature RSA
 Pour signer un message m ∈ P, A doit calculer:

h = H (m), avec H une fonction de hachage
s = h d mod n
• La signature de m calculée par A est s
 Pour vérifier la signature de A, B doit:

• Obtenir la clé publique de A (n, e)
• Calculer: h1 = s e mod n
• Calculer: h = H (m)
• Vérifier si h = h1 , sinon la signature est rejetée
92
DSA
• Le NIST a proposé le DSA « Digital Signature algorithm »
en 1991 et l'a adopté comme norme en 1994.
• Il est connu aussi avec le nom Digital Signature Standard
(DSS).
Génération de Clés
 Sélectionner deux nombre premiers (p,q) telque q | (p-1)
 Il est recommandé que le nombre de bits de p soit entre
512 and 1024 bits, et q de 160 bits
 Choisir g comme un élément de Zp* avec un ordre q
• Soit α un générateur de Zp*, et définir g = α(p-1)/q mod p
 Sélectionner 1 ≤ x ≤ q-1 et calculer y = gx mod p
Clé publique: (p, q, g, y)

Clé privée: x
DSA
Signer un message M:
 Sélectionnez un nombre aléatoire secret
k, 0 < k < q
 Calculer:
r = (gk mod p) mod q
s = k-1 ( H(M) + xr) mod q
H est une fonction de hachage
 Signature: (r, s)
• La signature se compose de deux nombres de
160 bits, lorsque q est de 160 bits

DSA
Vérification de signature
 Vérifier 0 < r < q and 0 < s < q, sinon, la
signature est invalide.
 Calculer:
u1 = H(M)s-1 mod q, u2 = rs-1 mod q
w= (gu1 yu2 mod p) mod q
 La signature est valide si r = w
ECDSA
 ECDSA - Elliptic Curve Digital Signature Algorithm

Génération de signature :
Pour signer un message m par l’émetteur A, en utilisant dA la clé privée
de A et QA = dA * G la clé publique de A.
1. Calculer e = H (m), avec H une fonction de hachage, comme SHA-1

2. Selectionner un nombre aléatoire k de [1,n − 1] avec n est l’ordre de G
3. Calculer r = x1 (mod n), avec (x1, y1) = k * G. Si r = 0, revenir à l’étape 2
4. Calculer s = k − 1(e + dAr)(mod n). Si s = 0, revenir à l’étape 2
5. La signature est la paire (r, s)

ECDSA
Vérification de signature
Pour que B authentifie la signature de A , B doit avoir la clé publique de A
QA
1. Vérifier que r et s appartiennent à [1,n − 1]. Sinon, la signature est
invalide
2. Calculer e = H(m), avec H est la même fonction utilisée dans la
génération de la signature
3. Calculer w = s −1 (mod n)
4. Calculer u1 = ew (mod n) et u2 = rw (mod n)
5. Calculer (x1, y1) = u1G + u2QA
6. La signature est valide si x1 = r(mod n)

Chapitre 2 Cryptographie

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre 2 Cryptographie

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Chapitre 2 Cryptographie

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre 2: La cryptographie

Fondements de sécurité, 2021 2

Fondements de sécurité, 2021 3

Fondements de sécurité, 2021 4

Fondements de sécurité, 2021 5

Fondements de sécurité, 2021 6

Fondements de sécurité, 2021 7

Caractéristiques d’un cryptosystème

Canal non sécurisé

Canal non sécurisé

Fondements de sécurité, 2021 8

Fondements de sécurité, 2021 9

• C = El1 ( x1 ) El2 ( x2 )...

 NIST définit plusieurs modes d’opérations:

Fondements de sécurité, 2021 11

 Principes et méthodes permettant de trouver un message

Fondements de sécurité, 2021 12

Fondements de sécurité, 2021 13

Clé Texte crypté= Clé

Texte clair Texte clair

Fondements de sécurité, 2021 14

Fondements de sécurité, 2021 15

Fondements de sécurité, 2021 16

Fondements de sécurité, 2021 17

Chiffrement par substitution simple

E.g.: Plaintext: bob. how are you. alice

Fondements de sécurité, 2021 18

Fondements de sécurité, 2021 19

Exemple de cryptage par substitution simple

• Ainsi, la lettre F d’un message crypté

Fondements de sécurité, 2021 21

Chiffrement par substitution polyalphabétique

THIS CIPHER IS NOT CERTAINLY SECURE

Fondements de sécurité, 2021 22

Fondements de sécurité, 2021 23

Chiffrement par substitution polyalphabétique

Fondements de sécurité, 2021 24

 L'idée de Vigenère est d'utiliser un code de César, mais où le

• A chaque lettre on additionne les deux rangs et on prend le

Fondements de sécurité, 2021 25

Fondements de sécurité, 2021 26

 Au lieu d'associer un seul caractère

Fondements de sécurité, 2021 27

Fondements de sécurité, 2021 28

Rail fence technique

Fondements de sécurité, 2021 29

Opérations algébriques simples

Fondements de sécurité, 2021 30

Fondements de sécurité, 2021 31 31

La sécurité d’un système cryptographique ne doit pas reposer sur

Fondements de sécurité, 2021 32

Fondements de sécurité, 2021 33

Fondements de sécurité, 2021 34

 Les grandes lignes de l'algorithme sont les suivantes :

Fondements de sécurité, 2021 35

2. Permutation initiale des blocs (IP)

Fondements de sécurité, 2021 36

Fondements de sécurité, 2021 37

Fondements de sécurité, 2021 38