Section 7.1 Symmetric Ciphers
Objectives
- Study Binary
- Arithmetic with Bits
- Key Streams
- Feistel
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:
Example 7.1.2. Writing a Number in Base 10.
Example 7.1.3. Another Number in Base 10.
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:
Example 7.1.5. Converting a Base 2 Number to Base 10.
Example 7.1.6. Converting Another Base 2 Number to Base 10.
Example 7.1.7. Converting Base 10 to Base 2.
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.
- \(\displaystyle 712-512=216\)
- \(\displaystyle 216-128=88\)
- \(\displaystyle 88-64=24\)
- \(\displaystyle 24-16=8\)
- \(\displaystyle 8-8=0\)
(c)
Now putting together the powers of 2 we get:
Example 7.1.8. Converting Base 10 to Base 2 Example 2.
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.
- \(\displaystyle 712-256=141\)
- \(\displaystyle 141-128=13\)
- \(\displaystyle 13-8=5\)
- \(\displaystyle 5-4=1\)
- \(\displaystyle 1-1=0\)
(c)
Now putting together the powers of 2 we get:
Checkpoint 7.1.9.
Convert \(n=(1001101)_2\) into base 10.
\(n=77\)
Checkpoint 7.1.10.
Convert \(n=(110110)_2\) into base 10.
\(n=54\)
Checkpoint 7.1.11.
Convert \(197\) into base 2.
\(n=(11000101)_2\)
Checkpoint 7.1.12.
Convert \(342\) into base 2.
\(n=(101010110)_2\)
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.
\(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.
Checkpoint 7.1.15.
What number represents “Y” in ASCII? What is its binary representation?
Be sure to pay close attention to the way we read off “G” in above.
\(n=89=(1011001)_2\)
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{.}\)
Checkpoint 7.1.16.
What number represents “@” in ASCII? What is its binary representation?
Checkpoint 7.1.17.
What number represents “\(\}\)” in ASCII? What is its binary representation?
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:
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.
Checkpoint 7.1.19.
Convert “T” and “4” to bits and add them together using the bitwise addition (\(\oplus\)) operation.
Look back at how we added “A” and “r” up above.
\(T\oplus 4\equiv (101 0100)_2\oplus(011 0100)_2=(110 0000)_2\)
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
Checkpoint 7.1.20.
Convert “N” and “c” to bits and add them together using the bitwise addition (\(\oplus\)) operation.
Checkpoint 7.1.21.
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
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.
\(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
The general algorithm we will follow is outlined below.
- Convert your message to bits.
- Split the bits into two halves, left and right.
- 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*}
- 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.
- Finally, put the two halves back together.
Example 7.1.26. Two Round Feistel Example: Encipher “hi”.
(a)
Convert “hi” to bits:
(b)
Expand this by adding two bits to the front of this to make it 16 bits long (a multiple of 8):
(c)
Split this into two messages of length 8:
(d)
Split \(M_0=00110100\) into a left and right piece:
Now we are ready to use our keys.
(e)
First Round:
(f)
Next round:
(g)
Final round:
And so the enciphered version of \(M_0\) is
(h)
Repeat for each block of bits
Checkpoint 7.1.27.
Follow the steps above to encipher the second half of the message
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\)
Checkpoint 7.1.28.
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.
\(C_2=0110 0100\)
Checkpoint 7.1.29.
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{.}\)
\(M_0=00110100\)
Checkpoint 7.1.30.
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{.}\)
\(M_1=01101001\)
Checkpoint 7.1.31.
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{.}\)
\(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?