RSA-Angriff < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:36 Do 22.01.2009 | | Autor: | Bob1982 |
| Aufgabe | Der öffentliche Schlüssel sei (n,e) mit n=pq (p,q prim) und e der Verschlüsselungsexponent der Nachricht m mit Schlüsseltext [mm]c=m^e[/mm] mod n wobei [mm]e \cdot d \equiv\ 1\ mod\ \varphi(n) [/mm] gilt mit Entschlüsselungsexponent d.
z.z.:
a) Es existiert eine natürliche Zahl k, so dass [mm]m^{e^k} \equiv\ m\ mod\ n[/mm] für jeden Klartext m aus {0,1,...,n-1}
b) Für das k aus a) gilt [mm]c^{e^{k-1}} \equiv\ m\ mod\ n[/mm] so dass man theoretisch ganz einfach mit bekanntem k an die Nachricht m kommen kann.
Theoretische Fragestellungen ohne Beweis:
c) Wie könnte man ohne das Wissen von d Kandidaten für k herausfinden ?
d) Was muss man vermeiden um den oben geschilderten Angriff wirklungslos zu machen ?
|
Hallo,
wie der Titel schon verrät geht es um eine Anwendungsaufgabe zur Zahlentheorie aus der Kryptographie, hier meine Gedanken zu der AUfgabe:
zu a)
Hier würde ich auf [mm]e^k \equiv\ 1\ mod\ \varphi(n)[/mm] folgern, wodurch ich noch zeigen müsste, dass [mm]e^k[/mm] ein Iverses besitzt oder die Lösung direkt mit k=r((p-1)(q-1)-1)=r(pq-p-q) angeben ?
zu b)
Damit müsste ja [mm]e^{k-1} \equiv\ d\ mod\ \varphi(n)[/mm] gelten, was wegen [mm]e^k=1=ed<=>e^{k-1}=d[/mm] ja dann hinkommen würde oder ?
zu c) und d) habe ich noch keine Ideen, was wäre hier zu beachten ?
Gruß Björn
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:29 Do 22.01.2009 | | Autor: | felixf |
Hallo
> Der öffentliche Schlüssel sei (n,e) mit n=pq (p,q prim) und
> e der Verschlüsselungsexponent der Nachricht m mit
> Schlüsseltext [mm]c=m^e[/mm] mod n wobei [mm]e \cdot d \equiv\ 1\ mod\ \varphi(n)[/mm]
> gilt mit Entschlüsselungsexponent d.
>
> z.z.:
>
> a) Es existiert eine natürliche Zahl k, so dass [mm]m^{e^k} \equiv\ m\ mod\ n[/mm]
> für jeden Klartext m aus {0,1,...,n-1}
>
> b) Für das k aus a) gilt [mm]c^{e^{k-1}} \equiv\ m\ mod\ n[/mm] so
> dass man theoretisch ganz einfach mit bekanntem k an die
> Nachricht m kommen kann.
>
> Theoretische Fragestellungen ohne Beweis:
>
> c) Wie könnte man ohne das Wissen von d Kandidaten für k
> herausfinden ?
>
> d) Was muss man vermeiden um den oben geschilderten Angriff
> wirklungslos zu machen ?
>
> Hallo,
>
> wie der Titel schon verrät geht es um eine
> Anwendungsaufgabe zur Zahlentheorie aus der Kryptographie,
> hier meine Gedanken zu der AUfgabe:
>
>
> zu a)
>
> Hier würde ich auf [mm]e^k \equiv\ 1\ mod\ \varphi(n)[/mm] folgern,
Wieso willst du das daraus folgern? Es reicht doch wenn dies der Fall ist (warum eigentlich?).
> wodurch ich noch zeigen müsste, dass [mm]e^k[/mm] ein Iverses
> besitzt oder die Lösung direkt mit
> k=r((p-1)(q-1)-1)=r(pq-p-q) angeben ?
Wieso sollte das eine Loesung sein? Und was ist $r$?
Was weisst du ueber $e$ in Relation zu [mm] $\varphi(n)$? [/mm] Sagt dir der kleine Satz von Fermat was?
> zu b)
>
> Damit müsste ja [mm]e^{k-1} \equiv\ d\ mod\ \varphi(n)[/mm] gelten,
Wieso sollte das daraus folgen? Es reicht doch voellig aus dass du mit dieser Aussage die Behaputung zeigen kannst. Dazu brauchst du doch nicht erst irgendwas behaupten was nachher moeglicherweise gar nicht stimmt, oder was du zumindest gar nicht beweist.
> was wegen [mm]e^k=1=ed<=>e^{k-1}=d[/mm] ja dann hinkommen würde oder
> ?
Warum wuerde das hinkommen? (Ja, das stimmt so, aber etwas argumentieren musst du schon -- warum kannst du einfach kuerzen? Du rechnest ja modulo [mm] $\varphi(n)$ [/mm] und nicht in den ganzen Zahlen!
> zu c) und d) habe ich noch keine Ideen, was wäre hier zu
> beachten ?
Bei c) musst du dir selber mal Gedanken machen.
Bei d) beachte allerdings, was fuer $k$ gelten sollte, damit [mm] $e^k \equiv [/mm] 1 [mm] \pmod{\varphi(n)}$ [/mm] gilt. Stichwort: Ordnung.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:15 Do 22.01.2009 | | Autor: | Bob1982 |
| Aufgabe | z.z.:
>
> a) Es existiert eine natürliche Zahl k, so dass $ [mm] m^{e^k} \equiv\ [/mm] m\ mod\ n $
> für jeden Klartext m aus {0,1,...,n-1}
>
> b) Für das k aus a) gilt $ [mm] c^{e^{k-1}} \equiv\ [/mm] m\ mod\ n $ so
> dass man theoretisch ganz einfach mit bekanntem k an die
> Nachricht m kommen kann.
>
> Theoretische Fragestellungen ohne Beweis:
>
> c) Wie könnte man ohne das Wissen von d Kandidaten für k
> herausfinden ?
>
> d) Was muss man vermeiden um den oben geschilderten Angriff
> wirklungslos zu machen ? |
> > zu a)
> >
> > Hier würde ich auf [mm]e^k \equiv\ 1\ mod\ \varphi(n)[/mm] folgern,
>
> Wieso willst du das daraus folgern? Es reicht doch wenn
> dies der Fall ist (warum eigentlich?).
Willst du darauf hinaus, dass ich ja noch gar nicht weiss ob die in der Aufgabe erwähnte Kongruenz gilt und nun erstmal davon ausgehe, sie gelte nicht und das dann zum Widerspruch führe, wodurch sie dann wahr sein muss ?
> > wodurch ich noch zeigen müsste, dass [mm]e^k[/mm] ein Iverses
> > besitzt oder die Lösung direkt mit
> > k=r((p-1)(q-1)-1)=r(pq-p-q) angeben ?
>
> Wieso sollte das eine Loesung sein? Und was ist [mm]r[/mm]?
Hast Recht, das stimmt nicht so ganz, es sollte eine Lösung für k wegen [mm] k \equiv 0\ mod\ \varphi(\varphi(n))[/mm] sein aber das kommt nicht so ganz hin. r sollte das ganzzahlige Vielfache ausdrücken.
> Was weisst du ueber [mm]e[/mm] in Relation zu [mm]\varphi(n)[/mm]? Sagt dir
> der kleine Satz von Fermat was?
Schon, nur der kleiner Fermat gilt doch nur für prime Modulos und [mm]\varphi(n)[/mm] muss ja nicht prim sein wenn man jetzt [mm]e^k \equiv\ 1\ mod\ \varphi(n)[/mm] betrachtet oder auf welche Kongruenz spielst du an ? [mm]e^{\varphi(n)}[/mm] wäre nach Euler-Fermat kongruent 1 modulo n, aber darum geht es hier ja nicht oder ?
> > zu b)
> >
> > Damit müsste ja [mm]e^{k-1} \equiv\ d\ mod\ \varphi(n)[/mm] gelten,
>
> Wieso sollte das daraus folgen? Es reicht doch voellig aus
> dass du mit dieser Aussage die Behaputung zeigen kannst.
> Dazu brauchst du doch nicht erst irgendwas behaupten was
> nachher moeglicherweise gar nicht stimmt, oder was du
> zumindest gar nicht beweist.
>
> > was wegen [mm]e^k=1=ed<=>e^{k-1}=d[/mm] ja dann hinkommen würde oder
> > ?
>
> Warum wuerde das hinkommen? (Ja, das stimmt so, aber etwas
> argumentieren musst du schon -- warum kannst du einfach
> kuerzen? Du rechnest ja modulo [mm]\varphi(n)[/mm] und nicht in den
> ganzen Zahlen!
Durch Linksmultiplikation von [mm]e^{-1}[/mm] folgt das in meinen Augen.
>
> > zu c) und d) habe ich noch keine Ideen, was wäre hier zu
> > beachten ?
>
> Bei c) musst du dir selber mal Gedanken machen.
Ich hatte an die Verfahren zur Berechnung diskreter Logarithmen gedacht (Shank, Index Calculus...etc)
> Bei d) beachte allerdings, was fuer [mm]k[/mm] gelten sollte, damit
> [mm]e^k \equiv 1 \pmod{\varphi(n)}[/mm] gilt. Stichwort: Ordnung.
Wenn k die Ordnung des Elements e wäre, dann müsste dieses gleichzeitig das kleinste k sein, für welches diese Kongurenz gilt.
Nach Euler-Fermat fällt mir auch wieder dasselbe Argument wie oben ein.
Gruß Björn
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 03:23 Sa 24.01.2009 | | Autor: | felixf |
Hallo
> > a) Es existiert eine natürliche Zahl k, so dass [mm]m^{e^k} \equiv\ m\ mod\ n[/mm]
> > für jeden Klartext m aus {0,1,...,n-1}
> >
> > b) Für das k aus a) gilt [mm]c^{e^{k-1}} \equiv\ m\ mod\ n[/mm] so
> > dass man theoretisch ganz einfach mit bekanntem k an
> > die Nachricht m kommen kann.
> >
> > Theoretische Fragestellungen ohne Beweis:
> >
> > c) Wie könnte man ohne das Wissen von d Kandidaten für k
> > herausfinden ?
> >
> > d) Was muss man vermeiden um den oben geschilderten
> > Angriff wirklungslos zu machen ?
> > > zu a)
> > >
> > > Hier würde ich auf [mm]e^k \equiv\ 1\ mod\ \varphi(n)[/mm] folgern,
> >
> > Wieso willst du das daraus folgern? Es reicht doch wenn
> > dies der Fall ist (warum eigentlich?).
>
> Willst du darauf hinaus, dass ich ja noch gar nicht weiss
> ob die in der Aufgabe erwähnte Kongruenz gilt und nun
> erstmal davon ausgehe, sie gelte nicht und das dann zum
> Widerspruch führe, wodurch sie dann wahr sein muss ?
Ich will darauf hinaus dass du nicht schreiben sollst, dass du aus der Voraussetzung der Aufgabenstellung, naemlich dsas [mm] $m^{e^k} \equiv [/mm] m [mm] \pmod{n}$ [/mm] fuer jedes $m$ folgt, dass [mm] $e^k \equiv [/mm] 1 [mm] \pmod{\varphi(n)}$ [/mm] ist. Das stimmt naemlich nur, wenn $n$ von der Form $p$ oder $2 p$ mit $p$ ungerader Primzahl ist. Andernfalls stimmt die Aequivalenz nur modulo [mm] $\frac{\varphi(n)}{2}$.
[/mm]
Wenn allerdings [mm] $e^k \equiv [/mm] 1 [mm] \pmod{\varphi(n)}$ [/mm] gilt, dann folgt daraus [mm] $m^{e^k} \equiv [/mm] m [mm] \pmod{n}$ [/mm] fuer alle $m$.
> > Was weisst du ueber [mm]e[/mm] in Relation zu [mm]\varphi(n)[/mm]? Sagt dir
> > der kleine Satz von Fermat was?
>
> Schon, nur der kleiner Fermat gilt doch nur für prime
> Modulos und [mm]\varphi(n)[/mm] muss ja nicht prim sein wenn man
> jetzt [mm]e^k \equiv\ 1\ mod\ \varphi(n)[/mm] betrachtet oder auf
> welche Kongruenz spielst du an ? [mm]e^{\varphi(n)}[/mm] wäre nach
> Euler-Fermat kongruent 1 modulo n, aber darum geht es hier
> ja nicht oder ?
Dann halt der Satz von Euler-Fermat. Doch, genau den mein ich. Allerdings ist demnach nicht [mm] $e^{\varphi(n)} \equiv [/mm] 1 [mm] \pmod{\varphi(n)}$.
[/mm]
> > > was wegen [mm]e^k=1=ed<=>e^{k-1}=d[/mm] ja dann hinkommen würde oder
> > > ?
> >
> > Warum wuerde das hinkommen? (Ja, das stimmt so, aber etwas
> > argumentieren musst du schon -- warum kannst du einfach
> > kuerzen? Du rechnest ja modulo [mm]\varphi(n)[/mm] und nicht in den
> > ganzen Zahlen!
>
> Durch Linksmultiplikation von [mm]e^{-1}[/mm] folgt das in meinen
> Augen.
Genau, da $e$ eine Einheit modulo [mm] $\varphi(n)$ [/mm] ist.
> > > zu c) und d) habe ich noch keine Ideen, was wäre hier zu
> > > beachten ?
> >
> > Bei c) musst du dir selber mal Gedanken machen.
>
> Ich hatte an die Verfahren zur Berechnung diskreter
> Logarithmen gedacht (Shank, Index Calculus...etc)
Kannst du die denn anwenden, wenn du [mm] $\varphi(n)$ [/mm] nicht kennst? Darueber muesstest du mal nachdenken.
> > Bei d) beachte allerdings, was fuer [mm]k[/mm] gelten sollte, damit
> > [mm]e^k \equiv 1 \pmod{\varphi(n)}[/mm] gilt. Stichwort: Ordnung.
>
> Wenn k die Ordnung des Elements e wäre, dann müsste dieses
Du musst genauer sein: die Ordnung von $e$ in welcher Gruppe?
> gleichzeitig das kleinste k sein, für welches diese
> Kongurenz gilt.
Ja.
LG Felix
|
|
|
|
