Cryptography Reference
In-Depth Information
m
e
1
(mod
n
)
c
1
≡
for the first user and
m
e
2
(mod
n
)
c
2
≡
for the second user. The outside adversary sees
c
1
and
c
2
, and can compute
the following pair of values:
e
−
1
1
t
1
≡
(mod
e
2
)
t
2
=
t
1
e
1
−
1)
/e
2
Equipped with
t
1
and
t
2
, the adversary can then recover the message
m
as
c
t
1
c
−t
2
. This is because
2
c
t
1
c
−t
2
m
e
1
t
1
m
−e
2
t
2
=
2
m
1+
e
2
t
2
m
−e
2
t
2
=
m
1+
e
2
t
2
−e
2
t
2
=
m
1
=
m.
=
Due to the common modulus attacks, it is important that a modulus
n
is never
used by more than one entity. This also means that the prime numbers used to
generate the moduli must be unique for all users.
Attacks that exploit the multiplicative structure of the RSA function:
There are
several attacks against the RSA public key cryptosystem that exploit the multiplica-
tive structure (or homomorphic property) of the RSA function. If, for example, two
plaintext messages
m
1
and
m
2
are encrypted with the same public key (
n, e
),then
one gets
c
1
≡
m
1
(mod
n
) and
c
2
≡
m
2
(mod
n
). In this case, one can construct
the following ciphertext:
(
m
1
m
2
)
e
(mod
n
)
c
=
c
1
c
2
≡
This means that anybody who knows two ciphertexts
c
1
and
c
2
can easily con-
struct (by a single modular multiplication) the ciphertext for the plaintext message
