The RSA Public Key Cryptosystem

Introduction

The RSA Public Key Cryptosystem* is based on the coiled-up clock numbers Z/pqZ that we studied earlier. However, for the purposes of cryptography, the factors p and q must remain secret; only the entire modulus n can be made public. When n is large, finding p and q is presumed to be difficult. The RSA algorithm is named for its inventors, Rivest, Shamir, and Adleman.

[Numeroscope Applet -- UNDER CONSTRUCTION: displays the clock numbers, and their invertibles, with variable composite modulus. Can serve as a calculator for this number system, or display additive and multiplicative series, as well as function ranges.]

Lab Activities

Mode	Oper.	r	c	Activity
sweep/fill r	×		1	Notice how in the new "Multiplicative View", repeated multiplication causes straight-line propagation (except for wraparound).
all r	×		1	Look at the sizes of the multiplicative series, and record your observations. Be sure to include the following cases: p 11 13 13 q 7 5 7

Discussion Topics

1. The ability to decrypt means that there is an exponent r such that z^r = z for any value of z (or -- more visibly in the numeroscope -- that z^r-1 = 1 for any invertible number z). For clock numbers modulo a prime p, we can take r=p so that the exponent is clear from the modulus. What is the smallest exponent that works for clock numbers modulo n=pq? Why are these r's difficult to find, if we only know n? [The answer to the last question is not known.]

2. How do the sizes of the multiplicative series you recorded affect cryptography?

For more information, see the excellent RSA FAQ.

The Woodrow Wilson Leadership Program in Mathematics lpt@www.woodrow.org
The Woodrow Wilson National Fellowship Foundation webmaster@woodrow.org
CN 5281, Princeton NJ 08543-5281 Tel:(609)452-7007 Fax:(609)452-0066