Refine
Document Type
- diplomthesis (1)
- Doctoral Thesis (1)
Language
- German (2) (remove)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
Institute
- Mathematik (2)
In der vorliegenden Diplomarbeit beschäftigen wir uns mit kryptographisch sicheren Pseudozufallsgeneratoren. Diese e±zienten Algorithmen erzeugen zu zufälliger Eingabe deterministisch eine längere Bitfolge, die praktisch von einer Folge zufälliger Münzwürfe nicht unterscheidbar ist. Wir geben die Definitionen von A. Yao sowie M. Blum und S. Micali, beweisen die Äquivalenz und charakterisieren den Unterschied zur klassischen Sichtweise von Zufallsgeneratoren. Mit der Blum-Micali-Konstruktion zeigen wir, wie man aus einer Oneway-Permutation und zugehörigem Hardcore-Prädikat einen kryptographisch sicheren Pseudozufallsgenerator konstruiert: Man wendet auf einen zufälligen Startwert iterativ die Oneway-Funktion an und gibt jeweils das Hardcore-Prädikat des Urbilds aus. Wir stellen das allgemeine Hardcore- Prädikat inneres Produkt modulo 2 von L.A. Levin und O. Goldreich vor und beweisen mit Hilfe des XOR-Lemmas von U.V. Vazirani und V.V. Vazirani die Verallgemeinerung zu einer Hardcore-Funktion, die statt eines Prädikats mehrere Bits ausgibt. Man geht davon aus, daß die Verschlüsselungsfunktionen des RSA- und des Rabin-Public- Key-Kryptosystems Oneway-Permutationen sind. Basierend auf dem Rabin-System haben L. Blum, M. Blum und M. Shub den x2-mod-N-Generator aufgebaut, W. Alexi, B. Chor, O. Goldreich und C.P. Schnorr haben den RSA-Generator konstruiert und den Sicherheitsbeweis zum x2-mod-N-Generator verbessert. Diese Generatoren basieren auf der Blum-Micali-Konstruktion mit dem Hardcore-Prädikat des untersten Bits. Durch neue Ideen können wir die beweisbare Sicherheit der Generatoren deutlich erhöhen, so daß in der Praxis kleinere Schlüssellängen genügen. Bisher war zum Beispiel für den x2-mod-N-Generator bekannt, daß man mit einem Algorithmus A, der das unterste Bit der Wurzel modulo einer n-Bit- Blumzahl mit Wahrscheinlichkeit 1 2 + ² in Zeit |A| = ¡n3¢ berechnet, den Modul in Zeit O¡n3² 9|A|¢ mit Wahrscheinlichkeit ²2 64 faktorisieren kann. Wir verbessern die Laufzeit zu O¡n² 4 log2(n² 1)|A|¢ und Wahrscheinlichkeit 1 9 . Diese neuen Resultate wurden auf der Eurocrypt-Konferenz im Mai 1997 in Konstanz vorgestellt, D.E. Knuth hat sie bereits in die neue Auflage seines Standardwerks The Art of Computer Programming aufgenommen.
Okamoto (Crypto 1992) hat die RSA-Repräsentation als Basis eines gegen aktive Angreifer sicheren Identifikationsschemas eingeführt. Eine RSA- Repräsentation von X E Z * N ist ein Paar (x; r) E Z e x Z * N mit X = g x r e (mod N) für vorgegebenes g E ZN , RSA-Modul N und primen RSA- Exponenten e. Das zugehörige Repräsentationsproblem, also das Auffinden eines Wertes X samt zweier verschiedener Darstellungen, ist äquivalent zum RSA-Problem, der Berechnung einer e-ten Wurzel von g modulo N . Von Brassard, Chaum und Crépeau (Journal Computing System Science, 1988) sowie Damgard (Journal of Cryptology, 1995) stammt eine analoge Konstruktion der Form X = g x r 2 t (mod N) mit x E Z 2 t für den Spezialfall der Blum-Zahlen als Modul N und gegebenes t größer gleich 1, wo die Möglichkeit, zwei verschiedene Repräsentationen zu berechnen, gleichbedeutend zur Zerlegung des Moduls in die Primfaktoren ist. Im ersten Abschnitt der vorliegenden Arbeit verallgemeinern wir dieses Konzept systematisch auf beliebige (RSA-)Module durch die Einführung eines Anpassungsparameters r:= r (N ), so dass X = g x r 2 r t (mod N) mit x E Z 2 t. Basierend auf dieser als Faktorisierungsrepräsentation bezeichneten Darstellung leiten wir Identifikations-, Signatur- und Blinde-Unterschriften-Verfahren her. Im zweiten Teil verwenden wir sowohl RSA- als auch Faktorisierungsrepräsentation als Grundlage sogenannter non-malleable Commitment-Schemata zur Hinterlegung (Verbriefung) einer geheimen Nachricht. Bei dem von Dolev, Dwork und Naor (SIAM Journal on Computing, 2000) eingeführten Begriff der Non-Malleability soll ein Angreifer außer Stande sein, die Hinterlegung einer Nachricht m so abzuändern, dass er diese später dann mit einem in Relation zu m stehenden Wert, man denke zum Beispiel an m 1, aufdecken kann. Von Dolev, Dwork und Naor stammt ein allgemeiner Ansatz zur Konstruktion von non-malleable Commitment-Schemata aufbauend auf einem sogenannten Knowledge-Extraktor. Für die RSA-Darstellung verfügt das von Okamoto entworfene Protokoll als Proof-Of-Knowledge über einen solchen Extraktor, bei dem im Fall der Faktorisierungsrepräsentation von uns entwickelten Verfahren fehlt allerdings der Extraktor. Aus diesem Grund stellen wir mit Hilfe des Chinesischen Restsatzes ein neues, auf Commitments zugeschnittenes Protokoll mit Knowledge-Extraktor vor, das in Verbindung mit der Faktorisierungsrepräsentation ein effizientes Hinterlegungsschema ergibt. Zum Abschluß wird bei einem Commitment- Verfahren mit abgeschwächter Non-Malleability-Eigenschaft von Di Crescenzo, Katz, Ostrovsky und Smith (Eurocrypt 2001) die RSA- durch die Faktorisierungsrepräsentation ersetzt und das Schema vereinfacht.