TD1: Cryptographie

Exercice 1 : Algorithme de chiffrement de Hill

Question 1 - Chiffrement du mot "chiffrer"

Nous devons chiffrer le mot chiffrer en utilisant l'algorithme de Hill avec les paramètres m = 2, a = 3, b = 5, c = 1, et d = 2.

Étape 1 : Diviser le texte à coder en blocs de m lettres Le mot se découpe en 4 blocs de 2 lettres : (c, h), (i, f), (f, r), (e, r)

Étape 2 : Convertir les lettres en chiffres En utilisant la convention A=0, B=1, ..., Z=25, nous obtenons les valeurs numériques suivantes :

• c = 2, h = 7
• i = 8, f = 5
• f = 5, r = 17
• e = 4, r = 17

Nos blocs x1, x2 sont donc : (2, 7), (8, 5), (5, 17), (4, 17).

Étape 3 : Calculer les yi Les combinaisons linéaires définies par l'énoncé sont : y1 = 3 × x1 + 5 × x2 y2 = 1 × x1 + 2 × x2

Effectuons le calcul pour chaque bloc :

• Bloc 1 (2, 7) : y1 = 3 × 2 + 5 × 7 = 6 + 35 = 41 y2 = 1 × 2 + 2 × 7 = 2 + 14 = 16
• Bloc 2 (8, 5) : y1 = 3 × 8 + 5 × 5 = 24 + 25 = 49 y2 = 1 × 8 + 2 × 5 = 8 + 10 = 18
• Bloc 3 (5, 17) : y1 = 3 × 5 + 5 × 17 = 15 + 85 = 100 y2 = 1 × 5 + 2 × 17 = 5 + 34 = 39
• Bloc 4 (4, 17) : y1 = 3 × 4 + 5 × 17 = 12 + 85 = 97 y2 = 1 × 4 + 2 × 17 = 4 + 34 = 38

Étape 4 : Calculer les zi (réduction modulo 26) Nous prenons le reste de la division entière par 26 (les multiples de 26 sont 26, 52, 78, 104...) :

• Bloc 1 : z1 = 41 - 26 = 15 ; z2 = 16
• Bloc 2 : z1 = 49 - 26 = 23 ; z2 = 18
• Bloc 3 : z1 = 100 - 78 = 22 ; z2 = 39 - 26 = 13
• Bloc 4 : z1 = 97 - 78 = 19 ; z2 = 38 - 26 = 12

Étape 5 : Déduire le mot codé Nous reconvertissons les nombres obtenus en lettres (0=A, 1=B...) :

• (15, 16) = (P, Q)
• (23, 18) = (X, S)
• (22, 13) = (W, N)
• (19, 12) = (T, M)

Le mot codé final est PQXSWNTM.

Question 2 - Analyse de fréquence

L'analyse de fréquence classique (basée sur l'apparition des lettres individuelles) ne permet pas de casser ce code de façon directe.

Explication : Le chiffrement de Hill est un chiffrement polygrammique. Puisque l'on chiffre par blocs de m lettres (ici des bigrammes), une même lettre en clair sera chiffrée différemment selon la lettre qui l'accompagne dans son bloc. La distribution des lettres seules dans le texte chiffré sera donc lissée, masquant les fréquences de la langue d'origine. (Il faudrait faire une analyse de fréquence sur les bigrammes entiers, ce qui requiert un texte infiniment plus long pour être statistiquement viable).

Exercice 2 : Algorithme RSA

Question 1 - Formules des variables

Dans le système RSA :

• n = p × q (où p et q sont deux grands nombres premiers distincts)
• ϕ(n) = (p - 1) × (q - 1) (l'indicatrice d'Euler)
• d est défini de sorte que : e × d ≡ 1 modulo ϕ(n). Autrement dit, d est l'inverse modulaire de e modulo ϕ(n).

Question 2 - Chiffrement et déchiffrement

1. Formule de chiffrement : c ≡ m^e modulo n (où m est le message en clair)
2. Formule de déchiffrement : m ≡ c^d modulo n (où c est le message chiffré)
3. Valeurs qui doivent rester secrètes : p, q, ϕ(n), et d. (La clé privée proprement dite est constituée de (d, n) mais p, q et ϕ(n) permettent de la retrouver facilement).
4. Valeurs publiques : n et e. (Ils forment ensemble la clé publique).

Question 3 - Calcul de la clé d

