Nom : CHOUBIK
Prénom : HOUSSAM
Filière : CS2C-1
Exercice 1: Chiffre de César
- Écrire une fonction qui prend en paramètre une chaine de caractère ch ainsi qu’un nombre de décalage k (entre 1 et 25) et retourne la chaine ch cryptée par le chiffre de César de décalage k.
- En déduire un programme qui lit une chaine de caractères ch et lui applique le cryptage et le décryptage en affichant à chaque étape le résultat.
- Écrire un programme qui cryptanalyse un message intercepté supposé chiffré par
César :
- En testant tous les décalages possibles (attaque par force brute),
- En utilisant une attaque statistique.
def cesar(ch,k):
cipher=""
for char in ch:
if char.isalpha():
d=ord('A') if char.isupper() else ord('a')
c=chr((ord(char)-d+k)%26+d)
cipher+=c
else:
cipher+=char
return cipher
def decrypt(ch,k):
plain=""
for char in ch:
if char.isalpha():
d=ord('A') if char.isupper() else ord('a')
c=chr((ord(char)-d-k)%26+d)
plain+=c
else:
plain+=char
return plain
message="ab"
k=2
cipher_text=cesar(message,k)
ch="cd"
print(cipher_text)
original=decrypt(ch,k)
print(original)
cd ab
def bruteforce(ch):
for k in range(26):
plain=""
for char in ch:
if char.isalpha():
d=ord('A') if char.isupper() else ord('a')
c=chr((ord(char)-d-k)%26+d)
plain+=c
else:
plain+=char
print(f"Clé {k}: {plain}")
bruteforce("cd")
Clé 0: cd Clé 1: bc Clé 2: ab Clé 3: za Clé 4: yz Clé 5: xy Clé 6: wx Clé 7: vw Clé 8: uv Clé 9: tu Clé 10: st Clé 11: rs Clé 12: qr Clé 13: pq Clé 14: op Clé 15: no Clé 16: mn Clé 17: lm Clé 18: kl Clé 19: jk Clé 20: ij Clé 21: hi Clé 22: gh Clé 23: fg Clé 24: ef Clé 25: de
def cryptanalyse_statistique(texte):
lettres_seules = [c.upper() for c in texte if c.isalpha()]
frequences = {}
for lettre in lettres_seules:
frequences[lettre] = frequences.get(lettre, 0) + 1
lettre_max = max(frequences, key=frequences.get)
k= (ord(lettre_max) - ord('E')) % 26
plain= ""
for char in texte:
if char.isalpha():
start = ord('A') if char.isupper() else ord('a')
c = chr((ord(char) - start - k) % 26 + start)
plain+= c
else:
plain+= char
return k, plain
message_intercepte = "Frpsuhqguh od fubswrjudsklh hvw sdvvlrqqdqwh !"
cle, resultat = cryptanalyse_statistique(message_intercepte)
print(f"Lettre la plus fréquente détectée comme étant le 'E'.")
print(f"Clé probable : {cle}")
print(f"Message décrypté : {resultat}")
Lettre la plus fréquente détectée comme étant le 'E'. Clé probable : 3 Message décrypté : Comprendre la cryptographie est passionnante !
Exercice 2: Chiffrement par Substitution Mono-Alphabétique
- Écrire une fonction qui génère aléatoirement une table de substitution mono- alphabétique Tab (Attention : éviter les répétitions).
- Écrire un programme qui lit un fichier texte ( .txt) et crypte son contenu par un chiffrement par substitution mono-alphabétique via la table Tab et range le résultat dans un autre fichier text.
- Écrire une fonction qui calcule la fréquence d’apparition des lettres dans un text et range le résultat pour un traitement ultérieur. (Ne pas compter les espaces)
- En se basant sur la table de fréquences de la langue utilisée pour la rédaction du texte, tenter de cryptanalyser un text intercepté (chaine de plus de 500 caractères) en supposant qu’il a été crypté par substitution mono-alphabétique.
N.B Vous pouvez utiliser un texte en anglais, en se référant à la table de fréquences appropriées.
import random
import string
def table_substitution():
alphabet = list(string.ascii_uppercase)
substitution = list(string.ascii_uppercase)
random.shuffle(substitution)
tab = {alphabet[i]: substitution[i] for i in range(len(alphabet))}
return tab
table=table_substitution()
print(table)
{'A': 'G', 'B': 'X', 'C': 'F', 'D': 'Z', 'E': 'R', 'F': 'N', 'G': 'M', 'H': 'J', 'I': 'C', 'J': 'S', 'K': 'D', 'L': 'V', 'M': 'K', 'N': 'Y', 'O': 'I', 'P': 'T', 'Q': 'W', 'R': 'B', 'S': 'U', 'T': 'H', 'U': 'L', 'V': 'O', 'W': 'E', 'X': 'P', 'Y': 'A', 'Z': 'Q'}
def chiffrer_fichier(source, destination, tab):
try:
with open(source, 'r', encoding='utf-8') as f_in:
texte = f_in.read()
texte_chiffre = ""
for char in texte:
if char.upper() in tab:
nouveau_char = tab[char.upper()]
texte_chiffre += nouveau_char if char.isupper() else nouveau_char.lower()
else:
texte_chiffre += char
with open(destination, 'w', encoding='utf-8') as f_out:
f_out.write(texte_chiffre)
print(f"Fichier chiffré enregistré dans : {destination}")
except FileNotFoundError:
print("Erreur : Fichier source introuvable.")
def frequences(texte):
lettres_uniquement = [c.upper() for c in texte if c.isalpha()]
total = len(lettres_uniquement)
if total == 0: return {}
frequences = {}
for char in string.ascii_uppercase:
count = lettres_uniquement.count(char)
frequences[char] = (count / total) * 100
return dict(sorted(frequences.items(), key=lambda x: x[1], reverse=True))
def cryptanalyser(texte_chiffre):
freq_fr_ordre = "ESAINT RULOD"
freq_fr_ordre = freq_fr_ordre.replace(" ", "")
freq_observees = frequences(texte_chiffre)
lettres_observees_ordre = "".join(freq_observees.keys())
decodage_probable = str.maketrans(lettres_observees_ordre, freq_fr_ordre[:len(lettres_observees_ordre)])
return texte_chiffre.translate(decodage_probable)
Exercice 3: Chiffre Homophone 1. Écrire une fonction qui génère aléatoirement un tableau de substitution Tab de 0 à 99 (voir cours). Attention : éviter les répétitions. 2. Écrire une fonction qui crypte un texte par un chiffre homophone en se basant sur la table Tab. Cette fonction doit choisir d’une manière uniforme les choix de substitution. i.e : ne pas choisir un nombre une deuxième fois avant que tous les autres nombres soient choisis au moins une fois. Dans l’exemple du cours pour la lettre D, les choix possibles sont 01, 03, 45, 79 3. Refaire les questions 1. et 2. : - En utilisant un carré de Polybe (initialisé manuellement ou aléatoirement) - En utilisant l’alternative 2 (voir cours)
import random
def generer_table_homophone():
repartition = {
'E': 14, 'S': 8, 'A': 8, 'I': 7, 'N': 7, 'T': 7, 'R': 6, 'U': 6,
'L': 5, 'O': 5, 'D': 4, 'C': 3, 'P': 3, 'M': 3, 'V': 2, 'G': 2,
'F': 2, 'B': 1, 'Q': 1, 'H': 1, 'X': 1, 'J': 1, 'Y': 1, 'Z': 1, 'K': 1
}
nombres = list(range(100))
random.shuffle(nombres)
tab = {}
index = 0
for lettre, quota in repartition.items():
tab[lettre] = nombres[index : index + quota]
index += quota
return tab
table_homo = generer_table_homophone()
def chiffrer_homophone(texte, tab):
compteurs = {lettre: 0 for lettre in tab.keys()}
resultat = []
for char in texte.upper():
if char in tab:
liste_nombres = tab[char]
idx = compteurs[char]
nombre_choisi = liste_nombres[idx]
resultat.append(f"{nombre_choisi:02d}")
compteurs[char] = (idx + 1) % len(liste_nombres)
return "-".join(resultat)
print(chiffrer_homophone("DEDEE", table_homo))
68-74-46-57-96
def generer_polybe():
lettres = "ABCDEFGHJKLMNOPQRSTUVWXYZ" # Sans le I (ou le J)
grille = list(lettres)
random.shuffle(grille)
tab_polybe = {}
for i in range(5):
for j in range(5):
tab_polybe[grille[i*5 + j]] = f"{i+1}{j+1}"
tab_polybe['I'] = tab_polybe['J'] # On lie I et J
return tab_polybe
def chiffrer_polybe(texte, tab):
return "".join([tab[c.upper()] for c in texte if c.upper() in tab])
def generer_alternative_2(cle="CRYPTO"):
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
suite = ""
for c in cle + alphabet:
if c not in suite:
suite += c
tab = {alphabet[i]: suite[i] for i in range(26)}
return tab
Exercice 4 : Chiffrement de Vigenère 1. Implémentation du chiffrement et du déchiffrement - Écrire une fonction qui chiffre un texte clair à l’aide du chiffre de Vigenère en prenant comme paramètres le texte clair et la clé alphabétique. - Écrire une fonction permettant de déchiffrer un texte chiffré à partir de la clé. 2. Cryptanalyse du chiffre de Vigenère a. Méthode de Kasiski La méthode de Kasiski permet d’estimer la longueur de la clé. Elle consiste à : - Repérer des séquences de lettres répétées dans le texte chiffré (LS=3,4,5,…), - Mesurer les distances entre leurs occurrences, déterminer les diviseurs communs de ces distances, qui sont de bons candidats pour la longueur de la clé. Réf:https://fr.wikipedia.org/wiki/Cryptanalyse_du_chiffre_de_Vigen%C3%A8re b. Affinement avec l’Indice de Coïncidence (IC) - Pour chaque longueur candidate (L) trouvée par Kasiski : 1. Découper le texte chiffré en L sous-textes : - Sous-texte 1 = lettres aux positions 0, L, 2L, … - Sous-texte 2 = lettres aux positions 1, L+1, 2L+1, … jusqu’au sous-texte L. 2. Calculer l’IC de chaque sous-texte : - IC proche de 0,065 : longueur probable correcte (texte français/anglais), - IC ~ 0,038 : longueur improbable (texte proche de l’aléatoire). 3. Retenir la longueur dont la moyenne des IC est la plus proche de 0,065. c. Récupération de la clé et déchiffrement - Appliquer une analyse fréquentielle sur chaque sous-texte pour retrouver la lettre correspondante de la clé. - Reconstituer la clé complète. - Déchiffrer le texte intercepté. 3. Étude de l’impact de la taille de la clé sur la sécurité - Chiffrer le même texte avec plusieurs clés de tailles différentes (par exemple : 3, 6, 10, 15 caractères…). - Appliquer la méthode de Kasiski et l’analyse fréquentielle dans chaque cas. - Montrer expérimentalement que plus la clé est longue, plus la cryptanalyse devient difficile, voire imprécise ou inefficace pour des textes de taille limitée.
def vigenere_chiffrer(texte, cle):
resultat = ""
cle = cle.upper()
index_cle = 0
for char in texte.upper():
if char.isalpha():
decalage = ord(cle[index_cle % len(cle)]) - ord('A')
nouveau_char = chr((ord(char) - ord('A') + decalage) % 26 + ord('A'))
resultat += nouveau_char
index_cle += 1
else:
resultat += char
return resultat
def vigenere_dechiffrer(chiffre, cle):
resultat = ""
cle = cle.upper()
index_cle = 0
for char in chiffre.upper():
if char.isalpha():
decalage = ord(cle[index_cle % len(cle)]) - ord('A')
nouveau_char = chr((ord(char) - ord('A') - decalage) % 26 + ord('A'))
resultat += nouveau_char
index_cle += 1
else:
resultat += char
return resultat
from math import gcd
from collections import Counter
def test_kasiski(chiffre, longueur_sequence=3):
distances = []
for i in range(len(chiffre) - longueur_sequence):
seq = chiffre[i:i+longueur_sequence]
prochaine_occurence = chiffre.find(seq, i + 1)
if prochaine_occurence != -1:
distances.append(prochaine_occurence - i)
return distances
def calculer_ic(texte):
n = len([c for c in texte if c.isalpha()])
if n <= 1: return 0
frequences = Counter(texte)
somme_f = sum(f * (f - 1) for f in frequences.values())
return somme_f / (n * (n - 1))
def trouver_longueur_cle(chiffre, max_L=20):
for L in range(1, max_L + 1):
sous_textes = [chiffre[i::L] for i in range(L)]
moyenne_ic = sum(calculer_ic(st) for st in sous_textes) / L
if moyenne_ic > 0.06:
return L
return None
def casser_vigenere(chiffre, L):
cle = ""
for i in range(L):
sous_texte = [c for c in chiffre[i::L] if c.isalpha()]
freqs = Counter(sous_texte)
lettre_la_plus_frequente = freqs.most_common(1)[0][0]
decalage = (ord(lettre_la_plus_frequente) - ord('E')) % 26
cle += chr(decalage + ord('A'))
return cle
Exercice 5: Chiffre de Hill (m = 2) 1. Écrire une fonction qui retourne l’inverse d’un nombre n dans Z/26Z s’il existe et 0 sinon. 2. Écrire une fonction qui génère une matrice Q(m,m) inversible dans Z/26Z. 3. Écrire une fonction qui crypte un texte via le chiffre de Hill basé sur la matrice Q. 4. Écrire une fonction qui décrypte un texte via le chiffre de Hill basé sur la matrice Q. 5. Écrire un programme qui illustre les questions de 1. à 4. 6. Cryptanalyse (attaque par clair connu) En supposant que l’attaquant connaît : - Au moins deux digrammes en clair et leurs chiffrés correspondants, - Et que le chiffrement a été effectué avec une matrice 2×2, Écrire un programme qui : - Retrouve la matrice de chiffrement Q, - Vérifie sa validité (inversible modulo 26), - Et déchiffre un message intercepté.
def inverse_modulaire(n, m=26):
for i in range(1, m):
if (n * i) % m == 1:
return i
return 0
import numpy as np
def generer_matrice_Q():
while True:
Q = np.random.randint(0, 26, size=(2, 2))
det = int(round(np.linalg.det(Q))) % 26
if inverse_modulaire(det, 26) != 0:
return Q
def texte_en_vecteurs(texte):
texte = "".join([c.upper() for c in texte if c.isalpha()])
if len(texte) % 2 != 0: texte += 'X' # Padding
return [(ord(texte[i])-65, ord(texte[i+1])-65) for i in range(0, len(texte), 2)]
def hill_chiffrer(texte, Q):
vecteurs = texte_en_vecteurs(texte)
chiffre = ""
for v in vecteurs:
res = np.dot(Q, v) % 26
chiffre += chr(res[0] + 65) + chr(res[1] + 65)
return chiffre
def inverser_matrice_mod(Q, m=26):
det = int(round(np.linalg.det(Q))) % m
inv_det = inverse_modulaire(det, m)
adj = np.array([[Q[1,1], -Q[0,1]], [-Q[1,0], Q[0,0]]])
return (inv_det * adj) % m
def hill_dechiffrer(chiffre, Q):
Q_inv = inverser_matrice_mod(Q)
return hill_chiffrer(chiffre, Q_inv)
def attaquer_hill(p1, c1, p2, c2):
P = np.array([[ord(p1[0])-65, ord(p2[0])-65],
[ord(p1[1])-65, ord(p2[1])-65]])
C = np.array([[ord(c1[0])-65, ord(c2[0])-65],
[ord(c1[1])-65, ord(c2[1])-65]])
try:
P_inv = inverser_matrice_mod(P)
Q = np.dot(C, P_inv) % 26
return Q
except:
return "Impossible de retrouver la clé (P non inversible)."
P1, C1 = "HE", "TF"
P2, C2 = "LP", "OW"
cle_retrouvee = attaquer_hill(P1, C1, P2, C2)
print("Matrice retrouvée :\n", cle_retrouvee)
Matrice retrouvée : [[11 5] [13 11]]