Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Ecole normale superieure Departement d'informatique

3 pages
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


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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin