ElGamal Systeme

Seminar Kryptographie und Datensicherheit

ElGamal Systeme

Michal OlejniczakPawel Kiedrowski

Seminar Kryptographie und Datensicherheit ElGamal Systeme 2

Übersicht

• Über Taher Elgamal• Einführung in die Gruppentheorie• Problem der diskreten Logarithmen• ElGamal Kryptosystem• Massey-Omura Verfahren• Der Shanksche Algorithmus• Pohlig-Hellman Algorithmus• Index Calculus Methode• DLP in (Zn, +)


Über Taher Elgamal

• Amerikanischer Wissenschaftler– Doktor an der Stanford-Universität– Spezialgebiete: Kryptologie und

Datensicherheit• Erfinder des ElGamal Kryptosystems („A

Public Key Cryptosystem and a Signature Scheme based on Diskrete Logarithms “ aus 1985)

• Zahlreiche Beiträge zur Kryptologie:– Digital Signature Standard– SSL-Protokoll


Einführung in die Gruppentheorie (I)

• Verknüpfung: Abbildung f, die ein Paar (a, b) auf einen Wert f(a, b) abbildet. Falls a, b M und f(a, b) M gilt (also f : M x M -> M), dann spricht man von einer Verknüpfung in M.

• Die Menge M zusammen mit der Verknüpfung heißt Verknüpfungsgebilde.


Einführung in die Gruppentheorie (II)• Das Verknüpfungsgebilde (G, *), wobei G

eine Menge und * eine zweistellige Verknüpfung auf G ist, heißt Gruppe, wenn folgende Axiome erfüllt sind:– Abgeschlossenheit: Sind a und b Elemente aus

M, so ist auch a × b aus G. – Assoziativität: a × (b × c) = (a × b) × c – Neutrales Element: Es existiert ein Element e

(auch 1 genannt) in G, so dass für alle Elemente gilt a × e = e × a = a.

– Inverses Element: Zu jedem Element a in G existiert ein Element, nenne es a-1, so dass a × a-1 = a-1 × a = e.


Einführung in die Gruppentheorie (III)

• Anzahl der Elemente wird als Ordnung der Gruppe bezeichnet, geschrieben |G|

• Ein Gruppenelement g G hat die Ordnung k, wenn k die kleinste natürliche Zahl ist, so dass

gk = e gilt.• Endliche Gruppen haben folgende Eigenschaft:

g|G| = e (dies kann auch für Untergruppen gelten).


Einführung in die Gruppentheorie (IV)• Betrachtet werden natürliche Zahlen bis

Obergrenze n => Erzwingung der Endlichkeit.

• Ergebnisse werden modular reduziert.• Wenn a und b ganze Zahlen sind mit a > b >

0 und es gilt: a = q * b + r, dann ist r der Rest bei der Division a/b, 0 ≤ r < b.

• Eine Funktion mod: Z x N -> N heiße Modulo-Funktion, wenn gilt:

• Der größte gemeinsame Teiler von a und b, ggT(a,b), ist diejenige größte natürliche Zahl g, für die gilt: a = q * g ^ b = p * g, wobei p, q N+


Einführung in die Gruppentheorie (V)

• Es soll die Gruppe (Zn, ) definiert werden. Es sei Zn ={0,1,2, … , n-1}

• Für a, b Zn ist die Verknüpfung dann folgendermaßen definiert: a b := (a + b) mod n

• Alle Axiome für diese Gruppe sind erfüllt• Die Ordnung der Gruppe beträgt |Zn|=n


Einführung in die Gruppentheorie (VI)• Betrachtet wird die Verknüpfung (Zn, ). Null ist

kein Element der Gruppe Zn.• Problem: das inverse Element existiert im

allgemeinen nicht.• Lösung: man definiert eine Gruppe Zn

*, man nimmt nur die Elemente a < n, die teilerfremd zu n sind: Zn

* = {a Zn | ggT(a, n) = 1}• Die Ordnung der Gruppe wird über die

Eulersche Ф-Funktion berechnet: |Zn*| = Ф(n)

