👌🏻 👨🏻‍🏫 ☪️ Masalah knapsack dalam kriptografi 👩🏿‍🌾 🖕🏼 🕺🏽

Masalah Knapsack (Knapsack Problem) adalah masalah yang menjadi dasar kriptografer Amerika Ralph Merkle dan Martin Hellman mengembangkan algoritma enkripsi kunci publik pertama.

Lebih lanjut dalam program ini

Pernyataan masalah knapsack (+ mengapa knapsack?)
Tantangan mudah dan sulit
Contoh dari
Sejarah

Apa itu enkripsi kunci publik?

, , «», .

. , , , .

: , .

, - !

Algoritma kunci publik umum pertama menggunakan algoritma ransel.

Berdasarkan definisi sistem kunci publik, dibutuhkan dua kunci untuk berhasil mengenkripsi (dan mendekripsi) pesan. Penerima pesan yang "sah" mengetahui kunci rahasia

А

sedangkan pengirim memiliki kunci publik lain

B

$B$ ...

Apa yang harus dilakukan jika kunci publik diketahui oleh penyerang?

Ada jawabannya: kunci publik harus diperoleh dari kunci rahasia menggunakan transformasi ( fungsi satu arah )

f

$f$ dengan dua properti berikut:

$B = f(A)$ mengetahui A, mudah untuk menghitung fungsi itu sendiri

$A = f^{-1} (B)$ , dan sulit untuk menghitung fungsi invers

Apa itu "mudah" dan "sulit"?

.

«» , . ..

n

$n$ , —

t \propto n^{a}

$t \propto n^a$ ,

a

$a$ — . , .

«» . , , .

..

n

$n$ ,

t \propto 2 n

$t \propto 2n$ , , .

Rumusan masalah knapsack adalah sebagai berikut

Set (vektor ransel)

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

$A = (a_1, ... , a_n)$ Apakah satu set yang dipesan

n

$n$ (

n > 2),

$n > 2),$ bilangan asli yang berbeda

a_{i}

$a_i$ ... Biarlah ada nomor

k

$k$ - utuh dan positif. Tugasnya adalah menemukan set seperti itu

a_{i}

$a_i$ Sehingga secara total mereka memberi dengan tepat

k

$k$ ...

Dalam versi paling terkenal dari masalah ransel, diperlukan untuk mengetahui apakah pasangan tertentu memilikinya

(A, k)

$(A , k)$ keputusan. Dalam varian yang digunakan dalam kriptografi, Anda membutuhkan masukan ini

(A, k)

$(A , k)$ membangun solusi dengan mengetahui bahwa solusi seperti itu ada. Kedua opsi ini NP-complete.

Analogi ransel

Dalam kasus yang paling sederhana

k

$k$ menunjukkan ukuran (kapasitas) ransel, dan masing-masing nomor

a_{i}

$a_i$ menunjukkan ukuran (berat) barang yang dapat dimasukkan ke dalam ransel. Tugasnya adalah menemukan set barang sedemikian rupa sehingga

ransel terisi penuh.

Artinya, bayangkan Anda memiliki satu set timbangan 1, 6, 8, 15 dan 24, Anda perlu mengemas ransel dengan berat 30.

Pada prinsipnya, solusi selalu dapat ditemukan dengan pencarian subset yang menyeluruh

А

dan memeriksa jumlah mereka yang mana

k

$k$ ... Dalam kasus kami, ini berarti kekerasan

2^{5} = 32

$2^5 = 32$ subset (termasuk set kosong). Ini sepenuhnya bisa dilakukan.

Tetapi bagaimana jika ada beberapa ratus angka $a_i$ ?

Dalam contoh kami, n = 5, agar tidak mempersulit presentasi. Dalam kondisi nyata, sebuah contoh akan memiliki, katakanlah, 300

a_{i} - х

$a_i-$ ... Intinya di sini adalah bahwa tidak ada algoritme yang diketahui memiliki kompleksitas yang jauh lebih rendah dibandingkan dengan penelusuran lengkap. Cari di antara

2^{300}

$2^{300}$ subset tidak dapat diproses. Memang, masalah knapsack dikenal sebagai NP-complete ... Masalah NP-complete dianggap sulit untuk dihitung.

Apakah fungsinya memenuhi persyaratan yang ditentukan?

Kami mendefinisikan fungsinya

f (x)

$f(x)$ dengan cara berikut. Nomor berapa saja

0 \leq x \leq 2 n - 1

$0 ≤ x ≤ 2n − 1$ dapat diberikan oleh representasi biner dari

