Cryptography Reference
In-Depth Information
den Chiffren zu ähnlicher Zeit gebrochen werden konnten, als die erforderliche Rechenleistung
zur Verfügung stand: 512-Bit-RSA in 1999 und 56-Bit-DES in 1998. Die letzte Spalte zeigt
zum Vergleich übliche Längen von symmetrischen Schlüsseln. Weiterführende Literatur findet
sich z.B. in [BSI06a] und [CrypTool]. In CrypTool kann man RSA-Verfahren in vielen Va-
rianten mit eigenen Parametern durchführen: siehe Menü Einzelverfahren \ RSA-Kryptosystem
\ RSA-Demo.
Die für l
equiv
ermittelten Werte darf man nicht allzu kritisch betrachten, zumal sie auch von
verfügbaren Faktorisierungs-Algorithmen abhängen. Die Tabelle zeigt jedoch die Tendenz,
dass die Schlüssellänge für RSA drastisch erhöht werden muss, um eine nur geringe Verlänge-
rung des äquivalenten, symmetrischen Schlüssels zu erreichen. Für l
symm
=256, was bei AES
schon verfügbar ist, würde der äquivalente RSA-Schlüssel bereits so lang sein, dass er prak-
tisch kaum noch handhabbar ist. Hier zeigt sich, dass Alternativen zu RSA irgendwann not-
wendig werden könnten.
4.2.4
RSA-Beschleunigung durch Chinesischen Restsatz
Mit dem Chinesischen Restsatz kann der RSA-Algorithmus um den Faktor 4 beschleunigt
werden. Dazu müssen jedoch die Primfaktoren p und q des Moduls n verfügbar sein. Aus die-
sem Grund kann der Chinesische Restsatz nur für den privaten Schlüssel d angewendet wer-
den, also bei der digitalen Signatur und bei der Entschlüsselung.
Der private Schlüssel d und auch die Primfaktoren p und q werden am besten auf einer Chip-
karte sicher und nicht auslesbar verwahrt. Im Sinne der Sicherheit ist es empfehlenswert, die
digitale Signatur und die Entschlüsselung direkt auf dieser Chipkarte durchzuführen. Der pri-
vate Schlüssel kann dann auch von einem Trojaner im Rechner nicht gelesen werden.
Die Chipkarte bietet Sicherheit für die private Schlüsselinformation, aber ihre Rechenleistung
ist gering. Genau in diesem Fall ist Bedarf nach Beschleunigung, und der Chinesische Restsatz
bietet sie dafür. Chipkarten für die digitale Signatur haben oft einen Koprozessor. Die Dauer
für eine digitale Signatur kann damit auf weniger als eine Sekunde gedrückt werden.
Wir wollen den Chinesischen Restsatz für den Fall der Entschlüsselung bei RSA anwenden.
d
m c)modn
fürm[0,n ,n pq,p q
(4.2-12)
Wir wenden die Operation modulo p auf (4.2-12) an und erhalten mit (4.2-13) das Teilergebnis
m
p
. In dem Ausdruck „((c
d
) mod n) mod p“ kann die Modulo-Operation mod n weggelassen
werden, denn wenn ein Ausdruck durch p teilbar ist, dann ist er auch durch ein Vielfaches von
p, nämlich n=p·q teilbar (vgl. (4.1-25) in Abschnitt 4.1.6). Weiter kann der Exponent d durch
d mod (p1) ersetzt werden, was aus dem Kleinen Satz von Fermat (4.1-11) folgt.
m
(m)modp
((c )modn)modp
d
(c
d mod ( p 1)
)modp
(4.2-13)
Entsprechend ergibt sich m
q
:
m
(m) mod q
((c ) mod n) mod q
d
(c
d mod (q
1)
) mod q
(4.2-14)
q
Das gewünschte Ergebnis m=(c
d
) mod n kann schließlich mit dem Chinesischen Restsatz
(4.1-24) aus den Teilergebnissen m
p
und m
q
berechnet werden:
