TD de Cryptologie IUT Licence 3

Feuille d'exercices n1

1 Csar, Vigenre et les autres

Tous les cryptogrammes de cette feuille d'exercices ont t obtenus partir de textes franais crits par R.Queneau et sont prsents par paquets de cinq lettres, pour plus de lisibilit. L'alphabet utilis est rduitaux 26 lettres latines, les lettres accentues tant converties en leurs quivalentes non accentues, les espaceset signes de ponctuation ayant t supprims.

1.1 Transpositions

Le principe d'une transposition est de modier l'ordre des lettres du texte clair, pour obtenir le texte chir.Il existe de nombreuses manires d'eectuer ce genre de manipulations.

Exercice 1 Un exemple de transposition simple

Une transposition simple oprant par remplissage d'un rectangle en lignes et relvement par colonnes fonc-tionne comme suit : la cl est une suite de lettres, mot ou phrase, comme par exemple ECRITURE. Chacunedes lettres de la cl est numrote, partir de A, et suivant l'ordre alphabtique. Sur notre exemple, celadonne :

E C R I T U R E2 1 5 4 7 8 6 3

Lors du chirement, le texte clair est crit sur des lignes de mme longueur que la cl, ces lignes tantdisposes l'une au-dessus de l'autre pour former un rectangle :

E C R I T U R E2 1 5 4 7 8 6 3R A Y M O N D QU E N E A U E ST U N A U T E UR F A N T A S TI Q U E

On relve ensuite les colonnes dans l'ordre dtermin par les nombres associs aux lettres de la cl :AEUFQ RUTRI QSUTM EANEY NNAUD EESOA UTNUT AQ 1 . Le cryptogramme suivant

PVSNO UPNOR AYREA VDNLQ SNDEEAUEUC AEUEI TOLDG EEENU EAEMSALLAA UNFDE LNUCL ETGED UITLNLIEMC QEERE IE

a t construit suivant ce procd avec le mot-cl QUENEAU. Retrouvez le texte clair.Q 2 . Que pourrait-on faire si on ne disposait pas de la cl, mais seulement de sa longueur ? Et si on nesavait rien de la cl ?

1

1.2 Substitutions

Une subsitution consiste en le remplacement des caractres du texte clair par d'autres caractres. Mais laplace des caractres dans le message n'est pas modie. Lorsque l'on essaie de dcrypter un message chiravec un tel procd, on utilise des donnes statistiques concernant le langage utilis pour la rdaction du texteclair. Pour vous aider percer les cryptogrammes dont la cl n'est pas donne, voici par ordre dcroissantdes frquences la rpartition des lettres en franais : (source : Manuel de cryptographie, L. Sacco, Payot,1947)

E 17,76 S 8,23 A 7,68 N 7,61 T 7,30 I 7,23R 6,81 U 6,05 L 5,89 O 5,34 D 3,60 C 3,32P 3,24 M 2,72 Q 1,34 V 1,27 G 1,10 F 1,06B 0,80 H 0,64 X 0,54 Y 0,21 J 0,19 Z 0,07K 0,01 W 0,00

et celle des bigrammes :

es 305 te 163 ou 118 ec 100 eu 89 ep 92le 246 se 155 ai 117 ti 98 ur 88 nd 80en 242 et 143 em 113 ce 98 co 87 ns 79de 215 el 141 it 112 ed 96 ar 86 pa 78re 209 qu 134 me 104 ie 94 tr 86 us 76nt 197 an 139 is 103 ra 92 ue 85 sa 75on 164 ne 124 la 101 in 90 ta 85 ss 73er 163

On utilisera dans les exercices suivants une reprsentation numrique des lettres de l'alphabet :

A B C D E F G H I J K L M N O P Q R S T U V ...0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ...

Exercice 2 Jules Csar

Le systme le plus ancien est attribu Jules Csar. Il consiste en un dcalage de l'alphabet (dans le systmeoriginal A tait remplac par C, B par D, C par E, . . . ).Q 1 . Voici un texte chir obtenu avec la cl H :

QLZBP ZHSVU KYLZK HUZBU LKLZYBLZSL ZWSBZ TPZLY HISLZ KLSHCPSSLQ LTHYJ OLLUT LKLTH UKHUAJVTTL UAZLK PABYP UVPYL UZSHUN

Retrouvez le texte clair.Q 2 . Voici un autre texte chir ; on ne connait pas ici la cl utilise.

2

FYPYQ LYELO TEUPD LTDOP DAZPXPDFYP YQLYE LOTEN SDLTD OPDAZPDTPD

