CMPUT 329

Lab #3

Treehouse Encryption

(2 weeks, Pairs)

You may work in PAIRS for this lab.

Overview

This lab introduces more complex use of VHDL components. The overall premise is encryption of keyboard input based on a well defined algorithm. Your job is to implement the given algorithm, create your own decryption algorithm and ensure that these signals are sent to the proper locations.

Background

Your little brother is a member of a "secret club" with his school friends. The members of the club thought it would be really cool to be able to send secret messages to each other, but they are disappointed by the quality of the paper algorithms in their favourite mystery novels, which are weak against the energy and creativity (not to mention their knowledge of mystery novel) of pesky siblings and parents.

The club approaches you, their own personal computer guru, to find a solution. Fortunately, they are quite well-funded, as one of the members' fathers has purchased FPGA setups for their clubhouses. They have commissioned you to create a hardware solution for their problem. In turn, you have come up with the Treehouse Encryption Algorithm. Though terribly weak against serious attacks, it is sure to defeat intruders interested in the club's secret messages. (The exact assignment is detailed here.)

Prelab:

  1. Read the the lab assignment, and understand the treehouse.c source code and the description given on this page. If you have a reasonable grasp of how the encryption works it will be easier to implement this design. Look at the required module specifications. Think about how you will implement the required components in VHDL.

  2. Sketch out the design of the circuit. Keep in mind the overall objective of the lab when putting components together. Pay attention to matching the inputs of one module with the outputs of another.

  3. 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 detailed enough to describe a hardware design).

The Algorithm:

The Treehouse Encryption Algorithm, implemented in C: treehouse.c
The algorithm takes in a 4-bit quantity and returns an 8-bit quantity. The 4-bit input is the hexadecimal number generated by the keyboard reader, these bits are named k3, k2, k1 and k0. There are several steps in this transformation:
  1. Expand and permute the original bits
    The k3, k2, k1 and k0 are used to create four new bits by XORing pairs of the original bits, and then the 8 bits are scrambled to form the bits p7, p6, ..., p0. In the following table the sign ^ is used to represent the XOR operation.

    2. Step 1:
    Output: p7 p6 p5 p4 p3 p2 p1 p0
    Source: k1^k0 k2 k3^k2 k1^k3 k0 k2^k0 k1 k3

  2. XOR original bits with ROM contents:
    Using the values of p2 and p4 of the result to address a 4x4 bit ROM, and find the values for A, B, C, and D. Use A, B, C, and D to compute the values for a new set of 8-bits r7, r6, ..., r0 according to the table below.

    3. Address Output
    p2 p4 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

    Step 2:
    Output: r7 r6 r5 r4 r3 r2 r1 r0
    Source: p7 p6^D p5 p4 p3^C p2 p1^B p0^A

  3. Final Permutation, Based on sequence
    Bits r7, r6, ... r0 are permuted according to an random scheme based on the following table to generate the value of the output o7, o6, ..., o0 to be finally transmitted. The first character (input #0) uses the first permutation (Permutation #0), the second uses the second permutation, and so on. After eight characters are processed, the cycle repeats.

    4. Step 3:
    Output: o7 o6 o5 o4 o3 o2 o1 o0
    Permutation #0: r3 r4 r5 r6 r0 r2 r7 r1
    Permutation #1: r2 r6 r4 r1 r7 r3 r0 r5
    Permutation #2: r7 r0 r1 r4 r6 r5 r3 r2
    Permutation #3: r2 r5 r6 r0 r4 r1 r7 r3
    Permutation #4: r5 r7 r4 r2 r0 r3 r1 r6
    Permutation #5: r0 r7 r5 r3 r1 r2 r6 r4
    Permutation #6: r6 r0 r4 r2 r5 r3 r1 r7
    Permutation #7: r7 r4 r0 r6 r3 r5 r1 r2

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).

  1. First, we get the scancode, which for the 'A' key is 0x1C, from the KB_READER. We want this to be the hex value A, (10 decimal), which is 1010 in binary. Thus the output of the KB_HEX unit should be:
    2. k3 k2 k1 k0
    1 0 1 0

  2. Expand and permute:
    3. p7 p6 p5 p4 p3 p2 p1 p0
    1 0 1 0 0 0 1 1
    (k1^k0) (k2) (k3^k2) (k1^k3) (k0) (k2^k0) (k1) (k3)

  3. Use bits 2 and 4 to find a value from the ROM:
    4. p2 p4 A B C D
    0 0 1 0 0 1

  4. Do the XOR to obtain r7, r6, ..., r0:
    5. r7 r6 r5 r4 r3 r2 r1 r0
    1 1 1 0 0 0 1 0
    (b7) (b6^1) (b5) (b4) (b3^0) (b2) (b1^0) (b0^1)

  5. Do the final permutation. Now, since the permutation to be used depends on how many characters came before this one, lets just say that this is the 3rd character, therefore we use row 2 (0 based, remember) of the permutation table which is:
    6. Output: o7 o6 o5 o4 o3 o2 o1 o0
    Value: 1 0 1 0 1 1 0 0
    Permutation #6: r7 r0 r1 r4 r6 r5 r3 r2

  6. Thus we must output this final value: 10101100. 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.

    		7.  Binary Hex
    First Digit: 1010 A
    Second Digit 1100 C
Thus, the final output on the XSTends board LEDs is AC. Decryption follows a similar, although reversed, process.

Lab:

You must implement the Treehouse algorithm using VHDL. You must read input from the keyboard, interpret it as hexadecimal, and encrypt it for display on the two 7-segment LEDs on the XStend board. For this assignment, you should only cosider the keypad numerical keys as well as the letters A-F as legal keys (in order to simplify your design.)

Further to the encryption, you must also implement a decryption algorithm, and output the decryption of the encrypted signal on the upper LED. This must work concurrently with the encryption, such that the key inputted is shown simultaneously with the encrypted signal. (note: the LEDs on the XStend board are active-low whereas those on the XSA-50 boards are active-high.)

In order to complete this lab, you must think carefully about the components that you need and how they work together. Obviously, the keyboard input module is a requirement. You may also want to reuse the scancode-hexadecimal translator module from Lab 2. The most important components, however, are the core of the design: the encryption and decryption; you must design these components on your own. When designing these parts, you must think about the functionality required. You have to encrypt and decrypt the digits, but you also must keep track of the numerical order of the inputs. Moreover, the outputs must be translated into a LED display format.

Because we are using testbenches to determine part of your mark, there are some required modules for your design that will ensure that your design works under the testbench conditions:
Entity Ports In Ports Out
Encrypter: count[2:0], hex[3:0] data[7:0]
Decrypter: count[2:0], data[7:0] hex[3:0]
Counter: incr, reset count[2:0]

Your design of the content of these modules is not limited. You may break them down further if you like. Moreover the design of the inner workings are up to you. The interface, however, must be written in this manner to work with our testbench.

To know when to check the keyboard input, you should use processes in VHDL that are sensitive to the keyboard input modules press signal. Sensing the press signal will enable the timely recomputation of the encrypted output and allow you to increment the counter.

There is one other issue involving this design that may cause some problems. When the circuit is reset, or when the keyboard connects to the PS/2 port, a confirmation signal is sent to the keyboard (as per the PS/2 protocol.) Because of how the keyboard input module is designed this confirmation signal might result in a reset being read as a key press. Depending on the design of your Counter module, this extra (invalid) key press result in your counter being incremented just after the circuit is reset. To prevent this problem, you should design your counter in such a way that it is incremented when a key is pressed and a valid scancode is detected.
NOTE: You need to write your own .ucf file for the pin assignments for this lab. Refer to the XSA details page as necessary.

Deliverables

You must submit all VHDL files used in your design (including those resources from this page that you have used) in a zip file called 'lab3.zip'.

Grading:

Resources:

[Return to CMPUT 329 Lab Home Page]
Created by Paul Berube, 2001; Modified by Paras Mehta, 2003.