Revision Notes

These are lecture notes from my Computer Science course.

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.

This entry was posted in cry, lecture. Bookmark the permalink.