Benaloh-Kryptosystem

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

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

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

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

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

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)[Bearbeiten]

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

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

Unter der Higher-Residuosity-Annahme kann gezeigt werden, dass das Verfahren semantisch sicher gegen gewählte-Klartext Angriffe 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[Bearbeiten]

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

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

Schlüsselerzeugung[Bearbeiten]

Zunächst wählen wir die Blöckgröße r=9, und wählen p=883 und q=1.019. 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 85.147^{882 \cdot 1108/3} \equiv 70.977\not\equiv 1\mod (883 \cdot 1109) erfüllt.

Damit erhalten wir:

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

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

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

Verschlüsselung[Bearbeiten]

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 = 175.884

Die Verschlüsselung ergibt sich damit zu:

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

Entschlüsselung[Bearbeiten]

Zur Entschlüsselung berechnen wir zuerst:

a = c(p-1)(q-1)/r mod n = 541197882·1108/9 mod 899777 = 487961
b = y(p-1)(q-1)/r mod n =  85147882·1108/9 mod 899777 = 494615

Eine systematische Suche liefert uns nun:

y0 mod n = 4946150 mod 899777 = 1 <> 487961
y1 mod n = 494615 <> 487961
y2 mod n = 678709 <> 487961
y3 mod n =  70977 <> 487961
y4 mod n = 283905 <> 487961
y5 mod n = 631022 <> 487961
y6 mod n = 487961

Die verschlüsselte Nachricht lautete daher m=6.

Referenzen[Bearbeiten]

  1. Josh Benaloh: Dense Probabilistic Encryption (englisch, PS) Abgerufen am 13. Juni 2012.
  2. Laurent Fousse, Pascal Lafourcade, und Mohamed Alnuaimi: Benaloh’s Dense Probabilistic Encryption Revisited (englisch, PDF; 177 kB) Abgerufen am 13. Juni 2012.