Rechnernetze
Home Nach oben

Verschlüsselung durch das Rucksack-Problem

Verfahren zur geheimen Übertragung von Daten mit Hilfe NP-vollständigen Problems, 
Rucksatzproblem (knapsack problem)
aus vorliegenden Menge von Zahlen
 z.B. 9, 33, 112, 118, 203, 250, 269, 361
jene herauszufinden, die bestimmte Summe ergeben, z.B. 357
für sehr große Zahlenmengen 'hartes' Problem,
z.B. mehr als 100 Zahlen, 
im Prinzip jede Kombination von Zahlen auszuprobieren 
sehr einfach lösbar, wenn 
Summe aller kleineren Zahlen kleiner als nächstgrößere Zahl, 
z.B.: 1, 3, 5, 11, 23, 46, 136, 263. 
Summe einfach durch Probieren der Subtraktion 
z.B. 188, 
beginnend mit größter Zahl
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

Transponiere einfaches Rucksackproblem 
durch Multiplikation modulo m mit einem Faktor a 
in schwieriges Rucksackproblem, 
Sender kann Bitfolge 
z.B. 11101000
durch Addition der entsprechenden Summanden chiffrieren
Chiffre an Empfänger übertragen
Der kennt Faktor a und Reziprokwert a-1
kann schwieriges Problem in einfaches zurück transformieren
Dieses kann gelöst werden und ergibt 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 
nur bedingt für Übertragung geheimer Nachrichten geeignet
Schwierigkeit eines transformierten Problems unbekannt
Schlüssel sehr lang sind (nämlich alle Zahlen) 
der Overhead der Chiffre sehr groß 
ist, z.B. eine Verdoppelung (im Beispiel müssen 8 Bits in maximal 12 Bits chiffriert werden). 
mittlerweile nicht mehr sicher
Angriffsverfahren entwickelt, die diese brechen
meistens andere Verfahren verwendet, z.B. RSA-Methode.