Abbildung 1: Einfaches Entschl¨ usselungs MIXnetz

und die MIXe im Idealfall warten sollten, bis eine gewisse große Anzahl Nachrichten einge- gangen ist, ist es nicht m¨ oglich ausgehende Nachrichten am MIX eingehenden zuzuordnen. Die Nachrichten haben nach jeder Entschl¨ usselungsstufe zwar ein anderes Aussehen (und kommen gegebenenfalls auch in anderer Reihenfolge heraus), aber immer noch die gleiche L¨ ange. Ausf¨ uhrlicheres zu MIXen finden Sie auch in [Pfit 00].

1.2 ElGamal-Kryptoverfahren

Das ElGamal Kryptoverfahren wurde 1985 erstmals von Taher ElGamal vorgestellt. Dieses Verfahren basiert auf dem diskreten Logarithmus. Zuerst wird eine m¨ oglichst große Primzahl p gew¨ ahlt, f¨ ur die gelten sollte: p−1 2 ist ebenfalls Primzahl. Desweiteren wird ein Generator

∗ 2 gew¨ ahlt. Eine zuf¨ allig gew¨ ahlte Zahl x (1 < x < p) als privater Schl¨ ussel wird von Z p noch ben¨ otigt. Der ¨ offentliche Schl¨ ussel errechnet sich wie folgt: y = g x mod p. Neben dem ¨ offentlichen Schl¨ ussel y werden auch der Generator g und die anfangs gew¨ ahlte Primzahl p ver¨ offentlicht.

Um eine Nachricht m zu verschl¨ usseln, wird nunmehr eine Zufallszahl k mit 1 < k < p ben¨ otigt. Der ¨ offentliche Schl¨ ussel y, der Generator g, sowie die Primzahl p sind

dem Empf¨ anger bereits bekannt. Die Nachricht wird als c 0 = (my k )mod p verschl¨ usselt. Zus¨ atzlich wird die Hilfsgr¨ oße c 1 = g k mod p ¨ ubermittelt. Die Zufallszahl k wird nicht

ver¨ offentlicht.

Der Empf¨ anger erh¨ alt c 0 und c 1 . Mithilfe seines privaten Schl¨ ussels x kann er die Nachricht jetzt entschl¨ usseln: m = (c 0 c p−1−x )mod p.

Ein kurzes Beispiel soll das ElGamal-Verfahren verdeutlichen:

1. Wahl der Primzahl, Generator, privater Schl¨ ussel: p = 23, g = 5, x = 3 2. Errechnen des ¨ offentlichen Schl¨ ussels: y = g x mod p = 5 3 mod 23 = 125 mod 23 = 10

3. Nachricht und Zufallszahl: m = 7, k = 2

4. Verschl¨ usselung: c 0 = (my k ) mod p = (7 ∗ 10 2 ) mod 23 = 10

5. Hilfsgr¨ oße: c 1 = g k mod p = 5 2 mod 23 = 2

6. Entschl¨ usselung: m = (c 0 c p−1−x

) mod p = (10 ∗ 2 23−1−3 ) mod 23 = 7

Abbildung 2: Schematische Darstellung ElGamal

2 Reencryption

Die Idee der Reencryption basiert auf der Problematik der Ausfallsicherheit von MIXservern in einem MIXnetz. Im eingangs gezeigten MIXnetz ist das komplette Netz unbrauchbar, sobald ein MIX ausf¨ allt. Daher ist es sinnvoll, ein Verfahren zu haben, dass unabh¨ angig von der Anzahl der MIXe zuverl¨ assig arbeitet. Dieses Verfahren muss aber die Eigenschaften des MIXnetzes weiterhin erf¨ ullen, die Nachrichten m¨ ussen also umcodiert und umsortiert von MIX zu MIX weitergeleitet werden. Um dieses unabh¨ angig von der Anzahl der MIXe zu gestalten, bietet es sich an, ein Verfahren ohne Schl¨ usselaustausch zwischen den MIXen zu kreieren. Eine Zwischenstufe ist die Reencryption mittels ElGamal. F¨ ur dieses Verfahren wird nur noch der ¨ offentliche Schl¨ ussel des Empf¨ angers ben¨ otigt.

2.1 ElGamal-Reencryption

