7 jours d'essai offerts
Cet ouvrage et des milliers d'autres sont disponibles en abonnement pour 8,99€/mois
´ 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