Okamoto-Uchiyama-Kryptosystem
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. 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-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 
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 
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) 
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 
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 
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 
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 
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, 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. 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  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 
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 
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 
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 

Asymmetrisches Verschlüsselungsverfahren