TP de Maple : Cryptographie
TP de Maple : Cryptographie
Cryptography, Algorithms · lab
Fiche de révisionGuide de TP
Rédigée à partir de ce document, puis vérifiée avant publication.
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.
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.
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.
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 :
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
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 :
m > Σ bi.w tel que pgcd(w,m) = 1, donc w est inversible modulo m.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 = 463814521w = 234203372u = 101vé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.
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.p = 37866809061660057264219253397q = 260 - 173 (attention, cette valeur semble incomplète dans la source)c = 101d = 13399813988306020923532260412972837706866401322Notez 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.
code et decode doivent permettre une conversion fidèle entre texte et nombres.est_super doit correctement identifier les suites super croissantes.resout doit retrouver la représentation binaire du message à partir de la somme et de la suite super croissante.Csac et Dsac doivent coder et décoder correctement des messages avec la méthode du sac à dos, notamment pour les données fournies.CRSA et DRSA doivent coder et décoder un message selon RSA, en respectant la propriété (M^c)^d ≡ M mod n.w doit être inversible modulo m (pgcd(w,m) = 1).c non premier avec ϕ(n) empêche de calculer l’inverse d.M < n lors du codage RSA.