Kryptosysteme basierend auf dem
Rucksack-Problem:
Analyse - Implementierung - Sicherheit
Corinna Feeken
Carl von Ossietzky Universität Oldenburg
16. Oktober 2015
1 / 34
Gliederung
Einführung
Motivation
Kryptosysteme
Das Rucksack-Problem
Das Merkle-Hellman-Kryptoystem und mögliche Angriffe
Das allgemeine Merkle-Hellman-Kryptoystem
Der Algorithmus von Shamir
Low-Density-Angriff mit dem Short-Vector-Algorithmus
Das Chor-Rivest-Kryptosystem
Das Nasako-Murakami-Kryptosystem
Fazit
2 / 34
Motivation
I
Sicherheit vieler Kryptosysteme basiert auf
I
I
Faktorisierungsproblem oder
Problem des diskreten Logarithmus
I
Algorithmus mit polynomieller Laufzeit für diese Probleme
bekannt (aber: benötigt Quantencomputer)
I
Rucksack-Problem (RP) ist NP-vollständig
3 / 34
Kryptosysteme
Ein Kryptosystem besteht aus
I
einem Klartextraum
I
einem Geheimtextraum
I
einem Schlüsselraum
I
Ver- und Entschlüsselungsfunktionen
Asymmetrische Kryptosysteme besitzen zudem
I
einen öffentlichen und einen privaten Schlüssel
I
eine Einwegfunktion
4 / 34
Das Rucksack-Problem
I
gegeben:
I
I
I
I
eine Menge N mit n Elementen
ein Gewichtsvektor w = (w1 , . . . , wn )
ein Profitvektor p = (p1 , . . . , pn )
eine Kapazität c ∈ R
wi ∈ R Gewicht und pi ∈ R Profit von Element i ∈ N
I
gesucht: ein Vektor x = (x1 , . . . , xn ) mit xi ∈ N, sodass
n
X
i=1
wi · xi ≤ c und
n
X
pi · xi maximal
i=1
5 / 34
Das Rucksack-Problem
unbegrenztes
Rucksack-Problem
Ppi = 1,
wi xi = c
unbegrenztes
Change-making-Problem
0 ≤ xi ≤ c/wi
begrenztes
Rucksack-Problem
Ppi = 1,
wi xi = c
Change-making-Problem
xi ∈ {0, 1}
0-1-Rucksack-Problem
wi = pi
Teilsummenproblem
n
P
i=1
wi xi ≤ c,
n
P
wi xi maximal mit xi ∈ {0, 1}, wi ∈ N
i=1
6 / 34
Das Rucksack-Problem
In der Kryptologie wird das Teilsummenproblem zur
Verschlüsselung genutzt:
I
binärer Klartextvektor: x = (x1 , x2 , . . . , xn )
I
öffentlicher Schlüssel: w = (w1 , w2 , . . . , wn )
n
P
Geheimtext: c =
wi · xi = w ∗ x
I
i=1
(∗ bezeichnet das Skalarprodukt von w und x)
7 / 34
Das Rucksack-Problem
Definition (stark wachsend)
Ein Gewichtsvektor w = (w1 , . . . , wn ) heißt stark wachsend, wenn
∀i ∈ {1, 2, . . . , n} : wi >
i−1
X
wj .
j=1
I
leichtes Rucksack-Problem: RP mit stark wachsendem
Gewichtsvektor (sonst schweres RP)
8 / 34
Das Merkle-Hellman-Kryptosystem (MHK)
I
eines der ersten Verfahren der asymmetrischen Kryptologie
I
1978 von Ralph C. Merkle und Martin E. Hellman
veröffentlicht
I
bereits mehrere erfolgreiche Angriffe auf das MHK
9 / 34
MHK - Schlüsselerzeugung
1. Wähle einen stark wachsenden Gewichtsvektor
a = (a1 , a2 , . . . , an ) mit Komponenten aus N \ {0}.
2. Wähle zwei große Zahlen m, w ∈ N mit
m>
n
X
ai
und ggT (m, w ) = 1.
i=1
3. Erzeuge einen neuen Gewichtsvektor b = (b1 , b2 , . . . , bn ) mit
b = w · a mod m.
I
Komponenten von b sind durch modulare Multiplikation
pseudo-zufällig angeordnet.
I
kpriv = (a, m, w )
I
kpub = b
10 / 34
MHK - Verschlüsselung
I
Verschlüssele eine binäre Nachricht x = (x1 , x2 , . . . , xn ) mit
öffentlichem Schlüssel b und erhalte die Chiffre Sb :
Sb =
n
X
bi x i = b ∗ x
i=1
11 / 34
MHK - Entschlüsselung
1. Berechne zu w die Inverse w −1 mod m.
2. Wandle das schwere RP in ein leichtes RP mit Kapazität Sa
um:
Sa = a ∗ x
≡ w −1 · b ∗ x mod m
≡ w −1 · Sb mod m
3. Löse das leichte RP mittels dem folgenden Algorithmus.
1
2
3
4
5
6
Algorithm 1: leichtes Rucksack-Problem lösen
for i ← n to 1 do
if Sa ≥ ai then
xi ← 1
Sa ← Sa − ai
else
xi ← 0
7
return x
12 / 34
Der Algorithmus von Shamir
I
Algorithmus in Polynomialzeit von Adi Shamir (1984)
I
Finde zu gegebenem öffentlichen Schlüssel b = (b1 , . . . , bn )
ein Trapdoor-Paar (w , m), sodass
a = w · b mod m
mit m >
Pn
i=1 ai
und a stark wachsend.
13 / 34
Der Algorithmus von Shamir
ai = w · bi mod m
m
bi
bi
m
bi
...
bi
2·m
bi
3·m
bi
bi
bi
(bi −2)·m
bi
(bi −1)·m
bi
m
w
Abbildung: ai -Sägezahnkurve
14 / 34
Der Algorithmus von Shamir
I
maximaler Abstand von w zum nächstgelegenen linken
ai -Minimum: baii
I
w liegt sehr nah an einem Minimum jeder ai -Kurve
I
Häufungspunkte suchen, um w zu finden
15 / 34
Der Algorithmus von Shamir
I
Löse die Abhängigkeit von m mittels Division durch m.
I
V =
w
m
ai = V · bi mod 1
1
bi
bi
1
bi
...
bi
2
bi
3
bi
bi
bi −2
bi
bi
bi −1
bi
1
V
16 / 34
Der Algorithmus von Shamir
I
Finde Häufungspunkte für die ersten k ai -Kurven.
I
k = 4 für das MHK mit n = 100
0
−2 ≤ p1 b2 − p2 b1 ≤ 02 −2 ≤ p1 /b1 − p2 /b2 ≤ 2 0
−3 ≤ p1 /b1 − p3 /b3 ≤ 3 ⇒ − ≤ p1 b3 − p3 b1 ≤ 0 3
3
−0 ≤ p1 b4 − p4 b1 ≤ 0 −4 ≤ p1 /b1 − p4 /b4 ≤ 4 4
4
mit pi ∈ N und 1 ≤ pi ≤ bi − 1
I
Löse die Ungleichung mit den Unbekannten pi .
17 / 34
Der Algorithmus von Shamir
I
Sei p eine Lösung für p1 aus dem Ungleichungssystem.
I
Betrachte das Intervall [p/a1 , (p + 1)/a1 ).
I
Ordne die Minima V1 , . . . , Vs der anderen ai -Kurven innerhalb
des Intervalls nach aufsteigender Größe.
18 / 34
Der Algorithmus von Shamir
ai = V · bi mod 1
−
τ1 t
1
...
Vb
1
...
p
b1
Vt
Vt+1
p+1
b1
1
V
τ1t
I
Geradengleichung: Vbi − τit , Vt ≤ V < Vt+1
I
τit : Anzahl an Minima der ai -Kurve in (0, Vt ]
19 / 34
Der Algorithmus von Shamir
I
Finde ein Teilintervall, in dem
n
X
(Vbi − τit ) < 1
i=1
und
∀i ∈ {2, . . . , n} : (Vbi − τit ) >
i−1
X
(Vbj − τjt )
j=1
für Vt ≤ V < Vt+1 erfüllt werden.
20 / 34
Der Algorithmus von Shamir
Wenn Teilintervall leer:
I
Fahre mit [Vt+1 , Vt+2 ), . . . [Vs−1 , Vs ) fort.
I
Betrachte weitere Häufungspunkte.
Wenn solch ein Teilintervall gefunden wurde:
w
m
I
Nenner und Zähler jedes Quotienten V =
ist ein Trapdoor-Paar.
im Teilintervall
I
Berechne privaten Schlüssel a = w · b mod m und löse
leichtes RP mit a und Kapazität Sa = w −1 · Sb mod m.
21 / 34
Low-Density-Angriff mit dem Short-Vector-Algorithmus
I
1985 von J. C. Lagarias und A. M. Odlyzko erfunden
I
gesuchter Klartext wird direkt gefunden (wenn Algorithmus
erfolgreich), ohne den privaten Schlüssel zu ermitteln
I
SV-Algorithmus findet für fast jedes RP mit geringer Dichte
(< 0, 645) in Polynomialzeit eine Lösung
Definition (Dichte)
Die Dichte eines Rucksack-Problems mit öffentlichem Schlüssel
b = (b1 , b2 , . . . , bn ) wird definiert als
d(b) =
n
log2 (max bi )
, i = 1, 2, . . . , n.
22 / 34
Der Short-Vector-Algorithmus
Definition (Gitter und Basismatrix)
Ein Gitter L ist eine Teilmenge des n-dimensionalen Vektorraums
Rn , welches von linear unabhängigen Vektoren v1 , v2 , ..., vn über
Rn aufgespannt wird:
( n
)
n
X
X
L :=
Zvi =
ri vi | ri ∈ Z, 1 ≤ i ≤ n
i=1
i=1
Die Basismatrix eines Gitters wird definiert als
v1
v1,1 v1,2 ... v1,n
v2 v2,1 v2,2 ... v2,n
V := . = .
.
.
.
. .
vn
vn,1 vn,2 ... vn,n
23 / 34
Der Short-Vector-Algorithmus
I
Algorithmus basiert auf der Suche nach kürzesten Vektoren in
ganzzahligen Gittern zur Basis {v1 , . . . , vn } ⊆ Zn+1 .
I
Gesucht wird der Vektor x 0 := (x1 , . . . , xn , 0).
I
Bei geringer Dichte ist x 0 fast immer der kürzeste
nicht-triviale Vektor in L.
I
Basis wird so gewählt, dass x 0 in L enthalten ist.
1
0
..
.
T
0
0
..
.
T
x1
+ · · · + xn
0
1
−b1
−bn
T
0
0
..
+. =
0
S−
S
x1
x2
..
.
T
T
x1
x2
.
= .. = x 0
xn
xn
n
P
bi · x i
0
i=1
I
Basismatrix V wird mit dem LLL-Algorithmus reduziert.
24 / 34
I
Der Erfolg des SV-Algorithmus hängt vom LLL-Algorithmus
ab, der nicht garantiert den kürzesten Vektor zu finden.
I
Der SV-Algorithmus wurde 1992 von Coster et al. verbessert,
sodass er auf Rucksack-Probleme der Dichte < 0,9408
anwendbar ist.
25 / 34
Das Chor-Rivest-Kryptosystem
I
1988 von Benny Chor und Ronald L. Rivest veröffentlicht
I
nutzt algebraische Konstruktionen über endlichen Körpern
I
öffentlicher Schlüssel besteht aus (b1 , . . . , bp ), p und h mit p
prim oder Primzahlpotenz und p ≥ h ∈ N
I
diskreter Logarithmus in GF (p h ) muss leicht berechenbar sein
26 / 34
Das Chor-Rivest-Kryptosystem
I
verschiedene vorgeschlagene Parameter, z.B. p = 197 und
h = 24
I
aufgrund hoher Dichte (1, 0769 für obige Parameter) kein
Low-density-Angriff möglich
I
erfolgreicher Angriff 2001 von Serge Vaudenay
I
Angriff nicht möglich, wenn p und h prim sind (aber
Berechnung des diskreten Logarithmus dann zu schwer)
27 / 34
Das Nasako-Murakami-Kryptosystem
I
2006 von Yasuyuki Murakami und Takeshi Nasako
veröffentlicht
I
Low-density-Angriff durch hohe Dichte und hohe Dimension
(n > 500) nicht möglich
I
nutzt chinesischen Restsatz zur Erzeugung vom öffentlichen
Schlüssel b = (b1 , . . . , bn ):
( (P)
ai mod P
bi ≡
(Q)
ai mod Q
(P)
mit ggT (P, Q) = 1, N = PQ und ai
Länge n
I
(Q)
, ai
private Vektoren der
angreifbar, sobald N faktorisiert werden kann
28 / 34
Fazit
I
bisherige Methoden noch zu unsicher
I
weiterhin interessant (NP-Vollständigkeit)
I
viele weitere Rucksack-Kryptosysteme seit MHK
29 / 34
Quellen I
Coster, M. J. ; Joux ; LaMacchia ; Odlyzko ; Schnorr ; Stern (1992)
Improved low-density subset sum algorithms.
computational complexity Volume 2, Issue 2 , S. 111-128
Encinas, L. Hernández ; Masqué, J. Munos ; Dios, A. Queiruga (2008)
Safer parameters for the Chor-Rivest cryptosystem
Computers and Mathematics with Applications 56 , S. 2883-2886
Lagarias, J. C. ; Odlyzko, A. M. (1985)
Solving low-density subset sum problems.
Journal of the association for Computing Machinery 32, No.1, S. 229–246
Lenstra, A. K. ; Lenstra, H. W. ; Lovász, L.(1982)
Factoring polynomials with rational coefficients.
Mathematische Annalen 261, S. 515–534
Martello, Silvano ; Toth, Paolo (1990)
Knapsack problems - Algorithms and computer implementations.
John Wiley & Sons Inc. New York, NY, USA
30 / 34
Quellen II
Merkle, Ralph C. ; Hellman, Martin E. (1978)
Hiding information and signatures in trapdoor knapsacks.
IEEE Transactions on Information Theory IT-24, No.5, S. 498–516
Nasako, Takeshi ; Murakami, Yasuyuki (2007)
Knapsack Public-Key Cryptosystem Using Chinese Remainder Theorem
IACR Cryptology ePrint Archive
Shamir, Adi (1984)
A polynomial-time algorithm for breaking the basic Merkle-Hellman
cryptosystem.
IEEE Transactions on Information Theory IT-30, No.5, S. 699–704
Vaudenay, Serge (2001)
Cryptanalysis of the Chor-Rivest cryptosystem
J. Cryptology 14 , S. 87–100
Wilkeit ; Elke (2013)
Kryptologie
Vorlesungsskript WS 2013/14 Carl von Ossietzky Universität Oldenburg
31 / 34
Der Short-Vector-Algorithmus
I
Algorithmus basiert auf der Suche nach kürzesten Vektoren in
ganzzahligen Gittern zur Basis {v1 , . . . , vn } ∈ Zn+1 .
I
Sei b = (b1 , . . . , bn ) der öffentliche Schlüssel, S der
Geheimtext und x = (x1 , . . . , xn ) der gesuchte Klartext.
I
Konstruiere die Basismatrix
v1
1 0
v2 0 1
V := ... =
v n 0 0
vn+1
0 0
des Gitters L
...
...
..
.
...
...
0 −b1
0 −b2
∈ Z(n+1)×(n+1) .
1 −bn
0 S
32 / 34
Der Short-Vector-Algorithmus
I
Gesucht wird der Vektor x 0 := (x1 , . . . , xn , 0).
I
Bei geringer Dichte ist x 0 fast immer der kürzeste
nicht-triviale Vektor in L.
I
x 0 ist in L enthalten, denn:
1
0
..
.
T
0
0
..
.
T
x1
+ · · · + xn
0
1
−b1
−bn
T
0
0
..
+. =
0
S−
S
x1
x2
..
.
T
T
x1
x2
.
= .. = x 0
xn
xn
n
P
bi · xi
0
i=1
33 / 34
I
I
Um x 0 zu finden, wird die Basismatrix V mit dem
LLL-Algorithmus zu V ∗ reduziert.
n
P
∗ für 1 ≤ j ≤ n + 1.
bi vj,i
Prüfe, ob S =
i=1
Dann ist vj∗ der gesuchte Vektor x 0 .
I
Wurde kein passender Vektor gefunden, wird der Vorgang für
n
P
S=
bi − S wiederholt.
i=1
34 / 34
© Copyright 2024 ExpyDoc
