Create a Merkle-Hellman knapsack cryptosystem in C++

Background:

MHK is an asymmetric-key cryptosystem that uses two keys: a private key and a public key. This algorithm is based on the subset set problem (which is a special case of the knapsack problem, for anyone that has been through CS472). The knapsack problem consists of finding a way to select some of the items to be packed such that their sum (the amount of space they take up) exactly equals the knapsack capacity (the target).

The MH knapsack cipher encodes a binary message as a solution to a knapsack problem by looking a block of binary plaintext and reducing it to target sum obtained by adding the knapsack terms cooresponding to 1-digits in the plaintext. For example, suppose the items to be put into the knapsack have weights of 1,2,5,9,20, and 43. For the binary plaintext block 101001, then the resulting ciphertext is 49 (sum of 1+5+43).

The knapsack problem is NP-complete. That means that it's computationally infeasible. But we need some function that adds a "trap-door" to the function for solving the knapsack problem. In this case, we have an easy solution for the special case where the sequence of item weights is "superincreasing". That means that each of element in the sequence is greater than or equal to sum of all the previous weights. For example, the sequence 1,2,4, and 9 is superincreasing.

OK, in order to get things working right we need to convert a superincreasing sequence into one that isn't superincreasing. Do that by selecting two integers \(w\) and \(n\) and multiply each element of the superincreasing sequence by \(w \mod n\). The procedure for choosing \(w\) and \(n\) works by selecting the value of \(n\) so that \(n\) is prime and greater than \(max(S)\), \(S\) being your superincreasing sequence and \(w

The public key \(H\) is the non-increasing sequence generated from \(S\). The private key is the tuple \((S,n,w)\).

The Encryption Algorithm

Divide the plaintext in blocks of bits whose size is equal to the number of elements in the sequence. Zero-pad the last block if required.

Trave rse the bits in the block, accumulating the sum of each element in the sequence \(H\) times the value of each bit (1 or 0).

The ciphertext becomes the sequences of sums from the last step.

Instructions for program:

Your program will need to get its input from a file in the following format

First line is an integer saying how many test cases are in the input file

A line containing the plaintext to be encrypted.

A line containing a single integer with the number of items in the sequence

A line containing the entire sequence.