ElGamal < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
also ich habe eine Frage zu quadratischen Resten und dem Jacobi-Symbol in Bezug auf das ElGamal-Kryptoschema.
Erstmal, was quadratischer Rest bedeutet:
Es sei n>0. Eine Zahl a [mm] \in \IZ [/mm] heißt quadratischer Rest modulo n, wenn ggt(a,n) =1 gilt und es eine Zahl b [mm] \in \IZ [/mm] gibt mit [mm] b^2 [/mm] mod n = a mod n.
Das Jacobi-Symbol wird hier gut erklärt: http://de.wikipedia.org/wiki/Jacobi-Symbol
So, jetzt habe ich im Skript stehen, dass man sich im ElGamal-Kryptoschema am besten auf Elemente aus der Untergruppe QR(p), der quadratischen Reste von [mm] \IZ_{p} [/mm] ^{*} bezieht, da hier alle Elemente das gleiche Jacobi-Symbol, nämlich 1, haben. Und das verstehe ich nicht...Könnte mir da jemand sagen, warum da alle Elemente das Jacobi-Symbol =1 haben?
Danke!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:34 Di 20.03.2012 | | Autor: | felixf |
Moin!
> also ich habe eine Frage zu quadratischen Resten und dem
> Jacobi-Symbol in Bezug auf das ElGamal-Kryptoschema.
> Erstmal, was quadratischer Rest bedeutet:
>
> Es sei n>0. Eine Zahl a [mm]\in \IZ[/mm] heißt quadratischer Rest
> modulo n, wenn ggt(a,n) =1 gilt und es eine Zahl b [mm]\in \IZ[/mm]
> gibt mit [mm]b^2[/mm] mod n = a mod n.
>
> Das Jacobi-Symbol wird hier gut erklärt:
> http://de.wikipedia.org/wiki/Jacobi-Symbol
>
> So, jetzt habe ich im Skript stehen, dass man sich im
> ElGamal-Kryptoschema am besten auf Elemente aus der
> Untergruppe QR(p), der quadratischen Reste von [mm]\IZ_{p}[/mm] ^{*}
> bezieht, da hier alle Elemente das gleiche Jacobi-Symbol,
> nämlich 1, haben. Und das verstehe ich nicht...Könnte mir
> da jemand sagen, warum da alle Elemente das Jacobi-Symbol
> =1 haben?
Nun, das Jacobi-Symbol $(a/p)$ ist genau dann gleich 1, wenn $a$ ein quadratischer Rest modulo $p$ ist.
Damit haben alle quadratischen Reste das Jacobi-Symbol = 1.
LG Felix
|
|
|
| |
|
Ok, das habe ich verstanden...bzw. auch wieder nicht. Irgendwie verstehe ich den Sinn von dem Jacobi-Symbol nicht so richtig. Was sagt mir das eigentlich?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:35 Mi 21.03.2012 | | Autor: | felixf |
Moin!
> Ok, das habe ich verstanden...bzw. auch wieder nicht.
> Irgendwie verstehe ich den Sinn von dem Jacobi-Symbol nicht
> so richtig. Was sagt mir das eigentlich?
Das sagt dir, ob etwas ein quadratischer Rest ist oder nicht. Der Witz in der ganzen Sache liegt daran, dass man mit dem Jacobi-Symbol und dessen Rechenregeln effizient bestimmen kann, ob eine Zahl ein quadratischer Rest modulo $p$ ist oder nicht.
Nur Anhand der Definition ist das alles andere als einfach.
LG Felix
|
|
|
| |
|
Ok. Aber was nützt mir dann die Information, ob etwas ein quadratischer Rest ist oder eben nicht? Also ich habe da so meine Theorie aufgestellt^^ :
Das Jacobi-Symbol ist ja über das Legendre-Symbol definiert:
Definition von Legendre-Symbol:
Es sei a eine ganze Zahl. Für jede Primzahl p>2 heißt [mm] L_{p}(a)= a^{\bruch{p-1}{2}} [/mm] rmod p Legendre-Symbol von a und p.
Und wenn jetzt beispielsweise für das Jacobi-Symbol =0 raus kommt, heißt das
[mm] a^{\bruch{p-1}{2}} [/mm] rmod p =0 und somit kann der Klartext auch nur 0 bzw. p sein. (Im Falle von, dass p keine Primzahl ist, so werden die Legendre-Symbole über die Primfaktorzerlegung von p miteinander multipliziert).
Somit lässt der Klartext sich in diesem Fall leicht berechnen. Bei -1 und 1 gibt es ja viele Möglichkeiten und deswegen ist der Klartext nicht so leicht berechenbar.
??? Stimmt das so ???
Und dann haben wir einen Beweis dazu, dass bei dem RSA-Verfahren sich der Klartext auf den Chiffretext überträgt (deswegen ist RSA u.a. auch nicht sicher). Das heißt:
[mm] J_{n}(x^{e}) [/mm] = [mm] J_{n}(x) [/mm] n=pq, und p und q sind Primzahlen. x ist Element aus [mm] \IZ_{n}. [/mm] e ist ein Element aus [mm] \IZ_{m} [/mm] ^{*} und m= (p-1)(q-1) also ist e ungerade und lässt sich auch als e=2f+1 schreiben für f ist eine ganze Zahl.
Der Beweis dazu sieht folgendermaßen aus:
[mm] J_{n}(x^{e}) [/mm] = [mm] (J_{n} (x))^{e} [/mm] = [mm] (J_{n}(x))^{2f+1} [/mm] = [mm] ((J_{n}(x))^{2})^{f} [/mm] * [mm] J_{n}(x) [/mm] = [mm] J_{n}(x)
[/mm]
Ich verstehe den Schritt: [mm] ((J_{n} (x))^{2})^{f} [/mm] * [mm] J_{n}(x) [/mm] = [mm] J_{n}(x)
[/mm]
nicht so ganz. Könnte mir da jemand einen Ansatz zu geben? Denn das heißt doch, dass [mm] ((J_{n} (x))^{2})^{f} [/mm] = 1 ist, und ich verstehe nicht warum.
Vielleicht sollte ich noch zwei Lemmas dazu angeben:
1. Für jede ungerade Zahl n [mm] \in \IN [/mm] und jedes a [mm] \in \IZ [/mm] gilt:
i) [mm] J_{n}(a) \in [/mm] {-1,0,1}
ii) [mm] J_{n}(a)=0 [/mm] gdw. ggT(a,n) [mm] \not= [/mm] 1
2.
[mm] J_{n}(1) [/mm] = 1
[mm] J_{n}(-1) [/mm] = [mm] -1^{\bruch{n-1}{2}}
[/mm]
[mm] J_{n}(2) [/mm] = [mm] -1^{\bruch{n^2-1}{8}}
[/mm]
[mm] J_{n}(a) [/mm] = [mm] J_{n}(a [/mm] mod n)
[mm] J_{n}(ab) [/mm] = [mm] J_{n}(a) [/mm] * [mm] J_{n}(b)
[/mm]
[mm] J_{mn}(a) [/mm] = [mm] J_{m}(a)*J_{n}(a)
[/mm]
Jedenfalls steht beim Beweis, dass das alles aus den beiden Lemmas folgt. Aber ich verstehe wie gesagt den einen Schritt da nicht.
DANKE
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:17 Fr 23.03.2012 | | Autor: | rainerS |
Hallo!
> Und dann haben wir einen Beweis dazu, dass bei dem
> RSA-Verfahren sich der Klartext auf den Chiffretext
> überträgt (deswegen ist RSA u.a. auch nicht sicher). Das
> heißt:
> [mm]J_{n}(x^{e}) = J_{n}(x)[/mm] n=pq, und p und q sind
> Primzahlen. x ist Element aus [mm]\IZ_{n}.[/mm] e ist ein Element
> aus [mm]\IZ_{m}[/mm] ^{*} und m= (p-1)(q-1) also ist e ungerade und
> lässt sich auch als e=2f+1 schreiben für f ist eine ganze
> Zahl.
> Der Beweis dazu sieht folgendermaßen aus:
> [mm]J_{n}(x^{e}) = (J_{n} (x))^{e} = (J_{n}(x))^{2f+1} = ((J_{n}(x))^{2})^{f} * J_{n}(x) = J_{n}(x)[/mm]
>
> Ich verstehe den Schritt: [mm]((J_{n} (x))^{2})^{f} * J_{n}(x) = J_{n}(x)[/mm]
> nicht so ganz. Könnte mir da jemand einen Ansatz zu
> geben? Denn das heißt doch, dass [mm]((J_{n} (x))^{2})^{f} = 1[/mm]
> ist, und ich verstehe nicht warum.
Nicht ganz: es heisst, dass [mm]((J_{n} (x))^{2})^{f} = 1[/mm], wenn [mm]J_{n}(x)\not=0[/mm] .
> Vielleicht sollte ich noch zwei Lemmas dazu angeben:
>
> 1. Für jede ungerade Zahl n [mm]\in \IN[/mm] und jedes a [mm]\in \IZ[/mm]
> gilt:
> i) [mm]J_{n}(a) \in[/mm] {-1,0,1}
> ii) [mm]J_{n}(a)=0[/mm] gdw. ggT(a,n) [mm]\not=[/mm] 1
Aus [mm]J_{n}(x) \in \{-1,0,1\}[/mm] folgt doch [mm](J_{n} (x))^{2} \in \{0,1\}[/mm] und damit auch [mm] $((J_{n} (x))^{2} )^f\in\{0,1\}$. [/mm]
Also entweder [mm] $J_n(x)=0$, [/mm] dann ist [mm] $((J_{n} (x))^{2} )^f [/mm] = 0$, oder aber [mm] $J_n(x)\not=0$, [/mm] dann ist [mm] $((J_{n} (x))^{2} )^f [/mm] =1$. In beiden Fällen ist
[mm] ((J_{n} (x))^{2})^{f} * J_{n}(x) = J_n(x)[/mm]
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:57 Sa 24.03.2012 | | Autor: | judithlein |
Verstanden! Danke! :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Fr 23.03.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
