Objectifs

Consignes

Un exemple de chiffrement symétrique : XOR

Le XOR (OU exclusif) est très utilisé dans les protocoles de chiffrement symétrique. En effet, c’est une opération qui est sa propre réciproque, ce qui n’est pas le cas du ET ni du OU.

C’est à dire que : XOR(XOR(A,B),B) = A (1)

Démontrer la propriété (1) à l'aide de tables de vérité.

Nous allons programmer un protocole de chiffrement symétrique utilisant le XOR.

On souhaite chiffrer un message (par exemple une chaîne de caractères) à l’aide d’une clé, qui peut aussi être une chaîne de caractères. Pour simplifier la programmation, on supposera que seuls des caractères ASCII sont utilisés (pas d’utf-8 ou plus généralement d’Unicode).

Ecrire le corps de la fonction convertit_texte_en_binaire(texte) qui convertit la chaine de caractères ASCII texte passée en paramètre en une chaine binaire et retourne cette chaine binaire. Chaque caractère sera représenté par son code ASCII en binaire sur un octet.

Exemple : convertit_texte_en_binaire("NSI") doit retourner la chaine : '010011100101001101001001'.

En effet :

Et, '01001110' + '01010011' + '01001001' = '010011100101001101001001'

Ecrire le corps de la fonction convertit_binaire_vers_entier_base_10(chaine_binaire) qui convertit la chaine binaire chaine_binaire passée en paramètre en le nombre décimal correspondant et retourne ce nombre décimal.

Exemple : convertit_binaire_vers_entier_base_10("01001110") doit retourner l'entier 78

En effet : 01001110 en base 2 = 0x1 + 1x2 + 1x4 + 1x8 + 0x16 + 0x32 + 1x64 + 0x128 = 2 + 4 + 8 + 64 = 78

Ecrire le corps de la fonction convertit_binaire_en_texte(chaine_binaire) qui convertit la chaine chaine_binaire passée en paramètre composée d'octets binaires représentant des caractères codés en ASCII en une chaine de caractères et retourne cette chaine de caractères.

Exemple : convertit_binaire_en_texte("010011100101001101001001") doit retourner la chaine : 'NSI'.

En effet :

'010011100101001101001001' = '01001110' + '01010011' + '01001001'

La chaîne retournée est donc bien "NSI".

Ecrire le corps de la fonction chiffre_xor(chaine_binaire,clef_binaire) qui chiffre la chaine binaire chaine_binaire passée en paramètre avec la clef binaire clef_binaire passée en paramètre en effectuant l'opération XOR bit à bit entre la chaine binaire et la clef binaire (répétée). La fonction doit retourner la chaine ainsi chiffrée.

Exemple : Chiffrons la chaine "SPECIALITE NSI" avec la clef "TERM". 

convertit_texte_en_binaire("SPECIALITE NSI")
retourne '0101001101010000010001010100001101001001010000010100110001001001010101000100010100100000010011100101001101001001'. 

convertit_texte_en_binaire("TERM")
retourne '01010100010001010101001001001101'.

L'application du XOR entre '0101001101010000010001010100001101001001010000010100110001001001010101000100010100100000010011100101001101001001' et la clef binaire répétée '01010100010001010101001001001101' donne : 

0101001101010000010001010100001101001001010000010100110001001001010101000100010100100000010011100101001101001001 XOR
0101010001000101010100100100110101010100010001010101001001001101010101000100010101010010010011010101010001000101 =
0000011100010101000101110000111000011101000001000001111000000100000000000000000001100010000000110000011100001100

Donc chiffre_xor('0101001101010000010001010100001101001001010000010100110001001001010101000100010100100000010011100101001101001001','01010100010001010101001001001101') doit retourner '0000011100010101000101110000111000011101000001000001111000000100000000000000000001110010000000110000011100001100'.

Montrer sur un exemple (message et clef de chiffrement de votre choix), que si on chiffre le message avec la clef et qu'on chiffre le message chiffré avec la même clef, on retrouve le message de départ en clair.

Par exemple : 


message = "SPECIALITE NSI"
clef = "TERM"
message_binaire = convertit_texte_en_binaire(message)
print(message,"en binaire",message_binaire)
clef_binaire = convertit_texte_en_binaire(clef)
print(clef,"en binaire",clef_binaire)
message_binaire_chiffre = chiffre_xor(message_binaire,clef_binaire)
print("message chiffré",message_binaire_chiffre)
message_binaire_dechiffre = chiffre_xor(message_binaire_chiffre,clef_binaire)
print("message_binaire_dechiffre",message_binaire_dechiffre)
print("message dechiffré en ASCII",convertit_binaire_en_texte(message_binaire_dechiffre))

conduit à l'affichage suivant : 

SPECIALITE NSI en binaire 0101001101010000010001010100001101001001010000010100110001001001010101000100010100100000010011100101001101001001
TERM en binaire 01010100010001010101001001001101
message chiffré 0000011100010101000101110000111000011101000001000001111000000100000000000000000001110010000000110000011100001100
message_binaire_dechiffre 0101001101010000010001010100001101001001010000010100110001001001010101000100010100100000010011100101001101001001
message dechiffré en ASCII SPECIALITE NSI

Un exemple de chiffrement asymétrique : kidRSA

Un algorithme de chiffrement asymétrique très utilisé se nomme RSA.

Dans ce TP, nous allons utiliser une version plus simple nommée kidRSA : le RSA pour les "enfants".

Principe de l'algorithme kidRSA

  1. Choisir 4 entiers : $a1, \; b1, \; a2, \; b2$.

  2. On calcule les entiers suivants :

    • $M = a1 \times b1 - 1$
    • $e = a2 \times M + a1$
    • $d = b2 \times M + b1$
    • $n = \frac{e \times d - 1}{M}$
  3. La clef publique est (e,n)
  4. La clef secrète est (d,n)
  5. Pour chiffrer un message représenté par un entier m plus petit que n, on effectue l'opération e x m (modulo n).
  6. Pour déchiffrer un message représenté par un entier m plus petit que n, on effectue l'opération d x m (modulo n).

Un exemple (avec des petits nombres)

Prenons $a1 = 5$, $b1 = 3$, $a2 = 7$ et $b2 = 5$.

Une implémentation en Python du chiffrement avec l'algorithme KidRSA

Implémenter les fonctions Python suivantes :

Tests de cette implémentation en Python de KidRSA

On choisit comme valeurs $a1 = 13, b1 = 32, a2 = 69$ et $b2 = 35$

Donner les informations suivantes à partir des fonctions Python codées pour l'algorithme KidRSA :

Casser (ou décrypter) le chiffrement KidRSA

Un message a été chiffré avec KidRSA à l'aide de la clef publique suivante (e,n) = (53447,5185112).

Voici le message chiffré obtenu :

[3580949, 2084433, 3687843, 4436101, 4489548, 1710304, 4329207, 4542995, 3901631, 1710304, 4061972, 3687843, 1710304, 3527502, 4222313, 4436101, 4436101, 1710304, 3687843, 4168866, 1710304, 4168866, 4436101, 3901631, 1710304, 3367161]

On souhaite "casser" le message chiffré et retrouver le message en clair. Pour cela, on a besoin de connaître la clef secrète (d,n). Comme on connait déjà $n$ ($n = 5185112$), il faut trouver une méthode pour calculer $d$.

Attaque de KidRSA par force brute

En étudiant la relation entre les nombres qui constituent les clefs publique et privées $e ,\; d$ et $n$ : $n = \frac{e \times d - 1}{M}$, qui peut s'écrire aussi : $e \times d - 1 = n \times M$.

On en déduit que $e \times d - 1$ est divisible par $n$.

Pour trouver l'entier $d$ qui fait partie de la clef secrète, comme on connait déjà $n$ et $e$, il suffit d'étudier parmi toutes les valeurs de $d$ comprises entre 1 et $n - 1$, laquelle vérifie la condition "$e \times d - 1$ est divisible par $n$."

On appelle ce type d'attaque par force brute car on doit étudier (dans le pire des cas) tous les entiers $d$ inférieurs à $n$. Ce qui peut être long si $n$ est grand.

Ecrire le corps de la fonction bruteForceKidRSA(e,n) qui permet de calculer et de retourner le premier entier $d$ inférieur à $n$ qui vérifie la relation "$e \times d - 1$ est divisible par $n$."

En déduire la valeur de $d$ et obtenir ainsi le déchiffrement du message chiffré donné plus haut.

Attaque de KidRSA plus subtile (à l'aide de l'algorithme d'Euclide étendu)

La réponse au message chiffré précédent est aussi chiffrée avec KidRSA mais avec une clef publique de longueur beaucoup plus grande.

Voici la clef publique utilisée : (e,n) = (230884490440319,194326240259798261076).

Et voici le message chiffré obtenu avec la clef publique :

[16623683311702968, 19625181687427115, 16392798821262649, 16392798821262649, 20548719649188391, 7388303694090208, 17547221273464244, 15931029840382011, 19163412706546477, 7388303694090208, 15238376369061054, 18239874744785201, 18008990254344882, 19163412706546477, 7388303694090208, 19394297196986796, 19625181687427115, 20548719649188391, 15007491878620735, 19625181687427115, 20317835158748072, 7388303694090208, 7619188184530527]

Essayer de retrouver la clef secrète à l'aide de la fonction bruteForceKidRSA(e,n). Quel est le problème rencontré ?

Il faut résoudre l'équation $ed \equiv 1 \pmod n$ avec une méthode plus efficace que par force brute. Cela revient à trouver l'inverse entier de $e$ modulo $n$.

Une méthode mathématique qui permet de résoudre ce problème se nomme l'algorithme d'Euclide étendu.

Exemple d'utilisation de l'algorithme d'Euclide étendu

L'algorithme d'Euclide étendu est basé sur une suite de divisions euclidiennes que nous ne détaillerons pas ici. Dans la partie arithmétique du programme de mathématiques expertes, il est possible que cet algorithme soit étudié.

On peut retenir que pour rechercher la clef secrète associée à une clef publique, l'algorithme d'Euclide étendu est beaucoup plus efficace que l'attaque par force brute.La complexité algorithmique par force brute est dans le pire des cas en $O(n)$ alors que celle avec l'algorithme d'Euclide étendu est en $O(log(n))$.

Voici deux fonctions données en pseudo-code qui permettent de trouver l'inverse d'un entier modulo un autre entier. 

fonction modinv(e,n)
	g,x,y = egcd(e,n)
	si g != 1 alors
		retourner Faux
	sinon
		retourner x % n

fonction egcd(a,b)
	Si a = 0 alors
		retourner (b,0,1)
	sinon
		g,y,x = egcd(b % a,a)
		retourner (g, x - (b//a)*y,y)

Coder ces deux fonctions en Python. En déduire la clef privée secrète associée à la clef publique : (19432624025979826176, 230884490440319). En déduire le décodage du deuxième message chiffré avec cette clef publique.

Une étude de la vulnérabilité de l'algorithme RSA

Nous venons de vérifier que l'algorithme KidRSa pouvait être facilement "cassé" même avec des clefs assez grandes à l'aide de l'algorithme d'Euclide étendu.

Heureusement, le véritable algorithme RSA utilisé par HTTPS sur internet est bien plus robuste.

Donner la taille des clefs couramment utilisées par RSA pour sécuriser des données sur Internet. Donner aussi quelle nouvelle technologie pourrait permettre de casser RSA en quelques secondes.

En complément, un bel article de CultureMath Voyage au coeur de la cryptographie en rapport avec le programme de Mathématiques Expertes.

Auteur : Hugues Malherbe (basé sur un document de Frédéric Mandon et Romain Mallet)