Skip to main content
Logo image

Discrete Math for Shockers

John Hammond

Section 3.6 Application: Encryption

In this section, we discuss two types of encryption algorithms. The first is a simple algorithm that uses linear congruence functions to encrypt and decrypt. The second, despite being pretty simple to explain is one of the most common encryption algorithms in current use.

Subsection Basic Cipher Examples

Our convention will be to use only capital English letters, A to Z. We will identify each letter with the remainders modulo 26. As our purpose is introducing basics of encryption, we won’t encrypt punctuation or spaces.
Table 3.6.1. List of Alphabet Encoding
letter number letter number letter number
A 0 J 9 S 18
B 1 K 10 T 19
C 2 L 11 U 20
D 3 M 12 V 21
E 4 N 13 W 22
F 5 O 14 X 23
G 6 P 15 Y 24
H 7 Q 16 Z 25
I 8 R 17

Definition 3.6.2. Shift Cipher.

A shift cipher is one in which the letters of the alphabet have been shifted by some fixed amount.

Example 3.6.3.

The classic example is the so-called Caesar Cipher which shifts the alphabet to the right three letters. A becomes D, B becomes E, etc.
We encrypt letter-by-letter via the function \(e(x) = x + 3 \pmod{26}\) and decrypt via \(d(x) = x-3 \pmod{26}\text{.}\)

Definition 3.6.4. Affine Cipher.

An affine cipher is one in which letters are transformed via a linear function, \(e(x) = ax+b \pmod{n} \) where \(a, b\in \Z\) and \(n\in \Z^+\text{.}\) If \(a =1\text{,}\) this is a shift cipher.

Example 3.6.6.

The function \(f(x) = 5x + 14 \pmod{26} \) is an example of an affine cipher function.
  1. Encipher the following letters:
    1. A
    2. M
  2. Given that \(5^{-1} \equiv 21\pmod{26}\text{,}\) find the inverse of \(f(x)=5x+14\pmod{26}\text{.}\) Please ensure your coefficients are reduced modulo \(26\text{.}\)
  3. Verify your inverse by confirming it deciphers the letters above.
Video / Answer.

Definition 3.6.7. The RSA Algorithm.

RSA is an example of a public-key algorithm. Its security is based on the fact that factoring integers is a hard problem. The process is outlined below:
To determine the keys:
  1. Choose two prime numbers \(p \and q\text{.}\) Let \(n=pq\) and \(m = (p-1)(q-1)\text{.}\)
  2. Find any number \(e\) which is relatively prime to \(m\text{.}\)
  3. Determine \(d\) which is the inverse of \(e\) modulo \(m\text{.}\)
  4. Your public key is \((e, n)\text{.}\)
  5. Your private key is \((d, n)\text{.}\)
To encrypt/decrypt:
  1. Convert our message (plaintext or ciphertext) to numeric values, each letter taking up two digits: A is 00, B is 01, ... Z = 25.
  2. Using the chosen \(n\) value, we split the message into blocks of even length according to the following scheme:
    1. If \(2525 \lt n \lt 252525\text{,}\) then the blocks will be length 4
    2. If \(252525 \lt n \lt 25252525\text{,}\) then the blocks will be length 6
    3. If \(25252525 \lt n \lt 2525252525\text{,}\) then the blocks will be length 8
    4. and so on...
    if the message doesn’t fit the appropriate block size, append a number of 23’s at the end. (padding the message with X’s).
  3. Encryption occurs my taking each numeric message block \(M\) and computing \(M^e\pmod{n}\)
  4. Decryption occurs my taking each numeric cipher block \(C\) and computing \(C^d\pmod{n}\)
This works because \((M^e)^d = M^{ed} = M^1 \pmod{n}\text{.}\) Although we haven’t proven this, it’s a result of Euler’s Totient Theorem which you’ll revisit in future course on number theory.

Example 3.6.8.

Let \(p = 59, q=83\text{.}\) Choose \(e=15\) Encrypt “WHATS UP” and then decrypt the result to confirm it worked. Do this by hand (with the help of a calculator).
Video / Answer.

Exercises Exercises

1.
Decrypt the following message, which was encrypted by the standard Caesar cipher: “L FDQ DOZDBV WUXVW BRX, EUXWXV.”
Solution.
“I can always trust you, Brutus.”
2.
Apply the affine shift \(e(x) = 7x + 11 \pmod{ 26 }\) to the string, “Encrypt me.”
Solution.
Removing spaces from the words and capitalizing everything: “NYZAXMOORN”. The integer values are 13, 24, 25, 0, 23, 12, 14, 14, 17, 13.
3.
Decrypt the text which was encrypted via the affine shift \(e(x) = 7x + 11 \pmod{ 26 }\text{:}\) “LJNHFRN”
Solution.
“Awesome”.

Subsection Number Theory Using Sage

Sage has a convenient way of determining if a number is prime by asking if the number is in a set primes:
Try testing any number in the cell above.
If you want to just want to get a prime number of some particular size (as we want with our RSA activity), we ask sage for the next_prime:
The following Sage code allows us to find the GCD and Bézout coefficients via the xgcd command:
The xgcd command returns a list of the form (gcd, first Bézout coefficient, second Bézout coefficient), and the code above pretty-prints this in a readable format.
In order to do modular exponentiation, we use the powermod function. For example, to compute \(2022^{2022} \pmod{1000}\text{:}\)

Subsection The RSA Activity

In this activity, you will generate a public/private key-pair. You will send me the public key and keep your private key secret (but don’t lose it! If you lose your private key, you won’t be able to complete the assignment and will receive no credit).
  1. Pick two prime numbers \(p \and q\) of some interesting size. Make them at least six or seven digits long (use Sage’s next_prime).
  2. Let \(m=(p-1)(q-1)\text{,}\) and pick any number \(e\) relatively prime to \(m\text{.}\)
  3. Find the multiplicative inverse, \(d\text{,}\) of \(e\) modulo \(m\text{.}\)
  4. Let \(n = pq\text{.}\)
  5. Record your numbers \((n, p, q, m, e, d)\) somewhere safe (but much of this is private! Keep it secret!).
  6. Send me your public key on via email (you can click this link!) 4  as:
                  n = 15244346903
              e = 751
  7. I’ll send you an encrypted message which will look like:
    [971896385, 3249912096, 4079022731, 8771096382, 10148198704]
  8. Enter this information into the Sage cell below to decrypt it (using your \(n, d, \and c\)), change what_to_do to “decrypt”, and then press Evaluate(Python).
  9. Send me the decrypted message to confirm you decrypted it correctly (remove the padded X’s if relevant, and put appropriate spaces to make it a normal English statement. For example “KEEPITSECRETKEEPITSAFEXX” will not receive full credit.
Video / Answer.
john.hammond@wichita.edu
<Prev^TopNext>