Cryptography Reference
In-Depth Information
m
e
mod
n
, where
m
is the session key and (
e, n
)is
Alice's key. To recover
m
(and read the entire message encrypted with the ses-
sion key), Eve uses the public key to encrypt any number,
r
, that is relatively
prime
3
to
n
. Then she takes the ciphertext produced and multiplies it with the
intercepted ciphertext,
c
:
perspective, she knows
c
=
y=cr
e
mod n
Foisting this
y
on Alice, Eve asks her for a signature, i.e., decryption. So Alice
computes
y
d
=c
d
r
ed
mod n
and gives this result back to Eve. On account of
m=c
d
r
ed
mod n
and
= r mod n
Eve now knows the remainder from dividing
mr
by
n
, and can use it together
with the extended Euclidean algorithm to compute
m
(using this algorithm, she
first solves the equation
rx
=
1 mod
n
and then multiplies
mr
=
u
mod
n
by
x
:
m
=
ux
mod
n
).
m
e
mod
n
to Alice for signature right
away. That would have been more obvious. In that case, however, though very
costly, Alice could have caught Eve cheating if she'd kept all encrypted session
keys and compared
c
with these keys. In the attack described here, Alice has
no chance to see through Eve's intention.
Of course, Eve could have submitted
c
=
Eve exploits a particularity of RSA, namely that the decryption of a cipher-
text can be derived from the encryption of another ciphertext, though the two
ciphertexts are apparently not related. This is not a weakness of RSA, but of the
cryptographic protocol. With the protocols used in practice, there is no chance
this weakness can be exploited. But knowing about it helps to prevent us from
developing insecure methods.
3
If it weren't relatively prime to
n
, Eve would have recovered a prime factor of
n
and reached
her goal.
