TUD Technische Universität Darmstadt
Hessische Landes-und Hochschulbibliothek
HLuHB

EPDA - Elektronische Publikationen Darmstadt


Autor: Möller, Bodo
Titel:Public-Key Cryptography
Dissertation:TU Darmstadt, Fachbereich Informatik, 2003

Die Dokumente in PDF 1.3 (mit Adobe Acrobat Reader 4.0 zu lesen):

pkc-tp.pdf (601903 Byte)

Abstract auf Deutsch:


Teil I: Theorie

Beweisbare Sicherheit ist ein wichtiges Ziel beim Entwurf von Public-Key-Kryptosystemen. Für die meisten Sicherheitseigenschaften muss hierbei praktische Sicherheit gegen Angreifer mit beschränkten Mitteln betrachtet werden: Ein Angriffsszenario beschreibt, wie Gegner mit dem Kryptosystem interagieren dürfen, um es anzugreifen; das System kann dann als sicher bezeichnet werden, wenn Gegner mit einem praktikablen Rechenaufwand nur vernachlässigbare Erfolgsaussichten erzielen können. Da es keine Berechnungsprobleme gibt, die bewiesenermaßen in einem geeigneten Sinne schwer sind, gibt es nur wenig Hoffnung für absolute Sicherheitsbeweise im Sinne solcher praktischer Sicherheit. Statt dessen muss auf reduktionsbasierte Sicherheitsbeweise zurückgegriffen werden: Die praktische Sicherheit eines komplexen kryptographischen Systems wird zu der Sicherheit einfacherer zugrundeliegender kryptographischer Primitive (mit jeweils passenden Sicherheitsbegriffen) in Beziehung gestellt. Der Grundgedanke ist, zu zeigen, dass das komplexe System nur dann unsicher sein kann, wenn eine der Primitiven unsicher ist. Die Sicherheit kann als "konkrete Sicherheit" quantitativ beschrieben werden in Abhängigkeit von den Mitteln, die Gegnern zur Verfügung stehen. Mit dem DHAES-Schema von Abdalla, Bellare und Rogaway kann man aus einem Schlüsselaustauschverfahren (key encapsulation mechanism, KEM), einem Einmal-MAC (message authentication code) und einem Pseudozufallsbitstringgenerator ein Public-Key-Verschlüsselungsverfahren konstruieren. Ein reduktionsbasierter Sicherheitsbeweis zeigt, dass DHAES Sicherheit gegen (adaptive) "Chosen-ciphertext"-Angriffe erzielt, falls die zugrundeliegenden Primitive sicher sind. (Solche Chosen-ciphertext-Angriffe sind das allgemeinste Angriffsszenario für Public-Key-Verschlüsselung.)

Eine spezifische Anwendung für Public-Key-Kryptographie wird betrachtet, Chaums Mix-Ketten-Konzept für nicht verfolgbare E-Mail über kryptographische Remailer: Damit Absender Anonymität erreichen können, ohne einer einzelnen Stelle vertrauen zu müssen, werden Nachrichten rekursiv für mehrere Zwischenstellen verschlüsselt (die "Mixe"), die jeweils die Nachricht weitersenden, nachdem sie eine Ebene der Verschlüsselung entfernt haben. Um bei der Benutzung von variablen Mix-Ketten sowenig Information wie möglich zu verraten, sollten alle an Mixe gesandte Nachrichten die gleiche Länge haben; also sollte die Nachrichtenlänge sich nicht verringern, wenn ein Mix eine ankommende Nachricht umwandelt in die Nachricht, die er an den nächsten Mix in der Kette weiterzuleiten hat. Die von Chaum beschriebene Konstruktion für solche längenerhaltene Mixe ist nicht sicher gegen aktive Angreifer. Diese Dissertation stellt eine neue Konstruktion für praktische längenerhaltene Mixe vor, welche auf den für DHAES angegebenen kryptographischen Primitiven aufbaut. Die übliche Definition für Sicherheit gegen "Chosen-ciphertext"-Angriffe bei Public-Key-Verschlüsselung kann für längenerhaltende Mixe nicht angewendet werden; deshalb werden angemessene Sicherheitsdefinitionen vorgestellt. Es wird gezeigt, dass die Mix-Konstruktion beweisbare Sicherheit bietet.

Teil II: Praxis

