Cryptography Reference
In-Depth Information
e
) is an RSA public key and that
d
is the corresponding
private key. We will sometimes use the notation
ab
to mean
a
We will assume that (
n
,
b
, just as we did
in Section 5.2. We will also use a mathematical result attributed to Fermat that
states that for any number
B
that satisfies gcd(
B
×
,
n
)
=
1, it follows that:
B
(
p
−
1)(
q
−
1)
=
1mod
n
.
Now, expressing the RSA decryption formula mathematically, we have:
C
d
(
P
e
)
d
P
ed
mod
n
=
=
.
Remember that because
d
is the modular inverse of
e
we have that
ed
=
1mod
(
p
−
1)(
q
−
1). This means that there is some positive integer
k
for which it is
true that:
ed
=
k
(
p
−
1)(
q
−
1)
+
1
.
Thus, by replacing this in our above expression for the decryption function:
C
d
P
ed
P
k
(
p
−
1)(
q
−
1)
+
1
mod
n
=
=
.
Now all we do is rewrite this expression by rearranging the powers of
P
. There are
no mathematical tricks here, we just follow the rules that describe how powers of
a number behave. So:
C
d
P
k
(
p
−
1)(
q
−
1)
+
1
mod
n
=
P
k
(
p
−
1)(
q
−
1)
=
×
P
mod
n
(
P
(
p
−
1)(
q
−
1)
)
k
.
The result due to Fermat that we quoted at the start can now be used. Writing
P
instead of
B
, we see that (so long as the greatest common divisor of
P
and
n
is 1)
this result says:
=
×
P
mod
n
P
(
p
−
1)(
q
−
1)
=
1mod
n
.
Thus we see that:
C
d
(1)
k
=
×
P
=
P
mod
n
,
which is what we hoped decryption would achieve.
The only case that we have not covered is when gcd(
P
,
n
) is not equal to 1.
Note that this is an extremely rare case and only happens in the highly unlikely
event that either
P
=
up
, for some
u
<
q
,or
P
=
vq
, for some
v
<
p
.If
P
=
up
then
P
=
0mod
p
and so
P
ed
P
=
0mod
p
.
Since
P
is a multiple of
p
, in this case it cannot be a multiple of
q
as well, and so
the greatest common divisor of
P
and
q
is 1. Thus we can apply Fermat's result
and the above RSA argument to see that
P
ed
=
0mod
p
. In other words,
P
ed
=
=
P
mod
q
. We have now shown
that
P
ed
=
P
mod
p
and
P
ed
=
P
mod
q
. It follows by a simple number theory
result that
P
ed
=
P
mod
n
.If
P
=
vq
then we apply a similar argument to show
the same result.