## SectionA.1Base 26 conversions

We will use base 26 conversions as a way to convert blocks of letters to a number to use with some of our encryption algorithms. It will also provide us with an example of a block cipher. To think about what base 26 means, we start by remembering that normal decimal representation is base 10. That is, $12345=1\times 10^4+2\times 10^3+3\times 10^2+4\times 10+5\times 10^0\text{.}$ Base 26 is similar with 10 replaced by 26. Since we need 26 “digits” we'll use A-Z instead of 0-9. For example, BCDEF=$1\times 26^4+2\times 26^3+3\times 26^2+4\times 26^1+5\times 26^0\text{.}$ Note that A=0 so ABCDEF=BCDEF just like 012=12.

###### ExampleA.1.1.

Convert the decimal 12345 to base 26.

Method 1: Find the highest power of 26 that is less than 12345. $26^2=676$ and $26^3=17576$ so $26^2$ is the highest power of 26 that is less than 12345. Next, divide 12345 by $676=26^2$ to find a quotient and remainder.

\begin{equation*} 12345=26^2(18)+177. \end{equation*}

Now repeat the process for 177. This time 26 is the largest power of 26 that is less than 177 and

\begin{equation*} 177=26(6)+21\text{.} \end{equation*}
\begin{equation*} 12345=26^2 (18) + 26(6) +21\text{.} \end{equation*}

So the number 12345 in decimal can be written as 18,6,21=SGV in base 26.

Method 2: Repeatedly apply the division algorithm to quotients when dividing by 26 until the quotient $\leq 26\text{.}$

\begin{align*} 12345\amp=26(474)+21\\ 474\amp=26(18)+6 \end{align*}

Rewrite using powers of 26 in reverse.

\begin{align*} 474\amp=26(18)+6\\ 12345\amp=26(26(18)+6)+21=26^2(18) + 26(6) +21 \end{align*}

So we again get 18,6,21=SGV in base 26.

We can create a block cipher using a base 26 key. Suppose the key is an $n$ letter word. To encrypt a message with a base 26 block cipher we break the message into blocks of $n$ letters and add the key base 26 to each block.

###### ExampleA.1.2.

Suppose the key word is FUN and the plaintext is DIG. To encrypt the message we want to add FUN+DIG base 26.

 D I G + F U N

$G+N=6+13=19=T$

$I+U=8+20=28=26+2=C$ (the 26 is carried over to the next column)

$D+F+1=3+5+1=9=J$ (the +1 is from the carry in the previous column)

 D+1 I G + F U N J C T

So the ciphertext would be JCT.

To decrypt a message we break the ciphertext into blocks of length $m$ and subtract the keyword mod 26 from each block. In this case we need to be careful about borrowing in base 26.

###### ExampleA.1.3.
Decrypt the message XVL with the keyword FUN
 X V L - F U N

$L-N=11-13$ isn't possible, so we have to borrow from V. Remember its base 26, so we are borrowing a 26. So $11+26-13=24=Y$

Since we borrowed one from the $V\text{,}$ it is reduced to $V-1=U\text{.}$ Now $U -U=0=A\text{.}$

Lastly, $X-F=23-5=18=S\text{.}$

 X V-1 L+26 - F U N S A Y

We have decrypted the message to get the plaintext SAY.