New public-key cryptosystems with fast decryption

Takagi, Tsuyoshi (2001)
New public-key cryptosystems with fast decryption.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

URL / URN: urn:nbn:de:tuda-tuprints-1043

Kurzbeschreibung (Abstract)

In this doctoral thesis, we propose three public-key cryptosystems with fast decryption function: the NICE cryptosystem, the PkQ cryptosystem and the Nk cryptosystem. The NICE cryptosystem is constructed over non-maximal quadratic orders. The PkQ cryptosystem is constructed over Z/pkqZ, where p,q are primes and k is a positive integer. The Nk cryptosystem is constructed over Z/nkZ, where n is the RSA-modulus and k is a positive integer. These three public-key cryptosystems are not only of theoretical interest but also practical one. The NICE cryptosystem and the PkQ cryptosystem are suitable for implementation on smartcards. The NICE cryptosystem is constructed over quadratic orders. The NICE cryptosystem has two interesting properties. The first property is that the trapdoor mechanism is different from previously reported public-key cryptosystems such as RSA cryptosystem and elliptic curve cryptosystems. The second property is that the decryption process of the NICE cryptosystem is very fast. It is of quadratic bit complexity in the length of the public key, i.e., polynomial time with a polynomial of degree = 2. The NICE cryptosystem is the only known public-key cryptosystem whose decryption has quadratic polynomial time. Our implementation shows that with regards to the decryption time, it is comparably as fast as the encryption time of the RSA cryptosystem with small encryption exponent e=216+1. The security of our cryptosystem is closely related to factoring the discriminant of a quadratic order. When we choose appropriate sizes of the parameters, the currently known fast algorithms for cryptanalysis such as the number field sieve, the elliptic curve method, or the Hafner-McCurley algorithm are not applicable. The PkQ cryptosystem is constructed over Z/pkqZ, where p,q are primes and k is a positive integer. The prominent property of the PkQ cryptosystem is its decryption time. It is about three times faster than implementations of the RSA cryptosystem that use the Chinese remainder theorem. Indeed, timings for implementations using LiDIA show that the PkQ cryptosystem is about 2.4 times faster than the RSA cryptosystem with the Chinese remainder theorem. The security of the PkQ cryptosystem is closely related to the RSA cryptosystem. We prove that standard attacks against the RSA cryptosystem, for example, the cycling attack and the low decryption exponent attack are not applicable to the PkQ cryptosystem. Moreover, to implement the PkQ cryptosystem we do not have to prepare extra cryptographic libraries; instead, we can use the standard one for the RSA cryptosystem. We can easily implement the PkQ cryptosystem in an environment designed for the RSA cryptosystem. The Nk cryptosystem is constructed over Z/nkZ, where n is the RSA modulus and k is a positive integer. The features of the Nk cryptosystem are as follows: We can encrypt a message which is several time larger than the RSA modulus. We can prove that breaking the second block of the Nk cryptosystems is as hard as breaking the original RSA cryptosystem. The decryption time of the first block is dominant, because after the first block we only calculate several basic operations to decrypt blocks after the first one. Even if a message is several times longer than a public-key n, we can encrypt the message fast without additionally using a symmetry-key cryptsystem.

Typ des Eintrags:

Dissertation

Erschienen:

2001

Autor(en):

Takagi, Tsuyoshi

Art des Eintrags:

Erstveröffentlichung

Titel:

New public-key cryptosystems with fast decryption

Sprache:

Englisch

Referenten:

Sakurai, Prof. Dr. Kouichi

Berater:

Buchmann, Prof. Dr. Johannes

Publikationsjahr:

1 März 2001

Ort:

Darmstadt

Verlag:

Technische Universität

Datum der mündlichen Prüfung:

30 Januar 2001

URL / URN:

urn:nbn:de:tuda-tuprints-1043

Kurzbeschreibung (Abstract):

Alternatives oder übersetztes Abstract:

Alternatives Abstract

Sprache

