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]

Wie viele asymmetrische Verschlüsselungsverfahren arbeitet das Okamoto-Uchiyama-Kryptosystem in der Gruppe (\mathbb{Z}/n\mathbb{Z})^*. Allerdings ist der verwendete Modul n im Gegensatz zu anderen Verfahren, z. B. RSA, von der Form n=p^2 q, wobei p,q große Primzahlen sind. Das Verfahren ist homomorph und leidet daher unter den damit einhergehenden Problemen.

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

Das Schlüsselpaar wird folgendermaßen generiert:

  • Man generiert zwei Primzahlen p,q gleicher Bitlänge k, und setzt n=p^2 q. In der Praxis sollte n zumindest 1024, besser jedoch 1536 oder 2048 Binärstellen haben.
  • Man wählt g zufällig in (\mathbb{Z}/n\mathbb{Z})^* sodass g_p = g^{p-1}\mod p^2 Ordnung p hat.
  • Man definiert h = g^n \mod n

Der öffentliche Schlüssel besteht aus (n,g,h,k), der private Schlüssel aus (p,q).

Verschlüsseln von Nachrichten[Bearbeiten]

Um eine Nachricht m mit 0<m<2^{k-1} zu verschlüsseln, verfährt man wie folgt:

  • Zuerst wählt man ein zufälliges r \in \mathbb{Z}/n\mathbb{Z}.
  • Die verschlüsselte Nachricht ist dann gegeben durch c = g^m h^r \mod n.

Entschlüsseln von Nachrichten (Decodierung)[Bearbeiten]

Zum Entschlüsseln definiert man zuerst die Funktion L(x) = \frac{x-1}{p}. Dann erhält man die ursprüngliche Nachricht folgendermaßen:

  • Man definiert c_p = c^{p-1}\mod p^2.
  • Man setzt m = \frac{L\left(c_p\right)}{L\left(g_p\right)} \mod p.

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

Korrektheit des Okamoto-Uchiyama Kryptosystems[Bearbeiten]

Für eine ungerade Primzahl p definiert man die p-Gruppe von (\mathbb{Z}/p^2\mathbb{Z})^* als

\Gamma = \left\{x\in (\mathbb{Z}/p^2\mathbb{Z})^* : x\equiv 1\mod p\right\}.

Das heißt, \Gamma enthält genau jene Elemente von (\mathbb{Z}/p^2\mathbb{Z})^*, welche bei Division durch p den Rest 1 liefern.

Man definiert dann die logarithmische Funktion L auf den Elementen von \Gamma als

L(x) = \frac{x-1}{p}.

Dieser Wert ist immer ganzzahlig, da für alle x\in\Gamma gilt, dass x-1\equiv 0\mod p.

Es gilt nun: L(xy \mod p^2) = L(x)+L(y) \mod p.

Beweis:


  \begin{align}
 L(xy \mod p^2) & = \frac{xy-1}{p}\mod p \\
 & = \frac{(x-1)(y-1)+(x-1)+(y-1)}{p}\mod p\\
 & = \frac{x-1}{p}(y-1)+\frac{x-1}{p}+\frac{y-1}{p}\mod p\\
 & = L(x)(y-1)+L(x)+L(y)\mod p\\
 & = L(x) + L(y)\mod p
  \end{align}

Die erste Gleichung gilt wegen L(xy)=\frac{xy-1 \mod p^2}{p} = \frac{xy-1}{p}\mod p. Die letzte Gleichung gilt, da nach der obigen Beobachtung y-1 = 0\mod p gilt.

Falls nun für ein x gilt, dass L(x)\ne 0\mod p, und weiters y=x^m \mod p^2 für ein m\in(\mathbb{Z}/p\mathbb{Z})^* ist, erhält man ferner

m = \frac{L(y)}{L(x)}\mod p.

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

Beweis: Dies folgt trivial aus der vorherigen Eigenschaft, weil L(y) = L(x^m\mod p^2) = L(x)+\dots+L(x) = mL(x)\mod p und 0\leq m<p gilt.

Daraus folgt nun insgesamt die Korrektheit des Verfahrens, dass also

m' = \frac{L\left(c_p\right)}{L\left(g_p\right)} \mod p

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

Beweis: Wir beobachten zuerst, dass

(g^mh^r)^{p-1} = (g^m g^{nr})^{p-1} = (g^{p-1})^m g^{p(p-1)rq} = (g^{p-1})^m \mod p^2,

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

m' = \frac{L\left(c_p\right)}{L\left(g_p\right)} = \frac{L\left(c^{p-1}\right)}{L\left(g^{p-1}\right)} = \frac{L\left((g^m h^r)^{p-1}\right)}{L\left(g^{p-1}\right)} = \frac{L\left((g^{p-1})^m\right)}{L\left(g^{p-1}\right)} = m\mod p.

Wichtig ist hier, dass 0<m<2^{k-1}, und damit auch m<p erfüllt war, da p nach Voraussetzung eine Zahl mit k Bit Länge war.

Sicherheit[Bearbeiten]

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

Homomorphieeigenschaften[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 c die Verschlüsselung eines unbekannten Wertes m. Dann kann durch Multiplikation mit g^{\Delta m} der verschlüsselte Wert sehr einfach um jeden beliebigen Wert \Delta m verändert werden:

c' = c g^{\Delta m}\mod n = g^m h^r g^{\Delta m}\mod n = g^{m+\Delta m}h^r \mod n.

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

c' = c^f \mod n = g^{fm} h^{fr}\mod n = g^{fm} h^{r'}\mod n.

Um hier allerdings ein vernünftiges Resultat zu erreichen (z. B., eine Verdoppelung des Klartextes), muss garantiert sein, dass f\cdot m < p gilt, bzw. sogar f\cdot m<2^{k-1}, 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 k-1 Bits lang sein).

Vorteile[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]

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]

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

Schlüsselerzeugung[Bearbeiten]

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

  • n = p^2 \cdot q = 916.872.763

Die zufällige, passende Wahl von g liefert

  • g = 332.706
  • g_p = g^{p-1}\mod p^2 = 899.778, wobei g_p^p = 1\mod n und g^p\ne 1\mod p^2 gilt.
  • h = g^n \mod n = 344.141.213

Der öffentliche Schlüssel ist damit gegeben durch: (n,g,h,k) = (916.872.763, 332.706, 344.141.213, 10).

Der geheime Schlüssel lautet (p,q) = (1.019, 883).

Vorarbeiten[Bearbeiten]

In einem ersten Schritt muss der zu verschlüsselnde Text in Zahlen kleiner als 2^{k-1}=2^{9}=512 ü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]

Wir haben drei Klartexte zu verschlüsselnde Klartexte (m_1=15, m_2=21 und m_3=11), für die wir jeweils ein r_i benötigen.

r1 = 523.423.432
r2 =  43.412.311
r3 = 633.186.663

Die Verschlüsselungen c_i ergeben sich damit zu:

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

Entschlüsselung[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 \mod p ausgeführt wird. Wir berechnen daher mittels des erweiterten Euklidischen Algorithmus das multiplikative Inverse von L(g_p) modulo p, und erhalten damit L(g_p)^{-1} = 502 \mod p. 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]

  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.