ElGamal, Generatorwahl < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:27 Mi 06.06.2012 | | Autor: | Iwanai |
Hallo zusammen,
bei der Berechnung des öffentlichen Schlüssels für die ElGamal-Verschlüsselung (auch Signierverfahren) werden nach der Bestimmung einer Primzahl $p$ zwei Zufallszahlen $g$ (Generator) und $x$ (privater Schlüssel) zufällig gewählt.
Unter der Annahme, dass $p$ genügend groß ist, sehe ich auf den ersten Blick keine Nachteile, wenn viele Anwendungen und Benutzer denselben $g$ verwenden, solange $g$ ein Generator von $p$ ist, denn [mm] $g^x$ [/mm] wäre aufgrund der Zufälligkeit von $x$ nicht vorhersagbar. Etwas anderes wäre, wenn [mm] $g^x$ [/mm] eine echte Untergruppe von $p$ generieren würde (mit einer (sehr) kleinen Ordnung).
Meine Fragen:
1) Welche Angriffsmöglichkeiten auf die ElGamal-Verschlüssel bestehen, wenn alle Benutzer denselben $g$ einsetzen?
2) Wie lässt sich die Tatsache ausnutzen, dass $g$ eine echte Untergruppe von $p$ (mit einer kleinen Ordnung) generiert?
3) Ermöglichen die beiden Faktoren effiziente Angriffe sowohl auf die ElGamal-Verschlüsselung als auch auf die ElGamal-Signatur, oder bestehen hier Unterschiede?
Vielen Dank im Voraus
Iwanai
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:03 So 10.06.2012 | | Autor: | felixf |
Moin!
> bei der Berechnung des öffentlichen Schlüssels für die
> ElGamal-Verschlüsselung (auch Signierverfahren) werden
> nach der Bestimmung einer Primzahl [mm]p[/mm] zwei Zufallszahlen [mm]g[/mm]
> (Generator) und [mm]x[/mm] (privater Schlüssel) zufällig
> gewählt.
>
> Unter der Annahme, dass [mm]p[/mm] genügend groß ist, sehe ich auf
> den ersten Blick keine Nachteile, wenn viele Anwendungen
> und Benutzer denselben [mm]g[/mm] verwenden, solange [mm]g[/mm] ein Generator
> von [mm]p[/mm] ist, denn [mm]g^x[/mm] wäre aufgrund der Zufälligkeit von [mm]x[/mm]
> nicht vorhersagbar. Etwas anderes wäre, wenn [mm]g^x[/mm] eine
> echte Untergruppe von [mm]p[/mm] generieren würde (mit einer (sehr)
> kleinen Ordnung).
>
>
> Meine Fragen:
>
> 1) Welche Angriffsmöglichkeiten auf die
> ElGamal-Verschlüssel bestehen, wenn alle Benutzer
> denselben [mm]g[/mm] einsetzen?
Ist das eine Frage, die du in einer Uebungsaufgabe beantworten sollst?
Ich wuerd einfach mal etwas mit google recherchieren. Weiterhin ist das Buch "Handbook of Applied Cryptography" komplett online einsehbar, dort ist moeglicherweise etwas dadrueber zu finden.
> 2) Wie lässt sich die Tatsache ausnutzen, dass [mm]g[/mm] eine
> echte Untergruppe von [mm]p[/mm] (mit einer kleinen Ordnung)
> generiert?
Wenn die Untergruppe sehr klein ist, z.B. nur aus 10 Elementen besteht, kann man diese alle hinschreiben und somit das DLP (Diskrete Logarithmus-Problem) sofort loesen. Bei mittelgrossen Untergruppengroessen kann man es schnell mit Algorithmen wie Pollard Rho oder Baby-Step Giant-Step loesen. Da die Sicherheit auf dem DLP basiert waere das fatal.
> 3) Ermöglichen die beiden Faktoren effiziente Angriffe
> sowohl auf die ElGamal-Verschlüsselung als auch auf die
> ElGamal-Signatur, oder bestehen hier Unterschiede?
Wenn du 1) und 2) beantwortet und verstanden hast, sollte das nicht schwer sein.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:00 Mo 11.06.2012 | | Autor: | Iwanai |
Danke Felix,
die Idee mit der kleinen Gruppenordnung hatte ich anfänglich auch. Nun scheint die Sicherheit des Verfahrens tatsächlich nicht von der Wahl des Generators abzuhängen. Der folgende Beitrag bestätigt dies mit dem Hinweis auf das "Applied Cryprography"-Buch: http://crypto.stackexchange.com/questions/639/does-the-generator-size-matter-in-diffie-hellman
Ich verstehe jedoch nicht, wie der Nachweis funktioniert: "When $p$ is a "safe prime", this means that [mm] $\frac{(p-1)}{2}$ [/mm] is also prime. We then define $q = [mm] \frac{(p-1)}{2}$. [/mm] In that situation, the order of any non-zero $g [mm] \bmod [/mm] p$ (except 1 and $p-1$) is either $q$ or $2q$, hence every $g$ between $2$ and $p-2$ (inclusive) is a fine DH generator and ensures optimal security. Therefore it is customary to select a $g$ which makes computations easier, usually $g = 2$ or $g = 3$."
Wieso geht man im Beweis von einer "sicheren Primzahl" aus? Dies ist imho nicht erforderlich. Vor allem verstehe ich nicht, wieso man hier $q$ einfach als $q = [mm] \frac{(p-1)}{2}$ [/mm] definiert. Vermutlich ist dies der Satz von Lagrange und der Knackpunkt des Beweises: Wenn $q$ im schlimmsten Fall die Hälfte von $p$ ist (alternativ: $2q$), dann wäre die Gruppenordnung bei einem beliebigen Generator nocht "groß genug".
Danke und Gruß
Iwanai
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:14 Mo 11.06.2012 | | Autor: | felixf |
Moin Iwanai!
> die Idee mit der kleinen Gruppenordnung hatte ich
> anfänglich auch. Nun scheint die Sicherheit des Verfahrens
> tatsächlich nicht von der Wahl des Generators abzuhängen.
Moment! Solange die erzeugte Untergruppe die gleiche bleibt, haengt es tatsaechlich nicht vom Generator ab. (Genau das besagt auch die Diskussion auf stackexchange.) Verschiedene Elemente aus [mm] $(\IZ/p\IZ)^\ast$ [/mm] erzeugen jedoch nicht notwendigerweise die gleiche Untergruppe.
> Der folgende Beitrag bestätigt dies mit dem Hinweis auf
> das "Applied Cryprography"-Buch:
> http://crypto.stackexchange.com/questions/639/does-the-generator-size-matter-in-diffie-hellman
>
> Ich verstehe jedoch nicht, wie der Nachweis funktioniert:
> "When [mm]p[/mm] is a "safe prime", this means that [mm]\frac{(p-1)}{2}[/mm]
> is also prime. We then define [mm]q = \frac{(p-1)}{2}[/mm]. In that
> situation, the order of any non-zero [mm]g \bmod p[/mm] (except 1
> and [mm]p-1[/mm]) is either [mm]q[/mm] or [mm]2q[/mm], hence every [mm]g[/mm] between [mm]2[/mm] and [mm]p-2[/mm]
> (inclusive) is a fine DH generator and ensures optimal
> security. Therefore it is customary to select a [mm]g[/mm] which
> makes computations easier, usually [mm]g = 2[/mm] or [mm]g = 3[/mm]."
>
> Wieso geht man im Beweis von einer "sicheren Primzahl" aus?
Die sorgen dafuer, dass es in [mm] $(\IZ/p\IZ)^\ast$ [/mm] eine Gruppe maximaler Primzahlordnung (im Vergleich zu $p$ selber) gibt.
Du kannst ja $p - 1$ immer schreiben als [mm] $\prod_{i=1}^n p_i^{k_i}$ [/mm] (Primfaktorzerlegung). Pohlig und Hellman haben gezeigt (Pohlig-Hellman-Algorithmus), dass das DLP in [mm] $(\IZ/p\IZ)^\ast$ [/mm] nur so schwer ist wie in einer Gruppe der Ordnung [mm] $p_i$ [/mm] fuer das groesste [mm] $p_i$ [/mm] (also braucht man hoechstens [mm] $\tilde{\mathcal{O}}(\sqrt{p_i})$ [/mm] Operationen). Hat also $p - 1$ nur kleine Primfaktoren [mm] $p_i$, [/mm] so ist das DLP in [mm] $(\IZ/p\IZ)^\ast$ [/mm] einfach.
Wenn $p$ eine safe prime ist, dann ist $n = 2$, [mm] $p_1 [/mm] = 2$, [mm] $k_1 [/mm] = 1$ und [mm] $k_2 [/mm] = 1$ und [mm] $p_2 [/mm] = [mm] \frac{p - 1}{2}$ [/mm] eine grosse Primzahl. Damit ist das DLP in [mm] $(\IZ/p\IZ)^\ast$ [/mm] schwer genug: mit Pohlig-Hellman kann man es nicht wesentlich schneller loesen als auf naive Weise (sprich: exponentielle Algorithmen wie Pollard-Rho doer BSGS) in [mm] $(\IZ/p\IZ)^\ast$. [/mm] Die schnellsten Algorithmen sind subexponentiell in [mm] $\log [/mm] p$ (aber eben in nichts kleinerem).
> Dies ist imho nicht erforderlich.
Ist es nicht. Man muss halt dafuer sorgen, dass $p - 1$ mindestens einen sehr grossen Primfaktor hat. Das ist bei einer safe prime halt erfuellt.
> Vor allem verstehe ich
> nicht, wieso man hier [mm]q[/mm] einfach als [mm]q = \frac{(p-1)}{2}[/mm]
> definiert.
Das ist der groesste Primteiler von $p - 1$.
> Vermutlich ist dies der Satz von Lagrange und
> der Knackpunkt des Beweises: Wenn [mm]q[/mm] im schlimmsten Fall die
> Hälfte von [mm]p[/mm] ist (alternativ: [mm]2q[/mm]), dann wäre die
> Gruppenordnung bei einem beliebigen Generator nocht "groß
> genug".
So in etwa.
Die Elemente in [mm] $(\IZ/p\IZ)^\ast$ [/mm] haben die Ordnungen 1, 2, q, 2q. Die Ordnung 1 hat nur das Element 1, die Ordnung 2 nur das Element $-1 [mm] \equiv [/mm] p - 1$. Jedes andere Element, also alle Restklassen der Elemente zwischen 2 und $p - 2$, haben Ordnung $q$ oder $2 q$. Und diese Ordnungen sind gross genug und mit Pohlig-Hellman kann man das DLP loesen nicht wirklich beschleunigen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:59 Mo 11.06.2012 | | Autor: | Iwanai |
Hallo Felix,
nochmals Danke für Deine Antwort und die Klarstellung.
Viele Grüße
Iwanai
|
|
|
|
