Diskussion:Elgamal-Verschlüsselungsverfahren

Letzter Kommentar: vor 3 Jahren von Fiona Weber in Abschnitt Probleme mit Untergruppen
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.
Archiv
Wie wird ein Archiv angelegt?

Wertebereiche

Bearbeiten

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   aus  . Dieses   wird lediglich als Exponent für   verwendet, welches wiederum eine Primitivwurzel modulo p der Ordnung   ist. Demnach gilt also  , ab   wiederholt sich also der Wert von   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   zu wählen. Aber das ist noch nicht das schlimmste. Indem man   erlaubt, lässt man den Fall zu, dass  , womit bei der Verschlüsselungsoperation praktisch der Klartext ausgegeben wird! Demnach müsste man also aus der Menge   wählen.

Bei der Verschlüsselung verhält es sich dann ähnlich. Zunächst einmal ist seltsamerweise für den zweiten Exponenten, also  , eine andere Wertemenge angegeben, als für  , nämlich  . Die Null ist hier also glücklicherweise schon nicht mehr enthalten, aber aus den selben Gründen wie oben sollte auch hier   stehen. Außerdem stört mich die Menge, die für den Klartext angegeben ist, nämlich  . Ich habe es jedenfalls so gelernt, dass   sein muss, also in der Menge der möglichen Potenzen von   modulo p liegen muss, womit es also q mögliche Werte für m gibt. Ich glaube, anderenfalls könnten zwei verschiedene Nachrichten   und   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  . (nicht signierter Beitrag von Litos (Diskussion | Beiträge) 2006-07-22, 00:28:35 Uhr)

Erzeugung von g

Bearbeiten

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

Bearbeiten

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

Bearbeiten

@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)Beantworten

Es wird ja bereits dort verwendet:  . 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)Beantworten
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)Beantworten

Probleme mit Untergruppen

Bearbeiten

"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)Beantworten

Da steht doch effektiv genau das was im Artikel steht?   hat Ordnung   und erfüllt daher die DDH-Annahme nicht. Die Untergruppe der Quadrate hat dagegen Ordnung   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   groß genug ist und keine Quantencomputer im Spiel sind. —Fiona Weber 17:04, 18. Mai 2021 (CEST)Beantworten