Ecole normale superieure Departement d'informatique

Publié par

Ecole normale superieure 2011-2012 Departement d'informatique Introduction a la cryptologie TD n? 5 : Cryptographie asymetrique 2/3 Un nombre compose n est dit de Carmichael si il est pseudo-premier de Fermat en base a pour tout entier a > 0 premier avec n. Exercice 1. 1. Montrer qu'un nombre de Carmichael est necessairement impair. Soient n un nombre de Carmichael et p un facteur premier de n. 2. Montrer que p2 ne divise pas n. 3. Montrer que p ? 1 divise n ? 1. On pourra considerer une racine primitive a modulo p et montrer que an?1 = 1 mod p. 4. Reciproquement, montrer que si n est un entier compose sans facteur carre, et tel que pour tout entier p divisant n, p? 1 divise n? 1 alors n est un nombre de Carmichael. 5. En deduire qu'un nombre de Carmichael a au moins trois diviseurs premiers. Exercice 2. 1. Demontrer le critere d'Euler 2. Montrer que si p est premier alors Z?pt est cyclique pour tout entier t ≥ 1. 3. Montrer que si n ≥ 3 n'est pas premier alors pour (au moins) la moitie des a ? Z?n, nous avons (a n ) 6? a(n?1)/2 mod n. 4.

  • racines carrees dans zn en temps ?

  • signature de ?

  • carre modulo

  • complexite de l'algorithme de signature

  • factorisation par divisions successives

  • methode de la question precedente

  • module rsa

  • extraction de racine carree modulo


