Chris Pollett > Old Classes > CS166
( Print View )

Student Corner:
  [Grades Sec3]

  [Submit Sec3]

  [Class Sign Up Sec3]

  [
Lecture Notes]
  [Discussion Board]

Course Info:
  [Texts & Links]
  [Topics/Outcomes]
  [Outcomes Matrix]
  [Grading]
  [HW/Quiz Info]
  [Exam Info]
  [Regrades]
  [Honesty]
  [Additional Policies]
  [Announcements]

HW Assignments:
  [Hw1]  [Hw2]  [Hw3]
  [Hw4]  [Quizzes]

Practice Exams:
  [Mid 1]  [Mid 2]  [Final]

                           












HW#1 --- last modified February 07 2019 15:05:23..

Solution set.

Due date: Sep 12

Files to be submitted:
  Hw1.zip

Purpose:To start thinking about issues in information security. To implement some classic cipher algorithms.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO1 (Learning Outcome 1) -- Understand the basics concepts of cryptography as illustrated by a classic cipher system such as the simple substitution or double transposition; demonstrate an elementary cryptanalytic attack on such a system and quantify the expected work factor.

LO2 -- Understand the implementation of modern symmetric ciphers such as RC4, DES and TEA; understand public key cryptosystems such as RSA, Diffie-Hellman and the knapsack; understand the implementation of a hash function, such as Tiger.

Specification:

This homework consists of two parts: A set of book problems, which are to be done individually, should be handwritten (no typing), and must be turned in at the start of class on the day indicated; a coding assignment, which can be done in a team of at most three people. For the coding portion only one team member needs to submit -- just be sure to mention the names of your teammates in the documentation for your code.

The book problems I want you to do are: Ch 1, Exercise 5 and 11 (due Aug. 29); Ch 2, Exercise 5 and 23 (due Sep. 5); Ch3, Exercise 4 and 7 (due Sep 12). One problem each week will be graded and it will be worth up to 1pt. The score given will be one the following: 0 (incorrect answer or insufficient justification), 0.5 (incorrect answer but some reasonable justification; or correct answer but justification only partly correct), 1 (correct answer and well-reasoned and correct justification).

For the coding portion of the assignment, I want you to write two programs: Cipher.java and Classifier.java -- the first of these two should be straightforward, the second might be a little more open-ended. These two files should be contained in the Hw1.zip file you submit -- do not include class files or project files or any other files. Your code will be compiled from the command line with the lines:

javac Cipher.java
javac Classifier.java

You can assume the grader has a Java 1.6 compiler. The first program will be run from the command-line with a line of the following format:

java Cipher action cipher_file.txt text_to_process.txt

Here action will be one of encrypt or decrypt. The file cipher_file.txt is a file used to describe a cipher using the format described below; the file text_to_process.txt is a file to perform the action on given the cipher described in cipher_file.txt. The format of cipher_file.txt should be:

cipher_type
details on specific cipher

Here cipher_type can be one of substitution or double-transposition. If the first line had substitution, then the next line should be a permutation of the letters a-z. For example,

hvieopwxyzqrsjklbcdtufgmna

This example would mean that, when encrypting, the letter 'a' should be substituted by 'h', the letter 'b' with 'v', etc. If cipher_type is double-transposition, then the next two lines contain the permutation for the rows and then for the columns. For example, the lines

321
4213

would correspond to the double transposition cipher given on page 26 of the book. You can assume the largest double transposition matrix you would need to construct is 9 x 9.

When run from the command line, Cipher should output to stdout the result of doing the given action with regard to the provided cipher in cipher_file.txt on the file text_to_process.txt.

The second program will be run from the command-line with a line like:

java Classifier filename.txt

Here filename.txt is some file which contains unpunctuated, lower-case, non-whitespaced, UTF-8 English text that has been encrypted with either a substitution or double transposition cipher. On such an input your program should output either "substitution" or "double transposition" depending on whether it thinks a substitution cipher was used or a double transposition was used. How you determine which is more likely the case is up to you. Hence, this part of the homework is open-ended. For example, you might try using things like Figure 2.2 in the book (how is this affected by a substitution cipher versus double transposition cipher? If you can't distinguish on single characters (there is a way to do this using single characters), try character pairs.).

In addition, to Cipher.java and Classifier.java, I want you to prepare two text files wiki_first.txt, wiki_last.txt, which are also to be included in Hw1.zip. To prepare these files, identify the first and last letter of the surname of the youngest member of your team. For me, Chris Pollett, this would be 'p' and 't'. Find Wikipedia articles beginning with these two letters. For example, http://en.wikipedia.org/wiki/Potato and http://en.wikipedia.org/wiki/Top_hat , then cut and paste these into either wiki_first.txt or wiki_last.txt, lower-case all letters, and strip all characters other than a through z. If the resulting file is less than 1 kilobyte choose a different Wikipedia article with that letter. To receive credit your classifier should be able to work on the two Wikipedia files you create. In addition, two bonus points will be awarded to the top three classifiers from amongst student submissions (this will be judged based on all the wikipedia files submitted).

Point Breakdown

Book Problems, graded as described above 3pts
Cipher to encrypt substitution ciphers on test files (1 all tests pass, 0.5 most pass, 0 otherwise) 1pt
Cipher to decrypt substitution ciphers on test files (1 all tests pass, 0.5 most pass, 0 otherwise) 1pt
Cipher to encrypt double transposition ciphers on test files (1 all tests pass, 0.5 most pass, 0 otherwise) 1pt
Cipher to decrypt double transposition ciphers on test files (1 all tests pass, 0.5 most pass, 0 otherwise) 1pt
Wiki files prepared as described (no partial credit) 1pt
Classifier works on wiki_first.txt when it is encrypted with test substitution and test double transposition ciphers (no partial credit) 1pt
Classifier works on wiki_last.txt when it is encrypted with test substitution and test double transposition ciphers (no partial credit) 1pt
Total10pts