– Ф(p) = p – 1 falls p prim ist– Ф(p*q) = (p – 1)*(q – 1) falls p und q prim sind

• Zyklische Gruppe: {i : 0 ≤ i ≤ p - 2}• |Zn

*| ist zyklisch, wenn n prim ist.


Problem der diskreten Logarithmen (I)

• Damit die Gruppe G für ein Kryptosystem geeignet ist, muss die Exponentation in G die Eigenschaften einer Einwegfunktion erfüllen.– Die Berechnung von ist effizient möglich– Die Berechnung von ist schwer


Problem der diskreten Logarithmen (II)

• Beispiel für Z11 = {0,1,2,…,10}

a = 0 => 3a mod p = 30 mod 11 = 1 mod 11 = 1a = 1 => 3a mod p = 31 mod 11 = 3 mod 11 = 3a = 2 => 3a mod p = 32 mod 11 = 9 mod 11 = 9a = 3 => 3a mod p = 33 mod 11 = 27 mod 11 = 5a = 4 => 3a mod p = 34 mod 11 = 81 mod 11 = 4a = 5 => 3a mod p = 35 mod 11 = 243 mod 11 = 1a = 6 => 3a mod p = 36 mod 11 = 729 mod 11 = 3a = 7 => 3a mod p = 37 mod 11 = 2187 mod 11 = 9a = 8 => 3a mod p = 38 mod 11 = 6561 mod 11 = 5 …


ElGamal Kryptosystem (I)• Schlüsselerzeugung: man wählt eine Primzahl

p (für die das DL Problem in Zp* unlösbar ist)

und zwei andere Zahlen (Primitivelement Zp*)

und a die kleiner als p sind. Man berechnet β:β = a mod p

– Öffentlicher Schlüssel (p, , β) wird publiziert– Privater Schlüssel (p, , β, a)

• Verschlüsselung: Um eine Nachricht x zu verschlüsseln, wählt man eine Zahl k und berechnet: eK(x,k)=(y1,y2),wo y1= k mod p, y2 = x β k mod p


ElGamal Kryptosystem (II)

• Entschlüsselung: dK(y1, y2) = y2(y1

a)-1 mod pMan berechnet das erhaltene k zur Potenz a: (k)a= ka = (a)k = βk

Man findet eine Inverse ξ zur βk (modulo p) mit Hilfe des erweiterten Euklidschen Algorithmus.

• Schließlich dividiert man mit βx:(x* βk)* ξ ≡ x * (βk * ξ) ≡ x * 1 ≡ x mod p


ElGamal Kryptosystem (III)

• Wir nehmen p = 2579, = 2 und a = 765 an.

• Berechnung von β:β = 2765 mod 2579 = 949

• Nachricht x = 1299 wird gesendet. Die zufällige Zahl ist k = 853. Man berechnet:

k = 2853 mod 2579 = 435x * βk = 1299 * 949853 mod 2579 =

2396• Entschlüsselung der Nachricht (435, 2396)

x = 2396*(435765)-1 mod 2579 = 1299


ElGamal Kryptosystem (IV)

• β = a mod py1= k mod py2 = x β k mod p

• x’ = y2 * y1p -1 - a mod p

• x’ = y2 * y1p -1 - a = (x * βk) * (k) p -1 - a =

= x * (a)k * -ak * k(p-1) • x’ = x * k(p-1) = x


ElGamal Kryptosystem (V)

• Momentan kann ElGamal als ein effektives Kryptosystem angesehen werden.

• Derzeit keine effizienten Algorithmen zur Berechnung diskreter Logarithmen.

• Zur Verschlüsselung sind zwei modulare Exponentationen nötig.

• Zur Entschlüsselung ist eine modulare Exponentation erforderlich.


ElGamal Kryptosystem (VI)

• Für Gruppe Zp* und p > 500 Bit

– 512 Bits (geringe Sicherheit) bis 1024 Bits (hohe Sicherheit)

• DL-Problem hängt von der Wahl der Gruppe ab.– Momentan so schwer wie

