Okamoto-Uchiyama-Kryptosystem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Okamoto-Uchiyama-Kryptosystem ist ein semantisch sicherer, asymmetrischer Verschlüsselungsalgorithmus. Es wurde erstmals im Jahr 1998 von Tatsuaki Okamoto und Shigenori Uchiyama an der Eurocrypt, einer der größten jährlich stattfindenden Kryptographiekonferenzen, vorgestellt.[1] Das Verfahren ist additiv-homomorph, was bedeutet, dass durch die Multiplikation zweier Schlüsseltexte die Klartexte addiert werden. Es ist also nicht nötig, die Schlüsseltexte zu entschlüsseln, um auf den Klartexten operieren zu können.

Verfahren[Bearbeiten | Quelltext bearbeiten]

Wie viele asymmetrische Verschlüsselungsverfahren arbeitet das Okamoto-Uchiyama-Kryptosystem in der Gruppe . Allerdings ist der verwendete Modul im Gegensatz zu anderen Verfahren, z. B. RSA, von der Form , wobei große Primzahlen sind. Das Verfahren ist homomorph und leidet daher unter den damit einhergehenden Problemen.

Erzeugung des öffentlichen und privaten Schlüssels[Bearbeiten | Quelltext bearbeiten]

Das Schlüsselpaar wird folgendermaßen generiert:

  • Man generiert zwei Primzahlen gleicher Bitlänge , und setzt . In der Praxis sollte zumindest 1024, besser jedoch 1536 oder 2048 Binärstellen haben.
  • Man wählt zufällig in sodass Ordnung hat.
  • Man definiert

Der öffentliche Schlüssel besteht aus , der private Schlüssel aus .

Verschlüsseln von Nachrichten[Bearbeiten | Quelltext bearbeiten]

Um eine Nachricht mit zu verschlüsseln, verfährt man wie folgt:

  • Zuerst wählt man ein zufälliges .
  • Die verschlüsselte Nachricht ist dann gegeben durch .

Entschlüsseln von Nachrichten (Decodierung)[Bearbeiten | Quelltext bearbeiten]

Zum Entschlüsseln definiert man zuerst die Funktion . Dann erhält man die ursprüngliche Nachricht folgendermaßen:

  • Man definiert .
  • Man setzt .

Im letzten Schritt ist zu beachten, dass die Division modulo durchgeführt werden muss, d. h., durch Multiplikation mit dem multiplikativ Inversen. Die Division in der Berechnung von wird über den ganzen Zahlen ausgeführt.

Korrektheit des Okamoto-Uchiyama Kryptosystems[Bearbeiten | Quelltext bearbeiten]

Für eine ungerade Primzahl definiert man die p-Gruppe von als

.

Das heißt, enthält genau jene Elemente von , welche bei Division durch den Rest 1 liefern.

Man definiert dann die logarithmische Funktion auf den Elementen von als

.

Dieser Wert ist immer ganzzahlig, da für alle gilt, dass .

Es gilt nun: .

Beweis:

Die erste Gleichung gilt wegen . Die letzte Gleichung gilt, da nach der obigen Beobachtung gilt.

Falls nun für ein gilt, dass , und weiters für ein ist, erhält man ferner

.

In dieser Beziehung liegt auch der Grund für den Namen logarithmische Funktion, da der diskrete Logarithmus von in Basis berechnet wird.

Beweis: Dies folgt trivial aus der vorherigen Eigenschaft, weil und gilt.

Daraus folgt nun insgesamt die Korrektheit des Verfahrens, dass also

tatsächlich mit der ursprünglichen Nachricht übereinstimmt.

Beweis: Wir beobachten zuerst, dass

,

wobei für die letzte Gleichung der Satz von Lagrange verwendet wurde. Wir erhalten dann:

.

Wichtig ist hier, dass , und damit auch erfüllt war, da nach Voraussetzung eine Zahl mit k Bit Länge war.

Sicherheit[Bearbeiten | Quelltext bearbeiten]

Unter der p-Untergruppen-Annahme kann gezeigt werden, dass das Verfahren semantisch sicher ist. Das Invertieren der Verschlüsselung ist bewiesenermaßen ebenso komplex wie das Faktorisieren des Moduls .

Homomorphieeigenschaften[Bearbeiten | Quelltext bearbeiten]

Wie bei allen homomorphen Verschlüsselungsverfahren kann ein Angreifer einen Schlüsseltext derart verändern, dass er zu einem mit dem ursprünglichen Klartext verwandten Klartext entschlüsselt wird. Sei zum Beispiel die Verschlüsselung eines unbekannten Wertes . Dann kann durch Multiplikation mit der verschlüsselte Wert sehr einfach um jeden beliebigen Wert verändert werden:

.

Auf ähnlich Weise kann man auch den unbekannten Klartext auch mit einem beliebigen Faktor multiplizieren, indem man den Schlüsseltext exponentiert:

.

