LAB 4: CRYPTOGRAPHY AND MATRIX MULTIPLICATIONS

Mathematics:

Cryptography is a study of algorithms for encoding and decoding of messages. This project exploits the Hill polygraphic system of cryptography, in which the plain uncoded text is divided into sets of n letters, each of which is replaced by a set of n coded letters, called ciphers. Encoding and decoding of plaintext messages and ciphertext messages are performed with the use of matrix multiplications. When n = 2, the polygraphic system is called Hill 2-ciphers.

Here we assign a number to each capital alphabet letter on a base of 26 numbers:

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	0

We will be transmitting the following message (quotation by R. Kennedy):

"One-fifth of the people are against everything all the time."

Deleting spaces and all punctuation signs and writing the text into capital letters, we convert the message to the form:

O N E F I F T H O F T H E P E O P L E A R E A G A I N S T E V E R Y T H I N G A L L T H E T I M E

Dividing the plaintext into groups of n = 2 letters, we obtain a sequence of plaintext pairs:

O

E

I

T

O

T

E

E

P

E

R

A

A

N

T

V

R

T

I

G

L

T

E

I

E

N

F

F

H

F

H

P

O

L

A

E

G

I

S

E

E

Y

H

N

A

L

H

T

M

Z

Using the coding table, we convert the plaintext pairs into ciphertext pairs and obtain the final sequence for encoding:

15 5 9 20 15 20 5 5 16 5 18 1 1 14 20 22 18 20 9 7 12 20 5 9 5

14 6 6 8 6 8 16 15 12 1 5 7 9 19 5 5 25 8 14 1 12 8 20 13 0

Now, we use the encoding 2-by-2 matrix A: A = [1, 3; 2, 1] to transform the ciphertext pairs to new ciphertext pairs:

5 23 1 18 7 18 1 24 0 8 7 22 2 19 9 11 15 18 25 10 22 18 13 22 5

18 16 24 22 10 22 0 25 18 11 15 9 11 21 19 23 9 22 6 15 10 22 4 5 10

Using the coding table, we convert the ciphertext pairs back to the plaintext pairs and concatenate all letters together:

E R W P A X R V G J R V A Z X Y Z R H K G O V I B K S U I S K W O I R V Y F J O V J R V M D V E E J

This encoding message is suitable for transmission over the Internet. If we would use a simple substitution of letters by numbers according to the coding table, the codes could be broken relatively easy by statistical methods. With the use of the encoding matrix A, the encoding message becomes not so easy for decoding. The encoding matrix A must be carefully hidden from any potential codebreaker. If the encoding matrix A is known, one can compute the inverse decoding matrix A^-1, and apply the same algorithm in the inverse order to decode the message back to the form:

O N E F I F T H O F T H E P E O P L E A R E A G A I N S T E V E R Y T H I N G A L L T H E T I M E Z

Objectives:

· develop MATLAB functions converting a plaintext message into ciphertext pairs and back

· develop MATLAB functions encoding and decoding the message with the use of matrices A and A^-1

· understand constraints on the encoding matrix A and modular arithmetic operations

· exploit the Hill encryption algorithm for encoding and decoding of various messages

MATLAB functions converting a plaintext message into ciphertext pairs and back

Denote S as a string input, that contains only capital alphabet letters and spaces.

Denote V as a 2-by-M matrix of characters after breaking S into pairs of characters, where the string S has 2*M letters. If the text has an odd number of letters, fill out the last pair by an arbitrary "dummy" letter such as "Z".

Denote P as a 2-by-M matrix of integers after converting characters of V into numbers according to the coding table.

Steps in writing the MATLAB functions:

1. Define the MATLAB function "Plain2Cipher" with the input parameter [S] and the output parameter [P].
2. Compute the matrix V from S by breaking the string S into pairs of characters.
3. Compute the matrix P from V by using the coding table. Use "switch" or "if, elseif, end" constructions.
4. Define the MATLAB function "Cipher2Plain" with the input parameter [P] and the output parameter [S].
5. Compute the matrix V from P by using the coding table. Use "switch" or ""if, elseif, end" constructions.
6. Compute the matrix S from V by concataneting pairs of characters into one string.

