IUP3 - Module M64/RISC - TD : DES et Calcul Modulaire
1 Le cryptosystème DES
Pour tout mot binaire m = a1 a2 . . . a2n de longueur 2n, on note L = a1 a2 . . . an et R =
an+1 an+2 . . . a2n la moitié gauche et la moitié droite de m. Ainsi L et R sont deux mots
binaires de longueur n, et m = L R. On peut noter :
L R
Soit f : {0, 1}n → {0, 1}n une fonction quelconque, pas forcément bijective. La fonction de
Feistel associée à f est la fonction :
F : {0, 1}2n → {0, 1}2n : L R 7→ L0 R0 où L0 = R et R0 = L ⊕ f (R)
F
L R / R L ⊕ f (R)
1. Soient n = 2 et f : {0, 1}2 → {0, 1}2 définie par :
x 00 01 10 11
f (x) 01 11 10 01
a. Est-ce que f est bijective ?
b. Décrire F : {0, 1}4 → {0, 1}4. Est-ce F est bijective ? Si oui, décrire la fonction
réciproque F −1 .
2. Dans le cas général, montrer que la fonction F est toujours bijective et décrire la
fonction réciproque F −1 .
3. Le DES est, essentiellement, composé de 16 fonctions de Feistel (pour n = 32)
correspondant à 16 fonctions f différentes. Les fonctions f sont toutes calculées par la même
méthode, mais en utilisant des parties différentes de la clé (la clé est de longueur 56, on utilise
48 de ces 56 bits pour chaque fonction f ). Dans cet exercice on simule un “mini-DES” à 2 tours
sur des mots de 4 bits. Donc n = 2, et on utilise les deux fonctions f1 et f2 : {0, 1}2 → {0, 1}2 :
x 00 01 10 11 x 00 01 10 11
f1 (x) 01 11 10 01 f2 (x) 11 00 00 01
a. Chiffrer le message 1101.
b. Déchiffrer le message obtenu à la question a.
2 Théorème chinois des restes
1. Résoudre les équations : a) 17x = 10[50]; b) 35y = 10[50]; c) 35y = 11[50].
2. Démontrer le théorème suivant, appelé Théorème Chinois Qkdes restes :
Soient (n1 , . . . , nk ) k entiers premiers deux à deux et N = i=1 ni .
L’application Ψ : Z/N Z −→ Z/n1 Z × . . . × Z/nk Z définie par
Ψ(u) = [u mod n1 ; . . . ; u mod nk ]
est un isomorphisme d’anneau, d’inverse Ψ−1 définie par (en posant Ni = N/ni ) :
k
!
X
−1 −1
Ψ ([u1 , . . . , uk )) = ui .Ni .(Ni mod ni ) mod N.
i=1
1
3. Trouver tous les x entiers tels que x ≡ 4 (mod 5) et x ≡ 5 (mod 11). En déduire l’inverse
de 49 modulo 55.
4. Pour le système de résidus [3,4,5] expliciter l’isomorphisme du théorème chinois des
restes Φ : Z/60Z −→ Z/3Z × Z/4Z × Z/5Z et son inverse Φ−1 .
Application: Calculer de tête avec ce système x = (36 ∗ 43 − 39 ∗ 27 − 12)/23 sachant
que 0 ≤ x < 60.
5. Trouver les entiers dont les restes par 2, 3, 4, 5, et 6 sont respectivement 1, 2, 3, 4, 5.
3 Un algorithme à clef secrète
Soit p un nombre premier et soient a, b deux entiers non nuls choisis dans {1, . . . , p − 1}. On
note Φa,b,p la fonction de Z/pZ : Φa,b,p (x) = (a.x + b) mod p.
Pour un message dans {0, . . . , p − 1}, on considère la fonction de codage E = Φ a,b,p .
1. Expliciter la fonction de décodage D associée à E en montrant qu’elle s’écrit sous la
forme D = Φα,β,p : expliciter α et β en fonction de a et b.
2. On suppose p = 43, a = 5, b = 37; on reçoit le message E(x) = 28. Que valait x ?
3. On suppose que l’on connaı̂t a, b et p. Soit M un message de n bits avec n log2 p.
Expliquer comment crypter M avec E et donner une estimation du temps nécessaire au
cryptage de M avec E en fonction de n et p.
4. On désire maintenant utiliser les fonctions précédentes dans un système à clef privée, en
supposant que p est connu : a, b et α, β sont privés, connus par Alice et Bob seulement.
Un espion sait qu’Alice envoie en secret à Bob les 2 messages différents x1 et x2 , avec
0 ≤ x1 , x2 < p. L’espion voit donc passer sur le réseau y1 = a.x1 + b mod p et y2 =
a.x2 + b mod p.
Connaissant (x1 , y1 ) et (x2 , y2 ), montrer que l’espion peut alors facilement casser le
code.
4 Fonction φ d’Euler et inversion modulaire
On étudie ici la fonction ϕ(n), introduite par Euler, et dont les propriétés sont à la base de
la méthode RSA.
On pose ϕ(1) = 1 et pour n > 1, ϕ(n) est le nombre d’entiers m ∈ {1, . . . , n − 1} premiers
avec n (i.e. gcd(m, n) = 1).
1 Pour n = pk où p est premier et k ∈ N∗ , montrer que ϕ(n) = 1 − p1 .n.
2 Montrer que si n1 et n2 sont premiers entre eux : ϕ(n1 .n2 ) = ϕ(n1 ).ϕ(n2 ). Indication :
utiliser l’isomorphisme entre les anneaux (Z/n1 Z) × (Z/n2 Z) et (Z/n1 n2 Z).
3 En déduire que, dans Z/nZ, le cardinal du groupe des éléments inversibles est
k
Y 1
ϕ(n) = n. 1−
i=1
pi
où les pi (i = 1, . . . , k) sont les k facteurs premiers distincts de n. e déduit directement
de 1 et 2.
4 On rappelle1 que dans un groupe fini commutatif (G, ×, e) de cardinal c, on a ∀x ∈ G :
xc = e. En déduire que pour tout x inversible dans Z/nZ: xϕ(n) = 1 mod n et proposer
un algorithme de calcul de l’inverse dans Z/nZ.
Application : calculer (le plus vite possible) 22−1 mod 63 et 52001 mod 24. On pourra
utiliser: 222 mod 63 = 43; 224 mod 63 = 22.
5 Donner trois algorithmes différents pour calculer l’inverse de y modulo N = pδ11 .pδ22 . . . . pδkk ,
où les pi sont des entiers premiers distincts.
1 Propriété Dans un groupe fini commutatif (G, ×, e) de cardinal c, ∀x ∈ G : xc = e.
Preuve. Soit a un élément quelconque de G. Comme G est un groupe, a est inversible. Q Donc, l’application
Q fa
de G dans G définie par fa : x 7→ a×x est une bijection. On a donc Im(fa ) = G; d’où y∈Im(fa ) y = x∈G x.
Or y∈Im(fa ) y = x∈G a×x = an x∈G x (commutativité de ×). Ainsi an x∈G x = x∈G x, d’où an = e.
Q Q Q Q Q
