COMP 250程序代做、代写Java程序、Java编程代写调试

日期：2021-03-06 11:02

Assignment 2

COMP 250 Winter 2021

posted: Saturday, Feb. 20, 2021

due: Sunday, Mar. 14, 2021 at 23:59

General Instructions

? Submission instructions

– Late assignments will be accepted up to 2 days late and will be penalized by 10 points per

day. Note that submitting one minute late is the same as submitting 23 hours late. We

will deduct 10 points for any student who has to resubmit after the due date (i.e. late)

irrespective of the reason, be it wrong file submitted, wrong file format was submitted

or any other reason. This policy will hold regardless of whether or not the student can

provide proof that the assignment was indeed “done” on time.

– Don’t worry if you realize that you made a mistake after you submitted : you can submit

multiple times but only the latest submission will be kept. We encourage you to submit

a first version a few days before the deadline (computer crashes do happen and codePost

may be overloaded during rush hours).

– These are the files you should be submitting on codePost:

? Deck.java

? SolitaireCipher.java

Do not submit any other files, especially .class files. Any deviation from these

requirements may lead to lost marks

? Please note that the classes you submit should be part of a package called assignment2.

? Do not change any of the starter code that is given to you. Add code only where

instructed, namely in the “ADD CODE HERE” block. You may add helper methods

as long as you keep them private.

? The assignment shall be graded automatically. Requests to evaluate the assignment manually

shall not be entertained, so please make sure that you follow the instructions closely or your

code may fail to pass the automatic tests. Note that for this assignment, you are NOT allowed

to import any other class, beside those already imported for you in the starter code. Any

failure to comply with these rules will give you an automatic 0.

? Whenever you submit your files to codepost, you will see the results of some exposed tests.

These tests are a mini version of the tests we will be using to grade your work. If your code

fails those tests, it means that there is a mistake somewhere. Even if your code passes those

tests, it may still contain some errors. We will test your code on a much more challenging set

1

of examples. We highly encourage you to test your code thoroughly before submitting your

final version.

? Later next week we will also post a Minitester class that you can run to test if your methods

are correct. This class will be equivalent to the exposed tests on codePost. Please note that

these tests are only a subset of what we will be running on your submissions. We encourage

you modify and expand this class. You are welcome to share your tester code with other

students on Piazza. Try to identify tricky cases. Do not hand in your tester code. Note that

your code will be tested on valid inputs only.

? Later next week we will also provide a table indicating how many points will be assigned to

each method.

? You will automatically get 0 if your code does not compile.

? Failure to comply with any of these rules will be penalized. If anything is unclear, it is up to

you to clarify it by asking either directly a TA during office hours, or on the discussion board

on Piazza.

Learning Objectives

There are several learning goals for this assignment.

First, you will get some exposure to some simple cryptography. We’ll introduce the idea behind

one-time pad and you will implement an example of a stream cipher.

Second, in this assignment you will also get some experience working with linked lists. You will

implement a data structure to represent a deck of cards. This data structure is implemented as a

circular doubly linked list.

Third, in this assignment we will start to focus also on the efficiency of your algorithms. You will

learn to look at code with a more critical eye, without only focusing on the correctness of your

methods.

Lastly, this assignment will also give you more practice programming in Java! Although COMP

250 is not a course about how to program, programming is a core part of computer science and the

more practice you get, the better you will become at it.

Introduction

In 1917, Vernam patented a cipher now called one-time pad encryption scheme. The point of an

encryption scheme is to transform a message so that only those authorized will be able to read it.

One-time pad was later (in 1949) proved to be perfectly secret. The idea behind one-time pad is

that given a plaintext message of length n, a uniformly random stream of digits of length n (which

is the key) is generated and then used to encode the message. The message is concealed by replacing

each character in the plaintext, with a character obtained combining the original one with one of the

digits in the given key. Of course the message can be retrieved by performing the inverse operation

2

on the characters of the encoded message (the ciphertext). Only those with access to the key can

