Kongruent modulo < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo, ich schreibe eine Ausarbeitung über das Thema RSA.
Dies woll keine spezifische Frage zum Thema RSA sein, jedoch zu einem anderen Problem.
Folgendes:
2 Primzahlen p und q
n=p*q
m=phi(n)
M = Klartext der als Zahl dargestellt wird
C: Verschlüsselter Text
e: Öffentlicher Schlüssel
d: privater Schlüssel
Für die Zahlen gilt:
e teilerfremd zu m
[mm] C=M^e [/mm] mod n
d ist das inverse von e mod m
[mm] M=C^d [/mm] mod n
Ich gehe auf den Square and multiply ALgorithmus ein, mit dem effizient Exponentationen durchgeführt werden können.
Hierzu findet man in der Ausarbeitung eine Formel mit der der Exponent e in die Bonärdarstellung umgewandelt wird.
e= [mm] \summe_{i=1}^{r} x_{i} [/mm] * [mm] 2^{i}; x_{i} \varepsilon [/mm] {0,1}; e = [mm] [x_{r} x_{r-1} [/mm] ... [mm] x_{0}]2;
[/mm]
Weiters findet man eine Formel für C.
[mm] C=M^{e} [/mm] mod n = [mm] (\produkt_{i:e_{i}=1}^{} M^{2^{i}} [/mm] mod n) mod n
Hier eine Frage von meinem Professor:
Wieso kann man bei dieser Formel auch ein kongruent modulo n schreiben, wenn man die Formel für e in die Formel von M einsetzt.
Also dies würde beim einsetzen ergeben:
C [mm] \equiv [/mm] n [mm] M^{\summe_{}^{} (xi * (2^i))} \equiv [/mm] n [mm] \produkt_{}^{} M^{xi*(2^i)} [/mm]
Folgende Sachen sind mir dazu eingefallen:
1) Die Formel ergibt das selbe aufgrund der Potenzgesetze [mm] X^{y^Z} [/mm] * [mm] X^{P^Q} [/mm] = [mm] X^{y^Z + P^Q}
[/mm]
2) a (kongr mod n) b gilt wenn a mod n und b mod n die selben reste ergeben. Dadurch dass die Formel ja eine Gleichheit angibt, muss das gegeben sein
Sonst würden mir keine Gründe einfallen, übersehe ich da was?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:20 Sa 13.10.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
