Skip to main content

Quantitative Reasoning for Social Justice: An Active Learning Workbook

Kenan Ince

Subsection 3.5 Onramp to number theory

At this stage, students are ready to learn the material in a standard integer division and modular arithmetic unit, in the order you wish to present it for your context. For example, the material of Chapters \(2\) through \(8\) of [cross-reference to target(s) "crismanNumberTheoryContext2021" missing or not unique], from integer division and Diophantine equations to the so-called “Chinese” (in particular, Sun-tzu) remainder theorem and the theory of cyclic groups, are all motivated by the theory of affine ciphers and can be covered at this stage. We highly recommend calling back to cryptography whenever possible; the following section is an overview of one possible order in which various number-theoretic results can be motivated by the theory of affine ciphers.
Following the presentation of shift ciphers above, students may then practice encrypting and decrypting affine ciphers with known multiplicative and additive keys. Prompt them to consider how they would cryptanalyze an affine cipher. After using frequency analysis, they may determine which ciphertext letter corresponds to \(e\text{,}\) but this is not enough since we need to solve for two unknowns, \(m\) and \(k\text{.}\) So students may realize we need to find two letter pairs of the form \((p,c)\) where \(c=f(p)\) and set up a system of congruences
\begin{equation*} \begin{aligned} c_{1} & \equiv m\cdot p_{1}+k\nonumber \\ c_{2} & \equiv m\cdot p_{2}+k\mod26.\label{KI-eq:affine-cipher-system} \end{aligned} \end{equation*}
Students may remember how they solved systems of equations in high school. It is recommended to encourage them to use elimination, not substitution, in preparation for future linear algebra classes down the road.
A fruitful area of inquiry at this point is to prompt students how, once they obtain a single congruence of the form
\begin{equation*} c_{2}-c_{1}\equiv m(p_{2}-p_{1})\mod26, \end{equation*}
they might solve for \(m\text{.}\) Usually students think they can simply “divide by \(p_{2}-p_{1}\text{,}\)” so it takes some prompting (“what if \(p_{2}-p_{1}=13\text{?}\)”) for them to realize this is not always possible modulo \(n\text{.}\) This is a natural spot to introduce the idea of inverses modulo \(26\text{,}\) and more generally modulo \(n\text{.}\) We’ll start with some more basic facts and build up to solving systems of congruences.
The multiplicative inverse \(a^{-1}\) of \(a\mod n\) is the number \(a^{-1}\) so that \(aa^{-1}\equiv1\mod n\text{,}\) if such an \(a^{-1}\) exists. Recall that a number is prime if the only integers that divide it are \(1\) and itself. Composite numbers are integers greater than one that are not prime. Every positive whole number has a unique prime factorization, i.e. a way to write it as a product of prime numbers. This fact is called the Fundamental Theorem of Arithmetic.
6. Have students attempt to encrypt given messages with the affine cipher using various multiplicative and additive keys. To illustrate the relevant idea that \(c\equiv mp+k\mod n\) is monoalphabetic if and only if \(\gcd(m,n)=1\text{,}\) have students use at least one \(m\) relatively prime to \(26\) and one \(m\) that is not (for example \(m=13\text{,}\) which makes very clear to students that the resulting affine cipher is not monoalphabetic and near-impossible to decrypt even by someone who knows the key).
Ask students: from the work you just did, what multiplicative keys do you think “work” for affine ciphers? What is the “problem” with the keys that don’t work? Even if they don’t have a complete sense of the issue, have them explain their hypothesis. Prompt students to make multiplication tables modulo \(n\) for some reasonably small composite \(n\text{;}\) ask them to compare what happens in rows which are relatively prime to \(n\) versus rows that aren’t. How might this connect to the issue with the affine cipher \(c\equiv13p+k\mod26\text{?}\) What patterns do they notice or wonder about?
Hopefully students will realize that there are significant problems with an affine cipher where \(m\mid26\text{!}\)
9.
  1. At this point, it is useful for students to make themselves a “cheat sheet” which tells them the multiplicative inverse of any number mod 26, if it exists. (My expectation is not that they memorize such a list, though more power to them if they’d like to!) At this point, the most likely strategy students will use to find \(m^{-1}\mod26\) is trial and error: multiplying each \(m\) by various integers mod \(26\) until they end up with \(1\mod26\text{.}\) The number they multiplied by to get \(1\) is their \(m^{-1}\text{,}\) if such a number exists. Ask: what relationship between \(m\) and the modulus \(26\) predicts whether \(m^{-1}\) exists?
  2. In an introduction to proof or number theory class, this would be an excellent time to prompt students to prove that \(m^{-1}\) exists modulo \(n\) if and only if \(\gcd(m,n)=1\text{.}\) Prompt them to think about their multiplication tables and the fact that every integer modulo \(n\) appears in the \(m\)th row precisely when \(m\) and \(n\) are relatively prime. In fact, students can prove that
    7. If \(m\) is a whole number between \(0\) and \(n-1\text{,}\) then \(\gcd(m,n)\) divides any number that’s congruent to \(m\mod n\text{.}\)
    One prompt to lead students toward the general proof is the following specific example: assume some number \(x\) is congruent to \(m=4\mod12\text{.}\) Then \(x/12=yR4\) (here \(R\) denotes “remainder” in language that should be familiar to students), where \(y\) is some whole number. So \(x\) is some multiple of \(12\) plus \(4\text{;}\) we can write \(x=12y+4\text{,}\) where \(y\) is some whole number. Now, \(\gcd(4,12)=4\) and \(x=4(3y+1)\) is divisible by \(4\text{.}\)
  3. At this point, students have the cheat sheet and tools necessary to decrypt affine ciphers with known key. Have them try decrypting some example ciphertext under various affine ciphers. Naturally, students may at first be most comfortable only doing arithmetic modulo \(26\text{,}\) but it takes surprisingly little in my experience to prompt them to consider other moduli. Students may try decrypting affine ciphers in different alphabets at this stage: for example, decrypt \(c\equiv7p\mod29\) using the lowercase English alphabet with !?, appended. We need to multiply both sides by some number \(x\) so that \(7x\equiv1\mod29\text{.}\) How do we systematically find \(x\text{?}\) This is a great time for an optional detour into the extended Euclidean algorithm; students without much previous college-level math experience often find this difficult, so it may be skipped without losing the thread of this activity.
  4. Students in a proof-based course may now attempt to prove the following corollary of Proposition [cross-reference to target(s) "KI-prop:gcd(m, n)-divides-mk" missing or not unique].
    8. If \(\gcd(m,n)\neq1\text{,}\) then no multiple of \(m\) is congruent to \(1\mod n\text{.}\) In other words, we can’t get every number in row \(m\) of the \(\mod n\) multiplication table, and \(m\) does not have a multiplicative inverse \(\mod n\text{.}\) In fact, the following are equivalent for any whole numbers \(m,n\text{:}\)
    1. \(\gcd(m,n)=1\text{.}\)
    2. any affine cipher with multiplicative key \(m\mod n\) is decryptable by the intended recipient.
    3. every number between \(0\) and \(n-1\) is a multiple of \(m\mod n\text{.}\)
    4. \(m\) has a multiplicative inverse \(m^{-1}\mod n\text{.}\)
    An example that may lead students toward part of the proof: consider the affine cipher \(c\equiv13p\mod26\text{.}\) Note that \(\gcd(13,26)=13\text{.}\) Any plaintext letter that we plug in will spit out some multiple of \(13\text{.}\) Reduced mod \(26\text{,}\) these multiples of \(13\) all become either \(13\) or \(0\text{.}\) And \(\gcd(13,26)=13\) divides both \(13\) and \(0\) evenly. Since no multiple of \(13\) can be congruent to \(1\mod26\text{,}\) \(13\) does not have a multiplicative inverse modulo \(26\text{.}\)
  5. Now, prompt students to consider how important it is before decrypting an affine cipher to verify that \(\gcd(m,n)=1\text{.}\) Given a cipher like \(c\equiv137p+538\mod341319\text{,}\) how could students determine whether the cipher was monoalphabetic, and hence whether our techniques will decrypt it?
  6. Computers can only understand numbers (which are written in \(0\)s and \(1\)s), not letters. The computer language ASCII represents all commonly-used written characters as numbers between \(1\) and \(256\text{.}\) Do you think we can encrypt ASCII messages using the affine cipher \(C\equiv8P\mod256\text{?}\) Why or why not? What multiplicative keys can be used in a monoalphabetic, affine ASCII cipher?
We now may introduce the Euclidean algorithm as a powerful (and programmable) tool for finding greatest common divisors. A recommended way of introducing the Euclidean algorithm, as in much of these notes, is to start with an example.
10.
  1. Suppose we want to find the greatest common divisor of, say, \(261\) and \(231\text{.}\) Have students recall (perhaps by verifying a specific example) that, if a number divides both \(261\) and \(231\text{,}\) then it divides \(261-231=30\) as well. Similarly, if a number divides both \(231\) and \(30\) (as it must if it divides \(261\) and \(231\)), then it divides \(231-30=201\text{,}\) and \(201-30=171\text{,}\) and\(\dots231-30(7)=21\text{.}\) Therefore, \(\gcd(261,231)=\gcd(231,30)=\gcd(30,21)=\dots\text{.}\) Hence, compute \(\gcd(261,231)\) and verify it using a method more familiar to you, such as factor trees.
  2. Prove that the Euclidean algorithm “works” in general to compute \(\gcd(m,n)\) for any \(m,n\in\mathbb{Z}\text{.}\)
  3. Use the Euclidean algorithm to compute the gcds of two or three pairs of numbers. It may benefit students to make the first pair of numbers relatively small and one of the pairs relatively large such that the pair of large numbers has a quick Euclidean algorithm solution which is nonobvious using the method of factor trees. For example, one may use any pair of numbers of the form \((n,kn+1)\) for some \(n,k\in\mathbb{N}\text{.}\)
  4. Unicode is an updated version of ASCII. Unicode gives a way of encoding information on a computer with \(1,114,112\) possible numbers. Only about \(10\%\) of them are currently in use; say there are \(111,411\) Unicode numbers in use. Does the affine cipher \(C\equiv103,011P+34,423\mod111,411\) encrypt Unicode characters monoalphabetically?
