💪 😖 📭 暗号化におけるナップザックの問題 🤲🏻 🙇🏾 🚵🏾

ナップザック問題（ナップザック問題）は、アメリカの暗号学者ラルフ・マークルとマーティン・ヘルマンが最初の公開鍵暗号化アルゴリズムを開発したことに基づいた問題です。

さらにプログラムで

ナップザック問題の定式化（+なぜナップザック？）
簡単で難しい課題
の例
歴史

公開鍵の暗号化とは何ですか？

, , «», .

. , , , .

: , .

, - !

最初の一般的な公開鍵アルゴリズムは、ナップザックアルゴリズムを使用していました。

公開鍵システムの定義に基づいて、メッセージを正常に暗号化（および復号化）するには、2つの鍵が必要です。メッセージの「合法的な」受信者は秘密鍵を知っています

А

送信者が別の公開鍵を所有している間

B

$B$ ..。

公開鍵が攻撃者に知られるようになった場合はどうすればよいですか？

答えがあります：公開鍵は、変換を使用して秘密鍵から取得する必要があります（一方向関数）

f

$f$ 次の2つのプロパティがあります。

$B = f(A)$ Aを知っていると、関数自体を計算するのは簡単です

$A = f^{-1} (B)$ 、および逆関数を計算することは困難です

「簡単」と「難しい」とは何ですか？

.

«» , . ..

n

$n$ , —

t \propto n^{a}

$t \propto n^a$ ,

a

$a$ — . , .

«» . , , .

..

n

$n$ ,

t \propto 2 n

$t \propto 2n$ , , .

ナップザック問題は次のように定式化されます

セット（バックパックベクトル）

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

$A = (a_1, ... , a_n)$ の注文セットです

n

$n$ （（

n > 2),

$n > 2),$ 明確な自然数

a_{i}

$a_i$ ..。数があるようにしましょう

k

$k$ -全体的で前向きです。タスクはそのようなセットを見つけることです

a_{i}

$a_i$ 合計で彼らは正確に与えるように

k

$k$ ..。

ナップザック問題の最も有名なバージョンでは、特定のペアが持っているかどうかを確認する必要があります

(A, k)

$(A , k)$ 決定。暗号化で使用されるバリアントでは、この入力が必要です

(A, k)

$(A , k)$ そのようなソリューションが存在することを知っているソリューションを構築します。これらのオプションは両方ともNP完全です。

バックパックのアナロジー

最も単純なケースでは

k

$k$ バックパックのサイズ（容量）と各番号を示します

a_{i}

$a_i$ バックパックに詰めることができるアイテムのサイズ（重量）を示します。タスクは、

バックパックが完全に満たされるように、そのようなアイテムのセットを見つけることです。

つまり、ウェイト1、6、8、15、24のセットがあるとすると、ウェイト30のバックパックを梱包する必要があります。

原則として、解決策はサブセットの徹底的な検索によって常に見つけることができます

А

合計がどれであるかを確認します

k

$k$ ..。私たちの場合、これはブルートフォースを意味します

2^{5} = 32

$2^5 = 32$ サブセット（空のセットを含む）。これは非常に実行可能です。

しかし、数百の数字がある場合はどうなりますか $a_i$ ？

この例では、プレゼンテーションを複雑にしないためにn = 5です。実際の状況では、例には、たとえば300があります

a_{i} - х

$a_i-$ ..。ここでのポイントは、徹底的な検索と比較して複雑さが大幅に低いアルゴリズムは知られていないということです。中から検索

2^{300}

$2^{300}$ サブセットは処理できません。確かに、ナップザック問題はNP-completeとして知られています... NP-complete問題は計算が難しいと考えられています。

機能は指定された要件を満たしていますか？

関数を定義します

f (x)

$f(x)$ 次のように。いずれかの番号

0 \leq x \leq 2 n - 1

$0 ≤ x ≤ 2n − 1$ からのバイナリ表現によって与えることができます

n

$n$ ビット。必要に応じて先行ゼロが追加されます。それでは、定義しましょう

f (x)

$f(x)$ から得られる数として

A

$A$ そのようなすべてを要約する

a_{i}

$a_i$ バイナリ表記の対応するビット

x

$x$ は1に等しいです。

つまり、

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$

. . .

$...$

関数

f (х)

$f( )$ 決定されました

n -

$n-$ セットする

A

$A$ ..。明らかに、私たちが計算することができれば

x

$x$ の

f (x)

$f(x)$ 、その後、実質的に同時にナップザックの問題が解決されます。

x

$x$ そのバイナリ表現はすぐに計算され、セットのコンポーネントが得られます。

A

$A$ の合計に含まれる

f (x)

$f(x)$ ..。一方、計算

f (x)

$f(x)$ の

x

$x$ 軽量です。ナップザックの問題はNP完全であるため、

f (x)

$f(x)$ 一方向関数の良い候補です。もちろん、それを要求する必要があります $n$ 十分な大きさでした $200$ ..。

暗号化

プレーンテキスト

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

2つの方法で暗号化できます。

メッセージ暗号は、このナップザックベクトルの要素を暗号化されたメッセージの対応するビットの累乗で累乗し、すべての結果を乗算することによって取得されます。 $A = (2,3,5)$ とメッセージ $(100)$ 、その場合、暗号は番号になります $2^1*3^0*5^0=2$ ..。これは乗法的な方法です。
メッセージ暗号は、このナップザックベクトルの要素に暗号化されたメッセージの対応するビットを乗算し、すべての結果を合計することによって取得されます。 $A = (2,3,5)$ とメッセージ $(100)$ 、その場合、暗号は番号になります $2^ *1+3^ *0+5^ *0= 2$ ..。この方法は加法と呼ばれます。

例

プレーンテキストをバイナリ表現で暗号化するには、長さのブロックに分割します

n

$n$ （たとえば、バイナリ11110で重み30を表すことができます）。1はバックパック内のアイテムの存在を示し、0はそのアイテムの不在を示すと考えられています。

バックパック暗号化は、秘密鍵が使いやすく、公開鍵を理解するのが難しい公開鍵と秘密鍵を作成するための優れたアプローチを提供します。

したがって、次のようなシステムを作成できます。「難しい」問題が

公開鍵であるため。これを使用すると、簡単に暗号化でき、メッセージを復号化することはできません。

秘密鍵-「簡単な」問題は次のように機能しますこれを使用すると、メッセージを簡単に復号化できます。秘密鍵がないと、「難しい」バックパックの問題を解決する必要があります。

「簡単な」問題

超成長バックパックベクトル

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

超成長ベクトルΑの場合、ナップザック問題は簡単に解決できます。それら。バックパックは組み立てが簡単です。

例を見てみましょう：

アルゴリズム

.

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

, .

「難しい」問題

特大でないバックパックの問題を解読することははるかに困難です。

特大の秘密鍵バックパックと非特大の公開鍵バックパックを使用する1つのアルゴリズムは、MerkleとHellmanによって作成されました。

彼らは、特大のバックパックタスクを取り、それを非特大のタスクに変換することによってこれを行いました。

（MerkleとHellmanは、モジュラー演算を使用して、「軽い」バックパックを「難しい」バックパックに変換する方法を考案しました）

公開鍵を作成します

いくつかの重要な概念

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

— , , , .

暗号システムの作成者はそのようなシステムを選択します

A, t, m, B

$A, t, m, B$ そのベクトル

A

$A$ 超成長している、そして

B

$B$ から来た

A

$A$ に関する強力なモジュラー乗算

m, t

$m, t$ ..。ベクター

B

$B$ 暗号化キーおよび長さのバイナリブロックとして拡張

n

$n$ 番号としてデザイナーに送信

β

$β$ ベクトルを使用して取得

B

$B$ ..。

メッセージインターセプターは、ナップザックの問題を解決して入力する必要があります

(B, β)

$(B, β)$ ..。暗号システムの作成者は計算します

