Diskussion:Elgamal-Signaturverfahren

Diese Diskussionsseite dient dazu, Verbesserungen am Artikel „Elgamal-Signaturverfahren“ 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, und unterschreibe deinen Beitrag bitte mit oder --~~~~.

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

hinweis zur versionsgeschichte (bitte stehenlassen)

die beschreibung des verfahrens wurde aus dem artikel Elgamal-Kryptosystem kopiert. die versionsgeschichte wurde nachgetragen. --Mario d 21:55, 21. Nov. 2011 (CET)

Inverses Element

Ich habe die Bestimmung von $k^{-1}$ nachgetragen. Wer nicht schon ein Kryptologie-Spezialist ist (und deshalb diesen Artikel bestimmt nicht braucht), ist mit der Bestimmung des Modularen Multiplikativen Inversen nämlich erstmal überfordert. Die Formeln finden sich im Englischen Wikipedia-Artikel Modular multiplikative inverse. Eine deutsche Version mit den verwendeten Formeln gibt es hierzu noch nicht. Nach meinen bisherigen Wikipedia-Erfahrungen hoffe ich jetzt mal, das in dem Fall Einsetzen und Auflösen nicht schon als Theoriefindung gilt. Stephan Brunker (Diskussion) 17:44, 25. Dez. 2013 (CET)

die wahl p=2q+1 ist eine haeufige, aber nicht zwingend. ich wuerde eine allgemeinere formulierung bevorzugen. ausserdem brauchst du das inverse von k mod p-1, nicht mod p. ich habe deshalb revertiert. --Mario d 15:46, 27. Dez. 2013 (CET)

Die Bedeutung der Primzahl q, großer Teiler von (p-1)?

In die Berechnung der Signatur und bei der Verifikation wird die ominöse Primzahl q nicht benötigt. Welche Bedeutung hat sie? 109.90.224.162 18:54, 10. Aug. 2015 (CEST)

def nextStrongPrime(p):
 if p % 2 == 0:
   p = p + 1
 while (pow(2,p-1,p) != 1) or (pow(2,2*p,2*p+1) != 1):
    p = p + 2
 for k in range(3,20):
   if (k % p != 0) and  (pow(k,p-1,p) != 1 or pow(k,2*p,2*p+1) != 1):
     return nextStrongPrime(p + 2)
 return 2*p + 1

Aber ok, wenn es denn so sein soll. Bei Zahlen bis zu 200 Bit, können solche vermeintlich starken Primzahlen durchaus gefunden werden. 109.90.224.162 21:14, 29. Aug. 2015 (CEST)

Ich glaube nicht, dass es unbedingt nötig ist, aber es schadet sicher auch nicht. Bei diesen starken Primzahlen kann der Generator einer Untergruppe beliebig gewählt werden im offenen Interval (1,p-1), da die Untergruppe mindestens q = (p-1)/2 Zahlen umfasst. 109.90.224.162 21:25, 29. Aug. 2015 (CEST)

Die Wahl von g - wann erzeugt g die Gruppe?

Offensichtlich sollte

$g^{x}\equiv (mod\,p)$

alle möglichen Werte 1 bis (p-1) annehmen können für jeweils ein x aus [1, p-1].

Aber für g = 2, p = $2^{u}+1$ sind es aber nur u verschiedene Werte, viel zu wenig!

Nur wenn

$g^{\frac {p-1}{2}}\not \equiv 1(mod\,p)$

gilt, werden alle Werte angenommen. Dann ist das Verfahren sicher, bei hinreichend großem p (mindestns 200 Bit).

109.90.224.162 10:59, 11. Aug. 2015 (CEST)

richtig, die gruppe muss sorgfältig gewählt werden. die gruppe in deinem beispiel erfüllt die forderung aus dem artikel nicht, dass p=2q+1 mit q prim. bei endlichen körpern sollte q eher 2000 bit haben, vielleicht war das ein tippfehler. --Mario d 15:18, 17. Aug. 2015 (CEST)

Nein, die Komplexität der Berechnung des privaten Schlüssels aus dem öffentlichen ist von der Ordnung ${\sqrt {p}}$ und ist mit 100 Bit voll ausreichend, um eine praktische Berechung auszuschließen. 109.90.224.162 21:52, 29. Aug. 2015 (CEST)

