die Wahl des Schlüssels \((N,e)=(35;13)\) ist etwas ungünstig, um es vorsichtig auszudrücken, da in diesem Fall die verschlüsselte Nachricht identisch zum Original ist, und der public-Key identisch zum private-Key. Aber Ok - Deine eigentliche Frage ist ja auch eine andere. square-and-multiply geht so:
Zur Verschlüsselung einer Nachricht \(m\) musst Du \(c \equiv m^e \mod N\) berechnen. Es läuft darauf hinaus, die Zahl \(e\) in das Binärsystem zu zerlegen und für jede 1 eine Multiplikation mit dem zugehörigen Exponenten durchzuführen - also in diesem Fall ist \(e=13=1101_2\):
$$m^{13} = m^8 \cdot m^4 \cdot m^1$$
Der Algorithmus geht in etwa so:
Setzte das Resultat \(c=1\) und eine Variable \(x=m\) - als Bespiel \(x=m=23\). \(m=23\) sei die zu übermittelnde Nachricht. Ist \(e\) ungerade, so multipliziere \(c\) mit \(x\) und lege das Ergebnis in \(c\) ab:
$$c := c \cdot x \equiv 23 \mod (N=35) \quad \text{für } e \equiv 1 \mod 2$$
Anschließend dividiere \(e\) durch 2 und ersetze \(e\) durch die nächst kleinere ganze Zahl
$$e := \lfloor (e=13) \div 2 \rfloor = 6$$
Ist \(e\) noch größer als 0, so quadriere \(x\) und nehme den Modulo zu \(N\)
$$x :\equiv (x=23)^2 \equiv 4 \mod (N=35)$$
mache jetzt am Anfang weiter. Jetzt ist \(e=6\) gerade, dann verzichte auf die Multiplikation mit \(x\). Alles andere wie gehabt:
$$c := c = 23 \quad \text{da } e = 6 \equiv 0 \mod 2$$
$$e := \lfloor (e=6) \div 2 \rfloor = 3$$
$$x := (x=4)^2 \equiv 16 \mod (N=35)$$
nächster Schritt
$$c := (c = 23) \cdot (x=16) \equiv 18 \mod (N=35) \quad \text{da } e = 3 \equiv 1 \mod 2$$ $$e := \lfloor (e=3) \div 2 \rfloor = 1$$$$x := (x=16)^2 \equiv 11 \mod (N=35)$$ nächster Schritt
$$c := (c = 18) \cdot (x=11) \equiv 23 \mod (N=35) \quad \text{da } e = 1 \equiv 1 \mod 2$$$$e := \lfloor (e=1) \div 2 \rfloor = 0$$ .. und Schluß, da \(e=0\) ist. Die verschlüsselte Nachricht ist \(c=23\).
