Lecture Notes on Modular Arithmetic and Ciphers

Contradiction and Homework

• If a question requires using contradiction, do so.
• Homework 18 covers section 4.4.
• Skip section 4.5; it is not part of the homework.
• Homework 19 covers section 4.6.
• The average missing homework rate is 4.6, so four lowest homework scores will be dropped.
• If a homework is not submitted, it will be scored as zero and dropped.
• The average missing quiz rate is two.
• There are eight quizzes plus one survey. The two lowest quiz scores will be dropped.

Solving Linear Congruences

• Use the Euclidean algorithm to find the inverse to solve linear congruences like $7x \equiv 6 \pmod{n}$.

Section 4.6: Applications to Cryptography

• Section 4.6 covers ciphers, which are applications of modular arithmetic.

Caesar Cipher

• The Caesar cipher is a simple shift cipher.
• It shifts each letter by a fixed number of positions.
• For example, shifting three letters forward:
  • A becomes D.
• To encrypt "city" with a shift of 3:
  • c becomes f,
  • i becomes l,
  • t becomes w,
  • y becomes b,
  • The encrypted word is "flwb".

Encryption and Decryption

• Encryption should always be decryptable; otherwise, information is lost.
• Decryption for a forward shift involves shifting backward.
• Treat encryption as a function mapping from a domain to a co-domain.
• Decryption is the inverse function, mapping back from the co-domain to the domain.
• Example: If the function maps A to D, the inverse function maps D to A.
• To decrypt "SDUIN" with a shift of 3, shift each letter back three positions.
  • s becomes p,
  • d becomes a,
  • u becomes r,
  • i becomes k,
  • n becomes k.
  • The decrypted word is "park".

Numbering Letters for Modular Arithmetic

• Number the letters from 0 to 25 instead of 1 to 26 to align with modular arithmetic.
• A shift of 3 forward can be represented as $P + 3 \pmod{26}$, where P is the original letter's numerical value.
• If $C = 2$, then $F(C) = 2 + 3 = 5$, which corresponds to the letter F.
• If $X = 23$, then $F(X) = 23 + 3 \pmod{26} = 26 \pmod{26} = 0$, but is is actually 0. This is equivalent to 0.

Decryption Key

• Decryption shifts letters backward.
• If the encryption function is $F(x) = x + 3$, the decryption function is $F^{-1}(x) = x - 3$.
• The inverse function undoes the encryption.
• When doing $mod 26$, one can consider it as grouping into sets of 26.

Inverse of Mod

• The concept of an inverse function still applies under mod 26.
• Because 1 and 26 are relatively prime, it is easy to find the inverse.
• It is acceptable to write the mod 26 once at the end of an equation, implying it applies to the entire equation.
• There is no remainder for the numbers equal to or less than the divisor. For example, $6 mod 26 = 6$, $41 mod 26 = 15$.

Example: Decrypting with the Key

• If $s = 18$, the decryption function $G(s) = 18 - 3 = 15$, which is the letter P.

Cipher Key

• Shift ciphers use a key, $K$.
• Encryption: $P + K \pmod{26}$.
• Decryption: $P - K \pmod{26}$.
• The key $K$ must be kept secret to maintain secure communication.
• Knowing K enables both encryption and decryption.

Definition Format in Mathematics

• Definitions are fundamental rules for a mathematical structure. Definitions act as a rule for the mathematical structure.
• Definitions are the foundation, and results are judged to be correct based on the definitions.

Example: Encrypting "Stony Brook Wing" with Key 11

• Convert the letters to numbers (A=0, B=1, …, Z=25):
  • S = 18, T = 19, O = 14, N = 13, Y = 24, B = 1, R = 17, O = 14, O = 14, K = 10, W = 22, I = 8, N = 13, G = 6
• Apply the encryption function $F(P) = P + 11 \pmod{26}$.
  • For S (18): $18 + 11 = 29 \pmod{26} = 3$, which is D.
• The encrypted message starts with DBB…

Decryption Process

• To decrypt, use the function $G(P) = P - 7 \pmod{26}$.
• Find the numerical value, subtract 7, and take the result mod 26 to convert back to letters.

Induction

• Induction was briefly mentioned, deferring a detailed discussion.

Adjusting Values to the 0-25 Range

• To ensure values are within the 0-25 range, add or subtract 26 as needed.
• For $6 mod 26$, the result is 6 because 6 is already within the range.
• If a result is negative, add 26 to bring it into the 0-25 range.

Affine Cipher

• The affine cipher is a more complex cipher with the form $aP + b$.
• $a$ and $b$ are integers.
• A necessary condition is that $GCD(a, 26) = 1$, where, A and 26 are realtively prime.
• This ensures the existence of a decryption function.
• For example, $7P + 3$ is a valid affine cipher since $GCD(7, 26) = 1$.

Using the Affine Cipher

• To encrypt using $7P + 3$, convert letters to numbers, apply the formula, and take the result mod 26.

Decryption Functions

• Find the inverse to decrypt the message

• Given a ciphertext $c$, the goal is to find the original plaintext $p$.

• Solve the equation $ap + b \equiv c \pmod{26}$ for $p$.

• Isolate $p$ by subtracting $b$ and dividing by $a$.

• To solve for $x$ in the linear congruence $ax + b = 5$, first subtract $b$ from both sides, then divide by $a$.

• $x = (5 - b) / a$. Similarly, we can perform the same process in our linear congruence.

Solving for $p$ Modulo 26

• Isolate $p$ in the equation $ap \equiv c - b \pmod{26}$.
• Multiply by the inverse of $a$ modulo 26. Since $GCD(a, 26) = 1$, an inverse exists.
• If a is not equal to one, then decryption function will be more complicated.
• The inverse of $a$, denoted $a^{-1}$, satisfies $a * a^{-1} \equiv 1 \pmod{26}$.

Finding the Inverse

• The inverse can be found using the Euclidean algorithm.
• The inverse, means $a * a^{-1} \equiv 1 \pmod{26}$.

Practice with Euclidean Algorithm

• Try the Euclidean algorithm to find the inverse of 7 mod 26.

Correctness and Alternative Approaches

• If a question asks to use the Euclidean algorithm, using trial and error will not grant full credit.

• A proper balanced mathematical equation is represented as mp equivalent to a times p plus b.

• When encryptying, we know $p$, but we wish to find $c$.

• When decrypting, we know $c$, but we wish to find $p$.

• Since division doesn't work in modular arithemetic, use an inverse.

• By the property of inverses, the variable will be isolated in order to decrypt.

Deciphering Steps

• The general way is as follows:
  $gcd(7,26)$
  Apply the Euclidean algorithm. First divide by 26 by 7, the divisor will then become the new dividend. The divisor of 26 is 7, with quotient, 3, then there is a remainder of 5.
• Then, 7 becomes a divisor with the dividend will be 25, with a quotient of 1 and a remainder of 2.
• For 5 becomes the new dividend with a divisor of 2, a quotient of 2, and a remainder of 1.

Back-Substitution for Bezout Coefficients

• Next we will find the Bezout coefficient:
• To find the coefficients a and b such that $1 = a * 7 + b * 26$
• Start with $1 = 5 - 2 * 2$, then, using previous equations to subtitute into the equations.
  Then use the equation from previous steps: $2 = 7 - 5 * 1 \newline 1 = 5 - 2 * (7 - 5 * 1) \newline = \dots \newline = 15 * 7 + (-4) * 26$
• Then use the equation from previous steps: $5 = 26 - 7 * 3 \newline 1 = \dots + 11 * 7 + \dots -1 = *26,$
• So, $117 \pmod{26}$, is the inverse of 7. This is used for solving for \p in the original equation.

Result

The correct form will be used:
$c - 3 = P \pmod{26}$
$-P + 11 = C \pmod{26}$

• Practice these algorithms. Practice it to make sure you know what you are doing.
• Final results are the Bezout coefficients and remainders, be sure to use all the information.

RSA

• If you already have experience with RSA ignore the concepts.

Public and Private

• There is cracking public and private cryptography, however to crack the public key, RSA, is relatively harder than the private key cyphers.

Review

• Finalize with a review of all exam three materials.
• Bring questions to the monday review session so discussion can be much smoother.
• Do not screen shot the math problem. This is an output and not secure.