Aber wie gesagt, wir können auch p als starke Primzahl mit 200 Bit wählen, so dass auch (p-1)/2 eine Primzahl ist, dann gibt es definitiv kein bekanntes, in der Literatur beschriebenes Verfahren mit Komplexität in Bit kleiner

$\log _{2}\left({\sqrt {\frac {p-1}{2}}}\right)>{\frac {1}{2}}\log _{2}\left({p}\right)-1$,

um den öffentlichen Schlüssel aus dem privaten zu berechnen, was praktisch nicht durchführbar ist. 109.90.224.162 11:06, 30. Aug. 2015 (CEST)

das ist nicht richtig. "On 11 June 2014, Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli and Emmanuel Thomé announced the computation of a discrete logarithm modulo a 180 digit (596-bit) safe prime using the number field sieve algorithm.", s. en:Discrete logarithm records. sqrt(p) ist die komplexität des besten generischen angriffs, der in bestimmten elliptischen kurven der beste bekannte angriff ist. in endlichen körpern wird ein zahlkörpersieb mit subexponentieller laufzeit verwendet. hier empfiehlt das BSI (für den allgemeineren fall p, q prim mit p=n*q+1): "Die Länge der Primzahl p sollte mindestens 2000 Bit [...] und die Länge der Primzahl q mindestens 224 Bit betragen. Für einen Einsatzzeitraum nach 2015 sollte q mindestens eine Bitlänge von 250 Bit besitzen". [1], S. 43 --Mario d 12:20, 30. Aug. 2015 (CEST)

Zahlenkörpersieb ??? - Ich das nicht ein Faktorisierungsmethode? 109.90.224.162 18:36, 30. Aug. 2015 (CEST)

Da kommt mir gerade ein Gedanke, wie wäre es ein RSA-Modul n = p*q mit 4096 Bit zu benutzen. Dann müssen n = p*q statt p und statt (p-1), $\phi =(p-1)(q-1)$ benutzen, wie bei RSA. Funktioniert sonst genauso. 109.90.224.162 18:44, 30. Aug. 2015 (CEST)

Wie bei RSA wird zur Prüfung der Signatur nur n, nicht p und q benötigt, die könnten geheim bleiben (Teil des privaten Schlüssel des Unterzeichners). 109.90.224.162 18:48, 30. Aug. 2015 (CEST)

Aber ich denke, das ist FUD, eine 200 Bit Primzahl und ein Generator g der gesamten Gruppe

$g^{\frac {p-1}{2}}\not \equiv 1(mod\,p)$

ist unknackbar. Das Verfahren ist ja schon etwa 40 Jahre öffentlich bekannt und bisher mir ist nicht bekannt, dass es nachweislich geknackt wurde. Ich erwarte dies auch in Zukunft nicht. 109.90.224.162 19:23, 30. Aug. 2015 (CEST)

Uups - es geht doch - mit einer 600 Bit Safe Prime wurde der Diskrete Logarithmus offenbar schon geknackt, vermutlich mit dem Index-Calculus-Algorithmus. 109.90.224.162 18:28, 1. Okt. 2015 (CEST)

Wir können die sichere Primzahl $p=2(2052522967+2^{2000})+1$ benutzen, das ist total sicher. 109.90.224.162 20:07, 3. Okt. 2015 (CEST)

das hier ist eine artikeldiskussionsseite. ich möchte dich bitte, nur fragen zu stellen, die direkt der verbesserung des artikels dienen. --Mario d 16:31, 4. Okt. 2015 (CEST)

Selten eingesetzt

Ich habe einen Hinweis darauf eingefügt, dass das originale ElGamal-Signaturverfahren nur selten benutzt wird (mit belegendem Hinweis auf SSL/TLS). Allerdings müsste man vielleicht fairerweise dazusagen, dass die genannten Nachteile (hoher Rechenaufwand, große Signaturen) auch auf RSA zutreffen, was aber durchaus weite Verbreitung fand, u.a. in SSL/TLS, SSH, PGP und dessen Derivaten. Übrigens: PGP benutzte ebenfalls nie das ElGamal-Signaturverfahren (sondern nur das ElGamal-Verschlüsselungsverfahren). Aragorn2 (Diskussion) 18:05, 19. Mai 2019 (CEST)