The University of Arizona / MATHEMATICS

SWRIMS HIGH SCHOOL WORKSHOPS

Public Key Cryptography

Saturday, 4 April 1998, 9:00 AM - 4:00 PM
Mathematics Building, Room 101


In public key cryptography, two parties are able to exchange secrets during a public conversation, without having previously met and exchanged a secret key. Sound impossible? It's not! And it uses a lot of neat mathematics. This type of cryptography is used all the time between computers on the Internet. Similar techniques are used in "digital signature verification", which guarantees that entities (computers on the net) are who they claim to be.

Prerequisite: You must have attended one of our Introduction to Cryptology workshops. Familiarity with modular arithmetic is a must.


Workshop schedule:
  • Review of elementary modular arithmetic
  • Modular exponentiation and the Diffie-Hellman key exchange
    • Computing 233^3150 MOD 14579
    • TI-82 Program MODEXP1 to calculate E^F MOD N
    • Diffie-Hellman key exchange
    • Breaking Diffie-Hellman
      (As two students perform the key exchange, we break it before their eyes in real-time.)
    • TI-82 Program DISCLOG to solve E^X MOD N = G
    • Using repeated squaring to compute 233^3150 MOD 14579
    • TI-82 Program MODEXP2 to calculate E^F MOD N using repeated squaring
  • Good and bad numbers
    • Multiplication table modulo 26
      Bad numbers multiply to zero; good numbers don't. The good ones are the ones relatively prime to the modulus.
    • Unit multiplication table modulo 26
      If we restrict attention to good numbers, via multiplication we never leave that world.
    • If modulus N = pq, then there are (p-1)(q-1) good numbers: most of them are good.
    • Given A MOD N, how do we tell whether A is good?
    • How do we compute GCDs?
    • GCD(A,B) = GCD(B, A MOD B)
    • Euclidean algorithm to find GCD
    • Working backwards to write GCD as linear combination
    • Question: if A is good, then for which B do we have AB=1 MOD N?
    • Using linear combination to figure this out (worksheet)
    • When A is good, solving AX=B MOD N
    • TI-82 Program EUCLID computes GCD and A^{-1} MOD N
  • Bridging from Diffie-Hellman to RSA
    • In Diffie-Hellman, sometimes A^X=1 MOD N, so that the shared secret ends up being 1, not much of a secret. When does this happen?
    • For which A and N can we solve A^X=1 MOD N? (worksheet)
    • Conclusion: if GCD(A,PQ)=1, then A^(P-1)(Q-1)=1 MOD PQ
    • Therefore: A^{(P-1)(Q-1)+1}=A MOD PQ
    • If we can factor this exponent, say DE=(P-1)(Q-1)+1, then A^D MOD PQ is "messed up", whereas (A^D)^E MOD PQ is "restored" back to A. This is like encrypting and decrypting.
    • Good enough to factor the exponent modulo (P-1)(Q-1), i.e., we just need to find D and E such that DE = 1 MOD (P-1)(Q-1)
    • RSA System: To enable people to send you secret messages, you publish N and D. To send the message A1,A2,..., someone sends A1^D MOD N, A2^D MOD N, ...; to decrypt, you simply raise everything to the E and presto, you get back A1, A2, ...
    • RSA System is one-directional: to send a message back, the other person has to publish their own N and D.
    • Security: To figure out E, you need to know (P-1)(Q-1), so you probably need to know P and Q, which you can find by factoring N. So we must choose N large enough so that factoring it will take thousands of years.
  • Using RSA
    • TI-82 program BIGMUL multiplies 10-digit numbers modulo 10-digit modulus
    • TI-82 program MODEXP computes E^F MOD N for 10-digit numbers
    • Give out list of 5-digit primes
      We restrict to 5-digits so that product N=PQ is at most 10-digits
    • Give out ASCII chart and explain how to use it to convert messages to numbers and back
    • Demonstration of how to randomly pick P,Q, compute N, then randomly pick D (easiest: pick another prime off list), compute E using program EUCLID, publish N,D on board under my name
    • Students do same in groups and publish N,D on board
    • We send messages to students, they decrypt them.
  • Digital Signature Verification
    • What it is
    • How RSA already supports it
    • Padlock analogy
    • Example RSA double-encryption
  • RSA in practice
    • Using really large numbers
    • Primality testing and factoring are not the same


Workshop participants:

Canyon del Oro High School
Tucson, Arizona
Teachers:
  Christopher Yetman
Christopher Yetman's students:
  Chad Reynolds
  Chris Graham
  Phil Hughes
  Joseph Vega
  Brian Weleck
  Daniel Doty
  Curtis Smith
  Mark Major
  Jessica Watters

  

Tucson High School
Tucson, Arizona
Ron Hopley's students:
  Jesse Stone
  Chris Macholtz
  Sara Bachman-Williams
  Augustine Williams
  Matt Brooks
  Linsay Craten

Highland High School
??WHERE??, Arizona
Teachers:
  Robert Grossman
Robert Grossman's students:
  David Grossman
  Peter Yi
  Michael Berry

  

Cholla High School
Tucson, Arizona
Patricia Deeren's students:
  Patricia Ibarra

Douglas High School
Douglas, Arizona
Teachers:
  Denise Garcia

Summary: 3 teachers and 19 students.


Webpage: http://www.math.arizona.edu/~rims/workshops/workshop4Apr98.html
Webmaster: Alexander Perlis