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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

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

Schlüsselerzeugung[Bearbeiten | Quelltext 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 1018/3} \equiv 70.977\not\equiv 1\mod (883 \cdot 1019) 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.019).

Verschlüsselung[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

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.

Referenzen[Bearbeiten | Quelltext 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.