Cryptography Reference
In-Depth Information
wobei der (zufallsgesteuerte) Schlüsselgenierungsalgorithmus G wie folgt arbeitet: Zu-
nächst lässt er GroupGen laufen, um ein Tupel der Form ( G,n,g ) zu erhalten, wobei, wie
beschrieben,
die Beschreibung einer zyklischen Gruppe mit Ordnung n und Erzeuger
g ist. Anschließend wählt G zufällig und gleichverteilt ein b ∈{ 0 ,...,n− 1 } und gibt
ein Schlüsselpaar bestehend aus dem öffentlichen Schlüssel (
G
,n,g,g b ) und dem privaten
G
Schlüssel (
G
,n,g,b ) aus. Wir nehmen an, dass das Multiplizieren und das Berechnen des
Inversen in
jeweils ezient möglich ist.
Die Menge K bezeichnet die Menge der Schlüsselpaare, die von G ausgegebenen werden
können. Gemäß Definition 6.1.1 bezeichnet K pub die Menge der öffentlichen und K priv
die Menge der privaten Schlüssel in K .
Die Menge der Klartexte ist
G
X = {G} ( G,n,g,h ) ∈K pub
,
d. h., die Klartexte sind die Gruppenelemente der jeweils betrachteten Gruppe.
Der Chiffrieralgorithmus E , der einen öffentlichen Schlüssel ( G,n,g,h ) und einen Klar-
text x
∈G
als Eingabe bekommt, ist wie folgt definiert:
E ( x, (
,n,g,h )):
a=flip(
G
{
0 ,...,n
1
}
)
gib ( g a ,x
h a ) aus
·
Der Dechiffrieralgorithmus D , der einen privaten Schlüssel (
G
,n,g,b ) und einen Chif-
fretext ( y 0 ,y 1 ) ,also y 0 ,y 1 ∈G
, als Eingabe bekommt, ist wie folgt definiert:
D (( y 0 ,y 1 ) , ( G,n,g,b )):
gib y 1 ·
(( y 0 ) b ) 1 aus
wobei (( y 0 ) b ) 1 das inverse Element zu ( y 0 ) b in
G
ist.
Zusammen mit der Annahme, dass die Laufzeit von GroupGen durch eine Konstante
beschränkt ist und dass das Multiplizieren und das Berechnen des Inversen in den von
GroupGen erzeugten Gruppen ezient möglich ist, sieht man leicht, dass das ElGamal-
Kryptoschema in der Tat ein asymmetrisches Kryptoschema gemäß Definition 6.1.1 ist.
Wie steht es nun mit der Sicherheit des GroupGen-ElGamal-Kryptoschemas? Zunächst
ist zu bemerken, dass, anders als RSA, ElGamal kein deterministisches Kryptoschema ist.
ElGamal kann also nicht sofort als unsicher entlarvt werden. Die Sicherheit von ElGamal
hängt allerdings stark von GroupGen ab, also der Klasse der betrachteten Gruppen.
Naheliegend ist, ElGamal mit den Einheitengruppen
Z p für ausreichend große Prim-
zahlen p zu betreiben. In diesem Fall liefert der Algorithmus GroupGen also Tupel der
Form ( p, p
1 ,g ) , wobei die Primzahl p in der ersten Komponente eine Beschreibung für
Z p ist und g ein Erzeuger von
Z p ist.
Wie wir nun sehen werden, ist diese Variante von ElGamal aber leider unsicher. Ähn-
lich wie für RSA kann nämlich aus dem Chiffretext das Jacobi-Symbol des Klartextes
berechnet werden. Da L p ( x )=J p ( x ) für alle Primzahlen p> 2 gilt, spielt es im folgenden
Lemma keine Rolle, ob wir das Legendre- oder das Jacobi-Symbol verwenden.
Search WWH ::




Custom Search