RSA-Verschlüsselung / Satz von Euler

Question

Hallo zusammen,

ich bin im Moment beim Rechnen von RSA Verschlüsselungen aber ich weiß hierbei grad nicht weiter. Mein Prof hat zwar die Rechnung drin aber ich kann sie nicht nachvollziehen und würde gerne wissen, wie ihr es rechnen würdet.

Geg: e = 25; N = 7849; φ(N) = 7636

Verschlüsselung C = 1318^e mod n   ->  1318²⁵ mod 7849

Seine Antwort dabei ist: 0380 mod 7849, diese stimmt auch, aber ich verstehe nicht wie man darauf kommt, da bei diesen großen Zahlen der Taschenrechner versagt.

Ich weiß, dass man da den Satz von Euler einsetzt, aber da N in diesem Fall größer als der Exponent ist, bin ich ratlos, denn ich habe den Satz bis jz nur angewandt, wenn der Exponent größer war, da ich den dann mit φ(N) aufsplitten konnte.

Danke im Voraus

Answer 1

Vielleicht Binäre Exponentiation

https://www.geogebra.org/m/wn4bappz

\(1318^{25} = 1318^{11001_{2}}\)

Alle Stellen-Werte an der die Binärzahl 1 steht miteinander multiplizieren.

\( \left\{ 1318^{\left(2^{4} \right)}, 1318^{\left(2^{3} \right)},   1318^{\left(2^{0} \right)} \right\}  mod\; n = \left\{ 1569 \cdot 1149 \cdot 1318 \right\} mod \; n = 380\)

Comments

Danke dir schon mal sehr. Die Zwischenergebnisse sind dieselben zu meinem Prof, nur verstehe ich noch nicht, wie die Zahlen 1569, 1149 rauskommen.

Könntest du vielleicht noch die anderen Zwischenschritte einfügen, denn genau das fehlt mir zum Verständnis.

Ich gebe das nämlich grad nur stumpf in den Taschenrechner ein und da kommt natürlich was ganz anderes raus.

DAnke

---

Ja, da ging was verlustig beim Kopieren:

Hast Du in den Link geschaut? Da ist ein ausführliches Beispiel:

Das ist eine Iteration/Rekursion über das Bit-Muster

\(1318^{25}\, mod \, 7849 \to 1318^{11001_2}\, mod \,7849 \to \\b_i = b_{i-1}^2\, mod \, 7849 \to \prod_{bit=1}^{11001_2} b_{i} \, mod \, 7849\)

\(b_i \, :=  \, \left(\begin{array}{rr}4&1569\\3&1149\\2&768\\1&2495\\0&1318\\\end{array}\right)\)

Bit 0: 1318 ->

Bit 1: 1318^2 mod n = 2495 ->

Bit 2: 2495^2 mod n = 768 ->

Bit 3: ....usw... ok?

und noch das (Produkt der 1er Bits) mod n

---

Ich schreib das mal maschinentechnischer auf

Mod(1569*Mod(1149*1318,n),n)

---

Danke dir. Jap, jetzt ist's klar geworden.

Answer 2

\(\begin{aligned} & 1318^{25}\ \mathrm{mod}\ 7849\\ = & 1318^{1+24}\ \mathrm{mod}\ 7849\\ = & \left(1318\cdot1318^{24}\right)\ \mathrm{mod}\ 7849\\ = & \left(1318\cdot\left(1318^{2}\right)^{12}\right)\ \mathrm{mod}\ 7849\\ = & \left(1318\cdot\left(1318^{2}\ \mathrm{mod}\ 7849\right)^{12}\right)\ \mathrm{mod}\ 7849 \end{aligned}\)