Introduction

The goal of this assignment is to design and implement a simple cryptographic cipher. A cipher transforms sensitive information (plaintext) into a form that is meaningless to all but the intended recipients (ciphertext). The process that transforms plaintext into ciphertext is called encryption and requires an encryption key. The reverse process is called decryption and transforms ciphertext back into plaintext using a decryption key.

In this assignment you will implement a simple version of the Hill cipher. The Hill cipher uses linear transformations to encrypt and decrypt data. The plaintext and ciphertext are represented by vectors of three values. The encryption and decryption keys are represented by 3x3 matrices. Encryption is done by multiplying the plaintext vector P with the key matrix K to obtain the ciphertext C as shown in figure 1. Decryption is done in the same way using the inverse of the the key matrix.

Figure 1: Encryption Operation

In this implementation all values are 4-bit wide allowing the representation of integers between 0 and 15. All operations are performed in modulo-16 arithmetic which amounts to discarding all but the four least significant bits of results as illustrated in the following example:

5₁₀ * 7₁₀ mod 16₁₀  = 35₁₀ mod 16₁₀ = 3₁₀

0101₂ * 0111₂ mod 16₁₀ = 10011₂ mod 16₁₀ = 0011₂.

Modulo arithmetic also obeys the following two rules:

.

Intermediate values of modulo-16 arithmetic calculations can thus be truncated to their least significant four bits.  

The Hill cipher requires the encryption key to be invertible in modulo-16 arithmetic. Here are three valid key pairs:

Figure 2: Key Pairs

In this assignment  you will implement the Hill cipher using VHDL. The cipher is composed of three main parts: the matrix multiplier, the key loader and key inverter. The matrix multiplier performs the actual encryption and decryption of data. The key loader is a mechanism that loads a key matrix column-by-column and stores it. The key inverter is a module that computes the decryption key corresponding to the stored encryption key. The complete Hill cipher is capable of both encrypting and decrypting data given a single key. 

The following sections will guide you through the implementation of the Hill cipher. In each section, you will be given a vector file that must be used to test your modules. The interface of each component is specified. The vector files will only work if you use the port names specified in the interface diagrams. Also note that the vector files are written with a clock frequency that should be sufficiently low for your designs. If the clock frequency of the vector files exceeds the maximum operating frequency of your design, you can modify the vector file by scaling every time value by the same factor. 

(Note: This assignment can be completed using the student version of Altera Max+Plus II.)

Design and Implementation

Part 1: Matrix Multiplier

The matrix multiplier is at the core of the Hill cipher. This module multiplies a 1x3 matrix (plaintext) by a 3x3 matrix (key). The result is a 1x3 matrix (ciphertext). Refer to figure 1 for details. Remember that all operations are performed using modulo-16 arithmetic.

The key matrix input will come from the key loader and can be assumed to be stable. It is thus not necessary to latch it into input registers. The plaintext input, on the other hand, will come from the user and should be read only on the rising edge of the clock. Similarly the ciphertext output should change only on the rising edge of the clock. The matrix thus has input registers for the plaintext and output registers for the ciphertext.

Name the ports of you matrix multiplier according to the interface shown in figure 3. Use this vector file for your simulations.

Figure 3: Interface of Matrix Multiplier

a) Behavioral Description 

Implement the matrix multiplier in VHDL using a behavioral description. A VHDL behavioral model specifies a module's function using VHDL programming constructs such as "if-then-else" clauses, etc. It does not specify any internal structure. 

Hints: 

• The FAQ explains how to perform arithmetic computations using signals of type STD_LOGIC_VECTOR.
• Registers can be implemented in behavioral VHDL by updating  signals on the rising edge of the clock. The cleartext input should thus be latched into internal signals on the rising edge of the clock. Similarly, the output ports should be written only on the rising edge of the clock.

Compile and test the design using the provided vector file. Include in the report a summary of the design's resource usage and maximum operating frequency.

b) Structural Description

Implement the matrix multiplier in VHDL using a structural description. A VHDL structural model specifies a module's internal structure by identifying all internal modules or units (call these "sub-modules") and defining how they are interconnected using the "port map" construct. It does not specify any internal behavior. 

Notice that each of the three elements in the resulting vector is computed through the same operations:

c_x = p₁k_1x + p₂k_2x + p₃k_3x.

Implement a sub-module that performs this computation using a structural description. Use lpm_mult and lpm_add_sub modules. LPM modules are predefined components provided by Altera Max+Plus II. See the Altera Max+Plus II help files for more details. You can use the simplest design possible with three multipliers and two adders. 

Hint: Read the compilation warnings carefully. Notice that when the output of the lpm_mult doesn't contain enough bits to represent all possible results the least-significant bits are discarded. Remember that we wish to discard the most-significant bits and keep the four least-significant bits. 

Use three of these sub-modules to form the structural description of the matrix multiplier. Add input and output registers for the plaintext input and ciphertext output using lpm_ff modules. 

Compile and test the design using the provided vector file. Include in the report a summary the design's resource usage and maximum operating frequency.

Part 2: Key Loader

A cipher is typically used for long periods of time without changing the encryption key. It is thus impractical to provide the key on dedicated input pins at all times. To save input pins, the key will be loaded in three cycles through the ports normally used to load the plaintext data. Remember that the plaintext data consists of three 4-bit values while the key consists of a 3x3 matrix of 4-bit values. 

A load_key signal will be raised for three clock cycles to load the key into the key loader. The first column of the key will be presented at the inputs on the first rising edge of the clock, followed by the second and third columns on subsequent clock cycles. The key loader loads one column of the key on each of the three rising edges of the clock during which the load_key signal is enabled. The key is then held stable at the output until a new key is loaded. The interface of the device is shown in figure 4. Ports p1, p2, and p3 correspond to the first, second and third row of a key column. Use this vector file for testing.

Figure 4: Interface of Key Loader

a) State Machine

Implement the key loader using a behavioral description in the form of a state machine. Figure 5 shows a suggested state diagram. Note that state machines usually have a reset mechanism. Instead of using a reset signal for this state machine we will use the fact that it goes to the idle state after at most 4 clock cycles unless the load_key signal is raised.

Figure 5: State Diagram of Key Loader

Hint: Remember that the first column is latched on the first rising edge of the clock during which the load_key signal is high. The first column of the key must be latched at the same time as the state of the state machines goes from idle to load_column_1. This can be done by  updating the output signals corresponding to the first column in the same processing block used to change the state to load_column_1.

Include your state diagram in the report if it is different from figure 5. Compile and test the design using the provided vector file. Include in the report a summary of the design's resource usage and maximum operating frequency.

b) Structural Description

It is also possible to implement the key loader using a simple chain of register banks. Figure 6 shows a diagram of a possible design. All the registers are enabled only when the load_key signal is high. The first column is loaded in the first bank of registers on the first clock cycle and is shifted to the second and third banks on the subsequent clock cycles. Note that the clock is not shown in this diagram.

Figure 6: Structural Diagram for Key Loader

Implement this design in structural VHDL. Indicate any changes that you made to this design in the report. Compile and test the design using the provided vector file. Include in the report a summary of the design's resource usage and maximum operating frequency. 

Part 3: Key Inverter

Encryption and decryption are performed through the same computations using two different but related keys. The key loader implemented in the previous section will hold an encryption key. In this section we will implement a module capable of computing the decryption key corresponding to the encryption key. The module will be implemented using a mixed behavioral and structural description. Figure 7 shows the interface of this module.

Figure 7: Interface of Key Inverter

The decryption key is the inverse matrix (in modulo arithmetic) of the encryption key. The inversion operation will be broken down into simple computations. The first step is to compute the cofactors of the key matrix as follows:

cof₁₁ = ek₂₂ek₃₃ - ek₂₃ek₃₂
cof₁₂ = ek₂₃ek₃₁ - ek₂₁ek₃₃
cof₁₃ = ek₂₁ek₃₂ - ek₂₂ek₃₁
cof₂₁ = ek₁₃ek₃₂ - ek₁₂ek₃₃
cof₂₂ = ek₁₁ek₃₃ - ek₁₃ek₃₁
cof₂₃ = ek₁₂ek₃₁ - ek₁₁ek₃₂
cof₃₁ = ek₁₂ek₂₃ - ek₂₂ek₁₃
cof₃₂ = ek₁₃ek₂₁ - ek₁₁ek₂₃
cof₃₃ = ek₁₁ek₂₂ - ek₁₂ek₂₁

The second step is to compute the adjoint matrix of the key. The adjoint matrix is the transpose matrix of the cofactor matrix and can be inverting its rows and columns as follows:

adj_ij = cof_ji

The third step is to compute the determinant of the key matrix:

det = k₁₁cof₁₁ + k₁₂cof₁₂ + k₁₃cof₁₃

The fourth step is to compute the multiplicative inverse of the determinant. Remember that we are still using modulo arithmetic. Computing a multiplicative inverse involves more than a simple division. Since there are only 16 possible determinants, we will use a ROM as a lookup table. Use this MIF file to initialize a lpm_rom module. This lpm_rom is the structural part of your design. All other computations can be performed behaviorally. Note that some determinants have no multiplicative inverse modulo-16. The ROM then returns the value 0. These cases correspond to invalid keys and can be ignored.

You now have all the elements necessary to compute the decryption key. The decryption key is the adjoint matrix computed above multiplied by the inverse of the determinant as found in the lookup table.

Notice that the computations required by this module are much more involved than those required by the matrix multiplication. The propagation delay of this module may thus become the limiting factor when determining the maximum operating frequency of the Hill cipher. To prevent this we will pipeline this module. Divide the computations in small operations and store intermediate results in pipeline registers. The key inverter will thus require a few clock cycles to produce the correct value but will not affect the maximum operating frequency of the design.

Hint: To pipeline behavioral code, simply use internal signals for the result of each intermediate computation and update these signals only on the rising edge of the clock. 

Compile and simulate this design using this vector file. Include in the report a summary of the design's resource usage and maximum operating frequency. What is the latency of this module?

Part 5: Hill Cipher

You now have almost all the parts necessary for a complete Hill cipher module capable both of encrypting and decrypting given only the encryption key. You will now need to implement a simple multiplexer capable of switching between two 3x3 matrix keys. Once this multiplexer is implemented and tested, place it at the key input of the matrix multiplier and use it to select between the encryption key and the decryption key. Figure 8 shows a diagram of the complete Hill cipher. Notice that the encrypt signal should be latched into a register so that it can be changed by the user between rising edges of the clock. The multiplexer must select the encryption key when the encrypt signal is high and the decryption key when it is low. Remember that the decryption key will be available only a few clock cycles after a new encryption key is loaded. You may choose any of the matrix multipliers and key loaders developed in sections 1 and 2. 

Figure 8: Complete Hill Cipher Diagram

Implement, compile and simulate this design using this vector file. Figure 9 shows the interface of this module. include in the report a summary of the design's resource usage and maximum operating frequency.

Figure 9: Interface of Hill Cipher

Guidelines

Source Code

Your VHDL code should be well documented. Each file should start with a header including the filename, the authors, the creation date, the last revision date and a meaningful description. A description for mux2.vhd such as "this is the mux2 implementation" doesn't add any information and is not considered meaningful. All the ports of an entity should be briefly described. Comments should be used to indicate interesting parts of the code or parts that could be improved. Use descriptive names for your variables and signals to improve the readability of your code. Imagine that someone who isn't familiar with this assignment is reading your code and trying to understand it.

Follow the code submission procedure described bellow to submit an electronic copy of your code. Do not hand-in a hardcopy of your code. 

Laboratory Report

Your laboratory report should include the following sections:

• A front page (course number, lab title, student name, ID, email, date).
• A summary of the results as requested in this document (resource usage and maximum operating frequency of designs, latency of key inverter, etc.).
• A brief discussion of known problems with your implementation of the Hill cipher or its sub-components, if any. 
• A brief description of changes that were made to the specifications or to vectors files, if any. (Not following the specifications will be penalized if not justified.)
• An index of the source files included in the electronic submission. 

Do not include simulation traces in the report. (Simulation files must be submitted electronically.)

Mini Presentation

As part of your report requirements, you will record and submit a brief (2 minute) oral presentation, using the Mini Presentation system in the EMF lab (McDonald Harrington).

The following questions are to be answered within the two-minute time frame allotted for your presentation:

1. For a general VHDL design, what factors should determine your choice between a behavioural vs. a structural design?
2. Which of these approaches do you think is better for the matrix multiplier of section 1 of this assignment? Justify your response.

Grading Scheme

Each model will be evaluated based on the following criteria:

• Elegance and efficiency of the design
• VHDL code (comments, structure, etc.)
• Testing and simulation results
• Evaluation of the model (throughput, latency, resource usage, etc.)

Code Submission Procedure

The "Subject:" field of your email message must have the following format: 487-A1-LASTNAME, with your own last name in place of LASTNAME; do not write anything else in the subject; do not write anything in the message other than the tar file. 

The tar file must create, when opened, a directory named with your student ID. (Just choose one for your group.) In this directory you should have only the .vec, .acf, .scf and .vhd files that you used for your assignment and a README file. Deductions will be made for missing or tampered files.

An example sequence of UNIX shell commands that creates and sends a tar file as specified follows [comments in square brackets]. Note that the example assumes a student's last name of "brynjolfson" with a student number of 952334. If your last name is not "brynjolfson" or your student number is not 952334, then make the appropriate changes if you want to receive credit.

[Create the source directory for student with id 952334.]
   % mkdir ./952334

[Copy all the sources in it.]
   % cp foo.acf bar.scf baz.vhd flop.vhd README ./952334

[Create the tar file with the directory content.]
   % tar cvf 487-A1-brynjolfson.tar ./952334

[Uuencode the tar file]
   % uuencode 487-A1-brynjolfson.tar 487-A1-brynjolfson.tar > 487-A1-brynjolfson.tar.uu

[Send it with the proper subject field.]
   % mail -s "487-A1-brynjolfson" 
Follow these instructions closely; if you don't, marks will be deducted. 
Yes, you'll need to use UNIX to submit your NT assignment. 



Last updated on 9/14/01 
by Vincent Levesque