ElGamal

0pa
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 20. Sep 2011 16:33

ElGamal

Beitrag von 0pa »

In den Vorlesungsfolien steht, dass sich der Public Key bei ElGamal aus g und h zusammen setzt, wobei sich h aus der Potenz von g mit a errechnen lässt.

Die Verschlüsselung erfolgt dann durch:
E(m)= (c1,c2):=(g^k,mh^k)

Entschlüsselung durch:
D(c1,c2)=c2(c1)^(-a)

Ich habe mir einen Wolf gegoogelt und finde den ElGamal immer mit einem Tripel was den PublicKey bildet und keinem Tupel.
Bspw. hier: http://www.adeptscience.co.uk/products/ ... Gamal.html

Verstehe ich das einfach nur falsch?
Ich habe es so wie auf adeptscience implementiert und die Ver- und Entschlüsselung funktioniert problemlos.
Implementiere ich es jedoch wie in der Vorlesung, frage ich mich, wie wir die Potenzen effizient errechnen können?
In der Vorlesung haben wir lediglich ein Verfahren zur modulare Exponentiation gemacht.
Wie berechnet man nun den in der Vorlesung vorgestellten Public-Key (g^k, mh^k) in denen offensichtlich keine Modulo-Operationen vorkommen??
Wenn ich g^k berechnen lasse, kann ich meinen PC für 30 Minuten nicht mehr benutzen... :shock:

LG

L4_
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 104
Registriert: 24. Apr 2012 15:44

Re: ElGamal

Beitrag von L4_ »

Meine Vermutung:
Wir sind im Ring Z_p, d.h. wir rechen immer mod p. Daher wurde beim Ver- und Entschlüsseln zur besseren Lesbarkeit das "mod p" weggelassen.

Mit Kapitel 4, Folie 8 ist die in der Vorlesung behandelte effiziente Exponentiation gemeint.
0pa hat geschrieben:Wie berechnet man nun den in der Vorlesung vorgestellten Public-Key (g^k, mh^k) ...
(g^k, mh^k) ist kein Public Key - das ist das Chiffrat C = (c1, c2) ;)

Würde mich aber auch interessieren, ob in der Folie nicht ergänzt werden sollte, dass p zum Public Key dazugehört.
Beim Verschlüsseln brauch man "mod p" rein mathematisch gesehen eigentlich nicht, da beim entschlüsseln wieder "mod p" angewandt wird.
Jedoch würde die Nachricht sich beim Verschlüsseln ohne "mod p" vermutlich gewaltig aufblähen.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: ElGamal

Beitrag von JannikV »

Hi,

der Modul p gehört mit zum Public Key. Wurde auf den Folien so vergessen. Aber den braucht man nunmal, wenn man dann Berechnungen durchführen will (man muss ja wissen in welcher Gruppe).

Dazu und warum es immer eine Berechnung mod p ist (auch wenn es nicht dabei steht) habe ich hier was zu geschrieben: viewtopic.php?f=199&t=27078#p148439

VG

Antworten

Zurück zu „Archiv“