Cryptography Reference
In-Depth Information
als
p
·
q
. Im obigen Beispiel ist dies leicht zu erkennen: Die unendlich vielen
Lösungen heißen 5, 17, 29, 41, 53, ..., wobei nur die erste dieser Zahlen kleiner
als 3·4=12 ist.
Abb. 11-3
Eine Gruppe läuft in Viererreihen (links), wobei eine Person übrig bleibt. Läuft sie in
Dreierreihen (rechts), dann bleiben zwei Personen übrig. Wie viele Personen zur Gruppe
gehören, lässt sich mit dem Chinesischen Restsatz ermitteln.
Nun ist die Frage, wie wir die Lösung (also den Wert von
x
) finden. Hierfür gibt
es eine Formel. Sie liefert immer die kleinste Lösung und lautet (
a
muss größer
oder gleich
b
sein):
x
= (((
a
- (
b
mod
p
)) · (
q
-1
(mod
p
))) mod
p
) ·
q
+
b
Machen wir die Probe aufs Exempel und setzen die oben genannten Werte für
a
,
b
,
p
und
q
ein. Dann ergibt sich:
x
= (((2
- (1 mod 3)) · (4
-1
(mod 3))) mod 3) · 4 + 1
= (((2
- 1) · 1) mod 3) · 4 + 1
= ((1 · 1) mod 3) · 4 + 1
= 1 · 4 + 1
= 5
Spätestens jetzt werden Sie sich fragen, was das alles mit dem RSA-Verfahren zu
tun hat. Um die Frage zu beantworten, stellen wir uns
c
(also den RSA-Geheim-
text) als Anzahl der Personen in der Gruppe vor. Wir gehen davon aus, dass sich
die Gruppe zunächst in Reihen zu je
p
Personen aufstellt, wobei
a
Personen übrig
bleiben. Danach stellen sich die Mitglieder in
q
-Reihen auf - mit
b
übrigen Perso-
nen.
p
und
q
sind im Zusammenhang mit RSA immer Primzahlen. Durch den