encode and decode a message. One-time pad is perfectly secret, but it has a number of drawbacks:

for it to be secure, the key is required to be as long as the message, and it can only be used once!

This clearly makes the cipher not a convenient one to use. Unfortunately, it was also proven that

the limitations of one-time-pad are inherent to the definition of perfect secrecy. This means that to

overcome those limitations the security requirements have to be relaxed.

Stream ciphers use the same idea of one-time pad encryption scheme except that a pseudorandom

sequence of digits is used as the pad instead of a random one. The idea is to use what are

called ‘pseudorandom generators’ which given a smaller key can generate streams of pseudorandom

digits.

In Neal Stephenson’s novel Cryptonomicon, two of the main characters are able to covertly communicate

with one another with a deck of playing cards and knowledge of the Solitaire encryption

algorithm, which was created (in real life) by Bruce Schneier. The novel includes the description of

the algorithm, but you can also find a revised version on the web1

.

The Solitaire encryption algorithm is an example of a stream cipher. The key in this case is the deck

of cards in its initial configuration. If two parties, Alice and Bob, share the same deck, following

the Solitaire encryption algorithm they will be able to communicate by encoding and decoding

messages. Of course, the deck and its configuration (i.e. the key) has to be kept secret to achieve

secrecy. To encode and decode messages, Alice and Bob use the deck to generate a pseudorandom

keystream which is then used as the “pad”.

Encode/Decode with Solitaire

Given a message to encode, we need to first remove all non–letters and convert any lower–case letters

to upper–case. We then use the keystream of values and convert each letter to the letter obtained

by shifting the original one a certain number of positions to the right on the alphabet. This number

is the one found in the keystream in the same position as the character we are encoding.

Decryption is just the reverse of encryption. Using the same keystream that was used to generate

the ciphertext, convert each letter to the letter obtained by shifting the original one the given

number of positions to the left on the alphabet.

For example, let’s say that Alice wants to send the following message:

Is that you, Bob?

Then she will first remove all the non-letters and capitalize all the remaining ones obtaining the

following:

ISTHATYOUBOB

She will then generate a keystream of 12 values. We’ll talk about the keystream generation in the

next section, so let’s assume that the keystream is the following:

11 9 23 7 10 25 11 11 7 8 9 3

1See https://en.wikipedia.org/wiki/Solitaire (cipher), or https://www.schneier.com/academic/solitaire/

3

Finally, she can generate the ciphertext by shifting each letter the appropriate number of positions

to the right in the alphabet. For example, the ‘I’ shifted 11 positions to the right, becomes a ‘T’.

The ‘S’ shifted 9 positions to the right becomes a ‘B’. And so on! The final ciphertext will be:

TBQOKSJZBJXE

Bob, upon receiving the message, will need to generate the keystream. If Alice and Bob shared the

same key and used it to generate the same number of pseudorandom values, then the keystream

generated in this moment by Bob will be equal to that used by Alice to encrypt the message. All

there’s left for Bob to do is convert all the letters by shifting them the appropriate number of

position to the left.

Generating a Keystream Using a Deck of Cards

The harder part of the Solitaire encryption algorithm is generating the keystream. The idea is to

use a deck of playing cards plus two jokers (a red one and a black one). Each card is associated with

a value which depends on its rank and its suit. Cards in order from Ace to King have value 1 to 13

respectively. This value can increase by a multiple of 13 depending on the suit of the card. For this

section let’s assume we’ll use the Bridge ranking for suits: clubs (lowest), followed by diamonds,

hearts, and spades (highest). So, for instance, the Ace of clubs has value 1, while the 5 of diamonds

has value 18, and the Queen of spades has value 51. The jokers have a value that depends on the

number of cards in the deck. If the deck has a total of 54 cards (the 52 playing cards plus the two

jokers), then the jokers have value 53. If the deck has total of 28 cards, then the jokers have value

27. That is, the jokers have both the same value and this value is equal to the total number of

cards in the deck minus one.

