RSA - Verfahren < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:35 Mi 24.10.2012 | | Autor: | susiii |
hallo :)
Ich schreibe mein Seminararbeit über Primzahlen, darunter auch, als praktische Anwendung, ein Kapitel über das RSA-Verfahren. Nun habe ich versucht, dass RSA-Verfahren an einfachen Zahlen auszuprobieren. Doch ich komme bei der Berechnung des Dechiffrierschlüssels nicht weiter.
Bisher habe ich gerechnet:
zwei Primzahlen p = 7 und q = 11
daraus folgt n= p*q= 77 und phi(n) = 60
außerdem a=8 festgelegt
verschlüsselt soll die zahl x= 12 werde
-> y= [mm] x^{a} [/mm] (mod n)
y= [mm] 12^{8} [/mm] (mod 77)
y= 61
Stimmen meine Berechnungen bisher?
nun soll der Dechiffrierschlüssel bestimmt werden mit:
ab (mod m) = 1
b= [mm] \bruch{1+k*m}{a}
[/mm]
b= [mm] \bruch{1+k*60}{8}
[/mm]
wobei k [mm] \in \IN [/mm] und so gewählt werden muss, dass auch b [mm] \in \IN.
[/mm]
Hier stehe ich auf dem schlauch. Wie kann k berechnet werden?
Wäre sehr super wenn mir jemand einen Tipp geben könnte.
Viele Dank im Voraus!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:44 Mi 24.10.2012 | | Autor: | felixf |
Moin!
> Ich schreibe mein Seminararbeit über Primzahlen, darunter
> auch, als praktische Anwendung, ein Kapitel über das
> RSA-Verfahren. Nun habe ich versucht, dass RSA-Verfahren an
> einfachen Zahlen auszuprobieren. Doch ich komme bei der
> Berechnung des Dechiffrierschlüssels nicht weiter.
> Bisher habe ich gerechnet:
> zwei Primzahlen p = 7 und q = 11
> daraus folgt n= p*q= 77 und phi(n) = 60
> außerdem a=8 festgelegt
> verschlüsselt soll die zahl x= 12 werde
> -> y= [mm]x^{a}[/mm] (mod n)
> y= [mm]12^{8}[/mm] (mod 77)
> y= 61
> Stimmen meine Berechnungen bisher?
Nicht ganz: [mm] $12^8$ [/mm] modulo 77 ist 67 und nicht 61.
> nun soll der Dechiffrierschlüssel bestimmt werden mit:
> ab (mod m) = 1
So ein $b$ gibt es fuer gegebenes $a$ nur dann, wenn $a$ und $m$ teilerfremd sind. Das ist bei dir nicht der Fall, da 60 und 8 nicht teilerfremd sind. Das kannst du auch hier sehen:
> b= [mm]\bruch{1+k*m}{a}[/mm]
> b= [mm]\bruch{1+k*60}{8}[/mm]
Damit ist $b = [mm] \frac{1}{8} [/mm] + [mm] \frac{15 k}{2}$. [/mm] Dies kann aber fuer ganzzahliges $k$ niemals eine ganze Zahl werden, da der Nenner von [mm] $\frac{15 k}{2}$ [/mm] niemals 8 werden kann.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:13 Mi 24.10.2012 | | Autor: | susiii |
Danke für die schnelle Antwort!
Ich hab übersehen, dass a und m teilfremd sein müssen.
Aber jetzt habe ich's verstanden.
|
|
|
|
