C代写：CS162 Crypto|留学生CS代写|代做Java编程|C作业|C++程序|Python代码

代写一个比较杂的作业，从开始的Vigénere cipher到Hash Table, 最后是AVL Tree.

Introduction

In this assignment, you will explore the applications of hash tables to encode plaintext using simple substitution ciphers in cryptography. Work individually. Follow the guidelines in the syllabus for any discussions with others. You may work in pairs on extra credit contests, but then the extra credit will be divided among the two of you. Extra credit entries must be bug-free to be eligible and turned in on time (no late days).

Files

After downloading the assignment tarball from the course website, extract the files by running:

tar -xvf lab3-handout.tgz

from a terminal window. Some of the files worth looking at are listed below.
Files you won’t necessarily modify:

Makefile
lib/*.h
lib/*.c
lib/words

Files you should modify (and the files denoted by * will be submitted for grading):

*vc-ht.c
*encrypt.c
*decrypt.c
*vigenere_test.c

Additionally, you should create a file called: written.pdf which contains the answers to the written parts of the assignment. For your convenience, we’ve provided a LATEX template (written.tex).

Submission

To submit your programming assignment, first generate a handin archive lab3-handin.tgz with the command

make clean && make package

then submit your lab3-handin.tgz file to your Subversion repository (svn) for the class. Once you’ve completed all problems, you should also submit your written.pdf to Gradescope.

Note that your code will not be graded until after the due date. It is your responsibility to test your code on the CSIL machines and proofread your writeup thoroughly before submitting. Code that does not compile will not receive any points.

Word Substitution Cipher

Due to your excellent work in parsing hashtags in lab 2, you are reached out by an agent from the Never Segfault Academy, also known as the NSA.1 To ensure secure communication among their newly set up computer network and prevent any data from being intercepted and copied, they intend to implement an encryption protocol. Your job is to implement a simple word substitution cipher using hash tables in C for their secure transmission network.

Vigénere cipher

After doing some research on different types of substitution cipher, you find that the Vigénere cipher may be a good start. So in this part of the assignment, you will implement a modified version of the Vigénere cipher.

First, a little cryptographic background. Let’s say you’re sitting in class bored, and you want to pass a note to your friend sitting way on the other side of the classroom. To get the note there, you’ll have to relay your note through a lot of your classmates. However, perhaps the message contains some secret information that you don’t want any classmate but your friend to know (name of your crush, your Netflix password, etc). The purpose of a cryptographic cipher is to encrypt the message in a way so that only you and your friend can figure out, or decrypt, the original message.

In order to accomplish this, you and your friend need some shared, secret piece of information, called a key. A cryptographic cipher is a function that takes a key k and a message m, and outputs a ciphertext c which is the encoding of m. There is also a matching decryption function that takes the key k and a ciphertext c, and outputs the original message m.

One of the very first ciphers ever used was the Caesar cipher. We will describe a slightly modified version of the Caesar cipher based on words (if you want to read about the original version, you can find it on Wikipedia). The key is a number, and encryption offsets the words in the message by the key value. The easiest way to describe this is by example. Let’s say all words in the message must come from some “language” L, for example

L = ["NSA", "CIA", "IRA", "PPAP", "PW", "DJT", "HRC", "IS", "WIFI"]

and we want to pass the message “WIFI PW IS CIA”. Notice that the “language” L in this example is not sorted in any order, but you can safely assume that the dictionary lib/words you will use later is sorted alphabetically. Furthermore, words in this example L are all capitalized, however the language we will use in later sections are all in lowercase. Using key 1, each word becomes the one at the next index in the language (with the last looping back) e.g. “NSA” becomes “CIA”, “CIA” becomes “IRA”, … , “IS” becomes “WIFI”, and “WIFI” becomes “NSA”. On key 2, each word becomes the one that is two indices away e.g. “NSA” becomes “IRA”, . . . , “HRC” becomes “WIFI”, “IS” becomes “NSA”, and “WIFI” becomes “CIA”. Applying this to each word, on key 4 the message “WIFI PW IS CIA” becomes “PPAP WIFI IRA DJT”. To decrypt, we would replace each word with the one 4 words before it.

The Vigénere cipher you are implementing is an improvement on this. Instead of using just a single number for a key, we use an entire phrase. Each word in the phrase is associated with its index in the language, and we shift the words in our message by that index as in the Caesar cipher.

Again, an example is the best description. Let’s use key “HRC DJT PPAP DJT” to encipher “WIFI PW
IS CIA”. We start by aligning the words of the message with key:

HRCD DJT PPAP DJT
WIFI PWD ISDD CIA

“HRC” is the 6th word of the language (0 index!), so we shift “WIFI” by 6 (like the Caesar cipher) to “DJT”. “DJT” is the 5th word, so we shift “PW” by 5 to “NSA”, and so on. The entire ciphertext becomes

DJT NSA CIA HRC

To decrypt, we align the key words with the ciphertext words, and take each words back by each index. Finally, we don’t want to require that the key and message have the same length. To get around this, we just repeat the key as many times as necessary to cover the message. For example, encrypting with key “DJT IS HRC” would produce

DJTD IS HRC DJT IS HRC
WIFI PW ISD CIA         →   PW IRA PW HRC

Task 4.1

Using the above language, encrypt “NSA IS CIA IS IRA” using the key “PW PPAP WIFI”.
Ok! For your next tasks, we work with a generic language, which we enumerate as w1, w2, …, wn and the l-word key as wk1 … wkl.

Task 4.2

If the message is wm1 wm2 … wmd and the ciphertext is wc1 wc2 … wcd, write a mathematical expression for encrypting i.e. computing the wci from the wmi .

Task 4.3

Write a mathematical expression for decrypting i.e. computing the wmi from the wci.

Hash Tables

As you discovered in the previous tasks, the best way to implement the Vigénere cipher is to associate each word in the language with a index. We could create an array of words, sorted in alphabetical order, and therefore find each word by its index. However, during the encipher/decipher process, we also need to be able to compute the index of a word efficiently.

Therefore, we will be using both arrays and hash tables to implement the Vigénere cipher protocol. In this part of the assignment, you are going to implement a wrapper around the generic hash tables implementation that is provided to you. So you do not have to implement the hash table from scratch. The wrapper will serve as an interface specifically for inserting and looking up the words used in Vigénere cipher.

The functions you will implement in vc-ht.c should respect the header interface in lib/vc-ht.h.
Specifically, you will need to complete the functions, vc_ht_new, vc_ht_insert, vc_ht_lookup, vc_ht_free, and other helper functions for the underlying hash table. Note that this hash table stores each word as its element struct vc_ht_elem_base which has two fields. The field idx is the index of the word in the dictionary lib/words. The field word is of type word_t, which is just a typedef of char *, and is the string value of the word stored in the hash table element.

Task 4.4

In vc-ht.c, implement the helper functions, each of which should be less than two lines (except for hash), as required by vc_ht_new. Notice that they will be passed into (the generic) ht_new as function pointers, and their argument and return types do not have the “vc_“ prefix, which means you will probably need to think carefully about casting before writing your code.

For instance, elem_key takes an input e of type ht_elem, but in order to read the value stored in e, you might need to cast to the proper type first.

More specifically, the helper functions are:

elem_key: Read off the key stored in the element.
key_equal: Key comparison function for the hash table.
hash: Hash function that maps each key to its appropriate location in the hash table. A good hash function should be efficient and should minimize the number of collisions.
elem_free: Tell the hash table how each element should be freed.

Task 4.5

In vc-ht.c, implement the function in less than two lines: vc_ht_elem vc_ht_insert(ht H, vc_ht_elem e) that adds the element e to the hash table H, and returns the old element with key of e that is replaced, if it exists, and returns NULL otherwise.

Task 4.6

In vc-ht.c, implement the function in less than two lines: vc_ht_elem vc_ht_lookup(ht H, vc_ht_key k) that returns NULL if no element with key k exists and the element associated with the key otherwise.

Task 4.7

In vc-ht.c, implement the function in less than two lines: void vc_ht_free(ht H) that frees the hash table and all of its data.

Encryption

Now we can finally put everything together and start implement the encryption protocol.

Task 5.1

In encrypt.c, implement the function:

1
2
3

void decrypt_msg(word_t *A, ht HT, int wordcount,
                 word_t *key_sentence, int key_len,
                 word_t *cipher_text, word_t *plain_text, int txt_len)

Task 5.2

And conversely, in decrypt.c, implement the function:

1
2
3

void decrypt_msg(word_t *A, ht HT, int wordcount,
                 word_t *key_sentence, int key_len,
                 word_t *cipher_text, word_t *plain_text, int txt_len)

For your convenience, we have implemented some utility functions to test your implementation.
You might want to check out the functions in lib/english.h and vigenere-test.c.
In lib/english.h:

word_cmp: Comparison function for type word_t.
print_sentence: Print an array of words to stdout.

In vigenere-test.c:

init_word_array: Allocate and initialize an array of words from lib/words.
free_word_array: Free the memory used by the array of words.
init_word_ht: Allocate and initialize a hash table from the word array.
free_word_ht: Free the memory used by the hash table of words.

Feel free to use/modify the functions implemented in vigenere-test.c, which is also where all your tests should go. We have provided you with a sample test in the main function, however it is strongly recommended that you add more of your own tests and run:

make vigenere

Runtime Complexity

Consider the following function that sorts the integers in an array, assuming swap and is_sorted were implemented, where swap(A, i, j) swaps the array element A[i] and A[j], and is_sorted(A, i, j) checks if A[i,j) is sorted.

void sort(int[] A, int n)
// pre_condition: 0 <= n && n <= length(A);
// post_condition: is_sorted(A, 0, n);
{
  for (int i = 0; i < n; i++)
  // loop_invariant: 0 <= i && i <= n;
  // loop_invariant: is_sorted(A, _____, _____);
  {
    int s = 0;
    for (int j = 0; j < n-i-1; j++)
    // loop_invariant: 0 <= j && j <= n−i−1;
    // loop_invariant: s > 0 || (s == 0 && is_sorted(A, 0, j));
    {
      if (A[j] > A[j+1]) {
        swap(A, j, j+1); // function that swaps A[j] and A[j+1]
        s = s + 1;
      }
    }
    if (s == 0) return;
  }
}

Task 6.1

Complete the missing loop invariant (at line 7) after the first i iterations.

Task 6.2

The asymptotic complexity of this sort depends on the number of comparisons made between pairs of array elements. Let T(n) be the worst-case number of such comparisons made when sort(A, n) is called. Give a closed form expression for T(n).

Task 6.3

Using Big-O notation, what is the asymptotic complexity of T(n)? This is the worst-case runtime complexity of sort.

Task 6.4

Using your answer from the previous part, show that T(n) ∈ O(f(n)) using the formal definition of Big-O. That is, find a c > 0 and n0 ≥ 0 such that for every n ≥ n0, T(n) ≤ cf(n). Show your work.

Task 6.5

Using Big-O notation, what is the best case asymptotic complexity of this sort as a function of n.

AVL Trees

Task 7.1

Draw the AVL trees that result after successively inserting the following keys into an initially empty tree, in the order shown:

27, 16, 8, 9, 6, 12, 7

Show the tree after each insertion and subsequent re-balancing (if any) is completed: the tree after the first element, 27, is inserted into an empty tree, then the tree after 16 is inserted into the first tree, and so on for a total of seven trees. Make it clear what order the trees are in.

Hashing

For the following two tasks, we use the hash function:

1
2
3

int hash(int x) {
  return x + (x % 3) * 4;
}

As seen from lecture, we say that if the hash value of a key k is hash(k), then the index that we insert this key to is hash(k)%m, where m is the size of the hash table.

Task 8.1

Draw the resulting hash table of size 7 after inserting the following values, using linear probing to resolve collisions:

84, 44, 66, 16, 105, 76

Task 8.2

Draw the resulting hash table of size 7 after inserting the following values, using quadratic probing to resolve collisions:

84, 44, 66, 16, 105, 76