CMPUT 329

Lab #3

Treehouse Encryption

(2 weeks)

You may work in PAIRS for this lab.

Your little brother is a member of a "secret club" with his school friends. The club thought it would be really cool to be able to send secret messages to each other, but thought that the simple paper algorithms shown in their favorite mystery novels were a little weak against the energy and creativity (and mystery novel awareness) of pesky siblings and parents. So, they approached you, their own personal computer guru, for advice. They are fortunate enough to be quite well funded, by one of the member's father. So, they have purchase FPGA setups for all the clubhouses, and have commissioned you to create a hardware solution to their problem. You have come up with the Treehouse Encryption Algorithm, which although terribly weak against any serious attack, will surely defeat the individuals interested in the club's secret messages.  (your exact assignment is detailed near the end of this document, here)

Prelab:

0.  Read the the lab assignment, and understand the treehouse.c source code and the description given on this page. The goal is to have a reasonable grasp of how the encryption works, so that it is easier to implement. Look at the block diagram. Think about how you will implement the required components in VHDL.

1.  Write the decryption algorithm in pseudo-code (or a more formal language, if you wish).  Do not be too vague in your code - it should clearly show how an encrypted message can be decrypted (ie the code should imply a hardware design).

Lab:

The Treehouse Encryption Algorithm, implemented in C: treehouse.c

The algorithm takes in a 4-bit quantity and returns an 8-bit quantity. There are several steps in this transformation:

0. Reverse the order of the input bits:
 
Original: B03 B02 B01 B00
New: B10 B11 B12 B13

1. Expand and permute the original bits: 4 new bits are created by XORing pairs of the original bits, and the 8 bits are scrambled. In the following table the sign ^ is used to represent the XOR operation.
 
New:
B20
B21
B22
B23
B24
B25
B26
B27
From:
B13
B11
B12^B10
B10
B11^B13
B13^B12
B12
B11^B10

2. XOR original bits with ROM contents: Use bits B22 and B24 to address a 4x4 bit ROM, and find the values for A, B, C, and D. Use these values read from the ROM to compute the new values for the bit according to the table below.
 
Address
Output
B22
B24
A
B
C
D
0
0
1
0
0
1
0
1
0
0
1
0
1
0
0
1
1
0
1
1
1
1
0
0
New: B30 B31 B32 B33 B34 B35 B36 B37
From: B20^A  B21^B B22 B23^C B24 B25 B26^D B27

3. Final Permutation, Based on sequence: The 8 bits are permuted according to an random scheme.  We count the number of inputs, starting with Input #0. There are 8 different permutations. The Input #0 uses the first permutation (from the first line of the table), the Input #1 uses the second ... the Input #7 uses the eighth, Input #7 uses the first (same as Input #0) and so on.
New: B40 B41 B42 B43 B44 B45 B46 B47
Input #0, From: B31 B37 B32 B30 B36 B35 B34 B33
Input #1, From: B35 B30 B33 B37 B31 B34 B36 B32
Input #2, From: B32 B33 B35 B36 B34 B31 B30 B37
Input #3, From: B33 B37 B31 B34 B30 B36 B35 B32
Input #4, From: B36 B31 B33 B30 B32 B34 B37 B35
Input #5, From: B34 B36 B32 B31 B33 B35 B37 B30
Input #6, From: B37 B31 B33 B35 B32 B34 B30 B36
Input #7, From: B32 B31 B35 B33 B36 B30 B34 B37

Example:

Here is what would happen when encrypting the input 'A' from the keyboard (Note that all bit numbers are in reference to the previous step in the process).

First, we get the scancode, which for the 'A' key is X"1C", from the KB_READER. We want this to be the hex value A, (10 decimal), which is 1010 in binary. This is what the KB_HEX unit does (see the block diagram further down this page).
1 0 1 0

but the above description has the LSB on the left, so we mirror this:
0 1 0 1

now, expand and permute:
1 (bit 3) 1 (b1) 0 (b2 XOR b0) 0 (b0) 0 (b1 XOR b3) 1 (b3 XOR b2) 0 (b2) 1 (b1 XOR b0)

