TP de Maple : Cryptographie

Ce TP de Maple porte sur la cryptographie et permet d’explorer deux méthodes fondamentales : l’algorithme du sac à dos et la méthode RSA. Il enseigne comment coder et décoder des messages, comprendre les propriétés mathématiques sous-jacentes, et implémenter ces algorithmes dans Maple. Pour réaliser ce TP, il est nécessaire de disposer de Maple et de connaissances de base en programmation et en arithmétique modulaire.

Objectifs

• Coder et décoder un texte en une suite de nombres et inversement.
• Comprendre et implémenter l’algorithme du sac à dos, notamment avec des suites super croissantes.
• Appliquer la méthode de cryptage et décryptage du sac à dos avec clé publique et clé privée.
• Comprendre la méthode RSA et coder/décoder un message avec cette méthode.
• Analyser les propriétés mathématiques nécessaires à la cryptographie à clé publique.

Prérequis et installation

• Logiciel Maple installé et fonctionnel.
• Connaissances de base en programmation Maple (procédures, boucles, conditions).
• Notions d’arithmétique modulaire, notamment sur les inverses modulo et la factorisation.
• Compréhension des notions de suites super croissantes et du problème du sac à dos.

Première opération : Codage d’un texte

Pour crypter un message, il faut d’abord le transformer en une suite de nombres. Maple offre la fonction convert avec l’option bytes pour convertir une chaîne de caractères en une liste de codes numériques.

Écrivez deux procédures :

• code(txt) : transforme une chaîne de caractères en une suite de nombres.
• decode(nums) : transforme une suite de nombres en une chaîne de caractères.

Ces procédures permettent de passer du texte clair à une représentation numérique exploitable pour le cryptage.

Cryptage par l’algorithme du sac à dos

Le problème du sac à dos consiste à trouver une combinaison d’objets (représentée par un vecteur binaire) dont la somme des valeurs correspond à un total donné. Ce problème est en général NP-complet, ce qui le rend difficile à résoudre sans information secrète.

Les suites super croissantes

Un n-uplet (b1, ..., bn) est super croissant si pour tout i ≥ 2 :

bi > Σ (j=1 à i-1) bj

1. Écrivez une procédure est_super(b) qui renvoie true si la suite b est super croissante, false sinon.

2. Si b est super croissante et S = Σ xi bi avec xi ∈ {0,1}, alors :

• Si bn > S, alors xn = 0.
• Si bn ≤ S, alors xn = 1.

En déduire un algorithme pour déterminer les xi connaissant b et S.

Écrivez une procédure resout(S,b) qui, étant donné une suite super croissante b et un entier S ≤ Σ bi, renvoie un entier M dont l’écriture binaire M = x1x2...xn vérifie :

S = Σ (i=1 à n) xi bi

Cryptographie et algorithme du sac à dos

La suite super croissante ne convient pas directement à la cryptographie car elle est facile à décoder. Merkle et Hellman ont proposé de transformer cette suite en une autre suite a non super croissante, rendant le décodage difficile sans la clé secrète.

Pour cela, on choisit :

• Un entier m > Σ bi.
• Un entier w tel que pgcd(w,m) = 1, donc w est inversible modulo m.
• L’inverse u = w⁻¹ mod m.

On calcule alors :

ai = w · bi mod m, pour i = 1,...,n

Le n-uplet a = (a1,...,an) est rendu public, tandis que u est secret.

Pour transmettre un message S écrit en binaire S = xnxn-1...x1, on calcule :

Σ = Σ (i=1 à n) xi ai

Ce nombre est envoyé. Pour déchiffrer, on calcule :

Σ · u mod m = Σ (i=1 à n) xi bi

La suite b étant super croissante, on peut retrouver facilement les bits xi.

1. Écrivez une procédure Csac(txt,a) qui, donné un texte txt, renvoie le message codé avec le n-uplet a selon la méthode ci-dessus. Utilisez la fonction convert de Maple pour obtenir l’écriture binaire des nombres.