Basierend auf der ElGamal Verschl¨ usselung k¨ onnen Nachrichten mehrfach mit dem selben ¨ offentlichen Schl¨ ussel verschl¨ usselt, jedoch in einem einzelnen Schritt entschl¨ usselt werden. Hierbei wird das ElGamal-Tupel (c 0 , c 1 ) mittels einer weiteren Zufallszahl k erneut ver- schl¨ usselt. Wie bereits erw¨ ahnt wird das Tupel (c 0 , c 1 ) mittels (m y k , g k ) errechnet. Die Ent-

c1 x = m y k

(p−1−x) ) mod p = c0 schl¨ usselung D(c 0 , c 1 ) = (c 0 c 1

mit y = g x ergibt m g k x

g k x = m. Dadurch er¨ offnet sich die M¨ oglichkeit mittels des bekannten

¨ offentlichen Schl¨ ussels und des Generators sowie einer neuen, vom aktuellen MIXserver gebil-

deten Zufallszahl die Nachricht wiederzuverschl¨ usseln. Damit ist die Wiederverschl¨ usselung

1 ) = (c 0 y k , c 1 g k ). Die Entschl¨ usselung ergibt sich wie oben:

folgendermaßen definiert: (c 0 , c

= c0y k c1g k x = my k y k g k g k x = my kk g kk x und aus y = g x folgt: mg kk x c c

D(c 0 , c 1 ) = = m wegen c x c x

Es ist also offensichtlich, dass die Anzahl der Zufallszahlen {k, k , k , ...} und somit auch die

Anzahl der Wiederverschl¨ usselungen keinen Einfluss auf den Entschl¨ usselungsvorgang haben.

Zur Demonstration dieses Verfahrens wird obiges Beispiel aufgegriffen und dementsprechend

1. Schritte 1-4 wie oben

2. 1. Wiederverschl¨ usselung

(a) Wahl der Zufallszahl k = 15

0 = (c 0 y k ) mod p = (10 ∗ 10 15 ) mod 23 = 4

(b) Verschl¨ usselung: c

1 = (c 1 g k ) mod p = (2 ∗ 5 15 ) mod 23 = 15

(c) Hilfsgr¨ oße: c

c

3. Entschl¨ usselung nach der 1. Wiederverschl¨ usselung: D(c 0 , c

= 4

15 3 mod 23 ergibt 3 (4 ∗ 19) mod 23 = 7 = m

4. 2. Wiederverschl¨ usselung

(a) Wahl der Zufallszahl k = 7

0 y k ) mod p = (4 ∗ 10 7 ) mod 23 = 10

(b) Verschl¨ usselung: c 0 = (c

1 g k ) mod p = (15 ∗ 5 7 ) mod 23 = 2

(c) Hilfsgr¨ oße: c 1 = (c

c

5. Entschl¨ usselung nach der 2. Wiederverschl¨ usselung: D(c 0 , c

= 10

2 3 mod 23 ergibt (10 ∗ 3) mod 23 = 7 = m

2.2 Universal Reencryption

Im Gegensatz zur ElGamal-Reencryption ben¨ otigt dieses Verfahren den ¨ offentlichen Schl¨ ussel

des Empf¨ angers nicht mehr. In einem universellen Kryptosystem besteht der Ciphertext einer

Nachricht m aus einem Ciphertextpaar [E[m]; E[1]]. Da die ElGamal Verschl¨ usselung homo-

morph 4 ist, kann die zweite Komponente verwendet werden die erste wiederzuverschl¨ usseln.

Die Schl¨ usselgenerierung erfolgt wie bereits gezeigt als (P K, SK) = (y, x) = (g x , x). Der

Sender verschl¨ usselt seine Nachricht m mittels des ¨ offentlichen Schl¨ ussels y, des Generators

g und zweier Zufallszahlen k 0 , k 1 .

C = [(a 0 , b 0 ); (a 1 , b 1 )] = [(my k0 , g k0 ); (y k1 , g k1 )]

Die beiden Ciphertextteile werden analog zum ElGamal-Verfahren entschl¨ usselt.

m 0 = a0 und m 1 = a1 . Wenn m 1 = 1 ist, dann ist m 0 die Nachricht. Ist dies nicht der Fall, b x b x

so ist die Entschl¨ usselung fehlgeschlagen und eine Meldung wird ausgegeben.

Die Wiederverschl¨ usselung der Nachrichten findet wie folgt statt:

k k k k

C = [(a 0 , b 0 ); (a 1 , b 1 )] = [(a 0 a 1 ); (a 1 , b 0 b

spiel n¨ aher gebracht werden:

1. Schl¨ usselgenerierung: x = 3, g = 5, p = 23

2. Errechnen des ¨ offentlichen Schl¨ ussels: y = g x mod p = 5 3 mod 23 = 10

3. Nachricht und Zufallszahlen: m = 7, k 0 = 2, k 1 = 3

4. Verschl¨ usselung: C = [(a 0 , b 0 ); (a 1 , b 1 )]

= [(my k0 , g k0 ); (y k1 , g k1 )] = [((7 ∗ 10 2 ) mod 23, 5 2 mod 23); (10 3 mod 23, 5 3 mod 23)]

= [(10, 2); (11, 10)]

5. 1. Wiederverschl¨ usselung

(a) Wahl der Zufallszahlen: k 0 = 8, k

(b) Verschl¨ usselung: C = [(a 0 , b

= [((10 ∗ 11 8 ) mod 23, (2 ∗ 10 8 ) mod 23); (11 9 mod 23, 10 9 mod 23)]

= [(11, 4); (19, 20)]

a a

6. Entschl¨ usselung nach der 1. Wiederverschl¨ usselung: m 0 =

m 0 = 11 4 3 mod 23, m 1 = 19 20 3 mod 23, m 0 = 11 ∗ 9 mod 23, m 1 = 19 ∗ 17 mod 23

m 0 = 7, m 1 = 1 Da m 1 = 1 ist, ist m 0 = 7 die Nachricht f¨ ur diesen Empf¨ anger.

7. 2. Wiederverschl¨ usselung

(a) Wahl der Zufallszahlen: k 0 = 13, k

(b) Verschl¨ usselung: C = [(a 0 , b

= [((11 ∗ 19 13 ) mod 23, (4 ∗ 20 13 ) mod 23); (19 17 mod 23, 20 17 mod 23)]

= [(8, 10); (21, 7)]

a a

8. Entschl¨ usselung nach der 2. Wiederverschl¨ usselung: m 0 =

m 0 = 8 10 3 mod 23, m 1 = 21 7 3 mod 23, m 0 = 8 ∗ 21 mod 23, m 1 = 21 ∗ 11 mod 23

m 0 = 7, m 1 = 1 Da m 1 = 1 ist, ist m 0 = 7 die Nachricht f¨ ur diesen Empf¨ anger.

3 Anwendung im MIXnetz

Eine konkrete Anwendung von ”Universal Reencryption” sind MIXnetze. Es gibt eine Men-

ge von Sendern die Nachrichten an Empf¨ anger senden wollen, ohne dass der Weg dieser

Nachrichten von irgendjemandem verfolgt werden kann. Es ist davon auszugehen, dass je-

der m¨ ogliche Sender alle ¨ offentlichen Schl¨ ussel seiner m¨ oglichen Empfangspartner kennt. Das

Kommunikationsprotokoll sieht dann wie folgt aus:

• Initialisierung

Jeder Sender ver¨ offentlicht seine universell verschl¨ usselte Nachricht; verschl¨ usselt mit

dem ¨ offentlichen Schl¨ ussel des Empf¨ angers, f¨ ur den diese Nachricht sein soll. Diese

Nachrichten aller Sender werden in irgendeiner Form 5 gesammelt. Alle Eintr¨ age ha- ben das gleiche Aussehen ([E(m); E(1)]), daher sind sie durch reines Betrachten nicht

• Universelles Mixen Jeder MIXserver erh¨ alt nunmehr einen Pool von Nachrichten den er wiederverschl¨ usselt und weitergibt; im Fall des Bulletin Board ver¨ offentlicht er sie einfach wieder.

• Empfangen der Nachricht Potentielle Empf¨ anger m¨ ussen alle Nachrichten entschl¨ usseln die das MIXnetz aus- gibt. Erfolgreiche Entschl¨ usselungen geben die Nachrichten aus, nicht erfolgreiche Ent- schl¨ usselungen geben die Fehlermeldung aus.

4 Schlußbemerkungen

4.1 Aufwand

Offensichtlich ist dieses Verfahren erheblich aufw¨ andiger als andere bekannte Verfahren. Schon aufgrund der zwei Ciphertextpaare ist der Wiederverschl¨ usselungsaufwand doppelt so hoch wie beim ElGamal-Reencryption Verfahren. Ebenfalls aufwendig erscheint der Broad- cast am Ende der MIXkette. Jeder m¨ ogliche Empf¨ anger muss also von allen n Nachrichten den zweiten Ciphertextteil entschl¨ usseln um herauszufinden, ob die Nachricht ¨ uberhaupt f¨ ur

ihn ist, um dann erst die eigentliche Nachricht zu entschl¨ usseln. Im Einzelnen: 6 O Sender = 2 O Reencryption = 2nk O Recipient = n + 1 O = 2 + 2nk + n + 1 = 2nk + n + 3

mit n − Anzahl N achrichten und k − Anzahl M IXserver F¨ ur n = 10 und k = 5 ist O n=10,k=5 = 2nk + n + 3 = 113.

Offensichtlich ist dieses Verfahren erheblich aufw¨ andiger als andere Verfahren.

4.2 Korrektheit

Solange alle MIXserver korrekt arbeiten, ist dieses Verfahren als korrekt anzusehen. Arbei- tet einer der MIXserver nicht mehr korrekt, geht die Nachricht verloren, da durch falsches Wiederverschl¨ usseln auch der zweite Ciphertextteil falsch wiederverschl¨ usselt wird und der eigentlich gemeinte Empf¨ anger diese Nachricht nicht finden kann. Eine zweite M¨ oglichkeit w¨ are, ein MIX versucht nur den ersten Ciphertextteil einer Nachricht zu ersetzen um einen Empf¨ anger gezielt falsche Informationen zukommen zu lassen. Dieses w¨ are m¨ oglich, wenn die- ser MIX weiß, welche Nachricht f¨ ur welchen Empf¨ anger ist, und er im Besitz des ¨ offentlichen Schl¨ ussels dieses Empf¨ angers ist.

4.3 Anonymit¨ at

Solange auch nur ein MIXserver ehrlich arbeitet, ist die Anonymit¨ at der Kommunikation gew¨ ahrleistet. Diese kann durch die Tatsache gw¨ ahrleistet werden, dass auch nach nur einem MIXserver nicht mehr nachvollzogen werden kann, von wem an wen diese Nachricht versandt

4.4 FAZIT

Das Verfahren des Universal Reencryption ist damit als Variante f¨ ur MIXnetze einsetzbar. Der große Vorteil liegt unzweifelhaft darin, dass es keine Schl¨ ussel der weiteren Kommunika- tionsteilnehmer ben¨ otigt. Ein weiterer Vorteil liegt darin, dass es m¨ oglich wird, MIXnetze zu skalieren und selbst bei Ausfall eines MIXes die Nachricht nicht zu verlieren. Der Hauptnach- teil dieses Verfahrens liegt in der Zustellung und Entschl¨ usselung der Nachrichten. Dadurch, dass jeder m¨ ogliche Empf¨ anger von allen Nachrichten zumindest einen Teil entschl¨ usseln muss, um ¨ uberhaupt ersteinmal herauszufinden, ob die Nachricht f¨ ur ihn ist, ist der Auf- wand f¨ ur die Zustellung der Nachrichten sehr hoch. Hier wird noch zu ¨ uberlegen sein, ob

dieses Verfahren im Ergebnis noch praxisrelevant einsetzbar ist.

[Pfit 00] A.Pfitzmann, Sicherheit in Rechnernetzen: Mehrseitige Sicherheit in verteilten und durch verteilte Systeme, 1990-2000, Karlsruhe, Hildesheim, Dresden

[www 00] Phillip Golle, Markus Jakobsson, Ari Juels, Paul Syverson, Universal Reencryption for Mixnets, publiziert unter:

[Abbildung 1] aus: A.Pfitzmann, Sicherheit in Rechnernetzen: Mehrseitige Sicherheit in verteilten und durch verteilte Systeme, S. 211, 1990-2000, Karlsruhe, Hildesheim, Dresden