Now, use bits 2 and 4 to find a value from the ROM:
b2 b4 A B C D
0 0 1 0 0 1

And do the XOR:
0 (b1 XOR A) 1 (b1 XOR B) 0 (same b2) 0 (b3 XOR C) 0 (same b4) 1 (same b5) 1 (b6 XOR D) 1 (same b7)

Finally, we do the final permutation. Now, since this depends on how many inputs came before this one, lets just say that this is the 3rd input, so we use row 2 (0 based, remember) of the permutation table:
permutation 2 2 3 5 6 4 1 0 7
original (above): 0 1 0 0 0 1 1 1
final: 0 0 1 1 0 1 0 1

Now, we need to output this value. We'll just use normal binary to hex conversion, and use the left 4 bits for the left hex digit, and the others for the right digit.
binary hex
First Hex Digit: 0011 3
Second Hex Digit: 0101 5

So, the final output on the XSTends board LEDs would be 35.

Decryption is the same process, but backwards.

Assignment:

Your task for this lab is to implement the Treehouse algorithm, using VHDL (only).  First, You will take input from the keyboard, and output the encrypted data to the two 7-segment LED displays on the XSTends board.  For this assignment you should consider that only the numerical keys in the keypad and the letters A - F are legal keys (this assumption shall simplify your design). These key inputs will be interpreted as HEX digits. Second, you will implement the decryption algorithm for Treehouse (also in VHDL), and implement that concurrently in the FPGA.  The input for the decrypter will be the output of the encrypter.  The output of the decrypter will be displayed on the 7-segment display on the XS40 board.  Here is a block diagram for the overall design. Note that the LEDs on the XStends board are ACTIVE-LOW, while the LED on the XS40 board is ACTIVE-HIGH. Your schematic may differ from this diagram, as long as it implements all the functionality as described above in VHDL.

Note that the blocks in this diagram may themselves be composed of several components with their own block diagrams. The only requirement is that the pieces be made in VHDL, but you can decompose the problem however you like. If you create a macro from a schematic (here's how) (for example, if you use several VHDL modules to create the encrypter, place these modules in a schematic and create a symbol from this schematic for use in your top level schematic), be sure to include this schematic in your lab report. Also, the KB_READER component will be provided for you, since is uses sequential logic, which we have not covered yet.  You are required to build all the other components (or components that result in equivalent final functionality (ie: as long as you end up with encryption and decryption functionality, and they both work and were created using VHDL (and the decryption part takes it's input from the encryption part), that's an acceptable solution))

In order to know when a key has been pressed, you will have to use processes in VHDL (to trigger the encryption process, and to count inputs for step 3). The KB_INPUT module has 3 outputs: RDY_PRS, RDY_RLS, and SCANCODE. RDY_PRS indicates when a key is pressed, RDY_RLS indicates when a key is released and SCANCODE is the PS/2 keyboard scancode used to identify which key was pressed. Note that this is a special encoding - it is NOT ASCII !!. You will also need a reset input in the module(s) where you count how many keys have been pressed, since successful encryption and decryption depends on starting at a known number of key presses. The KB_READER also needs this reset input. You should connect the RESET signal to the (active low) RESET button on the XStends board.

note that you will need to write your own .ucf file for the pin assignments for this lab.

Resources:

Here is some sample VHDL process code: .vhd or .txt Note that you can only assign to a signal in one process (or you will get errors about multiple drivers). You can read the value of a signal in any number of processes.

The Treehouse Encryption Algorithm, implemented in C: treehouse.c

PS/2 keyboard scancodes (local copy) The KB_READER will give you the "MAKE CODE" from this table. Don't worry about the "BREAK CODE". All the values are given in hex (ie X"2F" in vhdl). Also, since you are using the keypad for numerical input, use the KP_# values instead of the # values.

KB_INPUT VHDL code. Place this code in your project directory, open the HDL editor (from the main screen, with your project open) and open this code, then create a macro from it.

[Return to CMPUT 329 Lab Home Page]

Created by Paul Berube, 2001