Diskussion:Elgamal-Signaturverfahren

Letzter Kommentar: vor 5 Jahren von Aragorn2 in Abschnitt Selten eingesetzt
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.

hinweis zur versionsgeschichte (bitte stehenlassen)

Bearbeiten

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

Inverses Element

Bearbeiten

Ich habe die Bestimmung von   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)Beantworten

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

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

Bearbeiten

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

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

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

Die Wahl von g - wann erzeugt g die Gruppe?

Bearbeiten

Offensichtlich sollte

 

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 =   sind es aber nur u verschiedene Werte, viel zu wenig!

Nur wenn

 

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

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

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

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

 ,

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

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)Beantworten
Zahlenkörpersieb ??? - Ich das nicht ein Faktorisierungsmethode? 109.90.224.162 18:36, 30. Aug. 2015 (CEST)Beantworten
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),   benutzen, wie bei RSA. Funktioniert sonst genauso. 109.90.224.162 18:44, 30. Aug. 2015 (CEST)Beantworten
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)Beantworten
Aber ich denke, das ist FUD, eine 200 Bit Primzahl und ein Generator g der gesamten Gruppe
 
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)Beantworten
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)Beantworten
Wir können die sichere Primzahl   benutzen, das ist total sicher. 109.90.224.162 20:07, 3. Okt. 2015 (CEST)Beantworten

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

Selten eingesetzt

Bearbeiten

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