Public key cryptography [Elektronische Ressource] : theory and practice / von Bodo Möller

Description

Public-Key CryptographyTheory and PracticeVom Fachbereich Informatikder Technischen Universit at DarmstadtgenehmigteDissertationzur Erreichung des akademischen GradesDoctor rerum naturalium (Dr. rer. nat.)vonDipl.-Inform. Bodo M olleraus HamburgReferenten: Prof. Dr. Johannes Buchmann (TU Darmstadt)Prof. Dr. Christof Paar (Ruhr-Universit at Bochum)Tag der Einreichung: 1. Juli 2003Tag der mundlic hen Prufung: 16. September 2003Darmstadt, 2003Hochschulkennzi er: D 17Viele haben auf die eine oder andere Weise dazu beigetragen, dass diese Dissertation so entstehenkonnte, wie sie nun vorliegt. Der Versuch einer vollst andigen Aufz ahlung musste scheitern; hier seienzun achst die erw ahnt, die nicht mit Namen genannt werden k onnen, weil sie als anonyme Gutachterfur Konferenzen atigt waren und dabei Anregungen zur Darstellung einiger der hier pr asentiertenErgebnisse beigetragen haben. Au erdem zu nennen ist David Hopwood, der in einer fruheren Fassungder Ausfuhrungen zur beweisbaren Sicherheit des Mix-Verfahrens (hier in Abschnitt 4.2) eine Luc keaufgespurt hat. Prof. Johannes Buchmann hat es auf bemerkenswerte Weise verstanden, die Arbeits-bedingungen zu scha en, in denen diese Dissertation gedeihen konnte, und hat wertvolle Anregungengeliefert. Auch alle anderen am Fachgebiet Theoretische Informatik hatten teil daran, eine angenehmeund fruchtbare Arbeitsatmosph are zu scha en. Danke!Darmstadt, im September 2003 B. M.

Sujets

• Informatik

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2003
• Nombre de lectures: 29
• Langue: Deutsch

Extrait

Public-KeyTheoryandCryptographPracticey

ten:Referen

VomFachbereichInformatik
derTechnischenUniversit¨atDarmstadt
genehmigte

Dissertation

zurDoctorErreichrerumungdesnaturaliumakademisc(Dr.henrer.Gradesnat.)

von

ollerM¨doBoDipl.-Inform.

burgHamaus

Prof.Dr.JohannesBuchmann(TUDarmstadt)
Prof.Dr.ChristofPaar(Ruhr-Universit¨atBochum)

TagderEinreichung:1.Juli2003
Tagderm¨undlichenPr¨ufung:16.September2003

2003Darmstadt,Hochschulkennziffer:D17

VielehabenaufdieeineoderandereWeisedazubeigetragen,dassdieseDissertationsoentstehen
konnte,wiesienunvorliegt.DerVersucheinervollst¨andigenAufz¨ahlungm¨usstescheitern;hierseien
zun¨achstdieerw¨ahnt,dienichtmitNamengenanntwerdenk¨onnen,weilsiealsanonymeGutachter
f¨urKonferenzent¨atigwarenunddabeiAnregungenzurDarstellungeinigerderhierpr¨asentierten
Ergebnissebeigetragenhaben.AußerdemzunennenistDavidHopwood,derineinerfr¨uherenFassung
derAusf¨uhrungenzurbeweisbarenSicherheitdesMix-Verfahrens(hierinAbschnitt4.2)eineL¨ucke
aufgesp¨urthat.Prof.JohannesBuchmannhatesaufbemerkenswerteWeiseverstanden,dieArbeits-
bedingungenzuschaffen,indenendieseDissertationgedeihenkonnte,undhatwertvolleAnregungen
geliefert.AuchalleanderenamFachgebietTheoretischeInformatikhattenteildaran,eineangenehme
undfruchtbareArbeitsatmosph¨arezuschaffen.Danke!

Darmstadt,imSeptember2003

M.B.

Abstract

3

TheoryI:artPProvablesecurityisanimportantgoalinthedesignofpublic-keycryptosystems.Formost
securityproperties,itiscomputationalsecuritythathastobeconsidered:anattackscenario
describeshowadversariesinteractwiththecryptosystem,tryingtoattackit;thesystemcan
becalledsecureifadversarieswithreasonablyboundedcomputationalmeanshavenegligible
prospappropriateectsofsensesuccess.meansThethatlackofthereislittlecomputationalhopeforproblemsabsolutethatproareofsofguaranteedcomputationaltobehardsecuritinyan.
complexInstead,cryptographicreduction-basedschemesecuritisyprorelatedofstohavethetobsecuriteyused:ofthesimplercomputationalunderlyingsecuritcryptographicyofa
primitives(underappropriatenotionsofsecurity).Theideaistoshowthatifthecomplex
scdescribhemeedisnotquansecure,titativelythenasthisis“concretebecausesecuritoney”,ofthemeasuredprimitivdepesisendingnotonsecure.thepowSecuriterygivcanenbtoe
ersaries.advTheDHAESconstruction(duetoAbdalla,Bellare,andRogaway)allowsbuildingapublic-
keyencryptionschemefromakeyencapsulationmechanism(KEM),aone-timemessage
authenticationcode(one-timeMAC),andapseudo-randombitstringgenerator.Areduction-
basedsecurityproofshowsthatDHAESachievessecurityagainst(adaptive)chosen-ciphertext
attacgeneralksifattacthesekscenariounderlyingforprimitivpublic-keseyaresecure.encryption.)(Suchchosen-ciphertextattacksarethemost
Aspecificapplicationforpublic-keycryptographyisconsidered,namelyChaum’smix
chainwithoutconceptrequiringforuntrusttraceableinasingleelectronicauthoritmaily,viamessagescryptographicarerecursivremailers:elytopublic-kobtaineyanonencryptedymity
latoyermofultipleinencryption.termediatesToconceal(mixes),asmeacuchhofwhicinformationhforwaspardsossiblethewhenmessageusingaftervariableremoving(sourceone
routed)chains,allmessagespassedtomixesshouldbeofthesamelength;thus,message
lengthshouldnotdecreasewhenamixtransformsaninputmessageintothecorresponding
outputmessagedirectedatthenextmixinthechain.Chaumdescribedanimplementationfor
suchlength-preservingmixes,butitisnotsecureagainstactiveattacks.Thisthesispresents
anewconstructionforpracticallength-preservingmixes,whichusesthecryptographicprim-
itivesdescribedforDHAES.Theconventionaldefinitionofsecurityagainstchosenciphertext
attacpropriateksforsecuritpublic-kyeydefinitionsencryptionarescintrohemesduced;isnotitisshoapplicablewnthattothemixlength-preservingconstructionmixes,acsohievap-es
provablesecurity.

PracticeI:IartPMostinstantiationsofpublic-keycryptographyinvolvecomputingpowers(exponentiation)
orcomputingpowerproducts(“multi-exponentiation”)insomecommutativesemigroupwith
neutralelement.Thisthesisdescribestheslidingwindowtechniqueforarbitrarycommuta-
tivesemigroupswithneutralelementanditssigned-digitvariant(“windowNAF”)forgroups
whereinversionisfast(e.g.pointgroupsofellipticcurvesandclassgroupsofimaginary
quadraticnumberfields),andthenpresentsnewtechniques.Fractionalwindows,agen-
eralizationofthepreviouslyknownwindowmethods,canbeusefulfordeviceswithlimited
storage.Interleavedexponentiationisasimplestrategyformulti-exponentiation;thecompar-
isonwithprevioussimultaneousexponentiationmethodsshowsthatitoftenprovidesbetter

4

.efficiency

WindowNAFsplittingisamethodforfastexponentiationwithprecomputation

forafixedbaseingroupswhereinversionisfast.

Forthecaseofellipticcurves,side-channelattacksarediscussed,i.e.attackswhereadver-

sariesusepowerconsumptionmeasurementsorsimilarobservationstoderiveinformationon

secretvalues.Twomethodsareshownthataredesignedtolimitpotentialinformationleak-
ageavailabletoadversaries:a2w-aryleft-to-rightmethodemployingspecialrepresentations
ofscalars,anda2w-aryright-to-leftmethodwithaspecialrandomizedinitializationstage.

of

scalars,

and

a

2

-ary

right-to-left

method

with

methodemployingspecialrepresentations

a

special

randomized

initialization

stage.

Zusammenfassung

5

TheorieI:eilTBeweisbareSicherheitisteinwichtigesZielbeimEntwurfvonPublic-Key-Kryptosystemen.
F¨urdiemeistenSicherheitseigenschaftenmusshierbeipraktischeSicherheitgegenAngreifer
mitbeschr¨anktenMittelnbetrachtetwerden:EinAngriffsszenariobeschreibt,wieGegner
mitdemKryptosysteminteragierend¨urfen,umesanzugreifen;dasSystemkanndannals
sicherbezeichnetwerden,wennGegnermiteinempraktikablenRechenaufwandnurver-
nachl¨assigbareErfolgsaussichtenerzielenk¨onnen.DaeskeineBerechnungsproblemegibt,die
bewiesenermaßenineinemgeeignetenSinneschwersind,gibtesnurwenigHoffnungf¨ur
absoluteSicherheitsbeweiseimSinnesolcherpraktischerSicherheit.Stattdessenmussauf
reduktionsbasierteSicherheitsbeweisezur¨uckgegriffenwerden:DiepraktischeSicherheiteines
komplexenkryptographischenSystemswirdzuderSicherheiteinfachererzugrundeliegender
kryptographischerPrimitive(mitjeweilspassendenSicherheitsbegriffen)inBeziehunggestellt.
DerGrundgedankeist,zuzeigen,dassdaskomplexeSystemnurdannunsicherseinkann,
wenneinederPrimitivenunsicherist.DieSicherheitkannals,,konkreteSicherheit“quantita-
tivbeschriebenwerdeninAbh¨angigkeitvondenMitteln,dieGegnernzurVerf¨ugungstehen.
MitdemDHAES-SchemavonAbdalla,BellareundRogawaykannmanauseinem
Schl¨usselaustauschverfahren(keyencapsulationmechanism,KEM),einemEinmal-MAC
(messageauthenticationcode)undeinemPseudozufallsbitstringgeneratoreinPublic-Key-
Verschl¨usselungsverfahrenkonstruieren.EinreduktionsbasierterSicherheitsbeweiszeigt,dass
DHAESSicherheitgegen(adaptive),,Chosen-ciphertext“-Angriffeerzielt,fallsdiezugrun-
deliegendenPrimitivesichersind.(SolcheChosen-ciphertext-Angriffesinddasallgemeinste
Angriffsszenariof¨urPublic-Key-Verschl¨usselung.)
EinespezifischeAnwendungf¨urPublic-Key-Kryptographiewirdbetrachtet,ChaumsMix-
Ketten-Konzeptf¨urnichtverfolgbareE-Mail¨uberkryptographischeRemailer:DamitAb-
senderAnonymit¨aterreichenk¨onnen,ohneeinereinzelnenStellevertrauenzum¨ussen,werden
Nachrichtenrekursivf¨urmehrereZwischenstellenverschl¨usselt(die,,Mixe“),diejeweilsdie
Nachrichtweitersenden,nachdemsieeineEbenederVerschl¨usselungentfernthaben.Umbei
derBenutzungvonvariablenMix-KettensowenigInformationwiem¨oglichzuverraten,sollten
alleanMixegesandteNachrichtendiegleicheL¨angehaben;alsosolltedieNachrichtenl¨ange
sichnichtverringern,wenneinMixeineankommendeNachrichtumwandeltindieNachricht,
dieerandenn¨achstenMixinderKetteweiterzuleitenhat.DievonChaumbeschriebene
Konstruktionf¨ursolchel¨angenerhalteneMixeistnichtsichergegenaktiveAngreifer.Diese
DissertationstellteineneueKonstruktionf¨urpraktischel¨angenerhalteneMixevor,welcheauf
denf¨urDHAESangegebenenkryptographischenPrimitivenaufbaut.Die¨ublicheDefinition
f¨urSicherheitgegen,,Chosen-ciphertext“-AngriffebeiPublic-Key-Verschl¨usselungkannf¨ur
l¨angenerhaltendeMixenichtangewendetwerden;deshalbwerdenangemesseneSicherheits-
definitionenvorgestellt.Eswirdgezeigt,dassdieMix-KonstruktionbeweisbareSicherheit
bietet.

PraxisI:IeilTBeiderDurchf¨uhrungvonPublic-Key-Kryptographiesind¨ublicherweisePotenzenzuberech-
nen(Exponentiation)oderProduktevonPotenzen(,,Multi-Exponentiation“).DieseDisser-
tationbeschreibtdie,,Sliding-window“-Technikf¨urbeliebigekommutativeHalbgruppenmit
neutralemElementundihreVariantemitvorzeichenbehafteterCodierung(,,windowNAF“),

6

dief¨urGruppenmitschnellerInvertierungverwendetwerdenkann(z.B.Punktegruppen
elliptischerKurvenoderKlassengruppenimagin¨arquadratischerZahlk¨orper).Anschließend
wzu,erden,fractionalneueTecwindohnikwsen“kpr¨annasenf¨urtiert:RecDiehnerVmitbescerallgemeinerunghr¨anktemderSpbeicekannherplatztenFvonVenstermethoorteilsein.den
,,Ingleichterleamitveddenexpbekonenanntentiation“Multi-Expisteineoneneinfachetiations-MethoStrategiefden¨ur(,,simMulti-Expultaneousonenexptiation;onendertiationVer-“)
odezeigt,zurdassscderhnellenneueExpAnsatzonenofttiationbesseremitVorbEffizienzerechnliefert.ung,f¨ur,Windoeinew