Okamoto–Uchiyama-Kryptosystem

Das Okamoto-Uchiyama Verschlüsselungssystem 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

Wie viele asymmetrische Verschlüsselungsverfahren arbeitet das Okamoto-Uchiyama Verschlüsselungsverfahren 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²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

Das Schlüsselpaar wird folgendermaßen generiert:

• Man generiert zwei Primzahlen p,q gleicher Bitlänge k, und setzt n = p²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

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)

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, dh., 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

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, Γ 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 Γ 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 ist nun unschwer zu sehen, dass

$L(xy \mod p^2) = L(x)L(y) \mod p$

gilt, weil

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

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

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^Δm der verschlüsselte Wert sehr einfach um jeden beliebigen Wert Δ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

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

Aufgrund der angeführten Homomorphieeigenschaften ist das Verfahren allerdings nicht IND-CCA sicher, dh. nicht sicher unter gewählten Schlüsseltext-Angriffen. Jedes Verschü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

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

Schlüsselerzeugung

Zunächst werden zwei geheime Primzahlen gewählt, beispielsweise p = 1.019 und q = 883. Beide haben in der Binärdarstellung 10 Bits, dh., 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

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

Wir haben drei Klartexte zu verschlüsselnde Klartexte (m₁ = 15, m₂ = 21 und m₃ = 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

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

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.