n

$n$ bit, di mana angka nol di depan ditambahkan jika perlu. Sekarang mari kita definisikan

f (x)

$f(x)$ sebagai nomor yang diperoleh dari

A

$A$ menyimpulkan semua seperti itu

a_{i}

$a_i$ bahwa bit yang sesuai dalam notasi biner

x

$x$ sama dengan 1.

Yaitu,

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$

. . .

$...$

Fungsi

f (х)

$f( )$ ditentukan

n -

$n-$ set

A

$A$ ... Tentunya jika kita mampu menghitung

x

$x$ dari

f (x)

$f(x)$ , maka dalam waktu yang hampir bersamaan masalah ransel akan teratasi:

x

$x$ representasi binernya segera dihitung, yang pada gilirannya memberikan komponen-komponen himpunan

A

$A$ termasuk dalam jumlah untuk

f (x)

$f(x)$ ... Di sisi lain, perhitungannya

f (x)

$f(x)$ dari

x

$x$ ringan. Karena masalah knapsack adalah NP-complete,

f (x)

$f(x)$ adalah kandidat yang baik untuk fungsi satu arah. Tentu saja, orang harus menuntut itu $n$ cukup besar, jangan kurangi $200$ ...

Enkripsi

Teks biasa

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

Ada dua cara untuk mengenkripsi:

Sandi pesan diperoleh dengan menaikkan elemen vektor knapsack ini ke kekuatan bit yang sesuai dari pesan terenkripsi dan kemudian mengalikan semua hasilnya, yaitu, jika $A = (2,3,5)$ dan pesannya $(100)$ , maka sandi tersebut adalah nomornya $2^1*3^0*5^0=2$ ... Ini adalah cara perkalian .
Cipher pesan diperoleh dengan mengalikan elemen vektor knapsack ini dengan bit yang sesuai dari pesan terenkripsi dan kemudian menjumlahkan semua hasilnya, yaitu, jika $A = (2,3,5)$ dan pesannya $(100)$ , maka sandi tersebut adalah nomornya $2^ *1+3^ *0+5^ *0= 2$ ... Metode ini disebut aditif .

Contoh

Untuk mengenkripsi teks biasa dalam representasi biner, itu dibagi menjadi beberapa blok

n

$n$ (misalnya, Anda dapat merepresentasikan bobot 30 dengan biner 11110). Diyakini bahwa satu menunjukkan adanya suatu barang di ransel, dan nol menunjukkan ketiadaannya.

Enkripsi ransel memberikan pendekatan yang baik untuk membuat kunci publik dan privat di mana kunci privat mudah digunakan dan kunci publik sulit untuk diketahui.

Jadi, kita dapat membuat sistem di mana: masalah "hard" adalah

kunci publiknya , karena dengan itu, Anda dapat dengan mudah mengenkripsi dan tidak mungkin untuk mendekripsi pesan.

kunci pribadi - masalah "mudah" akan berfungsi sebagai menggunakannya, Anda dapat dengan mudah mendekripsi pesan. Tanpa kunci privat, Anda harus menyelesaikan masalah ransel yang "sulit".

Masalah "mudah"

Vektor ransel super tumbuh

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

Untuk vektor super-tumbuh Α, masalah ransel mudah dipecahkan. Itu. ransel mudah dirakit.

Mari kita ambil contoh:

Algoritma

.

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

, .

Masalah "sulit"

Jauh lebih sulit untuk menguraikan masalah tas punggung yang tidak terlalu besar .

Salah satu algoritme, yang menggunakan tas ransel kunci pribadi berukuran besar dan tas ransel kunci publik yang tidak terlalu besar, dibuat oleh Merkle dan Hellman.

Mereka melakukan ini dengan mengambil tugas ransel yang terlalu besar dan mengubahnya menjadi tugas yang tidak terlalu besar.

(Merkle dan Hellman, menggunakan aritmatika modular, menemukan cara untuk mengubah ransel "ringan" menjadi tas "keras")

Buat kunci publik

Beberapa konsep penting

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

— , , , .

Pencipta sistem kriptografi memilih sistem seperti itu

A, t, m, B

$A, t, m, B$ vektor itu

A

$A$ tumbuh super, dan

B

$B$ datang dari

A

$A$ perkalian modular yang kuat sehubungan dengan

m, t

$m, t$ ... Vektor

B

$B$ diperluas sebagai kunci enkripsi dan panjang blok biner

n

$n$ dikirim ke desainer sebagai angka

β

$β$ diperoleh dengan menggunakan vektor

B

$B$ ...

