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. |
|
|