Rechnernetze
Home Nach oben Stichworte

Verschlüsselung durch das Rucksack-Problem

Ein 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

Einfaches Problem

1

3 5 11 23 46 136 263 ´ 203 mod 491
Transformiertes Problem 203 118 33 269 250 9 112 361
umsortiert ergibt Schlüssel 9 33 112 118 203 250 269 361
Klartext 1 1 1 0 1 0 0 0
Chiffre 9 + 33 + 112 + 0 + 203 + 0 + 0 + 0 = 357
transformierte Chiffre

357 ´ 203-1 mod 491 = 357 ´ 387 mod 491

= 188
Lösung einfaches Problem 136 + 46 + 5 + 1 = 188
Lösung schwieriges Problem 112 + 9 + 33 + 203 = 357
Klartext 1 1 1 0 1 0 0 0

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.