本次美国代写是C++密码学的assignment

Introduction

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

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

In the Hill cipher the encryption key is an invertible, integer matrix of size nn and the algorithm is matrix
arithmetic; i.e.,

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 [1] and/or Section 2 (‘A Quick Reminder on Modular Arithmetic’) of
[2].

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 defined in the starter code inside the file Hill.hpp. Do not modify the public
portion of the class definition; you may modify the private portion. You will need to define the internal members
and methods and implement all methods in the Hill.cpp file. 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 file sets up everything for you. Just
generate your build directory for your development environment as described in the course work-flow 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 [1]).

Sections 3.1–2 of both [1] and [2] illustrate how to encode characters into integer matrices and perform
encryption/decryption (note in the case of [2] 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 [1] nicely shows why). Thus it is
not sufficient 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 find implementing a matrix inversion the most difficult 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 [1] and Section 2.3 of [2] illustrate matrix inversion, modulo a number (29 and 26, re-
spectively). You are encouraged to first review the Gauss-Jordan algorithm for the non-modulo case before
proceeding to modular matrix inversion ([3] shows the method for different sized matrices). An online
calculator may be used to check your implementation (e.g., [4]).

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 [1]
provides the multiplicative inverses for a = [1; 28] and c = 29.

2.3 Known-Plaintext Attack

Section 3.3 (‘Cracking a Hill cipher’) of [1] and Section 4 (‘Breaking the Hill Cipher’) of [2] provide the
mathematical basis for understanding a KPA, as well as a few illustrative examples of the process. Example 5 of
[1] is especially informative.

3 Hints

• 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++.

4 Grader

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 filling 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 file containing only the files: Hill.cpp, Hill.hpp, and
student_tests.cpp. There is a build target called “submission” configured by default to create this file with
the correct contents in your build directory.