Topics to cover

Review index of coincidence

2.  Modular exponentiation

3.  Hill Cipher -- another modular arithmetic application.

     I haven't talked about this.

4.

5.  The RSA algorithm

Let p and q be two prime numbers.

Let e be chosen such that gcd(e,(p-1)(q-1)) = 1.

Let d be the reciprocal of e mod (p-1)(q-1).

Make the numbers pq and e public.

To encrypt, take your message T and compute T^e mod pq.

To decrypt, take ciphertext C and compute C^d mod pq.

If the message is too large to code by a residue mod pq,
divide it into blocks and encode them separately.

Why does this work?

1.  phi(pq) (the number of n < pq such that gcd(n,pq) = 1) = (p-1)(q-1).

2.  (T^e)^d mod pq = T^ed mod pq.  ed = 1 mod (p-1)(q-1).  If we can
verify that T^(p-1)(q-1) = 1 mod pq, this will verify decryption.

Theorem: Consider the set of integers m < n such that gcd(m,n) = 1.
There are phi(n) such integers.  Each one has a reciprocal mod n; more
general, modular division is defined on these residues.  claim: m^e =
1 implies that e is a divisor of phi(n).  Suppose that g < n is not
equal to m^f for any f (mod n).  Then all the numbers gm^e must be
distinct from any m^f -- otherwise g would be m^(f-e) (so to speak),
since division is well-defined for residues relatively prime to n.
Similarly, all the numbers gm^e are distinct from each other.

So the set of residues mod n which are relatively prime to n can
be partitioned into sets of residues of size e (gm^0 -- g m^(e-1))
so e is a divisor of phi(n).

Clearly for any m < n there is some e such that m^e = 1 (powers must
eventually repeat, then use of division allows us to conclude that
some power is 1).  This e will be a divisor of phi(n), so we can conclude
further that m^phi(n) = 1 mod n.


From this, we can conclude that (T^e)^d = T and (C^d)^e = C in our
description of the RSA algorithm above.  So this is a cryptosystem.

The reason that it is secure is that from the information about
n = pq and e it is hard to determine what d is:  it would be sufficient
for example to factor n into its two prime factors, but it turns out
that this is difficult for large enough n (say 150 decimal digits).

LECTURE ON MODULAR EXPONENTIATION

0. Motivation:  describe the RSA algorithm.

1.  Compute a^e mod n: square and multiply algorithm.  Do examples.

Notice that this hand computation also goves an example of how to do
modular computations "by hand".

Compute 17 to the one thousandth power mod 19

17^1000 = 17^500*17^500
17^500 = 17^250*17^250
17^250 = 17^125*17^125
17^125 = 17^62*17^62*17
17^62 = 17^31*17^31
17^31 = 17^15*17^15*17
17^15 = 17^7*17^7*17
17^7 = 17^3*17^3*17
17^3 = 17*17*17

17^3 = 4913 - 19*258 = 11
17^7 = 11*11*17 = 2057 - 108*19 = 5
17^15 = 5*5*17 -22*19 = 7
17^31 = 7*7*17 -43*19 = 16
17^62 = 16*16 -13*19 = 9
17^125 = 9*9*17-72*19 = 9
17^250 = 9*9 - 4*19 = 5
17^500 = 5*5 - 19 = 6
17^1000 = 6*6 - 19 = 17

Modular exponentiation can be computed fairly easily, certainly with
the help of automation.  Note that no number greater than 19^3 needs
to be computed at any stage here.

2.  Theory of modular exponentiation.

Let n be the modulus (all computations are mod n).

First, we restrict our attention to residues m mod n with gcd(m,n) = 1
Division is well-defined on these, which makes them better behaved
with respect to multiplication mod n.

Observation:  if gcd(m,n) = 1, gcd(m^e,n) = 1 as well for any e.

Lemma:  If we look at the sequence of powers m^e mod n, starting
with m^0 = 1, the first power to repeat will be m^e = 1.

Proof: If m^e = m^f , 0 < e < f, is supposed to be the first pair of
equal powers in the sequence, note that we can divide both numbers by
m^e and get 1 = m^0 = m^(f-e), contradicting the purported
definition of e and f.

Theorem:  for any m with gcd(m,n) = 1, if m^e = 1, e is a divisor of
phi(n).

Proof:  There are e numbers in the set 1 = m^0, m^1,...m^(e-1).

Choose g<n, gcd(g,n) = 1, which is not one of these: all the numbers
gm^i are distinct from m^j's -- if gm^i = m^j then g = m^(j-i) by
modular division, contrary to assumption.

Now repeat this: choose an h (with gcd(h,n) = 1) which is not one of these -- the hm^i's
are distinct from m^j's by the same argument, and from the gm^j's by a
similar argument: gm^i = hm^j implies g = hm^(j-i) contrary to
assumptions.

Repeat this process until no more of the phi(n) residues mod n which are
relatively prime to n are left.  We see that phi(n) can be divided evenly
into sets of size e.

It follows that if gcd(m,n) = 1, then m^phi(n) = 1 mod n.

In the case of the RSA algorithm, this shows that for m relatively prime
to pq = N, (T^d)^e = T = (T^e)^d, since ed = 1 mod (p-1)(q-1), so decryption
works for these numbers.

It actually works for all residues; I'll talk about this later.  But in
fact it is overwhelmingly likely that any number less than pq will be
relatively prime to pq, and finding one that wasn't would enable one to
break the key anyway.