Cryptography Reference
In-Depth Information
see that the exponents
d
1
and
d
1
indeed define the same exponentiation function.
3
Finally, we observe that all the computations involved are efficient.
Remarks 8.8
1. As a consequence of the previous result, any RSA user (with public key
and
decryption exponent
d
) can decrypt the messages addressed to any other user who
shares the same RSA modulus (and hence has a public key of the form
(
n
,
e
)
e
)
(
n
,
)
by computing the exponent
d
1
in the above proposition.
2. Note that
d
1
is not necessarily an element of
Z
φ(
n
)
because
t
, and hence also
d
1
,
d
(
and
d
∈ Z
φ(
n
)
may be greater than
φ(
n
)
. However, since
d
1
≡
mod
φ(
n
))
by hypothesis, we have that
d
=
d
1
mod
φ(
n
)
.
Exercise 8.16
Consider the RSA key obtained in Example 8.2 by setting:
> rsakey := RSAKeyGen(1024, 618020429552270915383892324472348012175,
410275671464698780248543572127557803186):
and, for brevity, call the modulus
n
, the encryption exponent
e
(
2
16
=
+
1), and the
decryption exponent
d
.
(i) Prove that there is another RSA key,
rsakey2
, with the same modulus
as
rsakey
and with encryption exponent 257. Use Maple to find the key
rsakey2
.
(ii) Use the common modulus attack to find, given
e
,
d
and the encryption expo-
nent 257 of
rsakey2
, an exponent
d
1
that allows decryption of messages
encrypted with
rsakey2
. Check that
d
1
is not equal to the decryption exponent
of
rsakey2
but they are congruent modulo
φ(
n
)
.
The attack from Proposition 8.5 is called an
'insider attack'
because the adversary
must be in possession of a private key with the same modulus as the attacked key.
There is also an
'outsider attack'
against plain RSA that allows an adversary without
knowledge of any private key to recover a message encrypted with two different
keys that share the same modulus. For this, suppose that
(
,
e
1
)
(
,
e
2
)
n
and
n
are two
(
e
1
,
e
2
)
=
∈ Z
n
be a message which is
public RSA keys such that gcd
1 and let
m
m
e
i
mod
n
,for
i
encrypted with both keys, producing ciphertexts
c
i
2. An
eavesdropper who observes these ciphertexts can recover the plaintext by using the
extended Euclidean algorithm to compute integers
r
=
=
1
,
,
s
such that
re
1
+
se
2
=
1, and
then computing
c
1
c
2
mod
n
, since we have:
c
1
c
2
mod
n
m
re
1
m
se
2
mod
n
m
re
1
+
se
2
mod
n
=
=
=
m
.
Exercise 8.17
Exhibit a Maple demonstration of the 'outsider common modulus
attack' along the following lines. Write a procedure
CommonModulusAttack
that, on input two public keys with the same modulus and two ciphertexts obtained
by encrypting the same plaintext with these keys, produces as output the plaintext.
3
Alternatively, once we have shown that
e
d
1
≡
1
(
mod
φ(
n
))
, the proof of Proposition 8.1 goes
is the inverse of RSA
(
n
,
e
)
on
Z
n
.
through to show that RSA
(
n
,
d
1
)