α = (u β, m o d m)

$α = (uβ, modm)$

バックパックのエントリの問題を解決します

(A, α)

$(A, α)$ ..。これがすべて機能する理由

は、次の補題に示されています。

レンマ。ふりをしましょう

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

$A = (a_1, . . . , a_n)$ 超成長ベクトルとベクトル

B

$B$ に由来する

A

$A$ に関する強力なモジュラー乗算

m, t

$m, t$ ..。さらに、

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

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

β

$β$ -任意の自然数と

α = (u β, m o d m)

$α = (uβ,modm)$ ..。その場合、次のステートメントが当てはまります。

（i）ナップザックの問題

(A, α)

$(A, α)$ 線形時間で解ける。解決策が存在する場合、それは一意です。

（ii）ナップザックの問題

(B, β)

$(B, β)$ 最大で1つの解決策があります。

（iii）入力する解決策がある場合

(B, β)

$(B, β)$ 、それからそれは唯一のエントリーソリューションと一致します

(A, α)

$(A, α)$ ..。

証明（p。104）

例

超成長するシーケンスを考えてみましょう。たとえば、{1、2、4、10、20、40}。係数は、シーケンス内のすべての数値の合計よりも大きくする必要があります（例：110）。乗数は、係数と共通の除数を持ってはなりません。では、31を選びましょう。

そこで、公開鍵{31、62、14、90、70、30}と秘密鍵-{1、2、4、10、20.40}を計算しました。

次に、バイナリシーケンスを送信してみましょう：100100111100101110

公開鍵の利点のいくつか

公開鍵暗号システムを使用する場合、両者は会わず、お互いを知らず、あらゆる種類の通信を使用する可能性があります。

キーの長さ。対称暗号化では、キーが元のメッセージよりも長い場合、実際のゲインは達成されません。公開鍵暗号システムに関しては、公開され公開されているため、暗号化鍵の長さは重要ではありません。したがって、復号化キーの長さはそれほど重要ではありません（受信者は秘密の場所にのみ保存します）

歴史

長い間、バックパック暗号化システムは、NPの完全性と高い暗号化および復号化速度により、最も魅力的で有望な暗号化システムと見なされていました。多くのスキームがナップザック問題を使用します（さまざまなバリエーションで）、ここにそれらのほんの一部があります：コンパクトナップザック問題、乗法ナップザック問題、モジュラーナップザック問題、マトリックスカバー問題、グループ因数分解問題...

残念ながら、それらのほとんどは脆弱です攻撃。問題はNP-completeとして知られていますが、ナップザック問題に基づいて安全な暗号システムを設計することは簡単ではないことが判明しました。ほとんどのナップザック暗号システムはハッキングされています。それにもかかわらず、整数因数分解や離散対数とは異なり、一般的なナップザック（ソリューション）問題は、証明されたNP完全問題です。

ナップザック問題がまだNP完全である一方で、いつの日か、整数因数分解と離散対数問題を解決するために多項式時間アルゴリズムが発明される可能性があると考える人もいます。

ここにはいくつかの「しかし」があります。

第一に、NP完全性は最悪の場合の分析に基づいており、第二に、NP完全性は特定の場合ではなく、一般的な問題の特徴です。これは、平均的な複雑さを考慮すると、ナップザックの問題は単純になる可能性があることを意味します。

この資料は、この文献に基づいて作成されました。

（1） A.Salomaa。パブリックキー暗号化。 --Springer-Verlag、1990年。--p。 75-82、pp.101-111

（2）ミンキンライ。Knapsack Cryptosystems ：過去と未来-カリフォルニア大学、2001

（3） Baocang Wang、Qianhong Wu、YupuHu。ナップザックベースの確率的暗号化スキーム。2007

（4） - （5）

暗号化におけるナップザックの問題

ナップザック問題は次のように定式化されます

バックパックのアナロジー

暗号化

「簡単な」問題

「難しい」問題

公開鍵の利点のいくつか

歴史

More articles: