## 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.