🙏🏿 🐥 🛌🏻 Rucksackproblem in der Kryptographie ☠️ 💃🏽 💼

Das Knapsack-Problem (Knapsack-Problem) hat die amerikanischen Kryptographen Ralph Merkle und Martin Hellman dazu veranlasst, den ersten Verschlüsselungsalgorithmus für öffentliche Schlüssel zu entwickeln.

Weiter im Programm

Formulierung des Rucksackproblems (+ warum ein Rucksack?)
Einfache und schwierige Herausforderungen
Beispiele von
Geschichte

Was ist Verschlüsselung mit öffentlichem Schlüssel?

, , «», .

. , , , .

: , .

, - !

Der erste allgemeine Public-Key-Algorithmus verwendete den Rucksack-Algorithmus.

Basierend auf der Definition von Public-Key-Systemen sind zwei Schlüssel erforderlich, um eine Nachricht erfolgreich zu verschlüsseln (und zu entschlüsseln). Der "legale" Empfänger der Nachricht kennt den geheimen Schlüssel

А

während der Absender einen anderen öffentlichen Schlüssel besitzt

B

$B$ ...

Was tun, wenn einem Angreifer ein öffentlicher Schlüssel bekannt wird?

Es gibt eine Antwort: Der öffentliche Schlüssel muss mithilfe einer Transformation ( Einwegfunktion ) aus dem geheimen Schlüssel abgerufen werden.

f

$f$ mit den folgenden zwei Eigenschaften:

$B = f(A)$ Wenn man A kennt, ist es einfach, die Funktion selbst zu berechnen

$A = f^{-1} (B)$ und es ist schwierig, die Umkehrfunktion zu berechnen

Was ist "einfach" und "schwierig"?

.

«» , . ..

n

$n$ , —

t \propto n^{a}

$t \propto n^a$ ,

a

$a$ — . , .

«» . , , .

..

n

$n$ ,

t \propto 2 n

$t \propto 2n$ , , .

Das Rucksackproblem ist wie folgt formuliert

Das Set (Rucksackvektor)

A = (a_{1}, . . ., a_{n})

$A = (a_1, ... , a_n)$ Ist ein bestellter Satz von

n

$n$ ((

n > 2),

$n > 2),$ verschiedene natürliche Zahlen

a_{i}

$a_i$ ... Lass es eine Zahl geben

k

$k$ - ganz und positiv. Die Aufgabe besteht darin, einen solchen Satz zu finden

a_{i}

$a_i$ damit geben sie insgesamt genau

k

$k$ ...

In der bekanntesten Version des Rucksackproblems muss herausgefunden werden, ob ein bestimmtes Paar hat

(A, k)

$(A , k)$ Entscheidung. In der in der Kryptographie verwendeten Variante benötigen Sie für diese Eingabe

(A, k)

$(A , k)$ Erstellen Sie eine Lösung in dem Wissen, dass eine solche Lösung existiert. Beide Optionen sind NP-vollständig.

Rucksack-Analogie

Im einfachsten Fall

k

$k$ bezeichnet die Größe (Kapazität) des Rucksacks und jede der Zahlen

a_{i}

$a_i$ Gibt die Größe (das Gewicht) eines Artikels an, der in einen Rucksack gepackt werden kann. Die Aufgabe besteht darin, einen solchen Satz von Gegenständen zu finden, damit der

Rucksack vollständig gefüllt ist.

Stellen Sie sich vor, Sie haben einen Satz Gewichte 1, 6, 8, 15 und 24, Sie müssen einen Rucksack mit einem Gewicht von 30 packen.

Grundsätzlich kann eine Lösung immer durch umfassende Suche nach Teilmengen gefunden werden

А

und zu überprüfen, welche ihrer Summen ist

k

$k$ ... In unserem Fall bedeutet dies rohe Gewalt

2^{5} = 32

$2^5 = 32$ Teilmengen (einschließlich der leeren Menge). Das ist durchaus machbar.

Aber was ist, wenn es mehrere hundert Zahlen gibt? $a_i$ ?

In unserem Beispiel ist n = 5, um die Darstellung nicht zu erschweren. Unter realen Bedingungen hat ein Beispiel beispielsweise 300

a_{i} - х

$a_i-$ ... Der Punkt hier ist, dass keine Algorithmen bekannt sind, die im Vergleich zur vollständigen Suche eine wesentlich geringere Komplexität aufweisen. Suche unter

2^{300}

$2^{300}$ Teilmengen können nicht verarbeitet werden. In der Tat ist das Rucksackproblem als NP-vollständig bekannt ... NP-vollständige Probleme werden als schwierig zu berechnen angesehen.

Entspricht die Funktion den angegebenen Anforderungen?

Wir definieren die Funktion

f (x)

$f(x)$ auf die folgende Weise. Irgendeine Nummer

0 \leq x \leq 2 n - 1

$0 ≤ x ≤ 2n − 1$ kann durch eine binäre Darstellung von gegeben sein

n

$n$ Bits, bei denen bei Bedarf führende Nullen hinzugefügt werden. Nun definieren wir

f (x)

$f(x)$ als eine Zahl erhalten von

A

$A$ alles zusammenfassen

a_{i}

$a_i$ dass das entsprechende Bit in binärer Notation

x

$x$ ist gleich 1.

Das heißt,

f (1) = f (0 . . . 001) = a_{n}

$f(1) = f(0 . . . 001) = a_n$

f (2) = f (0 . . . 010) = a_{n - 1}

$f(2) = f(0 . . . 010) = a_{n−1}$

f (3) = f (0 . . . 011) = a_{n - 1} + a_{n}

$f(3) = f(0 . . . 011) = a_{n−1} + a_n$

. . .

$...$

Funktion

f (х)

$f( )$ wurde festgelegt

n -

$n-$ einstellen

A

$A$ ... Natürlich, wenn wir rechnen können

x

$x$ von

f (x)

$f(x)$ , dann wird praktisch in der gleichen Zeit das Rucksackproblem gelöst:

x

$x$ seine binäre Darstellung wird sofort berechnet, was wiederum die Komponenten der Menge ergibt

A

$A$ in der Summe für enthalten

f (x)

$f(x)$ ... Auf der anderen Seite die Berechnung

f (x)

$f(x)$ von

x

$x$ ist leicht. Da das Rucksackproblem NP-vollständig ist,

f (x)

$f(x)$ ist ein guter Kandidat für eine Einwegfunktion. Das muss man natürlich verlangen $n$ war groß genug, sag nicht weniger $200$ ...

Verschlüsselung

Klartext

(. plain text) — , , . ( ).

Sie können auf zwei Arten verschlüsseln:

Die Nachrichtenverschlüsselung wird erhalten, indem die Elemente dieses Rucksackvektors auf die Potenz der entsprechenden Bits der verschlüsselten Nachricht angehoben werden und dann alle Ergebnisse multipliziert werden, d. H. Wenn $A = (2,3,5)$ und die Nachricht $(100)$ dann ist die Chiffre die Nummer $2^1*3^0*5^0=2$ ... Dies ist ein multiplikativer Weg.
Die Nachrichtenverschlüsselung wird erhalten, indem die Elemente dieses Rucksackvektors mit den entsprechenden Bits der verschlüsselten Nachricht multipliziert werden und dann alle Ergebnisse aufsummiert werden, d. H. Wenn $A = (2,3,5)$ und die Nachricht $(100)$ dann ist die Chiffre die Nummer $2^ *1+3^ *0+5^ *0= 2$ ... Diese Methode wird als additiv bezeichnet .

Beispiel

Um Klartext in binärer Darstellung zu verschlüsseln, wird er in Längenblöcke aufgeteilt

n

$n$ (Zum Beispiel können Sie Gewicht 30 mit Binär 11110 darstellen). Es wird angenommen, dass man das Vorhandensein eines Gegenstandes im Rucksack anzeigt und Null seine Abwesenheit anzeigt.

Die Rucksackverschlüsselung bietet einen guten Ansatz zum Erstellen öffentlicher und privater Schlüssel, wobei der private Schlüssel einfach zu verwenden und der öffentliche Schlüssel schwer herauszufinden ist.

So können wir ein System schaffen, in dem: das "harte" Problem der

öffentliche Schlüssel ist , weil Es kann leicht verschlüsselt und nicht entschlüsselt werden.

ein privater Schlüssel - das "einfache" Problem wird als dienen Mit ihm können Sie die Nachricht einfach entschlüsseln. Ohne den privaten Schlüssel müssen Sie das "schwierige" Rucksackproblem lösen.

"Einfaches" Problem

Super wachsender Rucksackvektor

A = (a_{1}, . . ., a_{n})

$A=(a_{1},...,a_{n})$ ,

Σ_{i = 1}^{j - 1} a_{i} < a_{j}

$Σ_{i=1}^{j-1} a_{i} < a_{j}$

j = 2, . . ., n

$j=2,...,n$ , . .

Für superwachsende Vektoren Α ist das Rucksackproblem leicht lösbar. Jene. Der Rucksack ist einfach zu montieren.

Nehmen wir ein Beispiel:

Algorithmus

.

, , . , .
.
(1)-(2) .

, .

"Schwieriges Problem

Es ist viel schwieriger, das Problem eines nicht übergroßen Rucksacks zu entschlüsseln .

Ein Algorithmus, der einen übergroßen Rucksack mit privatem Schlüssel und einen nicht übergroßen Rucksack mit öffentlichem Schlüssel verwendet, wurde von Merkle und Hellman entwickelt.

Sie haben dies getan, indem sie die übergroße Rucksackaufgabe in eine nicht übergroße Aufgabe umgewandelt haben.

(Merkle und Hellman haben mithilfe modularer Arithmetik einen Weg gefunden, einen "leichten" Rucksack in einen "harten" zu verwandeln.)

Erstellen Sie einen öffentlichen Schlüssel

Mehrere wichtige Konzepte

$(x, mod m)$ $x$ $m$ ,

$x$ — , $m > 1$ , [x/m] — ,
$x = (x, m o d m) + [x / m] * m$
$x = (x, mod m) + [x/m]*m$

$A$ , $m > max A$ $t < m$ , $(t, m) = 1$ .

$B = (b_1, . . . , b_n)$ , $b_i = (ta_i, modm)$ , $i = 1, . . . , n$ , , B A m t , , $(m, t)$ .

$(t, m) = 1$

$t^{−1} = u$ , ,

$t u \equiv 1 (m o d m)$
$tu ≡ 1 (mod m)$

$1 ≤ u < m$ . , $A$ $B$

$m, u$ .

$m > max A$

$m > Σ_{i=1}^{n} a_{i}$ , , $B$ $A$ $m, t$ .

— , , , .

Der Schöpfer des Kryptosystems wählt ein solches System

A, t, m, B

$A, t, m, B$ dieser Vektor

A

$A$ ist super wachsend und

B

$B$ kommt von

A

$A$ starke modulare Multiplikation in Bezug auf

m, t

$m, t$ ... Vektor

B

$B$ erweitert als Verschlüsselungsschlüssel und binäre Längenblöcke

n

$n$ als Zahlen an den Designer gesendet

β

$β$ erhalten unter Verwendung des Vektors

B

$B$ ...

Der Nachrichtenabfangjäger muss das Rucksackproblem lösen, um eintreten zu können

(B, β)

$(B, β)$ ... Der Schöpfer des Kryptosystems berechnet

α = (u β, m o d m)

$α = (uβ, modm)$

und löst das Problem mit dem Rucksackeintritt

(A, α)

$(A, α)$ ... Warum dies alles funktioniert,

zeigt das folgende Lemma.

Lemma . Stellen wir uns das vor

A = (a_{1}, . . ., a_{n})

$A = (a_1, . . . , a_n)$ super wachsender Vektor und Vektor

B

$B$ abgeleitet von

A

$A$ starke modulare Multiplikation in Bezug auf

m, t

$m, t$ ... Nehmen wir weiter an

u \equiv t^{- 1} (m o d m)

$u ≡ t^{−1} (mod m)$ ,

β

$β$ - eine beliebige natürliche Zahl und

α = (u β, m o d m)

$α = (uβ,modm)$ ... Dann sind die folgenden Aussagen wahr.

(i) Das Rucksackproblem

(A, α)

$(A, α)$ in linearer Zeit lösbar. Wenn eine Lösung vorhanden ist, ist sie eindeutig.

(ii) Das Rucksackproblem

(B, β)

$(B, β)$ hat höchstens eine Lösung.

(iii) Wenn es eine Lösung gibt, die eingegeben werden muss

(B, β)

$(B, β)$ , dann entspricht es der einzigen Eingabelösung

(A, α)

$(A, α)$ ...

Beweis (S. 104)

Beispiel

Betrachten Sie eine superwachsende Sequenz; Zum Beispiel {1, 2, 4, 10, 20, 40}. Der Modul muss größer sein als die Summe aller Zahlen in der Sequenz, zum Beispiel 110. Der Multiplikator darf keine gemeinsamen Teiler mit dem Modul haben. Also lasst uns 31 auswählen.

Also haben wir den öffentlichen Schlüssel berechnet: {31, 62, 14, 90, 70, 30} und den privaten Schlüssel - {1, 2, 4, 10, 20.40}.

Versuchen wir nun, eine Binärsequenz zu senden: 100100111100101110

Einige der Vorteile öffentlicher Schlüssel

Bei Verwendung eines Kryptosystems mit öffentlichem Schlüssel treffen sich beide Parteien nicht, kennen sich möglicherweise nicht einmal und verwenden keine Kommunikation.

Schlüssellänge. Wenn bei der symmetrischen Kryptographie der Schlüssel länger als die ursprüngliche Nachricht ist, wird kein wirklicher Gewinn erzielt. Bei Kryptosystemen mit öffentlichem Schlüssel spielt die Länge des Verschlüsselungsschlüssels keine Rolle, da er offen und öffentlich ist. Daher ist die Länge des Entschlüsselungsschlüssels nicht so wichtig (der Empfänger speichert ihn nur an einem geheimen Ort).

Geschichte

Rucksack-Kryptosysteme galten lange Zeit aufgrund ihrer NP-Vollständigkeit und hohen Verschlüsselungs- und Entschlüsselungsgeschwindigkeit als die attraktivsten und vielversprechendsten Kryptosysteme. Viele Schemata verwenden das Rucksackproblem (in verschiedenen Variationen), hier nur einige davon: das kompakte Rucksackproblem, das multiplikative Rucksackproblem, das modulare Rucksackproblem, das Matrixcover-Problem, das Gruppenfaktorisierungsproblem ...

Leider sind die meisten von ihnen anfällig für Anschläge. Es stellte sich heraus, dass es nicht trivial ist, ein sicheres Kryptosystem basierend auf dem Rucksackproblem zu entwerfen, obwohl das Problem als NP-vollständig bekannt ist. Die meisten Rucksack-Kryptosysteme wurden gehackt. Trotzdem ist das allgemeine Rucksack- (Lösungs-) Problem im Gegensatz zur ganzzahligen Faktorisierung und dem diskreten Logarithmus ein bewährtes NP-vollständiges Problem.

Einige Leute denken, dass eines Tages ein Polynom-Zeit-Algorithmus erfunden werden könnte, um ganzzahlige Faktorisierungs- und diskrete Logarithmusprobleme zu lösen, während das Rucksackproblem noch NP-vollständig ist.

Hier gibt es mehrere "ABER".

Erstens basiert die NP-Vollständigkeit auf der Worst-Case-Analyse, und zweitens ist die NP-Vollständigkeit ein Merkmal eines allgemeinen Problems, nicht eines speziellen Falls. Dies bedeutet, dass das Rucksackproblem leicht sein kann, wenn wir die durchschnittliche Komplexität berücksichtigen.

Das Material wurde auf der Grundlage dieser Literatur hergestellt:

(1) A. Salomaa. Kryptographie mit öffentlichem Schlüssel. - Springer-Verlag, 1990. - p. 75-82, S. 101-111

(2)Min Kin Lai. Rucksack-Kryptosysteme : Vergangenheit und Zukunft - Universität von Kalifornien, 2001

(3) Baocang Wang, Qianhong Wu, Yupu Hu. Ein auf Rucksäcken basierendes probabilistisches Verschlüsselungsschema. 2007

(4) - (5)

Rucksackproblem in der Kryptographie