Cryptography Reference
In-Depth Information
as we use it on products of two prime numbers. This is our basic idea: we
know that it is extraordinarily difficult to calculate the prime numbers from a
product,
n
=
pq
, of two large prime numbers,
p
and
q
. The problem is referred
to as the
factoring
of
n
. The difficulty increases as numbers have increasingly
more decimal digits. We might be able to build an asymmetric algorithm:
n
is
known, and we could somehow encrypt something using this number, but we
couldn't decrypt it without knowing
p
and
q
.
We will first consider that Euler's function looks like this for all prime numbers:
φ
(pq) = (p-1)(q-1).
The proof is simple: there is a total of
pq
numbers, 1
,...,
pq
. Out of these
numbers, the following are
not
relatively prime to
pq
: the numbers
p
divisible
by
q
, and the numbers
q
divisible by
p
, i.e.,
p
q
. We have to bear in mind
that we considered
pq
twice, since it is divisible by
p
and
q
. All other numbers
divisible neither by
p
nor by
q
have got to be relatively prime to
pq
(since
p
and
q
are prime numbers). Thus
+
φ
(pq) = pq - (p+q-1) = (p-1)(q-1).
Consequently,
m
(
p
−
1
)(
q
−
1
)
= 1 mod pq
(2)
or
m
(
p
−
1
)(
q
−
1
)
+
1
= m mod pq
holds for all
m
that are divisible neither by
p
nor by
q
. This could be the
procedure we are looking for: we find two natural numbers,
d
and
e
,by
de = (p-1)(q-1)+1
and
d,e > 1
and publish
e
and
n
. Everybody can calculate the remainder for every number
that is relatively prime to
pq
,
m<
pq
, which
m
e
leaves when divided by
pq
.