2. Écrivez une procédure Dsac(txtcod,a,u) qui, à partir du message crypté txtcod, de la clé publique a et de la clé privée u, renvoie le message décodé.

3. Vérifiez que les données suivantes :

• b = [5, 13, 21, 89, 233, 377, 987, 2584, 6765, 17711, 251516, 6548456, 65484652, 114845465]
• m = 463814521
• w = 234203372
• u = 101

vérifient bien les propriétés voulues. Décryptez le message :

[648640591, 1329005307, 1162545881, 1016018455, 1116558815, 1033898626]

Notez que cette méthode, bien que prometteuse, a été cassée en 1982 par Shamir, car la clé publique a n’est pas totalement aléatoire, ce qui permet une attaque.

Méthode RSA

La méthode RSA, inventée en 1977 par Rivest, Shamir et Adleman, est aujourd’hui très populaire. Elle repose sur la difficulté de factoriser un grand entier en ses facteurs premiers.

On choisit deux nombres premiers distincts p et q, puis on calcule :

n := p · q

On définit :

ϕ(n) = (p - 1)(q - 1)

On choisit un entier c premier avec ϕ(n) et on calcule son inverse modulo ϕ(n) :

d := c⁻¹ mod ϕ(n)

La propriété suivante est vérifiée :

∀ x ∈ Z/nZ, (x^c)^d ≡ x mod n

Les entiers n et c sont publics, tandis que d est secret.

Le codage d’un message M < n consiste à calculer :

Mcod := M^c mod n

Le décodage se fait en calculant :

(Mcod)^d mod n = M

1. Écrivez une procédure CRSA(M,c,n) qui code un message M avec la méthode RSA et les clés publiques c et n. Utilisez l’opérateur ^ pour l’élévation à la puissance modulo.

2. Écrivez une procédure DRSA(CM,d) qui décode un message codé CM avec la clé privée d.

3. Pour tester, prenez :

• p = 47, q = 59, c = 157, d = 17.
• Montrez qu’il est facile de casser ce code avec Maple.
• Essayez aussi avec des nombres plus grands :
• p = 37866809061660057264219253397
• q = 260 - 173 (attention, cette valeur semble incomplète dans la source)
• c = 101
• d = 13399813988306020923532260412972837706866401322

Notez que la factorisation de nombres de moins de 400 bits est aujourd’hui possible, donc pour garantir la confidentialité, il faut utiliser des clés d’au moins 512 bits.

Résultats attendus

• Les procédures code et decode doivent permettre une conversion fidèle entre texte et nombres.
• La procédure est_super doit correctement identifier les suites super croissantes.
• La procédure resout doit retrouver la représentation binaire du message à partir de la somme et de la suite super croissante.
• Les procédures Csac et Dsac doivent coder et décoder correctement des messages avec la méthode du sac à dos, notamment pour les données fournies.
• Les procédures CRSA et DRSA doivent coder et décoder un message selon RSA, en respectant la propriété (M^c)^d ≡ M mod n.
• La vérification des propriétés mathématiques (inversibilité, primalité, etc.) doit être confirmée pour les exemples donnés.

Pièges courants

• Ne pas vérifier que la suite est bien super croissante avant d’appliquer l’algorithme de résolution du sac à dos.
• Confondre la clé publique et la clé privée dans la méthode du sac à dos (clé publique = a, clé privée = u).
• Oublier que w doit être inversible modulo m (pgcd(w,m) = 1).
• Dans RSA, choisir un c non premier avec ϕ(n) empêche de calculer l’inverse d.
• Ne pas respecter la condition M < n lors du codage RSA.
• Utiliser des clés trop petites pour RSA, ce qui rend le cryptage facilement cassable.
• Ne pas convertir correctement les messages en binaire avant le cryptage dans la méthode du sac à dos.