Asymmetrische Chiffren - Kryptographie und IT-Sicherheit - page 128

m 1 2 (m p m q)modn ! (m m )modn (4.2-15)

q p q p

Dabei werden die Größen und bzw. und mit dem erweiterten Euklidischen Algorithmus
ermittelt.

Gewinn durch den Chinesischen Restsatz
Zunächst erscheint es erst einmal komplizierter, statt der einen Formel (4.2-12) die drei For-
meln (4.2-13), (4.2-14) und (4.2-15) auswerten zu müssen. Der Rechenaufwand wird im We-
sentlichen durch die Bildung der Potenzen verursacht. Die Stellenlänge der Exponenten ist
etwa so groß wie die Stellenlänge des jeweiligen Moduls l M . „Etwa“ heißt, ihre Stellenlänge ist
l M oder l M 1 und selten geringer. Die Stellenlänge des Exponenten d in (4.2-12) ist etwa l d l n .
Die Stellenlänge der Exponenten d p =d mod (p1) und d q =d mod (q1) in (4.2-13) bzw.
(4.2-14) ist etwa l dp l p bzw. l dq l q . Die Stellenlänge der beiden Primfaktoren p und q ist in
Summe l p +l q l n . Damit ist auch die Stellenlänge der Exponenten in Summe l dp +l dq l n l d etwa
gleich der Stellenlänge von d.
Bei der Bildung der Potenzen modulo M sind (l M -1) Quadrierungen und im Mittel halb so viel
Multiplikationen erforderlich, siehe (4.1-17). Diese Zahl steigt also etwa proportional mit der
Länge der Exponenten. Wegen l dp +l dq l d ist die Zahl der Quadrierungen und der Multiplikatio-
nen für l d und l dp +l dq zusammen etwa gleich groß. Damit ist durch den Chinesischen Restsatz
noch nichts gewonnen.
Jedoch ist die Stellenlänge der Operanden (die Basis c) in der Arithmetik mod p und mod q nur
etwa halb so lang, l p l q l n /2. Eine Multiplikation mit 1/2 so langen Operanden benötigt nur 1/4
der Teilmultiplikationen. Denken Sie dabei an das aus der Grundschule bekannte Multiplikati-
onsschema, bei dem jede Stelle des Multiplikators mit jeder Stelle des Multiplikanden multip-
liziert wird. Bei der Langzahl-Multiplikation im Computer muss diese in ähnlicher Weise aus
Teilmultiplikationen zusammengesetzt werden.
Neben der Bildung der Potenzen sind die restlichen Operationen für den Chinesischen Restsatz
vernachlässigbar, so dass insgesamt etwa ein Faktor 4 gewonnen wird.

4.2.5 Übungen
Übung 1
Für RSA sind folgende Angaben bekannt: p=7, q=11, e=17.
a) Welche Eigenschaft muss e=17 erfüllen, damit ein privater Schlüssel d existiert?
Lösung
Der Schlüssel e=17 muss teilerfremd zu (7·11)=6·10=60 sein. Dies ist hier erfüllt .
b) Bestimmen Sie den privaten Schlüssel d.
Lösung
e·d 1 (mod (n)), 17·d 1 (mod 60), mit dem erweiterten Euklidischen Algorithmus:
ggT(60, 17)
ggT(17, 9) 9=60-3·17
ggT(9, 8) 8=17-9