|
|
|
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
|
|