[PDF] [PDF] Chiffrement affine : définition - LIPN

View - Download [PDF] Chiffrement affine : définition - LIPN

Previous PDF

Next PDF

SeCrypt

Travaux diriges : Cryptanalyse du chirement ane

Chirement ane : denition

Lechirement par decalageest un cas particulier duchirement par substitution dans lequel on utilise une translation comme substitution. Un autre cas particulier du chirement par substitution est lechirement ane. Dans ce procede, on limite les fonctions de chirement a certaines fonctions de la forme E (a;b)(x) =ax+bmod 26 (1) oua;b2Z26. Ces fonctions sont appelees desfonctions anes, d'ou l'on a tire le nom du procede. On remarque que l'on retrouve le chirement par decalage poura= 1. Pour que l'operation de dechirement soit possible, il est necessaire que la fonction ane soit bijective. Autrement dit, pour touty2Z26, l'equation ax+b=ymod 26 (2) doit avoir une, et une seule, solutionx. L'equation (2) est equivalente a ax=ybmod 26:(3) Lorsqueyparcourt l'ensembleZ26,ybdecrit egalement ce m^eme ensemble. Donc, il sut d'etudier l'equationax=zmod 26 pour toutz2Z26. On demontre que cette equation admet une unique solution pour toutzxe, si, et seulement si,pgcd(a;26) = 1 (oupgcdest le plus grand diviseur commun de ses arguments); au passage on dit quea et 26 sontpremiers entre eux. En eet siaet 26 sont premiers entre eux (et seulement dans ce cas), alorsaadmet un inversea12Z26(i.e.,aa1=a1a= 1 mod 26), et l'unique solution de l'equationax=zmod 26 estx=a1zmod 26. En particulier, x=a1(yb) mod 26 est l'unique solution a l'equation (2). Supposons donc queaet 26 sont premiers entre eux. On vient de voir que, dans ce cas, l'applicationE(a;b)est inversible. Sa bijection reciproque est donnee parD(a;b)(y) = a

1(yb) mod 26. Nous pouvons maintenant decrire completement le chirement ane.

Les ensembles de textes clairsPet chiresCsont tous les deux egaux aZ26. L'espace des clefs secretes est quant a lui donne par

K:=f(a;b)2Z26Z26:pgcd(a;26) = 1g:(4)

Pour tout (a;b)2 K, on denit

E (a;b)(x) :=ax+bmod 26 (5) et D (a;b)(y) :=a1(yb) mod 26:(6) 1

1 Exercice : Mise en uvre du chirement ane

(CORRECTION)

Soit (a;b) = (7;3).

1. Montrer que (a;b)2 Ket calculera1dansZ26.Correction :Pour montrer que

(a;b) est une clef valide, il sut de verier queaet 26 sont premiers entre eux, ce qui est ici le cas car 7 est un nombre premier.

2. Verier par calcul queD(a;b)(E(a;b)(x)) =xpourxquelconque dansZ26.Correc-

tion :Il faut que l'on calculeb=3 dansZ26:b= 263 = 23 mod 26. Il faut egalement calculera1= 71. Il s'agit de trouver un elementb2Z26pour lequel ab= 1 mod 26. Or on a 715 = 105 = 426 + 1, d'ou 715 = 1 mod 26 et a

1= 15. Calculons maintenant (modulo 26).

E (a;b)(x) = 7x+ 3 D (a;b)(E(a;b)(x)) =D(a;b)(7x+ 3) = 15(7x+ 3 + 23) = 15(7x+ 0) =x :

3. Chirer le mothotavec cette clef.Correction :On commence par coder les lettres

en element deZ26de la facon habituelle. On a alorsh$7,o$14 ett$19. Puis on applique la regle de chirement.

77 + 3 mod 26 = 52 mod 26 = 0;

714 + 3 mod 26 = 101 mod 26 = 23;

719 + 3 mod 26 = 136 mod 26 = 6:

On obtient donc le texte chire 0 23 6 qui, en lettres, donneaxg. 4. Enumerer lesa2Z26qui sont premiers avec 26.Correction :Il est facile de verier que les elements deZ26qui sont premiers avec 26 sont 1;3;5;7;9;11;15;17;19;21;23 et 25. En eet ce sont les seuls elements deZ26qui ne sont divisibles ni par 2 ni par

13 (les seuls diviseurs dierents de 1 deZ26).

5. Pour chacun des elementsa2Z26premiers avec 26, calculer son inverse (modulo

26).CorrectionPoura2 f1;3;5;7;9;11;15;17;19;21;23;25g, il s'agit de trouver

b2Z26tel queab= 1 mod 26 ou, en d'autres termes,ab=q26+1, pour un certain q(c'est-a-dire que le reste deabpar 26 est egal a 1, doncabest congru a 1 modulo

26). On obtient ainsi

aa 111
39
521
715
93
1119
157
1723
1911
215
2317

2525(7)

2

6. Calculer le nombre de clefs possibles. Qu'en deduisez-vous quant a la solidite de ce

procede de chirement?CorrectionLe nombre de clef possible est le nombre dea premiers avec 26 (qui est egal a 12 d'apres la question precedente) multiplie par 26 (le nombre deb) soit 1226 = 312. Le nombre de clefs est trop petits pour assurer la solidite du cryptosysteme.

2 Exercice : Cryptanalyse du chirement ane (COR-

RECTION)

Dans cet exercice, on s'interesse a une technique de cryptanalyse permettant de casser un procede de chirement ane. Cette technique est basee sur l'analyse des frequences d'oc- currence des lettres dans un texte ecrit dans une langue donnee (par exemple, l'anglais ou le francais). Dans le cas present, on eectue une hypothese simplicatrice : on suppose que le texte clair estun message redige en anglais sans ponctuations ni espaces. Plusieurs personnes ont estime la probabilite d'apparition des vingt-six lettres de l'alpha- bet en faisant des statistiques sur de nombreux romans, magazines et journaux quotidiens ecrits en anglais. Les estimations suivantes sur la langue anglaise ont ete obtenues par

Beker et Piper.

Frequences d'occurrences des lettres dans les textes ecrits en anglais (Beker & Piper)lettre probalettre proba

a0;082n0;067b0;015o0;075c0;028p0;019d0;043q0;001e0;127r0;060f0;022s0;063g0;020t0;091h0;061u0;028i0;070v0;010j0;002w0;023k0;008x0;001l0;040y0;020m0;024z0;001Nous allons utiliser ces statistiques pour dechirer un cryptogramme provenant d'un mes-

sage ecrit en anglais. Supposons donc qu'Oscar ait intercepte le message suivant (sans espaces ni signes de ponctuation) :

1. Calculer le nombre d'occurrences de chacune des lettres de l'alphabet dans ce mes-

3 sage.Correction : lettre frequencelettre frequence A2N1 B1O1 C0P2 D6Q0 E5R8 F4S3 G0T0 H5U2 I0V4 J0W0 K5X2 L2Y1 M2Z0

2. Expliquer pourquoi on peut supposer que la lettre R se dechire en E.Correction :

Le caractere le plus frequent est R (8 occurrences) suivi de D (6 occurrences), et, E, F et K (5 occurrences chacun). Comme en anglais la lettre la plus courante est E, on peut supposer que R se dechire en E. La seconde lettre la plus frequence est

T qui pourrait donc se chirer en D.

3. Supposons que la lettre D se dechire en T (et R en E). Trouver la clef (a;b)

qui en resulte, et expliquer pourquoi cette clef n'est pas valide.Correction :En transformant les lettres en des nombres, dire que R se dechire en E est equivalent aE(a;b)(17) = 4 (R= 17,E= 4). Dire que D se dechire en T signieE(a;b)(3) = 19 (D= 3,T= 19). En se souvenant queE(a;b)(x) =ax+b, oua;bsont inconnus, on obtient un systeme de deux equations a deux inconnues

4a+b= 17

19a+b= 3:

Il nous faut resoudre ce systeme dansZ26. Prenons la seconde equation 19a+b= 3 soita= 11(3b) (car 191= 11). On a donca= 3311b= 711bmod 26. On injecte cela dans la premiere equation et il en resulte que l'on a 4(711b)+b= 17 soit 2843b= 17,217b= 17 (car 28 = 2 mod 26 et 43 = 17 mod 26) ce qui est equivalent a17b= 15. Or17 = 2617 = 9, et on a donc 9b= 15. On resoud cela pour trouverb= 19 (en eet 91= 3, donc on doit calculerb= 315 = 45 = 19 mod 26). On trouve alorsa= 71119 mod 26 = 6. Cette clef n'est pas valide caraet 26 ne sont pas premiers entre eux.

4. Supposons que la lettre R se dechire en E, et K en T. Trouver la clef (a;b) qui en

resulte, et expliquer pourquoi cette fois-ci la clef est valide.Correction :Cette fois on obtienta= 3 etb= 5. En eet, il s'agit de resoudre dansZ26le systeme de deux equations a deux inconnuesaetb:

4a+b= 17

19a+b= 10

puisque la lettreKcorrespond au nombre 10 (4$E, 17$R, 19$T). De l'equation 19a+b= 10, on en deduit quea= 191(10b) = 11(10b) (puisque 4 19

1= 11) = 11011b= 611b(puisque 110 = 6 mod 26) = 6 + 15b(puisque

11 = 2611 = 15 mod 26). En injectant cela dans l'equation 4a+b= 17, on

obtient4(6 + 15b) +b= 17 ,24 + 61b= 17 ,24 + 9b= 17 (puisque 61 = 9 mod 26) ,9b= 1724 ,9b= 17 + 2624 ,9b= 19 ,b= 9119 ,b= 319 ,b= 57 ,b= 5 d'oua= 6 + 155 = 6 + 75 = 81 = 3 mod 26. Enn 3 est premier avec 26. Donc (3;5) est une clef valide.

5. En vous basant sur ce que vous avez trouve pouraa la question precedente, calculer

a

1(dansZ26). Une fois cela fait, dechirer le message an de verier qu'il s'agit bien

d'un texte ecrit en anglais.Correction :Le dechirement est donne parD(a;b)(y) =

9y19 (car 31= 9 qui avait ete calcule au prealable). Comme19 = 2619 = 7

mod 26, on aD(a;b)(y) = 9y+ 7. On dechire les lettres num lettreD (a;b)(num)lettre correspondante0A7H 1B16Q 2C25Z 3D8I 4E17R
5F0A 6G9J 7H18S 8I1B 9J10K

10K19T

11L2C

12M11L

13N20U

14O3D

15P12M

16Q21V

17R4E

18S13N

19T22W

20U5F

21V14O

22W23X

23X6G

24Y15P

25Z24Y(8)

En utilisant cette fonction de dechirement sur le message chire initial on obtient : 5 algorihmsarequitegeneraldenitionsofarithmeticprocesses . Ce message clair signiant \ Les algorithmes denissent de maniere assez generale les calculs arithmetiques ". 6quotesdbs_dbs23.pdfusesText_29

[PDF] chiffrement affine pdf

[PDF] chiffrement affine java

[PDF] on a reçu le message suivant : jwpnwmrcfwmy

[PDF] cryptage affine spé maths

[PDF] déchiffrement affine

[PDF] vigenere python code

[PDF] chiffre de vigenère langage c

[PDF] vigenere python decode

[PDF] decoder vigenere sans clef

[PDF] chiffre de vigenere algorithme

[PDF] algorithme rsa exemple

[PDF] algorithme rsa pdf

[PDF] algorithme rsa exercice corrigé

[PDF] cryptage rsa exemple

[PDF] cryptographie asymétrique algorithme