208 http://inventwithpython.com/hacking
Email questions to the author: [email protected]
So some keys will work in the affine cipher while others will not. The secret to determining
which key numbers will work is this:
In the affine cipher, the Key A number and the size of the symbol set must be relatively
prime to each other. That is, gcd(key, size of symbol set) == 1.
We can use the gcd() function we wrote earlier to test this. The key 7 works as an affine cipher
key because gcd(7, 26) returns 1. The larger key 8,953,851 will also work because
gcd(8953851, 26) also returns 1. However, the key 8 did not work because gcd(8, 26)
is 2. If the GCD of the key and the symbol set size is not 1, then they are not relatively prime and
the key won’t work.
The math we learned earlier sure is coming in handy now. We need to know how mod works
because it is part of the GCD and affine cipher algorithms. And we need to know how GCD
works because that will tell us if a pair of numbers is relatively prime. And we need to know if a
pair of numbers is relatively prime or not in order to choose valid keys for the affine cipher.
The second problem with affine cipher’s key is discussed in the next chapter.
Decrypting with the Affine Cipher...........................................................................................................................
In the Caesar cipher, we used addition to encrypt and subtraction to decrypt. In the affine cipher,
we use multiplication to encrypt. You might think that we need to divide to decrypt with the
affine cipher. But if you try this yourself, you’ll quickly see that it doesn’t work. To decrypt with
the affine cipher, we need to multiply by the key’s modular inverse.
A modular inverse (which we will call i) of two numbers (which we will call a and m) is such
that (a i) % m == 1. For example, let’s find the modular inverse of “5 mod 7”. There is
some number i where (5 i) % 7 will equal “1”. We will have to brute-force this
calculation:
1 isn’t the modular inverse of 5 mod 7, because (5 * 1) % 7 = 5.
2 isn’t the modular inverse of 5 mod 7, because (5 * 2) % 7 = 3.
3 is the modular inverse of 5 mod 7, because (5 * 3) % 7 = 1.The encryption key and decryption keys for the affine cipher are two different numbers. The
encryption key can be anything we choose as long as it is relatively prime to 26 (which is the size
of our symbol set). If we have chosen the key 7 for encrypting with the affine cipher, the
decryption key will be the modular inverse of 7 mod 26:
1 is not the modular inverse of 7 mod 26, because (7 * 1) % 26 = 7.
2 is not the modular inverse of 7 mod 26, because (7 * 2) % 26 = 14.