Faktorisierung angesehen

Jahr Schlüssel-länge

1990 6222000 9522010 13692020 18812030 24932040 32142050 4047


Massey-Omura Verfahren (I)

• Kryptosystem das ebenfalls auf dem Problem des diskreten Logarithmus basiert.

• Hat keine öffentliche Schlüssel• Keine gemeinsame geheime Schlüssel• Dient hauptsächlich zum Austausch von

Schlüsseln


Massey-Omura Verfahren (II)

• Wir betrachten Gruppe Zp* , p ist Primzahl.

• Beobachtung: sei e Zp* und d=e-1 mod (p-

1) das heißt ed 1(mod p-1). Dann gilt für x Zp

*

xed xs(p-1)+1 für ein s N x(p-1)s x x (mod p) weil x(p-1) 1

• Kommunikation - alle Teilnehmer kennen eine Primzahl p. A möchte an B Nachricht m Zp

* senden.


Massey-Omura Verfahren (III)


Massey-Omura, Zusammenfassung

• Nachteil: wir brauchen drei Nachrichten zum Schlüsseltausch und das macht „man-in-the-middle“-Angriffe möglich.

• Vorteil: Jeder Teilnehmer hat einen Schlüssel zum Verschlüsseln und einen zum Entschlüsseln.

• Keiner der Teilnehmer kennt die Schlüsseln des anderen. Es seiden jemand wird eine DL-Instanz brechen.


Algorithmen für das DL-Problem

• Berechne i solange, bis = a gefunden ist.

• Algorithmus braucht eine Laufzeit von O(n);


Algorithmen für das DL-Problem Der Shanksscher Algorithmus

• Wir suchen a, 0 a n-1 : a = bzw. a = log

• Beobachtung: Sei m :=n. Wir können schreiben: log = mj + i mit i,j 0 und i m-1

• Wir möchten jetzt zeigen, dass auch j m-1 darum nehmen wir an, dass j m => dann log = mj + i m2 n

aber: a = log n-1 Widerspruch !


Der Shanksscher Algorithmus (I)


Der Shanksscher Algorithmus (II)

• Warum funktioniert das? Wenn unsere Suche in Schritt 6 erfolgreich ist, dann gilt für i und j : mj = -i mj+i = mj + i = log


Der Shanksscher Algorithmus (III)

• Beispiel• Wir wollen log3525 in (Z809

* ,*) finden. 809 ist Primzahl. Wir haben =3, n=808, =525 und m=808 29

• Jetzt haben wir 29mod 809 = 99• Zuerst rechnen wir Paaren (j, 99j mod809)

´ für 0 j 28• Dann rechnen wir Paaren (i, 525*(3i)-1

mod809) für 0 i 28


Der Shanksscher Algorithmus (IV)

• für 0 j 28• (0,1) (1,99) (2,93) (3,308) (4,559) (5,329) (6,211)

(7,664) (8,207) (9,268) (10,644) (11,654) (12,26) (13,147) (14,800) (15,727) (16,781) (17,464) (18,632) (19,275) (20,528) (21,496) (22,564) (23,15) (24,676) (25,586) (26,575) (27,295) (28,81)

• 0 i 28• (0,525) (1,175) (2,328) (3,379) (4,396) (5,132) (6,44)

(7,554) (8,724) (9,511) (10,440) (11,686) (12,768) (13,256) (14,355) (15,388) (16,399) (17,133) (18,314) (19,644) (20,754) (21,521) (22,713) (23,777) (24,259) (25,356) (26,658) (27,489) (28,163)


Der Shanksscher Algorithmus (V)

• Jetzt müssen wir diese zwei Listen miteinander vergleichen und wir finden heraus dass (10,644) in L1 und (19,644) in L2 den selben wert haben.

• In unseren Beispiel a ist gleichlog3525 = (29 * 10 + 19 ) mod 808 = 309

• Wir prüfen jetzt ob unser Ergebnis stimmt 3309 525 (mod 809)


Der Shanksscher Algorithmus (VI)

• Komplexität

• Algorithmus braucht eine Laufzeit von O(m log m); bei Vernachlässigung logarithmischer Faktoren auf O(m) reduzierbar

• Dise Methode braucht auch vielen Speicherplatz für die beiden Listen


Algorithmen für das DL-Problem

Der Pohlig-Hellman-Algorithmus• Zuerst betrachten wir ein System von

linearen Kongruenzen mit a1,..., ar N, m1,...,mr N+, ggT(mi, mj)= 1 für i j und 1 i,j r. Wir suchen solche x, die alle Kongruenzen gleichzeitig erfüllen.


Der Pohlig-Hellman-Algorithmus (I)

• Zur Lösung von solchen Systeme brauchen wir den Chinesischen Restsatz:Gegeben sei ein System von linearen Kongruenzen. Alle Lösungen eines solchen Systems sind kongruent modulo M:= m1 m2... mr, und die Lösung modulo M ist


Der Pohlig-Hellman-Algorithmus (II)

• Wir gehen davon aus, dass wir die Primfaktoren von n kennen.

n = p1C1 * p2

C2 * ...* pkCk

Wo p1,..., pk verschiedene Primzahlen sind.• Wir suchen a = log (mod n). Nehmen wir an,

dass wir a mod piCi für alle Primfaktoren pi, 1 i

k, kennen, also Zahlen x1,..., xk mit:


Der Pohlig-Hellman-Algorithmus (III)

• Wie finden wir a mod piCi ?

• Wir suchen x = a mod qc für gegebene Primzahl q und ein c, für die gilt:

n =0 (mod qc) n 0 (mod qc+1)• Wir können auch schreiben daß:

a = x + sqC


Der Pohlig-Hellman-Algorithmus (IV)

• Für s N. dann folgende Formel für x stimmt.x = a0q0+ a1q1+....+ aC-1qC-1 für 0 a q-1

• Wir berechnen a0.• Dann berechnen wir aj aus aj-1 für j = 1,...,c-1

• Um a0 zu berechnen benutzen wir folgende Behauptung :n/q = aon/q


Der Pohlig-Hellman-Algorithmus (V)

• Beweis: n/q = aon/q


Der Pohlig-Hellman-Algorithmus (VI)

• Jetzt müssen wir aj aus aj-1 für j = 1,...,c-1 berechnen

• Wir definieren: 0 := j := -(ao+ a1q+...+ aj - 1q ) für 1 j c-

1• Man kann beweisen, dass unsere

Behauptung auch für folgende Gleichung erfüllt ist:


Der Pohlig-Hellman-Algorithmus (VII)


Der Pohlig-Hellman-Algorithmus (VIII)

• Komplexität

• Algorithmus braucht eine Laufzeit von O(cq);

• Wenn wir in Zeile 4 Shanksschen Algorithmus benutzen um das a zu finden dann erhalten wir Gesamtlaufzeit von O(cq)


Die Index Calculus Methode

• Die Index Calculus Methode lässt sich nur in Zp*

mit p Primzahl und primitives Element modulo p anwenden.

• Sie benutz eine Menge B={p1, p2,..., pB} „kleiner“ Primzahlen.

• Funktionsweise:1. Die Logarithmen der B Primzahlen in B werden

bestimmt.2. Mit Hilfe der nur bekannten diskreten

Logarithmen der B Primzahlen wird dann log berechnet.


Diskreter Logarithmus Problem in (Zn,+)

• Reduktion des Problems auf die additive Gruppe (Zn,+) mit Hilfe eines Isomorphismus Ф: (Zn,.) (Zn,+). Das Diskreter Logarithmus Problem lässt sich wie folgt übertrage: Finde a Zn mit a = (mod n). Schnell zu berechnen, da a= -1 mod n. Es existiert keine effiziente Methode zur Bestimmung des Isomorphismus.

Seminar Kryptographie und Datensicherheit

Danke für die Aufmerksamkeit

Fragen? Fragen

Documents

ElGamal Systeme