Cryptography Reference
In-Depth Information
Let this remainder be the ciphertext;
m
the
plaintext
; and
n
=
pq and
e
the
public key
(i.e.,
two
numbers!). We are the only ones to know
d
, the
private
key (actually this also includes
n
, but it is not secret). When somebody sends
us ciphertext
m
e
(or, more exactly, the remainder from the division by
n
), then
we calculate plaintext
m
as follows:
(m
e
)
d
=m
ed
=m
(
p
−
1
)(
q
−
1
)
+
1
= m mod pq
The calculation of
d
from
e
and
n
is done by factoring
n
=
pq
. Somebody
who does not factor
n
(i.e., who does not compute
p
and
q
from
n
) cannot
find
d
either. Is this correct? Isn't (
p
1) all an attacker needs to find
d
? Well, if he somehow managed to compute (
p
−
1)(
q
−
1) in any other way,
then he also knows
−
1)(
q
−
pq - (p-1)(q-1) - 1 = p+q
so that he can easily calculate
p
and
q
from
pq
and
p
q
, i.e., he can factor
n
. Calculating (
p
−
1)(
q
−
1) is not easier than factoring
n
. And the direct
calculation of
m
from
m
e
means taking the
e
th root, which is not easier than
computing the discrete logarithm of
m
e
to base
m
, or factoring large numbers.
There might be another way to find
d
or
m
, but nobody has found such a way
yet. The most recent work I know was presented at the EUROCRYPT '98;
but it merely suggests that there could be such a way, without showing the
direction.
+
All of this looks pretty good, doesn't it? The only thing is that we have left
two problems unsolved.
Problem 1
: Have you noticed the unproved prerequisite? The reason is that, in
general, there are no two numbers,
d
and
e
, with
d
,
e<
1 and
de = (p-1)(q-1) + 1.
For example,
(p-1)(q-1)+1 = 41
