Skip to main content

Quantitative Reasoning for Social Justice: An Active Learning Workbook

Kenan Ince

Section 3.2 Extensions and Alterations

These resources are currently used at a small liberal arts college in an entire first-year seminar course entitled “Making & Breaking Secret Codes.” As such, the project described above is supplemented with additional material and assignments such as the Python modules [cross-reference to target(s) "inceResourcesFirstYearCollege2022" missing or not unique] and pre-class Reading Questions, often from [cross-reference to target(s) "singhCodeBookScience2011" missing or not unique].
In this course, most of the material in [cross-reference to target(s) "mcdevittClassNotesCryptologic2012" missing or not unique] (which is also provided to students as a supplementary resource) is discussed, with the possible exception of probability, which is often left out due to time constraints. A sample of the discussion of the Diffie-Hellman key exchange and modular exponentiation is provided in Section [cross-reference to target(s) "KI-subsec:The-Diffie-Hellman-Key" missing or not unique]. These notes lead into the material on the square-and-multiply algorithm, Euler’s Theorem, and eventually RSA encryption described in [cross-reference to target(s) "mcdevittClassNotesCryptologic2012" missing or not unique]. Sometimes, the extended Euclidean algorithm is also introduced after describing the importance of finding multiplicative inverses when cryptanalyzing the affine cipher, though students without much prior mathematical experience tend to find this material confusing and somewhat intimidating.
This activity has not yet been extended to a research project; however, some ideas for such projects are included in Section [cross-reference to target(s) "KI-subsec:Potential-Undergraduate-Research" missing or not unique].
Finally, these notes arose from a course originally taught in the Duke TIP summer program which included an “evening session” in which students were walked through the Python modules found in [cross-reference to target(s) "inceResourcesFirstYearCollege2022" missing or not unique]. It is highly recommended to guide students through these modules if they are used, since students without prior coding experience often find Python, especially its ubiquitous and sometimes uninformative syntax error messages, intimidating. The Python modules could also be used as the “backbone” for an independent study on the use of programming in cryptography and/or to introduce the material described above.

Subsection 3.2.1 The Diffie-Hellman key exchange

In order to introduce more contemporary (i.e., post-\(1970\)) cryptography, specifically public-key cryptography, it is recommended to start with the Diffie-Hellman key exchange. The idea is introduced via discussion of the problem of informing the intended recipient what key to use to send an encrypted message (the key distribution problem), quite a significant issue: if one lives in a government where all Internet traffic is subject to government search, for example, how does one send a message across the world? Students often suggest physically transporting a key or sending a person to tell the recipient the key, but that just reframes the problem in terms of safely getting the key or person physically to the intended location.
At this stage, students engage in a Socratic dialogue on whether it’s possible to solve the key distribution problem. In other words, suppose Alice wants to send a message to Bob, and suppose they live in a country in which any unencrypted message, or any key, will be intercepted and read by the postal service. For this discussion, imagine that Alice has a physical key that she wants to send to Bob in such a way that it can’t be opened by the postal service. How could Alice do this?
One way that students eventually arrive at to solve this problem is that Alice can somehow secure the key so that it can’t be opened before Bob receives it. However, this begs the question of how Bob can access the key. Some semesters students discover the analogy used by Simon Singh in his excellent Code Book [cross-reference to target(s) "singhCodeBookScience2011" missing or not unique], which is usually assigned as a required text to provide students with historical background. Singh’s presentation is eminently readable without sacrificing accuracy or detail.
In any case, the analogy works in the following steps:
  1. Alice places her key inside a box and uses a padlock to lock the box. Alice keeps the key to the padlock and sends the locked box to Bob.
  2. The box can’t be opened in transit without Alice’s key. When Bob receives the box, he places an additional padlock on the box and keeps the key to his padlock. Bob then sends the doubly-locked box back to Alice.
  3. Again, the box can’t be opened in transit without both Alice and Bob’s keys. When Alice receives the box, she unlocks her padlock and sends the box back to Bob.
  4. Finally, the box can’t be unlocked in transit without Bob’s key. However, once Bob receives the box, he simply unlocks his padlock and opens the box.
This little story provides a solution to one of the oldest and most important problems in cryptography, the key exchange problem. Exchanging keys (whether physical or cryptographic) is a deeply vulnerable part of cryptography, and historically, if Alice and Bob wanted to exchange secret messages, they must first meet or somehow transmit a secret key unencrypted. Anyone who intercepts the key would be able to read any purportedly secret messages sent between Alice and Bob.
Now, the astute reader may notice that the analogy above requires double-encryption with our given cipher to be commutative. Students then investigate which ciphers discussed so far actually have this property. This is a worthwhile pre-class activity to assign: is the shift cipher commutative? That is, if we want to encrypt a message with two consecutive shift ciphers, does it matter which order we use (it does not)? What about affine ciphers (it does)? Vigenère ciphers (it does not)? Other ciphers?
What is really needed is a mathematical process that works more like padlocks than socks and shoes. In other words, we want to be able to have Alice and Bob each add their locks, then take them off in the opposite order in order to decrypt the message. And we want to do this without it being possible for anyone who intercepts the message to decrypt it! We want a trapdoor one-way function (easy to encrypt, hard to decrypt without the key) in which encryption with two keys is the same as decryption. A one-way function that arose in the affine cipher is multiplication mod \(p\) - finding inverses is hard!
This stage is a perfect time to introduce modular exponentiation and the theory behind it, which turns out to be the “lock” we use for the Diffie-Hellman key exchange. Though the treatment in these notes ends here, the treatment in [cross-reference to target(s) "mcdevittClassNotesCryptologic2012" missing or not unique] is recommended for courses without prerequisites, or the instructor’s favorite number theory book for proof-based courses. These suggested materials also include the Extended Euclidean Algorithm, an introduction to Euler’s totient function, Fermat’s Little Theorem, Euler’s Theorem on the totient function, and proofs of all theorems involved appropriate in level for an introductory abstract algebra or number theory course.

Subsection 3.2.2 Potential undergraduate research projects

The following are research projects that may be suitable for undergraduates who have a reasonable grasp on the material above and are interested in continuing to explore cryptography. In particular, these have been considered as research directions in a two-month summer undergraduate research program where the goal for students is primarily to gain mathematical maturity (defined here as gaining the ability to read research papers and to experience working on unsolved problems), not necessarily to prove publishable results.
  1. Read [cross-reference to target(s) "smithMakingHashThings2015a" missing or not unique]. Invent and test a new hash function. Perturb some conditions and see what happens.
  2. Read [cross-reference to target(s) "christensenPolishMathematiciansFinding2007a" missing or not unique]. Perturb some conditions in Rejewski’s Theorems and see what happens.
  3. Read Problem \(1727\) in [cross-reference to target(s) "johnstonProblems2006" missing or not unique] and its solution. Though this problem has already been solved, students could solve similar problems, perhaps by changing the seed or experimenting with determining the periods of the sequences generated from various seeds.
  4. Read [cross-reference to target(s) "marzuoliPostQuantumCryptography2011" missing or not unique]. How could one break this cryptosystem? Investigate Shor’s algorithm and the ability of quantum computers to cryptanalyze RSA. How could Bob know how to mutate the knots without using RSA? Investigate alternate key exchange algorithms (besides public or private key encryption). Could one use a public knot whose inverse is hard to find and mimic RSA?
<Prev^TopNext>