Covers and Logarithmic Signatures of Finite Groups in Cryptography [Elektronische Ressource] / Pavol Svaba. Gutachter: Han Vinck. Betreuer: Trung van Tran

Description

COVERS AND LOGARITHMIC SIGNATURESOF FINITE GROUPS IN CRYPTOGRAPHYVon der Fakult¨at fu¨r Ingenieurwissenschaften,Abteilung Informatik und Angewandte Kognitionswissenschaftder Universit¨at Duisburg-Essenzur Erlangung des akademischen GradesDoktor der Ingenieurwissenschaften (Dr.-Ing.)genehmigte DissertationvonPavol Svabaaus Bratislava, Slowakische Republik1. Gutachter: Prof. Dr. Tran van Trung2. Gutachter: Prof. Dr.-Ing. A.J. Han VinckTag der mu¨ndlichen Pru¨fung: 22. Juni 2011ZusammenfassungNachdem Diffie und Hellman [DH76] die Idee von getrennten Schlu¨sseln fu¨r Verschlu¨sse-lungsverfahren pr¨asentierten, wurde die asymmetrische Kryptographie zunehmend weiterentwickelt. Viele Public Key Kryptosysteme wurden vorgeschlagen, aber nur wenige wur-den letztlich nicht gebrochen. Die meisten von ihnen, die noch heute verwendet werden,basieren auf den bekannten Schwierigkeiten von bestimmten mathematischen Problemenin sehr großen endlichen zyklischen Gruppen.In den sp¨aten 1970ern begann S. Magliveras den Nutzen spezieller Faktorisierungen aufendlichen nicht-abelschen Gruppen, bekannt als logarithmische Signaturen, in der Kryp-tographie zu erforschen [MOS84,Mag86,MM89a,MM89b].

Sujets

• Informatik

Informations

• Publié par: universitat_duisburg-essen
• Publié le: 01 janvier 2011
• Nombre de lectures: 29
• Langue: Deutsch

Extrait

COVERSANDLOGARITHMICSIGNATURES
OFFINITEGROUPSINCRYPTOGRAPHY

VonderFakulta¨tfu¨rIngenieurwissenschaften,
AbteilungInformatikundAngewandteKognitionswissenschaft
derUniversita¨tDuisburg-Essen
zurErlangungdesakademischenGrades

DoktorderIngenieurwissenschaften(Dr.-Ing.)

genehmigteDissertation

nov

PavolSvaba
ausBratislava,SlowakischeRepublik

1.Gutachter:Prof.Dr.TranvanTrung
2.Gutachter:Prof.Dr.-Ing.A.J.HanVinck
Tagderm¨undlichenPru¨fung:22.Juni2011

Zusammenfassung

NachdemDieundHellman[DH76]dieIdeevongetrenntenSchlu¨sselnfu¨rVerschlu¨sse-
lungsverfahrenpra¨sentierten,wurdedieasymmetrischeKryptographiezunehmendweiter
entwickelt.VielePublicKeyKryptosystemewurdenvorgeschlagen,abernurwenigewur-
denletztlichnichtgebrochen.Diemeistenvonihnen,dienochheuteverwendetwerden,
basierenaufdenbekanntenSchwierigkeitenvonbestimmtenmathematischenProblemen
insehrgroßenendlichenzyklischenGruppen.
Indenspa¨ten1970ernbegannS.MagliverasdenNutzenspeziellerFaktorisierungenauf
endlichennicht-abelschenGruppen,bekanntalslogarithmischeSignaturen,inderKryp-
tographiezuerforschen[MOS84,Mag86,MM89a,MM89b].Spa¨terfolgtenweitereweg-
weisendeArbeitenvonMagliveras,StinsonundTranvanTrung[MST02],diesowohl
dasKryptosystemMST1,welchesauflogarithmischenSignaturenbasiert,alsauchMST2,
dasaufeineranderenArtvonGruppen-U¨berdeckungen–densogenannten[s,r]-Gittern
–arbeitet,bekanntmachten.BishersindallerdingsnochkeinepraktischeRealisierun-
genvonMST1oderMST2bekannt.Ku¨rzlichwurdeeinneuesPublicKeyKryptosystem
namensMST3[LMTW09]entwickelt,dasaufderGrundlagevonlogarithmischenSigna-
turenundzufa¨lligenU¨berdeckungenvonendlichennicht-abelschenGruppenarbeitet.Fu¨r
einemo¨glicheRealisierungdergenerischenVersiondiesesSystemswurdendieSuzuki-2-
Gruppenvorgeschlagen.
DasHauptzieldieserArbeitliegtdarinzuzeigen,dassMST3aufSuzuki-2-Gruppenreal-
isiertwerdenkann.DieseFrageko¨nnenwirimpositivenSinnebeantworten.Esgabeinige
A¨nderungeninderUmsetzungderRealisierungdesSystems.DasersteProblembesteht
darin,ezientzufa¨lligeU¨berdeckungenfu¨rgroßeGruppenmitgutenkryptographischen
Eigenschaftenzuerzeugen.IndemwirdenBezugzumklassischenBelegungsproblem(“the
occupancyproblem”)herstellen,ko¨nnenwireineSchrankefu¨rdieWahrscheinlichkeit,dass
einezufa¨lligeAnsammlungvonGruppenelementeneineU¨berdeckungbilden,bestimmen.
EineKonsequenzdarausist,dasswirdasProblem,zufa¨lligeU¨berdeckungenfu¨rbeliebige
großeGruppenzuerzeugen,l¨osenko¨nnen.WeiterhinstellenwireinigeResultatespezieller
Computerexperimentebezu¨glichU¨berdeckungenundgleichma¨ßigenU¨berdeckungenzuver-
schiedenenGruppenvor.