In dieser Arbeit entwickeln wir drei Public-Key Kryptosysteme mit einer schnellen Entschlüsselungsfunktion: das Kryptosystem NICE, das Kryptosystem PkQ und das Kryptosystem Nk. NICE wird über nicht-maximalen quadratischen Ordnungen konstruiert. PkQ wird über Z/pkqZ konstruiert, wobei p und q Primzahlen und k eine positive ganze Zahl ist. Nk wird über Z/nkZ konstruiert, wobei n ein RSA-Modulus und k eine positive ganze Zahl ist. Diese drei Public-Key Kryptosysteme sind nicht nur von theoretischem, sondern auch von praktischem Interesse. Die Systeme NICE und PkQ sind für die Implementierung auf Smartcards geeignet. Das Kryptosystem NICE arbeitet über quadratischen Ordnungen. Es hat zwei interesssante Eigenschaften. Zum einen ist der Trapdoor-Mechanismus anders als bei bisher vorgeschlagenen Public-Key Kryptosystemen wie z.B. RSA oder Systemen basierend auf elliptischen Kurven. Zum anderen ist der Entschlüsselungsprozeß bei NICE sehr schnell. Die Bitkomplexität ist quadratisch in der Länge des öffentlichen Schlüssels, d.h. polynomiell mit Polynomgrad 2. NICE ist das einzig bekannte Public-Key Kryptosystem mit quadratischer Polynomzeit für die Entschlüsselung. Unsere Implementierung zeigt, dass es im Hinblick auf die Entschlüsselungszeit vergleichbar schnell ist wie RSA mit kleinem Verschlüsselungsexponenten e=216+1. Die Sicherheit unserer Kryptosystems hängt eng mit dem Faktorisieren der Diskriminante einer quadratischen Ordnung zusammen. Falls wir geeignete Größen für die Parameter wählen, dann sind die zur Zeit bekannten, schnellsten Algorithmen wie das Zahlkörpersieb, die elliptische Kurven Methode und der Hafner-McCurley Algorithmus für die Kryptoanalyse nicht anwendbar. Das Kryptosystem PkQ ist über Z/pkqZ konstruiert, wobei p und q Primzahlen und k eine positive ganze Zahl ist. Die wichtigste Eigenschaft von PkQ ist seine Entschlüsselungszeit. Sie ist in etwa dreimal schneller als Implementierungen von RSA, die mit dem Chinesischen Restsatz arbeiten. In der Tat zeigen Zeitmessungen bei Implementierungen mit LiDIA, dass PkQ in etwa 2,4 Mal schneller ist als RSA mit Chinesischem Restsatz. Die Sicherheit von PkQ ist eng verknüpft mit der von RSA. Wir beweisen, dass Standardattacken gegen RSA wie z.B. die "cycling attack" und die Attacke bei kleinem Entschlüsselungsexponenten, nicht für PkQ anwendbar sind. Weiterhin müssen wir zur Implementierung von PkQ keine zusätzlichen kryptographischen Bibliotheken bereitstellen; stattdessen können wir die gleichen verwenden, die auch für RSA benötigt werden. Wir können PkQ leicht in einer für RSA spezifizierten Umgebung einsetzen. Das Kryptosystem Nk ist über Z/nkZ konstruiert, wobei n ein RSA-Modulus und k eine positive ganze Zahl ist. Die Eigenschaften von Nk sind folgende: Wir können eine Nachricht Verschlüsseln, die einige Male größer ist, als der RSA-Modulus. Wir können beweisen, dass das Brechen des zweiten Blockes von Nk genauso schwierig ist, wie das Brechen des RSA Systems. Die Zeit für die Entschlüsselung des ersten Blockes ist dominant, da nach dem ersten Block nur verschiedene Grundfuktionen durchgeführt werden, um die weiteren Blöcke zu entschlüsseln. Selbst wenn die Nachricht einige Male länger als der öffentliche Schlüssel n ist, können wir die Nachricht schnell ohne zusätzliche Verwendung eines symmetrischen Kryptosystems verschlüsseln.

Deutsch

Freie Schlagworte:

Kryptographie, Public-Key Kryptosystem, RSA, Faktorisierung, NICE

Schlagworte: