Pohlig-Hellmann-Algorithmus < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:15 Mo 16.05.2011 | | Autor: | Hanz |
Hallo,
ich versuche mir gerade den Pohlig-Hellmann-Algorithmus anzueignen mittels dieses pdf's:
http://www.wi.uni-muenster.de/pi/lehre/ws0708/seminar/Abgaben/Diskrete%20Logarithmen.pdf
Auf der Seite 19 werden dort [mm] \alpha_0, \alpha_1 [/mm] und [mm] \alpha_2 [/mm] berechnet. Ich kann es aber nicht nachvollziehen, wie man darauf kommt...
Könnte mir jemand erklären, wie man auf [mm] \alpha_2 [/mm] = 1579 + 2017 [mm] \IZ [/mm] kommt?
Danke.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:08 Di 17.05.2011 | | Autor: | Hanz |
Niemand eine Idee? :(
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:15 Di 17.05.2011 | | Autor: | felixf |
Moin!
> Niemand eine Idee? :(
Doch, schon, aber gerade nicht so viel Zeit. Und das PDF ist ein wenig verwirrend, so dass ich mich da etwas durchlesen muss um deine Frage beantworten zu koennen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:03 Do 19.05.2011 | | Autor: | Hanz |
Hi, wäre echt nett, wenn du mir da weiterhelfen könntest.
Vllt. würde ja das hier helfen:
http://www.cs.uni-potsdam.de/ti/lehre/09ws-Kryptographie/slides/slides-5.3.pdf
(Hier die Folien 9-11) Handelt sich um dasselbe Beispiel, aber wie man diese [mm] a_i [/mm] bestimmt, will mir nicht einleuchten :<
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:52 Do 19.05.2011 | | Autor: | felixf |
Moin!
> Hi, wäre echt nett, wenn du mir da weiterhelfen
> könntest.
>
> Vllt. würde ja das hier helfen:
>
> http://www.cs.uni-potsdam.de/ti/lehre/09ws-Kryptographie/slides/slides-5.3.pdf
>
> (Hier die Folien 9-11) Handelt sich um dasselbe Beispiel,
> aber wie man diese [mm]a_i[/mm] bestimmt, will mir nicht einleuchten
> :<
Das Beispiel ist schonmal viel leserlicher.
Versuch das ganze doch mal anhand der Rechnung auf Folie 11 nachzuvollziehen. Wenn du dazu eine Frage hast, sag genau zu welchem Gleichheitszeichen du eine Frage hast und stell sie hier.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:28 Do 19.05.2011 | | Autor: | Hanz |
Der Schritt den ich da nicht verstehe, ist wie man die y berechnet (auf Folie 11).
Wie kommt man da auf: [mm] y_{2,2} [/mm] = [mm] 1579^4?
[/mm]
Was muss ich genau rechnen, um auf die 1579 zu kommen?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:34 Fr 20.05.2011 | | Autor: | felixf |
Moin!
> Der Schritt den ich da nicht verstehe, ist wie man die y
> berechnet (auf Folie 11).
Du suchst $x$ mit [mm] $5^x \equiv [/mm] 3 [mm] \pmod{2017}$. [/mm] Da die Gruppenordnung $2016 = [mm] 2^5 \cdot (3^2 \cdot [/mm] 7) = [mm] 2^5 \cdot [/mm] 63$ ist, musst du [mm] $5^{63}$ [/mm] und [mm] $3^{63}$ [/mm] modulo 2017 ausrechnen. Es ist [mm] $g_2 [/mm] = [mm] 5^{63} \mod [/mm] 2017 = 500$ und [mm] $y_2 [/mm] = [mm] 3^{63} \mod [/mm] 2017 = 913$ (Notation von Folie 9). (Dieses [mm] $y_2$ [/mm] ist nachher [mm] $y_{2,0}$.)
[/mm]
Um jetzt [mm] $\log_5 [/mm] 3 [mm] \mod 2^5$ [/mm] auszurechnen, berechnet man erst [mm] $g_\ast [/mm] = [mm] 500^{2^{5 - 1}} \mod [/mm] 2017 = 2016$; dieses Element hat die Ordnung 2 (was nicht ueberraschend ist, da $2016 [mm] \equiv [/mm] -1 [mm] \pmod{2017}$) [/mm] in der multiplikativen Gruppe.
Wir schreiben [mm] $\log_5 [/mm] 3 [mm] \mod 2^5 [/mm] = [mm] x_{2,0} [/mm] + 2 [mm] x_{2,1} [/mm] + 4 [mm] x_{2,2} [/mm] + 8 [mm] x_{2,3} [/mm] + 16 [mm] x_{2,4}$.
[/mm]
Angenommen, es sind nun [mm] $x_{2,0}, \dots, x_{2,k-1}$ [/mm] bestimmt. Nach der Formel auf Folie 10 gilt nun [mm] $y_{2,k} [/mm] = [mm] (y_2 \cdot g_2^{-\sum_{i
Fangen wir also mit $k = 0$ an. Es ist [mm] $y_{2,0} [/mm] = [mm] (y_2 \cdot g_2^0)^{2^{5 - 0 - 1}} [/mm] = [mm] y_2^{2^4} [/mm] = [mm] y_2^{16} [/mm] = [mm] 913^{16} \equiv [/mm] 1 [mm] \pmod{2017}$, [/mm] also haben wir das DLP [mm] $2016^{x_{2,0}} \equiv [/mm] 1 [mm] \pmod{2017}$. [/mm] Hier sieht man, dass [mm] $x_{2,0} [/mm] = 0$ sein muss.
Jetzt zu $k = 1$. Es ist [mm] $y_{2,1} [/mm] = [mm] (y_2 \cdot g_2^{-x_{2,0} \cdot 2^0})^{2^{5 - 1 - 1}} [/mm] = [mm] (y_2 \cdot 1)^{2^3} [/mm] = [mm] 913^8 \equiv [/mm] 2016 [mm] \pmod{2017}$. [/mm] Also haben wir das DLP [mm] $2016^{x_{2,1}} \equiv [/mm] 2016 [mm] \pmod{2017}$, [/mm] und somit ist [mm] $x_{2,1} [/mm] = 1$.
Zu $k = 2$: es ist [mm] $y_{2,2} [/mm] = [mm] (y_2 \cdot g_2^{-x_{2,0} - 2 x_{2,1}})^{2^{5 - 2 - 1}} [/mm] = [mm] (y_2 \cdot g_2^{-2})^{2^2} [/mm] = (913 [mm] \cdot 500^{-2})^4 \equiv [/mm] (913 [mm] \cdot 593^2)^4 \equiv 1579^4 \equiv [/mm] 2016 [mm] \pmod{2017}$ [/mm] (da [mm] $500^{-1} \equiv [/mm] 593 [mm] \pmod{2017}$). [/mm] Also haben wir das DLP [mm] $2016^{x_{2,2}} \equiv [/mm] 2016 [mm] \pmod{2017}$ [/mm] und somit wieder [mm] $x_{2,2} [/mm] = 1$.
Zu $k = 3$: es ist [mm] $y_{2,3} [/mm] = [mm] (y_2 \cdot g_2^{-x_{2,0} - 2 x_{2,1} - 4 x_{2,2}})^{2^{5 - 3 - 1}} [/mm] = [mm] (y_2 \cdot g_2^{-6})^{2^1} \equiv [/mm] (913 [mm] \cdot 593^6)^2 \equiv 1^2 [/mm] = 1 [mm] \pmod{2017}$. [/mm] Damit haben wir das DLP [mm] $2016^{x_{2,3}} \equiv [/mm] 1 [mm] \pmod{2017}$ [/mm] und somit [mm] $x_{2,3} [/mm] = 0$.
Fuer $k = 4$ haben wir dann [mm] $y_{2,4} [/mm] = [mm] (y_2 \cdot 2^{-6})^{2^0} \equiv [/mm] 1 [mm] \pmod{2017}$ [/mm] und mittels [mm] $2016^{x_{2,4}} \equiv [/mm] 1 [mm] \pmod{2017}$ [/mm] schliesslich [mm] $x_{2,4} [/mm] = 0$.
Also ist [mm] $\log_5 [/mm] 3 [mm] \mod 2^5 [/mm] = [mm] x_2 [/mm] = 6$.
Ich hoffe, das ist jetzt besser nachvollziehbar...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:42 Mo 23.05.2011 | | Autor: | Hanz |
Vielen Dank für die sehr ausführliche Antwort. Habe das Verfahren jetzt auch ganz verstanden.
DANKE!!!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:40 Di 14.06.2011 | | Autor: | Hanz |
Hi,
mir ist gerade noch etwas aufgefallen, was ich im theoretischen nicht ganz nachvollziehen kann und zwar:
(handelt sich um das selbe pdf oben Seite 10/11)
Man reduziert doch die Gruppen auf Primzahlpotenzordnungen, warum aber rechnet man in den Rechnungen immer mod 2017 und nicht modulo die Primzahl?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:22 Di 14.06.2011 | | Autor: | felixf |
Moin!
> mir ist gerade noch etwas aufgefallen, was ich im
> theoretischen nicht ganz nachvollziehen kann und zwar:
>
> (handelt sich um das selbe pdf oben Seite 10/11)
>
> Man reduziert doch die Gruppen auf Primzahlpotenzordnungen,
> warum aber rechnet man in den Rechnungen immer mod 2017 und
> nicht modulo die Primzahl?
Du rechnest in einer Untergruppe der urspruenglichen Gruppe.
Die urspruengliche Gruppe ist hier [mm] $(\IZ/2017\IZ)^\ast$. [/mm] Die Untergruppe hat Ordnung $p$.
Die Untergruppe ist jetzt nicht gleich [mm] $(\IZ/p\IZ)^\ast$ [/mm] (die haett auch nur $p - 1$ Elemente).
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 Do 19.05.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
