Chapter 14 – Modular Arithmetic and the Multiplicative Cipher 205“Relatively Prime”
Relatively prime numbers are used for the multiplicative and affine ciphers. We say that two
numbers are relatively prime if their greatest common divisor is 1. That is, the numbers a and b
are relatively prime to each other if gcd(a, b) == 1.
Practice Exercises, Chapter 14, Set C
Practice exercises can be found at http://invpy.com/hackingpractice14C.
The Multiplicative Cipher
In the Caesar cipher, encrypting and decrypting symbols involved converting them to numbers,
adding or subtracting the key, and then converting the new number back to a symbol.
What if instead of adding the key to do the encryption, we use multiplication? There would be a
“wrap-around” issue, but the mod operator would solve that. For example, let’s use the symbol
set of just uppercase letters and the key 7. Here’s a list of the letters and their numbers:
0 1 2 3 4 5 6 7 8 9 10 11 12
A B C D E F G H I J K L M13 14 15 16 17 18 19 20 21 22 23 24 25
N O P Q R S T U V W X Y Z
To find what the symbol F encrypts to with key 7, multiply its number ( 5 ) by 7 and mod by 26 (to
handle the “wrap-around” with our 26-symbol set). Then use that number’s symbol. ( 5 × 7) mod
26 = 9 , and 9 is the number for the symbol J. So F encrypts to J in the multiplicative cipher with
key 7. Do the same with all of the letters: