On the computation of discrete logarithms in finite prime fields [Elektronische Ressource] / von Damian Weber

Sujets

• Mathematics

Informations

• Publié par: universitat_des_saarlandes
• Publié le: 01 janvier 2007
• Nombre de lectures: 22
• Langue: English

Extrait

On the Computation
of Discrete Logarithms
in Finite Prime Fields
Dissertation
zur Erlangung des Grades
Doktor der Ingenieurwissenschaften (Dr.–Ing.)
der Technischen Fakult¨at
der Universit¨at des Saarlandes
von
Damian Weber
Saarbrucken¨
1997Tag des Kolloquiums: 30.10.1997
Dekan: Prof. Dr.–Ing. Alexander Koch
Gutachter:
Prof. Dr. Johannes Buchmann
Prof. Ph. D. Raimund SeidelI
Acknowledgements
To write a thesis on discrete logarithms has been a very demanding and a highly
fascinating challenge.
First of all, I would like to thank my thesis supervisor, Prof. Dr. Johannes Buch-
mann, who approved of my proposal to consider the practicability of the asympto-
tically fastest discrete logarithm algorithm for finite prime fields, the NFS, and who
gave me the chance to join his research group at the university of Saarbrucken.¨
Many thanks to the members of this research group for their support and assis-
tance; especially to Thomas Denny who has been able to solve bigger and bigger
matrix equations and who shared his experience with the quadratic sieve factoring
algorithm. I am also very grateful to Thomas Papanikolaou for his generosity in
investing plenty of his time in answering questions about integer arithmetic and
C++ internals. Thank you as well to him and Susanne Wetzel for proofreading the
manuscript. Furthermore, I would like to thank Dr. Jo¨rg Zayer for providing many
implementation tricks and details of the NFS factoring algorithm.
Special thanks are due to Dr. Oliver Schirokauer (Oberlin College/Ohio) for his
constructive feedback on algebraic number theory and for giving insight into his
invention of the additive characters. I am also grateful to Marije Elkenbracht–
Huizing (Amsterdam/Netherlands) for stimulating discussions about the NFS for
factoring.
Many thanks to the GNU software project which provides numerous public domain
software toolsincluding the compilers gcc, g++, the awk–extension gawk, the packer
gzip, and the profiler gprof.IIIII
Kurzzusammenfassung
In dieser Arbeit berichten wir u¨ber praktische Erfahrungen mit der Lo¨sung von
Kongruenzen der Form
xa ≡b modp, a,b,p,x∈Z, p Primzahl.
∗Dies ist das Problem der Diskreten Logarithmen in (Z/pZ) . Zahlreiche kryp-
tographische Protokolle wie digitale Unterschriften, Verschlusselung von Nachrich-¨
ten, Schlu¨sselaustausch und Identifikation basieren auf der Schwierigkeit dieses Pro-
blems. IndieserArbeitbefassenwirunsmitderPraktikabilitatverschiedenerIndex–¨
Calculus Verfahren, die zur Zeit die asymptotisch schnellsten Algorithmen liefern,
umdiesesProblemzulosen. Wirprasentieren Berechnungen mitbiszu85–stelligem¨ ¨
p und legen eine partielle Lo¨sung zu McCurley’s Challenge vor, die ein 129–stelliges
p von spezieller Form benutzt.
Abstract
In this thesis we write about practical experience when solving congruences of the
form
xa ≡b modp, a,b,p,x∈ZZ, p prime.
∗This is referred to as the discrete logarithm problem in (Z/pZ) . Many crypto-
graphic protocols such as signature schemes, message encryption, key exchange and
identification depend on the difficulty of this problem. We are concerned with the
practicabilityofdifferentindexcalculusvariants, whicharetheasymtotically fastest
known algorithms at present to solve this problem. We present computations for p
havingupto85decimaldigits. WeincludeapartialsolutiontoMcCurley’schallenge
with a 129–digit p, which has a special form.IVZusammenfassung
Insofern sich die Sa¨tze der Mathe-
matikaufdieWirklichkeitbeziehen,
sindsienichtsicher,undinsofernsie
sicher sind, beziehen sie sich nicht
auf die Wirklichkeit.
Albert Einstein
Diese Dissertation besch¨aftigt sich mit praktischen Erfahrungen bei der Benutzung
verschiedener Index–Calculus Verfahren zur Losung des Problems Diskreter Loga-¨
∗rithmen(DLP)indermultiplikativen Gruppeendlicher Primk¨orper(Z/pZ) ,wobei
p Primzahl ist. Diese Gruppe besteht aus p−1 Elementen. Das Problem Diskreter
Logarithmen kann folgendermaßen formuliert werden. Gegeben seien ganze Zahlen
a, b und eine Primzahl p. Zu finden ist eine ganze Zahl x mit der Eigenschaft
xa ≡b modp,
oder ein Beweis dafur, daß ein solches x nicht existiert. Seit der Veroffentlichung¨ ¨
des Diffie–Hellman’schen Schlu¨sselaustausch–Protokolls im Jahre 1978ist das Inter-
esse am DLP standig gestiegen; dies ist aus der Erfindung vieler kryptographischer¨
Protokolle, deren Sicherheit von der Schwierigkeit des DLPin bestimmten Gruppen
∗abhangt, ersichtlich. Die Gruppe (Z/pZ) gehort zu denjenigen Gruppen, in de-¨ ¨
nen das DLP allgemein als schwierig angenommen wird, vorausgesetzt, daß p groß
ist und in der Primfaktorzerlegung von p− 1 ein großer Primfaktor q enthalten
ist. Es ist daher nicht verwunderlich, daß zahlreiche kryptographische Verfahren
∗die Gruppe (Z/pZ) benutzen; sogar das amerikanische National Institute of Stan-
dards and Technology hat ein digitales Signaturverfahren zum Standard erhoben,
welches diese Gruppe benutzt [49]. Dieses Verfahren basiert auf Vorschla¨gen von
∗ElGamal [21] und Schnorr [67]. Selbstverstandlich kann das DLP in (Z/pZ) auch¨
mit Algorithmen gelo¨st werden, die in beliebigen Gruppen funktionieren. Beispiels-
weise kann das Verfahren von Silver, Pohlig und Hellman [55] benutzt werden, das
entweder mit Hilfe der Methode von Shanks oder der von Pollard implementiertVI
werden kann. Der große Nachteil dieser Methode besteht jedoch in seiner Laufzeit,
die exponentiell vom gro¨ßten Primfaktor der Gruppenordnung p−1 abh¨angt. Den-
noch kann fur kleine Teiler q von p−1 mit diesem Algorithmus immer die partielle¨
L¨osung x modulo q erhalten werden.
Wegen der steigenden kryptographischen Bedeutung [51], wurde sehr intensiv
nach DL-Algorithmen mit subexponentieller Laufzeit geforscht. Daher kennen
∗wir nun einige deterministische und heuristische Verfahren fur (Z/pZ) ; allen¨
¨liegt die Index–Calculus Idee zugrunde, die man in nahezu jeder Ubersicht zum
DLP findet [51, 38, 44, 52, 65]. Da die Grundidee dieser Algorithmen bereits
bei Faktorisierungsalgorithmen in Erscheinung trat, erben die DL–Algorithmen in
naturlicher Weise die dortige Laufzeitnotation. Wir definieren¨
s 1−sL [s,c] :=exp((c+o(1))(logp) (loglogp) ).p
nImJahre1987bewiesPomerance, daßDiskreteLogarithmenineinemKorpervonp¨√
nElementen mit einer erwarteten Laufzeit vonL [1/2, 2] berechnet werden ko¨nnenp
[60]. Der Artikel von Coppersmith, Odlyzko und Schroeppel [13] enthalt drei heuri-¨
stischeVerfahren,diesichdieIndex–CalculusIdeezunutzemachen;sieerreicheneine
vermutete Laufzeit von L [1/2,1]. Im Jahre 1993 wurde ein großerer Durchbruch¨p
durch Gordon erzielt, der das beim Faktorisieren erfolgreiche Number Field Sieve
(NFS) auf das DLP ubertrug und damit eine heuristische erwartete Laufzeit von¨
2
3L [1/3,3 ] erzielte [27].p
Die neueste Effizienzsteigerung des NFS geht auf Schirokauer zuruck, der die ver-¨
mutete erwartete Laufzeit auf
1
3L [1/3,(64/9) ]p
verbesserte [64]. Diese Laufzeit ist identisch mit der schnellsten asymptotischen
Laufzeit, die zum Faktorisieren von zusammengestzten Zahlen gleicher Große beno-¨ ¨
tigt wird.
Dennoch blieb bis zum Jahre 1995 der einzige ernsthafte Versuch einer expliziten
Berechnung der von LaMacchia und Odlyzko im Jahre 1991. Zu diesem Zeitpunkt
zeigten sie die Unzula¨nglichkeit des von der Firma Sun verwendeten Kryptosystems
zur Sicherung ihres verteilten UNIX Dateisystems auf. Hierbei wurde ein DLP mit
einem 58–stelligen p gelost.¨
Die vorliegende Dissertation stellt umfangreiches experimentelles Datenmaterial zur
Verfu¨gung, welches die Praktikabilit¨at der verschiedenen Index–Calculus Versionen
durch die Erweiterung der Methode von [64] aufzeigt. Außerdem wird eine weitere
VersiondesNFSvomFaktorisierenaufdasDLPu¨bertragen. EinVergleichzwischenVII
den Verfahren gibt Aufschluß uber tatsachliche Laufzeiten, die in den Konstanten¨ ¨
des Ausdrucks L [s,c] verborgen sind. Das folgende Beispiel vermittelt einen Ein-p
druck davon, wie schwer es ist, die Exponentiation modulo einer Primzahl zu in-
vertieren. Die Berechnung einer Potenz modulo einer 85–stelligen Primzahl dauert
32 Millisekunden auf einem 40–mips Rechner. Der gleiche Rechner benotigt jedoch¨
ungefa¨hr ein Jahr, um den benutzten Exponent aufzufinden – und dies mit Hilfe des
besten bekannten DL–Algorithmus fu¨r endliche Primk¨orper dieser Gr¨oße.
Kapitel1fu¨hrtindieNotationunddiemathematischenGrundlagenein,diebeno¨tigt
werden, um die verwendeten Algorithmen zu beschreiben; diese werden in Kapitel
2 kurz skizziert.
Kapitel 3 bildet den Hauptteil dieser Arbeit. Es beginnt mit einer detaillierten
Beschreibung der ersten NFS Implementierung fu¨r das DLP, greift deren zahlreiche
VerfeinerungenmitihrenvierVariationenaufunderklart,wiedieParametergewahlt¨ ¨
werden. Zusa¨tzlich wird eine neue Methode eingefu¨hrt, um die beim Faktorisieren
erfolgreiche Large Prime Variante auch beim DLP anwenden zu konnen. Bei der¨
Beschreibung desGleichungssystems amSchluß desVerfahrenswird hervorgeho