Questions de cours
.
Exercice 1 : Substitution monoalphabétique : Chiffre de césar (50 av. j-c) (3.5pts)
Ils s’agissent d’un des plus simples et des chiffres classiques les plus populaires. Son principe est un décalage des lettres de l’alphabet. Dans les formulaires ci-dessous, p est l’indice de la lettre de l’alphabet, k est le décalage. Pour le chiffrement, on aura la formule C=E(p) = (p + k) mod 26.
1) Donner l’expression de la formule de déchiffrement P= D(c)
P=D(C) = (c - k) mod 26
2) Quel est le nombre de clés possibles dans le chiffre de césar ?
Seules 25(!) clés sont possibles.
3) A parti de votre réponse à la question 2) expliquer pourquoi la cryptanalyse par force brute est très facile dans le chiffre de césar.
Les clés sont de petite taille et le nombre de clés possible est très faible
4) Expliquer le principe de la cryptanalyse par analyse de fréquences. Dans quelle condition cette technique fonctionne bien ?
4.1. On exploite les régularités du langage par le principe d’analyse de la fréquence d’une lettre
4.2. Cette technique ne fonctionne bien que si le message chiffre est suffisamment long pour avoir des moyennes significatives.
5) Présenter deux moyens pour éviter les attaques (par force brut ou par analyse de fréquences) sur un texte chiffrer.
5.1. On peut par exemple chiffrer le message par digramme, trigramme, etc.
5.2. On peut également utiliser des homophones : Ils d’agit de remplacer une lettre non pas par symbole unique, mais, par symbole choisis au hasard parmi plusieurs.
EXERCICE 2 : Substitution polyalphabétique : Chiffre de Vigenere (1568)
1) Donner le texte chiffré
|
Texte clair
|
C
|
H
|
I
|
F
|
F
|
R
|
E
|
|
clef
|
B
|
A
|
C
|
H
|
E
|
L
|
I
|
|
Décalage
|
1
|
0
|
2
|
7
|
4
|
11
|
8
|
|
Texte chiffré
|
D
|
H
|
K
|
M
|
J
|
C
|
M
|
2) Le chiffre de césar utilise un alphabet. Le chiffre de vigenère utilise combien d’alphabet ?
26 alphabet décalé pour chiffré un message. On parle de carré de vigenère. Ce chiffre utilise une clef qui définit le décalage pour chaque lettre du message
3) Le chiffre de vigenère peut-il résister à une attaque de type analyse de fréquences ? Justifier votre réponse.
Oui, le chiffre de vigenère peut-il résister à une attaque de type analyse de fréquence. La grande force du chiffre de vigenère est que la même lettre sera chiffrée de différentes manières d’où perte de la fréquence des lettres, ce qui rend inutilisable l’analyse de fréquence classique.
4) Expliquer comment procéder pour que le chiffre de vigenère résiste à une attaque de type force brute.
Il faut utiliser des clés de très grande tailles.
5) Expliquer le principe de cryptanalyse de Kasiski.
Cette technique consiste à chercher des séquences de lettre qui apparaissent plus d’une fois dans le texte. En effet, dans ce cas, il n’y aura que deux possibilités :
- Soit la même séquence de lettre clair a été chiffrée avec la même partie de clef
- Soit deux suites de lettre différentes dans le texte clair auraient par coïncidence engendre la même suite dans le texte chiffré (probabilité faible).
6) Expliquer le principe de la cryptanalyse de Friedman.
Cette méthode utilise la notion d’indice de coïncidence (IC). Celui-ci est défini comme la probabilité que deux lettre choisis aléatoirement dans un texte soient identiques.
Exercice 3 : Le chiffrement par clés publique
1) Citer le problème sur lequel est base la méthode de chiffrement de El Gamal.
Consiste à retrouver un entier λ tel h = g λ mod p.
2) Même question qu’en 2) avec RSA.
Il est basé sur le calcul exponentiel. La sécurité d repose sur le cout pour factoriser de grands nombres.
3) Même question qu’en 2) avec Merkle-Hellman.
Il est basé sur la résolution du problème de sac au dos.
4) Chiffrement de Merkle-Hellman :
4.1.) Calculer la clé publique sur la base de la séquence super-croissante S = {1, 2, 4, 9} sachant que la valeur du multiplicateur n est 15 et la valeur du module m est 17.
1 * 15 mod 17 => 15
2 * 15 mod 17 => 13
4 * 15 mod 17 => 9
9 * 15 mod 17 => 16
Le havresac difficile est donc H = {15, 13, 9, 16}, et représente la clé publique.
4.2.) Effectuer le chiffrement de p = 0100101110100101 (0100 1011 1010 0101).
[0, 1, 0, 0] * [15, 13, 9, 16] => 13
[1, 0, 1, 1] * [15, 13, 9, 16] => 40
[1, 0, 1, 0] * [15, 13, 9, 16] => 24
[0, 1, 0, 1] * [15, 13, 9, 16] => 29
Le message chiffre est donc {13, 40, 24, 29} en utilisant le havresac public (la clef publique) H = [15, 13, 9, 16]