Kryptografische Protokolle

ElGamal-Verschlüsselung

 aufwärts

Das Ver­schlüsselungsverfahren von ElGamal [ElG 85] ist im Prinzip nichts anderes als eine Diffie-Hellman-Schlüssel­vereinbarung mit anschließendem Senden einer Nachricht, die mit dem vereinbarten Schlüssel ver­schlüsselt ist.

Prinzip

Öffentlich bekannt ist wiederum eine Primzahl p und eine Zahl g. Zunächst wird das Diffie-Hellman-Protokoll ausgeführt; beide Kommunikationspartner verfügen anschließend über den gemeinsamen Schlüssel k. Danach ver­schlüsselt der Sender B den Klartext m mit dem gemeinsamen Schlüssel k und sendet den resultierenden Geheimtext c an A. Der Empfänger A ent­schlüsselt den Geheimtext c mithilfe des gemeinsamen Schlüssels k und erhält den Klartext m zurück.

 

         A C          B 
 Primzahl p
Zahl g mit
1 < g < p-1
   
wählt
   Zufallszahl u
  wählt
   Zufallszahl v
  
berechnet
   a = gu mod p
  berechnet
   b = gv mod p
  Diffie-Hellman
     
berechnet
   k = bu mod p
  berechnet
   k = av mod p
  
    
  Verschlüsseln 
  berechnet
   c = k·m mod p
 
   
Entschlüsseln   
berechnet
   k -1·c mod p
= k -1·k·m mod p
= m mod p
   
Bild 1: Diffie-Hellman-Schlüsselvereinbarung mit anschließender Verschlüsselung

Das Verschlüsseln des Klartextes m mit dem Schlüssel k entspricht einer Multi­plikation

c  =  k · m  mod p.

Das Entschlüsseln des Geheimtextes c mit dem Schlüssel k entspricht der Multi­plikation

m  =  k-1 · c  mod p.

Realisierung

In der tat­sächlichen Realisierung finden die Berechnungen und Über­tragungen von Daten gegenüber dem obigen Diagramm zeitlich versetzt statt (siehe Bild 2).

 

         A C          B
Schlüssel
erzeugen
  
wählt
   Primzahl p
   Zahl g mit 1<g<p-1
   Zufallszahl u
  
berechnet
   a = gu mod p
  
   
Schlüssel
ver­öffentlichen
  
 p, g, a 
  Verschlüsseln
  wählt
   Zufallszahl v
  berechnet
   b = gv mod p
   k = av mod p
  berechnet
   c = k·m mod p
  
Entschlüsseln  
berechnet
   k -1 = b-u mod p
  
berechnet
   k -1·c mod p
= k -1·k·m mod p
= m mod p
  
Bild 2: Verschlüsselungsverfahren von ElGamal

A erzeugt die Zahlen p, g und a und ver­öffentlicht diese als seinen öffentlichen Schlüssel, hält aber die Zahl u als privaten Schlüssel geheim.

Von diesem Zeitpunkt an kann ein beliebiger Sender B einen Klartext m mit dem öffentlichen Schlüssel des Empfängers A verschlüsseln, indem er zunächst k berechnet und daraufhin m mit k ver­schlüsselt. Zusätzlich zum eigentlichen Geheimtext c sendet er nun die Zahl b an den Empfänger A. Dieser kann mithilfe seines privaten Schlüssels u die Zahl k-1 berechnen und den Klartext m zurück­gewinnen.

Sicherheit

Die Sicherheit des Ver­schlüsselungsverfahrens von ElGamal beruht auf der Sicherheit der Diffie-Hellman-Schlüssel­vereinbarung. Wichtig ist hier, dass g erzeugendes Element von ganze Zahlenp* ist.

Anhand von Bild 1 lässt sich erkennen, dass der Klartext m aus dem Geheimtext c nur durch Kenntnis des Schlüssels k zurück­gewonnen werden kann. Die Zahl k aber lässt sich aus den öffentlich bekannten Zahlen p, g, a und b nicht effizient berechnen (Problem des diskreten Logarithmus).

Durch eine Known-Plaintext-Attack allerdings, also bei Kenntnis eines Klartextes m und des zugehörigen Geheimtextes c, lässt sich k berechnen, nämlich durch

k  =  c · m-1  mod p

Daher ist es wichtig, den Schlüssel k immer nur ein einziges Mal zu verwenden. Dies geschieht dadurch, dass der Sender B bei jeder neuen Ver­schlüsselung eine neue Zufallszahl v wählt, so dass jedesmal ein neues k und ein neues b erzeugt werden.

Auch wenn ein längerer Klartext in Zahlen m0, m1, m2 usw. zerlegt wird, die einzeln ver­schlüsselt werden, muss jedesmal eine neue Zufallszahl v verwendet werden.

Effizienz

Für die Ver­schlüsselung einer Zahl m sind zwei modulare Exponentiationen und eine modulare Multi­plikation erforderlich.

Für die Ent­schlüsselung ist eine modulare Exponentiation und eine modulare Multi­plikation erforderlich. Die Berechnung b-u mod p lässt sich nämlich, sofern u < p gewählt wird, als modulare Exponentiation bp-1-u mod p ausführen, denn es ist (modulo p gerechnet)

bp-1-u   =   bp-1 · b-u   =   1 · b-u   =   b-u.

 

Beispiel

Anhand eines Zahlen­beispiels mit kleinen Zahlen lässt sich der Ablauf der Berechnungen noch einmal nach­voll­ziehen.

Schlüssel erzeugen

Der Empfänger A ver­öffentlicht als öffentlichen Schlüssel drei Zahlen p, g und a. Hierbei ist p eine starke Primzahl:

p:       

ferner ist g ein erzeugendes Element der Gruppe ganze Zahlenp*:

g:       

Um a zu berechnen, wählt A eine Zufallszahl u mit 1<u<p-1:

u:       

und berechnet a  =  gu mod p:

a:  

Der öffentliche Schlüssel von A ist also (p, g, a) = (11, 2, 8).

 

Verschlüsseln

Der Sender B möchte eine Nachricht m an A schicken:

m:       

Hierzu wählt B zunächst eine Zufallszahl v:

v:       

und berechnet b  =  gv mod p:

b:  

und k  =  av mod p:

k:  

sowie anschließend c   =   k · m mod p:

c:  

Somit sendet B den Geheimtext (b, c) = (9, 10) an A.

 

Entschlüsseln

Der Empfänger A berechnet zunächst k -1  =  b -u mod p  =  bp-1-u mod p:

k-1

sowie anschließend m  =  k -1 · c mod p:

m:  

und erhält somit den Klartext m = 7 zurück.

Literatur

[Bu 00]J.A. Buchmann: Introduction to Cryptography. Springer (2000)
[ElG 85]T. ElGamal: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31, 469-472 (1985)
[Wät 04]D. Wätjen: Kryptographie. Spektrum (2004)

 

Weiter mit:   [Shamirs No-Key-Protokoll]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 19.02.2010   Updated: 11.06.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik