Kongruenz < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:12 Mo 02.02.2015 | | Autor: | Ellie123 |
| Aufgabe | | Seien s,p [mm] \in \IN= \left\{ 1,2,... \right\} [/mm] und f,m [mm] \im \IZ \left[ X \right], [/mm] dann gilt pf+m [mm] \equiv [/mm] m (mod sp) |
Hallo zusammen,
ich möchte gerne die folgende Aussage beweisen, da ich denke, dass dies gehen müsste. Allerdings weiß ich nicht so richtig wie dies gehen könnte. Ich hatte schon an vollständige Induktion über s gedacht. Bin damit aber auch nicht wirklich weitergekommen.
Kann mir jemand helfen?
Viele Grüße, Ellie
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:16 Mo 02.02.2015 | | Autor: | felixf |
Moin!
> Seien s,p [mm]\in \IN= \left\{ 1,2,... \right\}[/mm] und f,m [mm]\im \IZ \left[ X \right],[/mm]
> dann gilt pf+m [mm]\equiv[/mm] m (mod sp)
Setze $f = 1$, $m = 0$. Dann steht da $p [mm] \equiv [/mm] 0 [mm] \pmod{s p}$. [/mm] Das ist genau dann wahr, wenn $s = 1$ ist.
Wenn allerdings $s = 1$ ist, dann ist die Aussage immer wahr.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:23 Di 03.02.2015 | | Autor: | Ellie123 |
Hallo,
leider ist mir nicht klar, was du mir damit
> Setze [mm]f = 1[/mm], [mm]m = 0[/mm]. Dann steht da [mm]p \equiv 0 \pmod{s p}[/mm].
> Das ist genau dann wahr, wenn [mm]s = 1[/mm] ist.
>
> Wenn allerdings [mm]s = 1[/mm] ist, dann ist die Aussage immer
> wahr.
>
> LG Felix
>
sagen willst. Warum betrachtest du diesen Sonderfall f=1 und m=0?
Mittlerweile frage ich mich auch, ob man meine ursprüngliche Aussage überhaupt beweisen kann? Und wenn ja wie? Ist die Idee mit der vollständigen Induktion total falsch?
Kann mir jemand weiterhelfen?
Grüße, Ellie
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:29 Di 03.02.2015 | | Autor: | hippias |
Das fragst Du Dich zu recht, denn die Aussage ist unter den gemachten Vorassetzungen falsch: betrachte etwa $s=1$, $p=3$, $f= 5$ und $m=0$ als Gegenbeispiel.
Vielleicht koenntest Du den Kontext posten, dann laesst sich vielleicht erraten, was tatsaechlich gemeint ist.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:57 Di 03.02.2015 | | Autor: | Ellie123 |
Hallo,
wenn ich aber die von dir gegeben Zahlen
>[mm]s=1[/mm], [mm]p=3[/mm],
> [mm]f= 5[/mm] und [mm]m=0[/mm] als Gegenbeispiel.
einsetze, komme ich doch auf 15 [mm] \equiv [/mm] 0 (mod3). Und das ist doch eine wahre Aussage.
> Vielleicht koenntest Du den Kontext posten, dann laesst
> sich vielleicht erraten, was tatsaechlich gemeint ist.
Genau genommen geht es bei meiner Frage um das NTRU Kryptosystem. Dabei ist die verschlüsselte Nachricht gegeben durch [mm] p\phi [/mm] * h +m. p ist wieder eine natürliche Zahl, [mm] \phi, [/mm] h und m sind Polynome aus [mm] \IZ \left[ X \right]. [/mm] Das Polynom m stellt die Klartextnachricht dar. Mit * ist die Bildung des Konvolutionsproduktes gemeint ist, wie sie in
ftp://ftp.informatik.uni-stuttgart.de/pub/library/medoc.ustuttgart_fi/DIP-3286/DIP-3286.pdf
beschrieben ist. Die Koeffizienten von der verschlüsselten Nachricht [mm] p\phi [/mm] * h +m werden dann aber noch als Elemente aus [mm] \IZ [/mm] /q [mm] \IZ [/mm] aufgefasst.
Es wird dann beim NTRU Verfahren gesagt, dass falls p |q gilt (also q=sp), es leicht möglich ist, eine verschlüsselte Nachricht zu dechiffrieren, also m herauszubekommen.
Das wollte ich eigentlich ursprünglich zeigen und habe das ganze versucht vereinfacht darzustellen.
Ellie
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:03 Di 03.02.2015 | | Autor: | hippias |
> Hallo,
> wenn ich aber die von dir gegeben Zahlen
> >[mm]s=1[/mm], [mm]p=3[/mm],
> > [mm]f= 5[/mm] und [mm]m=0[/mm] als Gegenbeispiel.
>
> einsetze, komme ich doch auf 15 [mm]\equiv[/mm] 0 (mod3). Und das
> ist doch eine wahre Aussage.
Richtig, ich habe mich geirrt. Aber trotzdem findest Du jetzt sicher selbst leicht ein Gegenbeispiel.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:13 Di 03.02.2015 | | Autor: | Ellie123 |
Ja, ich könnte z.B. p=4, f=1 , m=7 und s=2 setzen. Dann bekomme ich 11 [mm] \equiv [/mm] 7 (mod8) raus, was ja eine unwahre Aussage ist.
Kann mir jemand denn etwas zu meiner eigentlichen Frage bezüglich des NTRU Verfahrens, etwas sagen? Ich komme da nämlich alleine leider nicht weiter?!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:03 Di 03.02.2015 | | Autor: | Teufel |
Hi!
Ok, also wir bekommen die verschlüsselte Nachricht [mm] $e=p\phi h+m\in\IZ_q[X]/(X^N-1)\cong \IZ[X]/(q,X^N-1)$, [/mm] d.h. wir betrachten [mm] $p\phi [/mm] h+m$ nicht nur modulo $q$, sondern auch modulo dem Polynom [mm] $X^N-1$.
[/mm]
Wenn nun p|q gilt, dann haben wir für alle ganzen Zahlen a,b: [mm] a\equiv b\mod{q} \Rightarrow a\equiv b\mod{p} [/mm] (warum?).
Im Chiffretext [mm] $e=p\phi [/mm] h+m [mm] \mod{(q,X^N-1)}$ [/mm] sind nun die Koeffizienten von [mm] $p\phi [/mm] h$ durch $p$ teilbar. Wenn man also einfach die Koeffizienten von $e$ modulo $p$ ausrechnet, fliegt [mm] $p\phi [/mm] h$ weg und [mm] m\mod{(p,X^N-1)} [/mm] bleibt über.
Wieso können wir daraus nun wieder leicht [mm] m\mod{(q,X^N-1)} [/mm] bestimmen bzw. die richtige Nachricht $m$ bestimmen?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:17 Mi 04.02.2015 | | Autor: | Ellie123 |
Hallo,
vielen Dank für die Antworten. Leider steige ich aber immer noch nicht ganz durch.
> Hi!
>
> Ok, also wir bekommen die verschlüsselte Nachricht [mm]e=p\phi h+m\in\IZ_q[X]/(X^N-1)\cong \IZ[X]/(q,X^N-1)[/mm],
> d.h. wir betrachten [mm]p\phi h+m[/mm] nicht nur modulo [mm]q[/mm], sondern
> auch modulo dem Polynom [mm]X^N-1[/mm].
>
> Wenn nun p|q gilt, dann haben wir für alle ganzen Zahlen
> a,b: [mm]a\equiv b\mod{q} \Rightarrow a\equiv b\mod{p}[/mm]
> (warum?).
Es gilt dann a=kq+r und b=mq+r für k,m,r [mm] \in \IN. [/mm] Und da p|q gibt es ein s [mm] \in \IN, [/mm] so dass ps=q. Wir können deshalb a und b auch schreiben als a=kps+r und b=mps+r. Damit ist der Rest, der bei Division von a und b durch p übrig bleibt, derselbe, nämlich: r mod p
> Im Chiffretext [mm]e=p\phi h+m \mod{(q,X^N-1)}[/mm] sind nun die
> Koeffizienten von [mm]p\phi h[/mm] durch [mm]p[/mm] teilbar. Wenn man also
> einfach die Koeffizienten von [mm]e[/mm] modulo [mm]p[/mm] ausrechnet, fliegt
> [mm]p\phi h[/mm] weg und [mm]m\mod{(p,X^N-1)}[/mm] bleibt über.
>
> Wieso können wir daraus nun wieder leicht [mm]m\mod{(q,X^N-1)}[/mm]
> bestimmen bzw. die richtige Nachricht [mm]m[/mm] bestimmen?
Hier komme ich nicht so richtig weiter. Es kann auch sein, dass ich etwas grundlegend nicht verstanden habe. Wenn ich die Koeffizienten von [mm] e=p\phi [/mm] h+m modulo p ausrechne, fällt [mm] p\phi [/mm] h weg. Das kann ich wohl nachvollziehen. Aber die Koeffizienten von m (also der Klartextnachricht), verändern sich doch auch, zumindest, wenn sie [mm] \ge [/mm] p sind. D.h. doch dass verschiedenartige Koeffizienten aus der Klartextnachricht zu gleichen Koeffizienten werden können, wenn ich modulo p reduziere. Also, ich weiß nicht, wie ich daraus wieder die Klartextnachricht gewinnen kann?
Ich hoffe ich habe mich verständlich ausgedrückt und es kann mir nochmal wer weiterhelfen.
Viele Grüße, Ellie
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:12 Mi 04.02.2015 | | Autor: | Teufel |
Hi!
Genau, so kann man das machen. Der Knackpunkt ist jetzt, dass $m$ nur 0 und 1 als Koeffizienten hat, also z.B. für $N=5$ eben [mm] $m=X^4+X^3+1$, [/mm] was der Nachricht 11001 entsprechen könnte.
Und diese Koeffizienten bleiben gleich, wenn man modulo einer kleineren Zahl rechnet. Wenn $m$ beliebige Koeffizienten hätte, wäre das nicht so einfach Möglich, wie du schon richtig erkannt hast. Aber für Zahlen $<p$ ist das ok.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:42 Do 05.02.2015 | | Autor: | Ellie123 |
Hallo nochmal,
Ich habe nochmal eine Frage, zu dem was du geschrieben hast.
> Hi!
>
> Ok, also wir bekommen die verschlüsselte Nachricht [mm]e=p\phi h+m\in\IZ_q[X]/(X^N-1)\cong \IZ[X]/(q,X^N-1)[/mm],
> d.h. wir betrachten [mm]p\phi h+m[/mm] nicht nur modulo [mm]q[/mm], sondern
> auch modulo dem Polynom [mm]X^N-1[/mm].
>
> Wenn nun p|q gilt, dann haben wir für alle ganzen Zahlen
> a,b: [mm]a\equiv b\mod{q} \Rightarrow a\equiv b\mod{p}[/mm]
> (warum?).
> Im Chiffretext [mm]e=p\phi h+m \mod{(q,X^N-1)}[/mm] sind nun die
> Koeffizienten von [mm]p\phi h[/mm] durch [mm]p[/mm] teilbar. Wenn man also
> einfach die Koeffizienten von [mm]e[/mm] modulo [mm]p[/mm] ausrechnet, fliegt
> [mm]p\phi h[/mm] weg und [mm]m\mod{(p,X^N-1)}[/mm] bleibt über.
>
> Wieso können wir daraus nun wieder leicht [mm]m\mod{(q,X^N-1)}[/mm]
> bestimmen bzw. die richtige Nachricht [mm]m[/mm] bestimmen?
>
Was meinst du damit, dass man aus [mm] m\mod{(p,X^N-1)} [/mm] wieder [mm] m\mod{(q,X^N-1)} [/mm] bzw. die Klartextnachricht bestimmen kann? Ich würde jetzt denken, dass wenn p|q und man die verschlüsselte Nachricht [mm] e=p\phi [/mm] h+m [mm] \mod{(q,X^N-1)} [/mm] modulo p reduziert, man dann bereits die ursprüngliche Nachricht wiederbekommt.
Also, was genau meinst du mit aus [mm] m\mod{(p,X^N-1)} [/mm] wieder [mm] m\mod{(q,X^N-1)} [/mm] bestimmen?
Ich kann mir auch nach wie vor nicht vorstellen, wie ein Beweis der Aussage konkret aussehen kann? Kann mir jemand weiterhelfen? Ich wäre sehr, sehr dankbar.
Viele Grüße,
Ellie
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:33 Do 05.02.2015 | | Autor: | Teufel |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Na, wenn du deinen Chiffretext modulo p bestimmst, dann fällt ja das $p\phi h$ weg und du bekommst $m \mod{(p,X^N-1)$. Aber davor hast du ja immer \mod{q} und nicht \mod{p} gerechnet. Aber ja, du bekommst in dem Fall das m trotzdem wieder, eben weil die Koeffizienten von $m$ nur 0 und 1 sind.
Ein beispiel wo das nicht klappen würde, wäre z.B. für q=12, p=6, \phi=h=1, m=7\mod{q}.
Dann hast du c=p*\phi*h+m=13=1\mod{q} und das Rechnen \mod{p} würde m=1\mod{p} liefern, was auch stimmt, aber keiner könnte genau sagen, dass eigentlich m=7\mod{q} gilt. Aber wenn die Koeffizienten von $m$ eh alle kleiner als $p$ sind, ist das egal.
|
|
|
|
