[PDF] TP 7 - Chiffrement RSA 1 Lalgorithme dEuclide 2 Théor`eme de

View - Download TP 7 - Chiffrement RSA 1 Lalgorithme dEuclide 2 Théor`eme de

Previous PDF

Next PDF

IUT Littoral 2019 - 2020

Info 2A Math { C++

TP 7 - Chirement RSA

Denition 1.Unnombre premierest un entierpsuperieur ou egale a 2 dont les seuls diviseurs positifs sont 1 etp

1 L'algorithme d'Euclide

Denition 2.Soientaetbdes entiers non tous deux nuls. Le plus grand entier qui divisea etbs'appelle le plus grand commun diviseur deaet debet se note pgcd(a;b). Proposition 3.Soientaetbdes entiers positifs non tous deux nuls. Sirest le reste de la division euclidienne deaparb, alorspgcd(a;b) = pgcd(b;r).

Exercice 4.Calculer pgcd(585;247).

Exercice 5.

Ecrire une fonction recurssiveEntier pgcdrec(Entier a,Entier b)calculant les pgcd de deux nombres positifsaetb. Soientaetbdes entiers positifs non tous deux nuls. On construit une suiterien posantr0=a, r

1=bet pourk>2.

r k= reste de la division euclidienne derk2parrk1 =rk2qk1rk1ouqk1=rk2r k1

Il existe alors un unique entierNtels que

b=r1> r2> ::: > rN1> rN= 0; et nous avons alors pgcd(a;b) =rN1. Exercice 6.Ecrire une procedure non recurssiveEntier pgcd(Entier a,Entier b)calculant les pgcd de deux nombres positifsaetb. Denition 7.Soientaetbdes entiers non tous deux nuls. On dit queaetbsontpremiers entre euxsi pgcd(a;b) = 1.

2 Theoreme de Bezout

Theoreme 8.Siaetbsont des entiers positifs, alors il existe des entiersuetvtels que pgcd(a;b) =au+bv. En s'inspirant de l'algorithme d'Euclide, on construit deux suitesuketvkdeZveriantauk+ bv k=rkpour toutk6N. On pose alorsu0= 1;v0= 0 etu1= 0;v1= 1 ainsi que u k=uk2qk1uk1etvk=vk2qk1vk1: On a alors pgcd(a;b) =rN1auN1+bvN1=rN1= pgcd(a;b) et il sut de prendreu=uN1 etv=vN1. Exercice 9.Determiner des entiersuetvtels que 585u+ 247v= pgcd(585;247). 2

3 Congruences

Denition 10.On dit que deux entiersaetbsont congrus modulon, lorsqu'il donne le m^eme reste par la division euclidienne parn. On note alorsabmodn. Ou de maniere equivalente, deux entiersaetbsont congrus modulonlorsqueabest un multiple den, c'est-a-dire, lorsqu'il existek2Ztel queab=nk.

Exemple.Quels que soienta2Zetn2N, on a

{aamodn {armodnsirest le reste de la division euclidienne deaparn.

Proposition 11.Soeinta;b;c;d2Zetn2N, on a

{ siabmodnetbcmodnalorsacmodn. { siabmodnetcdmodnalorsa+cb+dmodn,acbdmodnetaccd modn.

4 Indicatrice d'Euler

Denition 12.Un entiera2Zest dit inversible modulons'il existeb2Ztel qu'on aitab1 modn. Exercice 13.Quels sont les entiers def0;:::;12gqui sont inversibles modulo 12? Denition 14.Pourn>2, on note(n) le nombre d'element def0;:::;n1gqui sont inversibles modulon.

Exercice 15.

a.Determiner(4),(5),(6) et(7). b.Que vaut(n) lorsquenest un nombre premier. Proposition 16.Soientpetqdeux nombres premiers distincts. On a(pq) = (p1)(q1).

Exercice 17.Demontrer la proposition precedente.

Exercice 18.Calculer(35).

5 Chirement RSA

Alice veut envoyer un message a Bob de maniere securisee : a la reception du message seul Bob doit pouvoir le dechirer. Pour ce faire Bob genere de maniere aleatoire deux grands nombres premierspetq. Il calcule ensuite leur produitn=pqainsi que(n) = (p1)(q1). Il choisit alors un troisieme nombre premierequi ne divise pas(n) (par conventionevaut souvent 3 ou 65537). A l'aide de l'algorithme d'Euclide etendue, il calcule 06d < (n) tel que ed1 mod(n). Il compose alors deux cles : une publique qu'il transmet a Alice (en clair) et une secrete qu'il conserve pour lui. La cle publique est composee denet dee. La cle secrete est composee denet ded. Les autres entiers ne sont plus necessaires.A la reception de la cle publique (n;e), Alice chire sont messageM2[0;n1[ parC=Memodn(exponentiation modulaire) qu'elle transmet a Bob. Bob dechire alors le messageCen posontM0=Cdmodn.

Nous avons alorsM0=M.

Pour pouvoir utiliser le chirement RSA il nous faut detailler quelques points : commen tcalculer da partir deeet(n);

6. Exponentiation modulaire3

l'exp onentiationmo dulairerapide (p oureectuer des exp onentiationsmo dulaireseca- cement); la g enerationde nom breal eatoire(ou presque) ; commen ttester la primalit e(ou presque) d'un nom brede mani ereecace. Pour calculerdil sut d'appliquer l'algorithme d'Euclide etendu aeet(n). Commeeest premier et ne divise pas(n) les entierseet(n) sont premiers entre eux. Il existe alorsuetv dansZveriantue+v(n) = 1. Les entiersuetvsont obtenus a l'aide de l'algorithme d'Euclide etendu. Pourdon prend alors le reste de la diviosion euclidienne deupar(n).

6 Exponentiation modulaire

Exercice 19.Caculer de maniere naive 410mod 13. Quel est le nombre d'etapes? Une autre strategie permet de reduire le nombre d'etapes. On part de 4

10= 4545. Pour calculer

4

10il sut alors de connaitre 45. De m^eme on a 45= 42424 et 42= 44. On obtient alors :

4

2= 44 = 163 mod 13

4

5= 424243343610 mod 13

4

10= 454510101009 mod 13

Avec cette methode seule 4 multiplicatins sont necessaires. Exercice 20.A l'aide de la methode precedente, imaginer un algorithmeexpmodrapidepre- nant en entree tois entiersa,petnet retournant l'unique entierbveriantbapmodn.

7 Generateurs pseudo-aleatoires

Une suite de bits est ditealeatoiresi elle est imprevisible, c'est-a-dire qu'aucune strategie eective

ne peut mener a un gain inni si l'on parie sur les termes de la suites. Un ordinateur ne peut pas creer de telles suites. Une suite de bits (an)n2Nest ditepseudo-aleatoiresi elle est produite par un algorithme et s'il est algorithmiquement "dicile" de prevoir avec une probabilite>12 le bitan+1a partir des premiers bitsa1;:::;an. D'un point de vu concret les suites pseudo-aleatoires ont un gros defaut, lies au fait que les ressources d'un ordinateur sont limites. Le generateur pseudo-aleatoire retrouvera alors le m^eme etat interne au moins deux fois et la suite sera donc periodique. En 1946, John Von Neumann propose le generateur "middle-square". Son principe est le suivant : 1. on c hoisiten en tierna quatre chires 2. on note mle nombre forme des quatre chires au milieu den2 3. on retourne m 4. on p osen=met on retourne a l'etape 2

Exercice 21.

a.Essayer cette algorithme avecn= 1111. b.Donner un majorant de la periodicite de la suite retournee. c.Quel est la periodicite minimale? Pour quelnest elle atteinte? En 1948, Derrick Henry Lehmer a introduit les generateurs congruentiels lineaires. Le principe est le suivant, on choisit des entiersa,cetnque l'on garde secret. Puis on choisix0et on calcul x i+1a partir dexi, en posantxi+1= (axi+b) modn. 4

Exercice 22.

a.Tester ce generateur poura= 3,b= 4,n= 8 etx0= 5. b.Quelle est la periodicite maximale d'un generateur congruentiel lineaire? Supposons quensoit connu, alors pour retrouveraetbil sut ce conna^tre les trois premiers termesx0,x1etx2. On posey1=x1x0,y2=x2x1.

Exercice 23.

a.Etablir la relationy2ay1modn. b.Comment retrouvera? puisb? b.Retrouver les parametresa;bqui on permis de creer la suite 97;188;235;293;604;596;412 avecn= 1023. Le choix des parametresa,betnd'un generateur congruentielle lineaire in uence l'ecacite du generateur est doit donc ^etre fait avec precaution. Un bon choix est celui utilise parstandard minimal:a= 16807 etn= 2311.

8 Test de primalite

Donnons sans demonstration le petit theoreme de Fermat : Theoreme 24.Sipest un nombre premier etaun nombre non divisible parpon a a p11 modp La reciproque de ce theoreme est fausse : il existe des entiersnnon premier tels que pour tout entierapremier avecnon aitan11 modn(n= 561 par exemple). Un tel entiernest appele nombre de Carmichael. Supposons que l'on veuille tester si un nombrenest premier. On choisit alors des entiers t

0;:::;tk1appeles temoins. Si pour une valeur deidansf0;:::;k1gon atn1i61 modn

alorsnn'est pas premier. Si on ne trouve pas de telialorsnest probablement premier. Ce test est appele test de primalite de Fermat. Les nombres de Carmickael sont detectes comme probablement premier par ce test or ils ne sont par premiers. Le test n'est donc pas s^ur a 100%. Neanmoins les nombres ce Carmickael sont assez rares et si le nombre de temoins est important il est peut probable de tomber sur un nombre non premier et detecter probablement premier. Nous allons utiliser ce test sur des nombres codes sur 32 bits avec les temoins 2;3;5;7;11;13 et 17. Parmi les entiers entre 2 et 2

321, exactement 203280702 sont detectes probablement

premier. Parmis eux seulement 481 ne sont pas premier. La liste complete des exceptions est diponible sur ma page web.quotesdbs_dbs21.pdfusesText_27

[PDF] algorithme de dijkstra python

[PDF] algoritmo de dijkstra java

[PDF] aliexpress france avis

[PDF] alkyl and aryl halides notes pdf

[PDF] alkyl halides notes pdf

[PDF] all google sites list

[PDF] all html5 tags list with examples pdf

[PDF] all police codes mn

[PDF] all the methods in the interface are internally

[PDF] allan_and_barbara_pease_ _body_language_the_definitive_book.pdf

[PDF] allemand langage familier

[PDF] aller + infinitif exercices

[PDF] aller retour paris ajaccio air france

[PDF] aller retour paris nice avion

[PDF] alliance gradebook pinnacle