Das sogenannte Rucksack- (oder Knapsack) Problem war eines der ersten Probleme, welches für Public-Key-Verfahren eingesetzt wurde. Die Beschreibung ist einfach: Gegeben ist ein Rucksack, mit dem man ein gewisses Gewicht tragen kann und eine große Anzahl von Objekten mit unterschiedlichen Massen. Das Problem ist, auszuwählen, was man in den Rucksack packen muss, um diesen optimal zu füllen. Für eine große Anzahl von Objekten ist dies wirklich ein hartes Problem; die darauf aufbauenden Algorithmen haben sich inzwischen aber alle als unsicher erwiesen.