MATLAB functions encoding and decoding the message with the use of matrices A and A^-1

Define the encoding 2-by-2 matrix A with integer entries:

A = (mod 26),

where (mod 26) indicates that any entry of the matrix A must be an integer between 0 and 25.

In the encoding algorithm, each pair p_j of ciphertext (numbers between 0 and 25) is transformed by multiplication of the encoding matrix A. The new vector q_j = A*p_j may have integer values beyond the limits of 0 and 25. Replace any integer beyond the limits by remainder of its division by 26. The remainder of division of any integer by 26 is an integer number between 0 and 25.

Define the inverse decoding matrix A^-1 with integer values:

A^-1 = (ad-bc)^-1 (mod 26),

where (ad-bc)^-1 is the reciprocal of the number (ad-bc) or its remainder after division by 26. The reciprocal numbers do not exist for all integer numbers between 0 and 25, they only exist for numbers below:

a	1	3	5	7	9	11	15	17	19	21	23	25
a^-1	1	9	21	15	3	19	7	23	11	5	17	25

For any integer number a, the reciprocal number a^-1 satisfies the identity: a^-1*a = 1 (mod 26), i.e. a^-1*a equals to any integer that has remainder one of its division by 26. The table shows that the number a must not be divisible by 2 and 13 in order the reciprocal number a^-1 to exist. The encoding matrix A must satisfy the condition that det A = (ad-bc) has a reciprocal number. In this case, the matrix A is invertible, i.e. there exists a matrix B = A^-1 such that A*B = B*A = 1 (mod 26).

In the decoding algorithm, each pair q_j of ciphertext (numbers between 0 and 25) is transformed by multiplication of the decoding matrix A^-1. If the new vector p_j = A^-1*q_j has integer values beyond the limits of 0 and 25, they are replaced by remainders of their division by 26.

Steps in writing the MATLAB functions:

1. Define the MATLAB function "Encode" with the input parameters [P,A] and the output parameter [Q].
2. Compute the matrix of products of each pair of ciphertext by the encoding matrix: Q = A*P
3. Replace each value of Q beyond the limits of 0 and 25 by its remainder of division by 26.
4. Define the MATLAB function "InverseModular" with the input parameters [A] and the output parameter [B].
5. Check the condition that the detA has a reciprocal number. Return empty matrix, if the condition is not satisfied. Compute the inverse matrix B = A^-1 if the condition is satisfied.
6. Replace each value of B beyond the limits of 0 and 25 by its remainder of division by 26.
7. Define the MATLAB function "Decode" with the input parameters [P,B] and the output parameter [Q].
8. Compute the matrix of products of each pair of ciphertext by the decoding matrix: Q = B*P
9. Replace each value of Q beyond the limits of 0 and 25 by its remainder of division by 26.

Exploiting the MATLAB functions:

1. Define S according to the text above. Use only capital letters for the plaintext letters.
2. Obtain the ciphertext P from the plaintext S.
3. Choose the encoding matrix A. Compute the inverse decoding matrix B, if it exists.
4. Encode the ciphertext P into the ciphertext Q with the encoding matrix A
5. Obtain the encoded plaintext SS from the encoded ciphertext Q. The text is suitable for encrypted transmission.
6. Reversing steps 2-5, decode the encoded plaintext into the original plaintext. You should find the same string S as in step 1, but S consists now of capital letters only.

QUIZ:

1. Encode the message "DARK NIGHT" with the encoding matrices:

(a) , (b)

2. Determine which of the following matrices is invertible modulo 26:

(a) , (b) , (c) , (d) , (e) , (f)

3. Decode the message "SAKNOXAOJX", provided the encoding matrix is