imported>Aka: /* Schlüsselerzeugung */ Tippfehler entfernt

2025-09-19T09:42:59Z

Neue Seite

Das '''Benaloh-Kryptosystem''' wurde 1994 von [[Josh Benaloh]] vorgestellt. Es handelt sich dabei um ein [[asymmetrisches Kryptosystem]]. Das Verfahren ist [[Gruppenhomomorphismus|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-Kryptosystem]]s: 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üssel (Kryptologie)|Schlüsselerzeugung]], und die Algorithmen zur Ver- und Entschlüsselung von Nachrichten.<ref>{{Internetquelle |autor=Josh Benaloh |url=http://research.microsoft.com/en-us/um/people/benaloh/papers/dpe.ps |titel=Dense Probabilistic Encryption |abruf=2012-06-13 |format=PS |sprache=en}}</ref><ref>{{Literatur |Autor=Laurent Fousse, Pascal Lafourcade, und Mohamed Alnuaimi |Titel=Benaloh’s Dense Probabilistic Encryption Revisited |Datum=2010-08-18 |Sprache=en |arXiv=1008.2991}}</ref>

=== Erzeugung des öffentlichen und privaten Schlüssels ===
Das Schlüsselpaar wird folgendermaßen generiert:
* Zuerst wählt man eine Blockgröße <math>r</math>.
* Dann generiert man zwei zufällige [[Primzahl]]en <math>p,q</math>, sodass <math>r|(p-1)</math>, <math>\operatorname{ggT}((p-1)/r, r)=1</math> sowie <math>\operatorname{ggT}(q-1, r)=1</math> gilt, und definiert <math>n=pq</math>. In der Praxis sollte n zumindest 1024, besser jedoch 1536 oder 2048 [[Bit|Binärstellen]] haben.
* Man wählt <math>y</math> zufällig in <math>(\mathbb{Z}/n\mathbb{Z})^*</math>, sodass für alle [[Primfaktorzerlegung|Primteiler]] <math>s</math> von <math>r</math> gilt: <math>y^{(p-1)(q-1)/s} \not \equiv 1 \mod n</math> gilt.

Der öffentliche Schlüssel besteht aus <math>(r,n,y)</math>, der private Schlüssel aus <math>(p,q)</math>.

=== Verschlüsseln von Nachrichten ===
Um eine Nachricht <math>m\in (\mathbb{Z}/r\mathbb{Z})</math> zu verschlüsseln, verfährt man wie folgt:
* Zuerst wählt man ein zufälliges <math>u\in (\mathbb{Z}/n\mathbb{Z})^*</math>.
* Die verschlüsselte Nachricht ist dann gegeben durch <math> c=y^m u^r \mod n </math>.

=== Entschlüsseln von Nachrichten (Decodierung) ===
Zum Entschlüsseln eines [[Geheimtext|Schlüsseltextes]] <math>c\in (\mathbb{Z}/n\mathbb{Z})^*</math> verfährt man dann wie folgt:
* Man setzt <math>a=c^{(p-1)(q-1)/r} \mod n</math> und <math>b=y^{(p-1)(q-1)/r} \mod n</math> und sucht dann ein <math>m</math> sodass <math>a=b^m\mod n</math> gilt. Ist <math>r</math> klein, so kann dies durch [[Brute-Force-Methode|Durchprobieren]] aller möglichen Werte geschehen; ist <math>r</math> dagegen groß, hat aber nur kleine [[Primfaktorzerlegung|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
:<math>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</math>

== Sicherheit ==
Unter der ''Higher-Residuosity''-Annahme kann gezeigt werden, dass das Verfahren [[Sicherheitsbegriff#Semantische Sicherheit (SEM)|semantisch sicher]] gegen [[Ciphertext Indistinguishability|Angriffe mit ausgewählten Klartexten]] ist. Diese Annahme besagt, dass für einen zusammengesetzten Modul <math>n</math> nicht effizient geprüft werden kann, ob ein Element in <math>(\mathbb{Z}/n\mathbb{Z})</math> eine <math>r</math>-te Wurzel modulo <math>n</math> besitzt oder nicht, falls <math>r</math> und <math>n</math> wie [[#Erzeugung des öffentlichen und privaten Schlüssels|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 <math>v</math> der enthaltene Wert mit <math>v</math> multipliziert wird. Außerdem kann die enthaltene Nachricht durch Multiplikation des Schlüsseltexts mit <math>y^w</math> um <math>w</math> 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 Blockgröße <math>r=9</math> und wählen <math>p=883</math> und <math>q=1019</math>. Damit gilt
:<math>\operatorname{ggT}((p-1)/r, r)=\operatorname{ggT}(882/9, 9)=\operatorname{ggT}(98, 9)=1</math>
sowie
:<math>\operatorname{ggT}(q-1, r)=\operatorname{ggT}(1018, 9)=1</math>.
Weiters wählen wir <math>y=85.147</math>, welches <math>85147^{882 \cdot 1018/3} \equiv 70977\not\equiv 1\mod (883 \cdot 1019)</math> erfüllt.

Damit erhalten wir:
r = 9
n = p·q = 899777
y = 85147

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

Der geheime Schlüssel lautet <math>(p,q) = (883,1.019)</math>.

=== Verschlüsselung ===
Angenommen, man möchte die Nachricht <math>m=6</math> verschlüsseln. Dazu wählen wir ein zufälliges <math>u\in(\mathbb{Z}/n\mathbb{Z})^*</math> :
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 <math>m=6</math>.

== Einzelnachweise ==
<references />

[[Kategorie:Asymmetrisches Verschlüsselungsverfahren]]

Benaloh-Kryptosystem - Versionsgeschichte

imported>Aka: /* Schlüsselerzeugung */ Tippfehler entfernt