Hill Cipher

I. Consider the following equation where x and y represent two relatively prime integers
23x-26y=1\qquad\left (E\right )
(a) Verify that the ordered pair \left (-9,-8\right ) is a solution of Eq. \left (E\right )
(b) Use part (a) to find a parametric solution of Eq. \left (E\right )
(c) Derive an integer a such that 0\leqslant a \leqslant 25 and 23a\equiv 1\left (\text{mod}\,26\right )

II. We want to encode a two-letter word by using the following procedure
STEP 1 Each letter is replaced by an integer according to the table below

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

0

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

We obtain an ordered pair \left (x_1,x_2\right ) where x_1 corresponds to the first letter of the word and x_2 corresponds to the second letter of the word.
STEP 2 \left (x_1,x_2\right ) is transformed into \left (y_1,y_2\right ) such that
y_1\equiv 11x_1+3x_2\left (\text{mod}\,26\right )\qquad\left (S_1\right )
y_2\equiv 7x_1+4x_2\left (\text{mod}\,26\right ) with 0\leqslant y_1\leqslant 25 and 0\leqslant y_2\leqslant 25
STEP 3 \left (y_1,y_2\right ) is transformed into a two-letter word by using the correspondence table given in STEP 1
Example:
.\;\;\text{STEP 1}\quad\text{STEP 2}\quad\text{ STEP 3}
\text{TE}\Rightarrow \left (19,4\right )\Rightarrow \left (13,19\right )\Rightarrow\text{NT}
plain text                         encoded text

1. Encode the word \text{ST}
2. We want to determine the decoding procedure:
(a) Show that if \left (x_1,x_2\right ) verifies the system of equations  \left (S_1\right ) then it verifies the system of equations
23x_1\equiv 4y_1+23y_2\left (\text{mod}\,26\right )\qquad\left (S_2\right )
23x_2\equiv 19y_1+11y_2\left (\text{mod}\,26\right )
(b) Use part (I) to show that if \left (x_1,x_2\right ) verifies the system of equations \left (S_2\right ) then it verifies the system of equations
x_1\equiv16y_1+y_2\left (\text{mod}\,26\right )\qquad\left (S_3\right )
x_2\equiv 11y_1+5y_2\left (\text{mod}\,26\right )
(c) Show that if \left (x_1,x_2\right ) verifies the system of equations \left (S_3\right ) then it verifies the system of equations \left (S_1\right )
(d) Decode the word YJ
Source: Baccalauréat Général, Série Scientifique, Session Avril 2012, Pondichéry, http://www.ilemaths.net

SOLUTION
I. (a) Verify that the ordered pair \left (-9,-8\right ) is a solution of the equation
23x-26y=1\qquad\left (E\right )
23\left (-9\right )-26\left (-8\right )=-207+208
=1
\left (-9,-8\right ) is a solution of the equation \left (E\right )

(b) Use part (a) to find a parametric solution of the equation \left (E\right )
Consider the system of equations
23x-26y=1
23\left (-9\right )-26\left (-8\right )=1
Multiply the second equation by -1 and add the equations
23x-26y=1
23\left (9\right )-26\left (8\right )=-1
——————————–
23\left (x+9\right )-26\left (y+8\right )=0
23\left (x+9\right )=26\left (y+8\right )\qquad\left (1\right )

23 divides 26\left (y+8\right )
23 divides \left (y+8\right ) because 23 and 26 are relatively prime
y+8= 23k for some integer k
y=23k-8
Substitute the value of y into Eq.\left (1\right )
23\left (x+9\right )=26\left (23k-8+8\right )
Simplify
23\left (x+9\right )=26\left (23k\right )
x+9=26k
x=26k-9
A parametric solution of Eq. \left (E\right ) is
x=26k-9
y=23k-8

(c) Derive an integer a such that 0\leqslant a\leqslant 25 and 23a\equiv 1\left (\text{mod}\,26\right )
If 23a\equiv 1\left (\text{mod}\,26\right ) then there exists an integer q such that
23a=26q+1
Simplify
23a-26q=1
From part (b)
a=26k-9
a=26-9 for k=1
=17
The multiplicative inverse of 23\,\text{modulo}\,26 is 17.

II. 1. Encode the word ST
STEP 1 The plain text ST corresponds to \left (x_1,x_2\right )=\left (18,19\right )
STEP 2 Transform \left (x_1,x_2\right ) into \left (y_1,y_2\right ) by substituting the values of x_1 and x_2 into the system of equations
y_1\equiv 11x_1+3x_2\left (\text{mod}\,26\right )\qquad\left (S_1\right )
y_2\equiv 7x_1+4x_2\left (\text{mod}\,26\right )

y_1\equiv 11\cdot 18+3\cdot 19\left (\text{mod}\,26\right )
Simplify
y_1\equiv 198+57\left (\text{mod}\,26\right )
\equiv 255\left (\text{mod}\,26\right )
\equiv 21\left (\text{mod}\,26\right )\quad 255=9\cdot 26+21
Similarly
y_2\equiv 7\cdot 18+4\cdot 19\left (\text{mod}\,26\right )
Simplify
y_2\equiv 126+76\left (\text{mod}\,26\right )
\equiv 202\left (\text{mod}\,26\right )
\equiv 20\left (\text{mod}\,26\right )\quad 202=7.26+20
\left (y_1,y_2\right )=\left (21,20\right )
STEP 3 From the table \left (21,20\right ) corresponds to the encoded text VU.

2. (a) Show that if \left (x_1,x_2\right ) verifies the system of equations \left (S_1\right ) then it verifies the system of equations
23x_1\equiv 4y_1+23y_2\left (\text{mod}\,26\right )\qquad\left (S_2\right )
23x_2\equiv 19y_1+11y_2\left (\text{mod}\,26\right )

Given that \left (x_1,x_2\right ) verifies the system of equations
y_1\equiv 11x_1+3x_2\left (\text{mod}\,26\right )\qquad\left (S_1\right )
y_2\equiv 7x_1+4x_2\left (\text{mod}\,26\right )
Substitute the value of y_1 and y_2 from \left (S_1\right ) into the right hand sides of \left (S_2\right )
4y_1+23y_2\left (\text{mod}\,26\right )\equiv 4\left (11x_1+3x_2\right )+23\left (7x_1+4x_2\right )\left (\text{mod}\,26\right )
\equiv 44x_1+12x_2+161x_1+92x_2\left (\text{mod}\,26\right )
\equiv 205x_1+104x_2\left (\text{mod}\,26\right )
\equiv 23x_1+0x_2\left (\text{mod}\,26\right )\quad 205=7\cdot 26+23 and 104=4\cdot 26+0
\equiv 23x_1\left (\text{mod}\,26\right )
Similarly
19y_1+11y_2\left (\text{mod}\,26\right )\equiv 19\left (11x_1+3x_2\right )+11\left (7x_1+4x_2\right )\left (\text{mod}\,26\right )
\equiv 209x_1+57x_2+77x_1+44x_2\left (\text{mod}\,26\right )
\equiv 286x_1+101x_2\left (\text{mod}\,26\right )
\equiv 0x_1+23x_2\left (\text{mod}\,26\right )\quad 286=11\cdot 26+0 and 101=3\cdot 26+23
\equiv 23x_2\left (\text{mod}\,26\right )
If \left (x_1,x_2\right ) verifies the system of equations \left (S_1\right ) then it verifies the system of equations \left (S_2\right ).

(b) Use part (I) to show that if \left (x_1,x_2\right ) verifies the system of equations \left (S_2\right ) then it verifies the system of equations
x_1\equiv 16y_1+y_2\left (\text{mod}\,26\right )\qquad\left (S_3\right )
x_2\equiv 11y_1+5y_2\left (\text{mod}\,26\right )

Given that \left (x_1,x_2\right ) verifies the system of equations
23x_1\equiv 4y_1+23y_2\left (\text{mod}\,26\right )\qquad\left (S_2\right )
23x_2\equiv 19y_1+11y_2\left (\text{mod}\,26\right )
Multiply both sides of the system of equations \left (S_2\right ) by 17, the multiplicative inverse of 23\,\text{modulo}\,26
17\cdot 23x_1\equiv 17\left (4y_1+23y_2\right )\left (\text{mod}\,26\right )
1x_1\equiv 68y_1+1y_2\left (\text{mod}\,26\right )
x_1\equiv 16y_1+y_2\left (\text{mod}\,26\right )\quad 68=2\cdot 26+16
Similarly
17\cdot 23x_2\equiv 17\left (19y_1+11y_2\right )\left (\text{mod}\,26\right )
1x_2\equiv 323y_1+187y_2\left (\text{mod}\,26\right )
x_2\equiv 11y_1+5y_2\left (\text{mod}\,26\right )\quad 323=12\cdot 26+11 and 187=7\cdot 26+5
If \left (x_1,x_2\right ) verifies the system of equations \left (S_2\right ) then it verifies the system of equations \left (S_3\right ).

(c) Show that if \left (x_1,x_2\right ) verifies the system of equations \left (S_3\right ) then it verifies the system of equations
y_1\equiv 11x_1+3x_2\left (\text{mod}\,26\right )\qquad \left (S_1\right )
y_2\equiv 7x_1+4x_2\left (\text{mod}\,26\right )

Given that \left (x_1,x_2\right ) verifies the system of equations
x_1\equiv 16y_1+y_2\left (\text{mod}\,26\right )\qquad \left (S_3\right )
x_2\equiv 11y_1+5y_2\left (\text{mod}\,26\right )
Substitute the values of x_1 and x_2 from \left (S_3\right ) into the right hand sides of \left (S_1\right )
11x_1+3x_2\left (\text{mod}\,26\right )\equiv 11\left (16y_1+y_2\right )+3\left (11y_1+5y_2\right )\left (\text{mod}\,26\right )
\equiv 176y_1+11y_2+33y_1+15y_2\left (\text{mod}\,26\right )
\equiv 209y_1+26y_2\left (\text{mod}\,26\right )
\equiv 1y_1+0y_2\left (\text{mod}\,26\right )\quad 209=8\cdot 26+1 and 26=1\cdot 26+0
\equiv y_1\left (\text{mod}\,26\right )
Similarly
7x_1+4x_2\left (\text{mod}\,26\right )\equiv 7\left (16y_1+y_2\right )+4\left (11y_1+5y_2\right )\left (\text{mod}\,26\right )
\equiv 112y_1+7y_2+44y_1+20y_2\left (\text{mod}\,26\right )
\equiv 156y_1+27y_2\left (\text{mod}\,\right )
\equiv 0y_1+1y_2\left (\text{mod}\,\right )\quad 156=6\cdot 26+0 and 27=1\cdot 26+1
\equiv y_2\left (\text{mod}\,26\right )
If \left (x_1,x_2\right ) verifies the system of equations \left (S_3\right ) then it verifies the system of equations \left (S_1\right ).

(d) Decode the word YJ
The encoded text YJ corresponds to \left (y_1,y_2\right )=\left (24,9\right )
Substitute the values of y_1 and y_2 into the system of equations
x_1\equiv 16y_1+y_2\left (\text{mod}\,26\right )\qquad \left (S_3\right )
x_2\equiv 11y_1+5y_2\left (\text{mod}\,26\right )

x_1\equiv 16\cdot 24+9\left (\text{mod}\,26\right )
\equiv 384+9\left (\text{mod}\,26\right )
\equiv 393\left (\text{mod}\,26\right )
\equiv 3\left (\text{mod}\,26\right )\quad 393=15\cdot 26+3
Similarly
x_2\equiv 11\cdot 24+5\cdot 9\left (\text{mod}\,26\right )
\equiv 264+45\left (\text{mod}\,26\right )
\equiv 309\left (\text{mod}\,26\right )
\equiv 23\left (\text{mod}\,26\right )\quad 309=11\cdot 26+23
\left (x_1,x_2\right )=\left (3,23\right )
The plain text is DX.

Answer: Given in solution.

Advertisements

About mvtrinh

Retired high school math teacher.
This entry was posted in Problem solving and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s