Bei der Durchführung von Public-Key-Kryptographie sind üblicherweise Potenzen zu berechnen (Exponentiation) oder Produkte von Potenzen ("Multi-Exponentiation"). Diese Dissertation beschreibt die "Sliding-window"-Technik für beliebige kommutative Halbgruppen mit neutralem Element und ihre Variante mit vorzeichenbehafteter Codierung ("window NAF"), die für Gruppen mit schneller Invertierung verwendet werden kann (z. B. Punktegruppen elliptischer Kurven oder Klassengruppen imaginärquadratischer Zahlkörper). Anschließend werden neue Techniken präsentiert: Die Verallgemeinerung der bekannten Fenstermethoden zu "fractional windows" kann für Rechner mit beschränktem Speicherplatz von Vorteil sein. "Interleaved exponentiation" ist eine einfache Strategie für Multi-Exponentiation; der Vergleich mit den bekannten Multi-Exponentiations-Methoden ("simultaneous exponentiation") zeigt, dass der neue Ansatz oft bessere Effizienz liefert. "Window NAF splitting" ist eine Methode zur schnellen Exponentiation mit Vorberechnung für eine feststehende Basis in Gruppen mit schneller Invertierung. Für den Fall von elliptischen Kurven werden schließlich Seitenkanalangriffe diskutiert, d. h. Angriffe, bei denen Angreifer Messungen des Stromverbrauchs oder ähnliche Beobachtungen benutzen, um Information über geheime Werte zu erhalten. Zwei Verfahren werden vorgestellt, die gezielt dem Bekanntwerden von geheimer Information über Seitenkanäle entgegenwirken: eine 2w-äre Links-nach-rechts-Methode, die auf einer speziellen Darstellung der Skalare beruht, und eine 2w-äre Rechts-nach-links-Methode mit einem besonderen randomisierten Initialisierungsschritt.




Abstract auf Englisch:

Part I: Theory

Provable security is an important goal in the design of public-key cryptosystems. For most security properties, it is computational security that has to be considered: an attack scenario describes how adversaries interact with the cryptosystem, trying to attack it; the system can be called secure if adversaries with reasonably bounded computational means have negligible prospects of success. The lack of computational problems that are guaranteed to be hard in an appropriate sense means that there is little hope for absolute proofs of computational security. Instead, reduction-based security proofs have to be used: the computational security of a complex cryptographic scheme is related to the security of simpler underlying cryptographic primitives (under appropriate notions of security). The idea is to show that if the complex scheme is not secure, then this is because one of the primitives is not secure. Security can be described quantitatively as "concrete security", measured depending on the power given to adversaries.

The DHAES construction (due to Abdalla, Bellare, and Rogaway) allows building a public-key encryption scheme from a key encapsulation mechanism (KEM), a one-time message authentication code (one-time MAC), and a pseudo-random bit string generator. A reduction-based security proof shows that DHAES achieves security against (adaptive) chosen-ciphertext attacks if these underlying primitives are secure. (Such chosen-ciphertext attacks are the most general attack scenario for public-key encryption.)

A specific application for public-key cryptography is considered, namely Chaum's mix chain concept for untraceable electronic mail via cryptographic remailers: to obtain anonymity without requiring trust in a single authority, messages are recursively public-key encrypted to multiple intermediates (mixes), each of which forwards the message after removing one layer of encryption. To conceal as much information as possible when using variable (source routed) chains, all messages passed to mixes should be of the same length; thus, message length should not decrease when a mix transforms an input message into the corresponding output message directed at the next mix in the chain. Chaum described an implementation for such length-preserving mixes, but it is not secure against active attacks. This thesis presents a new construction for practical length-preserving mixes, which uses the cryptographic primitives described for DHAES. The conventional definition of security against chosen ciphertext attacks for public-key encryption schemes is not applicable to length-preserving mixes, so appropriate security definitions are introduced; it is shown that the mix construction achieves provable security.

Part II: Practice

Most instantiations of public-key cryptography involve computing powers (exponentiation) or computing power products ("multi-exponentiation") in some commutative semigroup with neutral element. This thesis describes the sliding window technique for arbitrary commutative semigroups with neutral element and its signed-digit variant ("window NAF") for groups where inversion is fast (e.g. point groups of elliptic curves and class groups of imaginary quadratic number fields), and then presents new techniques. Fractional windows, a generalization of the previously known window methods, can be useful for devices with limited storage. Interleaved exponentiation is a simple strategy for multi-exponentiation; the comparison with previous simultaneous exponentiation methods shows that it often provides better efficiency. Window NAF splitting is a method for fast exponentiation with precomputation for a fixed base in groups where inversion is fast.

For the case of elliptic curves, side-channel attacks are discussed, i.e. attacks where adversaries use power consumption measurements or similar observations to derive information on secret values. Two methods are shown that are designed to limit potential information leakage available to adversaries: a 2w-ary left-to-right method employing special representations of scalars, and a 2w-ary right-to-left method with a special randomized initialization stage.



Dokument aufgenommen :2003-10-08
URL:http://elib.tu-darmstadt.de/diss/000372