Cryptography Reference
In-Depth Information
Es bleibt, die Dechiffrierbedingung aus Definition 6.1.1 zu überprüfen. Das folgende
Lemma zeigt, dass diese Bedingung in der Tat erfüllt ist.
Lemma 6.4.1. Es sei ( n, p, q, m, e, d ) ein RSA-Tupel. Dann gilt
D ( E ( x, ( n, e )) , ( n, d )) = x
für alle x ∈ Z n .
Beweis. Wir müsssen zeigen, dass
( x e ) d mod n = x
(6.4.1)
für alle x
Z n gilt. Wir führen eine Fallunterscheidung durch und beginnen mit dem
Fall x ∈ Z n . Dann gilt zunächst:
( x e ) d mod n = x ed mod n (* = x ed mod m mod n (** = x 1 = x,
(6.4.2)
| Z n |
wobei (*) aus (6.3.1) folgt und der Tatsache, dass m =
ist. Wir erhalten (**) aus
der Voraussetzung e
·
d mod m =1 .
Z n unterscheiden wir die folgenden drei Fälle: x =0 ; x
Für x/
=0 und p
|
x ; x
=0
und q
x .
Der Fall x =0 ist trivial. Die beiden anderen Fälle sind symmetrisch zueinander, so
dass wir uns auf x
|
x beschränken können.
Wir benutzen den Chinesischen Restsatz (Satz 6.3.1) und zwar mit a = p und b = q
(nach Annahme sind p und q verschiedene Primzahlen, so dass die Voraussetzungen des
Satzes erfüllt sind). Es sei h der Isomorphismus aus dem Chinesischen Restsatz. Dann
ist h ( x )=(0 ,y ) ,mit y = x mod q . Es gilt y
=0 und p
|
Z q wegen p
|
x und x
=0 .Analogzu
Z q :
(6.4.2) erhalten wir nun in
( y e ) d mod q = y ed mod q = y ed mod q− 1 mod q
(* = y ( ed mod m ) mod q− 1 mod q = y 1 = y,
(6.4.3)
wobei wir in (*) nutzen, dass für alle c ∈ Z und alle a, b ≥ 1 mit a | b gilt: c mod a =
( c mod b ) mod a .
Aus (6.4.3) ergibt sich nun in
Z p × Z q : ((0 ,y ) e ) d =(0 ,y ) , wobei die Exponentiation als
Opertionen im Ring
Z p × Z q betrachtet wird. Dies überträgt sich, nach dem Chinesische n
Restsatz, in den Ring
Z n ,was ( x e ) d mod n = x liefert.
S RSA ein deterministisches Kryptoschema. Gemäß Satz 6.2.1 ist
S RSA somit unsicher. RSA ist auch aus einem anderen Grund als asymmetrisches Krypto-
schema ungeeignet: Das Jacobi-Symbol des Klartextes überträgt sich auf den Chiffretext.
Der Chiffretext liefert also (nicht-triviale) Information über den Klartext. Dies wird im
folgenden Lemma präzisiert, in dem die am Ende von Abschnitt 3.3 eingeführte Notation
verwendet wird.
Offensichtlich ist
Lemma 6.4.2 (Jacobi-Symbol und RSA). Es sei ( n, p, q, m, e, d ) ein RSA-Tupel. Dann
 
Search WWH ::




Custom Search