Base 26 conversions

Section A.1 Base 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.

Example A.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.

Example A.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.

Example A.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.