1. Pourquoi cet algorithme (Euclide Étendu) est-il applicable dans ce cas ? L'algorithme d'Euclide étendu sert à trouver les coefficients de l'identité de Bézout. Il est applicable ici car pour que e admette un inverse modulo ϕ(n), il faut impérativement que e et ϕ(n) soient premiers entre eux (soit pgcd(e, ϕ(n)) = 1). D'après le théorème de Bézout, il existe alors deux entiers u et d tels que ϕ(n)×u + e×d = 1.

2. Correspondance des variables : L'équation de base du tableau est a×x + b×y = d. L'équation RSA est ϕ(n)×u + e×d = 1. Par identification directe :

Algo	a	b	x	y	d (pgcd)
RSA	ϕ(n)	e	u	d	1

(Attention à ne pas confondre le 'd' de l'algorithme qui représente le PGCD (donc 1) avec le 'd' de RSA qui correspond au coefficient 'y' de l'algorithme).

3. Calcul de d pour p=71, q=131 et e=3 : On a d'abord ϕ(n) = (71-1) × (131-1) = 70 × 130 = 9100. On cherche d tel que 3×d ≡ 1 modulo 9100, soit 9100×u + 3×d = 1. Par division euclidienne : 9100 = 3033 × 3 + 1. On peut isoler le reste (1) pour retrouver l'identité de Bézout : 1 = 9100 × 1 + 3 × (-3033) On identifie u = 1 et d = -3033. La clé privée d doit être positive. Comme nous travaillons modulo 9100 : d ≡ -3033 modulo 9100 d = 9100 - 3033 = 6067.

(Note : L'énoncé coupe la seconde méthode entamée par "soit p=". Nous ne fournissons donc que la résolution par l'algorithme principal documenté dans le tableau).

Exercice 3 : Analyse de fréquence

Question 1 - Fréquences des lettres dans le texte encrypté

Puisque le tableau fourni dans l'énoncé contient des incohérences de formatage, voici un outil Python pour calculer rigoureusement l'occurrence des caractères dans le texte crypté donné.

texte_chiffre = """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."""

import string

frequences = {}
lettres_total = 0

for char in texte_chiffre.lower():
    if char in string.ascii_lowercase:
        frequences[char] = frequences.get(char, 0) + 1
        lettres_total += 1

# On affiche de la lettre la plus fréquente à la moins fréquente
tri_freq = sorted(frequences.items(), key=lambda x: x[1], reverse=True)
for lettre, occ in tri_freq:
    print(f"{lettre} : {occ}")

L'exécution stricte révèle que la lettre r est la plus fréquente (typiquement le substitut du 'e' en français, confirmant un décalage).

Question 2 - Correspondance des chiffres et des lettres

En analysant le texte, et sachant que E est la lettre la plus fréquente en français, le caractère r correspond au e. En vérifiant l'alphabet, l'écart entre E(4) et R(17) est de 13. Ce texte est protégé par le chiffre de César avec un décalage de 13 (ROT13). Par conséquent, la table d'équivalence est simplement décalée de 13 lettres :

• r = e
• n = a
• v = i
• f = s
• g = t
• ... et ainsi de suite (a=n, b=o, c=p...).

Question 3 - Astuces pour affiner la solution

Trois astuces textuelles précieuses pour une analyse de fréquence rapide :

