Module: Sécurité Informatique
Chapitre II: Cryptographie
LfSI3
Nour BRINIS
[Link]@[Link]
1 / 23
K
Plan du chapitre
1. Introduction
2. Définitions
3. Cryptographie classique
4. Chiffrement par blocs: DES, AES
2
Introduction
● Depuis la nuit des temps les hommes, surtout les militaires,
ont pratiqué l’espionnage et le contre-espionnage
● Le chiffrement des messages est donc né presque en même
temps que l’écriture
● La cryptologie est la science des messages secrets et des
codes chiffrés utilisée traditionnellement par les militaires et
les gouvernements: Il s’agit d’une science mathématique
comportant deux branches : la cryptographie et la
cryptanalyse.
3
Définitions
● Cryptographie : Ensemble des principes, méthodes et
techniques dont l’application assure le chiffrement et le
déchiffrement des données, afin d’en préserver la
confidentialité et vérifier l’intégrité des messages
échangés:
Outil important de la politique de sécurité
● Cryptanalyse: Ensemble des méthodes et procédés de
décryptage visant à rétablir en clair un cryptogramme,
sans connaissance préalable de la clé de chiffrement
4
Définitions – protocole de chiffrement
5 / 23
K
Définitions
Chiffrement : Le chiffrement consiste à transformer une donnée
(texte, message, ...) afin de la rendre incompréhensible par une
personne autre que celui qui a créé le message et celui qui en est
le destinataire. La fonction permettant de retrouver le texte clair à
partir du texte chiffré porte le nom de déchiffrement.
Texte chiffré : Appelé également cryptogramme, le texte chiffré
est le résultat de l’application d’un chiffrement à un texte clair.
Clef : Il s’agit du paramètre impliqué et autorisant des opérations
de chiffrement et/ou déchiffrement. Dans le cas d’un algorithme
symétrique, la clef est identique lors des deux opérations. Dans le
/ 23 d’algorithmes asymétriques, elle diffère pour les deux
6cas
K
opérations.
Définitions
● Cryptosystème : Il est défini comme l’ensemble des clés
possibles (espace de clés), des textes clairs et chiffrés
possibles associés à un algorithme donné
7
Définitions
Un cryptosystème est un quintuplait (M,C,K,E,D)
- M l’ensemble des textes clairs possibles
- C l’ensemble des textes chiffrés
- K l’ensemble des clés
- E l’ensemble des fonctions de chiffrement
- De la forme ek,k ∈ K,t.q ek(m) ∈ C
- D l’ensemble des fonctions de déchiffrement
- De la forme dk,k ∈ K, t.q dk(ek(m)) = m
8
Qualités d’un cryptosystème
● Trois qualités recherchées :
– Confusion : Aucune propriété statistique ne peut être
déduite du message chiffré ⇒ message inintelligible
– Diffusion : Toute modification du message en clair se
traduit par une modification complète du chiffré
– Robustesse de la clé : Difficile de déterminer k (difficile
également d’énumérer tous les k)
Le système de chiffrement moderne ne doit pas dépendre du
secret de l’algorithme mais seulement du secret de la
clé.(Kerchoff 1883)
9
Cryptanalyse
● Afin de briser un code secret et obtenir ainsi les textes
en clair, l’attaquant à diverses possibilités :
– Attaques passives : par écoute électronique, l’attaquant
obtient une copie de tous les textes chiffrés échangés
entre les intervenants
– Attaques actives : l’attaquant joue un rôle actif lors du
protocole et peut altérer ou détruire des messages
10
Exemple d’attaque célèbre
La bataille de Midway Juin 1942,
Américains vs Japonais
L’attaque :
Les américains ont envoyés un faux message en clair entre deux de
leurs postes
Ils ont attendu que les Japonais l’interceptent Et qu’ils le
retransmettent chiffré à leur état major!
Les américains ont disposé d’un couple (m,ek(m))
et ont pu en déduire k
11 / 23
K
Chiffrement symétrique
Ce chiffrement nécessite un procédé rigoureux convenu
auparavant entre les parties cryptographie à clé secrète :
Les deux acteurs s’échangent une clé secrète (mot de passe)
La sécurité du chiffrement dépend de la non divulgation
de cette clé
12 / 23
K
Cryptographie classique
Chiffrement par transposition
Chiffrements monoalphabetiques
Chiffrements polyalphabétiques
Chiffrement de Vernam
13 / 23
K
Chiffrement par transposition
Chiffrement de type anagramme
Les lettres du messages sont déplacées
Exemple:
"col" ne peut se transformer qu’en "col", "clo", "ocl", "olc",
"lco" et "loc"
Niveau de sécurité théorique;
Message de n lettres : n! chiffrés possibles
Une transposition rectangulaire consiste à écrire le message
dans une grille rectangulaire, puis à arranger les colonnes de
cette grille selon un mot de passe donné
14 / 23
K
Exemple
On a choisi comme clé GRAIN pour chiffrer le message
SALUT LES PETITS POTS. En remplissant la grille, on
constate qu’il reste deux cases vides, que l’on peut remplir
avec des nulles (ou pas, selon les désirs des correspondants).
15 / 23
K
Chiffrement par transposition
La transposition simple consiste à:
Ecrire le texte à chiffrer longitudinalement sur une bandelette
enroulée.
Le message, une fois déroulé, n'est plus compréhensible
Exemple: « comment ça marche » est cryptée en « cecaeonar mt
c m mh »).
Il suffit au destinataire d'avoir un cylindre de même diamètre
pour pouvoir déchiffrer le message. En réalité un casseur peut
déchiffrer le message en essayant des cylindres de diamètre
successifs différents, ce qui revient à dire que la méthode peut
K
16 / 23 être cassée statistiquement
Chiffrement monoalphabétique
C’est une application bijective des lettres de l’alphabet vers
les lettres de l’alphabet. Appelée aussi permutation.
Niveau de sécurité théorique: Alphabet à 26 lettres : 26!
alphabets possibles
Chiffrement de César :
défini en décalant l’alphabet de trois lettres.
Par exemple, le mot « message » est crypté « PHVVDJH ».
On peut généraliser le chiffrement de César en changeant la
valeur de 3 par une valeur entière entre 1 et 26.
L’ensemble de cette famille d’algorithmes est appelée chiffrement
additif
17 / 23
K
Chiffrement monoalphabétique
Chiffrement multiplicatif :
Au lieu d’ajouter une valeur au code clair, on le multiplie par
une valeur et on calcule le modulo 26. x→t.x mod 26
Les valeurs de t acceptables doivent vérifier que pgcd (t,26)=1
sinon la décomposition n’est pas unique!
Le déchiffrement se fait par la division euclidienne. Trouver u tel
que ut=1 mod 26.
Le clair=c.u mod 26
Chiffrement affine:
Réalise une combinaison entre le chiffrement additif et
multiplicatif.
x→ (x.t + s ) (mod 26)
18 / 23
K La clé de chiffrement est la paire (t,s)
Chiffrement monoalphabétique
Chiffrement par mot clé:
On choisit un mot clé et une position de départ.
Le mot clé ne doit pas contenir de lettres qui se répètent
L’alphabet est substitué par la clé à la position de départ puis le
reste de l’alphabet
Exemple : mot clé hirondelle à la position 5
A B C D E F G H I J K L M N O P Q R S T U V WX Y Z
WX Y Z H I R O N D E L A B C F G J K M P Q S T U V
19 / 23
K
Chiffrement monoalphabétique -
Cryptanalyse
Le point commun de ces chiffrements est qu’ils se basent sur
la substitution d’une lettre par une autre lettre.
Faiblesse: une même lettre est toujours crypté de la même
façon: EX
L’analyse fréquentielle est une méthode de cryptanalyse
qui consiste à examiner la fréquence des lettres employées
dans un message chiffré.
L’analyse fréquentielle est basée sur le fait que, dans chaque
langue, certaines lettres ou combinaisons de lettres
(bigrammes) apparaissent avec une certaine fréquence. Par
exemple, en français, le e est la lettre la plus utilisée, suivie du
20 / 23 s et du a. Inversement, le w est peu usité.
K
Chiffrement monoalphabétique -
Cryptanalyse
Lettre Fréquence Lettre Fréquence
• Attaque statistique: A 8.40 % N 7.13 %
• Dans le texte crypté, on cherche la B 1.06 % O 5.26 %
lettre que apparaît le plus C 3.03 % P 3.01 %
• Cela devrait être C(E) D 4.18 % Q 0.99 %
• La lettre qui apparaît ensuite devrait E 17.26 % R 6.55 %
F 1.12 % S 8.08 %
être C(A)
G 1.27 % T 7.07 %
• Puis C(S) …
H 0.92 % U 5.74 %
Message initiale sous forme de texte à
I 7.34 % V 1.32 %
trous (il faut deviner les lettres
J 0.31 % W 0.04 %
manquantes)
K 0.05 % X 0.45 %
L 6.01 % Y 0.30 %
M 2.96 % Z 0.12 %
21 / 23
K
Chiffrement monoalphabétique -
Cryptanalyse
Exemple de cryptanalyse:
Tentons de déchiffrer
23 / 23
K
Chiffrement polygraphique
Il s’agit ici de chiffrer un groupe de k lettres par un autre
groupe de k autres lettres (chiffrement par bloc).
Chiffrement Vigenère:
L’algorithme se base sur une clé (suite de lettres de longueur k)
et effectue une substitution en fonction de la lettre
correspondante de la clé.
Chiffrement: Additionner à chaque lettre la lettre de la clé.
Déchiffrement : retirer le code de la lettre de la clé de la lettre
du cryptogrammes
Exemple : Clé=« ac », k=2
24 / 23
K
Chiffrement polygraphique
Exemple: « paiement annulé » avec la clé cake
p a i e m e n t a n n u l e
c a k e c a k e c a k e c a
16 1 9 5 13 5 14 20 1 14 14 21 12 5
3 1 11 5 3 1 11 5 3 1 11 5 3 1
19 2 20 10 16 6 25 25 4 15 25 26 15 6
s b t j p f y Y d o y z o f
25 / 23
K
Chiffrement polygraphique- Cryptanalyse
Faiblesse: deux lettres x qui sont situées à la même position
dans deux blocs différents sont cryptées par la même lettre!!
M A |M I (clé = AC) ND|NL
La cryptanalyse de l’algorithme de Vigenère se base sur:
1. la recherche de séquences qui se répètent pour déterminer la
longueur de la clé.
2. Application de l’analyse statistique pour déterminer le texte
clair.
26 / 23
K
Chiffrement polygraphique- Cryptanalyse
On trouve :
UMQI se retrouve après 30 caractères
OIGR se retrouve après 25 caractères
JIGRY se retrouve après 30 caractères
La longueur de la clé doit être un diviseur de 30 et de 25 : il est
possible qu’il s’agisse de 5
Ecrire en bloc de 5 et appliquer une analyse statistique
27 / 23
K
Chiffrement de Vernam
C’est un système de chiffrement utilisant une clé de même taille
que le message clair. La clé est utilisée une seule fois puis jetée
(masque jetable!). La clé est une séquence binaire aléatoire
qu’on fait en ou exclusif avec le message clair:
C=MK
( : xor, K: clé secrète, M: message clair, C: message crypté)
L’algorithme est formellement sûr, Cryptanalyse possible
uniquement si Mot-clé trivial
Mais très difficile de mettre en pratique surtout pour la
gestion de clés longues, parfaitement aléatoires stockées en
un lieu sûr et échangées entre les intervenants.
28 / 23
K
Algorithme DES
(Data Encryption Standard)
Historique :
Milieu des années 70
Premier algorithme de chiffrement pour l’industrie, utilisé pour
le chiffrement des mots de passe sous UNIX
Principe :
Entrées : Un message de 64 bits et une clé de 56 bits
Sorties : Un cryptogramme de 64 bits
Principe:
DES produit de transpositions et substitutions nombreuses et
compliquées pour une clé relativement courte.
Les chiffres à substitution et à transposition sont faciles à
29 / 23
réaliser en matériel.
K
Algorithme DES
(Data Encryption Standard)
Boîte de transposition(P - box "Permutation box"):
Exemple pour 8 bits:
Facile à réaliser par simple câblage
30 / 23
K
Algorithme DES
(Data Encryption Standard)
Boîte de substitution(S - box)
Exemple de solution matérielle pour 3 bit
Trois bits sélectionnent un fil en sortie-
L'ensemble subit une transposition.
K
31 / 23 Le résultat est remultiplexé sur 3 bits
Algorithme DES
(Data Encryption Standard)
1. Permutation Initiale (IP) donnant un message M’
2. M’ est divisé en 2 mots de 32 bits.L0 et R0.
3. Réaliser 16 itérations de la fonction f qui combine des
substitutions et des transpositions
4. Li=Ri-1
5. Ri=Li-1 f(Ri-1,Ki)
4. f est une fonction qui prend comme entrée les 32 bits de
la partie droite et la clé du tour. Elle est définie en
utilisant 8 permutations appelées S-boxes. La clé de tour
contient un sous-ensemble de la clé. Le cryptogramme C’
subit la transformation inverse de IP et donne le
K
32 / 23 cryptogramme final.
Algorithme DES
(Data Encryption Standard)
5. La fonction f commence par étendre les 32 bits de Ri-1 en
48 bits. Ensuite, un xor est effectué avec la clé de tour. On
divise le résultat ensuite en 8 blocs de 6 bits dénotés
B1,…,B8.
6. Chaque Bj est ensuite utilisé comme input de la fonction
de substitution S-BOX Sj,qui renvoie un bloc de 4 bits en
sortie Sj(Bj).
33 / 23
K
34 / 23
K
Algorithme DES
(Data Encryption Standard)
Avantages
Rapide Puces dédiées au DES
Facile à implémenter en hard (cartes à puce)
Inconvénients
Taille de la clé (56 bits)
Méthodes pour casser la clé :
Attaque exhaustive
Cryptanalyse linéaire
Cryptanalyse différentielle
35 / 23
K
Algorithme AES
(Advanced Encryption Standard)
Historique:
Rijndael - AES ou Rijndael, nom résultant de la contraction des
noms de ses inventeurs : Rijmen et Deamen
Principe:
l'AES est un standard, libre d'utilisation, sans restriction d'usage
ni brevet.
c'est un algorithme de type symétrique (comme le DES)
c'est un algorithme de chiffrement par blocs (comme le DES)
il supporte différentes combinaisons [longueur de clé]-[longueur
de bloc] : 128-128, 192-128 et 256-128 bits (en fait, Rijndael
supporte également des tailles de blocs variables, mais cela n'est
pas retenu dans le standard)
36 / 23
K
Algorithme AES
(Advanced Encryption Standard)
Algorithme:
L'AES opère sur des blocs de 128 bits (plaintext P) qu'il
transforme en blocs cryptés de 128 bits (C) par une séquence de
Nr opérations ou "rounds", à partir d'une clé de 128, 192 ou
256 bits. Suivant la taille de celle-ci, le nombre de rounds
diffère : respectivement 10, 12 et 14 rounds.
Le schéma suivant décrit succinctement le déroulement du
chiffrement :
BYTE_SUB (Byte Substitution) est une fonction non-linéaire
opérant indépendamment sur chaque bloc à partir d'un table
dite de substitution.
37 / 23
K
Algorithme AES
(Advanced Encryption Standard)
SHIFT_ROW est une fonction opérant des décalages
(typiquement elle prend l'entrée en 4 morceaux de 4 octets et
opère des décalages vers la gauche de 0, 1, 2 et 3 octets pour les
morceaux 1, 2, 3 et 4 respectivement).
MIX_COL est une fonction qui transforme chaque octet
d'entrée en une combinaison linéaire d'octets d'entrée et qui
peut être exprimée mathématiquement par un produit marticiel
sur le corps de Galois (28).
le désigne l'opération de OU exclusif (XOR).
Ki est la ième sous-clé calculée par un algorithme à partir de la
clé principale K.
38 / 23
K
Algorithme AES
Le déchiffrement
consiste à appliquer les
opérations inverses, dans
l'ordre inverse et avec
des sous-clés également
dans l'ordre inverse.
39 / 23
K
Chiffrement asymétrique –
Limites du chiffrement symétriques
Il faut pouvoir communiquer la clé secrète par un moyen sûr.
Pas très pratique
Nombre de clés à échanger pour communiquer entre n
personnes : n*(n-1)/2
40 / 23
K
Chiffrement asymétrique
La cryptographie à clé publique ou asymétrique est basée sur
un concept très différent de la cryptographie symétrique
Chaque intervenant possède une clé publique
Cette clé peut être connue de tous. Par exemple, disponible
dans un répertoire accessible publiquement, sur internet
Toute personne connaissant cette clé peut envoyer un message
chiffré au propriétaire de cette clé
Chaque intervenant possède une clé privée
Cette clé doit demeurer confidentielle
Cette clé est liée (mathématiquement) à la clé publique
correspondante
Cette clé permet de déchiffrer tout message chiffré avec la clé
41 / 23
K publique correspondante
Chiffrement asymétrique
Métaphore du cadenas
Facile à fermer
Nécessite une clé pour ouvrir
42 / 23
K
Chiffrement asymétrique
Avantages :
Si N intervenants veulent s’échanger des informations sans
l’aide d’un tiers, chaque intervenant doit avoir une clé publique
unique connue de tous
Donc, N clés sont suffisantes
Les clés publiques doivent être distribuées de façon authentifiée,
mais non confidentielle
Seule la clé publique est divulguée
Connaître la clé publique d’un intervenant ne permet pas de déchiffrer ses
messages
43 / 23
K
Chiffrement asymétrique
La cryptographie à clé publique est basée sur des problèmes
mathématiques difficiles à résoudre
Factorisation - problème RSA
Logarithme discret - problème Diffie Hellman
De ces problèmes, on extrait des fonction à sens unique à
brèche secrète
Calculer f (x) est facile (f =clé publique, x=message)
Calculer f−1(x) est difficile
Calculer f−1(x) sachant k est facile (k=clé privée, k est la
brèche)
44 / 23
K
Cryptosystème RSA
Chiffrement à clé publique le plus utilisé
Créé en 1977 par Rivest, Shamir et Adleman
Breveté par le MIT en 1983 aux états-Unis.
Utilisé dans :
Les banques
Les cartes à puce
Les site webs commerciaux
45 / 23
K
Chiffrement RSA
Problème difficile: factoriser un entier produit de deux
nombres premiers distincts
Clé publiques et clé sécrète: calculées à l’aide de l’algorithme
d’Euclide et des coefficients de Bézout
Environnement: calculs modulo un entier
Déchiffrement: possible grâce au théorème de Fermat
MrX veut envoyer un message à MrY
MrY prépare une clé publique et une clé privée
MrX utilise la clé publique de MrY pour crypter son message.
MrY reçoit le message crypté et le déchiffre grâce à sa clé
46 / 23
K privée.
Chiffrement RSA
Etape1: préparation des clés
1.1 Choix de deux nombres premiers
MrY effectue les opérations suivantes
Choix de nombres premiers distincts p et q (dans la pratique ce
sont de très grand nombres)
Calcul de n=p*q
Calcul de φ (n)=(p-1)*(q-1)
Application:
p=5 et q=17
n=p*q=85
φ(n)=(p-1)*(q-1)=φ (n)=64
47 / 23
K
Chiffrement RSA
1.2 choix d’un exposant et calcul de son inverse:
MrY choisit un exposant e tel que pgcd(e,φ(n))=1,
MrY calcule l’inverse d de e modulo φ(n):d×e≡1(modφ(n)).
Ce calcul se fait par l’algorithme d’Euclide étendu.
Application:
MrY choisit par exemple e=5 et on a bien
pgcd(e,φ(n))=pgcd(5, 64)=1,
MrY applique l’algorithme d’Euclide étendu pour calculer les
coefficients de Bézout correspondant à pgcd(e,φ(n))=1. On
trouve 5×13+64×(−1)=1. Donc 5×13≡1(mod 64) et
48 / 23
K l’inverse de e modulo φ(n) est d=13.
Chiffrement RSA
1.3 Clé publique
La clé publique de MrY est constituée des deux nombres :
n et e
Application: n=85 et e=5
1.4 Clé privée:
MrY garde pour lui sa clé privée
d
Application : d=13
49 / 23
K
Chiffrement RSA
Etape2: Chiffrement du message
MrX veut envoyer un message secret à MrY. Il se débrouille
pour que son message soit un entier (quitte à découper son
texte en bloc et à transformer chaque bloc en un entier).
2.1 Message
Le message est un entier m, tel que 0≤m<n.
Application: MrX veut envoyer le message m=10.
50 / 23
K
Chiffrement RSA
2.2 Message chiffré
MrX récupère la clé publique de MrY :n et e avec laquelle il
calcule, à l’aide de l’algorithme d’exponentiation rapide, le
message chiffré :
x≡me(mod n)
Il transmet ce message x à MrY
Application: m=10,n=85 et e=5
102≡100≡15(mod 85)
x≡me(mod n)≡105(mod 85) 104≡(102)2≡152≡225≡55(mo
d 85)
x≡105≡104×10≡55×10≡550
Le message chiffré est donc x=40
51 / 23 ≡40(mod 85)
K
Chiffrement RSA
Etape 3 : Déchiffrement:
MrY reçoit le message x chiffré par MrX, Il le décrypte à
l’aide de sa clé privée d, par l’opération :
m≡xd(mod n)
qui utilise également l’algorithme d’exponentiation rapide.
Application: c=40,d=13,n=85 donc xd≡(40)13(mod 85).
Donc xd≡4013≡10(mod 85) Calculons à la main 4013≡(mod 85)
on note que 13=8+4+1, donc
qui est bien le message m de MrX.
4013=408×404×40.
402≡1600≡70(mod 85)
404≡(402)2≡702≡4900≡55(mod 85)
52 / 23 408≡(404)2≡552≡3025≡50(mod 85)
K
4013≡ ≡50×55×40≡ 10(mod 85)
Chiffrement RSA
Récapitulatif:
MrX MrY
Exercice
p=7;q=17 e=13
Chiffrer le message 10 11 12 13
Vérifier le déchiffrement
53 / 23
K
p=7;n=77 e=13
Chiffrer le message 10 11 12 13
Vérifier le déchiffrement
Q=11
phi-(n)=6*10=60
⇒ 13*d=1 mod 60
Trouve d?
d=-23, 37, d*e=1modp
u*13 +v 60= 1 (-23*13+5*60=1)
+ 10^13 mod 77=10;
K
54 / 23 10^d mod 77
55 / 23
K
Lemme de déchiffrement
Le principe de déchiffrement repose sur le théorème de
Fermat amélioré.
Soit d l’inverse de e modulo φ(n).Si x≡me(mod n)alors
m≡xd(mod n).
Ce lemme prouve bien que le message original m de MrX,
chiffré par clé publique de MrY (e,n) en le message x, peut-
être retrouvé par MrY à l’aide de sa clé secrète d.
56 / 23
K
Cryptosystème Diffie Hellman
Pas un protocole de chiffrement,
mais un protocole d’échange de clé Basé sur le problème
Logarithme Discret
Objectif : A et B veulent s’échanger une information connue
d’eux seuls
57 / 23
K
Cryptosystème Diffie Hellman
Le problème Diffie Hellman :
Entrées :
Un entier premier p
Un générateur g de Zp*
Deux entiers gk1 mod p et gk2 mod p
Sortie : l’entier gk1*k2 mod p
Fonction à sens unique et à brèche secrète (k1,k2)
58 / 23
K
Cryptosystème Diffie Hellman
1. Soit p un grand nombre premier et g un générateur de Zp*
2. A et B se mettent d’accord sur p et g
3. A choisit un entier k1 et calcule gk1 mod p
4. A envoie gk1 mod p à B
5. B choisit un entier k2 et calcule gk2 mod p
6. B envoie gk2 mod p à A
7. A calcule (gk2 mod p)k1 mod p = gk1*k2 mod p
8. B calcule (gk1 mod p)k2 mod p = gk1*k2 mod p
9. La clé échangée est :
a = gk1*k2 mod p
59 / 23
K
Cryptosystème Diffie Hellman
g=4 6= 4k1mod10 k1?
p=10
4= 6k2mod10 k2?
x=4
y=6
y
MrX x MrY
k1=2 g=4 k2=3
g=4
x =gk1 mod p
p=10 y=gk2 mod p
p=10 y=4 =43modp=4
x=6 =42mod10 =6 x=6
y=4 a=yk1 mod p a=6 a=xk2 mod p
a=6
60 / 23
= 42mod10 = 63mod10
K =6 =6
Cryptosystème Diffie Hellman
Exemple:
A et B partagent p= 233 et g= 45
si A choisit k1= 11 et B choisit k2= 20
Quelle est leur clé secrète commune?
gk1= 4511mod 233 = 147,gk2= 4520mod 233 = 195,
(gk1)k2modp= 14720mod 233 = 169
(gk2)k1modp= 19511mod 233 = 169
A et B disposent d’une clé privée commune :k= 169
61 / 23
K
Chiffrement d’El Gamal
Algorithme de cryptographie asymétrique.
Problème difficile: basé sur les logarithmes discrets.
3xmod8 = 1 x? (x=4)
Encore plus difficile et moins rapide pour les grandes valeurs.
Il a été créé par Taher El Gamal en 1985.
62 / 23
K
Chiffrement d’El Gamal
Etape1: Génération des clés:
MrY fait les opérations suivantes:
Choix d’un nombre premier p.
Ensuite, choix de deux entiers a et g tels que
0≤a≤p−2 et 0≤g≤p−1
On pose alors n≡ga mod p
La clé publique sera le triplet (p,g,n) (partagé)
et la clé secrète sera l'entier a (gardé chez MrY).
Application:
Soit p=661. MrY choisit a=7 et g=23.
On a : n≡ga mod p ≡237 mod 661≡566 mod 661
63 / 23
la clé publique est donc le triplet (661,23,566)
K
la clé secrète l'entier 7.
Chiffrement d’El Gamal
Etape2: Chiffrement du message
On convertit de la même façon que RSA le message à chiffrer
en une suite de chiffres, telle que la valeur numérique de
chaque bloc doit être inférieure à p.
Soit (p,g,n)une clé publique.
On commence par choisir un entier k aléatoirement tel que
0≤k≤p−1.
Un bloc de chiffres m du message d'origine tel que m<p sera
alors chiffré par un couple de blocs de chiffres (u,v):
u≡gk mod p,
v≡m*nk mod p
64 / 23
K
Chiffrement d’El Gamal
Le message chiffré sera donc une suite de couples de blocs de
chiffres. On perçoit ici l'un des défauts de cet algorithme, le
message chiffré est deux fois plus long que le message d'origine.
Application :
On reprend la clé publique (p,g,n)=(661,23,566).
Cherchons à chiffrer le message 192.
On choisit aléatoirement l'entier k=13
m=192 est alors chiffré en (105,237)
u≡2313 mod 661≡105 mod 661 etv≡192×56613mod 661≡237 mod 661
65 / 23
K
Chiffrement d’El Gamal
Etape 3 : Déchiffrement:
Soit (p,g,n) une clé publique et a la clé secrète
correspondante.
Un couple de blocs de chiffres (u,v) du message chiffré
correspondra au bloc de chiffres m du message d'origine:
m≡u−a*v mod p= up-1-a*v mod p
Application:
(p,g,n)=(661,23,566) et a=7.
Déchiffrons donc le message (105,237)
x≡ 105−7×237 mod 661 =105661−1−7×237 mod 661≡192 mod
661=m. Ce qui correspond bien au message d’origine
66 / 23
K
Soit p= 541,g= 2,a= 113et k= 101. Crypter x= 200 en
utilisant El Gamal.
Sol: (68,534)
67 / 23
K
Chiffrement d’El Gamal
Exercice :
On veut transmettre le message m=1299.
Les paramètres publics sont p=2579, g=2,n=949
on choisit k=853
Chiffrer y1=435, y2=2396
Trouver le message clair.
68 / 23
K
