” COMP 250程序 写作、 辅导Java程序Assignment 2COMP 250 Winter 2021posted: Saturday, Feb. 20, 2021due: Sunday, Mar. 14, 2021 at 23:59General Instructions Submission instructions Late assignments will be accepted up to 2 days late and will be penalized by 10 points perday. Note that submitting one minute late is the same as submitting 23 hours late. Wewill 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 submittedor any other reason. This policy will hold regardless of whether or not the student canprovide proof that the assignment was indeed done on time. Dont worry if you realize that you made a mistake after you submitted : you can submitmultiple times but only the latest submission will be kept. We encourage you to submita first version a few days before the deadline (computer crashes do happen and codePostmay be overloaded during Rush hours). These are the files you should be submitting on codePost: Deck.java SolitaireCipher.javaDo not submit any other files, especially .class files. Any deviation from theserequirements 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 whereinstructed, namely in the ADD CODE HERE block. You may add helper methodsas long as you keep them private. The assignment shall be graded automatically. Requests to evaluate the assignment manuallyshall not be entertained, so please make sure that you follow the instructions closely or yourcode may fail to pass the automatic tests. Note that for this assignment, you are NOT allowedto import any other class, beside those already imported for you in the starter code. Anyfailure 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 codefails those tests, it means that there is a mistake somewhere. Even if your code passes thosetests, it may still contain some errors. We will test your code on a much more challenging set1of examples. We highly encourage you to test your code thoroughly before submitting yourfinal version. Later next week we will also post a Minitester class that you can run to test if your methodsare correct. This class will be equivalent to the exposed tests on codePost. Please note thatthese tests are only a Subset of what we will be running on your submissions. We encourageyou modify and expand this class. You are welcome to share your tester code with otherstudents on Piazza. Try to identify tricky cases. Do not hand in your tester code. Note thatyour code will be tested on valid inputs only. Later next week we will also provide a table indicating how many points will be assigned toeach 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 toyou to clarify it by asking either directly a TA during office hours, or on the discussion boardon Piazza.Learning ObjectivesThere are several learning goals for this assignment.First, you will get some exposure to some simple cryptography. Well introduce the idea behindone-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 willimplement a data structure to represent a deck of cards. This data structure is implemented as acircular doubly linked list.Third, in this assignment we will start to focus also on the efficiency of your algorithms. You willlearn to look at code with a more critical eye, without only focusing on the correctness of yourmethods.Lastly, this assignment will also give you more practice programming in Java! Although COMP250 is not a course about how to program, programming is a core part of computer science and themore practice you get, the better you will become at it.IntroductionIn 1917, Vernam patented a cipher now called one-time pad encryption scheme. The point of anencryption 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 isthat given a plaintext message of length n, a uniformly random stream of digits of length n (whichis the key) is generated and then used to encode the message. The message is concealed by replacingeach character in the plaintext, with a character obtained combining the original one with one of thedigits in the given key. Of Course the message can be retrieved by performing the inverse operation2on the characters of the encoded message (the ciphertext). Only those with access to the key canencode 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 thatthe limitations of one-time-pad are inherent to the definition of perfect secrecy. This means that toovercome those limitations the security requirements have to be relaxed.Stream ciphers use the same idea of one-time pad encryption scheme except that a pseudorandomsequence of digits is used as the pad instead of a random one. The idea is to use what arecalled pseudorandom generators which given a smaller key can generate streams of pseudorandomdigits.In Neal Stephensons novel Cryptonomicon, two of the main characters are able to covertly communicatewith one another with a deck of playing cards and knowledge of the Solitaire encryptionalgorithm, which was created (in real life) by Bruce Schneier. The novel includes the description ofthe 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 deckof cards in its initial configuration. If two parties, Alice and Bob, share the same deck, followingthe Solitaire encryption algorithm they will be able to communicate by encoding and decodingmessages. Of course, the deck and its configuration (i.e. the key) has to be kept secret to achievesecrecy. To encode and decode messages, Alice and Bob use the deck to generate a pseudorandomkeystream which is then used as the pad.Encode/Decode with SolitaireGiven a message to encode, we need to first remove all nonletters and convert any lowercase lettersto uppercase. We then use the keystream of values and convert each letter to the letter obtainedby shifting the original one a certain number of positions to the right on the alphabet. This numberis 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 generatethe ciphertext, convert each letter to the letter obtained by shifting the original one the givennumber of positions to the left on the alphabet.For example, lets 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 thefollowing:ISTHATYOUBOBShe will then generate a keystream of 12 values. Well talk about the keystream generation in thenext section, so lets assume That the keystream is the following:11 9 23 7 10 25 11 11 7 8 9 31See httpss://en.wikipedia.org/wiki/Solitaire (cipher), or httpss://www.schneier.com/academic/solitaire/3Finally, she can generate the ciphertext by shifting each letter the appropriate number of positionsto 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:TBQOKSJZBJXEBob, upon receiving the message, will need to generate the keystream. If Alice and Bob shared thesame key and used it to generate the same number of pseudorandom values, then the keystreamgenerated in this moment by Bob will be equal to that used by Alice to encrypt the message. Alltheres left for Bob to do is convert all the letters by shifting them the appropriate number ofposition to the left.Generating a Keystream Using a Deck of CardsThe harder part of the Solitaire encryption algorithm is generating the keystream. The idea is touse a deck of playing cards plus two jokers (a red one and a black one). Each card is associated witha value which depends on its rank and its suit. Cards in order from Ace to King have value 1 to 13respectively. This value can increase by a multiple of 13 depending on the suit of the card. For thissection lets assume well 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 diamondshas value 18, and the Queen of spades has value 51. The jokers have a value that depends on thenumber of cards in the deck. If the deck has a total of 54 cards (the 52 playing cards plus the twojokers), then the jokers have value 53. If the deck has total of 28 cards, then the jokers have value27. That is, the jokers have both the same value and this value is equal to the total number ofcards in the deck minus one.The keystream values depend solely on the decks initial configuration. We will implement the deckas a circular doubly linked list with the cards as nodes. This means that the first card (the one onthe top of the deck) is linked to the last card (the one at the bottom of the deck) and the last cardis linked to the first one. As an Example, lets consider a deck with 28 cards: the 13 of both clubsand diamonds, plus the two jokers. Lets 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 KDThe cards are represented with their rank, followed by their suit. For example, 6C denotes the 6 ofclubs, 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 wayfor 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 KD2Note that this is the same example you find on the wikipedia page httpss://en.wikipedia.org/wiki/Solitaire (cipher) where instead of the cards, they list the values.42. Locate the black joker and move it two cards down. If the joker is the bottom card of thedeck, move it just below the second card. If the joker is one up from the bottom card, moveit 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 KD3. Perform a triple cut: that is, swap the cards above the first joker with the cards below thesecond joker. Note that here we use first and second joker to refer to whatever joker isnearest to, and furthest from, the top of the deck. Their colors do not matter. Note that thejokers and the cards between them do not move! If there are no cards in one of the threesections (either the jokers are adjacent, or one is on top or the bottom), just treat that sectionas 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 6C4. Perform a count cut: look at the value of the bottom card. Remove that number of cardsfrom the top of the deck and insert them just above the last card in the deck. The deck willnow 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 6C5. 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 keystreamalgorithm. 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 isa 10 of diamonds which has value 23. By counting down to the 24th card we find the Jackof clubs which has value 11. Hence, 11 would be the first keystream value generated by ourdeck.Instructions and Starter CodeAs mentioned in the section before we will use a circular doubly linked list to represent a deck ofcards. 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 classcontains three nested classes: Card, PlayingCard, and Joker. SolitaireCipher This class represents a stream cipher that uses the Solitaire algorithm togenerate the keystream and then encode/decode messages.Please note that we defined all the members of the classes public for testing purposes. In reality, forbetter coding style, most of those methods and all of the fields should have been kept private.Methods you need to implementFor this assignment you need to implement all of the methods listed below. See the starter codefor 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 fromAce to numOfCardsPerSuit for the first numOfSuits in the class field suitsInOrder. Thecards should be ordered first by suit, and then by rank. In addition to these cards, a red jokerand a black joker are added to the bottom of the deck in this order. For example, with input4 and 3, and suitsInOrder as specified in the file, the deck contains the following cards inthis specific order:AC 2C 3C 4C AD 2D 3D 4D AH 2H 3H 4H RJ BJThe constructor should raise an IllegalArgumentException if the first input is not a numberbetween 1 and 13 (both included) or the second input is not a number between 1 and the sizeof the class field suitsInOrder. Remember that a deck is a circular doubly linked list somake 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: usethe method getCopy from the class Card. Disclaimer: this is not the correct way of makinga deep copy of objects that contain circular references, but it is a simple one and good enoughfor our purposes. Deck.addCard(Card c) : adds the input card to the bottom of the deck. This method runsin O(1). Deck.shuffle() : shuffles the Deck. There are different ways of doing this, but for this assignmentyou will need to implement an algorithm that uses the FisherYates 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 doj — random integer such that 0 = j = iswap 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 thespecified color. This method runs in O(n). Deck.moveCard(Card c, int p) : moves the card c by p positions down the deck. You canassume 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 deckusing the two input cards. You can assume that the input cards belong to the deck and thefirst 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 thevalue of the bottom card modulo the total number of cards in the deck. Note that this meansthat 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 thevalue of the card on the top of the deck, and counting down that many cards. If the cardfound is a Joker, then the method returns null, otherwise it returns the card found. Thismethod runs in O(n). Deck.generateNextKeystreamValue() : uses the Solitaire algorithm to generate one valuefor 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 keystreamof 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 keystreamof the correct size and using it to Decode the message as described earlier in the pdf.Small exampleGenerate a deck of 12 cards as follows:AC 2C 3C 4C 5C AD 2D 3D 4D 5D RJ BJIf you seed the random generator using 10 as the seed, then after shuffling the deck once you willget the following configuration:3C 3D AD 5C BJ 2C 2D 4D AC RJ 4C 5DIf you were to use this deck to create a Solitaire cipher and you would try to encode the messageIs that you, Bob? you would get the ciphertext MWIKDVZCKSFP obtained using the followingkeystream:4 4 15 3 3 2 1 14 16 17 17 14Finally, note that the keystream used in the section describing how to encode/decode is thekeystream you would obtain using the deck from the example used on how to generate keystreamvalues.如有需要，请加QQ：99515681 或WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
