Page sur un cryptage utilisant un groupe fini

Le sujet de mathématiques générales des épreuves écrites de l’agrégation 2007 comporte deux parties de cryptographie amusante, qui utilisent des résultats élémentaires de théorie des groupes finis.

Les trois parties suivantes modifient le cryptage précédent pour le faire passer à travers la moulinette d’une courbe cubique, mais je ne suis pas allé jusque là, je ne vais donc pas le traiter ici. Michel Coste en propose une correction complète.

Attention, le cryptage proposé ici est peu robuste.

On se place dans un groupe fini G de cardinal N≠0.

Détermination de l’inverse d’un élément d’un groupe

L’algorithme final nécessite le calcul de l’inverse d’un élément d’un groupe, on va voir trois méthodes.

Calcul direct

Je choisis a dans G.

Selon le théorème de Lagrange, $a^N=1$, donc $a^{N-1}a=1$, autrement dit, $a^{N-1}$ est l’inverse de a.

Il suffit de calculer N−1 fois la puissance de a pour obtenir son inverse, ce qui peut être vite pénible.

Utilisation de la base 2

En fait, il est plus simple de décomposer N−1 en base 2, cela va diminuer le nombre d’opérations.

Soit $N-1=\sum _{i=0}^k{x}_i{2}^i$ avec x_i∈{0;1}, le dernier x_k n’est pas nul.

Maintenant, on va calculer la suite suivante :

a₀=1, b₀=a, et par récurrence, $a_{i+1}=a_i{b}_i^{x_i}$ et $b_{i+1}=b_i^2$ pour i de 0 à k.

Donc $a_1=a_0{b}_0^{x_0}=a^{x_0}$, $b_1=b_0^2=a^2$, ensuite $a_2=a_1{b}_1^{x_1}=a^{x_0}{a}^{2x_1}=a^{x_0+2x_1}$, $b_2=b_1^2=a^4$.

Par récurrence immédiate, on a $a_{i+1}=a^{\sum _{j=0}^i{x}_j{2}^j}$ donc $a_{k+1}=a^{N-1}=a^{-1}$, et $b_i=a^{2^i}$.

L’intérêt est qu’au lieu de N−1 opérations on en effectue 2k+2, qui est de l’ordre de 2log₂(N).

Le programme que j’ai utilisé sur ma calculatrice est lisible ici. Il ne calcule pas la décomposition en base 2 de N−1, ce que fait en revanche celui-ci mais pour n’importe quelle base.

Utilisation de l’égalité de Bézout

Les deux parties précédentes fonctionnent quel que soit le groupe, on peut ruser quand on travaille dans $\frac{\mathrm{\mathbb{Z}}}{n\mathrm{\mathbb{Z}}}$ en utilisant l’égalité de Bézout quand a est premier avec n, autrement dit quand leur PGCD vaut 1, soit quand $a\in {\left(\frac{\mathrm{\mathbb{Z}}}{n\mathrm{\mathbb{Z}}}\right)}^{\times }$.

Ainsi, il existe u et v dans ℤ tels que un+va=1, autrement dit le reste de la division de v par n est l’inverse de a dans $\frac{\mathrm{\mathbb{Z}}}{n\mathrm{\mathbb{Z}}}$.

Pour trouver un couple (u;v), il suffit d’appliquer l’algorithme d’Euclide à a et n, on pose r₀=a : n=q₀r₀+r₁, ensuite r₀=q₁r₁+r₂ etc. jusqu’à ce que r_i+1=0. On doit avoir r_i=1 et r_i−2=q_i−1r_i−1+1.

Pour trouver les coefficients u et v, il faut multiplier des matrices 2×2.

En effet, on a : $\left[\begin{array}{cc}0& 1\\ 1& -q_0\end{array}\right]\left[\begin{array}{c}n\\ r_0\end{array}\right]=\left[\begin{array}{c}{r}_0\\ r_1\end{array}\right]$, $\left[\begin{array}{cc}0& 1\\ 1& -q_1\end{array}\right]\left[\begin{array}{c}{r}_0\\ r_1\end{array}\right]=\left[\begin{array}{c}{r}_1\\ r_2\end{array}\right]$, et ainsi de suite.

Il suffit donc de calculer $\left[\begin{array}{cc}0& 1\\ 1& -q_{\mathrm{i}}\end{array}\right]\dots \left[\begin{array}{cc}0& 1\\ 1& -q_2\end{array}\right]\left[\begin{array}{cc}0& 1\\ 1& -q_1\end{array}\right]\left[\begin{array}{cc}0& 1\\ 1& -q_0\end{array}\right]$ pour obtenir sur la ligne du bas les valeurs de u (à gauche) et de v (à droite) une fois qu'on a obtenu r_i+1=1. En fait, seul v nous intéresse et de plus, on peut très bien se limiter aux restes des divisions par n. Le programme pour Ti86 est ici.

Exemple

Le sujet proposait de calculer l’inverse de 5 dans $\left({\left(\frac{\mathrm{\mathbb{Z}}}{148\mathrm{\mathbb{Z}}}\right)}^{\times },\times \right)$.

En appliquant le deuxième algorithme, le nombre d’inversibles de $\frac{\mathrm{\mathbb{Z}}}{148\mathrm{\mathbb{Z}}}$ est donné par l’indicatrice d’Euler : N=ϕ(148)=72. En effet, si les facteurs premiers de N sont les p_i, i de 1 à m, $\varphi \left(N\right)=N\times \prod _{i=1}^m\left(1-\frac{1}{p_i}\right)$. Les deux diviseurs de 148 sont 2 et 37, donc $\varphi \left(148\right)=148\left(\frac{1}{2}\right)\left(\frac{36}{37}\right)=72$.

L’algorithme demande N−1=71=1000111₂, donc k=6.

On obtient ce tableau, modulo 148 :

1

1

1

0

0

0

1

a0=1

a1=5

a2=125

a3=129

a4=129

a5=129

a6=129

a7=89

b0=5

b1=25

b2=33

b3=53

b4=145

b5=9

b6=81

b7=?

Le sujet demandait de vérifier le calcul à l’aide de l’égalité de Bézout : 148=5×29+3 donc 2×148=5×58+6=5×59+1, soit dans $\frac{\mathrm{\mathbb{Z}}}{148\mathrm{\mathbb{Z}}}$, 0=5×59+1, or 59+89=148, donc l’inverse de 5 est 89.

Le cryptage

Comment il marche

On se place dans $\frac{\mathrm{\mathbb{Z}}}{n\mathrm{\mathbb{Z}}}$.

On a un message t, encodé dans un nombre entier. On choisit un nombre π dans le groupe G, et on calcule π^e sa puissance e, e devant rester secret. Toute la faiblesse du cryptage réside dans la facilité de retrouver e, il s’agit du logarithme discret.

π et π^e sont publics, t et e sont privés.

On choisit un nombre k<n et on transmet le couple α=π^k et β=tπ^ek.

Pour retrouver le message t, on calcule ${\alpha }^{-e}\beta ={\left({\pi }^k\right)}^{-e}t{\pi }^{ek}=t$. On a donc besoin de calculer l’inverse de α^e dans le groupe G.

Noter que le choix de k est libre, ce qui rend le cryptage moins sensible à l’attaque par la méthode des fréquences.

Exemples

Le message du sujet

Le sujet proposait de décrypter le message suivant (16,17) (18,24) (28,22) (17,21) (23,23) (24,8). On est dans $\frac{\mathrm{\mathbb{Z}}}{29\mathrm{\mathbb{Z}}}$ qui est un corps, 1=A, 2=B, … 26=Z, 27=« » et 28=«.» ; et de plus, on nous donnait comme information que π=2 et que π^e=18.

Cherchons d’abord e, les calculs se font modulo 29.

e	1	2	3	4	5	6	7	8	9	10	11
2e	2	4	8	16	3	6	12	24	19	9	18

Donc e=11.

Voici comment le décoder :

α	16	18	28	17	23	24
α11	25	19	28	12	20	16
α−11	7	26	28	17	16	20
β	17	24	22	21	23	8
α−11β	3	15	7	9	20	15
Lettre	C	O	G	I	T	O

Hu hu, le sujet se moque gentiment du candidat.

Autres messages

J’ai encodé avec ce programme (source en C), qu’il faut utiliser comme suit : echo 'essaie donc.'|./encryptage 29 3 11, avec N=29, π=3 et e=11. Il donne une paire de trop, visiblement le caractère nul est aussi encodé.

Voici le programme en C (source en C) pour décrypter les messages. La version 2 (code source en C) n’est pas limitée aux 28 caractères du sujet. Notez que les deux méthodes sont codées ; par défaut on utilise Bézout, pour accéder à l’autre utilisant ϕ, il faut ajouter un argument bidon après les trois autres.

echo "(16,17) (18,24) (28,22) (17,21) (23,23) (24,8)"|./decryptage 29 2 18 pour celle utilisant Bézout, et echo "(16,17) (18,24) (28,22) (17,21) (23,23) (24,8)"|./decryptage 29 2 18 glut pour celle du sujet.

Sans utiliser les codes ci-dessus, décodez les messages suivants :

Dans le même cas que ci-dessus, (2,4) (8,16) (18,5) (19,15) (26,7).

Maintenant, π=7 et π^e=25. Trouvez e pour décrypter (1,13) (1,9) (24,28) (7,3) (23,25) (16,18) (24,14) (24,19) (1,5) (7,8) (7,17) (20,16).

On se rend compte qu’on est assez limité avec les 26 lettres, le point et l’espace. Or, le petit script suivant montre que 2¹⁶+1=257 est premier, autrement dit qu’on peut encoder l’ASCII à 8 bits. Les 2ⁿ+1 sont appelés nombres de Fermat si l’exposant est lui-même une puissance de 2.

for (( i=0 ; $i<=20 ; i=$i+1 )) ; do factor `echo "2^$i+1"|bc -ql`;done

2i+1	2	3	5	9	17	33	65	129	257	513	1025	2049	4097	8193	16385	32769	65537	131073	262145	524289	1048577
facteurs premiers	2	3	5	32	17	3.11	5.13	3.43	257	33.19	52.41	3.683	17.241	3.2731	5.29.113	32.11.331	65537	3.43691	5.13.37.109	3.174763	17.61681

Voici donc une version légèrement modifée (source en C) du précédent, travaillant dans ce qu’on veut : les caractères ne sont plus codés par les premiers entiers, mais par l’ASCII. Cette fois, les capitales et les minuscules ne se valent plus et on peut même encoder des caractères utf8, mais ça fait des choses bizarres. La dernière paire est toujours en trop.

Cette fois, π=7 et π^e=132. Trouvez e pour décrypter le message suivant :

(123,27) (86,26) (182,214) (112,91) (87,147) (164,157) (109,37) (42,35) (201,256) (43,163) (130,83) (82,141) (94,38) (154,160) (203,196) (1,110) (22,126) (85,83) (103,187) (218,42) (206,27) (147,252) (53,70) (31,129) (43,61) (57,48) (111,35) (76,55) (71,50) (192,65) (129,54) (36,163) (156,158) (13,255) (62,105) (208,222) (76,180) (121,115) (220,202) (163,74) (9,103) (73,237) (2,230) (75,43) (64,230) (58,112) (231,49) (91,66) (227,36) (58,112) (49,194) (245,11) (45,134) (114,57) (57,73) (203,43) (194,252) (243,71) (148,240) (132,234) (139,4) (74,50) (126,144) (234,46) (64,36) (88,1) (161,34) (34,236) (111,82) (211,252) (145,186) (106,190) (71,82) (225,109) (71,233) (25,141) (102,132) (30,41) (68,137) (187,52) (198,65) (219,158) (120,198) (98,33) (37,29) (158,178) (15,27) (181,39) (198,158) (164,245) (248,128) (40,9) (155,99) (95,114) (108,29) (22,44) (203,207) (171,92) (234,126) (135,158) (198,123) (111,247) (175,99) (246,235) (80,185) (233,19) (181,220) (101,154) (51,144) (229,128) (18,125) (231,17) (152,138) (104,111) (150,202) (216,244) (218,103) (248,4) (32,253) (35,231) (193,218) (69,181) (115,143) (235,8) (92,244) (12,91) (30,68) (98,174) (183,90) (85,184) (123,171) (254,194) (173,186) (248,252) (225,237) (68,109) (141,90) (119,152) (100,117) (36,83) (38,99) (147,139) (160,131) (201,121) (128,78) (161,79) (240,173) (168,142) (93,232) (216,200) (226,76) (141,199) (220,201) (225,207) (239,51) (248,119) (92,9) (33,174) (131,113) (239,144) (107,7) (99,9) (228,92) (1,101) (93,216) (157,51) (230,42) (6,171) (99,79) (165,107) (141,33) (207,11) (124,117) (201,256) (143,70) (195,239) (254,170) (130,184) (54,142) (107,31) (83,244) (128,73) (181,240) (112,226) (39,200) (122,205) (113,110) (72,53) (208,173) (154,107) (246,57) (22,171) (122,205) (119,218) (150,159) (38,163) (99,106) (119,11) (106,106) (5,56) (235,86) (226,128) (1,101) (161,96) (248,225) (143,53) (116,58) (27,25) (49,139) (96,172) (119,37) (212,212) (140,197) (250,129) (51,169) (63,5) (135,47) (109,17) (134,188) (83,49) (85,13) (230,186) (114,146) (123,91) (128,80) (240,124) (117,177) (48,228) (225,142) (193,27) (240,175) (174,182) (185,1) (71,50) (1,32) (166,185) (92,97) (90,64) (163,218) (139,4) (243,230) (122,125) (61,231) (96,223) (135,52) (114,46) (93,127) (235,220) (123,104) (18,188) (143,70) (25,65) (28,191) (111,86) (248,154) (255,193) (171,103) (180,128) (23,166) (182,144) (45,134) (91,107) (155,86) (198,149) (36,38) (169,21) (253,46) (106,241) (47,242) (119,37) (159,224) (163,219) (18,10) (174,35) (106,190) (237,250) (47,253) (160,131) (173,47) (165,223) (53,53) (67,131) (13,251) (212,177) (218,190) (20,133) (123,193)

Systèmes de congruences

Un exemple

On continue dans les congruences, avec la résolutions de systèmes simples de congruences, c’est-à-dire comme suit :

$\{\begin{array}{c}x\; \equiv \; 1\; [2]\\ x\; \equiv \; 4\; [5]\end{array}$

On s’attend à trouver que x ≡ 9 [10].

Ce programme (variante sale) en scilab résout tous ces systèmes à partir du moment où les modulos sont premiers entre eux deux à deux (sinon, il plante avec une division par zéro). Le cas précédent se code en la matrice [1,2;4,5].

Comment ça marche

En fait, je réutilise, mais en scilab, l’algorithme qui trouve les coefficients de Bezout (bez pour deux termes, bezo pour plus) pour appliquer l’algorithme dans le cas suivant :

$\{\begin{array}{c}x\; \equiv \; 1\; [2]\\ x\; \equiv \; 1\; [3]\\ x\; \equiv \; 3\; [5]\\ x\; \equiv \; 3\; [7]\end{array}$

Pour l’entraînement, on cherche les coefficients de Bezout de 2, 3, 5 et 7. En fait, ça ne sert pas.

3−2=1.

Puis 5−4×1=1 donc 1×5−4×3+4×2=1.

7−6×1=1 donc 1×7−6×5+24×3−24×2=1.

2×3×5×7=210, qu’on va diviser par 2, 3, 5 et 7 respectivement, ce qui donne 105, 70, 42 et 30.

On va chercher les coefficients de Bezout pour ces nombres, en sachant qu’au départ, ils ne sont pas premiers entre eux deux à deux.

70−2×30=10 qui est le PGCD de 70 et de 30.

105−10×70+20×30=5 qui est le PGCD de 105, 70 et 30.

2×3=6 et 6−5=1, donc on va choisir les coefficients suivants, puisque 42×3=126 et que 25×5=125 :

3×42−25×(105−10×70+20×30)=1 soit 126−2625+17500−17500.

Maintenant, on fait intervenir les coefficients connus des équations :

modulo	2	3	5	7
	105	70	42	30
Bezout	−25	250	3	−500
produit	−2625	17500	126	−15000
coef	1	1	3	3
produit	−2625	17500	378	−45000

On additionne les quatre termes de la dernière ligne, on obtient donc 73 modulo 210.

Maison