Algorithmique Algébrique :
SageMath TP-crypto
Mark Asch - LAMFA/UPJV
2016–2017
Algorithmique Algébrique 2016-17
Exercice : Théorie des nombres
La cryptographie à clef publique utilise nombruex
concepts de la théorie des nombres, dont :
1. Nombres premiers.
2. PGCD.
3. Congruences
4. Fonction φ d’Euler
Algorithmique Algébrique 2016-17 1
Exercice : nombres premiers
– Rappeler le définition d’un nombre premier.
– Utiliser la commande primes first n() afin de
trouver les 20 premiers nombres premiers.
Algorithmique Algébrique 2016-17 2
Exercice : les PGCD
– Rappeler la définition d’un plus grand commun divi-
seur de a et b.
– Calculer le PGCD de deux nombres premiers quel-
conques.
Algorithmique Algébrique 2016-17 3
Exercice : congruences
– Rappel : les congruences nous permettent de décrire
la situation où deux entiers ont le même reste après
division par un entier non-nul,
a≡b( mod n)
où n est le reste.
– Calculer le reste de 23 divisé par 5 ; calculer le reste
de 8 divisé par 5 et en déduire la congruence.
Algorithmique Algébrique 2016-17 4
Exercice : Fonction φ d’Euler
– Ecrire un programme SAGE qui, pour un entier
donné, N, donne une liste d’entiers n, premiers entre
eux avec 1 ≤ n ≤ N. Calculer le nombre d’entiers
co-premiers entre 1 et 20.
– Comment peut-on, sans explicitement générer la liste,
compter le nomber de co-premiers entre 1 et N ?
Définition. Soit n ∈ Z positif. La fonction phi d’Euler,
φ(n), compte le nombre d’entiers a, avec 1 ≤ a ≤ n tels
que gcd(a, n) = 1.
– La fonction φ joue un rôle important en théorie de
l’information et plus particulièrement en cryptologie
(voir RSA plus loin).
– La commande de SAGE euler phi(n) calcule la
fonction phi d’Euler. Comparer avec le résultat de
votre programme.
Algorithmique Algébrique 2016-17 5
Exercice : crypto de César
– le principe :
+ ---------+ encrypt +------------+ decrypt +-----------+
| plaintext| ------> | ciphertext | ------> | plaintext |
+----------+ +------------+ +-----------+
– le code ASCII (American Standard Code for Infor-
mation Interchange) : soit Σ = {A, B, C, . . . , Z}
les lettes capitales et Φ = {65, 66, 67, . . . , 90} les
encodages ASCII corréspondants
– l’application f : Σ −→ Φ est décrite par le tableau
+----------------------------------------+
| A B C D E F G H I J K L M |
| 65 66 67 68 69 70 71 72 73 74 75 76 77 | +-------
| N O P Q R S T U V W X Y Z |
| 78 79 80 81 82 83 84 85 86 87 88 89 90 |
+----------------------------------------+
Algorithmique Algébrique 2016-17 6
– César : l’alphabet de chiffre est obtenu de l’alpha-
bet standard par le décalage d’un nombre fixe de
positions, donc 25 chiffres possibles
sage: alphabet = ’ABCDEFGHIJKLMNOPQRSTUVWXYZ’
sage: message = ’MATHEMATIQUES’
– chiffrement par décalage/substitution mono-
alphabétique : on décale par une valeur entre 1
et 25
sage: def encode(m, cle):
L=”
for x in m:
s=’ ’.join(alphabet[([Link](x)+cle)%
L = L + s
return L
– la substitution :
A B C D E F G H I J K L M N O P Q
E F G H I J K L M N O P Q R S T U
Algorithmique Algébrique 2016-17 7
sage: encode(message, 4)
’QEXLIQEXMUYIW’
– décodage :
sage:def decode(c, cle):
L=”
for x in m:
s=’ ’.join(alphabet[([Link](x)+cle)%
L = L + s
return L
sage: decode(’QEXLIQEXMUYIW’, 4)
’MATHEMATIQUES’
sage: encode(’QEXLIQEXMUYIW’, -4)
’MATHEMATIQUES’
– décryptage
sage: def casse(c):
for cle in range(26):
print cle, decode(c, cle)
sage: casse(’QEXLIQEXMUYIW’)
0 QEXLIQEXMUYIW
1 PDWKHPDWLTXHV
Algorithmique Algébrique 2016-17 8
2 OCVJGOCVKSWGU
3 NBUIFNBUJRVFT
4 MATHEMATIQUES
5 LZSGDLZSHPTDR
6 KYRFCKYRGOSCQ
7 JXQEBJXQFNRBP ...
Algorithmique Algébrique 2016-17 9
Exercice : le système RSA (exemple
de Bob et Alice)
– Alice choisit n = pq où p et q sont premiers
sage: n=77
sage: F = factor(77); F
11 * 7
sage: list(F)
[(7, 1), (11, 1)]
sage: p = 7; q = 11;
– Alice choisit e qui est co-premier avec φ(n) = (p −
1)(q − 1)
sage: phi = (p - 1)*(q - 1); phi
60
sage: e=13
sage: gcd(e,phi)
1
– Partie publique : (n, e) = (77, 13)
Algorithmique Algébrique 2016-17 10
– Alice calcule d = 1/e mod (φ(n))
sage: bezout = xgcd(e, phi); bezout
(1, -23, 5)
sage: d = mod(bezout[1], phi) ; d
37
– Partie privée : (p, q, d) = (7, 11, 37)
Algorithmique Algébrique 2016-17 11
Exercice : le système RSA (envoi d’un
message simple)
– Bob veut envoyer le message 0 < m < n à Alice.
Ex. : Bob veut envoyer la lettre « Z », qu’il code par
m = 26.
– Bob calcule c = me mod n
sage: m = 26
sage: c = mod (m^e,n); c
75
– Bob envoie le message crypté, c = 75, à Alice
– Alice déchiffre : m0 = cd mod n
sage: mp=mod(c^d,n); mp
26
Algorithmique Algébrique 2016-17 12
Exercice : le système RSA (exemple
réaliste)
– Etape 1 : générer les clefs publiques et privées
sage: p = (2^31) - 1
sage: is prime(p)
True
sage: q = (2^61) - 1
sage: is prime(q)
True
sage: n = p * q ; n
4951760154835678088235319297
– Trouver un entier positif qui est co-premier avec
φ(n) :
sage: phi = (p - 1)*(q - 1); phi
4951760152529835076874141700
sage: e = [Link] element(phi)
sage: while gcd(e, phi) != 1:
....: e = [Link] element(phi)
Algorithmique Algébrique 2016-17 13
...
sage: e # random
1850567623300615966303954877
sage: e < n
True
– Connaissant e et φ(n), calculer la valeur de d à l’aide
de la commande xgcd
sage: bezout = xgcd(e, phi); bezout # random
(1, 4460824882019967172592779313, -1667095708515377925087033035)
sage: d = Integer(mod(bezout[1], phi)) ; d # random
4460824882019967172592779313
sage: mod(d * e, phi)
1
– Le résultat est que notre clef publique RSA est
(n, e) = (4951760154835678088235319297, 1850567623300615966303954877)
est que la clef privée correspondante est
(p, q, d) = (2147483647, 2305843009213693951, 4460824882019967172592779313)
Algorithmique Algébrique 2016-17 14
Exercice : le système RSA (transfert
de message)
Nous voudrions envoyer le message HELLOWORLD de
façon cryptée à l’aide du cryptage RSA.
– La table ASCII donne :
+-------------------------------+
| H E L L O W O R L D |
| 72 69 76 76 79 87 79 82 76 68 |
+-------------------------------+
– On concatène tous les entiers de la table, afin d’ob-
tenir une représentation de notre message en nombre
entier,
m = 72697676798779827668.
– Faisons cela avec SAGE :
sage: m = "HELLOWORLD"
Algorithmique Algébrique 2016-17 15
sage: m = map(ord, m); m
[72, 69, 76, 76, 79, 87, 79, 82, 76, 68]
sage: m = ZZ(list(reversed(m)), 100) ; m
72697676798779827668
– Afin de crypter le message, nous prenons m à la
puissance e et réduisons le résultat modulo n
– La commande « naive » mod(a^b,n) risque d’ex-
ploser la machine dès que b est grand (disons de 20
chiffres ou plus).
– On utilise la méthode de carrés répétés, qui est
implémentée dans la fonction power mod de SAGE
sage: m = 72697676798779827668
sage: e = 1850567623300615966303954877
sage: n = 4951760154835678088235319297
sage: c = power mod(m, e, n); c
630913632577520058415521090
– Déchiffrement : afin de récupérer le plaintext, on
monte c à la puissance d et on réduit le résultat par
modulo n
sage: m = 72697676798779827668
Algorithmique Algébrique 2016-17 16
sage: c = 630913632577520058415521090
sage: d = 4460824882019967172592779313
sage: n = 4951760154835678088235319297
sage: power mod(c, d, n)
72697676798779827668
sage: power mod(c, d, n) == m
True
– Remarquer que la dernière valeur est bien égal à la
valeur de m, notre plaintext
Algorithmique Algébrique 2016-17 17
Exercice : Algorithme de Diffie-Merkle
1
– Tout d’abord, on génère la clé privée
(N, A, {a1, a2, · · · , an})
– D’abord, on génère une séquence super-croissante :
sage: A sc = [2, 7, 11, 21, 42, 89, 180, 354]
X8
– On calcule la somme : ai = 706 puis on choisit
i=1
un nombre N plus grand que cette somme :
sage: sA = sum(A sc); sA
sage: N = 881
–
– Puis on choisit un nombre A < N avec
gcd(A, N ) = 1 :
sage: A = 588
sage: gcd(A,N) == 1
– La clé privée est générée : c’est (N, A, {a1, a2, · · · , an})
Algorithmique Algébrique 2016-17 18
– À présent on calcule la clé publique
{b1, b2, · · · , bn} avec bi ≡ Aai mod N :
sage: b0 = (A sc[0]*A) % N
sage: b1 = (A sc[1]*A) % N
sage: b2 = (A sc[2]*A) % N
sage: b3 = (A sc[3]*A) % N
sage: b4 = (A sc[4]*A) % N
sage: b5 = (A sc[5]*A) % N
sage: b6 = (A sc[6]*A) % N
sage: b7 = (A sc[7]*A) % N
sage: b=[b0, b1,b2,b3,b4,b5,b6,b7]; b
[295, 592, 301, 14, 28, 353, 120, 236]
– Alice veut chiffrer le message "a".
– Elle traduit le message "a" en binaire (en utilisant
ASCII (=97) ou UTF-8) :
sage: m = 01100001
n
X
– Elle calcule le message chiffré c = mibi :
i=1
sage: c = 0 * 295...
+ 1 * 592...
+ 1 * 301...
Algorithmique Algébrique 2016-17 19
+ 0 * 14
+ 0 * 28
+ 0 * 353
+ 0 * 120
+ 1 * 236
sage: c
1129
– Elle envoie alors 1129 à Bob.
– Pour déchiffrer le message chiffré 1129, Bob calcule
p ≡ A−1c mod N :
sage: p = 1129 * 442 % 881; p
372
n
X
– Maintenant, Bob résout l’instance p = xiai
i=1
avec un algorithme glouton.
– Il décompose p = 372 en sélectionnant le ai le
plus grand qui est inférieur ou égal à 372. Puis
il recommence jusqu’à obtenir 0 :
sage: 372 - 354
18
sage: 18 - 11
7
Algorithmique Algébrique 2016-17 20
sage: 7 - 7
0
– Les éléments sélectionnées de notre sac privé
{a1, a2, · · · , an}, c’est-à-dire a2, a3, a8 donne
le message initial :
sage: w = 01100001
– qui correspond au message "a".
Algorithmique Algébrique 2016-17 21
Algorithme de Diffie-Merkle 2
Nous allons écrire un script avec des fonctions pour
l’algorithme de Diffie-Merkle...
Définition. Le problème de sous-ensemble est un pro-
blème de sac à dos où pour une suite d’e n entiers donnés
(a1, a2, . . . , an) et un entier N donnés, nous cherchons le
sous-ensemble J de la liste tel que la somme des éléments
dans J est égal à N.
Exemple. Pour la suite (14, 28, 56, 82, 90, 132, 197, 284, 341, 455)
est-ce que le nombre 516 peut être exprimé comme la
somme d’un sous-ensemble de ces valeurs ? Réponse : non,
mais 515 peut être exprimé de 3 façons,
515 = 14 + 28 + 132 + 341
= 28 + 56 + 90 + 341
= 14 + 82 + 90 + 132 + 197.
Ceci est une problème « dur » de point de vue des calculs (à
Algorithmique Algébrique 2016-17 22
partir d’une centaine d’éléments), et il n’y pas une meilleure
façon que de procéder par tatonnement.
– un algorithme pour résoudre le problème de « sous-
ensemble » dans une séquence super-croissante :
– étape 1 : soit a la plus grande valeur dans la
séquence inférieur ou égal à N ; si a = N alors
STOP avec succès.
– étape 2 : soit a0 la plus grande valeur dans la
séquence inférieur ou égal à N − a ; si a + a0 = N
alors STOP avec succès.
– étape 3 : soit a00 la plus grande valeur dans la
séquence inférieur ou égal à N − a − a0 ; si a +
a0 + a00 = N alors STOP avec succès.
– étape n : etc.
L’algorithme dans une fonction sage :
def sc solve(lst,N):
M=N;res=[]
for i in reversed(lst):
if i<=M:
Algorithmique Algébrique 2016-17 23
res = [i] + res
M = M - i
if M<>0:
print "Pas de solution !"
else:
return res
Algorithmique Algébrique 2016-17 24
Exercice : Algorithme de Diffie-Merkle
3
– Alice choisit une séquence super-croissante :
sage: a=[2, 3, 7, 25, 67, 179, 356, 819]
– Alice choisit une valeur N et un entier w co-premier
avec N
sage: N = 1600
sage: w = 57
– Alice multiplie chaque valeur de la séquence par w
et calcule le reste modulo N :
sage: b = [(x*w)%N for x in a]; b
– le résultat est sa clef publique
[114, 171, 399, 1425, 619, 603, 1092, 283]
Algorithmique Algébrique 2016-17 25
– Bob veut envoyer un message à Alice - il le décompose
en blocs de 8 bits. Supposons qu’un des blocs est
10110010. Il chiffre cela utilisant la clef publique :
114 + 399 + 1425 + 1092 = 3030
sage: m = [1, 0, 1, 1, 0, 0, 1, 0]
sage: c = sum(x*y for x,y in zip(m,b)); c
3030
– Alice procède à déchiffrer : elle multiplie par
w−1 ( mod N ) et résoud le résultat avec la sé-
quence super-croissante - elle calcule alors
57−1 ( mod 1600) = 393
et puis
3030 × 393 ( mod 1600) = 390
et finalement elle résoud le problème de sous-
ensemble pour 390 utilisant sa séquence super-
croissante, pour trouver
390 = 2 + 7 + 25 + 356
Algorithmique Algébrique 2016-17 26
d’où elle en déduit que le bloc de message est
10110010.
sage: s = sc solve(a,mod(c/w,N)); s
[2, 7, 25, 356]
sage: [[Link](i) for i in a]
[1, 0, 1, 1, 0, 0, 1, 0]
Algorithmique Algébrique 2016-17 27
