[PDF] Examen Partiel – Cryptographie Correction

View - Download Examen Partiel – Cryptographie Correction

Previous PDF

Next PDF

Examen Partiel - Cryptographie

jeudi 1er d´ecembre 2005

Correction

Exercice 1 (12pts)

Soitpun nombre premier. Donner une formule simple pour ?21p Indication :on distinguera les trois cas : 1)p= 2 ; 2)p= 3 oup= 7 ; 3)pimpair etp?= 5,7.

Solution.1) Pourp= 2, on a?212

?=?21 mod 22 ?=?12 ?= 1 puisque 1 n"est pas divisible par 2 et est un carr´e modulo 2.

2) Pourp= 3 etp= 7, puisquepdivise 21, on a par d´efinition?21p

?= 0.

3) Pourpimpair,pdiff´erent de 3 et 7, on utilise les propri´et´es du symbole de Jacobi

?21p = (-1)(21-1)(p-1)4 ?p21 = (-1)5(p-1)?p3×7? =?p3 p7

Les classes inversibles modulo 3 sont 1 et 2, et 1 est un carr´e modulo 3 (c"est le carr´e de 1),

alors que 2 n"est pas un carr´e modulo 3. Donc on a ?p3

1 sip≡1 (mod 3)

-1 sip≡2 (mod 3)

Les classes inversibles modulo 7 sont 1,2,3,4,5 et 6. Parmi celles-ci les carr´es sont 1 (carr´e

de 1), 2 (carr´e de 3) et 4 (carr´e de 2). Ainsi on a ?p7

1 sip≡1,2,4 (mod 7)

-1 sip≡3,5,6 (mod 7)

On trouve donc que

?p21 = 1 si et seulement si on est dans un des deux cas suivants : a)p≡1 (mod 3) etp≡1,2,4 (mod 7), ou b)p≡2 (mod 3) etp≡3,5,6 (mod 7). Pour obtenir des

congruences modulo 21, on utilise le th´eor`eme des restes chinois. Notons que (-2)·3+1·7 = 1

et donc les deux congruences?x≡a(mod 3) x≡b(mod 7) sont ´equivalentes `a la congruencex≡c(mod 21) o`uc= 7a-6bmod 21. On trouve ainsi que?p21 = 1 si et seulement sip≡1,4,5,16,17,20 Les classes possibles pourpmodulo 21 sont 1,2,4,5,7,8,10,11,13,16,17,19,20. En effet, les classes 3, 6, 9, 12, 15, 18 ne sont pas possibles car elles impliquent quepest divisible par 3, de mˆeme sip≡7,14 (mod 21) alorspest divisible par 7. Puisque?p21 vaut 1 pour les 6 classes list´es ci-dessus, on a ?p21 =-1 pour les 6 classes restantes : 2,8,10,11,13 et 19

Exercice 2 (6pts)

On consid`ere un diagramme de Feistel `a deux rondes o`u les fonctionsf1etf2sont constantes, c"est-`a-dire il existe deux chaˆınes binairesc1etc2telles quef1(w) =c1etf2(w) =c2pour toutw.

1. Donner les expressions des chaˆınesw??1etw??2renvoy´ees par le diagramme.

2. Montrer comment un attaquant, qui ne connaˆıt pas les valeurs dec1etc2, peut quand

mˆeme retrouverw1etw2`a partir dew??1etw??2`a l"aide d"uneseuleattaque `a texte clair choisi. Solution.1. Les chaˆınes renvoy´es par le diagramme sontw??1=f2(f1(w1)?w2)?w1 etw??2=f1(w1)?w2. Puisque les fonctions sont constantes, on a doncw??1=c2?w1et w ??2=c1?w2.

2. Un attaquant qui interceptew??1etw??2pour faire une attaque `a texte clair choisi en deman-

dant le cryptage de la chaˆınew??1·w??2. Il re¸coit en r´eponse les chaˆınesc2?w??1=c2?c2?w1=w1

etc1?w??2=c1?c1?w2=w2. Il retrouve ainsi le message clair initial.

Exercice 3 (10pts)

