Verschlüsselungsverfahren < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:04 Mi 27.07.2011 | | Autor: | taiBsu |
Hallo, ich befasse mich zurzeit mit einem Public-Key-Kryptoverfahren namens RSA (benannt nach Rivest, Shamir und Adleman) und habe dazu zwei Fragen.
Erstens, [mm]\varphi (n)[/mm] wird ja berechnet durch [mm] \varphi [/mm] (n) = n * (1 - [mm] \bruch{1}{p_1}) [/mm] * ... * (1 - [mm] \bruch{1}{p_k}), [/mm] was sich ja auf die kanonische Darstellung einer Zahl n bezieht. Jetzt würde ich gerne wissen, wie man diese Primzahlen im Kopf rausbekommt, ohne ewig rumzuprobieren?
Meine zweite Frage lautet, in meinem Script steht, dass nach dem Lemma von Euler-Fermat folgendes gilt:
D(~m) = [mm] m^{k*\varphi(n)+1} [/mm] = [mm] m^{\varphi(n)*k+1} [/mm] = m.
Wie komme ich darauf, dass [mm] m^{\varphi(n)*k+1} [/mm] das selbe ist wie m?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
hallo taiBsu
> Hallo, ich befasse mich zurzeit mit einem
> Public-Key-Kryptoverfahren namens RSA (benannt nach Rivest,
> Shamir und Adleman) und habe dazu zwei Fragen.
> Erstens, [mm]\varphi (n)[/mm] wird ja berechnet durch [mm]\varphi[/mm] (n) =
> n * (1 - [mm]\bruch{1}{p_1})[/mm] * ... * (1 - [mm]\bruch{1}{p_k}),[/mm] was
> sich ja auf die kanonische Darstellung einer Zahl n
> bezieht. Jetzt würde ich gerne wissen, wie man diese
> Primzahlen im Kopf rausbekommt, ohne ewig rumzuprobieren?
Nun, man muss halt die Primteiler von n suchen. Wenn ich es
richtig sehe, konstruiert man aber doch bei RSA das n gerade
als Produkt zweier Primzahlen p und q, also liegen diese dann
doch ohnehin vor, und es ist [mm] $\varphi(n)=\varphi(p*q)=(p-1)*(q-1)$
[/mm]
> Meine zweite Frage lautet, in meinem Script steht, dass
> nach dem Lemma von Euler-Fermat folgendes gilt:
>
> D(~m) = [mm]m^{k*\varphi(n)+1}[/mm] = [mm]m^{\varphi(n)*k+1}[/mm] = m.
Was soll das "(~m)" heißen ?
> Wie komme ich darauf, dass [mm]m^{\varphi(n)*k+1}[/mm] das selbe ist
> wie m?
Euler-Fermat sagt: $\ [mm] m^{\varphi(n)} \equiv [/mm] 1\ \ [mm] (\mathrm{mod}\,n)$ [/mm] (falls m,n teilerfremd)
Dann folgt: [mm]m^{\varphi(n)*k+1}\ =\ \left(m^{\varphi(n)}\right)^k*m^1\ \equiv\ 1^k*m\ \equiv\ m\quad(mod\ n)[/mm]
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:19 Mi 27.07.2011 | | Autor: | taiBsu |
> Nun, man muss halt die Primteiler von n suchen. Wenn ich es
> richtig sehe, konstruiert man aber doch bei RSA das n gerade
> als Produkt zweier Primzahlen p und q, also liegen diese dann
> doch ohnehin vor, und es ist $ [mm] \varphi(n)=\varphi(p\cdot{}q)=(p-1)\cdot{}(q-1) [/mm] $
Ist das wirklich so einfach? Muss man beim [mm] \varphi(n) [/mm] mit n als Produkt zweier Primzahlen wirklich nur (p-1)*(q-1) rechnen?
>Was soll das "(~m)" heißen ?
"m Schlange", einfach nur ne Variable die auf m Bezug nimmt, also diese Tilde soll eigentlich über dem m liegen.
>Euler-Fermat sagt: $ \ [mm] m^{\varphi(n)} \equiv [/mm] 1\ \ [mm] (\mathrm{mod}\,n) [/mm] $
>(falls m,n teilerfremd)
>Dann folgt: $ [mm] m^{\varphi(n)\cdot{}k+1}\ [/mm] =\ [mm] \left(m^{\varphi(n)}\right)^k\cdot{}m^1\ \equiv\ 1^k\cdot{}m\ \equiv\ m\quad(mod\ [/mm] n) $
Das habe ich soweit verstanden, danke :D
|
|
|
| |
|
>
> > Nun, man muss halt die Primteiler von n suchen. Wenn ich
> > es richtig sehe, konstruiert man aber doch bei RSA das n
> > gerade als Produkt zweier Primzahlen p und q, also liegen
> > diese dann doch ohnehin vor, und es ist
> [mm]\varphi(n)=\varphi(p\cdot{}q)=(p-1)\cdot{}(q-1)[/mm]
>
> Ist das wirklich so einfach? Muss man beim [mm]\varphi(n)[/mm] mit n
> als Produkt zweier Primzahlen wirklich nur (p-1)*(q-1)
> rechnen?
Setz doch mal in deine Formel ein !
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:31 Mi 27.07.2011 | | Autor: | taiBsu |
Hm, gut, das funktioniert tatsächlich :D danke :)
Man, ich habe noch so viele Fragen und so wenig Zeit, immer so lange im Forum auf Antworten zu warten... Außerdem ist es schwierig, Probleme schriftlich zu erläutern...
|
|
|
| |
|
> Hm, gut, das funktioniert tatsächlich :D danke :)
> Man, ich habe noch so viele Fragen und so wenig Zeit, immer
> so lange im Forum auf Antworten zu warten... Außerdem ist
> es schwierig, Probleme schriftlich zu erläutern...
naja, über langes Warten-müssen kannst du dich aber
wohl kaum beschweren ...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:46 Mi 27.07.2011 | | Autor: | taiBsu |
Nein, auf keinen Fall - es ist eher so, dass ich dem Stoff extrem hinterher bin und langsam die Aufgabenstellungen mal begreifen muss, weil in 2 Wochen die Prüfung ist und mir noch 1/2 Semester Mathe fehlt... :(
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:31 Mi 27.07.2011 | | Autor: | felixf |
Moin!
> >Euler-Fermat sagt: [mm]\ m^{\varphi(n)} \equiv 1\ \ (\mathrm{mod}\,n)[/mm]
> >(falls m,n teilerfremd)
>
> >Dann folgt: [mm]m^{\varphi(n)\cdot{}k+1}\ =\ \left(m^{\varphi(n)}\right)^k\cdot{}m^1\ \equiv\ 1^k\cdot{}m\ \equiv\ m\quad(mod\ n)[/mm]
>
> Das habe ich soweit verstanden, danke :D
Das war aber noch nicht alles  Das ganze gilt ja nur dann, wenn $m$ teilerfremd zu $n$ ist. Es kann aber z.B. $m = 0$, $m = p$, $m = 123 p$, $m = q$, $m = 871782 q$ sein (vorausgesetzt $n$ ist gross genug). Insgesamt fehlen [mm] $\frac{1}{p} [/mm] + [mm] \frac{1}{q} [/mm] - [mm] \frac{1}{p q}$ [/mm] aller $m$.
Fuer die restlichen $m$, die eben nicht teilerfremd zu $n$ sind, musst du den Chinesischen Restsatz bequemen und beachten, dass [mm] $0^{irgendwas} [/mm] = 0$ ist.
(Hier braucht man ganz wichtig, dass $n$ quadratfrei ist, d.h. es gibt keine Primzahl $p$ mit [mm] $p^2 \mid [/mm] n$.)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:35 Mi 27.07.2011 | | Autor: | taiBsu |
Wie wende ich den chinesischen Restsatz an, habe davon noch nie etwas gehört?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:14 Mi 27.07.2011 | | Autor: | felixf |
Moin!
> Wie wende ich den chinesischen Restsatz an, habe davon noch
> nie etwas gehört?
Fuer $n = p q$ mit zwei verschiedenen Primzahlen sagt der chinesische Restsatz folgendes aus:
fuer $a, b [mm] \in \IZ$ [/mm] gilt genau dann $a [mm] \equiv [/mm] b [mm] \pmod{n}$, [/mm] wenn $a [mm] \equiv [/mm] b [mm] \pmod{p}$ [/mm] und $a [mm] \equiv [/mm] b [mm] \pmod{q}$ [/mm] gilt.
Oder anders gesagt: wenn du etwas modulo $n$ pruefen willst, kannst du es auch getrennt erstmal modulo $p$ anschauen, und dann modulo $q$.
LG Felix
|
|
|
| |
|
> > >Euler-Fermat sagt: [mm]\ m^{\varphi(n)} \equiv 1\ \ (\mathrm{mod}\,n)[/mm]
> > >(falls m,n teilerfremd)
> >
> > >Dann folgt: [mm]m^{\varphi(n)\cdot{}k+1}\ =\ \left(m^{\varphi(n)}\right)^k\cdot{}m^1\ \equiv\ 1^k\cdot{}m\ \equiv\ m\quad(mod\ n)[/mm]
> Das war aber noch nicht alles Das ganze gilt ja nur
> dann, wenn [mm]m[/mm] teilerfremd zu [mm]n[/mm] ist. Es kann aber z.B. [mm]m = 0[/mm],
> [mm]m = p[/mm], [mm]m = 123 p[/mm], [mm]m = q[/mm], [mm]m = 871782 q[/mm] sein (vorausgesetzt [mm]n[/mm]
> ist gross genug). Insgesamt fehlen [mm]\frac{1}{p} + \frac{1}{q} - \frac{1}{p q}[/mm]
> aller [mm]m[/mm].
Hallo Felix,
ich war in meiner Antwort nur auf die Frage eingegangen,
wie man Euler-Fermat anwendet, und dort wird die
Teilerfremdheit vorausgesetzt. Im übrigen war mir nicht
klar, für welche m denn die Äquivalenz gebraucht würde.
LG Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:13 Mi 27.07.2011 | | Autor: | felixf |
Moin Al,
> ich war in meiner Antwort nur auf die Frage eingegangen,
> wie man Euler-Fermat anwendet, und dort wird die
> Teilerfremdheit vorausgesetzt. Im übrigen war mir nicht
> klar, für welche m denn die Äquivalenz gebraucht
> würde.
kein Problem :) Das m ist hier die Nachricht, und darf ein beliebiger Wert zwischen 0 und n-1 sein. Wenn man natuerlich zufaellig eine Nachricht erwischt, die nicht teilerfremd zu n ist (und nicht gerade 0 ist), so kann man n faktorisieren. Das muss also schon sehr unwahrscheinlich sein.
Aber RSA kommt auch mit solchen Nachrichten zurecht, das ist der springende Punkt  Und dazu braucht man ganz dringend, dass n teilerfremd ist, da ansonsten die Verschluesselungsfunktion $m [mm] \mapsto m^e \mod [/mm] n$ nicht mehr injektiv ist.
LG Felix
|
|
|
|
