AATA Private Key Cryptography

Section 7.1 Private Key Cryptography

In single or private key cryptosystems the same key is used for both encrypting and decrypting messages. To encrypt a plaintext message, we apply to the message some function which is kept secret, say

f .

This function will yield an encrypted message. Given the encrypted form of the message, we can recover the original message by applying the inverse transformation

f^{- 1} .

The transformation

f

must be relatively easy to compute, as must

f^{- 1};

however,

f

must be extremely difficult to guess from available examples of coded messages.

🔗

Example 7.1.

🔗

One of the first and most famous private key cryptosystems was the shift code used by Julius Caesar. We first digitize the alphabet by letting

A = 00, B = 01, \dots, Z = 25 .

The encoding function will be

f (p) = p + 3 mod 26;

🔗

that is,

A \mapsto D, B \mapsto E, \dots, Z \mapsto C .

The decoding function is then

f^{- 1} (p) = p - 3 mod 26 = p + 23 mod 26 .

🔗

Suppose we receive the encoded message DOJHEUD. To decode this message, we first digitize it:

3, 14, 9, 7, 4, 20, 3 .

🔗

Next we apply the inverse transformation to get

0, 11, 6, 4, 1, 17, 0,

🔗

or ALGEBRA. Notice here that there is nothing special about either of the numbers

3

26 .

We could have used a larger alphabet or a different shift.

🔗

Cryptanalysis is concerned with deciphering a received or intercepted message. Methods from probability and statistics are great aids in deciphering an intercepted message; for example, the frequency analysis of the characters appearing in the intercepted message often makes its decryption possible.

🔗

Example 7.2.

🔗

Suppose we receive a message that we know was encrypted by using a shift transformation on single letters of the

26

-letter alphabet. To find out exactly what the shift transformation was, we must compute

b

in the equation

f (p) = p + b mod 26 .

We can do this using frequency analysis. The letter

E = 04

is the most commonly occurring letter in the English language. Suppose that

S = 18

is the most commonly occurring letter in the ciphertext. Then we have good reason to suspect that

18 = 4 + b mod 26,

b = 14 .

Therefore, the most likely encrypting function is

f (p) = p + 14 mod 26 .

🔗

The corresponding decrypting function is

f^{- 1} (p) = p + 12 mod 26 .

🔗

It is now easy to determine whether or not our guess is correct.

🔗

Simple shift codes are examples of monoalphabetic cryptosystems. In these ciphers a character in the enciphered message represents exactly one character in the original message. Such cryptosystems are not very sophisticated and are quite easy to break. In fact, in a simple shift as described in Example 7.1, there are only

26

possible keys. It would be quite easy to try them all rather than to use frequency analysis.

🔗

Let us investigate a slightly more sophisticated cryptosystem. Suppose that the encoding function is given by

f (p) = a p + b mod 26 .

🔗

We first need to find out when a decoding function

f^{- 1}

exists. Such a decoding function exists when we can solve the equation

c = a p + b mod 26

🔗

for

p .

By Proposition 3.4, this is possible exactly when

a

has an inverse or, equivalently, when

gcd (a, 26) = 1 .

In this case

f^{- 1} (p) = a^{- 1} p - a^{- 1} b mod 26 .

🔗

Such a cryptosystem is called an affine cryptosystem.

🔗

Example 7.3.

🔗

Let us consider the affine cryptosystem

f (p) = a p + b mod 26 .

For this cryptosystem to work we must choose an

a \in Z_{26}

that is invertible. This is only possible if

gcd (a, 26) = 1 .

Recognizing this fact, we will let

a = 5

since

gcd (5, 26) = 1 .

It is easy to see that

a^{- 1} = 21 .

Therefore, we can take our encryption function to be

f (p) = 5 p + 3 mod 26 .

Thus, ALGEBRA is encoded as

3, 6, 7, 23, 8, 10, 3,

or DGHXIKD. The decryption function will be

f^{- 1} (p) = 21 p - 21 \cdot 3 mod 26 = 21 p + 15 mod 26 .

🔗

A cryptosystem would be more secure if a ciphertext letter could represent more than one plaintext letter. To give an example of this type of cryptosystem, called a polyalphabetic cryptosystem, we will generalize affine codes by using matrices. The idea works roughly the same as before; however, instead of encrypting one letter at a time we will encrypt pairs of letters. We can store a pair of letters

p_{1}

and

p_{2}

in a vector

p = (\begin{matrix} p_{1} \\ p_{2} \end{matrix}) .

🔗

Let

A

be a

2 \times 2

invertible matrix with entries in

Z_{26} .

We can define an encoding function by

f (p) = A p + b,

🔗

where

b

is a fixed column vector and matrix operations are performed in

Z_{26} .

The decoding function must be

f^{- 1} (p) = A^{- 1} p - A^{- 1} b .

🔗

Example 7.4.

🔗

Suppose that we wish to encode the word HELP. The corresponding digit string is

7, 4, 11, 15 .

A = (\begin{matrix} 3 & 5 \\ 1 & 2 \end{matrix}),

🔗

then

A^{- 1} = (\begin{matrix} 2 & 21 \\ 25 & 3 \end{matrix}) .

🔗

b = (2, 2)^{t},

then our message is encrypted as RRGR. The encrypted letter R represents more than one plaintext letter.

🔗

Frequency analysis can still be performed on a polyalphabetic cryptosystem, because we have a good understanding of how pairs of letters appear in the English language. The pair th appears quite often; the pair qz never appears. To avoid decryption by a third party, we must use a larger matrix than the one we used in Example 7.4.

Prev Top Next