D´ecoder le message suivant encod´e par le procotole de Vigen`ere avec une cl´e de longueur 2

OSFFBDWCJFDAPSGSYWJSQSUSQSVHSZXGFCQ

GLRHFHRHBRGMCXFVQRAPSXBSFRHRQRZHGXF

(Note : les espaces et signes de ponctuation ont ´et´e supprim´es.) Solution.On consid`ere les deux sous-messages extraits :OFBWJDPGYJQUQVSXFQLHHHRMXVRPXS RRRHXetSFDCFASSWSSSSHZGCGRFRBGCFQASBFHQZGF. Dans le premier sous-message, la lettre la plus fr´equente estRavec 5 occurences. Apr`es, on trouveHetXavec chacune 4 occurences. Dans le deuxi`eme sous-message, la lettre la plus fr´equente estSavec 7 occurences, ensuite on aFavec 6 occurences. En posantRcomme codage deEpar la premi`ere lettreC1de la cl´e et Scomme codage deEpar la deuxi`eme lettreC2, on obtient queC1 = R - E = NetC2 = S - E = O. On essait de d´ecoder le d´ebut du message, on obtient

BESROP...

Ce qui ne semble pas `a un texte en fran¸cais. On essaie d"autre possibilit´es. Par exemple, en

supposant que le codage deE + C1 = H. On trouve alors queC1 = H - E = D. Le d´ecodage du d´ebut du message avec la cl´eDOdonne

LECRYPTOGRAMMEDEVIGENERE...

donc est correct.

Exercice 4 (18pts)

SoitGun groupe cyclique d"ordreN=p2qavecpetqdeux nombres premiers distincts.

Notonsγun g´en´erateur deGet soitα?G.

On cherche `a d´eterminer le logarithme discret deαen baseγ, c"est-`a-dire `a trouverxtel que

1. On posey:=xmodp2.

(a) Montrer qu"on peut ´ecrire y=y0+y1·p (b) Calculerαpqen tant que puissance deγ. En d´eduire quey0est l"unique solution (entre 0 etp-1) de y0=αpq o`uβ=γpq. (c) On poseα1=α·γ-y0. Montrer quey1est l"unique solution (entre 0 etp-1) de y1=αq 1

2. On posez:=xmodq.

(a) Montrer quezest l"unique solution (entre 0 etq-1) de z=αp2 o`uη=γp2.

3. Expliquer comment on peut retrouverx`a partir deyetz.

4. Que peut-on en conclure sur la complexit´e du probl`eme du logarithme discret dans le

groupeG?

On pose

y=qp+r y/p < p

2/p=p. Donc on peut prendrey1=qety0=r.

1.(b) Posonsx=kp2+y=kp2+y0+y1p. On calcule

pq=?

γx?pq=γxpq=γkp3q+y0pq+y1p2q=?

γp2q?kp?

γpq?y0?

γp2q?y1=?

γpq?y0

puisqueγp2qest l"identit´e deG. Ainsi, on trouve que pq=βy0 Puisqueβ=αpq, on sait queβest d"ordreN/pq=pety0est l"unique solution de l"´equation ci-dessus entre 0 etp-1.

1.(c) On calcule

q 1=?

γp2q?k?

γpq?y1=βy1

Et de mˆeme mani`ere,y1est l"unique solution entre 0 etp-1 de cette ´equation. p2=?

γx?p2

=γp2(lq+z)=?

γp2q?l?

γp2?z=ηz

De plusηest d"ordreN/p2=qet donczest l"unique solution entre 0 etq-1 de cette ´equation.

3. Une fois d´etermineryetz, on a le syst`eme suivant

?x≡y(modp2) x≡z(modq) En utilisant le th´eor`eme des reste chinois, on en d´eduit la valeur dex.

4. Pour r´esoudre le probl`eme du logarithme discret dansG, il suffit de savoir r´esoudre succes-

sivement les trois probl`emes de logarithme discret donn´e ci-dessus avec des ´el´ements d"ordre

respectivementp,petq. Donc la complexit´e du probl`eme du logarithme discret d´epend juste de la taille du plus grand des nombres premierspetq, et non pas de la taille deN.quotesdbs_dbs1.pdfusesText_1

[PDF] examen cti 0209

[PDF] examen cytobactériologique des crachats fiche technique

[PDF] examen cytobactériologique des liquides d épanchement

[PDF] examen d'admission gymnase vaudois

[PDF] examen d'analyse et de raisonnement déductif

[PDF] examen d'analyse personnel technique

[PDF] examen d'aptitude professionnelle ide 1er grade

[PDF] examen d'aptitude professionnelle ide echelle 10

[PDF] examen d'aptitude professionnelle maroc

[PDF] examen de bacalaureat national 2015 varianta 9

[PDF] examen de bacalaureat national 2016 proba e

[PDF] examen de biologie animale avec correction pdf

[PDF] examen de biologie animale s2 pdf

[PDF] examen de biologie cellulaire 1ere année

[PDF] examen de chimie 1er année st