The second part of Project 1 will familiarize you with algorithm development and show you how a class you’ve
previously written can be used to solve a problem eﬃciently.
1 The Hill Cipher
Cryptography is the art and science of turning ordinary information (plaintext) into seemingly random
information (ciphertext), and vice-versa, through the use of an encryption algorithm. Transforming a plaintext
P into a ciphertext C is accomplished using the encryption algorithm with an encryption key E. The reverse
process, known as decryption, relies on using the algorithm with a decryption key D to transform C back into
In the Hill cipher the encryption key is an invertible, integer matrix of size nn and the algorithm is matrix
C = EP (1)
where P is an n p matrix representing the integer equivalents of our plaintext symbols, with C (also an
n p matrix that) representing the integer equivalents of our ciphertext symbols. Note that we have to convert
(map) our plaintext into integers to be able to perform the matrix multiplication that constitutes the Hill cipher.
To decrypt the ciphertext C one uses the inverse of the encryption key as the decryption key D. Note that
by multiplying both sides of (1) by E 1 we have
E 1 C = E 1 EP = P (2)
Thus, using D = E 1 we are able to recover the plaintext
P = DC = E 1 C = P (3)
The one caveat of all this is that operations (multiplication, addition, and subtraction) must be performed
modulo an integer. Before proceeding, if not familiar with modular arithmetic (and its notation), you should
read Section 2 (‘Modular Arithmetic’) of  and/or Section 2 (‘A Quick Reminder on Modular Arithmetic’) of
2 The Hill Class
The class you are to implement allows for the encryption and decryption of a std::string using the Hill cipher.
Given an encryption key E, the class will be capable of deriving the decryption key D, and vice-versa. It will
also be capable of launching a known-plaintext attack (KPA) on the Hill cipher. In a KPA it is assumed that an
adversary knows (guesses) the plaintexts that correspond to a given set of ciphertexts. The succesful use of
KPA against German and Japanese ciphers was not merely incidental to the Allies winning World War II.
The outline of the class is deﬁned in the starter code inside the ﬁle Hill.hpp. Do not modify the public
portion of the class deﬁnition; you may modify the private portion. You will need to deﬁne the internal members
and methods and implement all methods in the Hill.cpp ﬁle. You should add appropriate comment blocks to
each method, as well, in Hill.cpp. You will need to write tests in the student_tests.cpp using the Catch
testing framework, as described in class. The included CMakeLists.txt ﬁle sets up everything for you. Just
generate your build directory for your development environment as described in the course work-ﬂow tutorial.
2.1 Encoding Plaintext and Performing Encryption/Decryption
The Hill cipher is built on matrix arithmetic so all of the information we encrypt/decrypt must be represented by
numbers (otherwise how would we perform matrix operations on the plaintext?) For this project we’ll assume
that we are encrypting/decrypting the 26 upper-case letters of the English alphabet, as well as the period,
question mark, and blank space (for a total of 29 characters) so we’ll need to map each character (symbol) to
an integer via a conversion table. We’ll use the straightforward mapping of A ! 0; B ! 1; :::; space ! 28 (see
Table 3 of ).
Sections 3.1–2 of both  and  illustrate how to encode characters into integer matrices and perform
encryption/decryption (note in the case of  that only upper-case letters of the English alphabet are used).
2.2 Modular Arithmetic and Matrix Inversion
As noted above all of our matrix arithmetic will be modular (Section 2.3 of  nicely shows why). Thus it is
not suﬃcient to simply invert a matrix, it must be done modulo some number. In the Hill cipher this number
must equal the number of symbols in our plaintext alphabet (i.e., 29).
You will ﬁnd implementing a matrix inversion the most diﬃcult part of this project. You are not allowed
to use someone else’s code or a library (e.g., Boost C++) to perform the matrix inversion. The inverse
of a matrix can be determined by concatenating the matrix with an appropriately sized identity matrix and
putting the matrix into reduced row echelon form. You are highly encouraged to use Gauss-Jordan elimination
to calculate matrix inversions (the TAs will only be familiar with this approach).
Example 4 of  and Section 2.3 of  illustrate matrix inversion, modulo a number (29 and 26, re-
spectively). You are encouraged to ﬁrst review the Gauss-Jordan algorithm for the non-modulo case before
proceeding to modular matrix inversion ( shows the method for diﬀerent sized matrices). An online
calculator may be used to check your implementation (e.g., ).
Info: In non-modulo (regular) Gauss-Jordan elimination one divides the row by the pivot entry to make the
pivot entry equal to one. In the modular version one multiplies the row by the pivot’s modular multiplicative
inverse to make the pivot entry equal one.
Given the number a, it’s multiplicative inverse is the number b such that ab 1 mod c. For example,
when c = 29 the multiplicative inverse of a = 2 is b = 15 as 2 15 mod 29 = 30 mod 29 = 1. The
multiplicative inverse for a given a; c can be found using the Extended Euclidean Algorithm. Table 7 of 
provides the multiplicative inverses for a = [1; 28] and c = 29.
2.3 Known-Plaintext Attack
Section 3.3 (‘Cracking a Hill cipher’) of  and Section 4 (‘Breaking the Hill Cipher’) of  provide the
mathematical basis for understanding a KPA, as well as a few illustrative examples of the process. Example 5 of
 is especially informative.
• It is recommend that your matrix inversion code (e.g., Gauss-Jordan elimination algorithm) is working
before proceeding to the other methods.
• The results of Gauss-Jordan elimination indicate whether a matrix is invertible.
• Note the bounds for the modular operation. In the references taking the modulus of a negative number
always results in a positive number. This is not the default behavior with the % operator in C++.
We will be using an automatic grader to help you determine your assignment’s completeness and correctness.
A portion of each assignment grade will be determined by the number of passing tests as determined by the
autograder, with our evaluation ﬁlling in the rest. This means you know before you turn in your submission
that all is well. You can submit to the autograder as many times as you like, but it is rate limited (4 submissions
every hour) to keep you from using it as your compiler. See this canvas for a summary of how to use the grader
(Note is is not WebCAT, which many of you may be familiar with).
For this assignment you should upload a zip ﬁle containing only the ﬁles: Hill.cpp, Hill.hpp, and
student_tests.cpp. There is a build target called “submission” conﬁgured by default to create this ﬁle with
the correct contents in your build directory.