Cryptography Reference
In-Depth Information
In Definition 6.4.2 (RSA-Kryptoschema) wurde erwähnt, dass
e
häufig konstant ge-
wählt wird. Insbesondere wählt man gerne kleine Werte für
e
,etwa
3
, da dann das Ver-
schlüsseln besonders ezient durchgeführt werden kann: Die Berechnung von
x
3
mod
n
benötigt lediglich zwei Multiplikationen modulo
n
. Die RSA-Annahme scheint auch dann
noch gerechtfertigt zu sein. Allerdings handelt man sich neue Angriffe auf »Textbook
RSA« ein, die der RSA-Annahme jedoch nicht widersprechen. Ist zum Beispiel
0
x<
n
1
/
3
, so kann man bei gegebenem
y
=
x
3
mod
n
leicht
x
bestimmen, denn
x
=
y
1
/
3
(in den ganzen Zahlen!). Für kleine Klartexte kann man also leicht vom Chiffretext auf
den Klartext schließen. Wir verweisen auf Aufgabe 6.7.15 für einen weiteren Angriff, der
durch die Wahl
e
=3
möglich wird.
≤
6.4.3
RSA-basierte asymmetrische Kryptoschemen
Es bleibt die Frage, ob man auf Basis der RSA-Annahme ein sicheres asymmtrisches
Kryptoschema konstruieren kann. Glücklicherweise ist dies möglich.
Eine solche Konstruktion ist sogar leicht möglich: Man wählt pro Verschlüsselung
einen zufällig gewählten Bitvektor
r
bestimmter Länge und konkateniert diesen mit dem
Klartext
x
in der Form
r · x
,wobei»
·
« für die Konkatenation steht. Interpretiert als
x
wie gewohnt mit dem RSA-Verfahren verschlüsselt.
Unter der RSA-Annahme und falls der Bitvektor
r
ausreichende Länge hat, lässt sich
dann Sicherheit in unserem Sinne zeigen. Der Beweis ist allerdings relativ aufwändig und
wird hier nicht vorgeführt. Um ein ausreichendes Maß an Sicherheit zu erhalten, muss
zudem
r
recht lang sein, so dass die eigentliche Nachricht
x
kurz ausfallen muss, was das
Verfahren für die Praxis im Allgemeinen unbrauchbar macht.
Ein ähnlicher Ansatz wird in PKCS#1 v1.5 verfolgt. Die Abkürzung PKCS steht für
»Public Key Cryptography Standards« und bezeichnet einen von den RSA Laboratories
entwickelten Satz kryptographischer Standards. In PKCS#1 v1.5 wird u. a. ein (verbreite-
tes) asymmetrisches Kryptoschema definiert. In diesem wird nicht nur
r
mit dem Klartext
konkateniert, sondern zusätzlich konstante Bitvektoren. Genauer wird der Bitvektor
Element von
Z
n
wird dann
r
·
0
14
·
0
8
·
10
·
r
·
x
(6.4.7)
interpretiert als Element von
Z
n
, mit dem RSA-Verfahren verschlüsselt, wobei wiederum
« für die Konkatenation steht. Es wird vermutet, dass auch PKCS#1 v1.5 Sicherheit
in unserem Sinne bietet, auch wenn
r
deutlich kürzer gewählt wird als im zuvor beschrie-
benen Verfahren. Ein Beweis ist allerdings nicht bekannt.
Wie in Abschnitt 6.2 erwähnt, kann man für asymmtrische Kryptoschemen auch CCA-
Sicherheit definieren. CCA-sichere RSA-basierte Kryptoschemen sind allerdings aufwän-
diger als die oben betrachteten Konstruktionen. In der Tat liefern die oben betrachteten
Konstruktionen keine CCA-Sicherheit. Für die erste Konstruktion soll dies in Aufga-
be 6.7.16 gezeigt werden.
Daniel Bleichenbacher hat 1998 einen Angriff im Sinne der CCA-Sicherheit auf PK-
CS#1 v1.5 gefunden. Mit einem vollen Dechiffrierorakel wäre dies kaum der Rede wert.
Was diesen Angriff aber besonders interessant und beunruhigend machte, ist die Tatsache,
dass er mit einem sehr schwachen Dechiffrierorakel auskommt, welches in der Praxis exis-
»
·
