0 Daumen
212 Aufrufe

ich habe den public key (n,e) = 35,13 und soll die Potenzen nach dem square and multiply verfahren berechnen. Wie gehe ich voran? 

von

1 Antwort

0 Daumen

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\).



von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community