Additive Ciphers 264422

Additive Ciphers The simplest code is an additive cipher. Each coded letter is simply shifted a certain number of spaces from the plain text letter. The number of spaces the letter has been shifted is called the key. The example shown below uses a key of 5. Using lowercase letters for plaintext (messages which are not encoded ), and capitol letters for ciphertext (encoded text), a → F, b → G, etc. It is sometimes easier to do this by the number of the letter. a is letter #1. Since 1 + 5 = 6 we want the 6th letter, F, to represent a. (Note: lowercase is used for plain text, uppercase is used for cipher text)

Figure 1: Additive Cipher Ring with Key = 5 When we try to encode the letter y, though, 25 + 5 = 30. What is the 30th letter? On the code ring it is obviously D. How’s that work? Mathematically, we need to use modular addition. We use modular addition all the time. If we look at the clock at 10 o’clock and need to be somewhere in four hours, we know 10 + 4 = 14. 14 mod 12 means find the remainder of 14 ÷ 12, which is 2. Therefore, 10 + 4 = 2 (mod 26). To find the 30th letter, since there are 26 letters, we want to find 30 mod 26 = 4. The fourth letter is D. ENCODING The message “the world is green and blue.” would be encoded “YMJ BTWQI NX LWJJS FSI GQZJ”. To further disguise the message we might break the encrypted message into character blocks of any length, say 3 characters, “YMJ BTW QIN XLW JJS FSI GQZ J”. Now any interceptor of the message cannot use word length as a clue to the message. DECODING To decode a message encrypted with an additive key, we simply add the inverse of the original key. If a is encrypted to F with a key of 5, we would have to continue around the circle another 21 spaces to get back to the letter a. Thus, 21 is the inverse of 5. (26 - the encoding key = the decoding key.) So we can either go backwards 5, or go forward 21 to get back to the un-encoded letter. An encrypted W has a value of 23. 23 + 21 = 44. 44 mod 26 = 18. The 18th letter is r. Another way to find 44 mod 26, by the way, is to subtract 26 from 44 (44 - 26 = 18). If the result is not

less than 26, do it again. To find 75 mod 26, for example, 75 -26 = 49 which is still too big. 49 –26 = 13. The 13th letter is m. BREAKING THE CODE What if we find a message, but don’t know the key? A little bit of statistics helps here. Table 1, at the bottom of this page shows the relative frequencies of letters in the English language. The letter e is by far the most common. In the encoded message above, the letter J appears 4 times, twice as much as anything else, so it’s a good bet that J is used for e. Noticing that there are five spaces between e and j suggests the original key is five. We would then decipher the message with a key of 21 (the inverse of 5) and see if it makes any sense. If not, then we go to the next most common letter. If we guess that J were used for t, then the original key would have been 15, so we would decipher with a key of 26 -15 = 11. Table 1: Relative Frequencies of Letters Letter

Freq

Letter

Freq

Letter

Freq

Letter

Freq

e

12.7%

h

6.1%

w

2.3%

k

.8%

t

9.1%

r

6.0%

f

2.2%

j

.2%

a

8.2%

d

4.3%

g

2.0%

x

.1%

o

7.5%

l

4.0%

y

1.9%

q

.1%

i

6.9%

c

2.8%

p

1.9%

z

.1%

n

6.7%

u

2.7%

b

1.5%

s

6.3%

m

2.4%

v

.9%

You try it! Additive Encryption: Enter your name in the top row, put each letter’s value in the second row, add 15 to each number in the third row, find out what the third row would be mod 26 to fill in the fourth row, and write the corresponding letter in the last row. Plain Text Value + 15 mod 26 Cipher Text

Additive Decryption: This message was encrypted with a key of 12. Decode it. Cipher Text Value Add inverse mod 26 Plain Text

E

B

D

U

Z

S

U

E

Z

U

O

Q

Additive Decryption: You intercept this message from the enemy and think it uses an additive cipher. Cipher Text Value Add inverse mod 26

S

K

K

Z

S

K

O

T

Z

N

K

N

G

R

R

Plain Text a 1

b 2

c 3

d 4

e 5

f 6

g 7

h 8

i 9

j k l m n o p q 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 Most frequent letters: e, t, a, o, I, n, s, h, r, d, l, c, u, m, w, f, g, y, p, b, v, k, j, x, q, z

r 1 8

s 1 9

t 2 0

u 2 1

v 2 2

w 2 3

x 2 4

y 2 5

z 2 6