Skip to main content

Section 7.1 Symmetric Ciphers

Subsection 7.1.1 Binary

Some stuff about binary

Definition 7.1.1.

In base 10 numbers are expressed in terms of powers of 10 using the digits 0 through 9. That is if for each \(i\) \(d_i\) is a digit from 0 to 9, we understand \(d_4d_3d_2d_1d_0\) to mean:

\begin{equation*} d_4d_3d_2d_1d_0 = d_4\cdot 10^4+d_3\cdot 10^3+d_2\cdot 10^2+d_1\cdot 10^1+d_0\cdot 10^0. \end{equation*}
\begin{align*} 72381 \amp = 70000+2000+300+80+1\\ \amp =7\cdot 10000+2\cdot 1000+3\cdot 100+8\cdot 10+1\cdot 1\\ \amp =7\cdot 10^4+2\cdot 10^3+3\cdot 10^2+8\cdot 10^1+1\cdot 10^0 \end{align*}
\begin{align*} 3.145 \amp = 3+1/10+4/100+5/1000\\ \amp =3\cdot 1+1\cdot 1/10+4\cdot 1/100+5\cdot 1/1000\\ \amp =3\cdot 10^0+1\cdot 10^{-1}+4\cdot 10^{-2}+5\cdot 10^{-3} \end{align*}
Definition 7.1.4.

In base 2 or binary numbers are expressed in terms of powers of 2 using the digits 0 and 1. That is if for each \(i\) \(b_i\) is either 0 or 1, we understand \(b_4b_3b_2b_1b_0\) to mean:

\begin{equation*} b_4b_3b_2b_1b_0 = b_4\cdot 2^4+b_3\cdot 2^3+b_2\cdot 2^2+b_1\cdot 2^1+b_0\cdot 2^0. \end{equation*}
\begin{align*} (1001001)_2\amp = 1\cdot 2^6+0\cdot 2^5+0\cdot 2^4+1\cdot 2^3+0\cdot 2^2+0\cdot 2^1+1\cdot 2^0\\ \amp = 1\cdot 64+1\cdot 8+1\cdot 1\\ \amp = 64+ 8+ 1\\ \amp = 73 \end{align*}
\begin{align*} (0101011)_2\amp = 0\cdot 2^6+1\cdot 2^5+0\cdot 2^4+1\cdot 2^3+0\cdot 2^2+1\cdot 2^1+1\cdot 2^0\\ \amp = 1\cdot 32+1\cdot 8+1\cdot 2+1\cdot 1\\ \amp = 32+ 8+ 2+1\\ \amp = 43 \end{align*}

We can convert any number like \(n=728\) from base 10 to base 2 in the following way.

(a)

Find the largest power of 2 less than \(n=728\text{;}\) in this case it is \(512=2^9\text{.}\)

(b)

Subtract this number from \(n=728\) to get \(n=728-512=216\text{.}\) Now repeat previous step until you have zero left.

  1. \(\displaystyle 712-512=216\)
  2. \(\displaystyle 216-128=88\)
  3. \(\displaystyle 88-64=24\)
  4. \(\displaystyle 24-16=8\)
  5. \(\displaystyle 8-8=0\)
(c)

Now putting together the powers of 2 we get:

\begin{align*} 712 \amp = 512+128+64+16+8\\ \amp = 2^9+2^7+2^6+2^4+2^3\\ \amp = 2^9+0\cdot 2^8+2^7+2^6+0\cdot 2^5+2^4+2^3+0\cdot 2^2+0\cdot 2^1+0\cdot 2^0\\ \amp = (1011011000)_2 \end{align*}

We can convert any number like \(n=397\) from base 10 to base 2 in the following way.

(a)

Find the largest power of 2 less than \(n=397\text{;}\) in this case it is \(256=2^8\text{.}\)

(b)

Subtract this number from \(n=387\) to get \(n=397-256=141\text{.}\) Now repeat the previous step until you have zero left.

  1. \(\displaystyle 712-256=141\)
  2. \(\displaystyle 141-128=13\)
  3. \(\displaystyle 13-8=5\)
  4. \(\displaystyle 5-4=1\)
  5. \(\displaystyle 1-1=0\)
(c)

Now putting together the powers of 2 we get:

\begin{align*} 712 \amp = 256+128+8+4+1\\ \amp = 2^8+2^7+2^3+2^2+2^1\\ \amp = 2^8+2^7+0\cdot 2^6+0\cdot 2^5+0\cdot 2^4+2^3+2^2+0\cdot 2^1+2^0\\ \amp = (110001101)_2 \end{align*}

Convert \(n=(1001101)_2\) into base 10.

Answer

\(n=77\)

Convert \(n=(110110)_2\) into base 10.

Answer

\(n=54\)

Convert \(197\) into base 2.

Answer

\(n=(11000101)_2\)

Convert \(342\) into base 2.

Answer

\(n=(101010110)_2\)

Figure 7.1.13. Base Converter Cell

Subsection 7.1.2 Bitwise Addition

Modern computers and programing languages use Unicode or ASCII Code to convert characters to collections of bits (0's and 1's) instead of the International Telegraph Code (Figure 5.2.5) we studied previously. We can read the ASCII codes on Table 7.1.14. The bits for a character are listed as \((b_7b_6b_5b_4b_3b_2b_1)\) with the first three bits along the top and the next four on the side. If we look up the character \(G\text{,}\) the top of the column gives (100) and on the left we read (0111), so that \(G\equiv(1000111)\text{.}\) You should also see that at the top of the column is 64 and on the left is 7, so we can also write \(G\equiv 64+7=71\) which is the value of \((1000111)\) in base 2.

Table 7.1.14. ASCII Code Chart
\(b_7\, b_6\, b_5 \rightarrow \) 000 001 010 011 100 101 110 111
\(\downarrow b_4\, b_3\, b_2\, b_1\) 0 16 32 48 64 80 96 112
0000 0 NUL DLE 0 @ P ` p
0001 1 SOH DC1 ! 1 A Q a q
0010 2 STX DC2 " 2 B R b r
0011 3 ETX DC3 # 3 C S c s
0100 4 EOT DC4 $ 4 D T d t
0101 5 ENQ NAK % 5 E U e u
0110 6 ACK SYN & 6 F V f v
0111 7 BEL ETB ' 7 G W g w
1000 8 BS CAN ( 8 H X h x
1001 9 TAB EOM ) 9 I Y i y
1010 10 LF SUB * : J Z j z
1011 11 VT ESC + ; K [ k \(\{\)
1100 12 FF FS , < L \(\backslash\) l |
1101 13 CR GS - = M ] m \(\}\)
1110 14 SO RS . > N \(\wedge\) n \(\sim\)
1111 15 SI US / ? O \(\_\) o DEL

If you look in the ASCII table you will notice that the first 32 entries are different from the others. These are called control characters. Rather than printing something out they tell the computer to do something. For example LF stands for line feed and it tells the computer to go back to the beginning of the line. And CR stands for carriage return and tells the computer to go down one line.

What number represents “Y” in ASCII? What is its binary representation?

Hint

Be sure to pay close attention to the way we read off “G” in above.

Answer

\(n=89=(1011001)_2\)

Solution

Looking at the top of the column with the “Y” we see 80 and it is in row 9, so \(n=89\text{.}\) Also at the top of the column are the bits (101) and the row is labeled (1001) so in binary we get \((1011001)_2\text{.}\)

What number represents “@” in ASCII? What is its binary representation?

Hint

Be sure to pay close attention to the way we read off “G” in above.

Answer

\(n=64=(1000000)_2\)

What number represents “\(\}\)” in ASCII? What is its binary representation?

Hint

Be sure to pay close attention to the way we read off “G” in above.

Answer

\(n=125=(1111101)_2\)

Definition 7.1.18.

A bit is a single 1 or 0 and when we add bitwise we follow the following rules:

  • \(\displaystyle 0\oplus 0 = 0\)
  • \(\displaystyle 0\oplus 1 = 1\)
  • \(\displaystyle 1\oplus 0 = 1\)
  • \(\displaystyle 1\oplus 1 = 0\)

This is essentially the same as using XOR (see Definition 5.2.12).

So given \(A\equiv(1000001)\) and \(r\equiv(1110010)\) we calculate \(A\oplus r\) as:

\begin{align*} A\oplus r \amp \equiv (1000001) \oplus (111001)\\ \amp = (0110011)\\ \amp \equiv 3 \end{align*}

Where we added the 0's and 1's term by term. This is essentially the same as the \(\oplus/XOR\) operation in Section 5.2.

Convert “T” and “4” to bits and add them together using the bitwise addition (\(\oplus\)) operation.

Hint

Look back at how we added “A” and “r” up above.

Answer

\(T\oplus 4\equiv (101 0100)_2\oplus(011 0100)_2=(110 0000)_2\)

Solution

Looking at the top and sides of the table we get \(T\equiv 84 =(1010100)_2\) and \(4\equiv 52=(011 0100)_2\text{.}\) Then we add these together term by term using Definition 7.1.18 we get

\begin{equation*} T\oplus 4\equiv (101 0100)_2\oplus(011 0100)_2=(110 0000)_2. \end{equation*}

Convert “N” and “c” to bits and add them together using the bitwise addition (\(\oplus\)) operation.

Hint

Look back at how we added “A” and “r” up above.

Answer

\(N\oplus c\equiv (100 1110)\oplus(110 0011)_2=(010 1101)_2\)

Convert “$” and “/” to bits and add them together using the bitwise addition (\(\oplus\)) operation.

Hint

Look back at how we added “A” and “r” up above.

Answer

\($\oplus /\equiv (010 0100)\oplus(010 1111)_2=(000 1011)_2\)

Figure 7.1.22. Bit Addition Cell

Subsection 7.1.3 Key Streams

Definition 7.1.23.

A stream cipher is a cipher that uses a sequence (or stream) of different keys in order to encipher successive pieces of plaintext. Examples of this include Vigenère's autokey cipher (Subsection 3.3.2) and Vernam's one-time pad cipher (Subsubsection 5.2.2.2).

One way to generate a stream of keys is to convert an initial key to bits and then use successive pieces of the result. For example suppose our random key is \(key=19FA9ED5\text{.}\) In bits this is

\begin{equation*} k=1100\ 0111\ 1001\ 1000\ 1101\ 0000\ 0111\ 1001\ 1000\ 1011\ 0001\ 0011\ 0101 \end{equation*}

from which we might use four bits at a time. We will do this by taking the first four bits, then shifting over one bit and taking the next four, and the repeating that pattern. This creates what is called a key schedule like below.

Table 7.1.24. Partial Key Schedule based on \(key=19FA9ED5\)
\(key\ 0\ =\ 1100 \) \(key\ 1\ =\ 1000 \) \(key\ 2\ =\ 0001 \)
\(key\ 3\ =\ 0011 \) \(key\ 4\ =\ 0111 \) \(key\ 5\ =\ 1111 \)
\(key\ 6\ =\ 1110 \) \(key\ 7\ =\ 1100 \) \(key\ 8\ =\ 1001 \)
\(key\ 9\ =\ 0011 \) \(key\ 10\ =\ 0110 \) \(key\ 11\ =\ 1100 \)
\(key\ 12\ =\ 1000 \) \(key\ 13\ =\ 0001 \) \(key\ 14\ =\ 0011 \)
\(key\ 15\ =\ 0110 \) \(key\ 16\ =\ 1101 \) \(key\ 17\ =\ 1010 \)

Comprehension Check:

  • How did we get \(key\ 0\) and \(key\ 1\) from \(k\text{?}\)
  • How about \(key\ 2\) and \(key\ 3\) from \(k\text{?}\)
  • What is the general pattern for generating keys from
    \begin{equation*} k=1100\ 0111\ 1001\ 1000\ 1101\ 0000\ 0111\ 1001\ 1000\ 1011\ 0001\ 0011\ 0101? \end{equation*}
  • Since there are 52 bits in the sequence above, what is the maximum number of keys in the key schedule?
  • Can you explain why not all the keys are unique in this example?

Now that we have a key schedule we can look at a much more modern version of a stream cipher.

Subsection 7.1.4 Feistel Cipher

A Feistel cipher is a cipher that enciphers the plaintext in rounds by splitting the information up like a deck of cards and shuffling it around. Part of this shuffling process involves a function called \(f\) which is used to combine half of the text being enciphered with a key from the key schedule. For our example here we will just add the bits together, that is

\begin{equation*} f((1101),(0100))=(1101)\oplus(0100)=(1001). \end{equation*}

The general algorithm we will follow is outlined below.

  1. Convert your message to bits.
  2. Split the bits into two halves, left and right.
  3. In reach round, except the last, move the right half to the left and make the new right half equal to
    \begin{equation*} R_{i+1}=L_i\oplus f(R_i,k_i)=L_i\oplus R_i \oplus k_i. \end{equation*}
  4. In the last round just swap the left and right hand sides, this ensures that deciphering will work exactly like enciphering but with the key schedule reversed.
  5. Finally, put the two halves back together.
This figure gives an outline of the workings of a Feistel style cipher.
Figure 7.1.25. Outline of a Feistel Cipher
(a)

Convert “hi” to bits:

\begin{equation*} 1101000 1101001 \end{equation*}
(b)

Expand this by adding two bits to the front of this to make it 16 bits long (a multiple of 8):

\begin{equation*} 0011010001101001 \end{equation*}
(c)

Split this into two messages of length 8:

\begin{equation*} M_0=00110100\ \text{and}\ M_1=01101001 \end{equation*}
(d)

Split \(M_0=00110100\) into a left and right piece:

\begin{equation*} L_0=0011,\ R_0=0100 \end{equation*}

Now we are ready to use our keys.

(e)

First Round:

\begin{align*} L_1\amp=R_0=0100\\ R_1\amp=L_0\oplus f(R_0,k_0)\\ \amp=L_0\oplus R_0 \oplus k_0\\ \amp=0011\oplus 0100 \oplus 1100\\ \amp=1011 \end{align*}
(f)

Next round:

\begin{align*} L_2\amp =R_1=1011\\ R_2\amp=L_1\oplus f(R_1,k_1)\\ \amp=L_1\oplus R_1 \oplus k_1\\ \amp=0100\oplus 1011 \oplus 1000\\ \amp=0111 \end{align*}
(g)

Final round:

\begin{align*} L_3\amp =R_2=0111\\ R_3\amp =L_2=1011 \end{align*}

And so the enciphered version of \(M_0\) is

\begin{equation*} C_0=L_3\, R_3=0111 1011 \end{equation*}
(h)

Repeat for each block of bits

Follow the steps above to encipher the second half of the message

\begin{equation*} M_1=01101001. \end{equation*}

For the keys use \(key\ 2=0001\) and \(key\ 3=0011\) from above.

(a)

Split \(M_1\) into a left and right piece.

Answer

\(L_0=0110\) and \(R_0=1001\)

(b)

Swap the halves and add the round key, \(key\ 2\)

Answer

\(L_1=1001\) and \(R_1=1110\)

(c)

Swap the halves and add the round key, \(key\ 3\)

Answer

\(L_2=1110\) and \(R_2=0100\)

(d)

Final round, just swap the sides and paste them together.

Answer

\(L_3=0100\) and \(R_2=1110\) so that \(C_1=0100 1110\)

Suppose there was a third part to our message \(M_2=1110 1101\text{,}\) use \(key\ 4=0111\) and \(key\ 5=1111\) from above and encipher this.

Answer

\(C_2=0110 0100\)

Follow the exact same algorithm as above with \(C_0=0111 1011\text{,}\) using \(key\ 1=1000\) and then \(key\ 0=1100\text{,}\) if you are careful you will end up with \(M_0=00110100\text{.}\)

Answer

\(M_0=00110100\)

Follow the exact same algorithm as above with \(C_1=0100 1110\text{,}\) using \(key\ 3=0011\) and then \(key\ 2=0001\text{,}\) if you are careful you will end up with \(M_1=01101001\text{.}\)

Answer

\(M_1=01101001\)

Follow the exact same algorithm as above with \(C_2=0110 0100\text{,}\) using \(key\ 5=1111\) and then \(key\ 4=0111\text{,}\) if you are careful you will end up with \(M_2=1110 1101\text{.}\)

Answer

\(M_2=1110 1101\)

The Sage Cell below can carry out a single round of the basic Feistel cipher described above. You should still strive to understand how the cipher works, but this should help with a little of the grunt work. When you need to just swap the left and right sides use the key 0000; why does this work?

Figure 7.1.32. Single Feistel Round Cell