Examen Partiel – Cryptographie jeudi 1er décembre 2005 Correction Exercice 1 (12pts) Soit p un nombre premier Donner une formule simple pour (21 p )
Previous PDF | Next PDF |
[PDF] Examen Partiel – Cryptographie Correction
Examen Partiel – Cryptographie jeudi 1er décembre 2005 Correction Exercice 1 (12pts) Soit p un nombre premier Donner une formule simple pour (21 p )
[PDF] Examen Final – Cryptographie
Examen Final – Cryptographie jeudi 19 janvier 2006 Correction Exercice 1 Alice change sa clé RSA tous les 25 jours Bob lui change sa clé tous les 31 jours
[PDF] Corrigé - DI ENS
Introduction `a la cryptographie Examen (d) (4pts) Identifier et expliquer quelles sont les vulnerabilités d'un tel cryptosyst`eme Solution 1 Il s'agit d'un
[PDF] Cryptographie et arithmétique Corrigé dexamen Université de
Université de Bordeaux Cryptographie et arithmétique – Corrigé de l'examen 2014 Exercice 1 1 corrections en TD) On cherche à obtenir une congruence
[PDF] Exercices et problèmes de cryptographie - Dunod
largement le cadre strict de la cryptographie Ce talent et préparer aux examens s'il cherche des solutions personnelles avant d'en étudier les corrections
[PDF] Cryptographie Paris 13 - Laboratoire Analyse, Géométrie et
1 oct 2010 · On emploiera indifféremment les mots cryptographie, chiffrement et codage Les mots en cryptage mais de la correction d'erreur) Bob veut
[PDF] Examen Final - Université de Lille
16 mai 2013 · Ce sujet est composé de 4 pages 1 QCM `a auto-correction cryptographique Cet exercice contient un QCM que vous allez remplir, et que vous
[PDF] Exercices de cryptographie - LIM
On choisit e = 3 : est-ce correct ? Pourquoi ? 4 Donnez une valeur correcte pour d 5 Cryptez le message M = 5 Un sujet d'examen Résolvez l'exercice 1 du
[PDF] TD de Cryptologie IUT Licence 3 Feuille dexercices n 2 (corrigés)
évidemment non pour les deux car les messages à chiffrer/déchiffrer doivent appartenir à Zn, c'est à dire Z319 dans ce cas Exercice 2 (Cryptographie RSA et
[PDF] Correction du TD sécurité réseau : Crypto Correction exercice 1
Correction du TD sécurité réseau : Crypto Correction exercice 1: attaques sur le cryptosystème de Cesar COA : l'attaque frequentielle n'est pas efficace pour un
[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
Examen Partiel - Cryptographie
jeudi 1er d´ecembre 2005Correction
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 p7Les 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 ?p31 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 ?p71 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 descongruences 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 19Exercice 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 obtientBESROP...
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´eDOdonneLECRYPTOGRAMMEDEVIGENERE...
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 12. 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 < p2/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