Public-key cryptography

• Keys can come in pairs; an encryption key and a decryption key.
• Can’t generate one key from the other.

Knapsack Algorithms

• Knapsack algorithms came first.
• Based off the knapsack problem, an NP-complete problem: Given a pile of items with different weights, is it possible to put some of them into a knapsack so that the knapsack weights a given amount?
• Merkle-Hellman knapsack algorithm; encode a message as a solution to a series of knapsack problems.

There are two types of knapsack problems: Easy and Hard:

• Easy: Super-increasing knapsack; each element of the knapsack is greater than the sum of all the previous elements. You can solve this problem for a given weight w in linear time. Where x is the last element of the knapsack, if w > x it is not in the knapsack. If it is, w = w - x and x = x - 1. Else x = x - 1. Keep going until you reach the end, noting which ones are in the knapsack.
• Hard: Not super-increasing. No known quick algorithm to solve.

An easy knapsack can be transformed into a hard one. Merkle-Hellman uses a sequence of weights for a super-increasing knapsack as the private key, and a sequence of weights for a normal knapsack as the public key. The weights result in the same solution (the same weight presumably).

I don’t know if we need to learn the details about Merkle-Hellman. It uses 2 values n and m to convert a superincreasing knapsack into a normal one: Multiply all of the values by n, mod m. m should be a number greater than the sum of all the numbers in the sequence. n should have no factors in common with m.

You encrypt a binary message by breaking it up into pieces the size of the size of the knapsack sequence, then you add together the weights the bits pick in the sequence:

knapsack: {62,93,81,88,102,37}
message: 011000 110101 101110

011000 corresponds to 93 + 81 = 174
110101 corresponds to 62 + 93 + 88 + 37 = 280
101110 corresponds to 62 + 81 + 88 + 102 = 333

ciphertext: 174,280,333

You decrypt a message by determining an n^-1 such that n(n^-1) = 1 (mod m). Multiply each of the ciphertext values by n^-1 mod m and then partition with the private knapsack in the same way as encryption to get the plaintext values.

Why does this suck?

Merkle-Hellman has a weakness in the transformation making it possible to construct the superincreasing knapsack from the normal knapsack.

All other knapsacks have been analysed and broken generally using the same cryptographic techniques.