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.
 
Search WWH ::




Custom Search