Diskussion:Elgamal-Verschlüsselungsverfahren/Archiv/1

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Elgamal-Verschlüsselungsverfahren/Archiv/1#Thema 1]]

oder als Weblink zur Verlinkung außerhalb der Wikipedia

https://de.wikipedia.org/wiki/Diskussion:Elgamal-Verschl%C3%BCsselungsverfahren/Archiv/1#Thema_1

Ohne Titel

und wie funktionierts?

Ich habe versucht die Funktionsweise kurz darzustellen. Ich hoffe es ist nicht zu mathematisch. Leider lässt sich das bei diesem Thema kaum verhindern. Wenn Ihr Fragen habt, meldet Euch einfach auf meiner Benutzerdiskussionsseite. Stern !? 19:29, 22. Okt 2004 (CEST)

Unterschied ElGamal <-> Diffie Hellman

Wo genau liegt denn nun der Unterschied zwischen ElGamal und DH? Irgendwie erscheint mir das im Endeffekt vollkommen gleich.. --84.56.173.70 09:56, 7. Dez. 2007 (CET)

DH ist ein Schluesselaustauschprotokoll (am Ende kommt ein Schluessel $g^{ab}$ raus), ElGamal eine Verschluesselung fuer eine Nachricht. Das bedeutet z.B. auch andere Sicherheitsmodelle (fuer ElGamal gibt es keinen Man-in-the-Middle-Angriff, weil der public key als zum Empfaenger gehoerend vorausgesetzt wird). --Mario d 21:32, 30. Nov. 2010 (CET)

Diskreter Logarithmus Falltürfunktion

Eine Falltürfunktion ist doch eine Einwegfunktion, wo man mit einem Trick die Rückrichtung vereinfachen kann. So etwas wird hier aber nicht genutzt. Ich wäre daher dafür das durch den schwächeren Begriff "Einwegfunktion" zu ersetzen.(nicht signierter Beitrag von 134.61.45.29 (Diskussion) 2008-02-14, 15:58:46 Uhr)

Dem schließe ich mich an. Denn so, wie der Text heute aussieht, ist es schlicht falsch, da der diskrete Logarithmus eine Einweg-Funktion ist - es gibt keine Falltür. (nicht signierter Beitrag von 85.178.173.110 (Diskussion | Beiträge) 16:30, 5. Mär. 2010 (CET))

Angriffsmöglichkeiten

Die Angriffsmöglichkeiten sollten eig. nicht unter Effizienz zu finden sein...(nicht signierter Beitrag von 87.123.160.246 (Diskussion) 2008-05-07, 07:57:05 Uhr)

Außerdem stimmt folgender Satz meines Erachtens nicht: "Wer das Elgamal-Kryptosystem brechen kann, der kann $g^{ab}\,{\bmod {\,}}p$ bestimmen." Andersrum ist die Aussage richtig - aber es ist durchaus auch im Bereich des Möglichen, Elgamal auf eine andere Weise zu brechen, die nicht gegen die DH-Annahme verstößt. (nicht signierter Beitrag von 85.180.75.129 (Diskussion) 11:50, 19. Jul 2010 (CEST))

Dass das nicht geht kann man beweisen: Die beiden Probleme sind aequivalent. Ich schreibe den beweis vielleicht schnell noch hin. --Mario d 21:29, 30. Nov. 2010 (CET)

Unterscheidung zwischen Signatur und Verschlüsselung

Elgamal-Verschlüsselung und Elgamal-Signatur sind zwei getrennte Verfahren, die deutlich verschieden voneinander sind, im Vergleich zu RSA-Veschlüsselung und RSA-Signatur. Sie haben nur ähnliche Namen, weil beide von der selben Person entwickelt wurden.

Ich denke, das sollte mindestens in der Einleitung klargemacht werden - besser vielleicht sollten beides eigene Artikel werden. -- Paul E. 23:41, 15. Nov. 2011 (CET)

Sei mutig! 78.52.242.253 23:43, 15. Nov. 2011 (CET)

das stimmt. ich denke, es waere am besten, die artikel in Elgamal-Verschlüsselung und Elgamal-Signatur zu trennen. --Mario d 13:13, 16. Nov. 2011 (CET)

Danke für die Ermunterung. Ich habe jetzt den Artikel Elgamal-Signatur angelegt, und dorthin die Signatur-bezogenen Abschnitte ausgelagert. Ich habe den Abschnitt zur Schlüsselerzeugung neugeschrieben, anstatt ihn zu kopieren, weil ich ihn hier weniger verständlich fand. Allerdings bin ich Mathematiker, und mir nicht ganz sicher, dass das jetzt noch allgemeinverständlich ist. Könnte da jemand drüberlesen? Falls es jetzt (oder nach einigen Bearbeitungen) besser ist, könnten wir ihn auch hierhin übernehmen. -- Paul E. 19:11, 16. Nov. 2011 (CET)

Allgemeines

Ich finde zum einen gehören die allgemeinen Texte zu Ver- und Entschlüsselung nicht in diesen Artikel. Die Beschreibung wie das funktioniert findet sich bereits unter Asymmetrisches Kryptosystem. In der konkreten Beschreibung eines Verfahrens eine allgemeine Definition zu wiederholen ist überflüssig und lenkt ab.

Zum anderen machen die inkonsistenten Variablenbenennungen es schwieriger zu verstehen. A, B, c, sind irgendwie einfach nur durchnummeriert und A und B sind gross, weil a und b schon belegt waren. Ein Vorschlag der sich fast mit dem Originalpaper deckt:

• Geheimer Schlüssel: $x$
• Öffentlicher Schlüssel: $(p,g,y)$ mit $y\equiv g^{x}\,{\bmod {\,}}p$

--

• Zum Verschlüsseln verwendet man dann ein zufälliges $k$ und erhählt durch $a\equiv g^{k}\,mod\,p$ und $b\equiv y^{k}m\,{\bmod {\,}}p$ das Chiffrat $(a,b)$
• Die Entschlüsselung ergibt sich dann mit $m\equiv (y^{k})^{-1}b\equiv b(g^{xk})^{-1}\equiv b((g^{k})^{x})^{-1}=b(a^{x})^{-1}\,{\bmod {\,}}p$ (was mir eh einleuchtender erscheint als die aktuelle Beschreibung) (nicht signierter Beitrag von 141.3.12.91 (Diskussion) 16:06, 17. Apr. 2012 (CEST))

ich denke auch, dass sich der artikel noch etwas straffen laesst. die variablenbenennung ist allerdings fast schon kanonisch, m fuer die nachricht (message), c fuer das chiffrat, g fuer den erzeuger und p=2q+1 sind sprechende variablennamen und werden durchgaengig verwendet. die bezeichnung A = g^a, B = g^b ist ebenfalls standard und deckt sich mit der beschreibung des eng verwandten diffie-hellman schluesselaustauschs und der standardnotation von CDH und DDH. --Mario d 16:29, 17. Apr. 2012 (CEST)

gegen m,c,p,q,g habe ich nichts, denn das ist tatsächlich Standard. Allerdings wird ja sogar das im Artikel falsch verwendet: hier ist c nicht mehr das Chiffrat, sondern Teil davon ($(B,c)$). Richtig wäre zum Beispiel $c=(a,b)$. Ich vermute A und B sind allenfalls Standard hier bei Wikipedia, was ja gerade mein Problem ist. Man liest Paper oder einschlägige Literatur, will es hier nochmal nachlesen und plötzlich sind alle Buchstaben vertauscht ;). Ich verstehe ehrlich gesagt überhaupt nicht, warum zum Beispiel bei CDH in der Literatur das Originalpaper zwar angegeben ist, jedoch im Artikel dann überall A und B statt X und Y aus eben diesem Originalpaper verwendet werden. (nicht signierter Beitrag von 141.3.12.91 (Diskussion) 18:02, 17. Apr. 2012 (CEST))

das original ist angegeben, weil es ein beleg ist. die notation die im artikel verwendet wird, wird verwendet, weil sie sinnvoll und standard ist. gibt es fuer x, y, k noch einen grund, ausser der verwendung im originalpapier? welche einschlaegige literatur hast du denn gelesen? --Mario d 22:48, 17. Apr. 2012 (CEST)

Wie ich bereits sagte, beschränkt sich der Standard ganz offensichtlich auf die deutsche Wikipedia. Auch, dass dieser "Standard" nichtmal in sich konsistent ist, hatte ich bereits dagelegt. Spontan kann ich dir als "einschlägige Literatur in der es so benannt ist" ISBN 978-0-262-03384-8 nennen, wobei mir mittelmäßig schleierhaft ist, warum dir nicht schon die Originalarbeiten ausreichen. Ich finde es schade, dass die deutsche Wikipedia nach 11-jährigem Bestehen oftmals, gerade für mathematische und technische Themen, keine sinnvolle Nachschlagemöglichkeit darstellt. Diese Diskussion zeigt mir gerade einen der Gründe warum das so ist. Da ich aber weder Zeit noch Lust habe gegen "wir machen das hier so, weil wir das hier so machen und deshalb ist es Standard" anzuargumentieren, klinke ich mich hiermit aus. (nicht signierter Beitrag von 141.3.12.91 (Diskussion) 14:10, 18. Apr. 2012 (CEST))

ganz offensichtlich hast du einfach keine ahnung, was standard ist. das paper von Elgamal ist 27 jahre alt, in der zeit hat sich einiges getan. "Introduction to algorithms" ist auch nicht unbedingt das referenzwerk, wenn es um krypto geht. das erste buch, was ich hier aus dem regal ziehe, ist Buchmanns "introduction to cryptography" und dort wird die gleiche notation verwendet wie hier im artikel. argumente fuer die notation habe ich dir bereits genannt: "die bezeichnung A = g^a, B = g^b ist ebenfalls standard und deckt sich mit der beschreibung des eng verwandten diffie-hellman schluesselaustauschs und der standardnotation von CDH und DDH." kleinbuchstaben fuer skalare und grossbuchstaben fuer gruppenelemente zu verwenden ist durchaus sinnvoll (ausser bei g und h, weil da die grossbuchstaben bereits belegt sind). dein einziges gegenargument war, dass du verwirrt bist, weil wir nicht die notation des originalartikels verwenden. tut mir leid, das reicht einfach nicht. egal welche notation wir verwenden, irgendjemand ist immer verwirrt. wenn du der deutschen WP aufgrund dieser notation absprichst, eine "sinnvolle Nachschlagemöglichkeit" zu sein, dann sagt das mehr ueber dich aus, als ueber die WP. nicht, dass sie es waere, aber das ist sicher nicht der grund. --Mario d 15:05, 18. Apr. 2012 (CEST)

Ich habe das Gefühl ich rede gegen eine Wand. Eigentlich wollte ich hier ja nichts mehr schreiben, aber das was du hier von dir gibst, kann man so einfach nicht stehen lassen: 1) ich habe mir jetzt mal 5 Minuten Zeit genommen und habe mich in der Bibliothek des KIT ein wenig umgesehen. Tatsächlich ist die in diesem (und in dem von CDH und DDH) Artikel verwendete Notation keineswegs Standard. 2) "dein einziges Gegenargument war, dass du verwirrt bist" und "sagt das mehr ueber dich aus...". Ganz davon abgesehen, dass beide Aussagen unwahr sind: entschuldige mal, aber was soll diese dumme Polemik? Ist das hier Gang und Gäbe auf diesem Niveau miteinander zu reden? Ich hoffe du bist in deiner akademischen Laufbahn schon so weit fortgeschritten, dass du dir eine solche Umgangsart erlauben kannst oder gehörst einfach nur zu den Leuten die der Meinung sind mit dem Einschalten des Bildschirms das gute Benehmen und den Anstand ausschalten zu können. Nichtsdestotrotz: Viel Spaß noch hier. (nicht signierter Beitrag von 141.3.12.91 (Diskussion) 15:42, 24. Apr. 2012 (CEST))

dein gefuehl kommt vermutlich daher, dass du dich standhaft weigerst, fundiert zu argumentieren. persoenliche angriffe vom kaliber "dumme Polemik" oder das absprechen guten benehmens habe ich stets vermieden. fuer den durch den satz "Man liest Paper oder einschlägige Literatur, will es hier nochmal nachlesen und plötzlich sind alle Buchstaben vertauscht" beschriebenen zustand halte ich "verwirrt sein" fuer eine durchaus uebliche bezeichnung und die guete eines artikels nach der verwendeten notation zu beurteilen finde ich immer noch abwegig. --Mario d 17:38, 24. Apr. 2012 (CEST)

Englische Übersetzung

Ich habe diesen Artikel ins Englische übersetzt. Es gab einige Fragen von en:User:Chris_Peikert über die Richtigkeit des alten Artikels im englischen, woher ein Kenner die Informationen zusammenmischen soll. Kann jemand von hier das anschauen? ElGamal discrete log cryptosystem. Danke. Mpolo 09:07, 22. Nov 2004 (CET)

Stimmt dies wirklich? "Zur Schlüsselerzeugung benötigt man eine Primzahl p, sodass p − 1 einen großen Primfaktor q besitz" Die Englische version behauptet nämlich nicht dass zur schluesselerzeugung wirklich primzahlen notwendig sind und ein kryptoexperte empfahl mir diesen algorythmus eben aus demselben grund.

ja, man braucht eine primzahl, und auch im englischen steht "Choose a random large prime p such that p − 1 = kq for some small integer k and large prime q.". 84.56.169.235 17:46, 23. Apr 2006 (CEST)

Nein, das stimmt so nicht ganz. Siehe auch meine Antwort unten im Abschnitt "Primzahl q". Für das korrekte Funktionieren des Verfahrens ist es zunächst einmal nur notwendig, dass man eine zyklische Gruppe ${\mathcal {G}}$ betrachtet und einen Erzeuger $g\in {\mathcal {G}}$ mit $\langle g\rangle ={\mathcal {G}}$ hat. Die Gruppe kann zunächst einmal völlig beliebig sein, solange sie zyklisch und endlich ist. Zum Beispiel auch die Gruppe von rationalen Punkte einer elliptischen Kurve. Das einfachste und anschauliche Beispiel für eine zyklische Gruppe ist natürlich die Einheitengruppe eines Zahlkörpers, also $\mathbb {Z} _{n}^{\times }$ mit $n=p^{m}$ und $p\in \mathbb {P} ,m\in \mathbb {N}$. Denn die Einheitengruppe von jedem endlichen Körper ist zyklisch und mehr braucht man nicht für das FUNKTIONIEREN des Verfahrens. $\mathbb {Z} _{17}^{\times }$ ist zum Beispiel eine ganz wunderbare Wahl, aber nicht empfehlenswert. (Es gilt nämlich leider $17-1=2^{4}$.)

Allerdings ist es für die SICHERHEIT des Verfahrens notwendig, dass die Gruppe möglichst nur in wenige und große Untergruppen zerfällt. Aus diesem Grund empfiehlt sich $\mathbb {Z} _{p^{m}}^{\times }$ nicht beliebig zu wählen, sondern nur $\mathbb {Z} _{p}^{\times }$ zu betrachten (d.h. $m=1$) und dabei auch nur solche $p$ zuzulassen, die $p-1=2q$ mit $q\in \mathbb {P}$ erfüllen. In diesem Fall hat nämlich $\mathbb {Z} _{p}^{\times }$ nur vier Untergruppen: die triviale Untergruppe $\lbrace 1\rbrace$, die ganze Gruppe und je eine Untergruppe von Ordnung $2$ und von Ordnung $q$. Dies trägt wesentlich zur Sicherheit bei.

Wählt man aber als zyklische Gruppe etwas ganz anderes, z.B. die bereits erwähnten rationalen Punkte einer elliptischen Kurve, so sieht die Welt schon wieder ganz ander aus. Hier gelten ganz andere Bedingungen, um möglichst sichere Gruppen zu bekommen. Leider krankt der ganze Artikel an dem Problem, dass die allgemeine Beschreibung des Verfahrens, das zum korrekten Funktionieren notwendig ist, vermischt wird mit einem konkreten Beispiel und für dieses konkrete Beispiel Bedingungen formuliert werden, ohne deutlich zu machen, dass diese Bedingung nur für das Beispiel und auch nur für die Sicherheit notwendig ist.

153.96.12.26 10:03, 6. Feb. 2014 (CET)Matthias

Primfaktor q

Im Artikel steht momemtan, dass man eine Primzahl $p$ so wählt, dass $p-1$ einen großen Primfaktor $q$ hat. Darauf wird aber nicht weiter eingegangen. Ich vermute, dass man irgendwo $\mod p$ geschrieben hat, wo $\mod q$ stehen müsste. Kann das jemand überprüfen?

Grüße, --Martin Thoma 11:09, 20. Jul. 2013 (CEST)

Nein, es ist richtig, dass überall $\mod p$ gerechnet wird. Der Wunsch nach $p-1=2q$ mit $q$ möglichst groß und prim, ist wichtig, damit dass Verfahren möglichst hohe Sicherheit bietet. Grundsätzlich würde das Verfahren auch korrekt funktionieren (d.h. Ver- und Entschlüsselung heben sich auf), wenn $p-1$ in viele kleine Primfaktoren zerfällt. Allerdings ist es dann nicht mehr so sicher. Leider wird dies im Artikel nicht explizit erwähnt.

Das dies nicht erwähnt wird, liegt aber an einer grunsätzlichen Schräche des Artikels. Das ElGamal-Verfahren funktioniert auf jeder endlich, zyklisch erzeugten Gruppe. Zum Beispiel auch auf Gruppen bestimmter Punkten über elliptischen Kurven. Dieser allgemeine Gruppenansatz wird im Artikel nur angedeutet, wenn davon geredet wird, dass $g$, $A$ und $B$ Gruppenelemente seien. Das Beispiel, was sich dann aber quer durch den Artikel zieht und quasi mit der allgemeinen Beschreibung vermischt ist, ist ein Beispiel für eine speziellen Typ von Gruppe, nämlich die zyklische Einheitengruppe eines Primzahlkörpers. Aber nur für diesen speziellen Gruppentyp ist die Bedingung $p-1=2q$ wichtig.

Jetzt die kurze Erklärung, warum die Sache unsicher wird, wenn man $p-1=2q$ nicht beachtet. Wählt man als Gruppe, die multiplikative Einheitengruppe $(\mathbb {Z} _{p})^{\times }$ so hat diese $n=p-1$ Elemente. Nach dem Hauptsatz über endliche abelsche Gruppen zerfällt aber jede Gruppe der Ordnung $n$ in die direkte Summe von Untergruppen mit Primzahlpotenz-Ordnung. Wählt man beispielsweise $p=13$, so hat $(\mathbb {Z} _{13})^{\times }$ 12 Elemente und es gilt $((\mathbb {Z} _{13})^{\times },\cdot )\equiv (\mathbb {Z} _{4},+)\times (\mathbb {Z} _{3},+)$. Das heißt, die Einheitengruppe zerfällt in zwei kleine Untergruppen und ein Angreifer könnte die Verschlüsselung auf den kleinen Untergruppen brechen. Wenn $p$ prim ist, ist $p-1$ zwangsläufig gerade. Das heißt, mit 2 als Primfaktor muss man irgendwie leben. Man will aber erreichen, dass der "Rest" möglichst nicht auch noch zerfällt, sondern groß bleibt. Das erreicht man natürlich am besten, wenn $p-1=2q$ mit $q$ prim gilt. In diesem Sinne ist $23$ eine gute Wahl wegen $23-1=2\cdot 11$, aber $29$ wegen $29-1=2^{2}\cdot 7$ eine schlechte Wahl. $29$ ist zwar größer als $23$, trotzdem ist die Gruppe $(\mathbb {Z} _{29})^{\times }$ schlechter, weil die größte Untergruppe nur $7$ Elemente hat, während bei $(\mathbb {Z} _{23})^{\times }$ die größte Untergruppe 11 Elemente hat.

FUNKTIONIEREN tun aber beide Gruppen. Bei elliptischen Kurven stellt sich dieses Problem zum Beispiel gar nicht.

Aus diesem Grund müsste man den Artikel eigentlich grundsätzlich neu strukturieren. Erst ein allgemeiner Abschnitt für jede Art von zyklischer Gruppe. Hier hat dann auch der Hinweis $p-1=2q$ nichts zu suchen, weil der für die korrekte Funktionweise überflüssig ist. Dann als zweites ein anschauliches Beispiel mit Einheitengruppen über Primzahlkörpern. Hier kann gerne das Beispiel aus dem Text genommen werden. Als drittes vielleicht ein Beispiel mit einer Gruppe über einer elliptischen Kurve. (Das wird allerdings unanschaulich.) Am Ende folgt dann der Hinweis, dass aus Gründen der Sicherheit darauf geachtet werden muss, dass die gewählte Gruppe nicht in kleine Untergruppen zerfallen sollte. Bei Einheitengruppen über Primzahlkörper kann dies dann mit der Bedingung $p-1=2q$ sichergestellt werden. Bei elliptischen Kurven gilt ähnliches, aber natürlich sind hierfür andere Bedingungen notwendig.

153.96.12.26 10:04, 6. Feb. 2014 (CET)Matthias

schoen, dass du dich fuer den artikel interessierst, es gibt auch einiges zu verbessern. ich wuerde allerdings den abschnitt, der die korrektheit des verfahrens von der sicherheit trennt, eher vor den abschnitt "schluesselerzeugung" packen. sicherheit ist ja eine zentrale eigenschaft des verfahrens, ich faende merkwuerdig, wenn sie erst am ende erwaehnt wird. dort wuerde ich auch kurz auf elliptische kurven eingehen - ein zweites, noch dazu unanschauliches, beispiel ist vielleicht nicht unbedingt noetig. --Mario d 15:12, 11. Feb. 2014 (CET)

Sophie-Germain-Primzahl und Primitivwurzeln

Im Text heißt es "Bei diesen Primzahlen p ist jede Zahl g im Bereich 1<g<p eine Primitivwurzel (manchmal auch Generator genannt) zu p, also eine Zahl deren Potenzen modulo p alle Zahlen in \{1, \ldots,p-1\} treffen.". Das ist falsch, wie man schon am Eintrag für Primitivwurzel am Beispiel p=7=2*3+1 sieht, wo 2 die Ordnung 3 hat und folglich keine Primitivwurzel sein kann (generell ist -1=p-1<p ein Element der Ordnung 2 und daher im Allgemeinen keine Primitivwurzel). Für Sophie-Germain-Primzahlen garantiert aber der Satz von Gauß (s. Primitivwurzel) bzw. kurze Überlegung die Existenz einer Primitivwurzel. Ich denke daher, dass es hier heißen muss: "Bei diesen Primzahlen p kann man eine Zahl g wählen, die Primitivwurzel modulo p ist." (nicht signierter Beitrag von 178.24.195.194 (Diskussion) 21:10, 15. Nov. 2013 (CET))

Ist mir auch grade aufgefallen. Tatsächlich ist (nach Primitivwurzel#Primitivwurzeln_modulo_Primzahlen) für Sophie-German-Primzahlen der Form $2q+1$ nicht nur die Existenz einer Primitivwurzel sicher, sondern die Existenz von $\varphi (\varphi (2q+1))=\varphi (2q)=\varphi (2)\varphi (q)=q-1$ Primitivwurzeln. Daher ist die Formulierung vom 3. Oktober 2013 wohl korrekt, die aktuelle auf keinen Fall. --109.192.195.45 01:08, 18. Feb. 2014 (CET)

Große Neuüberarbeitung

Wie hier als Antwort auf einige Nachfragen (siehe #Englische_Übersetzung und #Primfaktor_q) schon angeklungen und wie auf Benutzerseute von Stern und MarioS angekündigt, habe ich mich mal an die Neufassung gewagt:

1. Trennung von grundsätzlichen Verfahren und Beispiel
2. Abschnitt "Sicherheit" ausführlicher

• das Problem $p-1=2q$ sollte jetzt klarer sein

1. Elliptische Kurven mit aufgenommen

Ich habe mich jetzt erstmal nur um den Inhalt gekümmert. Ich hoffe, es sind nicht zuviele Rechtschreib-, Grammatik und Notationsfehler aufgetreten. --Nagmat84 (Diskussion) 13:01, 21. Feb. 2014 (CET)

ueberarbeitung

ich habe leider gerade nicht so viel zeit, mir sind bei der groben durchsicht drei dinge aufgefallen:

1. gibt es fuer die aenderung der variablenbenennung einen grund? ich bevorzuge sprechende variablennamen, ein standard ist bspw. A = g^a fuer den oeffentlichen schluessel, B = g^b oder R = g^r fuer das zufaellige element im chiffrat.
2. der satz "Für die Sicherheit des Verfahrens ist es unerheblich, ob jeder Empfänger "seine eigene" zyklische Gruppe nutzt oder ob alle Parteien mit der gleichen zyklischen Gruppe arbeiten." ist unbelegt und erscheint mir zweifelhaft, insbes. sagt das HAC, Note 8.24 dazu: "For common system-wide parameters (cf. Note 8.20) even larger key sizes may be warranted."
3. bei verwendung des gleichen zufalls gibt es einen ciphertext-only angriff, da A^b*m_1 / A^b*m_2 = m_1/m_2, woraus evtl. mit statistischer analyse die beiden klartexte gewonnen werden koennen. ich habe leider gerade keinen beleg zur hand. --Mario d 13:30, 21. Feb. 2014 (CET)

Antworten

Bis auf "Englische Überarbeitung" wollte ich hier den Rest gelöscht, weil sich die Kommentare eh auf die alte Version der Seite beziehen. Meine Intention dahinter war, dass ein Betrachter dieser Diskussionsseite nicht verwirrt würde aufgrund von Diskussionen zu Seiten Bestandteilen, die gar nicht mehr existieren. Das wurde von Benutzer:Astrofreund jedoch nicht so gerne gesehen (siehe Benutzer_Diskussion:Nagmat84). Egal, dass darf jetzt jemand anderes entscheiden. --Nagmat84 (Diskussion) 16:41, 21. Feb. 2014 (CET)

Jetzt aber zu den Fragen oben:

"Gibt es für die Änderung der Variablennennung einen Grund?"

Jein. Ich habe mir jetzt nicht die Mühe gemacht die Notation einer bestimmten Quelle zu nehmen, weil da jeder Autor eh seine eigene Notation hat. Ich habe diese Neuüberarbeitung ohne (konkrete) Vorlage geschrieben, sondern einfach so aufgeschrieben, wie es auch bei uns am Lehrstuhl unterrichtet wird. Abgesehen davon, jetzt kurz zur Systematik. Dass $G$ die Gruppe und $g$ den Erzeuger bezeichnet, ist - hoffe ich - Konsens. Außerdem ist die Bezeichnung $m$ für die Klartextnachricht (message) und $c$ für das Chiffrat (cipher) auch gängig. Insbesondere, wenn die Elemente aus veschiedenen Räumen stammen, hat man häufig die Bezeichnung $m\in M$ und $c\in C$. In unseren Fall gilt natürlich $M=C=G$. Insgesamt hat man dann aber schon mal drei Kleinbuchstaben $g$, $m$ und $c$ die allesamt Gruppenelemente sind. Ich fände es dann inkonsequent, wenn plötzlich für die Zwischenergebnisse bei den Gruppenelementen Großbuchstaben verwendet werden. Wofür diese zusätzliche Auszeichnung? Die Elemente $A$ und $B$ (früher) also $h$ bzw. $f$ (jetzt hier) sind doch nicht "besonderer" als $m$, $c$ und $g$. Insbesondere bleiben auf diese Weise Großbuchstaben für Mengen reserviert. Zur Buchstabenwahl: Da $g$ schon ein Gruppenelement bezeichnet (group) wurden $f$ und $h$ gewählt, weil sie in der Nähe liegen. Aus dem gleichen Grund wurden sukkzessiv $i$, $j$ und $k$ als Indizes verwendet.

Grundsätzlich ist natürlich Nomenklatur Schall und Rauch. Daran werde ich mich nicht aufhängen. Ich finde allerdings, dass Großbuchstaben für Elemente eine Assoziation an Mengen hervorruft, die eher verwirrt, weil sie falsch ist.

Ich schaue mal nachher in die Bücher, die wir in unseren Skripten als Nachschlagewerke angeben. Keine Ahnung, was dort üblich ist.--Nagmat84 (Diskussion) 16:41, 21. Feb. 2014 (CET)

"der satz 'Für die Sicherheit [...]' ist unbelegt und erscheint mir zweifelhaft"

Andersherum wird ein Schuh daraus. Die Sicherheitsgarantie von Elgamal basiert ausschließlich auf der Komplexität des diskreten Logarithmus. Die Hoffnung, eine möglichst "kreative" Gruppe zu nehmen, die nur der Emfänger selbst nutzt, birgt eher die Gefahr, dass die Gruppe unerkannte Strukturen offenbart, die einen Angriff erst möglich machen. Insbesondere gilt dies natürlich, wenn der Emfänger selbst die zusätzliche Struktur in der Gruppe noch nicht erkannt hat, der Angreifer aber diese Struktur schon ausnutzt.

Dies ist bei Elgamal über elliptischen Kurven Fluch und Segen zugleich gewesen.

Eines der wichtigen Kriterien ist, dass die zyklische Gruppe nicht in viele kleine Untergruppen zerfällt. Bei Einheitengruppen ist dies relativ einfach für jeden selbst über die Bedingung $p=2q+1$ zu kontrollieren. Deswegen wird hier die Gruppe auch vom Empfänger selbst als Teil seines öffentlichen Schlüssel selbst erzeugt. Bei elliptischen Kurven ist die Sache viel, viel komplizierter. Deswegen gibt es hier nur eine feste Auswahl von elliptischen Kurven, die von vielen Personen untersucht und als "gut" befunden wurden. Der Empfänger gibt dann nur an, welche elliptische Kurve er für seinen Schlüssel nutzt. Die als "gut" befundenen elliptischen Kurven haben feste Namen bekommen. Eine eigene elliptische Kurven zu generieren, birgt die Gefahr, dass diese unerkannterweise völlig trivial zerfällt. Das war aber leider zugleich der NSA-Angriff auf eine der elliptischen Kurven. Hier wurde eine elliptische Kurve von der NSA vorgeschlagen und von der NIST in den Standard aufgenommen, von der man mittlerweile vermutet, dass die NSA die Zerlegung in Untergruppen kennt. Diese Zerlegung wurde aber von keinem anderen bei der Standardisierung entdeckt. Ich müsste mal heraussuchen, welche Kurve das genau ist. Wenn ich Lust habe, schreibe ich auch noch etwas dazu im Artikel.

Nun zum Erzeuger bei Einheitengruppen. Auch hier ist in der konkreten Implementierung von Elgamal, wie es in Betriebssystemen, Browsern etc. eingesetzt wird, sogar festgeschrieben, dass als Erzeuger $3$, $7$ oder $65536=2^{1}6$ genommen werden soll. Grund hierfür ist, dass in der Binärdarstellung nur eine, zwei oder drei Einsen vorkommen. Deswegen ist die Ausführung auf x86/amd64/ia64-Architekturen besonders schnell, weil die Geschwindigkeit der Exponentation von der Anzahl der Einsen abhängt. (Hier geht es nur um die reale Laufzeit. Die theoretische Komplexität bleibt natürlich die gleiche.) Auch hier ist der Parameter also sogar festgeschrieben und wird nicht der Phantasie des Empfängers überlassen.

Grundsätzlich ist es sogar so, dass bei Elgamal über elliptische Kurven (mit nur einer kleinen Auswahl an elliptischen Kurven) die Schlüssellänge bei gleicher Sicherheit kürzer sein kann als bei Elgamal über Einheitengruppen, obwohl es bei den Einheitengruppen eine freiere Auswahl gibt. Die Einheitengruppen kann man als Menge in die natürlichen Zahlen einbetten und sich von dort eine Anordnung der Zahlen "ausleihen". Dann nutzt man den Baby-Step-Giant-Step-Algorithmus, um das Ziehen des diskreten Logarithmus zu beschleunigen. Es bleibt zwar nachwievor bei einer exponentiellen Laufzeit, man kann den Faktor aber deutlich nach unten drücken. Bei elliptischen Kurven fehlt diese Zusatzstruktur. Deswegen reichen hier kürzere Schlüssel. Auch hier zeigt sich wieder, dass gut untersuchte Gruppen sicherer sind. Schlecht untersuchte Gruppen können nämlich unangenehme Zusatzstrukturen offenbaren.--Nagmat84 (Diskussion) 16:41, 21. Feb. 2014 (CET)

"bei verwendung des gleichen zufalls gibt es einen ciphertext-only angriff, da A^b*m_1 / A^b*m_2 = m_1/m_2"

Da stehe ich gerade auf dem Schlauch, was Du meinen könntest.--Nagmat84 (Diskussion) 16:41, 21. Feb. 2014 (CET)

Ach so, jetzt weiß ich, worauf Du hinaus willst. (Deine Gleichung hatte ich schon vorher verstanden.) Aber den gleichen Zufall soll man ja auch gar nicht verwenden. Das steht ja schon im Artikel. Ob sich hieraus aber ein erfolgreicher Angriff bauen lässt, steht noch auf einem ganz anderen Blatt und hängt davon ab, ob man noch irgendwelche statistischen Aussahgen über die Gruppenelemente, die als Klartext vorkommmen, machen kann. In der Regel ist es ja so, dass man nicht Gruppenelemente verschlüsseln will, sondern bspw. irgendwelche Texte mit irgendeiner Codierung. Das heißt man hat natürlich Funktionen, die einem die eigentliche Nachricht auf Gruppenelemente abbildet und vice versa. Wenn diese Abbildung natürlich irgendwie dumm gemacht ist, kann dies ein Kryptoverfahren natürlich auch wieder zum Einseturz bringen. Für die ganzen Sicherheitsaussagen (IND-CPA, IND-CCA, IND-CCA2) geht man natürlich immer davon aus, dass man gleichverteilt ein Gruppenelement auswählt. (nicht signierter Beitrag von Nagmat84 (Diskussion | Beiträge) 2014-02-21, 17:57:04 Uhr)

1. das problem ist, dass sich eine halbe seite nach der beschreibung niemand mehr erinnert, was f jetzt fuer ein element war. die benennung a' = g^a wuerde dem prinzip "grossbuchstaben fuer mengen" folgen, aber ich finde, das ' stoert bei der exponentiation. aus diesem grund bevorzuge ich die "stanford-notation" (das wort ist meine erfindung, Dan Boneh und seine (ex-)studenten verwenden sie haeufig) mit grossbuchstaben fuer gruppenelemente und kleinbuchstaben fuer skalare und erzeuger. mengen koennen ja z.B. kursiv geschrieben werden. konseqenterweise koennte man dann auch M und C grossschreiben (g jedoch nicht).
2. hast du den link angeklickt und dir die begruendung durchgelesen (S. 296, 15 im pdf)? ich sehe nicht, wo du darauf eingehst. wir gehen davon aus, dass gruppen erzeugt werden, in denen DLOG schwer ist. wenn das der fall ist, geht dein argument fehl. wenn nicht, auch: denn dann ist nicht garantiert, dass die eine gruppe, die alle benutzen, sicher ist. mit kurven vs. koerper hat das erstmal nichts zu tun, sonder damit, dass bei gemeinsamer nutzung einer gruppe evtl. ein groesserer sicherheitsparameter gewaehlt werden muss.
3. wie nachrichten als gruppenelemente codiert werden, beeinflusst die sicherheit nicht. nachrichten werden bei IND-CPA etc. vom angreifer gewaehlt, sind also nicht gleichverteilt. tatsache ist, dass der angreifer in diesem fall m_1/m_2 gewinnen kann, was sicher nicht gut ist. --Mario d 14:47, 23. Feb. 2014 (CET)

ich habe den unbelegten satz jetzt entfernt. --Mario d 12:02, 8. Apr. 2014 (CEST)

Praktische Verständlichkeit?

Nachdem der Artikel jetzt überarbeitet ist, scheint er der Theorie nach jetzt ziemlich korrekt zu sein. Das Problem ist, das Ihn jetzt eigentlich nur noch jemand versteht, der sich intensiv mit dem Thema befasst hat und deshalb das Vefahren sowieso schon kennt. Ich habe mir die Coursera-Vorlesung von Dan Boneh angetan und weiß jetzt, wie ElGamal in der Praxis zu konstruieren ist, aber mit dem Artikel kann ich nicht wirklich was anfangen. Die Frage ist, ob das so der Sinn der Sache ist? Die internen Links helfen auch nicht wirklich weiter, da diese zu genauso theorifizierten, überaus umfangreichen Artikeln führen. Aus guter Erfahrung lasse ich aber die Finger davon hier irgendwas zu ändern was sowieso nicht bleibt. Ist nur schade, dass jemand, der ElGamal implementieren will, schlussendlich sich seine Informationen woanders her holen muss. Weiterhin fehlen die Hinweise auf die praktische Anwendung, dass das Verfahren dazu genutzt wird einen Schlüssel zu erzeugen, mit dem dann ein symmetrisches Verfahren benutzt wird - und der Hinweis, das - zumindest nach meinem Wissensstand bei der Verwendung mit Sophie-Germain-Primzahlen - diese mindestens 2048bit gross sein sollten. Also so ziemlich das, was in der Vorlesung und in den dazu gehörenden drei, vier Seiten Präsentation steht. Vielleicht bekommen die Praktiker doch mal noch eine Chance hier..? Stephan Brunker (Diskussion) 20:45, 20. Apr. 2014 (CEST)

dass sich jemand, der ElGamal implementieren will, seine infos woanders her holen muss, ist volle absicht. WP ist kein ratgeber (WP:WWNI). alleine auf grundlage eines WP-artikels ein kryptosystem zu implementieren ist gefaehrlich. um das zu verstehen, muss man einfach arbeit investieren und sich richtig informieren. der artikel beschreibt das verfahren, das ist das, was er leisten soll. die schluessellaenge koennte man evtl in den abschnitt "sicherheit" aufnehmen, fuer das hybride verfahren gibt es den artikel Elliptic Curve Integrated Encryption Scheme. --Mario d 10:22, 21. Apr. 2014 (CEST)

Nur, dass die Wikipedia hier mal wieder alles andere als konsistent ist. So steht in der englischen Version von Salsa20 zum Beispiel der Pseudocode der Rundenfunktionen drin. Meiner bescheidenen Meinung nach gehörten hier die paar Zeilen Pseudocode der ElGamal-Version wie sie Dan Boneh beschreibt hier rein ... nur wie gibt man eine Vorlesung als Quelle an? Damit wäre am Besten beschrieben, wie das Verfahren funktioniert, zumal bei einer ganzen Reihe von kryptografischen Verfahren der Pseudocode schön knackig kurz ist (wenn man mal von AES absieht ...). Und bei der Variante wird gar nicht erst das multiplikative Inverse gebildet, sondern beide Seiten berechnen g^b mod p und g^(a*b) mod p und benutzen den Hashwert daraus als Schlüssel für den nächsten Schritt. Stephan Brunker (Diskussion) 00:44, 22. Apr. 2014 (CEST)

ich habe mir die folien angeschaut und bin dagegen, das hier in den artikel zu uebernehmen. Boneh ist ein guter und die konstruktion, die er zeigt, ist interessant, aber es ist nicht die standardkonstruktion - das ist IES. die annahmen sind ebenfalls nichtstandard. hier sollten wir uns an die grundlagen halten, also das, was in lehrbuechern steht. --Mario d 12:19, 23. Apr. 2014 (CEST)

Es läuft immer wieder aufs gleiche heraus: Die Wikipedia bildet schlussendlich dass ab, was einzelne User mit etwas Rückhalt als andere und Hartnäckigkeit so haben wollen, ob das nun sinnvoll ist oder nicht. Dieser Artikel ist nämlich im Vergleich zu dem ursprünglichen Papier von ElGamal, was Verständlichkeit und Komplexität angebetrifft ein Schlag ins Gesicht und ich kann jedem nur raten, den Wiki-Artikel zu entsorgen und stattdessen mit dem originalen Quellenmaterial zu arbeiten, damit fährt man einfacher und besser. Und der Spruch "... das was in den Lehrbüchern steht" ist als Rechtfertigung sehr, sehr dünn. Denn wer schreibt wohl die Lehrbücher, wenn nicht die Wissenschaftler und Dozenten und da ist Dan Boneh genauso gut wie jeder andere auch. Und hier eine Quelle ohne belastbare Argumente über die andere zu stellen, halte ich dann doch für sehr fragwürdig, und die Tatsache, dass ein enzyklopädischer Eintrag zu einem Verfahren komplizierter ist als die originale Beschreibung des Verfahrens selbst, ist ganz sicher was Wikipedia nicht sein soll. Aber ich lass es jetzt endgültig bleiben hier Zeit und Mühe darauf zu verschwenden. Stephan Brunker (Diskussion) 12:33, 23. Apr. 2014 (CEST)

du vermischst jetzt zwei punkte. wenn du konkrete vorschlaege hast, wie der artikel lesbarer oder verstaendlicher gestaltet werden kann, bist du herzlich eingeladen, sie hier vorzustellen. was den inhalt angeht, so ist der bezug auf lehrbuecher genau das, was WP:Q vorgibt. --Mario d 19:58, 27. Apr. 2014 (CEST)

Nicht über Z_p^* IND-CPA sicher

Elgamal ist über der Gruppe Z_p^* nicht IND-CPA sicher. Man wählt für das IND-CPA-Experiment für die Nachrichten m₀, m₂ eine Quadratzahl und eine Nicht-Quadratzahl. Dadurch das man weiß, ob der öffentliche Schlüssel eine Quadratzahl ist, weiß man welche Nachricht verschlüsselt wurde.

Siehe Folie 19. https://cseweb.ucsd.edu/~mihir/papers/pkc-talk.pdf

Ist das korrekt? --77.6.137.219 22:39, 12. Jun. 2015 (CEST)

Entschlüsselung

Wäre $21^{-5}\cdot 20\equiv 21^{23-1-5>0}\cdot 20\ mod\ 23\,\equiv 8\ mod\ 23\,=m$ anstelle von $m\equiv 21^{23-1-5}\cdot 20\equiv 8\mod 23$ nicht ebenso richtig, aber verständlicher? Gruß, Peter -- 11:04, 4. Nov. 2016 (CET)
Ich nehme dieses Lemma von meiner Beobachtungsliste, bei Antwort bitte pingen: {{ping|Peter Gröbner}}. Danke, Peter Gröbner -- 11:30, 11. Jul. 2017 (CEST)

@Peter Gröbner: Ich glaube nicht, dass >0 im Exponenten das ganze lesbarer macht. Das ganze ist ja jetzt auch ohnehin übersichtlicher, da ich 23 - 1 (den Modulus - 1) durch 11 (die eigentliche Gruppenordnung ersetzt habe. (23-1 funktioniert weil alle vielfachen von 11 äquivalent sind, nicht weil 23 hier irgendetwas verloren hätte.) --Fiona Weber 01:39, 4. Sep. 2018 (CEST)

Danke für deine Antwort. Das Thema ist für mich allerdings schon so lange her, dass ich mich derzeit nicht nochmal einarbeiten möchte. Gruß, Peter Gröbner -- 07:11, 4. Sep. 2018 (CEST)

Überarbeitung

Ich habe jetzt mal angefangen den Artikel insgesammt zu überarbeiten. Es fehlen nach wie vor Eigenschaften die das Verfahren hat (siehe auch Kommentar im Quelltext) und an der Verständlichkeit müssten wir vermutlich auch nochmal arbeiten. (Wobei korrekt für's erste wichtiger als verständlich ist, insbesondere da alle wichtigen Fachbegriffe verlinkt sein sollten.) --Fiona Weber 01:41, 4. Sep. 2018 (CEST)