Decryption:

We need one more piece of (private) information.

Euclid, about 300 B.C.E.

If a and b don't have any common prime factors, then there are integers c and d such that

[Graphics:Images/rsa7_gr_1.gif]

Since we picked e such that e and (p-1)(q-1) don't have any common prime factors, then there are integers c and d such that

[Graphics:Images/rsa7_gr_2.gif]

or

[Graphics:Images/rsa7_gr_3.gif]

Euclid also tells us how to find c and d, using the Euclidean Algorithm.

Once we have found the decryption exponent d, which is private, we can decrypt.

For each C, compute

[Graphics:Images/rsa7_gr_4.gif]

What will this give you?

We know

[Graphics:Images/rsa7_gr_5.gif]

although we don't yet know what P is.  So

[Graphics:Images/rsa7_gr_6.gif]

but

[Graphics:Images/rsa7_gr_7.gif]

by Euler's Theorem!  So

[Graphics:Images/rsa7_gr_8.gif]

and we get our original plaintext back.

Example:

[Graphics:Images/rsa7_gr_9.gif]
[Graphics:Images/rsa7_gr_10.gif]
[Graphics:Images/rsa7_gr_11.gif]
[Graphics:Images/rsa7_gr_12.gif]
[Graphics:Images/rsa7_gr_13.gif]
[Graphics:Images/rsa7_gr_14.gif]
[Graphics:Images/rsa7_gr_15.gif]
[Graphics:Images/rsa7_gr_16.gif]
[Graphics:Images/rsa7_gr_17.gif]
[Graphics:Images/rsa7_gr_18.gif]
[Graphics:Images/rsa7_gr_19.gif]
[Graphics:Images/rsa7_gr_20.gif]
[Graphics:Images/rsa7_gr_21.gif]

Next Section


Converted by Mathematica      February 7, 2001