Write a Merkle-Hellman cryptosystem in C++ **Please don't just copy/paste some code, if you don't know, then don't answer** Information on cipher can be found here: https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem

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. (Needs to be converted to binary).

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

A line containing the entire sequence.

Input example:

2 (number of test cases in program)

HELLO (Input from file that needs to be converted to binary)

3 (number of items in super increasing sequence)

123 (super increasing sequence)

Can't find examples online but here are some other articles describing the cryptosystem in more detail: http://www-math.ucdenver.edu/~wcherowi/courses/m5410/ctcknap.html https://asecuritysite.com/encryption/knap http://www.tomarse.f9.co.uk/si22/

NOTE: A lot of people have answered this by copying the code from this github repository; https://github.com/moontails/Merkle-Hellman-knapsack-cryptosystem/blob/master/Encryption.cpp THIS IS NOT WHAT I NEED as it does not read in from a file.

More examples:

Creating the public/private key

First we have to choose a super-increasing knapsack (to use as the private key) with which to encrypt our data. To keep it simple, in my knapsack, I have objects of the following weights: {1, 7, 9, 18, 50, 86 }

Now I pick a modulus, m, which is bigger than the sum of all the elements. With my knapsack, the total weight is 171, so 175 would be a suitable value, so m=175.

I then pick a number, n, that is less than, and relatively prime to (that is, sharing no factors beside 1 with) m. I will take n=27.I then multiply each element in my knapsack by n mod m. This gives me: 1* 27 mod 175 = 27 7 * 27 mod 175 = 14 9 * 27 mod 175 = 68 18 * 27 mod 175 = 136 50 * 27 mod 175 = 125 86 * 27 mod 175 = 47

This creates the knapsack { 27, 14, 68, 136, 125, 47 }. This will be our public key because, as the subset-sum problem demonstrates, solving this will be hard because it is not super-increasing.

Encryption

Now we need something to encrypt. For example 01010101 11001100 00100101 First we break it up into blocks that are the length of our knapsack, so: 010101 011100 110000 100101 If we look at the first block (010101), there are 1s in the second, fourth and sixth positions. This means that we take the second, fourth and sixth numbers in our public key, and add them together: 14+136+47 = 197 Repeating this for the other 3 blocks gives us: 011100 = 14 + 68 + 136 = 218 110000 = 27 + 14 = 41 100101 = 27 + 136 + 47 = 210

This gives us the encrypted version of 01010101 11001100 00100101 as {197, 218, 41, 210}. This encrypted data would then be transmitted to the recipient. We know that the subset-sum problem is easy to solve using a super-increasing set and since our private key is super-increasing we can send them this along with m and n (as chosen earlier), to enable them to decrypt the message.

Decryption

Decrypting the message is the same as solving the subset-sum problem with the original, decrypted message as our target. First we need to solve: (x * 27) mod 175 = 1 so that we can move from the hard non-super-increasing set to the easy super-increasing set. In this case, x = 13. We can then do

(13 * 197) mod 175 = 111 to translate the target of the hard to solve problem to the target of the easy to solve problem. If we look at the private key ( {1, 7, 9, 18, 50, 86 } ), we can easily see that 111 is made up of 86 + 18 + 7. Since these correspond to the second, fourth and sixth values in the key, we can convert this to 010101. Repeating this with the other parts of the encrypted data will reveal the whole message.