La lecture à portée de main
Découvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDécouvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDescription
Sujets
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