Common Modulus Attack < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:24 Do 06.06.2013 | | Autor: | Erbse |
| Aufgabe | | Gebe ein Beispiel zum Common Modulus Attack an. |
Modulus N = 143 [mm] p_a [/mm] = 7 [mm] p_b [/mm] = 61
Wenn ich nun den Erweiterten Euklid anwende komme ich auf:
3*61 - 26 * 7 = 1
a = -26
b = 61
Wie kann ich jetzt den Klartext einer Nachricht bekommen?
Wenn ich die Nachricht M = 4 verschlüssele kommt [mm] enc_a [/mm] = 82 und [mm] enc_b [/mm] = 4 herraus.
Dann müsste ja M = [mm] enc_a [/mm] ^ a * [mm] enc_b [/mm] ^ b
a ist aber hier negativ, und so kommt eine Kommazahl herraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:33 Do 06.06.2013 | | Autor: | felixf |
Moin!
> Gebe ein Beispiel zum Common Modulus Attack an.
Hier geht es offenbar um RSA. Es wuerde allerdings nicht schaden, das dabeizuschreiben. Wir koennen ja nicht hellsehen.
> Modulus N = 143 [mm]p_a[/mm] = 7 [mm]p_b[/mm] = 61
> Wenn ich nun den Erweiterten Euklid anwende komme ich
> auf:
>
> 3*61 - 26 * 7 = 1
> a = -26
> b = 61
Was sollen $N$, [mm] $p_a$ [/mm] und [mm] $p_b$ [/mm] sein? Und was sind $a$ und $b$?
> a ist aber hier negativ, und so kommt eine Kommazahl
> herraus.
Quark! Du musst modular rechnen. Sprich, du invertierst erstmal modulo $N$ (oder modulo was auch immer du rechnest), und dann rechnest du hoch den Absolutbetrag vom negativen Exponenten. Da kommt eine ganze Zahl zwischen $0$ und dem Modulus heraus, und kein Dezimalbruch!
LG Felix
|
|
|
|