To motivate solving systems of linear congruences, we may use the cryptanalysis of affine ciphers. As in ([cross-reference to target(s) "KI-eq:affine-cipher-system" missing or not unique]) above, systems of linear congruences arise naturally after guessing two plaintext-ciphertext pairs in an affine cipher. Solving the system is necessary to determine the multiplicative and additive keys of the affine cipher, hence to decrypt it. The dangerous thing for students at this point is to make the “wrong” guess and end up trying to solve a congruence of the form \(am\equiv b\mod26\) where \(\gcd(a,26)\neq1\text{.}\) This is an excellent time to discuss the general theory of solving linear congruences, and if you wish even generalize to polynomial, factorial, and other more general congruences. At any rate, students may now use the following algorithm to cryptanalyze any monoalphabetic affine cipher:
  1. Form a system of linear congruences to solve for \(m\text{,}\) the multiplicative constant, and \(k\text{,}\) the additive constant.
  2. Simplify the system of congruences by substitution, elimination, or addition/subtraction of congruences.
  3. Find the solution of the resulting congruence using trial and error or the extended Euclidean algorithm.
  4. Use \(m\) and \(k\) to decrypt the ciphertext using the formula \(p=m^{-1}(c-k)\) mod \(26\text{.}\)
To accomplish step \(1\text{,}\) students must guess two plaintext-ciphertext pairs, and to avoid insoluble congruences, it suffices to always guess the ciphertext corresponding to plaintext \(e,t\text{.}\) Students can type the messages into an online frequency analysis tool to get a frequency count, or, in a more programming-focused course, the collection of Python modules at [cross-reference to target(s) "inceResourcesFirstYearCollege2022" missing or not unique] includes a module in which students write a frequency analysis tool themselves in Python.
Students may notice one issue with this algorithm: what if you have no idea what ciphertext letter corresponds to plaintext \(e\) in your message? Certainly English messages may have different most-common letters. This could lead to a lesson on the index of coincidence and other probabilistic methods for determining both which cipher we’re dealing with and matching letter frequencies. Though these concepts are beyond the scope of these notes as written, see Chapter \(2\) of [cross-reference to target(s) "mcdevittClassNotesCryptologic2012" missing or not unique] for an excellent treatment without prerequisites.
11.
  1. Encrypt some short (\(3\)-\(10\) words) plaintext using an affine cipher of your choice. Now, give students the equation of the affine cipher (say, \(c\equiv 3p+2\mod26\)) and have students determine the decryption equation for that affine cipher by solving for \(p\) in the cipher’s equation. Finally, use that decryption equation to determine the plaintext \(p\) corresponding to each given ciphertext letter \(c\text{,}\) and hence decrypt the message.
  2. Encrypt some short (\(3\)-\(10\) words) plaintext in which the most common letter is ‘e’ and the second-most common is ‘t’) using an affine cipher of your choice. Now, have students use the algorithm to cryptanalyze this affine ciphertext.
At this point in the project, one may introduce the Vigenère cipher and its primary tools for cryptanalysis, the Kasiski and Friedman tests. This leads naturally to asking what happens when a Vigenère keyword is as long as the message it’s used to encrypt, whence students can prove to themselves that such a cipher (a one-time pad) is theoretically unbreakable by showing that different keywords lead to intelligible, but different, plaintext messages. The Enigma machine is then introduced as a “portable one-time pad generator,” providing an opportunity to tie the course to the more recent history of World War II.
However, because these concepts are less explicitly connected to number theory and algebra, they are omitted in this text. See [cross-reference to target(s) "mcdevittClassNotesCryptologic2012" missing or not unique] for an excellent set of notes for those who choose to teach this material.
<Prev^TopNext>