Historic Ciphers and Modular Arithmetic

Question 1

What is Congruence?

Answer 1

Congruence is the principle that checks whether two numbers, when a mod is applied, have the same remainder. Example:
17 and 5 both have a remainder of 5 when mod 12 is applied to them.

Question 2

What are equivalence classes?

Answer 2

Equivalence classes are sets of numbers that have the same remainder when a mod is applied e.g. -5, 0 and 5 all have a mod of 0 when mod 5 is applied

Question 3

What is a ring?

Answer 3

A ring is a set of numbers where you can add or multiply any two numbers together and the result is another number in the ring.

Question 4

What are the 5 core features that make a set a ring?

Answer 4

• Closure i.e. if you perform an operation on two numbers, then the result remains in the set.
• Associativity i.e. it doesn’t matter how you group numbers in an operation, the result is still the same
• Additive Identity i.e. there is a number in the ring that, when added to any other number, the result is the original number
• Additive Inverse i.e. for every number in the ring, you can add a number to it to make it 0
• Distributive Property i.e. multiplying a number across a sum works how you would expect it to

Question 5

How can you find if a number has a modular inverse?

Answer 5

Take the number and the number that you were modding by, and calculate the greatest common denominator between the two. If the answer is 1, then it has a modular inverse

Question 6

What is a modular inverse?

Answer 6

A modular inverse is when a number can be multiplied by a second number to make a total that, when divided by the modulus, results in a 1.

Question 7

What is a Shift Cipher?

Answer 7

A Shift Cipher is also known as a Caesar Cipher, which takes a letter, and shifts the value by k amount. If the shift exceeds the alphabet, then it wraps back around to the beginning/end, depending on direction.

Question 8

Why is an Affine Cipher stronger than a Shift Cipher?

Answer 8

More key options: Range increases from 26 to 312
It contains multiplicative and additive transformations, increasing complexity

Question 9

What are both Affine Ciphers and Shift Ciphers weak to?

Answer 9

A frequency analysis will be able to crack the cipher incredibly quickly