Benaloh-Kryptosystem

Das Benaloh-Kryptosystem wurde 1994 von Josh Benaloh vorgestellt. Es handelt sich dabei um ein asymmetrisches Kryptosystem. Das Verfahren ist homomorph, d. h., zwei verschlüsselte Nachrichten können addiert werden, ohne die Nachrichten vorher zu entschlüsseln.

Das Verfahren ist eine Erweiterung des Goldwasser-Micali-Kryptosystems: während letzteres lediglich das Verschlüsseln von einzelnen Bits ermöglicht, erlaubt das Benaloh-Kryptosystem das Verschlüsseln von größeren Blocks. Ein kleiner Fehler in der Beschreibung wurde später von Laurent Fousse et al. korrigiert.

Verfahren

Im Folgenden beschreiben wir die Schlüsselerzeugung, und die Algorithmen zur Ver- und Entschlüsselung von Nachrichten.

Erzeugung des öffentlichen und privaten Schlüssels

Das Schlüsselpaar wird folgendermaßen generiert:

• Zuerst wählt man eine Blockgröße $r$.
• Dann generiert man zwei zufällige Primzahlen $p,q$, sodass $r|(p-1)$, $\operatorname {ggT} ((p-1)/r,r)=1$ sowie $\operatorname {ggT} (q-1,r)=1$ gilt, und definiert $n=pq$. In der Praxis sollte n zumindest 1024, besser jedoch 1536 oder 2048 Binärstellen haben.
• Man wählt $y$ zufällig in $(\mathbb {Z} /n\mathbb {Z} )^{*}$, sodass für alle Primteiler $s$ von $r$ gilt: $y^{(p-1)(q-1)/s}\not \equiv 1\mod n$ gilt.

Der öffentliche Schlüssel besteht aus $(r,n,y)$, der private Schlüssel aus $(p,q)$.

Verschlüsseln von Nachrichten

Um eine Nachricht $m\in (\mathbb {Z} /r\mathbb {Z} )$ zu verschlüsseln, verfährt man wie folgt:

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

Entschlüsseln von Nachrichten (Decodierung)

Zum Entschlüsseln eines Schlüsseltextes $c\in (\mathbb {Z} /n\mathbb {Z} )^{*}$ verfährt man dann wie folgt:

• Man setzt $a=c^{(p-1)(q-1)/r}\mod n$ und $b=y^{(p-1)(q-1)/r}\mod n$ und sucht dann ein $m$ sodass $a=b^{m}\mod n$ gilt. Ist $r$ klein, so kann dies durch Durchprobieren aller möglichen Werte geschehen; ist $r$ dagegen groß, hat aber nur kleine Primteiler, kann der Index-Calculus-Algorithmus verwendet werden.

Dass die Entschlüsselung tatsächlich wieder die geheime Nachricht liefert, kann etwa folgendermaßen gesehen werden. Es gilt

$a=c^{(p-1)(q-1)/r}=(y^{m}u^{r})^{(p-1)(q-1)/r}\equiv y^{m(p-1)(q-1)/r}u^{(p-1)(q-1)}\equiv y^{m(p-1)(q-1)/r}=b^{m}\mod n$

Sicherheit

Unter der Higher-Residuosity-Annahme kann gezeigt werden, dass das Verfahren semantisch sicher gegen Angriffe mit ausgewählten Klartexten ist. Diese Annahme besagt, dass für einen zusammengesetzten Modul $n$ nicht effizient geprüft werden kann, ob ein Element in $(\mathbb {Z} /n\mathbb {Z} )$ eine $r$-te Wurzel modulo $n$ besitzt oder nicht, falls $r$ und $n$ wie oben beschrieben gewählt wurden.

Homomorphieeigenschaften

Das Benaloh-Kryptosystem ist additiv-homomorph. Das bedeutet, dass durch Multiplikation zweier Schlüsseltexte die darin enthaltenen Klartexte addiert werden, bzw. durch Exponentiation eines Schlüsseltextes mit $v$ der enthaltene Wert mit $v$ multipliziert wird. Außerdem kann die enthaltene Nachricht durch Multiplikation des Schlüsseltexts mit $y^{w}$ um $w$ vergrößert werden. Allerdings gibt es keine bekannte Möglichkeit, um durch Operationen auf zwei Schlüsseltexten die enthaltenen Nachrichten miteinander zu multiplizieren.

Vollständiges Beispiel

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

Schlüsselerzeugung

Zunächst wählen wir die Blöckgröße $r=9$, und wählen $p=883$ und $q=1019$. Damit gilt

$\operatorname {ggT} ((p-1)/r,r)=\operatorname {ggT} (882/9,9)=\operatorname {ggT} (98,9)=1$

sowie

$\operatorname {ggT} (q-1,r)=\operatorname {ggT} (1018,9)=1$.

Weiters wählen wir $y=85.147$, welches $85147^{882\cdot 1018/3}\equiv 70977\not \equiv 1\mod (883\cdot 1019)$ erfüllt.

Damit erhalten wir:

r = 9
n = p·q = 899777
y = 85147

Der öffentliche Schlüssel ist damit gegeben durch: $(r,n,y)=(9,899777,85147).$

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

Verschlüsselung

Angenommen, man möchte die Nachricht $m=6$ verschlüsseln. Dazu wählen wir ein zufälliges $u\in (\mathbb {Z} /n\mathbb {Z} )^{*}$ :

u = 175884

Die Verschlüsselung ergibt sich damit zu:

c = ymur mod n = 851476 1758849 mod 899777 = 541197

Entschlüsselung

Zur Entschlüsselung berechnen wir zuerst:

a = c(p-1)(q-1)/r mod n = 541197882·1018/9 mod 899777 = 4077
b = y(p-1)(q-1)/r mod n =  85147882·1018/9 mod 899777 = 887550

Eine systematische Suche liefert uns nun:

y0 mod n = 8875500 mod 899777 = 1 <> 4077
y1 mod n = 887550 <> 4077
y2 mod n = 136547 <> 4077
y3 mod n = 425943 <> 4077
y4 mod n = 803992 <> 4077
y5 mod n = 553318 <> 4077
y6 mod n = 4077

Die verschlüsselte Nachricht lautete daher $m=6$.