Eulersche Phi-Funktion, RSA < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | e × d = 1 (mod (φ(N))
<=> (e × d)×φ(N)× k =1
<= > e × d = k(p -1)(q -1)+1 |
Hallo, ich habe die RSA-Verschlüsselung als Facharbeitsthema und hab hierzu eine Frage.
Wer schon mal was mit der RSA-Verschlüsselung zu tun hatte, wird sich wahrscheinlich an die Gleichung erinnern. Für alle, die sich mit RSA nicht auskennen, aber dennoch über die Eulersche Phi-Funktion und über Modulo-Rechnung Bescheid wissen, hier die Erklärung der Variablen:
e ist eine Zahl aus [mm] \IN, [/mm] die zufällig gewählt wird und wobei gilt: 1<e<φ(N) ist.
φ(N)=(p-1)(q-1), wobei N das Produkt der Primzahlen p und q ist.
Wie kommt man nun von Zeile 2 auf Zeile 3? Müsste man nicht einfach φ(N)× k mittels Division auf die andere Seite bringen? Und woher kommt dann plötzlich "+ 1"?
Vielleicht versteht das ja jemand. Danke für die Hilfe schon im Vorraus.
PS: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt. 
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:38 Mi 02.12.2009 | | Autor: | felixf |
Hallo und ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !
> e × d = 1 (mod (φ(N))
> <=> (e × d)×φ(N)× k =1
Hier sollte stehen: $(e [mm] \cdot [/mm] d) + [mm] \varphi(N) \cdot [/mm] k = 1$.
Bzw. eigentlich noch eher: es gibt ein $k [mm] \in \IZ$ [/mm] mit $(e [mm] \cdot [/mm] d) + [mm] \varphi(N) \cdot [/mm] k = 1$.
> <= > e × d = k(p -1)(q -1)+1
Hier waer auch ein "es gibt ein $k [mm] \in \IZ$ [/mm] mit" davor angebracht.
> e ist eine Zahl aus [mm]\IN,[/mm] die zufällig gewählt wird und
> wobei gilt: 1<e<φ(N) ist.
Wichtiger ist noch, dass $e$ zu [mm] $\varphi(N)$ [/mm] teilerfremd ist. (Ansonsten gibt es ein solches $d$ gar nicht.)
> φ(N)=(p-1)(q-1), wobei N das Produkt der Primzahlen p und
> q ist.
>
> Wie kommt man nun von Zeile 2 auf Zeile 3?
Wenn du es korrigierst, so wie ich es oben geschrieben hast: einfach $k [mm] \cdot \varphi(N)$ [/mm] abziehen, und $k$ durch $-k$ ersetzen (da es nur darum geht, ob es ein solches $k$ gibt, muss es ja in Zeile 2 und Zeile 3 nicht das gleiche $k$ sein).
Ich hoffe das hilft dir weiter.
LG Felix
|
|
|
| |
|
Alternativ habe ich auch folgendes für den Ansatz gefunden:
Der größte gemeinsame Teiler von e und φN ist ggT(e, φN) = 1 (da e und p−1·q−1 teilerfremd per Definition und nur durch 1 gemeinsam teilbar).
Daraus ergibt sich die folgende Gleichung: 1=ed–k·p−1·q−1
Damt kann man d ausrechnen. Dies verstehe ich (noch) nicht. Hierzu muss ich noch Recherchen betreiben.
Also: die Quelle von der ich den Ansatz hatte, war nicht aufschlussreich genug. Mit dem neuen Ansatz, der den Weg nicht verschweigt, versteh ich den Rechenweg. Wie gesagt, muss ich mich noch über ggT informieren.
Momentan habe ich also keine weiteren Fragen mehr. Aber einen großen Dank an dich für deine Mühe.
|
|
|
| |
|
Danke für die Antwort. Habe das Verfahren endlich verstanden. Gibt es aber eine andere, effizientere Mehtode zum Ausrechnen von ggT(φN;e) als der Euklidische Algorithmus wie hier beschrieben: http://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus ?
Irgendwie sieht er für mich zu umständlich aus, vor allem um ihn in der Facharbeit zu erklären.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 03:40 Di 08.12.2009 | | Autor: | felixf |
Hallo!
> Danke für die Antwort. Habe das Verfahren endlich
> verstanden. Gibt es aber eine andere, effizientere Mehtode
> zum Ausrechnen von ggT(φN;e) als der Euklidische
> Algorithmus wie hier beschrieben:
> http://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus
> ?
Wenn du gleichzeitig $d$ finden willst: nein. Und soo kompliziert ist der Algorithmus auch wieder nicht.
> Irgendwie sieht er für mich zu umständlich aus, vor
> allem um ihn in der Facharbeit zu erklären.
Sooo schwierig ist der Algorithmus auch wieder nicht :) Hast du dir mal die ![[]](/images/popup.gif) rekursive Implementation angeschaut?
LG Felix
|
|
|
| |
|
Ich habe nicht gesagt, dass er schwierig wär. Ich meine nur, dass ich ihn bloß erklären muss in der Facharbeit und uns stehen ca 20 Seiten zu. Und das ist ja auch nicht das einzige, was erklärt werden muss. bleibt aber anscheinend nichts anderes übrig.
Was mir aber aufgefallen ist, ist, dass der Algorithmus irgendwie nicht immer funktioniert.
Bsp: p = 7; q = 13 -> N = pq = 91 -> φ(N) = (p-1)(q-1) = 72; e = 5
->
72 = 14·5 + 2
5 = 2·2 + 1
2 = 2·1 + 0
->
1 = 5 - 2·2 =
= 5 - (72 - 14·5) =
= 29·5 - 2·72
-> d = 29 -> passt!
hier das, was nicht funktioniert:
e = 11
->
72 = 6·11 + 6
11 = 1·6 + 5
6 = 1·5 + 1
5 = 5·1 + 0
->
1 = 6 - 1·5 =
= 6 - (11 - 1·6) =
= 2·6 - 11 =
= 2(72 - 6·11) - 11 =
= -13·11 + 2·72
-> d = -13
So, die Gleichung stimmt natürlich. Aber d = -13 ist unsinnig zum entschlüsseln. Somit die Frage: kann es sein, dass der Algorithmus nicht für alle [mm] e\IN [/mm] funktioniert, obwohl e und φ(N) teilerfremd sind? Ich dachte, dass der Algorithmus für alle e gelten muss. Morgen werd ich noch meinen Lehrer mal fragen. Facharbeitsbesprechung.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:16 Di 08.12.2009 | | Autor: | felixf |
Hallo!
> Ich habe nicht gesagt, dass er schwierig wär. Ich meine
> nur, dass ich ihn bloß erklären muss in der Facharbeit
> und uns stehen ca 20 Seiten zu. Und das ist ja auch nicht
> das einzige, was erklärt werden muss. bleibt aber
> anscheinend nichts anderes übrig.
Ja, das sieht so aus. Oder kannst du einfach darauf verweisen, dass man dies mit dem EEA ausrechnen kann?
> Was mir aber aufgefallen ist, ist, dass der Algorithmus
> irgendwie nicht immer funktioniert.
>
> [...]
>
> hier das, was nicht funktioniert:
>
> e = 11
>
> ->
> 72 = 6·11 + 6
> 11 = 1·6 + 5
> 6 = 1·5 + 1
> 5 = 5·1 + 0
>
> ->
> 1 = 6 - 1·5 =
> = 6 - (11 - 1·6) =
> = 2·6 - 11 =
> = 2(72 - 6·11) - 11 =
> = -13·11 + 2·72
>
> -> d = -13
>
> So, die Gleichung stimmt natürlich.
Ja.
> Aber d = -13 ist unsinnig zum entschlüsseln.
Naja, du musst $d$ modulo [mm] $\varphi(N)$ [/mm] nehmen. Dann bekommst du $-13 + [mm] \varphi(N) [/mm] = -13 + 72 = 59$. Das macht mehr Sinn, nicht?
Und es gilt weiterhin $11 [mm] \cdot [/mm] 59 [mm] \equiv [/mm] 1 [mm] \pmod{\varphi(N)}$.
[/mm]
LG Felix
|
|
|
| |
|
Achso. Ok. Habe jetzt das System kapiert. Danke für deine Hilfe.
LG Artur
|
|
|
|
