程序代写 CS 61B Fall 2021

10/28/21, 8:21 PM
Project 1 | CS 61B Fall 2021
Course Info
1: The Enigma

Introduction
This programming assignment is intended to exercise a few useful data structures and an object-based view of a programming problem. There is some background reading, but the necessary program is not (or rather need not be) terribly big. The conceptual video walkthrough is located here, which we HIGHLY RECOMMEND watching.
We will be grading largely on whether you manage to get your program to work (according to our tests). In addition, we will be looking at your own tests (which you should be sure to turn in as well). While we have supplied a few unit tests and some simple integration tests and testing utilities, the tests in the skeleton are entirely inadequate for testing your program. There is also a stylistic component: the grading machinery require that your program pass a mechanized style check (style61b), which mainly checks for formatting and the presence of comments in the proper places. See the Style Guide for a brief description of the style rules. You may change any of the code we’ve provided, as long as the resulting program works according to the specifications here.
To obtain the skeleton files (and set up an initial entry for your project in the repository), you can use the command sequence
git fetch shared
git merge shared/proj1 -m “Get proj1 skeleton”
from your Git working directory. Should we update the skeleton, you can use exactly the same sequence to update your project with the same changes.
Background
You may have heard of the Enigma machines that Germany used during World War II to encrypt its military communications. If you have not, I recommend you read the wikipedia page on them, or similar resource, especially the part about design and operation. This video shows what one version of the machine looked like and how it operated. This project involves building a simulator for a generalized version of this machine (which itself had several versions.) Your program will take descriptions of possible initial configurations of the machine and messages to encode or decode (the
Navigation
Introduction
Background
Describing Permutations
Input and Output
Editing Main
Handling Errors
Writing Unit Tests & Integration Tests
Running Enigma in IntelliJ
Comparing with the Staff Solution
Extra Credit Office Hours Checkpoint What To Turn In Grading Details Advice Common Bugs
https://inst.eecs.berkeley.edu/~cs61b/fa21/materials/proj/proj1/index.html

10/28/21, 8:21 PM
Project 1 | CS 61B Fall 2021
Enigma algorithms were reciprocal, meaning that encryption is its own inverse Course Info Staff Beacon Resources Piazza
operation.)
The Enigmas effect a substitution cipher on the letters of a message. That is, at any given time, the machine performs a permutation—a one-to-one mapping—of the alphabet onto itself. The alphabet consists solely of the 26 letters in one case (there were various conventions for spaces and punctuation).
Plain substitution ciphers are easy to break (you’ve probably seen puzzles in newspapers that consist of breaking such ciphers). The Enigma, however, implements a progressive substitution, different for each subsequent letter of the message. This made decryption considerably more difficult.
The device consists of a simple mechanical system of (partially) interchangeable rotors (Walzen) that sit side-by-side on a shaft and make electrical contact with each other. Most of these rotors have 26 contacts on both sides, which are wired together internally to effect a permutation of signals coming in from one side onto the contacts on the other (and the inverse permutation when going in the reverse direction). To the left of the rotors, one could select one of a set of reflectors (Umkehrwalzen), with contacts on their right sides only, and wired to connect half of those contacts to the other half. A signal starting from the rightmost rotor enters through one of the 26 possible contacts, flows through wires in the rotors, “bounces” off the reflector, and then comes back through the same rotors (in reverse) by a different route, always ending up being permuted to a letter position different from where it started; that is, the permutation was always a derangement. (This was a significant cryptographic weakness, as it turned out. It doesn’t really do a would-be code-breaker any good to know that some letters in an encrypted message might be the same as the those in the plaintext if he doesn’t know which ones. But it does a great deal of good to be able to eliminate possible decryptions because some of their letters are the same as in the plaintext.)
Each rotor and each reflector implements a different permutation, and the overall effect depends on their configuration: which rotors and reflector are used, what order they are placed in the machine, and which rotational position they are initially set to. This configuration is the first part of the secret key used to encrypt or decrypt a message. The reflector’s permutation was designed to be a derangement, so each letter was mapped to a different letter, which guaranteed that the letter inputted into the enigma machine would be different than the one outputted. In what follows, we’ll refer to the selected reflector and rotors in a machine’s configuration as 1 through N, with 1 being the reflector, and N the rightmost rotor. In our simulator, N will be a configuration parameter. In actual Enigma machines, it was fixed for any given model (the Kreigsmarine (Navy) used (four rotors and reflector) and the Wehrmacht used
The overall permutation changes with each successive letter because some rotors rotate after encrypting a letter. Each rotor has a circular ratchet on its right side and an
Navigation
Introduction
Background
Describing Permutations
Input and Output
Editing Main
Handling Errors
Writing Unit Tests & Integration Tests
Running Enigma in IntelliJ
Comparing with the Staff Solution
Extra Credit Office Hours Checkpoint What To Turn In Grading Details Advice Common Bugs
https://inst.eecs.berkeley.edu/~cs61b/fa21/materials/proj/proj1/index.html

10/28/21, 8:21 PM Project 1 | CS 61B Fall 2021
Navigation
Introduction
Background
Describing Permutations
Input and Output
Editing Main
Handling Errors
Writing Unit Tests & Integration Tests
Running Enigma in IntelliJ
Comparing with the Staff Solution
Extra Credit Office Hours Checkpoint What To Turn In Grading Details Advice Common Bugs
letter of a message is translated, a spring-loaded pawl (lever)—one to the right of each rotating rotor—tries to engage the ratchet on the right side of its rotor and thus rotate its rotor by one position, changing the permutation performed by the rotor. Thus, pawls always try to engage with the ratchet of their own rotor. The lever on the rightmost rotor (N) always succeeds, so that rotor N (the “fast” rotor) rotates one position before each character. The pawls pushing the other rotors, however, are normally blocked from engaging their rotors by the alphabet ring on the left side of the rotor to their right. This interactive website provides a good visualization of how signals travel through the rotors and how messages are encrypted. DISCLAIMER: This visualizer does not depict the underlying details of how rotors rotate. It’s just a tool that may help your understanding of how the electrical signals propagate through the system.
This ring usually holds the pawl away from its own ratchet, preventing the rotor wheel to its left from moving. However, the rings have notches in them (either one or two in the original Enigma machines), and when the pawl is positioned over a notch in the ring for the rotor to its right, it slips through to its own rotor and pushes it forward. A “feature” of the design called “double stepping” (corrected in other versions of the Enigma, since it reduced the period of the cipher) is that when a pawl is in a notch, it also moves the notch itself and the rotor the notch is connected to. Since the notch for rotor is connected to rotor , when the pawl of rotor slips through into the notch for rotor , rotors on both sides of the pawl move (so rotor and rotor move).
The effect of advancing a wheel is to change where on the wheel any given signal enters or leaves. When a wheel is in its ‘A’ setting in the machine, then a signal that arrives from the right at, say, the ‘C’ position, goes into the ‘C’ contact on the wheel. Likewise, a signal that leaves the wheel from its left ‘C’ contact exits at the ‘C’ position. When the wheel is rotated by one to its ‘B’ setting, a signal that arrives at the ‘C’ position goes instead into the ‘D’ contact on the wheel, and a signal that leaves through the ‘D’ contact does so at the ‘C’ position. It’s easier to calculate if we use numbers 0- -25 rather than letters (‘A’ is 0, ‘B’ is 1, etc.). Then, when the wheel is in its setting, a signal entering at the position enters the contact on the wheel, and a signal exiting through the contact does so at the position. For example, Figure 1 shows one of the rotors from the real Enigma machines (called rotor “I”) and the effect of moving from its ‘A’ to its ‘B’ setting.
“alphabet ring” on its left side that fits over the ratchet of the rotor to its left. Before a
Course Info Staff Beacon Resources Piazza
https://inst.eecs.berkeley.edu/~cs61b/fa21/materials/proj/proj1/index.html
62 dom k − c c 62 dom k + p
i1−i i 1−iii

10/28/21, 8:21 PM
Project 1 | CS 61B Fall 2021
Rotor 2 advances whenever Rotor 3 is at C, pushed by pawl 2. Rotor 3 has a
Course Info Staff Beacon Resources Piazza
notch at C, so pawl 2 slips into the notch and engages with its ratchet (the ratchet belonging to Rotor 2). Rotor 3 also advances when it is at C, because when pawl 2 is engaged through Rotor 3’s notch it will push against that notch when it moves, moving Rotor 3, as well as moving Rotor 2 by pushing on Rotor 2’s ratchet.
Since there is no pawl 1, double-stepping does not occur, so Rotor 2 (unlike Rotor 3) does not advance just because it is at C.
Rotor 1 never changes, since there is no pawl on either side of it.
Each rotor can only advance at most one position per keypress.
So the advancement of the rotors, while similar to that of the wheels of an odometer, is not quite the same. If it were, then the next position after AACA would be AACB, rather than ABAB. Also, it would take 27 steps to return to the initial configuration instead of 18.
The contacts on the rightmost rotor’s right side connect with stationary input and output contacts, which run to keys that, when pressed, direct current to the contact from a battery or, when not pressed, direct current back from the contact to a light bulb indicating a letter of the alphabet. Since a letter never encrypts or decrypts to itself after going back and forth through the rotors, the to and from directions never conflict.
The used a machine with 12 rotors and five slots for them:
Eight rotors labeled with roman numerals I–VIII, of which three will be used in any given configuration as the rightmost rotors,
Two additional non-moving rotors (Zusatzwalzen) labeled “Beta” and “Gamma”, of which one will be used in any configuration, as the fourth-from-right rotor, and
Two reflectors (Umkehrwalzen), labeled ‘B’ and ‘C’, of which one will be used in any given configuration as the leftmost rotor.
Given just this equipment, there are 614,175,744 possible configurations (or keys): Two possible reflectors, times
Two possible rotors in the fourth position, times
choices for the rightmost three rotors and their ordering,
possible initial rotational settings for the rightmost four rotors (each reflector had only one possible position.).
Especially by today’s standards, this is not a large key size (less than 30 bits). To make things more difficult for code-breakers, therefore, the Enigma incorporated a plugboard (Steckerbrett) between the keyboard and the rightmost wheel. It acted as a non- moving, configurable rotor. The operator could choose any set of disjoint pairs of letters
Navigation
Introduction
Background
Describing Permutations
Input and Output
Editing Main
Handling Errors
Writing Unit Tests & Integration Tests
Running Enigma in IntelliJ
Comparing with the Staff Solution
Extra Credit Office Hours Checkpoint What To Turn In Grading Details Advice Common Bugs
https://inst.eecs.berkeley.edu/~cs61b/fa21/materials/proj/proj1/index.html
462 633 = !)3 − 8(/!8

10/28/21, 8:21 PM
Project 1 | CS 61B Fall 2021
by means of cables placed between them on the plugboard. Each selected pair would
Course Info Staff Beacon Resources Piazza
then be swapped going into the machine from the keyboard and coming out into the indicator lights. Thus, if the operator connected (“steckered”) the letters A and P, then P would be substituted for each A typed and vice versa. Likewise, if an ingoing letter was encrypted to P by the other rotors, it would display as A, and letters decrypted as A would display as P.
Describing Permutations
Since the rotors and the plugboard implement permutations, we’ll need a standard way to describe them. We could simply have a table showing each letter and what it maps to, but we’ll use a more compact notation known as cycle representation. The idea is that any permutation of a set may be described as a set of cyclic permutations. For example, the notation
(AELTPHQXRU) (BKNW) (CMOY) (DFG) (IV) (JZ) (S)
describes the permutation in Figure 1. It describes seven cycles: A maps to E, E to L, L to T, …, R to U, and U back to A.
B maps to K, K to N, N to W, and W back to B.
C maps to M, M to O, O to Y, and Y back to C.
D maps to F, F to G, and G back to D. I maps to V and V back to I.
J maps to Z and Z back to J.
S maps to itself.
The inverse permutation just reverses these cycles:
U maps to R, R to X, …, E to A, and A back to U. …
S maps to itself.
Each letter appears in one and only one cycle, so the mapping is unambiguous. As a shorthand, we’ll say that if a letter is left out of all cycles, it maps to itself (so that we could have left off “(S)” In the example above.)
Figure 2 shows the permutations corresponding to the rotors used in the ‘s Enigma machine.
Rotor I Rotor II
Permutation (as cycles) Notch
(AELTPHQXRU) (BKNW) (CMOY) (DFG) (IV) (JZ) (S) Q (FIXVYOMW) (CDKLHUP) (ESZ) (BJ) (GR) (NT) (A) (Q) E
Navigation
Introduction
Background
Describing Permutations
Input and Output
Editing Main
Handling Errors
Writing Unit Tests & Integration Tests
Running Enigma in IntelliJ
Comparing with the Staff Solution
Extra Credit Office Hours Checkpoint What To Turn In Grading Details Advice Common Bugs
https://inst.eecs.berkeley.edu/~cs61b/fa21/materials/proj/proj1/index.html

10/28/21, 8:21 PM
Project 1 | CS 61B Fall 2021
(ABDHPEJT) (CFLVMZOYQIRWUKXSG) (N) V
Course Info
Staff Beacon Resources Rotor
Rotor Rotor
(AEPLIYWCOXMRFZBSTGJQNH) (DV) (KU) J (AVOLDRWFIUQ)(BZKSMNHYC) (EGTJPX) Z
(AJQDVLEOZWIYTS) (CGMNHFUX) (BPRK) (ANOUPFRIMBZTLWKSVEGCJYDHXQ)
(AFLSETWUNDHOZVICQ) (BKJ) (GXY) (MPR)
(ALBEVFCYODJWUGNMQTZSKPR) (HIX)
(AFNIRLBSQWVXGUZDKMTPCOYJHE)
(AE) (BN) (CK) (DQ) (FU) (GY) (HW) (IJ) (LO) (MP) (RX) (SZ) (TV)
(AR) (BD) (CO) (EJ) (FN) (GT) (HK) (IV) (LM) (PW) (QZ) (SX) (UY)
Rotor Gamma
Reflector B Reflector C
Figure 2. The rotors used in the Naval Enigma, showing the permutations they implement and the point(s) at which there are notches that allow their left neighbor rotor to advance. Thus, when Rotor I is at ‘Q’ and the machine advances, the rotor to the left of Rotor I will advance. The Beta and Gamma rotors and the reflectors do not rotate. The reflectors shown here are the “thin” versions of the reflectors used in the naval M4 Enigma machine. The B reflector together with the Beta rotor in the ‘A’ position had the same effect as the usual (“thick”) B reflector in the older three-rotor M3 Enigma machine (likewise the C reflector with the Gamma rotor). This allowed the M4 to encrypt and decrypt messages to and from M3 Enigmas. Source: ‘s pages.
As an example of a translation, consider the set of rotors from Figure 2, and suppose that
The rotors in positions 1–5 are, respectively, B, Beta, III, IV, and I.
The rotors in positions 2–5 are currently at positions A, X, L, E, respectively.
In the plugboard, the letter pair ‘Y’ and ‘F’ and the letter pair ‘Z’ and ‘H’ are both interchanged.
We input the letter ‘Y’, which causes the following steps:
1. The pawls all move. This causes rotor 5 to advance from E to F. The other two pawls are not over notches, so rotors 3 and 4 do not move.
2. The letter ‘Y’ enters the plugboard and is converted to ‘F’.
Navigation
Introduction
Background
Describing Permutations
Input and Output
Editing Main
Handling Errors
Writing Unit Tests & Integration Tests
Running Enigma in IntelliJ
Comparing with the Staff Solution
Extra Credit Office Hours Checkpoint What To Turn In Grading Details Advice Common Bugs
https://inst.eecs.berkeley.edu/~cs61b/fa21/materials/proj/proj1/index.html

10/28/21, 8:21 PM
Project 1 | CS 61B Fall 2021
3. The letter ‘F’ enters the right side of rotor 5 (an I rotor) at position 5, since ‘F’ is
Course Info Staff Beacon Resources Piazza
the 5th letter of the alphabet numbering from 0. Since the current setting of rotor 5 is ‘F’, the signal enters the rotor at position , but hits contact , or ‘K’.
4. According to Figure 2, rotor I converts ‘K’ to ‘N’ (letter number 13). Because the setting of rotor I is ‘F’, however, the signal actually comes out at letter

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts