Diskussion:Elgamal-Verschlüsselungsverfahren

Diese Diskussionsseite dient dazu, Verbesserungen am Artikel „Elgamal-Verschlüsselungsverfahren“ zu besprechen. Persönliche Betrachtungen zum Thema gehören nicht hierher. Für allgemeine Wissensfragen gibt es die Auskunft.

Füge neue Diskussionsthemen unten an:

Klicke auf Abschnitt hinzufügen, um ein neues Diskussionsthema zu beginnen.

• Diskussionsregeln
• Hilfe zu Diskussionsseiten
• Sei sachlich und freundlich!
• Greife niemanden persönlich an!
• Geh von guten Absichten aus.

Automatische Archivierung

Auf dieser Seite werden Abschnitte automatisch archiviert, deren jüngster Beitrag mehr als 150 Tage zurückliegt und die mindestens einen signierten Beitrag enthalten. Um die Diskussionsseite nicht komplett zu leeren, verbleiben mindestens 5 Abschnitte.

Archiv

Archiv

Wie wird ein Archiv angelegt?

Wertebereiche

Also entweder bin ich jetzt völlig durcheinander, oder mit den Wertebereichen im Artikel stimmt etwas nicht.

Die erste Ungereimtheit ist bei der Schlüsselerzeugung: Man wählt ein $a$ aus $\{0,...,p-2\}$. Dieses $a$ wird lediglich als Exponent für $g$ verwendet, welches wiederum eine Primitivwurzel modulo p der Ordnung $q$ ist. Demnach gilt also $g^{q}=1$, ab $a=q$ wiederholt sich also der Wert von $g^{a}$ immer wieder. Anders ausgedrückt, durch Potenzieren von g modulo p kann man nur q verschiedene Werte bekommen. Es ist also völlig unsinnig, ein $a>q$ zu wählen. Aber das ist noch nicht das schlimmste. Indem man $a=0$ erlaubt, lässt man den Fall zu, dass $g^{a}=1$, womit bei der Verschlüsselungsoperation praktisch der Klartext ausgegeben wird! Demnach müsste man also aus der Menge $\{1,...,q-1\}$ wählen.

Bei der Verschlüsselung verhält es sich dann ähnlich. Zunächst einmal ist seltsamerweise für den zweiten Exponenten, also $b$, eine andere Wertemenge angegeben, als für $a$, nämlich $\{1,...,p-2\}$. Die Null ist hier also glücklicherweise schon nicht mehr enthalten, aber aus den selben Gründen wie oben sollte auch hier $\{1,...,q-1\}$ stehen. Außerdem stört mich die Menge, die für den Klartext angegeben ist, nämlich $\{0,...,p-1\}$. Ich habe es jedenfalls so gelernt, dass $m\in <g>$ sein muss, also in der Menge der möglichen Potenzen von $g$ modulo p liegen muss, womit es also q mögliche Werte für m gibt. Ich glaube, anderenfalls könnten zwei verschiedene Nachrichten $m_{1}$ und $m_{2}$ existieren, die mit dem selben Schlüssel die gleiche Verschlüsselung haben, was ein Entschlüsseln unmöglich macht. In diesem Fall bin ich mir aber nicht hundertprozentig sicher - ich weiß nur, dass ich es so gelernt habe, dass $m\in <g>$. (nicht signierter Beitrag von Litos (Diskussion | Beiträge) 2006-07-22, 00:28:35 Uhr)

Erzeugung von g

In der Wiki steht dass die Primitivwurzel g die Ordnung q haben muss. Kann g aber nicht auch die Ordnung p-1 haben(ist dann auch sicherer). Dann würde nämlich der Klartext m wieder aus der Menge {0,...,p − 1} gewählt werden können.(nicht signierter Beitrag von 217.229.250.167 (Diskussion) 2006-12-07, 16:27:43 Uhr)

• Nach dem "kleinen Fermat": für jedes z aus {0,...,p} (p=primzahl) gilt: z^(p-1) mod p = 1 mod p. Das wäre nicht so gut ;)(nicht signierter Beitrag von 83.135.197.113 (Diskussion) 2007-04-25, 13:53:37 Uhr)

weitere Eigenschaften

Im Artikel sollten noch weitere Eigenschaften von ElGamal erwähnt werden. Ich schreibe das hier nur Stichwortartig auf und bin mir vor allem bei letzterem Punkt nicht sicher, ob das richtig von mir verstanden und übersetzt wurde. Wäre schön wenn das jemand fachlich kompetentes mal sichten würde und dann in den Artikel einarbeitet.

• ElGamal ist probabilistisch, d.h. wenn man eine Nachricht zu verschiedenen Zeitpunkten verschlüsselt führt sie nicht zu demselben Chiffrat
• ElGamal ist "schmiedbar" (im engl. malleable, Siehe engl. Wikipedia) d.h. modifizierbar: Man kann aus einem Chiffrat ein anderes formen und somit ein fortlaufendes, bekanntes Feld von Chiffraten gezielt manupulieren.(nicht signierter Beitrag von 83.135.199.170 (Diskussion) 2007-08-17, 13:04:53 Uhr)

Vereinfachung Entschlüsselung

@Fiona Weber, du hast in Versionsunterschied die Erklärung der Vereinfachung entfernt mit den Worten: „Dass man dazu ^(phi(p)) rechnet ist ein Implementierungsdetail, dass in den Beispielabschnitt gehört (und dort ja auch verwendet wird).“ Soweit okay, aber dann ändere es bitte auch im Beispielabschnitt/füge es hinzu, und revertiere nicht nur die Änderung. Danke. --rugk (Diskussion) 21:13, 7. Jul. 2019 (CEST)

Es wird ja bereits dort verwendet: $13^{-5}\cdot 9\equiv 13^{11-5}\cdot 9$. Aber gut, vielleicht könnte man das auch noch im Text erwähnen. Ich Überlege mir mal was. Viele Grüße, --Fiona Weber 22:55, 7. Jul. 2019 (CEST)

Danke, so wie jetzt geändert ist das doch gut erklärt. Dann wäre das hier erledigtErledigt. --rugk (Diskussion) 23:11, 7. Jul. 2019 (CEST)

Probleme mit Untergruppen

"dass die Ordnung q {\displaystyle q} q von G {\displaystyle \mathbb {G} } {\mathbb {G}} prim ist, so dass die triviale Gruppe die einzige echte Untergruppe von G {\displaystyle \mathbb {G} } {\mathbb {G}} ist. Ist dem nicht so, kann dies fatale Folgen haben:"

Stimmt meines erachtens nicht. Quelle: https://web.engr.oregonstate.edu/~rosulekm/crypto/ (S. 258, "For Which Groups does the DDH Assumption Hold?")

Allerdings möchte ich meinen Einwand bestätigt bekommen, bevor ich editiere. --Cafntown (Diskussion) 18:41, 23. Jan. 2021 (CET)

Da steht doch effektiv genau das was im Artikel steht? $\mathbb {Z} _{p}^{\times }$ hat Ordnung $p-1$ und erfüllt daher die DDH-Annahme nicht. Die Untergruppe der Quadrate hat dagegen Ordnung ${\textstyle {\frac {p-1}{2}}}$ was bei geeigneter Wahl von 𝑝 prim ist und die DDH-Annahme (vermutlich) erfüllt. Im Artikel wir diese Untergruppe dann als 𝔾 verwendet was nach aktuellem Stand der Forschung sicher ist, solange $p$ groß genug ist und keine Quantencomputer im Spiel sind. —Fiona Weber 17:04, 18. Mai 2021 (CEST)