Cryptography Reference
In-Depth Information
E
XAMPLE
.
We will demonstrate RSA using small numbers. To establish a public and private
key, an individual first selects two primes, say
p
= 563 and
q
= 2357. So,
n
= 563
2357 =
1326991. Finally, he selects an integer
e
= 3 relatively prime to (
p
1)(
q
1) = 1324072,
and computes the inverse of
e
modulo (
p
1)(
q
1) by solving
3
d
1 mod (1324072)
for
d
. This yields
d
882715 (mod 1324072).
The values for
n
and
e
are made public;
d
,
p
, and
q
remain private.
Suppose someone wants to send the message (regarded as an integer)
P
= 1107300
to the aforementioned individual. They must simply calculate and send the ciphertext
C
= 875102
1107300
3
(mod 1326991).
To decrypt, the recipient uses the decryption key to derive the plaintext thus:
875102
882715
(mod 1326991).
P
= 1107300
14.9
WEAKNESSES OF RSA
RSA can be compromised given certain conditions. We will examine these issues here.
Small Encryption Exponent
It has been suggested that a small encryption expo-
nent in RSA be used since it speeds up encryption. For example, all users could use
e
= 3
as their public encryption key. This doesn't help recover their decryption exponents, since
this still seems to involve factoring each of their moduli (each still chooses a different mod-
ulus). However, a small common value for
e
allows one to compute the
e
th root (with the
aid of the Chinese Remainder Theorem) when the same message is sent to multiple entities.
Recall that a similar problem occurs with the Rabin cipher.
Suppose
e
= 3 for some individual, and they send the same message
m
(enciphered) to
three different entities, having respective moduli
n
1
,
n
2
, and
n
3
. The ciphertext sent to each
entity will be denoted
c
1
,
c
2
, and
c
3
. An eavesdropper intercepting these messages merely
has to find the simultaneous solution
x
to the system
x
c
1
(mod
n
1
)
x
c
2
(mod
n
2
)
x
c
3
(mod
n
3
).
Since
m
3
<
n
1
n
2
n
3
, (and these moduli are almost certainly pairwise relatively prime) the
lnr of the
x
obtained using CRT is in fact,
m
3
. Thus, to recover
m
, one needs only compute
Search WWH ::
Custom Search