TD1: Cryptographie
Exercice 1 :
Lester Hill, mathématicien cryptographe (1891-1961) propose en 1929 un nouveau type d'algorithme de chiffrement. Son idée n'est plus de coder lettres par lettres, mais de coder simultanément des groupes de m lettres! Bien sûr, plus m est grand, plus les analyses statistiques deviennent difficiles!
D'abord, nous remplaçons chaque lettre par son ordre dans l'alphabet -1 : A devient 0, B devient 1,..., Z devient 25. On groupe les nombres ainsi obtenus par m (prenons par exemple m=2).
Pour chaque bloc de m nombres à coder x1x2...xm, on calcule le texte codé en effectuant des combinaisons linéaires (ici m=2) :
y1=ax1+bx2
y2=cx1+dx2
Si a,b,c,d sont des entiers, y1 et y2 seront aussi des entiers. Pourtant, si l'on souhaite les reconvertir en lettres, il faudrait qu'ils soient compris entre 0 et 25 ce dont on ne peut s'assurer. On les y ramène en prenant leur reste dans la division par 26. Si z1 et z2 sont les restes respectifs de y1 et y2 dans la division par 26, on peut retransformer z1 et z2 en lettres, et obtenir le message codé.
1. Codez le mot chiffrer avec le chiffre de Hill, pour m=2, a=3, b=5, c=1 et d=2.
1. Diviser le texte à coder en blocs de m lettres
2. Convertir les lettres en chiffres
3. Calculer les yi
4. Calculer les zi
5. Déduire le mot codé
2. Est-ce qu'une analyse de fréquence des lettres permet de casser ce code? Expliquez.
Exercice 2 :
On utilise les notations habituelles du RSA : p,q, n, ϕ(n), e et d
1. Donner les formules qui définissent les variables n, ϕ(n) et d en fonction d'une ou de plusieurs autres variables.
2. On chiffre un message m qui devient le message c en utilisant l’algorithme de chiffrement asymétrique RSA
1. Quelle est la formule de chiffrement ?
2. Quelle est la formule de déchiffrement ?
3. Quelles sont les valeurs qui doivent rester secrètes parmi n, p, q, ϕ(n), e, d ?
4. Quelles sont les valeurs publiques parmi n, p, q, ϕ(n), e, d ?
3. L'algorithme suivant est utilisé pour calculer la clé d.
Publicité
1. Pourquoi cet algorithme est-il applicable dans ce cas?
Dans RSA, on cherche à trouver d tel que: ϕ(n).u + e.d = 1
1. Faire correspondre les variables utilisées dans la définition de RSA et celles utilisées dans cet algorithme.
| | | | | | |
| --- | --- | --- | --- | --- | --- |
| Algo | a | b | x | y | d |
| RSA | ϕ(n) | e | u | d | 1 |
1. En appliquant l'algorithme, calculer d pour p=71, q=131 et e=3.
ϕ(n)=130\*70=9100
| | | | | | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| x | y | a | b | d | q | r | x1 | x2 | y1 | y2 |
| | | 9100 | 3 | 1 | | | 0 | 1 | 1 | 0 |
| 1 | -3033 | 3 | 1 | | 3033 | 1 | 1 | 0 | -3033 | 1 |
| -3 | 9100 | 1 | 0 | | 3 | 0 | -3 | 1 | 9100 | -3033 |
| 1 | -3033 | | | 1 | | | | | | |
ϕ(n).u + e.d = 1 ⇒ 9100\1+(-3033)\3=1
ϕ(n).u + e.d + e. ϕ(n) = 1 + e. ϕ(n) ⇒ e(d+ϕ(n)) -1 = ϕ(n).(e-u)
⇒ e(d+ϕ(n)) ≡ 1 mod ϕ(n)
(puisque si a ≡ b mod c, alors il existe un entier k tel que a – b = k.c)
d=6067
Une seconde méthode pour faire ce même calcul (exemple du cours):
soit p=
Exercice 3 :
Dans cet exercice, on considère l'analyse de fréquence, c'est-à-dire la méthode qui consiste à décrypter un texte chiffré en se basant sur l'étude statistique de l'apparition des caractères dans une langue.
Publicité
On considère le texte encrypté suivant :
qrznva, qrf y'nhor, n y'urher h oynapuvg yn pnzcntar,
wr cnegvenv. ibvf-gh, wr fnvf dhr gh z'nggraqf.
w'venv cne yn sberg, w'venv cne yn zbagntar.
wr ar chvf qrzrhere ybva qr gbv cyhf ybatgrzcf.
wr znepurenv yrf lrhk svkrf fhe zrf crafrrf,
fnaf evra ibve nh qrubef, fnaf ragraqer nhpha oehvg,
frhy, vapbaah, yr qbf pbheor, yrf znvaf pebvfrrf,
gevfgr, rg yr wbhe cbhe zbv fren pbzzr yn ahvg.
wr ar ertneqrenv av y'be qh fbve dhv gbzor,
av yrf ibvyrf nh ybva qrfpraqnag iref unesyrhe,
rg dhnaq w'neevirenv, wr zrggenv fhe gn gbzor
ha obhdhrg qr ubhk ireg rg qr oehlrer ra syrhe.
1. Remplir le tableau suivant avec les fréquences des lettres dans le texte.
| | | | | | | | | | | | | | | | | | | | | | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | ww | x | y | z |
| Fréquence | 30 | 25 | 9 | 4 | 40 | 33 | 26 | 33 | 6 | 0 | 3 | 2 | 0 | 37 | 8 | 9 | 15 | 68 | 4 | 4 | 6 | 34 | 10 | 0 | 21 | 15 |
| Rang | 7 | 9 | 14 | 19 | 2 | 5 | 8 | 5 | 17 | 24 | 22 | 23 | 24 | 3 | 16 | 14 | 11 | 1 | 19 | 19 | 17 | 4 | 13 | 24 | 10 | 11 |
| Lettre d'origine | | | | | | | | | | | | | | | | | | e | | | | | | | | |
1. D'après Wikipedia, la fréquence moyenne d'apparition des lettres en français est la suivante :
Ce qui nous donne l'ordre suivant, de la lettre la plus fréquente à la lettre la moins fréquente : E A I S T N R U L O D M P C V Q G B F J H Z X Y K W
Proposez dans le tableau de la question 1 la correspondance des chiffres et des lettres.
ce, de
Publicité
je, le
me, ne, se ,te
a?
qeznva, qef y'nhoe, n y'uehee h oynapuvg yn pnzcntae,
we cnegvenv. ibvf-gh, we fnvf dhe gh z'nggeaqf.
w'venv cne yn sbeeg, w'venv cne yn zbagntae.
we ae chvf qezeheee ybva qe gbv cyhf ybatgezcf.
s?
we znepueenv yef lehk svkef fhe zef ceafeef,
fnaf evea ibve nh qeubef, fnaf eageaqee nhpha oehvg,
fehy, vapbaah, ye qbf pbheoe, yef znvaf pebvfeef,
gevfge, eg ye wbhe cbhe zbv feen pbzze yn ahvg.
we ae eetneqeenv av y'be qh fbve dhv gbzoe,
av yef ibvyef nh ybva qefpeaqnag ieef unesyehe,
eg dhnaq w'neevieenv, we zeggenv fhe gn gbzoe
ha obhdheg qe ubhk ieeg eg qe oehleee ea syehe.
1. Proposez au moins 3 astuces qui pourraient vous aider à affiner votre solution (mots particuliers, suite de lettres, lettres dans des positions particulières, …).
2. Décryptez le texte.
3. Donner un exemple d'algorithme de chiffrement que cette méthode permet de casser et un autre exemple d'algorithme de chiffrement contre lequel cette méthode est inefficace.
Exercice 4 :
1. En utilisant le chiffre de Vigenère:
1. Chiffrez le message suivant en utilisant le mot clé "UNIVERSITE":
"CET EXERCICE EST FACILE"
- 1. Dechiffrez le message suivant, en utilisant le mot clé "ETUDIANT" :
" FKUYW CRLX MLHA BVXR "
Publicité
Exercice 5:
Soit la fonction de Feistel "F" représentée dans le schéma ci-dessous qui transforme les deux blocs de texte en clair M1 et M2 en deux blocs de texte chiffré C1 et C2:
M1
M2
C1
C2
1. Donnez l'expression de la fonction de chiffrement (c'est-à-dire exprimez C1 et C2 en fonction de M1, M2 et F).
2. Donnez l'expression de la fonction de chiffrement (c'est-à-dire exprimer M1 et M2 en fonction de C1, C2 et F).
3. Le schéma suivant représente la fonction de Feistel utilisée dans DES:
4. Donner l'expression de la fonction de Feistel F
5. Donner l'expression de chiffrement
6. Donner l'expression de déchiffrement
7. Les fonctions utilisées ont-elles besoin d'être inversibles pour effectuer le déchiffrement? Expliquez.
Exercice 6 :
1. Donnez la formule de chiffrement
2. Donnez la formule ET le schéma de déchiffrement
3. Lors du déchiffrement:
1. Quel est l'effet d'une erreur au niveau d'un bloc ci
2. Quel est l'effet de l'inversion de deux blocs ci et ci+1
Plain and Cipher Block Chaining (PCBC)