Dark ITSec

ELGamal

In PGP, GnuPG und in S/MIME wird für die Verschlüsselung des Sitzungsschlüssels ein asymmetrisches Verfahren gewählt.
Neben RSA ist hier Diffie-Hellmann und ElGamal vorgesehen.

1. Schritt

Zunächst benötigen wir eine große Primzahl Z. Sicherheitshalber sollte diese Zahl um Eins verringert und dann halbiert (Z-1)/2 ebenfalls prim sein. Je nach Schlüssellänge ist diese Zahl viele Bit lang, in unserem Falle soll ihr Wert aber nur 11 betragen.

2. Schritt

Wir benötigen zwei weitere beliebige Zahlen y und g, die größer als Eins, aber kleiner als die Zahl Z sein müssen. Nehmen wir für unser Beispiel y=2 und g=3. Aus diesen Werten, zusammen mit Z, bilden wir:

p=y^g mod Z

Also y wird mit g potenziert, durch Z geteilt und der Rest wird als p weiterverwertet.

p, y und Z sind öffentlich und werden auch im öffentlichen Schlüssel verwendet. g dagegen ist geheim und darf nie veröffentlicht werden.

Betrachten wir das Ergebnis mal in unserem Beispiel:

p	=	23	mod 11
	=	8/11
	=	0	Rest 8
p	=	8

Damit hätten wir bis jetzt

Z = 11
p = 8
y = 2
g = 3

Verschlüsselung

Die Klartextnachricht soll lauten:

05070810

Die zu verschlüsselnde Nachricht muss einen Wert aufweisen, der kleiner als Z ist, sonst muss er in Teile zerlegt werden.

Für unser Beispiel gilt daher für die Nachricht:

05 07 08 10

Der Absender benötigt noch eine zufällige Zahl x, die größer Eins, aber kleiner Z-1 sein muss und keinen gemeinsamen Teiler mit Z haben soll. Wir nehmen mal den Wert x=5 an.

Der Absender erzeugt zunächst mal die Hilfsgrösse c1:

c₁= y^x mod Z

und ausserdem für jeden zu verschlüsselnden Klartextteil

c₂=(k p^x) mod Z mit k= Klartextteil.

In unserem Beispiel wäre c1 damit

c1	=	25	mod 11
	=	32/11
	=	2	Rest 10
c1	=	10

und für c₂ ergäbe sich mit k=05

c2	=	(5*85)	mod 11
	=	163840/11
	=	14894	Rest  6

usw.

k	c2
05	06
07	04
08	03
10	01

Die chiffrierte Nachricht lautet

06 04 03 01

Zusätzlich wird der Wert c₁=10 übermittelt.

Entschlüsselung

Der Empfänger weiss nichts von der Hilfszahl x, benötigt diese aber für die Rückrechnung auch nicht.
Für die Entschlüsselung gilt

k= (c₂ c₁^(Z-1-g)) mod Z

Im ersten Teil der Nachricht 06 würde dies ergeben:

k	=	(6*10(11-1-3))	mod 11
	=	(6*107)	mod 11
	=	6*10000000/11
	=	5454545	Rest 5

 

c2	k
06	05
04	07
03	08
01	10

Die Darstellung sollte zeigen, dass ähnlich wie bei RSA der Vorgang sehr simpel und die Mathematik nicht schwierig ist (sieht man mal vom Umgang mit sehr großen Zahlen ab). Unsere Darstellung ist bewusst sehr einfach gewählt und hat dem besseren Verständnis dienend unrealistisch kleine Werte verwendet. Ziel war es dabei nicht, die Unbrechbarkeit von ElGamal zu beweisen, sondern vielmehr Verständnis für die Vorgänge zu wecken, die sonst immer hinter den Vorhängen stattfinden.