1. Les mots d'une lettre : En français, les mots isolés composés d'une seule lettre sont généralement "a" (verbe avoir ou préposition à) ou "y".
2. Les apostrophes : L'usage de lettres coupées par des apostrophes (comme l', d', j', qu', n') réduit drastiquement les combinaisons possibles pour la lettre qui précède l'apostrophe.
3. Les mots très fréquents et terminaisons : Reconnaître les petits mots récurrents (le, la, de, un, et) ou les terminaisons redondantes (les pluriels en "s" ou "x", l'imparfait, les doubles consonnes "ll", "tt", "ee").

Question 4 - Décryptage du texte

En appliquant le décalage ROT-13, nous retrouvons le célèbre poème de Victor Hugo :

Demain, dès l'aube, à l'heure où blanchit la campagne, Je partirai. Vois-tu, je sais que tu m'attends. J'irai par la forêt, j'irai par la montagne. Je ne puis demeurer loin de toi plus longtemps.

Je marcherai les yeux fixés sur mes pensées, Sans rien voir au dehors, sans entendre aucun bruit, Seul, inconnu, le dos courbé, les mains croisées, Triste, et le jour pour moi sera comme la nuit.

Je ne regarderai ni l'or du soir qui tombe, Ni les voiles au loin descendant vers Harfleur, Et quand j'arriverai, je mettrai sur ta tombe Un bouquet de houx vert et de bruyère en fleur.

Question 5 - Efficacité de l'analyse de fréquence

• Algorithme pouvant être cassé par cette méthode : Le chiffre de César (ou de manière générale, tout chiffre de substitution monoalphabétique simple).
• Algorithme contre lequel cette méthode est inefficace : Les chiffrements par blocs modernes (comme AES ou DES) ou les algorithmes asymétriques (comme RSA), dont la structure détruit toute corrélation statistique entre les fréquences du texte clair et celles du texte chiffré.

Exercice 4 : Chiffre de Vigenère

Question 1 - Chiffrement

Message : "CET EXERCICE EST FACILE" Clé : "UNIVERSITE" (répétée : UNIVERSITEUNIVERSITEU)

On additionne les positions des lettres (A=0, B=1...Z=25) modulo 26 :

• C (2) + U (20) = 22 -> W
• E (4) + N (13) = 17 -> R
• T (19) + I (8) = 27 = 1 -> B
• E (4) + V (21) = 25 -> Z
• X (23) + E (4) = 27 = 1 -> B
• E (4) + R (17) = 21 -> V
• R (17) + S (18) = 35 = 9 -> J
• C (2) + I (8) = 10 -> K
• I (8) + T (19) = 27 = 1 -> B
• C (2) + E (4) = 6 -> G
• E (4) + U (20) = 24 -> Y
• E (4) + N (13) = 17 -> R
• S (18) + I (8) = 26 = 0 -> A
• T (19) + V (21) = 40 = 14 -> O
• F (5) + E (4) = 9 -> J
• A (0) + R (17) = 17 -> R
• C (2) + S (18) = 20 -> U
• I (8) + I (8) = 16 -> Q
• L (11) + T (19) = 30 = 4 -> E
• E (4) + E (4) = 8 -> I

Message chiffré : WRB ZBVJKBGY RAO JRUQEI

Question 2 - Déchiffrement

Message chiffré : "FKUYW CRLX MLHA BVXR" Clé : "ETUDIANT" (répétée : ETUDIANTETUDIANTETUD)

On soustrait les positions de la clé aux positions du message (modulo 26) :

• F (5) - E (4) = 1 -> B
• K (10) - T (19) = -9 = 17 -> R
• U (20) - U (20) = 0 -> A
• Y (24) - D (3) = 21 -> V
• W (22) - I (8) = 14 -> O
• C (2) - A (0) = 2 -> C
• R (17) - N (13) = 4 -> E
• L (11) - T (19) = -8 = 18 -> S
• X (23) - E (4) = 19 -> T
• M (12) - T (19) = -7 = 19 -> T
• L (11) - U (20) = -9 = 17 -> R
• H (7) - D (3) = 4 -> E
• A (0) - I (8) = -8 = 18 -> S
• B (1) - A (0) = 1 -> B
• V (21) - N (13) = 8 -> I
• X (23) - T (19) = 4 -> E
• R (17) - E (4) = 13 -> N

Message clair : BRAVO CEST TRES BIEN

Exercice 5 : Fonction de Feistel (et DES)

Question 1 et 2 - Expressions génériques (Schéma 1)

Dans un réseau de Feistel classique (où le bloc M est scindé en moitié gauche M1 et moitié droite M2) :

1. Chiffrement : C1 = M2 C2 = M1 ⊕ F(M2)
2. Déchiffrement : M2 = C1 M1 = C2 ⊕ F(C1)

(Le symbole ⊕ représente l'opérateur logique XOR ou "OU exclusif").

Question 3 à 6 - Application au DES

L'énoncé signale l'application de ce modèle dans le standard DES (Data Encryption Standard). Bien que le schéma propre au DES ne soit pas affiché, voici les composantes classiques exigées.

4. Expression de la fonction de Feistel F (dans DES) : Dans DES, la fonction F prend la moitié droite (R) et la clé de sous-tour (K). L'expression est : F(R, K) = P(S_boxes(E(R) ⊕ K)) Où E est la fonction d'expansion, S_boxes sont les boîtes de substitution, et P est la permutation finale.

5. Expression de chiffrement pour le tour i : L_{i} = R_{i-1} R_{i} = L_{i-1} ⊕ F(R_{i-1}, K_i)

6. Expression de déchiffrement pour le tour i : R_{i-1} = L_i L_{i-1} = R_i ⊕ F(L_i, K_i)

Question 7 - Inversibilité de la fonction F

La fonction F (utilisée au sein de l'algorithme) n'a pas besoin d'être inversible. C'est l'un des plus grands avantages conceptuels des réseaux de Feistel. En effet, lors du déchiffrement, la fonction F n'est évaluée que dans le sens "aller" (on applique F sur C1 qui est identique à M2), et le recouvrement du message est garanti mathématiquement par les propriétés de l'opération XOR (X ⊕ Y ⊕ Y = X).

Exercice 6 : Mode PCBC (Plain and Cipher Block Chaining)

Question 1 - Formule de chiffrement

Dans le mode PCBC, avant d'être chiffré par l'algorithme sous-jacent avec la clé K, le bloc de texte clair courant (P_i) subit un XOR avec à la fois le bloc chiffré précédent (C_{i-1}) ET le bloc clair précédent (P_{i-1}). Formule : C_i = E_K(P_i ⊕ P_{i-1} ⊕ C_{i-1}) (Pour le premier bloc i=1, un vecteur d'initialisation IV est utilisé tel que P_0 ⊕ C_0 = IV).

Question 2 - Formule et schéma de déchiffrement

Pour déchiffrer, on déchiffre d'abord le bloc cryptogramme courant (ce qui ramène à l'étape intermédiaire où les XOR ont eu lieu), puis on applique à nouveau le double XOR avec P_{i-1} et C_{i-1} : Formule : P_i = D_K(C_i) ⊕ P_{i-1} ⊕ C_{i-1}

Schéma de déchiffrement : Le bloc entrant C_i passe dans la fonction de déchiffrement D_K. La sortie de cette boîte subit un premier XOR avec C_{i-1} puis un second XOR avec P_{i-1} (qui vient d'être déchiffré à l'étape d'avant). Le résultat final sortant est P_i.

Question 3 - Propriétés d'erreurs (Propagations)

1. Effet d'une erreur au niveau d'un bloc C_i : Dans le mode PCBC, une erreur (bit inversé ou altéré) dans le cryptogramme C_i va corrompre totalement P_i. Or, le bloc suivant P_{i+1} dépend à la fois de C_i et de P_i. Les erreurs de C_i et P_i s'additionnant dans le XOR ne s'annulent pas. Par conséquent, P_{i+1} sera lui aussi corrompu, tout comme P_{i+2}, etc. L'erreur se propage jusqu'à la fin de toute la chaîne de blocs de manière irrémédiable.

2. Effet de l'inversion de deux blocs (C_i et C_{i+1}) : Contrairement au mode CBC (où l'erreur d'un échange se limite localement avant que le déchiffrement ne se remette sur pied), dans PCBC l'inversion de deux blocs brise la logique en chaîne. Le calcul de P_{i+1} (désormais basé sur l'ancien C_i mal positionné) échoue dramatiquement et corrompt tout le texte en clair de ce point jusqu'à la fin du message. (C'est d'ailleurs pour vérifier rigoureusement l'intégrité globale que Kerberos v4 utilisait PCBC initialement).

Méthode

Face à une épreuve de cryptographie fondamentale (chiffrements classiques et structures par blocs) :

• Pour les exercices manuels (Hill, Vigenère), portez une attention maximale à vos bases d'arithmétique modulaire (réduction de nombres négatifs ou très grands modulo 26) et au bon comptage des positions (A=0).
• Une erreur de calcul sur le premier bloc du chiffre de Hill affecte tout ce qui suit dans votre tableau ; validez vos équations linéaires avant de procéder aux conversions textuelles.
• Pour l'algorithme d'Euclide étendu, respectez scrupuleusement le format de tableau présenté par votre professeur et vérifiez toujours, à la dernière étape, que l'inverse d retourné est bien positif, en appliquant d = d + ϕ(n) si nécessaire.
• Ne bloquez pas si un énoncé réfère à un "schéma manquant" : la nomenclature normalisée (ex: DES, PCBC, Feistel) définit mathématiquement de façon universelle les dépendances entre les variables. Appuyez-vous sur les définitions génériques de vos cours.