Verschlüsselung durch das Rucksack-ProblemEin Verfahren zur geheimen Übertragung von Daten kann mit Hilfe eines NP-vollständigen Problems, dem Rucksatzproblem (knapsack problem), durchgeführt werden. Bei diesem Verfahren gilt es, aus einer vorliegenden Menge von Zahlen (z.B. 9, 33, 112, 118, 203, 250, 269, 361) jene herauszufinden, die eine bestimmte Summe ergeben, z.B. 357; dieses ist zumindest für sehr große Zahlenmengen, z.B. mehr als 100 Zahlen, ein 'hartes' Problem, da im Prinzip jede Kombination von Zahlen ausprobiert werden muss. Allerdings ist das Rucksackproblem sehr einfach lösbar, wenn die Summe aller kleineren Zahlen kleiner ist als die nächstgrößere Zahl, z.B.: 1, 3, 5, 11, 23, 46, 136, 263. Jetzt kann eine Summe, z.B. 188, einfach durch Probieren der Subtraktion erhalten werden, beginnend mit der größten Zahl; damit ist das Problem in linearer Zeit lösbar. 188-263<0, 188-136=52, 52-46=6, 6-23<0, 6-11<0, 6-5=1, 1-1=0, d.h. 1+5+46+136=188 Transponiert man ein einfaches Rucksackproblem durch Multiplikation modulo m mit einem Faktor a in ein schwieriges Rucksackproblem, so kann ein Sender eine Bitfolge (z.B. 11101000) durch Addition der entsprechenden Summanden chiffrieren, und diese Chiffre an den Empfänger übertragen. Der kennt den Faktor a und dessen Reziprokwert a-1, und kann somit das schwierige Problem in ein einfaches zurück transformieren. Dieses kann gelöst werden und ergibt somit wieder den Klartext. Beispiel zum Rucksackproblem
Rucksackprobleme eignen sich nur bedingt für die Übertragung geheimer Nachrichten, da zum einen die Schwierigkeit eines transformierten Problems nicht einfach bewertet werden kann, zum anderen Schlüssel sehr lang sind (nämlich alle Zahlen) und der Overhead des Chiffre sehr groß ist, z.B. eine Verdoppelung (im Beispiel müssen 8 Bits in maximal 12 Bits chiffriert werden). Darüber hinaus gelten sie mittlerweile auch nicht mehr als sicher, da Angriffsverfahren entwickelt wurden, die diese brechen. Aus diesem Grunde werden meistens andere Verfahren verwendet, z.B. die RSA-Methode.
|