Retrouvez le texte clair.

Exercice 3 A faire la maison Chirement de Vigenre

Q 1 . Ce cryptogramme a t obtenu par chirement de Vigenre avec le mot-cl 'RAYMOND'

RILEW FRETJ QGZRV UPERR VDAJQGRWUE QRSZH CLCER NQJLC DSTQVALUAN OUEDM QBQGR MHWQH ETGQZYH

Q 2 . Dcryptez maintenant ce cryptogramme sans connatre la cl

KESIY QEZCN NUDIW ZUSMQ NUSWRZVDKP ZVZKL DTSMT TIRQP RDZVWDNSTI QIFWH NNNCF HEMTE UAKAISTD

Exercice 4 Le masque jetable

La technique du masque jetable a t labore en 1926 par G. Vernam sous le nom de 'one-time pad', etconsiste en l'ajout au texte clair d'une suite de symboles alatoire de mme longueur que le texte clair, etqui sera jete aprs usage. Il faudra considrer une nouvelle suite alatoire pour un chirement ultrieur. C.Shannon, fondateur de la thorie de l'information, a dmontr en 1949 que ce systme est inconditionnelle-ment sr (c'est le seul systme inconditionnellement sr l'heure actuelle).Q 1 . Le cryptogramme suivant

QCFPP WXAZS POUIH QHHCF VVFGTGFDAS VSKUE BSYYD QESWV OEHDB

a t chir par une technique du masque jetable. Expliquez pourquoi vous ne pouvez pas le dcrypter.Q 2 . Discutez des avantages et inconvnients de ce systme.

2 Pour se familiariser avec les ordres de grandeur

Exercice 5 Vider l'ocan avec un d coudre

La recherche d'une cl par force brute revient 'vider l'ocan avec un d coudre'. On considre qu'un d coudre est un cylindre de 1, 5 cm. de hauteur pour 1, 5 cm de diamtre. Selon l'Institut Franais desMers, les ocans couvrent 360 millions de km2 avec une profondeur moyenne de 3800 m. Encadrer entredeux puissances de 2 conscutives le nombre de ds coudre d'eau que contiennent les ocans.

Exercice 6 La force brute

Le facteur de travail d'un algorithme est le nombre d'instructions lmentaires ncessaire son excution.La puissance d'une machine est le nombre d'instructions qu'elle excute par unit de temps. La puissanced'un PC actuel (en 2004) est d'environ 1800 Mips. (millions d'instructions par secondes). Le facteur detravail d'un algorithme optimis pour tester une cl de 128 bits de l'algorithme AES est d'environ 1200instructions lmentaires. On dispose d'un couple clair/chir connu et on dsire retrouver la cl utilise parforce brute, c'est- -dire en testant toutes les cls les unes aprs les autres. Une cl est constitue d'un motde 128 symboles binaires. On suppose que toutes les cls sont quiprobables.

3

Q 1 . En combien de temps une machine de 1800 Mips teste-t-elle une cl ?Q 2 . Combien y a-t-il de cls possibles ? Quel est le nombre moyen de cls tester avant de trouver labonne ?Q 3 . Quel est le facteur de travail moyen (en Mips annes) pour trouver la cl.Q 4 . A quel temps moyen de calcul cela correspond-il si on suppose que les 300 millions de PC de l'internetsont mobiliss cette tche ?

Exercice 7 La loi de Moore

Il est admis que, grce aux progrs technologiques permanents, la puissance des machines double en moyennetous les 18 mois (loi de Moore). On suppose maintenant que l'on change les machines tous les mois (30 jours)en commenant avec une machine d'une puissance de 1800 Mips. Pour tout entier n, on note Wn le nombred'instructions excutes par la machine du mois n.Q 1 . Quel est le facteur d'amlioration a de la puissance des machines d'un mois l'autre ?Q 2 . Calculer W0, puis Wn en fonction de W0, de a et de n.Q 3 . Quel est le temps moyen ncessaire pour trouver la cl (de l'exercice prcdent) ?

3 Rappels d'arithmtique modulaire

Exercice 8 Algorithme d'Euclide Etendu

On demande de trouver les coecients de Bezout pour les nombres entiers suivants:

(a, b) = (17, 50)

(a, b) = (11, 280)

(a, b) = (35, 50)

Exercice 9 Calcul modulaire

Rsoudre les quations suivantes:

1. 17x 10 mod 50

2. 35x 10 mod 50

3. 35y 11 mod 50

Exercice 10 Calculer l'inverse de 317 mod 521.

Exercice 11 Calculer pgcd(6874009, 2673157)

4