Um hier allerdings ein vernünftiges Resultat zu erreichen (z. B., eine Verdoppelung des Klartextes), muss garantiert sein, dass gilt, bzw. sogar , damit der Empfänger aus der Entschlüsselung keine Rückschlüsse auf die Manipulation ziehen kann (alle korrekt verschlüsselten Klartexte dürfen laut Vorschrift ja höchstens Bits lang sein).

Vorteile[Bearbeiten | Quelltext bearbeiten]

Die homomorphen Eigenschaften werden u. a. im Zusammenhang mit den folgenden Anwendungen ausgenützt.

  • E-Voting: Nachdem jeder Wahlberechtigte seine Stimme (im einfachsten Fall eine 1 für ja, eine 0 für nein) verschlüsselt und an die Wahlbehörde übermittelt hat, werden alle Schlüsseltexte multipliziert, und die resultierende Verschlüsselung enthält die Verschlüsselung der Gesamtanzahl an Ja-Stimmen. Durch Entschlüsseln erhält man nun das Wahlergebnis. Wichtig ist, dass die den ersten Schritt ausführende Partei keine Kenntnis des geheimen Schlüssels benötigt, wodurch keine einzelnen Stimmen entschlüsselt werden können.
  • eCash
  • Zero-Knowledge-Beweise im Universal Composability Modell

Nachteile[Bearbeiten | Quelltext bearbeiten]

Aufgrund der angeführten Homomorphieeigenschaften ist das Verfahren allerdings nicht IND-CCA sicher, d. h. nicht sicher unter gewählten Schlüsseltext-Angriffen. Jedes Verschlüsselungssystem, das diese Sicherheit besitzt müsste nämlich auch nicht-verformbar sein, eine Eigenschaft die zur Homomorphie im Widerspruch steht. In der Literatur findet man auch Transformationen, das System in eine IND-CCA sichere Variante zu transformieren.[2][3] Ob diese Transformationen angebracht sind oder nicht, ist von der jeweiligen Anwendung abhängig.

Vollständiges Beispiel[Bearbeiten | Quelltext bearbeiten]

Die oben angeführten Schritte sollen hier an einem kleinen Beispiel veranschaulicht werden.

Schlüsselerzeugung[Bearbeiten | Quelltext bearbeiten]

Zunächst werden zwei geheime Primzahlen gewählt, beispielsweise und . Beide haben in der Binärdarstellung 10 Bits, d. h., es ist . Damit ergibt sich weiters:

Die zufällige, passende Wahl von liefert

  • , wobei und gilt.

Der öffentliche Schlüssel ist damit gegeben durch:

Der geheime Schlüssel lautet .

Vorarbeiten[Bearbeiten | Quelltext bearbeiten]

In einem ersten Schritt muss der zu verschlüsselnde Text in Zahlen kleiner als übersetzt werden. Wir ersetzen dazu einfach jeden Buchstaben durch seine Position im Alphabet:

A=01 B=02 C=03 usw. (00 = Leerzeichen)

Wir verschlüsseln nun jedes Zeichen einzeln, da zwei aufeinanderfolgende Buchstaben u.U. einen zu großen Wert liefern könnten.

Klartext:  O  U  K
Kodierung: 15 21 11

Verschlüsselung[Bearbeiten | Quelltext bearbeiten]

Wir haben drei zu verschlüsselnde Klartexte (, und ), für die wir jeweils ein benötigen.

r1 = 523.423.432
r2 =  43.412.311
r3 = 633.186.663

Die Verschlüsselungen ergeben sich damit zu:

ci = gmihri mod n
c1 = 33270615 344141213523423432 mod 916872763 = 289652071
c2 = 423840839
c3 = 684226192

Entschlüsselung[Bearbeiten | Quelltext bearbeiten]

Wir können die Nachrichten entschlüsseln durch:

mi = L(cip-1 mod p2) / L(gp) mod p

Wichtig ist hier, dass die Division ausgeführt wird. Wir berechnen daher mittels des erweiterten Euklidischen Algorithmus das multiplikative Inverse von modulo , und erhalten damit . Damit ergibt sich die Entschlüsselung zu:

m1 = L(2896520711018 mod 1038361) * 502 mod 1019 = 15
m2 = 21
m3 = 11

Durch Invertierung der Substitutionsvorschrift kann man diese Werte nun wieder in Buchstaben übersetzen.

Quellen[Bearbeiten | Quelltext bearbeiten]

  1. Tatsuako Okamoto und Shigenori Uchiyama: A new public-key cryptosystem as secure as factoring (englisch). In: Eurocrypt 98, Springer Verlag, 1998, S. 308–318. 
  2. Eiichiro Fujisaki und Tatsuako Okamoto: How to Enhance the Security of Public-Key Encryption at Minimum Cost (englisch). In: PKC 99, Springer Verlag, 1999, S. 53–68. 
  3. Pascal Paillier und David Pointcheval: Efficient Public-Key Cryptosystems Provably Secure Against Active Adversaries (englisch). In: ASIACRYPT 99, Springer Verlag, 1999, S. 165–179.