Need help with this Java assignment!

Background In Neal Stephenson's novel Cryptonomicon, two of the main characters covertly communicate with one another with a deck of playing cards (including the Jokers) using the knowledge of an encryption algorithm, developed, in real life, by security technologist Bruce Schneier. If you are interested in learning more about the algorithm, Schneier wrote a blog post- detailing its security implications and general cryptographer best practices. The idea is that you might want to write secret messages without having access to a computer, and a deck of cards is inconspicuous enough not be looked at too closely if you're apprehended by the bad guys. For this assignment, we simplify the algorithm in several ways. First, we assume that we're only using only two suits (say, Hearts and Spades) from a deck of cards, plus the two Jokers. Furthermore, we assume that the values of the 26 suit cards are 1 to 26 (Ace to King of Hearts, followed by Ace to King of Spades), that the A Joker is 27, and that the B Joker is 28. Thus, 15 represents the 2 of spades. Now that you've got the idea, we can represent each card as a number between 1 and 28 (only because we're programming this on a computer). Generating Keystream Values In cryptography, a keystream is a stream of random or pseudorandom values (whether bits, bytes, numbers, or actual letters) that are combined with the plaintext message to produce the ciphertext (the encrypted message). If we start with a list of values from 1 to 28 (as described above), the steps to generate the keystream are: 1. Find the A Joker (27). Swap Joker A with the card beneath (after) it in the deck. (What if the Joker is the last card in the deck? You can imagine that the deck of cards as continuous (the card following the bottom card is the top card of the deck) so you would swap them as usual.) 2. Find the "B" Joker (28). Move Joker B two cards down by performing two swaps. 3. Perform a triple cut. Take all the cards above the first Joker (the one closest to the top of 1 http://www.schneier.com/solitaire.html 1 the deck; "A" and "B" don't matter in this step.) and swap it with all the cards below the second Joker. 4. Remove the bottom card from the deck. Count down from the top card by a quantity of cards equal to the value of that bottom card. (If the bottom card is one of the Jokers, let its value be 27.) Take that group of cards and move them to the bottom of the deck. Return the bottom card to the bottom of the deck. 5. Look at the top card's value. Keep it at the top of the deck. Count down the deck by that many cards. Record the value of the next card in the deck, but don't remove it from the deck. If the next card is a Joker, don't record anything, and start again from the first step. Repeating until the next card is not a joker. The recorded value in the last step is one value of the keystream, and will be in the range 1- 26, inclusive (to match with the number of letters in the alphabet). To generate another value, we take the deck as it is after the last step and repeat the algorithm. We need to generate as many keystream values as there are letters in the message being encrypted or decrypted. Example Assume that this is the original ordering of our half-deck of cards: 14 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 27 2 5 8 11 14 17 20 23 26 Step 1 Swap 27 with the card after it. So, we swap 27 and 2: 14 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 2 27 5 8 11 14 17 20 23 26 Step 2 Swap 28 with the card after it twice. 14 7 10 13 16 19 22 25 3 6 28 9 12 15 18 21 24 2275 8 11 14 17 20 23 26 Step 3 Perform a triple cut. Swap the cards before the first Joker (28, in this case) with the ones after the second Joker (27, in this case): 5 8 11 14 17 20 23 26 28 9 12 15 18 21 24 2 27 14 7 10 13 16 19 22 25 36 Step 4 The last card's value is 6. Remove the last card. Move the first 6 cards to the end. Replace the removed card. 23 26 28 9 12 15 18 21 242 27 1 4 7 10 13 16 19 22 25 358 11 14 17 20 6 Step 5 The first card's value is 23. The next card after the 230 card is 11. This is the first keystream value. 2 23 26 28 9 12 15 18 21 242 27 1 4 7 10 13 16 19 22 25 358 11 14 17 20 6 Checkpoint: What is the next keystream value? (The answer is at the end of assignment.) Encryption and Decryption What you do with the generated keystream values depends on whether you are encoding or decoding a message. But the sender and recipient must have a deck in the same initial configuration. Either they memorized it or know an algorithm for generating the initial configuration. Encryption To encode a message with Solitaire, remove all non-alphabetical characters and capitalize everything. (If you wanted to follow traditional cryptographic practices, you would also divide the letters into groups of five.) Then, convert the letters to their corresponding numerical representation (A=1, B=2, etc.). Use Solitaire to generate keystream values the same length as the message. Add the corresponding pairs of numbers, modulo 26. Convert the numbers back to letters. Example Plaintext message: The Spy Museum in D.C. is cool. Removing the non-alphabetical characters and capitalizing: THESPYMUSEUMINDCISCOOL The message is 22 characters long, so we need to pad the message with a filler character, say "X", to make the message a multiple of 5. Now, we can convert the letters to numbers: N 0 T 20 HE S PYM 8 5 19 16 25 13 S EUM 21 19 5 21 13 9 DCI 439 SC O 19 315 24 24 24 14 15 12 Assume that we generated the following 25 keystream values: 21 6 2 19 15 18 12 23 2351714 6 13 1 26 16 12 20 9 17 21 12 4 To add the two groups of numbers together pairwise, modulo 26, just subtract 26 from the sum if it is greater than 26. (Note that the % operator in Java won't quite give the correct results. Why?) The top row is our converted message, the middle row is our keystream, and the last row is after adding: 2 The next keystream value is 9. This makes it so ostensibly an adversary can't use anything about the message length to figure out what the actual message. 3 20 8 5 19 16 25 13 21 19 5 21 13 9 14 4 3 9 19 3 15 15 12 24 24 24 24 21 6 2 19 15 18 12 23 23 5 1 7 14 6 13 1 26 16 12 20 9 17 21 12 4 15 14 7 12 5 17 25 18 16 10 22 20 23 20 17 4 9 9 15 25 24 3 19 10 2 Finally, convert back to letters: ONGLEQYRPJVTWTQDIIOYXCSJB Decryption The recipient can decrypt the ciphertext by reversing the encryption process. First, convert the encrypted message's letters to numbers, generate the same keystream (by starting with the same initial deck ordering as was used for the encryption), and subtract the keystream values from the message numbers. If the message value is equal to or smaller than the keystream value, add 26 to it before subtracting the pair. 15 14 7 12 5 17 25 18 16 10 22 20 23 20 17 4 9 9 15 25 24 3 19 10 21 6 2 19 15 18 12 23 23 5 12 23 23 5 1 7 14 6 13 1 26 16 12 20 9 17 21 12 208 5 19 16 25 13 21 19 5 21 13 9 14 4 3 9 19 3 15 3 15 15 12 24 24 2 4 24 Finally, convert the numbers back to letters: 20 8 5 19 16 25 13 21 19 5 21 13 9 14 4 3 9 19 3 15 15 12 24 12 24 24 24 THE SPYMUS EU MONDCISCO OLX X Assignment Use CircularLinkedList.java as the starting point for your program to read in a "deck" of 28 numbers (from a file, from a command line, or an array. Dealer's choice!). It should ask the user if they want to encrypt or decrypt. Then, ask the user for one or more messages. Finally, your program should then use the Solitaire algorithm described about to perform the requested action and output the results. Note that if your program is decrypting multiple messages, all but the first should be encrypted/ decrypted using the deck as it exists after the decryption of the previous message. (The first uses the deck provided, of course.) Additional Hints Start early! There are lots of little things that need to be done to write this program. Make sure that you understand the Solitaire algorithm before you start writing the program; you can't write a program to solve a problem you don't understand. Don't try to write the whole program at once; start small. For example, complete the add method first, then test it. Then move on to remove after you confirm it's working. You can check your program's work by hand. Take the data file, manually generate the first few keystream letters, and check that your program generated the same ones. Create some encrypted messages for your program to decrypt. Write an encoding method for your program. 4 . Exchange encrypted messages with your classmates. Why? If you only test with your own encryption and decryption routines, any logical error with the algorithm implementation is likely to appear in both routines. With-out independent verification, you may think that your logically flawed code is correct. Each of the steps of the encryption algorithm are actually very simple. If you need to do something complicated, like it in Step 3, think about how you can break your linked list into new, temporary, smaller linked lists and recombine them! Background In Neal Stephenson's novel Cryptonomicon, two of the main characters covertly communicate with one another with a deck of playing cards (including the Jokers) using the knowledge of an encryption algorithm, developed, in real life, by security technologist Bruce Schneier. If you are interested in learning more about the algorithm, Schneier wrote a blog post- detailing its security implications and general cryptographer best practices. The idea is that you might want to write secret messages without having access to a computer, and a deck of cards is inconspicuous enough not be looked at too closely if you're apprehended by the bad guys. For this assignment, we simplify the algorithm in several ways. First, we assume that we're only using only two suits (say, Hearts and Spades) from a deck of cards, plus the two Jokers. Furthermore, we assume that the values of the 26 suit cards are 1 to 26 (Ace to King of Hearts, followed by Ace to King of Spades), that the A Joker is 27, and that the B Joker is 28. Thus, 15 represents the 2 of spades. Now that you've got the idea, we can represent each card as a number between 1 and 28 (only because we're programming this on a computer). Generating Keystream Values In cryptography, a keystream is a stream of random or pseudorandom values (whether bits, bytes, numbers, or actual letters) that are combined with the plaintext message to produce the ciphertext (the encrypted message). If we start with a list of values from 1 to 28 (as described above), the steps to generate the keystream are: 1. Find the A Joker (27). Swap Joker A with the card beneath (after) it in the deck. (What if the Joker is the last card in the deck? You can imagine that the deck of cards as continuous (the card following the bottom card is the top card of the deck) so you would swap them as usual.) 2. Find the "B" Joker (28). Move Joker B two cards down by performing two swaps. 3. Perform a triple cut. Take all the cards above the first Joker (the one closest to the top of 1 http://www.schneier.com/solitaire.html 1 the deck; "A" and "B" don't matter in this step.) and swap it with all the cards below the second Joker. 4. Remove the bottom card from the deck. Count down from the top card by a quantity of cards equal to the value of that bottom card. (If the bottom card is one of the Jokers, let its value be 27.) Take that group of cards and move them to the bottom of the deck. Return the bottom card to the bottom of the deck. 5. Look at the top card's value. Keep it at the top of the deck. Count down the deck by that many cards. Record the value of the next card in the deck, but don't remove it from the deck. If the next card is a Joker, don't record anything, and start again from the first step. Repeating until the next card is not a joker. The recorded value in the last step is one value of the keystream, and will be in the range 1- 26, inclusive (to match with the number of letters in the alphabet). To generate another value, we take the deck as it is after the last step and repeat the algorithm. We need to generate as many keystream values as there are letters in the message being encrypted or decrypted. Example Assume that this is the original ordering of our half-deck of cards: 14 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 27 2 5 8 11 14 17 20 23 26 Step 1 Swap 27 with the card after it. So, we swap 27 and 2: 14 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 2 27 5 8 11 14 17 20 23 26 Step 2 Swap 28 with the card after it twice. 14 7 10 13 16 19 22 25 3 6 28 9 12 15 18 21 24 2275 8 11 14 17 20 23 26 Step 3 Perform a triple cut. Swap the cards before the first Joker (28, in this case) with the ones after the second Joker (27, in this case): 5 8 11 14 17 20 23 26 28 9 12 15 18 21 24 2 27 14 7 10 13 16 19 22 25 36 Step 4 The last card's value is 6. Remove the last card. Move the first 6 cards to the end. Replace the removed card. 23 26 28 9 12 15 18 21 242 27 1 4 7 10 13 16 19 22 25 358 11 14 17 20 6 Step 5 The first card's value is 23. The next card after the 230 card is 11. This is the first keystream value. 2 23 26 28 9 12 15 18 21 242 27 1 4 7 10 13 16 19 22 25 358 11 14 17 20 6 Checkpoint: What is the next keystream value? (The answer is at the end of assignment.) Encryption and Decryption What you do with the generated keystream values depends on whether you are encoding or decoding a message. But the sender and recipient must have a deck in the same initial configuration. Either they memorized it or know an algorithm for generating the initial configuration. Encryption To encode a message with Solitaire, remove all non-alphabetical characters and capitalize everything. (If you wanted to follow traditional cryptographic practices, you would also divide the letters into groups of five.) Then, convert the letters to their corresponding numerical representation (A=1, B=2, etc.). Use Solitaire to generate keystream values the same length as the message. Add the corresponding pairs of numbers, modulo 26. Convert the numbers back to letters. Example Plaintext message: The Spy Museum in D.C. is cool. Removing the non-alphabetical characters and capitalizing: THESPYMUSEUMINDCISCOOL The message is 22 characters long, so we need to pad the message with a filler character, say "X", to make the message a multiple of 5. Now, we can convert the letters to numbers: N 0 T 20 HE S PYM 8 5 19 16 25 13 S EUM 21 19 5 21 13 9 DCI 439 SC O 19 315 24 24 24 14 15 12 Assume that we generated the following 25 keystream values: 21 6 2 19 15 18 12 23 2351714 6 13 1 26 16 12 20 9 17 21 12 4 To add the two groups of numbers together pairwise, modulo 26, just subtract 26 from the sum if it is greater than 26. (Note that the % operator in Java won't quite give the correct results. Why?) The top row is our converted message, the middle row is our keystream, and the last row is after adding: 2 The next keystream value is 9. This makes it so ostensibly an adversary can't use anything about the message length to figure out what the actual message. 3 20 8 5 19 16 25 13 21 19 5 21 13 9 14 4 3 9 19 3 15 15 12 24 24 24 24 21 6 2 19 15 18 12 23 23 5 1 7 14 6 13 1 26 16 12 20 9 17 21 12 4 15 14 7 12 5 17 25 18 16 10 22 20 23 20 17 4 9 9 15 25 24 3 19 10 2 Finally, convert back to letters: ONGLEQYRPJVTWTQDIIOYXCSJB Decryption The recipient can decrypt the ciphertext by reversing the encryption process. First, convert the encrypted message's letters to numbers, generate the same keystream (by starting with the same initial deck ordering as was used for the encryption), and subtract the keystream values from the message numbers. If the message value is equal to or smaller than the keystream value, add 26 to it before subtracting the pair. 15 14 7 12 5 17 25 18 16 10 22 20 23 20 17 4 9 9 15 25 24 3 19 10 21 6 2 19 15 18 12 23 23 5 12 23 23 5 1 7 14 6 13 1 26 16 12 20 9 17 21 12 208 5 19 16 25 13 21 19 5 21 13 9 14 4 3 9 19 3 15 3 15 15 12 24 24 2 4 24 Finally, convert the numbers back to letters: 20 8 5 19 16 25 13 21 19 5 21 13 9 14 4 3 9 19 3 15 15 12 24 12 24 24 24 THE SPYMUS EU MONDCISCO OLX X Assignment Use CircularLinkedList.java as the starting point for your program to read in a "deck" of 28 numbers (from a file, from a command line, or an array. Dealer's choice!). It should ask the user if they want to encrypt or decrypt. Then, ask the user for one or more messages. Finally, your program should then use the Solitaire algorithm described about to perform the requested action and output the results. Note that if your program is decrypting multiple messages, all but the first should be encrypted/ decrypted using the deck as it exists after the decryption of the previous message. (The first uses the deck provided, of course.) Additional Hints Start early! There are lots of little things that need to be done to write this program. Make sure that you understand the Solitaire algorithm before you start writing the program; you can't write a program to solve a problem you don't understand. Don't try to write the whole program at once; start small. For example, complete the add method first, then test it. Then move on to remove after you confirm it's working. You can check your program's work by hand. Take the data file, manually generate the first few keystream letters, and check that your program generated the same ones. Create some encrypted messages for your program to decrypt. Write an encoding method for your program. 4 . Exchange encrypted messages with your classmates. Why? If you only test with your own encryption and decryption routines, any logical error with the algorithm implementation is likely to appear in both routines. With-out independent verification, you may think that your logically flawed code is correct. Each of the steps of the encryption algorithm are actually very simple. If you need to do something complicated, like it in Step 3, think about how you can break your linked list into new, temporary, smaller linked lists and recombine them