PYTHON
CRYPTOGRAPHY – AFFINE CIPHER

DESCRIPTION

You will write code related to the Affine cipher that can be used in encrypting/decrypting messages.

THE AFFINE CIPHER

Before looking at this cipher, we need to look at numerical values for letters. We start at A equal to 0. See the image below.

The Affine cipher is a substitution cipher where letters are mapped to new letters using the function y = Ax + B mod 26 where

• x is the letter’s original number (see image above)
• y is the encrypted letter’s number
• A is almost any number (details below)
• B is any number

This may seem complicated (it really isn’t) so let’s look at an example.

EXAMPLE
Let’s choose the values A=5 and B=3. So the function is y=5x + 3 mod 26. Let’s look at what the letters A through K will be transformed to.

Letter for x	A	B	C	D	E	F	G	H	I	J	K
x	0	1	2	3	4	5	6	7	8	9	10
Ax + B	3	8	13	18	23	28	33	38	43	48	53
y = Ax + B mod 26	3	8	13	18	23	2	7	12	17	22	1
Letter for y	D	I	N	S	X	C	H	M	R	W	B

Note: Notice that every letter above goes to a different letter. That would be the case if we looked at all 26 letters.

MATH THEORY PART 1 – ONE-TO-ONE

The transformation caused by the function y = Ax + B mod 26 requires one important attribute. It needs to be a one-to-one function.

A one-to-one function is when every value of x leads a to unique value of y. There cannot be two values of x that lead to the same value of y.

An example of a function that is not one-to-one is y=x². It is not one-to-one because x=2 and x=-2 both give the value y=4.

Why is one-to-one important? Well, when we encrypt, we need to be able to decrypt that value. If two letters lead the same new letter, there would be no way to figure out which of those two letters was the original letter in the plaintext.

MATH THEORY PART 2 – COPRIME

While we won’t go into the math detail here, a mathematician discovered a long time ago that for y=Ax + B mod 26 to be one-to-one, there was one requirement:

The size of the alphabet (in our case, 26) and the value of A must be coprime.

That simply means that 26 and A cannot have any common factors.

Since 26 only has the factors 2 and 13, we can chose any A that does not have a factor of 2 (so not even numbers) or of 13.

So A can be 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 and 25. Note that A can continue on to bigger numbers greater than the alphabet size but it would give the same result as another lower value of A.

MATH THEORY 3 – INVERSE FUNCTIONS

So, we know that y = Ax + B mod 26 will be one-to-one (as long as 26 and A are coprimes).

The function y = Ax + B mod 26 can therefore be undone or reversed. A function that undoes another function is called an inverse function. Note that only functions that are one-to-one can have inverse functions.

For example, let’s consider the function y = 2x. Applying this function to a set of numbers will essentially double all numbers. The inverse function, which will half all numbers is y=x/2.

DECRYPTING FUNCTION

The decrypting function (aka the inverse function) for y = Ax + B mod 26 is as follows:

x = A¹(y-b) mod 26

where A¹ is such that A times A¹ mod 26 = 1.

Note: A1 is called either A prime or inverse of A.

Note: Both A and A¹ will be less than the alphabet’s length, so less than 26.

Example

If A is 7, then what value of A¹ allows us to decrypt cyphertext?

Solution

We know that when we multiply A by A1, we have to be off by one compared to a multiple of 26.

The multiples of 26 are:

26, 52, 78, 104, 130, 156, 182, 208, …

Now we add one to those values:

27, 53, 79, 105, 131, 157, 183, 209, …

So we know that A times A¹ has to give one of these values.

We need to find a value that is divisible by 7. (This means that when you divide the number by 7, you get a whole number.)

We try them one by one. 27 is not divisible by 7. Nor is 53 or 79.

The number 105 can be divided by 7 because 7 x 15 = 105.

So the value of A¹ is 15.

FULL ENCRYPTING AND DECRYPTING EXAMPLE

Example

Let’s choose the values A=9 and B=2. So the encrypting function will be y=9x + 2 mod 26.

STEP 1 – FIGURE OUT A¹

Let’s first figure out the decrypting function. We need to know A¹. We know that:

9 times A1 mod 26 = 1

The multiples of “26 plus one” are:

27, 53, 79, 105, 131, 157, 183, 209, …

It turns out that 27 is divisible by 9 as 9 x 3 gives us 27.

So A¹ is 3.

STEP 2 - ENCRYPT

Now, let’s encrypt and then decrypt the letters A through K.

Recall that A = 9, B = 2 and that the encryption function is y=Ax + B mod 26.

Letter for x	A	B	C	D	E	F	G	H	I	J	K
x	0	1	2	3	4	5	6	7	8	9	10
Ax + B	2	11	20	29	38	47	56	65	74	83	92
y = Ax + B mod 26	2	11	20	3	12	21	4	13	22	5	14
Letter for y	C	L	U	D	M	V	E	N	W	F	O

Interestingly, D maps to D in this cipher.

STEP 3 – DECRYPT

Let’s decrypt the line of y.

Recall that A¹ = 3, B = 2 and the decryption function is x = A¹(y-b) mod 26.

Letter for y	C	L	U	D	M	V	E	N	W	F	O
y	2	11	20	3	12	21	4	13	22	5	14
y-b	0	9	18	1	10	19	2	11	20	3	12
A^1(y-b)	0	27	54	3	30	57	6	33	60	9	36
x = A^1(y-b) mod 26	0	1	2	3	4	5	6	7	8	9	10
Letter for x	A	B	C	D	E	F	G	H	I	J	K

Notice that the letters for x at the bottom are the same as the letters we started with. So the encryption and decryption process worked!

Ta dah! It’s like magic! Math is awesome!

WORK

QUESTION 1

In a Python file called Affine, write the function inverse_of that calculates A¹ for a given value of A.

The line print(inverse_of(9)) will output:

3

The line print(inverse_of(11)) will output:

19

Note: There are two examples above showing you how to calculate A¹ from A.

QUESTION 2

Write the enc and dec functions for Affine ciphers. They only need to work with lowercase letters.

enc (word, A, B)

dec (word, A, B)

Note that the dec function will have to call the inverse_of function to get A¹ before doing its work.

Test your code.

QUESTION 3

Decrypt the following sentences that have been encrypted using the Affine cipher

a) with A=17 and B=3

xjgostyhxxjujijovhkxflltxxkfiivqdwjbdojqbdqdxotghjckjt

icjxdyyghejzdotivosgttoshfxdqcxtwtqsfqcgtcdqcontqovohhqt

b) with A=23 and B=1

opqpcwpuurpwgplssz