iii

DankihrereinfachenStrukturerlaubenunsdieSuzuki-2-GruppendieSicherheitdesSys-
temsgenauzustudierenundesezientzuimplementieren.IndererstenRealisierungwird
einespezielleKlassevonkanonischlogarithmischenSignaturenzuelementar-abelschen2-
GruppenalsBasisfu¨rdieSchlu¨sselgenerierungverwendet.Diesesindleichtzukonstruieren
underlaubeneinesehrezienteFaktorisierung.WirbetrachteneinenAngri,derzeigt,
dasskanonischeSignaturennichtbenutztwerdenko¨nnenumeinesichereUmsetzungvon
MST3mitSuzuki-2-Gruppenzurealisieren.MotiviertdurchdieAttackeaufdieerste
RealisierungkonntenwireineneueVariantemitsignikantenVerbesserungenvorstellen,
welchedieSicherheitdesSystemsdeutlichsta¨rken.ZudiesemZweckverwendetenwir
fu¨rdasSetupdesSystemseineFunktionzurMaskierungdesprivatenSchlu¨ssels.Ferner
fu¨hrtenwireineKlassevonfusioniertentransversalenlogarithmischenSignaturenfu¨rdie
RealisierungdesVerfahrensein.DieseerlaubeneineezienteFaktorisierungmitHilfe
einer“Trapdoor”Information.WirstelleneinegenaueStudiederSicherheitdesSystems
vor,indemwirheuristischeundalgebraischeMethodenverwenden.Zuna¨chstbestimmen
wirdieuntereSchrankederKomplexita¨tbezu¨glichderGruppengro¨ßevonmo¨glichvorstell-
barendirektenAttacken,umdenprivatenSchlu¨sselzuerhalten.DieseSchrankengeben
einenHinweisaufdieSta¨rkedesSystems.Weiterhinentwickelnwireinema¨chtigeMethode
fu¨reineChosen-Plaintext-Attacke,undzeigen,dassnicht-fusioniertetransversalelogarith-
mischeSignaturennichtverwendetwerdenko¨nnen.Zudemzeigenwir,dassdievorgeschla-
geneKlassenvonfusioniertentransversalenSignaturendieserAttackewiderstehen,und
nachunseremWissen,siedamiteinesichereRealisierungdesSystemsermo¨glichen.Wir
beschreibenunddiskutierendieImplementierungdesSystemsimDetailundziehendabei
Datenu¨berdieEzienz,diewiralsResultatevoneinemExperimenterhielten,mitein.
AbgesehenvondemzentralenForschungsobjektwerdenwirnocheinenneuenAnsatzfu¨rdie
Konstruktionpseudo-zufa¨lligerZahlengeneratoren(PRNG)vorstellen,welcheraufzufa¨lli-
genU¨berdeckungenvonendlichenGruppenbasiert.PRNGsbasierendaufzufa¨lligenU¨ber-
deckungen,auchMSTggenannt,zeigtensichbisherzueinerbestimmtenKlassevonGrup-
penalsho¨chstezientundproduziertenqualitativhochwertigezufa¨lligeBit-Sequenzen.
EinesehrkomplexeFolgevonaufwendigenZufa¨lligkeits-TestszeigtedurchNutzungder
NIST“StatisticalTestSuite”und“DiehardBatteryofTest”diestarkenEigenschaftender
neuenMethodik.Nochwichtigeristallerdings,dasswirBeweiseerbringenko¨nnen,dass
dieseKlassevonGeneratorenada¨quatfu¨rkryptographischeAnwendungensind.Schließlich
fu¨genwirnochDaten¨uberdieEzienzderGeneratorenanundschlageneineMethode
zurpraktischenAnwendungvor.

Acknowledgments

Iwouldliketothankmymotherforherinnitelove.Idedicatethisthesistoher.

MydeepestthankstomyadviserProfessorTranvanTrungforhiskindguidance,andall
thehelpandsupport.Ithasbeenarealhonourandpleasuretoworkwithandlearnfrom
suchanexceptionalperson.Icouldnothavewishedforabettermentor.

ThankstoProfessorHanvanVinckforhiskindnessandconsistentsupportthroughallthe
years.

ThankstoProfessorSpyrosMagliverasforhisfriendshipandhelp,aswellasforhiswork
whichhasbeengreatlyinspiring.

ThankstoProfessorOtokarGrosekforopeningmyeyestotheworldofcryptography.

ThankstotheInstituteofExperimentalMathematicsofUniversityDuisburg-Essen,and
theFacultyofElectricalEngineeringandInformationTechnologyoftheSlovakUniversity
ofTechnology.

v

Contents

ListofFiguresxi
ListofTablesxii
ListofAlgorithmsxiii
ListofSymbolsxiv
1Introduction1
1.1Public-keyCryptography............................1
1.2GroupFactorizationsinCryptography.....................2
1.3Objectives.....................................3
1.4Contributions...................................3
1.5Organization...................................4
2Preliminaries6
2.1LogarithmicSignaturesandCovers.......................6
2.2CoverMappings.................................10
2.3Transformationsofcovers............................12
2.3.1Two-sidedtransform...........................12
2.3.2Blockshue...............................13
2.3.3Elementshue..............................13
2.3.4Fusionofblocks.............................14
2.4TransversalLogarithmicSignatures.......................15
2.5CryptosystemsBasedonLogarithmicSignaturesand
Covers.......................................20
2.5.1PGM...................................20
2.5.2MST...................................22
12.5.3MST2...................................23
2.5.4MST...................................24
3

iiv

iiiv

2.6Suzuki2-groups..................................24
2.7Summary.....................................26
3GenerationofRandomCoversforFiniteGroups27
3.1UniformRandomCover.............................27
3.2NewBoundforRandomCover.........................28
3.3Experimentalresultsforgeneratingrandomcovers..............29
3.4Randomgeneratingcovers............................30
3.5Comparisonofcoversfromarandomalgorithmandagreedyalgorithm..31
3.6Numberofrepresentations............................33
3.7Conclusions....................................34
4FirstRealizationofMSTonSuzuki2-Groups35
34.1GenericVersionofMST3.............................35
4.2LogarithmicSignaturesforElementaryAbelian2-Groups..........37
4.3FirstRealizationonSuzuki2-groups......................40
4.4SecurityAnalysisoftheFirstRealization...................41
4.4.1Usednotation...............................41
4.4.2Attackonaprivatekey.........................42
4.4.3AttackonMST3whenusingcanonicalsignature...........44
4.4.4NormalizedMST............................46
34.5Conclusions....................................49
5SecondRealizationofMST3onSuzuki2-Groups50
5.1Set-up.......................................50
5.2Generationoflogarithmicsignatureanditsfactorization..........52
5.2.1Transformationsoflogarithmicsignatures...............53
5.2.2Algorithmforgenerationof......................53
5.2.3Factorizationwith...........................55
5.3Attackonprivatekey..............................58
5.3.1LogarithmicsignaturesforZandtheirtwosidedtransformations..58
5.3.2Buildinganequation...........................59
5.3.3Analysisoftheequation.........................61
AttackonbJ...............................61
Attackona...............................62
JMoreonAttackonaJ..........................65
CombinedAttackonbJandaJ.....................67
5.4Attackonciphertexts...........