本次美国代写是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 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

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 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 [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 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 [1] and Section 2.3 of [2] 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 ([3] shows the method for diﬀerent 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 ﬁ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.