Diskussion:Elgamal-Signaturverfahren
Füge neue Diskussionsthemen unten an:
Klicke auf , um ein neues Diskussionsthema zu beginnen.hinweis zur versionsgeschichte (bitte stehenlassen)
[Quelltext bearbeiten]die beschreibung des verfahrens wurde aus dem artikel Elgamal-Kryptosystem kopiert. die versionsgeschichte wurde nachgetragen. --Mario d Diskussion:Elgamal-Signaturverfahren#c-MarioS-2011-11-21T20:55:00.000Z-hinweis zur versionsgeschichte (bitte stehenlassen)11
Inverses Element
[Quelltext 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) Diskussion:Elgamal-Signaturverfahren#c-Stephan Brunker-2013-12-25T16:44:00.000Z-Inverses Element11
- 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 Diskussion:Elgamal-Signaturverfahren#c-MarioS-2013-12-27T14:46:00.000Z-Stephan Brunker-2013-12-25T16:44:00.000Z11
Die Bedeutung der Primzahl q, großer Teiler von (p-1)?
[Quelltext 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 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-08-10T16:54:00.000Z-Die Bedeutung der Primzahl q, großer Teiler von (p-1)?11
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 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-08-29T19:14:00.000Z-Die Bedeutung der Primzahl q, großer Teiler von (p-1)?11
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 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-08-29T19:25:00.000Z-Die Bedeutung der Primzahl q, großer Teiler von (p-1)?11
Die Wahl von g - wann erzeugt g die Gruppe?
[Quelltext 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 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-08-11T08:59:00.000Z-Die Wahl von g - wann erzeugt g die Gruppe?11
- 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 Diskussion:Elgamal-Signaturverfahren#c-MarioS-2015-08-17T13:18:00.000Z-109.90.224.162-2015-08-11T08:59:00.000Z11
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 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-08-29T19:52:00.000Z-Die Wahl von g - wann erzeugt g die Gruppe?11
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 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-08-30T09:06:00.000Z-Die Wahl von g - wann erzeugt g die Gruppe?11
- 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 Diskussion:Elgamal-Signaturverfahren#c-MarioS-2015-08-30T10:20:00.000Z-109.90.224.162-2015-08-30T09:06:00.000Z11
- Zahlenkörpersieb ??? - Ich das nicht ein Faktorisierungsmethode? 109.90.224.162 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-08-30T16:36:00.000Z-MarioS-2015-08-30T10:20:00.000Z11
- 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 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-08-30T16:44:00.000Z-109.90.224.162-2015-08-30T16:36:00.000Z11
- Zahlenkörpersieb ??? - Ich das nicht ein Faktorisierungsmethode? 109.90.224.162 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-08-30T16:36:00.000Z-MarioS-2015-08-30T10:20:00.000Z11
- 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 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-08-30T16:48:00.000Z-109.90.224.162-2015-08-30T16:36:00.000Z11
- 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 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-08-30T17:23:00.000Z-MarioS-2015-08-30T10:20:00.000Z11
- 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 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-10-01T16:28:00.000Z-109.90.224.162-2015-08-30T17:23:00.000Z11
- Wir können die sichere Primzahl benutzen, das ist total sicher. 109.90.224.162 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-10-03T18:07:00.000Z-109.90.224.162-2015-10-01T16:28:00.000Z11
- 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 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-10-01T16:28:00.000Z-109.90.224.162-2015-08-30T17:23:00.000Z11
- 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 Diskussion:Elgamal-Signaturverfahren#c-109.90.224.162-2015-08-30T17:23:00.000Z-MarioS-2015-08-30T10:20:00.000Z11
das hier ist eine artikeldiskussionsseite. ich möchte dich bitte, nur fragen zu stellen, die direkt der verbesserung des artikels dienen. --Mario d Diskussion:Elgamal-Signaturverfahren#c-MarioS-2015-10-04T14:31:00.000Z-Die Wahl von g - wann erzeugt g die Gruppe?11
Selten eingesetzt
[Quelltext 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) Diskussion:Elgamal-Signaturverfahren#c-Aragorn2-2019-05-19T16:05:00.000Z-Selten eingesetzt11