The keystream values depend solely on the deck’s initial configuration. We will implement the deck

as a circular doubly linked list with the cards as nodes. This means that the first card (the one on

the top of the deck) is linked to the last card (the one at the bottom of the deck) and the last card

is linked to the first one. As an example, let’s consider a deck with 28 cards: the 13 of both clubs

and diamonds, plus the two jokers. Let’s also consider the following initial configuration2

:

AC 4C 7C 10C KC 3D 6D 9D QD BJ 3C 6C 9C QC 2D 5D 8D JD RJ 2C 5C 8C JC AD 4D 7D 10D KD

The cards are represented with their rank, followed by their suit. For example, 6C denotes the 6 of

clubs, JD the Jack of diamonds, and RJ the red joker.

Here are the steps to take to generate one value of the keystream:

1. Locate the red joker and move it one card down. (That is, swap it with the card beneath it.)

If the joker is the bottom card of the deck, move it just below the top card. There is no way

for it to become the first card. After this step, the deck above will look as follows:

AC 4C 7C 10C KC 3D 6D 9D QD BJ 3C 6C 9C QC 2D 5D 8D JD 2C RJ 5C 8C JC AD 4D 7D 10D KD

2Note that this is the same example you find on the wikipedia page

https://en.wikipedia.org/wiki/Solitaire (cipher) where instead of the cards, they list the values.

4

2. Locate the black joker and move it two cards down. If the joker is the bottom card of the

deck, move it just below the second card. If the joker is one up from the bottom card, move

it just below the top card. There is no way for it to become the first card. After this step,

the deck above will look as follows:

AC 4C 7C 10C KC 3D 6D 9D QD 3C 6C BJ 9C QC 2D 5D 8D JD 2C RJ 5C 8C JC AD 4D 7D 10D KD

3. Perform a “triple cut”: that is, swap the cards above the first joker with the cards below the

second joker. Note that here we use “first” and “second” joker to refer to whatever joker is

nearest to, and furthest from, the top of the deck. Their colors do not matter. Note that the

jokers and the cards between them do not move! If there are no cards in one of the three

sections (either the jokers are adjacent, or one is on top or the bottom), just treat that section

as empty and move it anyway. The deck will now look as follows:

5C 8C JC AD 4D 7D 10D KD BJ 9C QC 2D 5D 8D JD 2C RJ AC 4C 7C 10C KC 3D 6D 9D QD 3C 6C

4. Perform a “count cut”: look at the value of the bottom card. Remove that number of cards

from the top of the deck and insert them just above the last card in the deck. The deck will

now look as follows:

10D KD BJ 9C QC 2D 5D 8D JD 2C RJ AC 4C 7C 10C KC 3D 6D 9D QD 3C 5C 8C JC AD 4D 7D 6C

5. Finally, look at the value of the card on the top of the deck. Count down that many cards.

(Count the top card as number one.) If you hit a joker, ignore it and repeat the keystream

algorithm. Otherwise, use the value of the card you counted to as the next keystream value.

Note that this step does not modify the state of the deck. In our example, the top card is

a 10 of diamonds which has value 23. By counting down to the 24th card we find the Jack

of clubs which has value 11. Hence, 11 would be the first keystream value generated by our

deck.

Instructions and Starter Code

As mentioned in the section before we will use a circular doubly linked list to represent a deck of

cards. The starter code contains two files with five classes which are as follows:

? Deck - This class defines a deck of cards. Most of your work goes into this file. This class

contains three nested classes: Card, PlayingCard, and Joker.

? SolitaireCipher – This class represents a stream cipher that uses the Solitaire algorithm to

generate the keystream and then encode/decode messages.

Please note that we defined all the members of the classes public for testing purposes. In reality, for

better coding style, most of those methods and all of the fields should have been kept private.

Methods you need to implement

For this assignment you need to implement all of the methods listed below. See the starter code

for the full method signatures. Your implementations must be efficient. For each method below,

we indicate the worst case run time using O() notation.

5

? Deck.Deck(int numOfCardsPerSuit, int numOfSuits) : creates a deck with cards from

Ace to numOfCardsPerSuit for the first numOfSuits in the class field suitsInOrder. The

cards should be ordered first by suit, and then by rank. In addition to these cards, a red joker

and a black joker are added to the bottom of the deck in this order. For example, with input

4 and 3, and suitsInOrder as specified in the file, the deck contains the following cards in

this specific order:

AC 2C 3C 4C AD 2D 3D 4D AH 2H 3H 4H RJ BJ

The constructor should raise an IllegalArgumentException if the first input is not a number

between 1 and 13 (both included) or the second input is not a number between 1 and the size

of the class field suitsInOrder. Remember that a deck is a circular doubly linked list so

make sure to set up all the pointers correctly, as well as the instance fields.

? Deck.Deck(Deck d) : creates a deck by making a deep copy of the input deck. Hint: use

the method getCopy from the class Card. Disclaimer: this is not the correct way of making

a deep copy of objects that contain circular references, but it is a simple one and good enough

for our purposes.

? Deck.addCard(Card c) : adds the input card to the bottom of the deck. This method runs

in O(1).

? Deck.shuffle() : shuffles the deck. There are different ways of doing this, but for this assignment

you will need to implement an algorithm that uses the Fisher–Yates shuffle algorithm.

The algorithm runs in O(n) using O(n) space, where n is the number of cards in the deck.

To perform a shuffle of the deck follow the steps:

– Copy all the cards inside an array

– Shuffle the array using the following algorithm:

for i from n-1 to 1 do

j <-- random integer such that 0 <= j <= i

swap a[j] and a[i]

To generate a random integer use the Random object stored in the class field called gen.

– Use the array to rebuild the shuffled deck.

? Deck.locateJoker(String color) : returns a reference to the joker in the deck with the

specified color. This method runs in O(n).

? Deck.moveCard(Card c, int p) : moves the card c by p positions down the deck. You can

assume that the input card belongs to the deck (which implies that the deck is not empty).

This method runs in O(p).

? Deck.tripleCut(Card firstCard, Card secondCard) : performs a triple cut on the deck

using the two input cards. You can assume that the input cards belong to the deck and the

first one is nearest to the top of the deck. This method runs in O(1).

6

? Deck.countCut() : performs a count cut on the deck. The number used for the cut is the

value of the bottom card modulo the total number of cards in the deck. Note that this means

that if the value of the bottom card is equal to a multiple of the number of cards in the deck,

then the method should not do anything. This method runs in O(n).

? Deck.lookUpCard() : returns a reference to the card that can be found by looking at the

value of the card on the top of the deck, and counting down that many cards. If the card

found is a Joker, then the method returns null, otherwise it returns the card found. This

method runs in O(n).

? Deck.generateNextKeystreamValue() : uses the Solitaire algorithm to generate one value

for the keystream using this deck. This method runs in O(n).

? SolitaireCipher.getKeystream(int size) : generates a keystream of the given size.

? SolitaireCipher.encode(String msg) : encodes the input message by generating a keystream

of the correct size and using it to encode the message as described earlier in the pdf.

? SolitaireCipher.decode(String msg) : decodes the input message by generating a keystream

of the correct size and using it to decode the message as described earlier in the pdf.

Small example

Generate a deck of 12 cards as follows:

AC 2C 3C 4C 5C AD 2D 3D 4D 5D RJ BJ

If you seed the random generator using 10 as the seed, then after shuffling the deck once you will

get the following configuration:

3C 3D AD 5C BJ 2C 2D 4D AC RJ 4C 5D

If you were to use this deck to create a Solitaire cipher and you would try to encode the message

"Is that you, Bob?" you would get the ciphertext MWIKDVZCKSFP obtained using the following

keystream:

4 4 15 3 3 2 1 14 16 17 17 14

Finally, note that the keystream used in the section describing how to encode/decode is the

keystream you would obtain using the deck from the example used on how to generate keystream

values.

7