RSA	Pohlig-Hellman Algorithmus

Das ElGamal Kryptosystem

Verschlüsselung Entschlüsselung Korrektheit Nachteile

Die Sicherheit des RSA-Systems basiert darauf, dass Faktorisieren von natürlichen Zahlen wahrscheinlich algorithmisch schwierig ist, das bedeutet, es sind derzeit keine Polynomialzeitalgorithmen zur Lösung dieses Problems bekannt. Ein vermutlich ähnlich schweres Problem ist das des diskreten Logarithmus in $\text{[math]}$ , auf dem das ElGamal Kryptosystem basiert. Hintergrund ist folgender:

Gegeben:	Ein Tripel $\text{[math]}$ , wobei $\text{[math]}$ eine Primzahl und $\text{[math]}$ primitiv ist, also Erzeuger von $\text{[math]}$ ,
	das heißt $\text{[math]}$ , und $\text{[math]}$ .
Gesucht:	Ein $\text{[math]}$ mit $\text{[math]}$ und $\text{[math]}$ .

Für kryptographische Anwendungen sollte die Primzahl $\text{[math]}$ mindestens $\text{[math]}$ Bits haben, damit ein Angreifer nicht mit Brute Force Verfahren ein geeignetes $\text{[math]}$ mit $\text{[math]}$ in vertretbarer Zeit finden kann.

Verschlüsselung

Alice möchte an Bob eine Nachricht senden. Beim ElGamal Kryptosystem ist das Tripel $\text{[math]}$ öffentlich, während $\text{[math]}$ mit $\text{[math]}$ geheim ist. Zum Verschlüsseln einer Nachricht $\text{[math]}$ wählt Alice eine zufällige Zahl $\text{[math]}$ und berechnet

\text{[math]}

Entschlüsselung

Zum Dechiffrieren wird von Bob

\text{[math]}

berechnet.

Man wählt nicht $\text{[math]}$ , da dann $\text{[math]}$ als Klartext übertragen wird.

Korrektheit

\text{[math]}

Nachteile

Das Chiffrat ist doppelt so lang wie der Klartext.

Wird zweimal der gleiche Exponent $\text{[math]}$ verwendet, so kann ein Angreifer, wenn er zwei Chiffrate $\text{[math]}$ und $\text{[math]}$ hat und die zu $\text{[math]}$ zugehörige Nachricht $\text{[math]}$ , auch die zu $\text{[math]}$ gehörige Nachricht $\text{[math]}$ mit $\text{[math]}$ berechnen, denn wegen $\text{[math]}$ und $\text{[math]}$ gilt $\text{[math]}$ .