Achtung! / Attention!

Diese Seite ist Teil unser alten Internetpräsenz, die nicht weiter gepflegt wird. Besuchen Sie auch unsere neue Präsenz unter http://ig.cs.tu-berlin.de.
This page is part of our former website that is not being maintained anymore. You may want to visit our new website at http://ig.cs.tu-berlin.de.

knapsack

knapsack (engl.) - Rucksack, Tornister
 

Die Bezeichnung `knapsack' wählte Ralph Merkle 1974 für einen von ihm entwickelten Ansatz zur Public Key-Kryptographie. Manchmal findet man auch die Bezeichnung Merkle-Hellman knapsack.

Das Problem basiert auf mengentheoretischen Überlegungen (superincreasing subset sum problem) und liefert nur eine ``geringe'' Sicherheit, da der Zeitaufwand zum unbefugten Entschlüsseln gegenüber dem Zeitaufwand zum befugten Entschlüsseln nicht unverhältnismäßig hoch ist.