[PDF] Examen de cryptographie (3h) Exercice 1 : bits faciles et difficiles





Previous PDF Next PDF



EXAMEN DE CRYPTOGRAPHIE

Examen de Cryptographie et Sécurité. Durée : 1h30 – Documents non autorisés. Exercice 1 (7pts) On s'intéresse à l'algorithme cryptographique d'ElGamal.



Examen de cryptographie IUT Licence 3

Examen de cryptographie IUT Licence 3. Enseignant : CAYREL Pierre-Louis. Corrigé détaillé. Mercredi 19 décembre 2007. Durée : 1h30.



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.



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 



Examen Final – Cryptographie

Examen Final – Cryptographie vendredi 16 janvier 2009 16h – 17h30. Solutions. Probl`eme 1 (Cryptanalyse différentielle). On consid`ere le cryptosyst`eme E 



Solutions pour lexamen partiel – Cryptographie

Solutions pour l'examen partiel – Cryptographie vendredi 14 décembre 2007 13h – 14h30. Exercice 1. Soient X et Y deux variables aléatoires indépendantes.



Examen de cryptographie (3h) Exercice 1 : bits faciles et difficiles

Examen de cryptographie (3h). Vous disposez de la moitié du temps pour résoudre les deux premiers exercices et de l'autre moitié pour résoudre l'exercice 3.



Examen Partiel – Cryptographie

Examen Partiel – Cryptographie vendredi 10 novembre 2006. Toutes les réponses devront être soigneusement justifiées. Exercice 1.



Examen Partiel – Cryptographie

Examen Partiel – Cryptographie vendredi 24 octobre 2008 14h – 15h30. Documents de cours autorisés. Toutes les réponses devront être soigneusement 



STEGANOCRYPTOGRAPHIE EN IMAGERIE MEDICALE

L'utilisation conjointe de la steganographie et de la cryptographie est une solution conditions de l'examen (nature lieu

Examen de cryptographie (3h) Exercice 1 : bits faciles et difficiles UGA - M1 Mathematiques2020-2021Examen de cryptographie (3h) Vous disposez de la moitie du temps pour resoudre les deux premiers exercices et de l'autre moitie pour resoudre l'exercice 3. Durant la premiere partie de l'examen, vous n'avez pas acces aux documents ni aux ordinateurs. Pour la deuxieme partie, vous devez utiliser un ordinateur et programmer sous sagemath dans votre environnement habituel. Votre chier informatique doit ^etre televerse a la n de l'epreuve sur Exercice 1 : bits faciles et diciles pour le logarithme discret Soitpun grand nombre premier. Pour tout entierxcompris entre 0 etp1, sonbit de poids faible, note lsb(x) (least signicant bit), est le dernier chire dexdans son ecriture en base 2; on a donc lsb(x) =(

0 sixest pair

1 sixest impair

Lebit de poids fortdex, note msb(x) (most signicant bit), est deni de maniere un peu dierente : msb(x) =(

0 six

1 sixp12

On considere un generateurgdu groupe cyclique (Z=pZ), et un elementh2(Z=pZ). On note x2J0;p2Kle logarithme discret dehen baseg, mais celui-ci n'est pas connu a priori. 1.

D emontrerles equivalences:

lsb(x) = 0()hest un carre dans (Z=pZ)()h(p1)=2= 1 modp En deduire une methode ecace de calcul de lsb(x) et en donner la complexite en fonction dep. 2.

On consid erel' ecriturebinaire du r eel

xp1: xp1= (0;y1y2y3:::)2=X k1y k2k (a)

D emontrerq uey1= msb(x), puis que pour toutj1,

y j= msb 2 j1x(p1)j1X k=1y k2j1k! (b) On supp oseq uel'on disp osed' unefonction msbDL, qui, pour toute entreeg02(Z=pZ), renvoie le bit de poids fort du logarithme discret deg0en baseg. i.

Mon trerque yj=msbDL(h2j1) pour toutj1.

ii. Donner une m ethodep ermettantde retrouv erle logarithme discret xdehen baseg apresdlog2(p1)eappels a la fonctionmsbDL. On pourra commencer par montrer que pour toutm2N, on a l'egalite (0;y1:::ym)2=b2mxp1c=2m. (c) En d eduirequ'il est p ossiblede calculer (en temps p olynomialen la taille de p) le bit de poids fort du logarithme discret d'un element de (Z=pZ)si et seulement si il est possible de calculer (en temps polynomial en la taille dep) ce logarithme discret en entier. 1

UGA - M1 Mathematiques2020-20213.On consid ered esormaisun elementa2(Z=pZ)dont l'ordre est un entierimpairr.

(a) En s'in spirantdes questions p recedentes,m ontrerque si l'on disp osed'u nefonction lsbDL qui, pour toute entreeb2 hai, renvoie le bit de poids faible du logarithme discret en base adeb, alors il est possible de calculer le logarithme discret en basead'un elementh2 hai endlog2(r)eappels alsbDL. Indication : on pourra noteruun inverse de 2 modulor, etx= (xm:::x1x0)2le logarithme discret deh. Que vaut alorslsbDL((hax0)u)? (b) En d eduirequ'il est p ossiblede calc uler(en temps p olynomiale nla taille de r) le bit de poids fort du logarithme discret d'un element du sous-groupehaisi et seulement si il est possible de calculer (en temps polynomial en la taille der) ce logarithme discret en entier.

Exercice 2 : Decodage des codes de Reed-Solomon

On rappelle la denition suivante :

Soientkndeux entiers,Fqun corps ni, etx1;:::;xndes elements distincts deFq. Le code de Reed-Solomon surFqde parametres (k;n) associe aux elementsx1;:::;xnest l'ensemble

C=f(P(x1);:::;P(xn))jP2Fq[X];deg(P)< kg1.Rapp elerp ourquoila distance minimale de Cest egale ank+ 1.

On note dans la suitet=bnk2

cla capacite de correction deC. Soitw= (y1;:::;yn)2(Fq)nun message recu; on suppose qu'il y a eu au plusterreurs lors de la transmission. Decoderwrevient alors a retrouver l'unique polyn^omePde degre strictement inferieur aktel queP(xi) =yipour au moinsntvaleurs distinctes dei. 2.

Soien tQ0=nt1X

j=0c jXjetQ1=ntkX j=0d jXjdeux polyn^omes deFq[X] de degres strictement inferieurs antet antk+ 1 respectivement. Montrer que, pour touti2J1;nK,Q0(xi)yiQ1(xi) = 0 si et seulement si le (2n2tk+1)-uplet (c0;:::;cnt1;d0;:::;dntk) est solution d'un systeme lineaire que l'on explicitera. 3. Mon trerque ce syst emelin eairep ossedeau m oinsune solution non n ulle. 4. On supp osed esormaisque ( c0;:::;cnt1;d0;:::;dntk) est une solution non nulle du systeme lineaire ci-dessus, et donc queQ0(xi)yiQ1(xi) = 0 pour touti2J1;nK. On noteIJ1;nKle sous-ensemble des positions ou il n'y a pas eu d'erreurs de transmission.

Demontrer queQ0(xi)P(xi)Q1(xi) = 0 pour touti2I.

5.

Mon trernalemen tque Q1est non nul et queP=Q0=Q1.

Quelle est la complexite de cette methode de decodage? 6. Justier que le p olyn^omeQ1ainsi trouve est un multiple deY i2J1;nKnI(Xxi) (parfois appele polyn^ome localisateur d'erreurs). 2 UGA - M1 Mathematiques2020-2021Exercice 3 : Generateurs congruentiels lineaires Les generateurs congruentiels lineaires (LCG) forment une famille tres simple de PRNG, qui s'appuie sur les suites arithmetico-geometriques.Etant donnes des parametresa;c;met une graineX0, un tel generateur calcule les termes successifs de la suite (Xn) veriant la relation X n+1=aXn+cmodm On peut ensuite renvoyer soit directement la suite (Xn) des etats du generateurs, soit seulement une

partie des bits desXn. Un tel generateur a l'avantage d'^etre rapide et tres simple, donc interessant

dans un environnement contraint (systeme embarque) ou si l'on n'a pas besoin d'un pseudo-hasard tres robuste. Cependant, la qualite d'un tel PRNG depend enormement du choix des parametres. On considere donc une suite (Xn)n2N, a valeurs dansf0;:::;m1g, veriant pour toutn2Nl'egalite X n+1=aXn+cmodm. 1. Ecrire en SageMath une fonctionLCG(X0,a,c,m,N)qui renvoie la liste desNpremieres valeurs de la suite (Xn). Exemple : >>> LCG(0,2,1,5,9) [0,1,3,2,0,1,3,2,0]

I. Periode : exemples

2. (a) Rapp elerp ourquoila sui te( Xn) est ultimement periodique, de periodeTm. (b) Justier que s iaest premier avecm, alors la suite (Xn) est en fait periodique. 3.

Un premier exemple.

On considere le generateur donne par la relation de recurrenceXn+1= 96Xn+ 47 mod 1309, avecX0= 1. (a) Ecrire un programme (suite d'instructions) permettant de trouver la periode de cette suite. (b) P ourtout n2N, on poseYn=Xnmod 7 avecYn2 f0;:::;6getZn=Xnmod 11 avec Z n2 f0;:::;10g. Acher la liste des 300 premiere valeurs des suites (Yn) et (Zn) et donner (sans justication) leur periode. (c) P ourtout n2N, on poseUn=Xnmod 10 avecUn2 f0;:::;9g. Acher la liste des 300 premieres valeurs de la suite (Un). Quelle(s) dierence(s) peut-on observer avec le comportement des suites (Yn) et (Zn)? Determiner en quelques lignes de code la periode de (Un) (on pourra utiliser sans justica- tion qu'il s'agit d'un diviseur de la periode de la suite (Xn)). 4.

Un deuxi emeexemple.

Le generateurRANDU, introduit dans les annees 1960 par IBM, utilisait la relation de recurrence X n+1= 65539Xnmod 231. (a) En partan td'une v aleurde X0impaire de votre choix, acher la liste des 200 premieres valeurs de la suite (Xn), ecrite en base 2. On utilisera la commanden.digits(2)pour obtenir cette ecriture binaire, du bit de poids faible vers le bit de poids fort. (b) Observ erla suite form eepar les premiers bits, les deuxi emesbits, etc. Que p eut-onconsta- ter? Ce comportement persiste-t-il pour une autre valeur deX0? (c) La suite ( Xn) ainsi generee est-elle une bonne suite pseudo-aleatoire? 3 UGA - M1 Mathematiques2020-2021II. Periode : theorie On considere toujours une suite (Xn)n2N, a valeurs dansf0;:::;m1g, veriant pour toutn2N l'egaliteXn+1=aXn+cmodm. 5. (a) Soit dun diviseur dem. Montrer que la suite (Xnmodd)n2N(a valeurs dansf0;:::;d1g ouZ=dZ) verie aussi une relation de recurrence. (b) En d eduireque la suite ( Xnmodd)n2Nest ultimement periodique, de periodeTdd. (c) Expliquer les comp ortementsobserv esaux questions 3.b et 4.b. 6.

Un cas particulier : c= 0(generateur de Lehmer).

(a) Donner la f ormedu terme g eneralde la sui telorsque c= 0 eta^m= 1.

Que peut-on dire de la periode de la suite?

(b)

Soit Qr

i=1piila decomposition en nombres premiers distincts dem. Montrer que le maxi- mum des periodes (amxe impair, et toujours pourc= 0) vaut ppcm('(p11);:::;'(prr)).

Comment choisiraetX0pour obtenir cette periode?

7.

Un cas particulier : m=ppremier.

(a) Mon trerque si a6= 1 modp, alors il existe un entierbtel que pour toutn2N, X n=an(X0b) +bmodp: Que peut-on alors en deduire sur la periode de la suite? (b) D emontrerque la suite ( Xn) est de periodepsi et seulement sia= 1 modpetp-c. Est-ce que la suite de periode maximale ainsi obtenue est une bonne suite pseudo-aleatoire?

III. Quelques faiblesses

8.

P ointset plans.

Pour certaines applications comme le calcul d'integrales multiples par methode de Monte-Carlo, on a besoin d'interpreter les valeurs (Xn) renvoyees comme les coordonnees de points de l'espace, en posantAn= (X3n;X3n+1;X3n+2)2 f0;:::;m1g3. On considere a nouveau le generateurRANDU, utilisant la relation de recurrenceXn+1=

65539Xnmod 231.

(a) En partan td'une v aleurimpaire de X0, generer la liste des 1000 pointsA0;:::;A999. On pourra representer un point soit comme un triplet(x,y,z)soit comme une liste a trois elements[x,y,z]. (b) A l'aide des commandespointsoupoint3d, qui prennent toutes deux en parametres une liste de points, acher le nuage de points correspondant et l'observer sous dierents angles. En cas de dicultes d'achage, on pourra \renormaliser" les points pour les mettre dans [0;1]3en divisant toutes les coordonnees par 231. Les points semblent-ils uniformement repartis dans le cube de c^ote de longueur 2 31?
(c)

En r emarquantque 65539 = 2

16+3, montrer queXn+2= 6Xn+19Xnmod 231pour tout

n2N. (d) P ourk2Z, on notePkle plan ane d'equation 9x6y+z= 231k. En utilisant la question precedente et les valeurs prises par la suite (Xn), montrer que pour toutn2N, le pointAn= (X3n;X3n+1;X3n+2)2R3appartient a l'union[ 5k9P k.

Faire le lien avec la question (b).

4 UGA - M1 Mathematiques2020-20219.P aradoxedes anniv ersaires. On suppose qu'un generateur congruentiel lineaire renvoie la suite des (Xn), de periodeTproche dem. Combien de temps faut-il attendre pour observer une repetition dans la liste des valeurs pro- duites? Expliquer pourquoi ce comportement n'est pas typique d'une vraie suite aleatoire a valeurs dansf0;:::;m1g. Quelle modication simple permettrait d'avoir un comportement plus aleatoire? 5quotesdbs_dbs29.pdfusesText_35

[PDF] Examen de fin d 'études secondaires 2017 - MENlu

[PDF] 1/4 Module : Floristique Examen Ecrit- 1 juin 2016 Nom

[PDF] La couverture des services fournis par un optométriste - Régie de l

[PDF] Special Costco Membership Offer for the members of Actra

[PDF] Controls SMC_P_-S2 - FSR

[PDF] Examen de Management Stratégique - BU Toulon

[PDF] Examen Microbiologie Juin 2007

[PDF] epreuve de « macroeconomie 1 - BU Toulon - Université de Toulon

[PDF] Corrigé de l 'Examen final de Microéconomie

[PDF] Examen juin 2016 (partie Intégration, avec - Université de Lorraine

[PDF] L 'évaluation des apprentissages du FLE dans les collèges cas de 3

[PDF] Langue Vivante Anglais Sujets d 'Examens 2007-2008 - Université

[PDF] Examen de CES Révision Comptable Session de - Révision Fac

[PDF] examens de techniciens decembre 2013 - Ucanss

[PDF] Génie mécanique - Université de M 'sila