Index Calculus Algorithmus < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:11 Sa 06.08.2011 | | Autor: | Hanz |
Hallo,
ich beschäftige mich gerade mit dem Index-Calculus-Verfahren
(siehe http://parsys.informatik.uni-oldenburg.de/~best/kryptographie/kry-skript-kap6b.pdf (Seite 8f.) )
Nun arbeitet dieser Algorithmus ja in der Gruppe [mm] \mathbb Z_p^{\times}, [/mm] p Primzahl. Warum arbeitet er eigtl. nur in dieser Gruppe?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:24 Sa 06.08.2011 | | Autor: | felixf |
Moin!
> ich beschäftige mich gerade mit dem
> Index-Calculus-Verfahren
>
> (siehe
> http://parsys.informatik.uni-oldenburg.de/~best/kryptographie/kry-skript-kap6b.pdf
> (Seite 8f.) )
>
> Nun arbeitet dieser Algorithmus ja in der Gruppe [mm]\mathbb Z_p^{\times},[/mm]
> p Primzahl. Warum arbeitet er eigtl. nur in dieser Gruppe?
Der Einfachkeit halber 
Allgemein kannst du den Algorithmus in allen Gruppen $G$ machen, wo du folgende Eigenschaften hast:
* es gibt effektiv bestimmbare Elemente [mm] $p_1, \dots, p_n$
[/mm]
* ein beliebiges Element $g [mm] \in [/mm] G$ laesst sich mit einer bestimmten, nicht verschwindenen Wahrscheinlichkeit effektiv darstellen als $g = [mm] \prod_{i=1}^n p_i^{e_i}$ [/mm] mit [mm] $e_i \in \IZ$
[/mm]
Dabei sollte $n$ polynomiell (oder subexponentiell) in [mm] $\log [/mm] |G|$ sein und wenn $p$ die Wahrscheinlichkeit aus dem zweiten Punkt ist, dann sollte [mm] $\frac{1}{p}$ [/mm] subexponentiell in [mm] $\log [/mm] |G|$ sein. In dem Fall muesste der Algorithmus in subexponentieller Zeit laufen.
Solche Gruppen kennt man allerdings nicht so viele. Beispiele sind [mm] $\IZ_p^\ast$, $\IZ_n^\ast$, $(\IZ_p[x]/(f))^\ast$ [/mm] (die multiplikative Gruppe eines endlichen Koerpers, der durch das irreduzible Polynom $f$ ueber [mm] $\IZ_p$ [/mm] konstruiert wurde).
Man kann das auch in der Divisorklassengruppe von (hyperelliptischen) Funktionenkoerpern anwenden (es ist dann subexponentiell, wenn das Geschlecht gegen unendlich geht - deswegen hilft das ganze auch bei elliptischen Kurven nichts, da das Geschlecht dort 1 ist) oder in der Idealklassengruppe/Infrastruktur von Zahlkoerpern. Dazu braucht man aber "etwas" mehr Theorie in dieser Hinsicht.
Andere bekannte Anwendungsfaelle gibt es meines Wissens nicht. Da ein Grossteil der bekannten Anwendungsfaelle zu kompliziert ist, beschraenkt sich das Skript halt auf einen sehr einfachen Fall: $G = [mm] \IZ_p^\ast$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:25 So 07.08.2011 | | Autor: | Hanz |
Danke erstmal für die sehr sehr ausführliche Antwort!!!
Ich dachte nämlich, dass es nur für [mm] \mathbb Z_p^{\times} [/mm] gilt, weil ich auch in einer anderen Quelle, wo Algorithmen zur Berechnung von diskreten Logarithmen kategorisiert wurden und da stand eben:
"Special algorithms that exploit the representation of the group elements and thus work only in the group they were designed for. The index calculus algorithm for [mm] \mathbb Z_p^{\times} [/mm] is an example."
Die Quelle ist allerdings von 1998, kann es sein, dass der Algorithmus für [mm] \mathbb Z_p^{\times} [/mm] entwickelt wurde und man erst später "gemerkt" hat, dass er sich auch auf andere Gruppen ausweiten lässt?
> Allgemein kannst du den Algorithmus in allen Gruppen [mm]G[/mm]
> machen, wo du folgende Eigenschaften hast:
> * es gibt effektiv bestimmbare Elemente [mm]p_1, \dots, p_n[/mm]
>
> * ein beliebiges Element [mm]g \in G[/mm] laesst sich mit einer
> bestimmten, nicht verschwindenen Wahrscheinlichkeit
> effektiv darstellen als [mm]g = \prod_{i=1}^n p_i^{e_i}[/mm] mit [mm]e_i \in \IZ[/mm]
Das heißt doch im Prinzip, dass eine eindeutige Primfaktorzerlegung möglich sein muss, oder?
> Solche Gruppen kennt man allerdings nicht so viele.
> Beispiele sind [mm]\IZ_p^\ast[/mm], [mm]\IZ_n^\ast[/mm], [mm](\IZ_p[x]/(f))^\ast[/mm]
> (die multiplikative Gruppe eines endlichen Koerpers, der
> durch das irreduzible Polynom [mm]f[/mm] ueber [mm]\IZ_p[/mm] konstruiert
> wurde).
Meinst du mit [mm] \mathbb Z_n^{\times} [/mm] eine multiplikative Gruppe, wo n beliebig sein kann, z.B. n=38? Bin grad am überlegen, was dann genau den Unterschied zwischen [mm] \mathbb Z_n^{\times} [/mm] und [mm] \mathbb Z_p^{\times} [/mm] ausmachen würde im Algorithmus... es müsste ja am finden der Relationen liegen...
Ich hätte da noch eine Frage zum Pohlig-Hellman-Algorithmus in Bezug auf die Realität. Ich lese immer wieder, dass dieser Algorithmus nur effizient arbeitet, wenn die Primfaktoren der Gruppenordnung einer gegebenen Gruppe möglichst klein sind. Für große Primteiler wird er ineffizient. Was heißt eigtl. "großer Primteiler"? Wie großt ist so eine Zahl in der Realität etwa? Andererseits muss bei kryptographischen Verfahren mind. ein Primteiler genügend groß sein, damit das DLP in dieser Gruppe schwer zu lösen, um Sicherheit garantieren zu können. Das heißt doch im Prinzip, dass der Pohlig-Hellman-Algorithmus in der Realität keinen Einsatz findet, oder irre ich mich jetzt?
Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:46 So 07.08.2011 | | Autor: | felixf |
Moin,
> Danke erstmal für die sehr sehr ausführliche Antwort!!!
>
> Ich dachte nämlich, dass es nur für [mm]\mathbb Z_p^{\times}[/mm]
> gilt, weil ich auch in einer anderen Quelle, wo Algorithmen
> zur Berechnung von diskreten Logarithmen kategorisiert
> wurden und da stand eben:
>
> "Special algorithms that exploit the representation of the
> group elements and thus work only in the group they were
> designed for. The index calculus algorithm for [mm]\mathbb Z_p^{\times}[/mm]
> is an example."
>
> Die Quelle ist allerdings von 1998, kann es sein, dass der
> Algorithmus für [mm]\mathbb Z_p^{\times}[/mm] entwickelt wurde und
> man erst später "gemerkt" hat, dass er sich auch auf
> andere Gruppen ausweiten lässt?
also 1998 war auch schon bekannt, dass man den Algorithmus z.B. auch auf [mm] $\IF_q^\ast$ [/mm] anwenden kann fuer $q$ eine Primzahlpotenz. Warum die Quelle hier nur [mm] $\IZ_p^\ast$ [/mm] nennt weiss ich nicht, sie haette zumindest von [mm] $\IF_q^\ast$ [/mm] (oder [mm] $GF(q)^\times$, [/mm] wenn dir die Notation lieber ist) reden koennen.
> > Allgemein kannst du den Algorithmus in allen Gruppen [mm]G[/mm]
> > machen, wo du folgende Eigenschaften hast:
> > * es gibt effektiv bestimmbare Elemente [mm]p_1, \dots, p_n[/mm]
>
> >
> > * ein beliebiges Element [mm]g \in G[/mm] laesst sich mit einer
> > bestimmten, nicht verschwindenen Wahrscheinlichkeit
> > effektiv darstellen als [mm]g = \prod_{i=1}^n p_i^{e_i}[/mm] mit [mm]e_i \in \IZ[/mm]
>
> Das heißt doch im Prinzip, dass eine eindeutige
> Primfaktorzerlegung möglich sein muss, oder?
Nein, auch wenn das meist trotzdem der Fall ist. Es reicht aus, wenn es irgendwelche [mm] $p_i$ [/mm] gibt, so dass du effektiv mit gewisser Wahrscheinlichkeit irgendeine solche Zerlegung finden kannst.
> > Solche Gruppen kennt man allerdings nicht so viele.
> > Beispiele sind [mm]\IZ_p^\ast[/mm], [mm]\IZ_n^\ast[/mm], [mm](\IZ_p[x]/(f))^\ast[/mm]
> > (die multiplikative Gruppe eines endlichen Koerpers, der
> > durch das irreduzible Polynom [mm]f[/mm] ueber [mm]\IZ_p[/mm] konstruiert
> > wurde).
>
> Meinst du mit [mm]\mathbb Z_n^{\times}[/mm] eine multiplikative
> Gruppe, wo n beliebig sein kann, z.B. n=38?
Genau.
Die Grund-Idee, also das Relationen sammeln, wird z.B. auch beim Faktorisieren verwendet; dort arbeitet man dann in [mm] $\IZ_n^\ast$ [/mm] und das Ziel ist, $x, y$ zu finden mit $x [mm] \not\equiv \pm [/mm] y [mm] \pmod{n}$ [/mm] und [mm] $x^2 \equiv y^2 \pmod{n}$. [/mm] Ein solches Paar $x, y$ liefert mit $ggT(x - y, n)$ sofort einen nicht-trivialen Faktor von $n$. Wenn man genuegend solche Relationen wie beim Index Calculus hat, kann man mit Linearer Algebra ueber [mm] $\IZ_2$ [/mm] daraus $x$ und $y$ konstruieren, die mit Wahrscheinlichkeit [mm] $\ge \frac{1}{2}$ [/mm] die Bedingung $x [mm] \not\equiv \pm [/mm] y$ erfuellen.
> Bin grad am
> überlegen, was dann genau den Unterschied zwischen [mm]\mathbb Z_n^{\times}[/mm]
> und [mm]\mathbb Z_p^{\times}[/mm] ausmachen würde im Algorithmus...
Ich glaube, es macht kaum einen Unterschied. Ausser das man zufaellig auf Faktoren von $n$ stossen kann, mit denen man [mm] $\IZ_n$ [/mm] als Produkt von Ringen schreiben kann und das DLP jeweils in den Faktoren loesen kann -- dort ist es wesentlich einfacher. (Allgemein ist es vermutlich schneller, erst $n$ zu faktorisieren und dann das DLP in [mm] $\IZ_p^\ast$ [/mm] zu loesen fuer Primfaktoren $p$ von $n$.)
> es müsste ja am finden der Relationen liegen...
>
>
> Ich hätte da noch eine Frage zum
> Pohlig-Hellman-Algorithmus in Bezug auf die Realität. Ich
> lese immer wieder, dass dieser Algorithmus nur effizient
> arbeitet, wenn die Primfaktoren der Gruppenordnung einer
> gegebenen Gruppe möglichst klein sind. Für große
> Primteiler wird er ineffizient. Was heißt eigtl. "großer
> Primteiler"? Wie großt ist so eine Zahl in der Realität
> etwa?
In etwa von der Groesse [mm] $2^{160}$ [/mm] oder groesser. Dann braucht man ca. [mm] $2^{80}$ [/mm] Operationen mit einer generischen Methode (Pollard rho, Baby Step Giant Step).
(Wenn man in [mm] $\IF_q^\ast$ [/mm] oder so rechnet, muss man natuerlich eine viel groessere Gruppenordnung $q - 1$ haben, da Index Calculus schneller als die oben genannten square-root-Methoden ist.)
> Andererseits muss bei kryptographischen Verfahren
> mind. ein Primteiler genügend groß sein, damit das DLP in
> dieser Gruppe schwer zu lösen, um Sicherheit garantieren
> zu können. Das heißt doch im Prinzip, dass der
> Pohlig-Hellman-Algorithmus in der Realität keinen Einsatz
> findet, oder irre ich mich jetzt?
Nun, wie bei vielen Attacken versucht man halt zu vermeiden, dass die Attacken anwendbar sind. Das ist natuerlich auch beim Pohlig-Hellman-Algorithmus so.
Der Algorithmus wird aber trotzdem woanders eingesetzt. Zum Beispiel muss man bei manchen zahlentheoretischen Problemen auch oefter mal DLPs loesen. Und da kann es gut mal passieren, dass Pohlig-Hellman anwendbar ist...
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:48 So 07.08.2011 | | Autor: | Hanz |
Ok, danke das Hilft mir jetzt weiter!
Hätte aber noch eine letzte Frage bis jetzt und zwar wird beim Index-Calculus-Algorithmus ja mit Hilfe der gefundenen Relationen ein Kongruenzsystem aufgestellt, welches modulo der Gruppenordnung eindeutig lösbar sein muss.
Es galt ja, dass ein Kongruenzsystem mod n eindeutig lösbar ist, wenn die Determinante der Koeffizientenmatrix teilerfremd zu n ist.
Welcher mathematische Hintergrund liegt hier zugrunde, dass die Determinante tatsächlich immer teilerfremd ist bzw. besteht überhaupt jemals die Gefahr, dass man ein Kongruenzsystem erhält, welches nicht eindeutig lösbar ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:12 So 07.08.2011 | | Autor: | felixf |
Moin!
> Hätte aber noch eine letzte Frage bis jetzt und zwar wird
> beim Index-Calculus-Algorithmus ja mit Hilfe der gefundenen
> Relationen ein Kongruenzsystem aufgestellt, welches modulo
> der Gruppenordnung eindeutig lösbar sein muss.
Muss es nicht. Wenn es nur wenige Wahlmoeglichkeiten gibt, lassen sich diese schnell ueberpruefen. Aber es ist besser, dass es moeglichst wenig Moeglichkeiten gibt.
> Es galt ja, dass ein Kongruenzsystem mod n eindeutig
> lösbar ist, wenn die Determinante der Koeffizientenmatrix
> teilerfremd zu n ist.
Das gilt nur, wenn du genausoviele Unbestimmte wie Gleichungen hast. Normalerweise sammelst du aber lieber ein paar mehr Gleichungen; das erhoeht die Wahrscheinlichkeit, dass du "genuegend" hast und das System eindeutig loesbar ist. Vor allem: wenn du mehr Gleichungen hast, gibt es keine Determinante mehr. Du kannst dann die Zeilenstufenform der Matrix (modulo $n$) bilden, die Nullzeilen wegschneiden, und hoffen dass diese Matrix gross genugen Rang / invertierbare Determinante hat.
> Welcher mathematische Hintergrund liegt hier zugrunde, dass
> die Determinante tatsächlich immer teilerfremd ist bzw.
> besteht überhaupt jemals die Gefahr, dass man ein
> Kongruenzsystem erhält, welches nicht eindeutig lösbar
> ist?
Nehmen wir mal an, die Gruppenordnung ist $n$ und du hast $k$ Elemente [mm] $p_1, \dots, p_k$, [/mm] deren diskrete Logarithmen (bzgl. einem Erzeuger $g$) du bestimmen willst (in der ersten Runde). Du sammelst der Reihe nach Relationen [mm] $(e_1, \dots, e_k, [/mm] f)$ mit [mm] $\prod_{i=1}^k p_i^{e_i} [/mm] = [mm] g^f$. [/mm] Wenn du $k + 1$ linear unabhaengige Relationen hast, dann bist du fertig: mehr gibt es nicht.
Wenn du weniger als $k + 1$ linar unabhaengige Relationen hast, kannst du dir die Menge der Relationen anschauen und vergleichen mit der Menge der Relationen die linear unabhaengig von den bisherigen ist. Falls $n = p$ prim ist, sind [mm] $p^k$ [/mm] Relationen linear abhaengig von den bisherigen und [mm] $p^{k+1} [/mm] - [mm] p^k$ [/mm] linear unabhaengig, die Wahrscheinlichkeit eine linear unabhaengige Relation zu finden ist also [mm] $\ge [/mm] 1 - [mm] \frac{1}{p}$, [/mm] und das ist normalerweise ziemlich gross. Falls $n$ nicht prim ist, wird es ein wenig ekeliger die Wahrscheinlichkeit zu berechnen, aber das ist auch moeglich. Es kommt zumindest etwas heraus was $> 0$ ist.
Wenn die Wahrscheinlichkeit gleich $A$ ist, dann brauchst du im Durchschnitt [mm] $\frac{1}{A}$ [/mm] Versuche, eine linear unabhaengige Relation zu finden. Daraus folgt, dass du mit recht hoher Wahrscheinlichkeit in endlich vielen Schritten genuegend Relationen findest.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 20:00 So 07.08.2011 | | Autor: | Hanz |
Nochmals danke!!!
Hast du zufällig einen (oder mehrere) Literaturtipps, wo ich das en détail nachlesen kann?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:38 Di 09.08.2011 | | Autor: | felixf |
Moin,
> Hast du zufällig einen (oder mehrere) Literaturtipps, wo
> ich das en détail nachlesen kann?
hmm, nicht wirklich. Ich hab Index Calculus in gefuehlten 100 Vortraegen kennengelernt bzw. in Papern was dazu gelesen. Eine vernuenftige Quelle zum Nachlesen (die insb. fuer Anfaenger geeignet ist) kenne ich leider nicht...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:21 Di 09.08.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:21 So 21.08.2011 | | Autor: | Hanz |
So, mir ist jetzt noch ne Frage dazu eingefallen und zwar wenn ich in einer primen Restklassengruppe bin, dann steht im Buch von Buchmann, dass das Auffinden von Relationen hier möglich ist, da die Elemente in den Ring der ganzen Zahlen geliftet werden können und hier eine eindeutige PFZ existiert.
Umgangssprachlich könnte man doch sagen, dass man statt mit Restklassen mit ganzen Zahlen rechnet, oder?
Eine Begründung dafür, also warum man das überhaupt machen muss, könnte so aussehen:
[mm] \mathbb Z_p^{\times} [/mm] ist ein Körper ohne die Null, d.h. jedes Element ist eine Einheit. Diese sind per Definition nicht prim, folglich besitzt der Körper keine Primelemente und die Primfaktorzerlegung in [mm] \mathbb Z_p^{\times} [/mm] sind gerade die Elemente selber.
Ist das so ok?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:49 So 21.08.2011 | | Autor: | felixf |
Moin!
> So, mir ist jetzt noch ne Frage dazu eingefallen und zwar
> wenn ich in einer primen Restklassengruppe bin, dann steht
> im Buch von Buchmann, dass das Auffinden von Relationen
> hier möglich ist, da die Elemente in den Ring der ganzen
> Zahlen geliftet werden können und hier eine eindeutige PFZ
> existiert.
Genau.
> Umgangssprachlich könnte man doch sagen, dass man statt
> mit Restklassen mit ganzen Zahlen rechnet, oder?
Ja.
> Eine Begründung dafür, also warum man das überhaupt
> machen muss, könnte so aussehen:
>
> [mm]\mathbb Z_p^{\times}[/mm] ist ein Körper ohne die Null, d.h.
> jedes Element ist eine Einheit. Diese sind per Definition
> nicht prim, folglich besitzt der Körper keine Primelemente
> und die Primfaktorzerlegung in [mm]\mathbb Z_p^{\times}[/mm] sind
> gerade die Elemente selber.
>
> Ist das so ok?
Ja, das stimmt so. :)
Das ist auch mit ein Grund, warum Index Calculus z.B. nicht ohne weiteres in der Punktegruppe einer elliptischen Kurve funktioniert: man kann nicht einfach irgendwo hinliften, wo man einfacher Punkte als Summe von anderen Punkten schreiben kann (die hoffentlich alle in einer gewissen Teilmengen liegen - der Faktorbasis).
Bei [mm] $(\IZ/p\IZ)^\ast$ [/mm] und [mm] $(\IF_p[x]/(f))^\ast$ [/mm] kann man halt auf [mm] $\IZ$ [/mm] bzw. [mm] $\IF_p[x]$ [/mm] zurueckgreifen... (oder auch auf [mm] $\mathcal{O}_K/\mathfrak{a}$ [/mm] mit $K$ einem Zahlkoerper)
LG Felix
|
|
|
|
