RSA-Verfahren < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Also die Aufgabe lautet wie folgt:#
Gegeben seien m=21, s=5 und es gelte 15 [mm] \le [/mm] c [mm] \le [/mm] 20 sowie p [mm] \le [/mm] q .
a)Wie viele Verschlüsselungen sind möglich?
b)Bestimmen sie für jede dieser Möglichkeiten die Verschlüsselung w omega mit einem dach) von w=3 und demonstrieren Sie die Richtigkeit des RSA-Verfahrens durch die anschließende Entschlüsselung von w (omega dach).
der öffentliche schlüssel m ist gegeben (produkt von p*q -> wie ermittel ich aber p,q .. die brauch ich doch bei der berechnung der Verschlüsselungen oder nicht? ... )
mein privater schlüssel ist auch gegeben...nämlich s...
ich weiß jedoch nicht wie ich wo anfangen soll.. kann mir da jmd helfen?
|
|
| |
|
Hallo sormanehaldeyim,
> Also die Aufgabe lautet wie folgt:#
>
> Gegeben seien m=21, s=5 und es gelte 15 [mm]\le[/mm] c [mm]\le[/mm] 20 sowie
Welche Bedeutung hat dieses c?
> p [mm]\le[/mm] q .
> a)Wie viele Verschlüsselungen sind möglich?
> b)Bestimmen sie für jede dieser Möglichkeiten die
> Verschlüsselung w omega mit einem dach) von w=3 und
> demonstrieren Sie die Richtigkeit des RSA-Verfahrens durch
> die anschließende Entschlüsselung von w (omega dach).
>
> der öffentliche schlüssel m ist gegeben (produkt von p*q
> -> wie ermittel ich aber p,q .. die brauch ich doch bei der
> berechnung der Verschlüsselungen oder nicht? ... )
> mein privater schlüssel ist auch gegeben...nämlich s...
>
> ich weiß jedoch nicht wie ich wo anfangen soll.. kann mir
> da jmd helfen?
Da m der öffentliche Schlüssel und
s der private Schlüssel ist, gilt
[mm]m*s \equiv 1 \ \operatorname{\left(mod \ \varphi\left(N\right)\right)}[/mm]
,wobei [mm]\varphi\left(N\right)\right)=\left(p-1\right)\left(q-1\right)[/mm]
für p,q zwei verschiedene Primzahlen ist.
Berechnet man das mit den angegebenen Daten, so folgt
[mm]m*s =21*5=105 \equiv 1 \ \operatorname{\left(mod \ \varphi\left(N\right)\right)}[/mm]
Damit ist [mm]\varphi\left(N\right)[/mm] ein Teiler von 105-1=104.
Klar ist auch, daß [mm]\varphi\left(N\right) > 21[/mm] sein muss.
Stelle diese Teiler als Produkt zweier Zahlen dar,
und überprüfe dann ob p und q Primzahlen sind.
Gruss
MathePower
|
|
|
| |
|
c ist doch auch ein öffentlicher schlüssel oder nicht ?
und mein produt wäre doch 8*13=104 ... so ?
|
|
|
| |
|
Hallo sormanehaldeyim,
> c ist doch auch ein öffentlicher schlüssel oder nicht ?
Ich weiss nicht, was c für eine Bedeutung hat.
>
> und mein produt wäre doch 8*13=104 ... so ?
Ja, das ist eine von mehreren Produktbildungen.
Es gilt ja die Gleichung
[mm]104=8*13=\left(p-1\right)*\left(q-1\right)[/mm]
Daraus ergibt sich p=9, q=14 und dies sind keine Primzahlen.
Es muss also noch weitere Möglichkeiten geben.
Gruss
MathePower
|
|
|
| |
|
und was wär mit
[mm] 2^3*13 [/mm] ?
|
|
|
| |
|
Hallo sormanehaldeyim,
> und was wär mit
>
> [mm]2^3*13[/mm] ?
Das hatten wir doch schon.
Zerlege 104 so:
104 =1*104 = 2* 52 = 4*26= 8*13
Teste jetzt alle diese Möglichkeiten auf die Darstellung
[mm]104=\left(p-1\right)\left(q-1\right)[/mm]
,wobei p und q Primzahlen sein müssen.
Gruss
MathePower
|
|
|
| |
|
achso...
dann kommt nur 2* 52 in Frage
mit den Primzaheln 3 und 53
stimmt das so?
und wie gehts nun weiter ?
|
|
|
| |
|
Hallo sormanehaldeyim,
> achso...
> dann kommt nur 2* 52 in Frage
> mit den Primzaheln 3 und 53
> stimmt das so?
> und wie gehts nun weiter ?
Berechne jetzt das N, das brauchst Du nämlich um die Nachricht w=3
zu verschlüsseln und dann wieder zu entschlüsseln.
Gruss
MathePower
|
|
|
| |
|
okay dann hab ich p=3 und q=53
p* q = N
3*53 = 159
aber wie verschlüssel ich jettz w=3
ich weiß w [mm] \equiv \vec{w} [/mm] mod m mit 0 [mm] \le [/mm] w < m ist...
|
|
|
| |
|
Hallo sormanehaldeyim,
> okay dann hab ich p=3 und q=53
>
> p* q = N
> 3*53 = 159
>
> aber wie verschlüssel ich jettz w=3
> ich weiß w [mm]\equiv \vec{w}[/mm] mod m mit 0 [mm]\le[/mm] w < m ist...
Jetzt musst Du
[mm]w^{21} = 3^{21} \ \operatorname{mod} 159[/mm]
berechnen.
Gruss
MathePower
|
|
|
| |
|
Aber dieses [mm] 3^{21} [/mm] ist doch eine ziemlich große Zahl...
Wie berechne ich denn das?
|
|
|
| |
|
Hallo sormanehaldeyim,
> Aber dieses [mm]3^{21}[/mm] ist doch eine ziemlich große Zahl...
>
> Wie berechne ich denn das?
Die Zahl 21 lässt sich als Summe von 2er Potenzen darstellen: [mm]21=2^{4}+2^{2}+2^{1}[/mm]
Das geht so:
Es ist [mm]3 \equiv 3 \ \operatorname{mod} \ 159[/mm]
Dann geht das so weiter:
[mm]3^{2} \equiv 3*3 = 9 \ \operatorname{mod} \ 159[/mm]
[mm]3^{4} \equiv 3^{2}*3^{2} = 9*9=81 \ \operatorname{mod} \ 159[/mm]
[mm]3^{8} \equiv 3^{4}*3^{4} = 81*81 \ \operatorname{mod} \ 159[/mm]
[mm]3^{16} \equiv 3^{8}*3^{8} \ \operatorname{mod} \ 159[/mm]
Und es gilt:
[mm]21=2^{4}+2^{2}+2^{1}[/mm]
Demnach
[mm]3^{21}=3^{2^{4}+2^{2}+2^{1}}=3^{2^{4}}*3^{2^{2}}*3^{2^{1}}=3^{16}*3^{4}*3^{1}[/mm]
Gruss
MathePower
|
|
|
| |
|
danke nun versteh ich es so langsam...
ich hab mal weiter probiert
Bestimmung von e (öffentlicher Schlüssel des Empfängers)
e muss zu 104 Teilerfremd sein
mit ggt(e, phi(N))= 1
e wäre dann 3
richitg?
So dann d mit d*e mod phi(n)
d= 35
Also sind meine öffentlichen Schlüssel (n,e) = (159,3)
aber was ich grade nicht verstehe, wie komme ich darauf wieviele RSA Verschlüsselungen mit den Angaben möglcih wäre (Aufgabenstellung)
|
|
|
| |
|
Hallo sormanehaldeyim,
> danke nun versteh ich es so langsam...
>
> ich hab mal weiter probiert
>
> Bestimmung von e (öffentlicher Schlüssel des
> Empfängers)
> e muss zu 104 Teilerfremd sein
> mit ggt(e, phi(N))= 1
>
> e wäre dann 3
> richitg?
>
> So dann d mit d*e mod phi(n)
>
> d= 35
>
> Also sind meine öffentlichen Schlüssel (n,e) = (159,3)
Der öffentliche Schlüssel ist doch mit m=21 gegeben
(Das ist der Schlüssel mit dem der Absender eine Nachricht verschlüsselt).
Ebenso ist der private Schlüssel mit s=5 gegeben.
(Das ist der Schlüssel mit dem der Empfänger eine Nachricht entschlüsselt).
Berechnet wurde lediglich das N mit N=159.
>
> aber was ich grade nicht verstehe, wie komme ich darauf
> wieviele RSA Verschlüsselungen mit den Angaben möglcih
> wäre (Aufgabenstellung)
>
Solange ich die Bedeutung des Parameters c nicht kenne,
kann ich Dir das auch nicht sagen.
Gruss
MathePower
|
|
|
| |
|
das c ist doch auch ein öffentlicher Schlüssel wie m
Seien c, s [mm] \in [/mm] N mit c · [mm] s\equiv [/mm] 1 mod (p − 1)(q − 1)
so hatten wir das in der Vorlesung..
|
|
|
| |
|
Hallo sormanehaldeyim,
> das c ist doch auch ein öffentlicher Schlüssel wie m
>
> Seien c, s [mm]\in[/mm] N mit c · [mm]s\equiv[/mm] 1 mod (p − 1)(q − 1)
>
> so hatten wir das in der Vorlesung..
Ok.
Gruss
MathePower
|
|
|
| |
|
Aber wie bekomme ich nun raus wie viele Verschlüsselungen es existieren.
Kannst du mir bitte weiterhelfen?
|
|
|
| |
|
Hallo sormanehaldeyim,
> Aber wie bekomme ich nun raus wie viele Verschlüsselungen
> es existieren.
>
> Kannst du mir bitte weiterhelfen?
Die Kongruenz
[mm]c*s \equiv 1 \ \operatorname{mod} \ 104[/mm]
hat nur dann eine Lösung. wenn
[mm]ggT\left(c,104\right)=1[/mm]
ist.
Gruss
MathePower
|
|
|
| |
|
die Zahl c muss zu 104 teilerfremd sein
dann wähl ich zum Beispiel 19
c=19 und N=104 bilden den öffentlcihen Schlüssel
Muss ich nun das Inverse zu c finden?
|
|
|
| |
|
Hallo sormanehaldeyim,
> die Zahl c muss zu 104 teilerfremd sein
>
> dann wähl ich zum Beispiel 19
>
> c=19 und N=104 bilden den öffentlcihen Schlüssel
>
> Muss ich nun das Inverse zu c finden?
Ja.
Gruss
MathePower
|
|
|
| |
|
Okay ich versuche es mal
aber ich habe für c=5 genommen
5*d + k*104=1 = ggT (5, 104)
Mit dem erweiterten euklidischen Algorithmus habe ich
d= 21 und k=(-1) berechnet
d ist der private Schlüssel
Woher weiss ich nun wieviele Möglichkeiten es gibt?
|
|
|
| |
|
Hallo sormanehaldeyim,
> Okay ich versuche es mal
> aber ich habe für c=5 genommen
>
> 5*d + k*104=1 = ggT (5, 104)
>
> Mit dem erweiterten euklidischen Algorithmus habe ich
> d= 21 und k=(-1) berechnet
>
> d ist der private Schlüssel
Hmm, das hatten wir eingang schon, m=21,s=5.
> Woher weiss ich nun wieviele Möglichkeiten es gibt?
Wie schon erwähnt, c und 104 müssen teilerfremd sein.
Zerlege dazu 104 in seine Primfaktoren, und schaue
dann für welche c, [mm] 15 \le c \le 20[/mm] der ggT
dieser zwei Zahlen 1 ist.
Gruss
MathePower
|
|
|
| |
|
Okay Primfaktorzerlegung von 104 = 2*2*2*13 [mm] =2^{3}*13
[/mm]
Aber ich weiß gerade nicht wie ich den ggT finde :(
|
|
|
| |
|
Hallo sormanehaldeyim,
> Okay Primfaktorzerlegung von 104 = 2*2*2*13 [mm]=2^{3}*13[/mm]
>
> Aber ich weiß gerade nicht wie ich den ggT finde :(
Mache das gleich mit c, [mm]15 \le c \le 20[/mm]
Beispiel c=15
15=3*5
104=2*2*2*13
Demnach sind 15 und 104 teilerfremd.
Analog für die anderen c's.
Gruss
MathePower
|
|
|
| |
|
Okay also:
16= [mm] 2^{4}
[/mm]
17 ist ja selbst ne Primzahl
18= 2*3*3
19 wie 17
20= 2*2*5
Kann ich jetzt die 17 oder 19 als ggT nehmen?
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:40 Do 16.12.2010 | | Autor: | Bilmem |
Mich würde es jetzt auch interessieren, wie geht es weiter, ist der vorherige Beitrag von dem Threadsteller richtig?
|
|
|
| |
|
Hallo Bilmem,
> Mich würde es jetzt auch interessieren, wie geht es
> weiter, ist der vorherige Beitrag von dem Threadsteller
> richtig?
Bis auf die Tatsache, daß der Threadsteller eine
Möglichkeit vergessen hat, ist der Beitrag richtig.
Gruss
MathePower
|
|
|
| |
|
Hallo sormanehaldeyim.
> Okay also:
> 16= [mm]2^{4}[/mm]
> 17 ist ja selbst ne Primzahl
> 18= 2*3*3
> 19 wie 17
> 20= 2*2*5
>
> Kann ich jetzt die 17 oder 19 als ggT nehmen?
Du kannst jetzt als c 17 oder 19 wählen.
Aber es gibt ja noch eine Möglichkeit, c zu wählen.
Gruss
MathePower
|
|
|
| |
|
Ich brauche noch Hilfe:(
ich sitze schon seit 3 Tagen an dieser Aufgabe...
verstehe einfach die Logik nicht
|
|
|
|
