Chiffrement ElGamal et attaques sur le logarithme discret Option

212227 Chi↵rementElGamaletattaque ssurlelogarithmediscre t

Optionagr ´egationC

ChristopheRitzenthaler

December12,2007

Abstract

R´esum´e:ond´e criticilechi↵rementd'ElGamalet di↵´erentesattaquessurle probl`emedulogarithmedis cret . Ilestra ppel´equ elejuryn'exigepasuneco mpr´ehen sionexh austivedutext e.Vous ˆeteslaiss ´e(e)libred'organiservotredis cussioncommevo usl'entendez.Dessuggestionsde d´eveloppement,largementind´ependantesles unesdesautres,sontpr opos´eesenfindetexte. Vousn'ˆetespa stenu(e)delessuivre. Ilvousestc onseill´edemettre enlumi `erevosc onnais- sances`apartird ufilcon ducteurconstitu´epa rletext e.Lejur ydemandequeladiscussionsoi t accompagn´eed'exemplestrait´esparo rdinateur.Ilestsouhaitable quevousorganisiezvotre pr´esentationcommesilejuryn'avaitpa sconnaissancedu texte.L ejurya uran´eanmoins le textesouslesyeu xpendantvotre expos´e.

1Int roduction

Ilya`a pei neq uelque sann´ees,leprobl `emedelas´ecurit´edestr ansmissionsdedonn´eesse mblait

ˆetrel'apanagedesse ulsmilitaires.C en'estplu slecas,avecl'es sordestechniquesnum´eriques danslecomme rce(In ternet,lescartesdecr´ edit,lest´el´ecommunications,les d´ecodeu rsde

t´el´evision,etc.)Lesm´ethodesempiri questraditionnell esses ontr´ev´el´eestropfragiles;ell es

reposaientsouventsurlesch´ emasuivant:onchoisitu nlivre,u nefoisp ourtoutes,eton consid`erelapermutationdesvin gt-sixl ettresdel'alphabetd´efiniepar lesvingt-s ixpremi`eres lettresdecelivre.Lecod aged'un textec onsistealors`aapplique rc ettepermutati onaute xte `acode r,etled´ecodage`aapp liquer laperm utationr´eciproque 1 aute xte`ad´ecoder.E n num´erique,siparexemplelemessage`a transme ttrees tcod´esur64bits,onpeut employ er cettetechniquee nconsid´erantunepermutation2⌃ 64
.C' estcegenred'id´e esqui est sousjacentauproc´ed´eDES,dˆ u` aIBM,etquiestencoreleplusut ilis´eeninfor matique.Le talond'Achil ledecegenredecryptosyt`em eestle suivant :siquelqu'u nsaitco der,ilsait aussid´ecoder ,carilesttr`esfaciledetrouver laperm utation r´eciproq ued'unepermutat ion sur26,64,128oum ˆem e256lettres.C'es tpou rquoil'apparitiondecryptosys t`emesdits`a cl´epublique ,`alafindusi`ecledernier,af aitsens ation.C escryp tosyst` emes,commelenom l'indique,sonttelsquelecodageest public:t outlemondeconna ˆıtl'algorit hmepou rcoder lemess age.Maisonnepeutpasend ´eduirele d´e codage. Enfait, celarevient `aconstruireu nepermutationd'unens emble`aN´el´ements,maisiciN estgigantes que(del'ordrede10 500
,par exempl e.)Onnepeutmˆemepas´ecrirel aliste deces ´el´ements,etlam´ethodehabituelle pourtrou verlap ermutationr´eciproqued'un epermutation donn´eenepeutpluss 'appliq uer. 1 Nouspr´e sentonsiciunconcurrentdeRSAappel ´eElGamalet quire posesurleprobl`emedu logarithmediscretdans(Z/pZ) 2Chi rementElGammal Soitpungrandn ombrepremi er.Onsaitquelegr oupemultiplicatifH=(Z/pZ) estcy- clique.Soit↵ung´en ´erateurdecegroupe.Ond´efinitlesyst `emede chi↵rementsuivant:

EnsembledesmessagesP=(Z/pZ)

Ensembledeschi

r´esC=H⇥(Z/pZ)

Cl´esecr`ete: a2[0,#H1];

Cl´epublique: p,↵et⌘↵

a (modp); Chi rement:E e (x)⌘(y 1 ,y 2 k (modp),x k (modp)p ourunk2[0,#H1] al´eatoire,di

´erentpourchaquex;

D´echi

rement:D d ((y 1 ,y 2 ))⌘y 2 y a 1 (modp).

Las´ ecurit´educhi

rementreposesurlad i cult´e(pr´esum´ee )ducalculdeasachant. Ceprob l`emeestappel´eprobl`emedulogarithmedi scret(DLP)dansH.On neconna ˆıtpas d'algorithmerapidepourr´esoudrec eprobl`ememaisnou sallonspr´e senterci-dessouscertaines attaquesquiam´eliorel' algorithmen a¨ıfderechercheexhaust ive.

3At taquessurlelogarithmedis cret

3.1Meille ureattaqueg´en´erique

Nouspr´e sentonsicil'algorithmedespasdeb´eb ´e,pasdeg´ eant.SoitungroupecycliqueG d'ordrenetleDLP dansG:↵ x =y.On posem=d p neeton´e cri tx=qm+ravec

0r,q qm+r =y)(↵ m q =y↵ r

Oncalcu led'abordlespasdeb´eb ´e

B={(y↵

r ,r),0rSiontr ouve (1,r)alor sy=↵

r .Si nononcalcule=↵ m .On testeal orspourq=1,2,...,m sil' ´el´ement q estlaprem i`erec omposanted'un´el´ementdeB.D` esquec'estle casonaune solutionduDLP. q estappel´ epasdeg´ean t.

Ilestf aciledevoir quecetalgorithmee stenO(

p #G).

Remarque1.Cettem´ethode doitstockerO(

p #G)´el´ements.Ilexisteunalgorit hmepr ob-

abiliste⇢Pollardquin´ecessitepeud em´emoi re.Lafonction'pseudo-al´eat oire'ut ilis´ee est

f:G!Gd´efiniepar f()= 8 ↵if2G 1 2 if2G 2 y if2G 3 o`uG 1 ,G 2 ,G 3 formentunepartitio ndeG.On choisi tx 0 2 {1,...,n}puisoncalcul e 0 x0 et i+1 =f( i 2

3.2L'atta quedePohlig-Hellman

Nousmontr onsiciqueleDLPdansun groupecycli queGd'ordrenpeutˆetrer ´eduit`ades DLPdans dessous-grou pesd'ordre premierssionconnaˆıtlafactoris ationden n=#G= Y p p e(p)

SoitdoncleD LPdansG:↵

x =y.

1.R´ eductionauxpuissancesdenombres premi ers.Pourchaquediviseurpremie rpden,

onpos e n p =n/p e(p) p np ,y p =y np Chi↵rementElGamaletattaque ssurlelogarithmediscre t

Optionagr ´egationC

ChristopheRitzenthaler

December12,2007

Abstract

R´esum´e:ond´e criticilechi↵rementd'ElGamalet di↵´erentesattaquessurle probl`emedulogarithmedis cret . Ilestra ppel´equ elejuryn'exigepasuneco mpr´ehen sionexh austivedutext e.Vous ˆeteslaiss ´e(e)libred'organiservotredis cussioncommevo usl'entendez.Dessuggestionsde d´eveloppement,largementind´ependantesles unesdesautres,sontpr opos´eesenfindetexte. Vousn'ˆetespa stenu(e)delessuivre. Ilvousestc onseill´edemettre enlumi `erevosc onnais- sances`apartird ufilcon ducteurconstitu´epa rletext e.Lejur ydemandequeladiscussionsoi t accompagn´eed'exemplestrait´esparo rdinateur.Ilestsouhaitable quevousorganisiezvotre pr´esentationcommesilejuryn'avaitpa sconnaissancedu texte.L ejurya uran´eanmoins le textesouslesyeu xpendantvotre expos´e.

1Int roduction

Ilya`a pei neq uelque sann´ees,leprobl `emedelas´ecurit´edestr ansmissionsdedonn´eesse mblait

ˆetrel'apanagedesse ulsmilitaires.C en'estplu slecas,avecl'es sordestechniquesnum´eriques danslecomme rce(In ternet,lescartesdecr´ edit,lest´el´ecommunications,les d´ecodeu rsde

t´el´evision,etc.)Lesm´ethodesempiri questraditionnell esses ontr´ev´el´eestropfragiles;ell es

reposaientsouventsurlesch´ emasuivant:onchoisitu nlivre,u nefoisp ourtoutes,eton consid`erelapermutationdesvin gt-sixl ettresdel'alphabetd´efiniepar lesvingt-s ixpremi`eres lettresdecelivre.Lecod aged'un textec onsistealors`aapplique rc ettepermutati onaute xte `acode r,etled´ecodage`aapp liquer laperm utationr´eciproque 1 aute xte`ad´ecoder.E n num´erique,siparexemplelemessage`a transme ttrees tcod´esur64bits,onpeut employ er cettetechniquee nconsid´erantunepermutation2⌃ 64
.C' estcegenred'id´e esqui est sousjacentauproc´ed´eDES,dˆ u` aIBM,etquiestencoreleplusut ilis´eeninfor matique.Le talond'Achil ledecegenredecryptosyt`em eestle suivant :siquelqu'u nsaitco der,ilsait aussid´ecoder ,carilesttr`esfaciledetrouver laperm utation r´eciproq ued'unepermutat ion sur26,64,128oum ˆem e256lettres.C'es tpou rquoil'apparitiondecryptosys t`emesdits`a cl´epublique ,`alafindusi`ecledernier,af aitsens ation.C escryp tosyst` emes,commelenom l'indique,sonttelsquelecodageest public:t outlemondeconna ˆıtl'algorit hmepou rcoder lemess age.Maisonnepeutpasend ´eduirele d´e codage. Enfait, celarevient `aconstruireu nepermutationd'unens emble`aN´el´ements,maisiciN estgigantes que(del'ordrede10 500
,par exempl e.)Onnepeutmˆemepas´ecrirel aliste deces ´el´ements,etlam´ethodehabituelle pourtrou verlap ermutationr´eciproqued'un epermutation donn´eenepeutpluss 'appliq uer. 1 Nouspr´e sentonsiciunconcurrentdeRSAappel ´eElGamalet quire posesurleprobl`emedu logarithmediscretdans(Z/pZ) 2Chi rementElGammal Soitpungrandn ombrepremi er.Onsaitquelegr oupemultiplicatifH=(Z/pZ) estcy- clique.Soit↵ung´en ´erateurdecegroupe.Ond´efinitlesyst `emede chi↵rementsuivant:

EnsembledesmessagesP=(Z/pZ)

Ensembledeschi

r´esC=H⇥(Z/pZ)

Cl´esecr`ete: a2[0,#H1];

Cl´epublique: p,↵et⌘↵

a (modp); Chi rement:E e (x)⌘(y 1 ,y 2 k (modp),x k (modp)p ourunk2[0,#H1] al´eatoire,di

´erentpourchaquex;

D´echi

rement:D d ((y 1 ,y 2 ))⌘y 2 y a 1 (modp).

Las´ ecurit´educhi

rementreposesurlad i cult´e(pr´esum´ee )ducalculdeasachant. Ceprob l`emeestappel´eprobl`emedulogarithmedi scret(DLP)dansH.On neconna ˆıtpas d'algorithmerapidepourr´esoudrec eprobl`ememaisnou sallonspr´e senterci-dessouscertaines attaquesquiam´eliorel' algorithmen a¨ıfderechercheexhaust ive.

3At taquessurlelogarithmedis cret

3.1Meille ureattaqueg´en´erique

Nouspr´e sentonsicil'algorithmedespasdeb´eb ´e,pasdeg´ eant.SoitungroupecycliqueG d'ordrenetleDLP dansG:↵ x =y.On posem=d p neeton´e cri tx=qm+ravec

0r,q qm+r =y)(↵ m q =y↵ r

Oncalcu led'abordlespasdeb´eb ´e

B={(y↵

r ,r),0rSiontr ouve (1,r)alor sy=↵

r .Si nononcalcule=↵ m .On testeal orspourq=1,2,...,m sil' ´el´ement q estlaprem i`erec omposanted'un´el´ementdeB.D` esquec'estle casonaune solutionduDLP. q estappel´ epasdeg´ean t.

Ilestf aciledevoir quecetalgorithmee stenO(

p #G).

Remarque1.Cettem´ethode doitstockerO(

p #G)´el´ements.Ilexisteunalgorit hmepr ob-

abiliste⇢Pollardquin´ecessitepeud em´emoi re.Lafonction'pseudo-al´eat oire'ut ilis´ee est

f:G!Gd´efiniepar f()= 8 ↵if2G 1 2 if2G 2 y if2G 3 o`uG 1 ,G 2 ,G 3 formentunepartitio ndeG.On choisi tx 0 2 {1,...,n}puisoncalcul e 0 x0 et i+1 =f( i 2

3.2L'atta quedePohlig-Hellman

Nousmontr onsiciqueleDLPdansun groupecycli queGd'ordrenpeutˆetrer ´eduit`ades DLPdans dessous-grou pesd'ordre premierssionconnaˆıtlafactoris ationden n=#G= Y p p e(p)

SoitdoncleD LPdansG:↵

x =y.

1.R´ eductionauxpuissancesdenombres premi ers.Pourchaquediviseurpremie rpden,

onpos e n p =n/p e(p) p np ,y p =y np