## 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$.