Interceptor pesan harus menyelesaikan masalah ransel untuk masuk

(B, β)

$(B, β)$ ... Pencipta sistem kriptografi menghitung

α = (u β, m o d m)

$α = (uβ, modm)$

dan memecahkan masalah masuknya ransel

(A, α)

$(A, α)$ ... Mengapa semua ini berhasil

ditunjukkan dalam lemma berikut.

Lemma . Mari kita anggap itu

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

$A = (a_1, . . . , a_n)$ vektor dan vektor super berkembang

B

$B$ berasal dari

A

$A$ perkalian modular yang kuat sehubungan dengan

m, t

$m, t$ ... Anggaplah itu lebih jauh

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

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

β

$β$ - bilangan asli sewenang-wenang dan

α = (u β, m o d m)

$α = (uβ,modm)$ ... Maka pernyataan berikut ini benar.

(i) Masalah ransel

(A, α)

$(A, α)$ solvable dalam waktu linier. Jika ada solusi, maka itu unik.

(ii) Masalah ransel

(B, β)

$(B, β)$ memiliki paling banyak satu solusi.

(iii) Jika ada solusi untuk masuk

(B, β)

$(B, β)$ , lalu cocok dengan satu-satunya solusi entri

(A, α)

$(A, α)$ ...

bukti (p. 104)

Contoh

Pertimbangkan urutan tumbuh super; misalnya, {1, 2, 4, 10, 20, 40}. Modulus harus lebih besar dari jumlah semua angka dalam barisan, misalnya 110. Pengali tidak boleh memiliki pembagi yang sama dengan modulusnya. Jadi mari kita pilih 31.

Jadi, kami menghitung kunci publik: {31, 62, 14, 90, 70, 30} dan kunci pribadi - {1, 2, 4, 10, 20.40}.

Sekarang mari kita coba mengirim urutan biner: 100100111100101110

Beberapa manfaat kunci publik

Saat menggunakan sistem kriptografi kunci publik, kedua belah pihak tidak bertemu, mereka bahkan mungkin tidak saling mengenal dan menggunakan jenis komunikasi apa pun.

Panjang kunci. Dalam kriptografi simetris, jika kuncinya lebih panjang dari pesan asli, tidak ada keuntungan nyata yang dicapai. Adapun untuk sistem kriptografi kunci publik, panjang kunci enkripsi tidak menjadi masalah, karena ini publik dan publik. Oleh karena itu, panjang kunci dekripsi tidak begitu penting (penerima hanya menyimpannya di tempat rahasia)

Sejarah

Untuk waktu yang lama, backpack cryptosystems dianggap sebagai cryptosystem yang paling menarik dan menjanjikan karena kelengkapan NP dan kecepatan enkripsi dan dekripsi yang tinggi. Banyak skema menggunakan masalah knapsack (dalam berbagai variasi), berikut ini hanya beberapa di antaranya: masalah knapsack kompak, masalah knapsack multiplikasi, masalah knapsack modular, masalah matrixcover, masalah faktorisasi grup ...

Sayangnya, kebanyakan dari mereka rentan terhadap serangan. Ternyata tidak sepele merancang sistem kriptografi yang aman berdasarkan masalah knapsack, meskipun masalah tersebut dikenal dengan NP-complete. Kebanyakan cryptosystem knapsack telah diretas. Meskipun demikian, berbeda dengan faktorisasi integer dan logaritma diskrit, masalah knapsack (solusi) umum adalah masalah NP-complete yang terbukti.

Beberapa orang berpikir bahwa suatu hari algoritma polinomial-waktu dapat ditemukan untuk memecahkan masalah faktorisasi integer dan logaritma diskrit, sedangkan masalah knapsack masih NP-complete.

Ada beberapa "TAPI" di sini.

Pertama, kelengkapan NP didasarkan pada analisis kasus terburuk, dan kedua, kelengkapan NP adalah karakteristik masalah umum, bukan kasus spesifik. Artinya jika kita mempertimbangkan rata-rata kompleksitas, masalah knapsack bisa jadi mudah.

Materi yang disusun berdasarkan literatur ini:

(1) A. Salomaa. Kriptografi Kunci Publik. - Springer-Verlag, 1990. - hal. 75-82, hlm. 101-111

(2)Min Kin Lai. Knapsack Cryptosystems : Past and Future - University of California, 2001

(3) Baocang Wang, Qianhong Wu, Yupu Hu. Skema enkripsi probabilistik berbasis ransel. 2007

(4) - (5)

Masalah knapsack dalam kriptografi