RSA-Algorithmus < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ich arbeite gerade an einer Ausarbeitung zum Thema RSA.
Mir ist vieles klar, jedoch verstehe ich ein kleines Detail nicht.
Hier gibt es eine kleine Übersicht wie RSA im groben funktioniert.
http://www.mathe-online.at/materialien/Franz.Embacher/files/RSA/
Der Text der verschlüsselt werden soll (im Beispiel oben ist das x), muss kleiner als n sein.
Um jedoch den Text wieder entschlüsseln zu können, muss man den Satz von Euler anwenden, der nur dann angewendet werden darf, wenn zwei Zahlen teilerfremd sind.
Also müssen beim entschlüsseln n (produkt 2er Primzahlen) und x teilerfremd sein.
Doch wie wird sichergestellt, dass x und n teilerfremd sind? Laut der Quelle ist es sichergestellt, sobald x kleiner als n ist.
n ist das Produkt 2er Primnzahlen und deshalb selbst wieder eine Primzahl. Doch n und x sind nicht teilerfremd, wenn x den selben Wert hat, wie eine der beiden Primzahlen.
Also müsste die Bedingung sein dass x kleiner n ist und ungleich den Primzahlen, jedoch darf der Kommunikationspartner nichts über die Primzahlen wissen, also wie wird das sonst sichergestellt?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
lg
|
|
| |
|
moin,
> Der Text der verschlüsselt werden soll (im Beispiel oben
> ist das x), muss kleiner als n sein.
>
> Um jedoch den Text wieder entschlüsseln zu können, muss
> man den Satz von Euler anwenden, der nur dann angewendet
> werden darf, wenn zwei Zahlen teilerfremd sind.
>
> Also müssen beim entschlüsseln n (produkt 2er Primzahlen)
> und x teilerfremd sein.
>
> Doch wie wird sichergestellt, dass x und n teilerfremd
> sind? Laut der Quelle ist es sichergestellt, sobald x
> kleiner als n ist.
Nein, das $x<n$ hat nichts damit zu tun, es sorgt nur dafür, dass man Eindeutigkeit beim Entschlüsseln erhält.
> n ist das Produkt 2er Primnzahlen und deshalb selbst wieder
> eine Primzahl.
Ich bin mir sicher das meinst du nicht so... :)
> Doch n und x sind nicht teilerfremd, wenn x
> den selben Wert hat, wie eine der beiden Primzahlen.
>
> Also müsste die Bedingung sein dass x kleiner n ist und
> ungleich den Primzahlen, jedoch darf der
> Kommunikationspartner nichts über die Primzahlen wissen,
> also wie wird das sonst sichergestellt?
Das $x$ dürfte auch kein Vielfaches der Primzahlen sein; also auch $2p$ wäre ein Problem.
Nehmen wir jetzt mal an $x=p$.
Es ist also zu zeigen [mm] $p^{m+1} \equiv [/mm] p [mm] \mod [/mm] n$.
Das kannst du - etwa mit Chinesischem Restsatz oder indem du diese Aussage in eine Teilbarkeitsaussage übersetzt - äquivalent umformen zu:
[mm] $p^{m+1} \equiv [/mm] p [mm] \mod [/mm] q
Hierfür brauchst du in erster Linie, dass $p$ und $q$ als verschiedene Primzahlen insbesondere teilerfremd sind.
Damit erhältst du:
[mm] $p^m [/mm] = [mm] p^{(p-1)(q-1)} [/mm] = [mm] (p^{q-1})^{p-1} \equiv 1^{p-1} \equiv [/mm] 1 [mm] \mod [/mm] q$ und damit durch Multiplikation mit $p$ die gewünschte Aussage.
Für $q$ und auch alle Vielfachen von $p$ bzw kannst du dann ähnlich verfahren, überlege dir dazu am besten noch mal ein wenig was allgemeines.
Überdies müsstest du meinen Weg von oben (wenn du ihn verwenden willst) noch ein wenig begründen, ich hab mich da absichtlich ein wenig kurz mit Begründungen und Argumenten gehalten; du sollst dich ja auch nicht langweilen.^^
lg
Schadow
|
|
|
| |
|
Ich bin nicht gut in Mathematik, deshalb werde ich aus deiner Antwort auch nicht wirklich schlau.
Könntest du deine Antwort eventuell anders formulieren, sodass man sie ohne viel mathematisches hintergrundwissen verstehen kann?
Wäre dir sehr verbunden
|
|
|
| |
|
Nun, den RSA ohne Mathematik zu beweisen könnte schwer bis unmöglich werden.
Du brauchst zum einen den Satz von Euler und Fermat, der dir eine Aussage trifft falls dein $x$ teilerfremd zum $n$ ist.
Ist $x$ nicht teilerfremd zu $n$ so wäre es sehr praktisch, wenn du den Chinesischen Restsatz kennen würdest.
Ohne machen wir den Fall $x=p$ mal folgendermaßen:
Zu zeigen ist:
[mm] $p^{m+1} [/mm] = p [mm] \mod [/mm] n$.
Dies lässt sich auch schreiben als
[mm] $p^{m+1} [/mm] - p = 0 [mm] \mod [/mm] n$ oder $n [mm] \mid p(p^m-1)$
[/mm]
Das heißt es ist zu zeigen:
[mm] $\frac{p(p^m-1)}{n}$ [/mm] ist eine ganze Zahl.
Dazu:
[mm] $\frac{p(p^m-1)}{n} [/mm] = [mm] \frac{p^m-1}{q}$
[/mm]
Also muss man zeigen:
[mm] $p^m \equiv [/mm] 1 [mm] \mod [/mm] q$
Hierfür schreiben wir [mm] $p^m [/mm] = [mm] (p^{q-1})^{p-1} \equiv 1^{p-1} [/mm] = 1 [mm] \mod [/mm] q$.
Dass [mm] $p^{q-1} \equiv [/mm] 1 [mm] \mod [/mm] q$ folgt wieder mit Euler & Fermat.
Also wie du siehst kommst du um den Euler & Fermat nicht drum herum.
Ist nun $x$ nicht teilerfremd zu $n$, so ist $x = ap$ oder $x = bq$ mit geeigneten natürlichen Zahlen $a,b$.
Also musst du (etwa so wie oben für $x=p$) zeigen, dass die Kongruenz auch für diese gilt.
Das sollte aber kein Problem sein, da du bei obiger Argumentation für $x=ap$ einfach ein $a$ ausklammern kannst; dann hast du wieder den Fall $x=p$.
lg
Schadow
|
|
|
| |
|
Ich verstehe leider nicht worauf du hinauswillst.
Ich finde auch relativ wenig im Internet über genau diese Problemstellung.
Ist es so logisch, und ich verstehe es nicht, oder ist es kompliziert das sich keiner in einer AUsarbeitung richtig damit auseinandersetzt?
Folgendes Weis ich jetzt:
Falls x und n teilerfremd sind, liefert mir der Satz von Euler eine Aussage.
Falls x und n nicht teilerfremd sind, muss man sich die Zahlen ansehen, für welche dies zutreffen kann, diese wären dann 0 p und q.
Für 0 ist mir der Fall klar.
Und was muss ich jetzt genau mit p und q machen? Was sagen deine Behauptungen/Beweise aus? Gehts/Gehts nicht?
Könntest du, so banal es klingen mag, bei jedem Schritt angeben welchen Satz du verwendest bzw warum du das so machst.
Info: Anhand meinen Fragen könnt ihr sehen dass ich relativ wenig Ahnung habe, jedoch muss ich genau diese Ausarbeitung machen um diesen Kurs zu schaffen. VOm Professor bekommen wir nix vermittelt, dadurch auch die schlechten Kenntnisse.
Ich arbeite wie gesagt an einer Ausarbeitung, eventuell würde es leichter gehen wenn ich dir die Ausarbeitung per Mail zukommen lasse, und dir genau sage wo das Problem liegt, würde mir sehr helfen (könntest mir deine Email per PN schicken).
Ich würde auch dann hier einen Lösungsbericht verfassen.
|
|
|
| |
|
Sehe ich das richtig, das sobald T und n nicht teilerfremd sind, der Satz von Euler nicht angewendet werden kann.
ANstatt dessen muss man das dann mit dem Chinesischen Restsatz machen.
Hierzu habe ich folgende Vorgehensweise gefunden:
T=Klartext; g=Geheimtext; d=privater schlüssel; n = p*q
Man teilt nun T auf 2 Elemente auf, mit der Begründung dass wenn etwas duch p teilbar ist, es auch durch ein Vielfaches davon Teilbar sein muss wie n=p*q
d ersetzt man durch d mod (p-1) aufgrund des kleinen satzes von Fermat.
Tp = [mm] (G^d [/mm] mod n)mod p = [mm] (G^d [/mm] mod(p-1))mod p
Tq = [mm] (G^d [/mm] mod n)mod q = [mm] (G^d [/mm] mod(q-1))mod q
T = (Tp * Sigma * p + Tq * Pi * q) modn
Ist das soweit richtig?
Wenn ja: welche Werte werden dann für p und q verwendet?
Weiters steht dass die Werte für Sigma und Pi mit dem erweiterten euklidschen ALgorithmus berechnet werden können. Wie ist da vorzugehen?
Wenn nein: warum nicht?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:16 Mi 05.09.2012 | | Autor: | rainerS |
Hallo!
> Sehe ich das richtig, das sobald T und n nicht teilerfremd
> sind, der Satz von Euler nicht angewendet werden kann.
Nein, das stimmt so nicht ganz. Der Satz von Euler hat zwar die Voraussetzung, dass T und n teilerfremd sein müssen, aber beim RSA-Algorithmus geht es um einen Spezialfall des Satzes von Euler, nämlich dass $n=p*q$ das Produkt zweier Primzahlen p und q ist. Dann folgt tatsächlich aus dem Satz von Euler, dass die Aussage auch dann richtig ist, wenn T und gemeinsame Teiler haben. (Den chinesischen Restsatz braucht man für den Beweis gar nicht.)
> ANstatt dessen muss man das dann mit dem Chinesischen
> Restsatz machen.
>
> Hierzu habe ich folgende Vorgehensweise gefunden:
>
> T=Klartext; g=Geheimtext; d=privater schlüssel; n = p*q
>
> Man teilt nun T auf 2 Elemente auf, mit der Begründung
> dass wenn etwas duch p teilbar ist, es auch durch ein
> Vielfaches davon Teilbar sein muss wie n=p*q
Das ist ganz falsch. Beispiel: p=5, q=2, T=25. T ist durch p teilbar, aber nicht durch p*q.
> d ersetzt man durch d mod (p-1) aufgrund des kleinen
> satzes von Fermat.
Da verstehe ich überhaupt nicht, was du meinst. Schreib mal auf, wo du das herhast.
Viele Grüße
Rainer
|
|
|
| |
|
Hallo Rainer,
danke für deine Antwort.
>> wenn T und gemeinsame Teiler haben
Du meinst hier vermutlich T und n?
Wie kann ich diese spezialisierung vom Satz von Euler definieren, bzw. ausdrücken dass es sich dabei um einen Spezialfall handelt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:33 Do 06.09.2012 | | Autor: | rainerS |
Hallo!
> Hallo Rainer,
>
> danke für deine Antwort.
>
> >> wenn T und gemeinsame Teiler haben
>
> Du meinst hier vermutlich T und n?
Ja.
> Wie kann ich diese spezialisierung vom Satz von Euler
> definieren, bzw. ausdrücken dass es sich dabei um einen
> Spezialfall handelt?
Der Spezialfall ist doch vorgegeben dadurch, dass n das Produkt zweier Primzahlen p und q ist.
Und der Punkt ist, dass du zeigen musst, dass
[mm] T^{k(p-1)(q-1)+1 } \equiv T \pmod{n} [/mm]
für alle ganzen Zahlen k ist.
Entweder T und n sind teilerfremd, dann kannst du den Satz von Euler direkt anwenden.
Aber aber sie haben einen gemeinsamen Teiler, dann ist wegen $T<n$ T entweder ein Vielfaches von p oder von q.
Sei T ein Vielfaches von p. Dann ist [mm] $T\equiv 0\pmod [/mm] p$ und daher auch
[mm] T^{k(p-1)(q-1)+1} \equiv T \pmod{p} [/mm]
Außerdem gilt
[mm] T^{k(p-1)(q-1)+1} = T^{k(p-1)(q-1)} * T = (T^{q-1})^{k(p-1)} * T [/mm] .
Nach dem Satz von Euler ist
[mm] T^{q-1} \equiv 1 \pmod{q} [/mm],
und daher
[mm] (T^{q-1})^{k(p-1)} \equiv 1^{k(p-1)} \equiv 1 \pmod q [/mm] .
Eingesetzt:
[mm] T^{k(p-1)(q-1)+1} \equiv 1* T \equiv T \pmod q [/mm] .
Da [mm] $T^{k(p-1)(q-1)+1} \equiv [/mm] T [mm] \pmod{p}$ [/mm] und [mm] $T^{k(p-1)(q-1)+1} \equiv [/mm] T [mm] \pmod{q}$, [/mm] gilt auch
[mm] T^{k(p-1)(q-1)+1} \equiv T \pmod{p*q} [/mm] .
Das steht auch in jedem Buch über den RSA-Algorithmus.
Viele Grüße
Rainer
|
|
|
| |
|
Ok hört sich eigentlich ganz logisch an =)
Nur bezüglich dem k:
Sagt dieses aus, dass es eben für alle Zahlen k gültig sein soll, und nicht nur für Zahlen die Teilerfremd sind zu n?
Wenn nein, was sagt es genau aus?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Sa 08.09.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
> Ich verstehe leider nicht worauf du hinauswillst.
>
> Ich finde auch relativ wenig im Internet über genau diese
> Problemstellung.
Für so einen Fall gibt es immer noch Bücher.
In jeder gut ausgestatteten Unibibliothek findest du Material zum RSA.
Wenn du einen mathematischen Beweis suchst könnte ein Buch über elementare Zahlentheorie oder über Kryptographie ganz ratsam sein.
Hier entweder den Prof fragen (auch wenn er dir nicht hilft so kann er dir vielleicht Quellen empfehlen) oder mal die Inhaltsverzeichnisse einiger Bücher in der Bibliothek durchsehen.
> Ist es so logisch, und ich verstehe es nicht, oder ist es
> kompliziert das sich keiner in einer AUsarbeitung richtig
> damit auseinandersetzt?
Es gibt sicher einige Ausarbeitungen darüber; aber frag mich nicht wo genau.
> Folgendes Weis ich jetzt:
>
> Falls x und n teilerfremd sind, liefert mir der Satz von
> Euler eine Aussage.
genau
> Falls x und n nicht teilerfremd sind, muss man sich die
> Zahlen ansehen, für welche dies zutreffen kann, diese
> wären dann 0 p und q.
Nein.
Die Zahlen $0,p,q$ sind ein paar Kandidaten, aber längst nicht alle.
So ist etwa auch $2p$ nicht teilerfremd zu $n=pq$; auf die Art bekommst du noch mit allen Vielfachen von $p$ und $q$ ein paar Probleme.
> Für 0 ist mir der Fall klar.
>
> Und was muss ich jetzt genau mit p und q machen? Was sagen
> deine Behauptungen/Beweise aus? Gehts/Gehts nicht?
Doch, es geht.
> Könntest du, so banal es klingen mag, bei jedem Schritt
> angeben welchen Satz du verwendest bzw warum du das so
> machst.
>
> Info: Anhand meinen Fragen könnt ihr sehen dass ich
> relativ wenig Ahnung habe, jedoch muss ich genau diese
> Ausarbeitung machen um diesen Kurs zu schaffen. VOm
> Professor bekommen wir nix vermittelt, dadurch auch die
> schlechten Kenntnisse.
Es ist normal, dass man sich für eine Ausarbeitung selbst Wissen aneignen muss; auch ggf. selbst Quellen/Bücher zu Rate ziehen.
Wenn ihr die ganzen Sätze (Euler & Fermat, Chinesischer Restsatz, etc.) noch nicht hattet würde ich mich rechtzeitig beim Prof informieren, ob du diese einfach ohne Beweis verwenden darfst.
Einen Beweis der beiden solltest du in jedem besseren Buch zur Linearen Algebra finden.
Dann gucken wir uns das aus meinem vorherigen Post nochmal genau an:
Ich mache hier den Kandidaten $p$, der ja nicht teilerfremd zu $n$ ist.
Auf sehr ähnliche Art kannst du das ganze für $a*p$ beweisen für eine beliebige ganze Zahl $a$ oder für $a*q$.
> Zu zeigen ist:
> $ [mm] p^{m+1} [/mm] = p [mm] \mod [/mm] n $.
Ist dir klar, wieso das gezeigt werden muss?
> Dies lässt sich auch schreiben als
> $ [mm] p^{m+1} [/mm] - p = 0 [mm] \mod [/mm] n $ oder $ n [mm] \mid p(p^m-1) [/mm] $
Hier habe ich im ersten Schritt die Rechengesetze für modulo verwendet und im zweiten Schritt benutzt, dass eine Zahl genau dann kongruent zu $0 [mm] \mod [/mm] n$ ist, wenn sie durch $n$ geteilt wird.
> Das heißt es ist zu zeigen:
> $ [mm] \frac{p(p^m-1)}{n} [/mm] $ ist eine ganze Zahl.
Die Aussage, dass $n [mm] \mid p(p^m-1)$ [/mm] lässt sich auch so wie hier schreiben, denn $n$ teilt diese Zahl genau dann wenn obiger Bruch eine ganze Zahl ist.
> Dazu:
> $ [mm] \frac{p(p^m-1)}{n} [/mm] = [mm] \frac{p^m-1}{q} [/mm] $
Bedenkst du, dass $n=pq$ sollte klar sein, wieso sich dies so kürzen lässt.
Jetzt lässt sich dies wie oben wieder umschreiben zu $q [mm] \mid p^m-1$, [/mm] da unser Bruch nach wie vor eine ganze Zahl ergeben soll.
In Moduloschreibweise wäre dies
[mm] $p^m-1 \equiv [/mm] 0 [mm] \mod [/mm] q$ oder:
> $ [mm] p^m \equiv [/mm] 1 [mm] \mod [/mm] q $
Benutze nun $m = (p-1)(q-1)$, die Potenzgesetze und schließlich wiederum Euler & Fermat, in diesem Fall ist [mm] $\phi(q) [/mm] = q-1$.
> Hierfür schreiben wir $ [mm] p^m [/mm] = [mm] (p^{q-1})^{p-1} \equiv 1^{p-1} [/mm] = 1 [mm] \mod [/mm] q $.
> Dass $ [mm] p^{q-1} \equiv [/mm] 1 [mm] \mod [/mm] q $ folgt wieder mit Euler & Fermat.
Da [mm] $p^m \equiv [/mm] 1 [mm] \mod [/mm] q$ eine wahre Aussage ist, ist auch die Aussage ganz vom Anfang [mm] ($p^{m+1} \equiv [/mm] p [mm] \mod [/mm] n$) eine wahre Aussage.
Wie gesagt lässt sich für $a*p$ oder $a*q$ für beliebige ganze Zahl $a$ fast der gleiche Beweis verwenden.
lg
Schadow
|
|
|
| |
|
...Ist dir klar, wieso das gezeigt werden muss? ...
Nein leider nicht.
Wenn du mir das noch kurz sagen könntest, sehe ich mir den Rest morgen mal genauer an.
Danke
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:20 Fr 07.09.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
