Examen Partiel Cryptographie jeudi 1er decembre

pages

Français

Documents

2005

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Ebook

2005

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

zauj

Publié le

01 décembre 2005

Nombre de lectures

Langue

Français

Niveau: Supérieur
Examen Partiel – Cryptographie jeudi 1er decembre 2005 Correction Exercice 1 (12pts) Soit p un nombre premier. Donner une formule simple pour ( 21 p ) Indication : on distinguera les trois cas : 1) p = 2 ; 2) p = 3 ou p = 7 ; 3) p impair et p 6= 5, 7. Solution. 1) Pour p = 2, on a ( 21 2 ) = ( 21 mod 2 2 ) = ( 1 2 ) = 1 puisque 1 n'est pas divisible par 2 et est un carre modulo 2. 2) Pour p = 3 et p = 7, puisque p divise 21, on a par definition ( 21 p ) = 0. 3) Pour p impair, p different de 3 et 7, on utilise les proprietes du symbole de Jacobi ( 21 p ) = (?1) (21?1)(p?1) 4 ( p 21 ) = (?1)5(p?1) ( p 3? 7 ) = ( p 3 )( p 7 ) Les classes inversibles modulo 3 sont 1 et 2, et 1 est un carre modulo 3 (c'est le carre de 1), alors que 2 n'est pas un carre modulo 3.

puissance de ?

chaınes renvoyes par le diagramme

diagramme de feistel

logarithme discret de ? en base ?

complexite du probleme du logarithme discret

expressions des chaınes w??1

Voir

Publié par

zauj

Publié le

01 décembre 2005

Nombre de lectures

Langue

Français

Examen Partiel – Cryptographie jeudi1erde´cembre2005 Correction

Exercice 1 (12pts) SoitpDonner une formule simple pourun nombre premier.   21 p Indication :on distinguera les trois cas :1)p= 2 ; 2)p= 3 oup= 7 ; 3)pimpair etp6= 5,7.     21 21mod 21 Solution.1) Pourp= 2, on a= == 1 puisque 1 n’est pas divisible par 2 2 22 etestuncarre´modulo2.   21 2) Pourp= 3 etp= 7, puisquepnoit.0=apon1,e2nieﬁd´ardvisi p 3) Pourpimpair,pleboJadesd´eymusrporte´iesilpselocibede3ertnunit7to,iﬀ´ed       21p pp p (21−1)(p−1) 5(p−1) = (−(1) =−1) = 4 p21 3×7 37 Lesclassesinversiblesmodulo3sont1et2,et1estuncarr´emodulo3(c’estlecarre´de1), alorsque2n’estpasuncarre´modulo3.Doncona (   p1 sip≡3)1 (mod = 3−1 sip≡2 (mod3) Les classes inversibles modulo 7 sont 1,2,3,4,´rracselic-selle´errca1(ntsoesrmic6.Pa5et de1),2(carr´ede3)et4(carre´de2).Ainsiona (   p1 sip≡1,2,4 (mod7) = 7−1 sip≡3,5,6 (mod7)   p On trouve donc que= 1 si et seulement si on est dans un des deux cas suivants :a)p≡1 21 (mod 3) etp≡1,2,4 (mod7), ou b)p≡3) et2 (modp≡3,5,6 (mod7). Pourobtenir des congruencesmodulo21,onutiliselethe´ore`medesresteschinois.Notonsque(−2)∙3 + 1∙7 = 1 et donc les deux congruences  x≡a(mod 3) x≡b(mod 7) sonte´quivalentesa`lacongruencex≡cu`o)m(12doc= 7a−6bmod 21.On trouve ainsi que   p = 1 si et seulement sip≡1,4,5,16,17,20 21 Les classes possibles pourpmodulo 21 sont 1,2,4,5,7,8,10,11,13,16,17,19,eﬀet, les20. En classes 3, 6, 9, 12, 15, 18 ne sont pas possibles car elles impliquent quepest divisible par 3,

Voir