Feuille de TP Codage RSA

De
Publié par

Niveau: Secondaire, Lycée, Première
Feuille de TP 2 - Codage RSA L'objet de cette feuille de TP est de donner une application à la cryptographie des résultats obtenus dans la partie Arithmétique du cours . Plus précisément, nous introduisons les principes de la méthode de Ron Rivest, Adi Shamir et Len Adleman, dite méthode RSA. Il faut faire le TP en parallèle avec les Exercices de la Feuille TP 2 - Exercices préliminaires : Exercice 1 (Classes modulo n) Exercice 2 (Indicatrice d'Euler) Exercice 5 (Petit Théorème de Fermat) Exercice 6 (Principe Codage RSA) Exercice 7 (Echange de clés) 0. PB (2007-09-30-mat231_tp02.mws) 1. Initialisation Dans une première approche, et pour limiter le temps de calcul, on choisira des nombres pas trop grands. NB : On note as un nombre destiné à rester secret et Np un nombre destiné à être public. On choisit deux nombres premiers a et b de l'ordre de 200 et 300.nombres premiers a et b de l'ordre de 200 et 300. Exercice Mettre en oeuvre cette étape avec des nombres premiers a et b de l'ordre de 200 et 300 (voir Exercice 6). Exercice Trouver l'inverse cs (secret) de Cp modulo fs (Voir Exercice 6, Question 1)

  • espace quotient de z par la relation d'equivalence ?

  • contrôle de temps d'exécution

  • exercices préliminaires

  • tp en parallèle avec les exercices de la feuille

  • inverse de l'application ?


Publié le : mercredi 30 mai 2012
Lecture(s) : 65
Tags :
Source : www-fourier.ujf-grenoble.fr
Nombre de pages : 6
Voir plus Voir moins
Feuille de TP 2 - Codage RSA
L'objet de cette feuille de TP est de donner une application à la cryptographie des résultats obtenus dans la partie "Arithmétique" du cours .
Plus précisément, nous introduisons les principes de la méthode de Ron Rivest, Adi Shamir et Len Adleman, dite "méthode RSA".
Il faut faire le TP en parallèle avec les Exercices de la Feuille "TP 2 - Exercices préliminaires" :
Exercice 1 (Classes modulo n) Exercice 2 (Indicatrice d'Euler) Exercice 5 (Petit Théorème de Fermat) Exercice 6 (Principe Codage RSA) Exercice 7 (Echange de clés)
0. PB (2007-09-30-mat231_tp02.mws)
1. Initialisation
Dans une première approche, et pour limiter le temps de calcul, on choisira des nombres pas trop grands.
NB : On noteun nombre destiné à restersun nombre destiné à êtreecret etpublic. as Np
On choisit deux nombres premiers a et b de l'ordre de 200 et 300.nombres premiers a et b de l'ordre de 200 et 300.
Exercice Mettre en oeuvre cette étape avec des nombres premiers a et b de l'ordre de 200 et 300 (voir Exercice 6).
Exercice Trouver l'inverse cs (secret) de Cp modulo fs (Voir Exercice 6, Question 1)
2. Codage et décodage d'un nombre plus petit que (Np-1)
Exercice Ecrire une procédure de codage et une procédure de décodage (voir Exercice 6, Question 2, fonctionsCetD). Vérifier que ces procédures correspondent à des fonctions inverses l'une de l'autre.
3. Avec des nombres plus grands ...
Exercice Recommencer ce qui vient d'être fait avec des nombres premiers initiaux plus grands, par exemple de l'ordre de 500. Introduire un contrôle de temps d'exécution. Conclusion.
4. Transmission de messages cryptés
Transmission de messages cryptés
Exercice Décrire une procédure possible de transmission de messages cryptés basée sur ce qui précède et sur les Exercices 6 et 7 de la Feuille "TP 2 - Exercices préliminaires".
Exercice a)deEn utilisant un contrôle de temps d'exécution, appliquer la fonction nextprime MAPLE à des grands nombres : nombres d'une trentaine de chiffres, nombres de la forme n a10#b oùaetbont unevingtaine de chiffres et oùnen a une centaine. b)de MAPLEEn utilisant un contrôle de temps d'exécution, appliquer la fonction ifactor à des grands nombres (nombres d'une vingtaine de chiffres, trentaine de chiffres et cinquantaine de chiffres). c)Sur quelle hypothèse de travail peut-on baser la sécurité des transmission par la méthode décrite dans l'exercice précédent.
4. Calcul d'une puissance
Exercice n Montrer que le calcul brutal dea modulom nécessitede l'ordre den opérations. Donner un algorithme, basé sur l'écriture denen base 2, nécessitant de l'ordre deln(n)opérations. Faire des tests de rapidité d'exécution avec MAPLE.
Références
Universite´JosephFourierL2MAT2312007-2008 2007-10-15-mat231_feuille_exos_04.tex (24 octobre 2007)
o Feuille d’exercice n4
CertainsdesexercicesdecetteFeuillesontn´ecessairesa`lacompre´hensionde ladeuxi`emefeuilledeTP.
Notations.
  – PournN, on noteRn:= 0,1, . . . , n1 . ´ Etantdonn´esdeuxentiersu, vavecv >se´dengino,0ripam(reu, v) le reste de la division euclidienne deuparv. – OnnoteZnl’espace quotient deZrlarelationd´eqipuaavelcne(modne,c-`stdia-re) l’ensemble des classes modulon. – On noteen:ZZnuinqioattienun`arelpcilpaxassocie sa classe modulon. On rappelle queZnest en bijection avecRnpar la formuleen(x) =en(irem(x, n)). On note ¯ ¯ e´galement0,1, . . .e´em´sleeelntsdZn, voire plus simplement encore 0,1, . . . ,(n1) quand ilnyapasdambiguı¨t´e.Onnoteraenparticulier0,laclassedelentier0,et1,laclasse de l’entier 1.
Les questions suivies de la mention “[Facultatifheneisnoalocpm´rptnosen]`aesirsaesecn´as du TP.
Exercice 4.1 (Classes modulon)SoitnN. ´ 1.Etantdonn´esx, yN, montrer queen(x+y)ndpe´eedeedqunen(x)et deen(y). En de´duirequelonpeutainsid´eniruneaddition(encorenote´e+) surZn. ´ 2.Etantdonne´sx, yN, montrer queen(x×y)uqdeepdndee´enen(x)et deen(y). En d´eduirequelonpeutainsid´enirunemultiplication(encorenot´ee×) surZn. 3. Montrerque(Zn,+,×)est un anneau commutatif. [Facultatif] 4. Montrerque les anneauxZ6,Z12admettent des diviseurs de0(linssenoptsani`tgeer)s, cest-a`-diredes´el´ementsnonnulsα, βarinte´vα×β= 0. Donner une condition ge´n´eralepourqueZnadmette des diviseurs de0. 5.Montrerquun´el´ementαdeZnest inversible (pour la multiplication) si et seulement s’il existemαriuea`d-se-t(crientnemdont la classe modulonestα) tel que pgcd(m, n) = 1vnreesedD´.eretnemiirlαau moyen dem. 6. MonterqueZpest un corps si et seulement sipest un nombre premier.
MAT 2312007-2008
Exercicescomple´mentaires.
2
Lesdeuxexercicessuivantscomple`tentlExercice4.1.Ilsnesontpasne´cessairesa`lacompr´e-hension du TP.
´ Exercice 4.2 (Classes modulon, suite)snn´eodtnatEαZnetkN, on noterale´le´mentα+∙ ∙ ∙+α(kfois), avec la convention que0α= 0, la classe0). On dira qu’un ´elementαengendreZnut´el´emsitodtneeZnest de la formepour un certainkN. 1. Montrerque1engendreZnpour toutnNelare´nenom,tnemtrerqueg´usPl.αest ung´en´erateurdeZnsi et seulement siαest inversible (pour la multiplication) dans Zn. ´ 2. Soientm, nNodnnattn.E´eαZmn, montrer que le couple(em(x), en(x))ne d´ependpasduchoixdexαintaeunpnied´silppaenurnoitaci.requeloEnd´edui ΦdeZmndansZm×Zn. 3. Onsuppose quepgcd(m, n) = 1. Montrer queΦest bijective. 4. On suppose toujours quepgcd(m, n) = 1. On se donne(α, β)Zm×ZnetxZ unrepr´esentantdeα,yZetdnuerrpe´estnnaβns.O´eneonedtnemelagu, vdes entiers tels quemu+nv= 1. Montrer que l’application(x, y)7→xnv+ymupermet de construire l’applicationΨqui est l’inverse de l’applicationΦ.oi2neutslaqae`nied´
Exercice 4.3vinaet(suqleopneles´equationssurgnocneusetovuedurrRc´oeismeomscde oucommedes´equationsdansuncertainZn). 1.6x4 (mod10). 4 2.3x2 )1 (mod. 3.x2 (mod3)etx5)3 (mod.
Exercice 4.4 (Indicatrice d’Euler)SoitnN. On notePnl’ensemble Pn:={rN|1rnetpgcd(r, n) = 1}. Onde´nitlafonction indicatrice d’Eulerpar ϕ(n) = Card(Pn). 1. Calculerϕ(p)pourppremier. α 2. Calculerϕ(p)pourppremier. 3. Calculerϕ(pq)pourp, qpremiers. 4.Plusge´n´eralement,montrerqueϕ(mn) =ϕ(m)ϕ(n)pour tousm, nN, premiers entre eux. [Facultatif] 5. PourmN, exprimerϕ(m)notcoidnefnmpositioelad´ecoresactenenfremiursp dem. [Facultatif] 6. Montrerqueϕ(n)eltsederbmonicplioatanndsbielpsuolrmaluit´el´ementsinversZn. [Facultatif]
Exercice4.5(Petitthe´ore`medeFermat)Soitpun nombre premier. k 1. MontrerquepˆomeentdubineloceicidivesCpour toutktel quek6= 0etk6=p. p 2. Montrerque p p aa0 (modp)eid-auqerec`-tspdiviseaa pour tout entieraN. [Indication :urecR´rusecnera.]
MAT 2312007-2008
3
Exercice 4.6 (Principe codage RSA)Soienta, bdeux nombres premiers distincts. On consid`ereleurproduitN:=a×bet on choisit un nombreCiuqre´vei 1Cϕ(N)etpgcd(C, ϕ(N)) = 1. 1. Montrerqu’il existe un nombresntari´ev1s < ϕ(N)ets C1 (modϕ(N)). 2.Onde´nitdeuxapplicationsCetDdeRNanduislrm-eˆemap C s C(M) := irem(M,N)etD(M) := irem(M,N). Montrer que ces deux applications sont inverses l’une de l’autre. m mm1m2m2 2m2 ´ Indications.e(t´Eatlbrildineitxy) = (xy)x+x y+x y+∙ ∙ ∙xy+ m1s sC ´ y´edonntant.EM∈ RNetP:=C(Mlppa,)´eitntdeirlueiqneeta`rpe´´cdePM sC puis montrer queNdiviseMMa`etriepFeth.´mtatari`leoeddudeem Les nombresN, Csont lesspubliqusecl´edu codage RSA. Le nombresest la´eclete`rces. Lexercicesuivantfournitunemanie`rede´changerunecle´secr`etecommune.
´ Exercice4.7(Echangedecl´es)On reprend les notations de l’Exercice 4.6. Soient deux correspondantsAliceetBob.Alicefournitlescle´spubliquesNetC. Elle choisitxx RNet envoie le nombreX:= irem(NC ,)cboh.boBa`oBitisy∈ RNet calculem:= y yx irem(X ,N)etY:= irem(C ,N). Il envoie alorsY.ecitnoMqrereu`aAlm= irem(Y ,N). AliceetBobdisposentmaintenantdunecl´esecre`tecommunem.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.