Publié le : mardi 19 juin 2012
Lecture(s) : 56
Source : di.ens.fr
Nombre de pages : 3
Voir plus Voir moins
´ Ecolenormalesup´erieure D´epartementdinformatique
Introduction`alacryptologie TDn5:Cryptographieasym´etrique2/3
2011-2012
Unnombrecompose´nest dit de Carmichael si il est pseudo-premier de Fermat en baseapour tout entiera >0 premier avecn. Exercice 1. 1.MontrerquunnombredeCarmichaelestn´ecessairementimpair. Soientnun nombre de Carmichael etpun facteur premier den. 2 2. Montrerquepne divise pasn. 3. Montrer quep1 divisenuneracersionerd´uopncarrO.1itevnipeirimamodulopet montrer que n1 a= 1 modp. 4.Re´ciproquement,montrerquesinrientteesuarnpsofasc´´rec,oemcnatrireuuqtpeenttlseeuoetuotrp divisantn,p1 divisen1 alorsnest un nombre de Carmichael. 5.Ende´duirequunnombredeCarmichaelaaumoinstroisdiviseurspremiers.
Exercice 2. 1.De´montrerlecrit`eredEuler 2. Montrerque sipest premier alorsZtest cyclique pour tout entiert1. p 3. Montrerque sinalomni)sdeseti´iorsperalaumoour(tsen3imerpsapaZ, nous avons n   a (n1)/2 6≡amodn. n 4.End´eduirepourtoutentierTuanrtneineeu´etrenenntnaerp,iuqemhtirogln, retourneCs´eompoou 3 PremierenO(Tlogneseroetuqirna,desioatbinso)re´p – sil’algorithme retourneCompos´e, alorsn;´eecoreosmpsrnuonbmtsotjuuo T – sil’algorithme retournePremierorsl,alqeeuil´tabibpaorn.stees´poomtcois2a`erueire´fni
Exercice 3.SoientNun moduleRSA, 2< e < Nun entier premier avecϕ(N) et 2< d < ϕ(N) l’inverse dee moduloϕ(Nnodtse´n´,iunatelibieqstlopnitarba)r.oMeliuqreanuetsixhmitorlgomynolepN,eetd, retourne la factorisation deN.
Exercice 4. 0 1.Montrerquesilondisposedeschir´esRSAcetclciadnu´larotaeerimclunrlaiei´dtem+ru`,o 0< r < N(euqpourunecl´epublietsocnn,uN, e= 3), alors on peut retrouvermen temps polynomial. 2.Montrercommentge´n´eralisercetteapprochepourtoutentiere. 3.Application.trreveouteenurpoegmelrassehodedelaerlam´etrpe´´cdeuqseitnosilitUmvairten´c= 17017 mmodNetc= (mmod+ 1)Navec N= 4750268523286534182543999246472514570042418299923101154793593 c= 1935621880512522306378371392939548737091684771868008026431626 0 c= 1011424881854699101846188248967755233987658392601847378035075.
Exercice 5(Factorisation par divisions successives).Factoriser l’entier
n= 3148240326296492491829836036538028522262397298543021512290073
par divisions successives.
1
Exercice 6F(caotirtr)lam´ethosdaetFieornmpaa.Factoriser l’entier
n= 4433634977317959977189716351978918572296527677331175210881861
parlam´ethodedeFermat.
Exercice 7ethoderositaoipnraal´mtcaF(p1 de Pollard).Factoriser l’entier
n= 117827681420271584017432903522327303325344948050665323956545863
parlame´thodep1 de Pollard.
Exercice 8E(artxacinecarctionderol´reeomudp).Soitpun nombre premier. 3 1. Noussupposons queppmocixele´tDonnod4.3memedirhtlaogrenuO(logpanriseuq,i)oerp´ioatbins   α2 e´tantdonn´eα∈ {1, . . . , p1}tel que= 1, retourneβ∈ {1, . . . , p1}tel queβαmodp. p h Noussupposonsd´esormaisquep1 mod 4. Posonsp= 2m+ 1avecmimpair. 2.Donnerunalgorithmeprobabilistequie´tantdonne´prtneln´me´eoueteurnγde{1, . . . , p1}tel que   γ2m =esp´empse1tner´eO(logps.reaiinrqrentMoe´po)bsnoitareuoprunuetlγel´ementl,´δ=γ p hengendre l’unique sous-groupe d’ordre 2deZ. p m 3. Soitα∈ {1, . . . , p1}tel que (α|p) = 1. Montrer queαatsuitneppraaenpendges-ouougrpe´rraδet en utilisantunalgorithmedelogarithmediscret,end´eduireunalgorithmepourcalculeruneracinecarre´de m αmodulop. 3 4.Conclureendonnantunalgorithmepermettantdecalculerlesracinescarre´sdeαen tempsO((logp) + 2 hlog(h) log(p) ).
` Exercice 9(Eraxtiocterndceracaniomud´reelop).Soitpun nombre premier impair et`2 un entier. 2` ` 1. Montrerqu’un entierxpremier avecpvri´eex1 modpsi et seulement six≡ ±1 modp. ` 2. Montrerqu’un entierxpremier avecpcaunsteoludome´rrpsi et seulement sixrrcamo´eloduenutsp. ` 3.Donnerunalgorithmepourcalculeruneracinecarre´edexmodulop. Indication.cerpmmenlcularcanOarocopruedeeecinr´aruneracerxmodulopsiupevemtnr´ecursicalculer i+1i uneracinecarre´edexmodulopenudritrapa`ederr´enecaracixmoduloppour tout entieri{1, . . . , `1}.
Exercice 10(Eoitcartxnicaredneer´areclodumoN).SoitNnuneitreodntlad´ecompositinenotcafrue f1fd premier estN=q .. . qou`qiPsont des nombres premiers etfi1 pouri∈ {1, . . . , d}). 1d   x 1. Montrerqu’un entierxestunudolacrre´omNe´tnodse`a`xuagssleboymuesqustordneedselgeLe qj 1 pourj∈ {1, . . . , d}. d 2.Montrerquuntelcarr´emoduloNarsceer´s.etcatnemar2enicaex 3. Montrerque s’il existe un algorithmeAsee´rracsenicarsdereaitrexdleabcapdansZNen tempsτ, alors 1d il existe un algorithmeBqui retourne un diviseur propre deNntempses´pree´eO(τ(12 )).
Exercice 11ngisrutalocoedseetgeauCheDedoneJS()medesprot´ecurit´.´drenoisuocsNntesariaeuxvonsd dusche´madesignatureRSAldeumole`uoN=pqest le produit de deux nombres premierspetqditsforts 0 00 0 (i.e.p= 2p+ 1etq= 2q+1o`upetqsont premiers). ∗ ∗m 1. Supposonsque la signature d’un message impairmZest l’entierσZ, s’il existe, tel queσ= N N mmodNousulleserseunivc¸noerafoctnuaent`anstsi´esrpastename´hcseceuqr.Montreatnequtaae` deux messages choisis. ∗ ∗2m+1 2. Supposons que la signature d’un messagemZest l’entierσZ, s’il existe, tel queσ= N N mmodN.oMaqtruequ`teneartsapnae´hmeeccsauneant`sistsr´evinunoc¸afertnocatnesuouesllseer deux messages choisis.
2
Indication.On pourra chercher deux messagesm1etm2detsd(pe´eanndm) et deux entiersaetbtels que a b σ=s σ1 2oit une signature valide dem`u(oσ1etσ2sont les signatures dem1etm2).
Exercice 12ignaturedeBoyd)(ecS´iturude´torplocosede.oNsuocsndie´orsnocotprunigesedolerutan nume´riqueo`ulacl´epubliqueestuncoupledentiers(N, gtuneteescr`e´eseallc)tereitnrtelles que (i)Nest le produit de deux nombres premiers distinctspetq(i.e.N;est un module RSA) (ii)rest un diviseur premier dep1 ; (iii)geseutme´eeln´drordntrdansZ. N Nous notonskla taille en bits des nombres premierspetqet`la taille en bits de l’entierr. La signatureσ m d’un entiermde taille`est la racinemeemed-`gdansZ(i.e.σ=g). N 1. Montrerque sirne divise pasq1, alors la connaissance de (N, g) permet de factoriser l’entierN. Nous supposerons dans toute la suite de l’exercice que : (iv)rdiviseq1 ; 2.Proposerunalgorithmeprobabilistequi,prenantenentre´edeuxentiersket`, retourne un triplet (N, g, r) v´eriantlespropri´ete´s(i)(iv)etcomparerlacomplexit´edelalgorithmedesignatureaveccelledela signatureRSAclassique. 3.Bris total. `/2(a)Donnerunalgorithmedecomplexite´Onodsaritpoe´)(2upeegroanslZpermettant de retrouver N ra`aptrriedalnndoep´eliube(quN, g). 1/4 (b) Montrer que sirest connu alors il est possible de factoriserNenO(N /ro)oitare´psnadsnel groupeZ. N Indication :en notantp=xret+ 1q=yr+ 1et (N1)/r=ur+vavec 0v < r, on pourra utiliser un algorithme de logarithme discret pour retrouver laretenuecne´drapeix+y=v+cr   et montrer que sa connaissance est suffisante pour retrouverpetq. 4.ntrefa¸conuniveresll.eoC (a)Montrerquilexisteunalgorithmepolynomialquiprenantenentr´eeNet un entiermpremier avecr, retourne un entierγtel que1 modrE.dnnecontre´eduireuusenseuouqetaatonunfa¸cselliver a`cle´seulecontrelesche´madesignaturedeBoyd. Noussupposeronsd´esormaisque: (ii’)rest un diviseurc´ospmeodep1 de taille`; et qu’il est difficile de calculer un multiple der. (b) Montrerque la connaissance de la signature de deux messagesm1etm2premiers entre eux permet de calculer la signature du message produitm=m1m2d´En).ntmeueoqprfertnocenueriudena¸coe(rte´ic universellesousuneattaquea`deuxmessageschoisiscontrelesch´emadesignaturedeBoyd. Noussupposeronsde´sormaisque: H(m) (v) Lasignatureσd’un messagem∈ {0,1}est la racineH(mde)-i`emeg(i.e.σ=g`ou)H: ` {0,1} →{0,1}est une fonction de hachage cryptographique (dans la suite nous supposerons queHire).fenotcoian´laeotnuemmocetropmoces 5..Contrefa¸enoctsixitneelle Montrer que la connaissance d’un ensemble de messages{m, m1, . . . , mt}t:anire´v H(m) =a1a2∙ ∙ ∙atesulo`airsenemieuxpr`adexu;rteesoxuedsreitnesedtn aidiviseH(mi) pouri∈ {1, . . . , n} estsusantepourmonterunecontrefac¸onexistentiellesousuneattaquea`messageschoisis.Ende´duire quelesch´emanestpasre´sistantauxcontrefa¸consexistentielleslorsque`est significativement plus petit quek.
3
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.