Loading article…
暗号学において、マークルのパズルは、 1974 年にラルフ マークルによって考案され、1978 年に公開されたプロトコルである公開鍵暗号システムの初期の構成です。これにより、事前に共通の秘密を持っていなくても、2 つの当事者がメッセージを交換することで共有秘密に同意できるようになります。
説明
アリスとボブが通信したいとします。ボブは次のようにしてアリスにメッセージを送信できます。まず、彼は多数のパズルを作成します。各パズルの難易度は中程度で、アリスが中程度の計算労力でパズルを解くことができるものでなければなりません。パズルは、未知のキーを持つ暗号化されたメッセージの形式です。キーは、ブルート フォース攻撃が可能なほど短くなければなりません。ボブはすべてのパズル (つまり、暗号化されたメッセージ) をアリスに送信し、アリスはランダムに 1 つ選択してそれを解きます。復号化された解には識別子とセッション キーが含まれているため、アリスはどのパズルを解いたかをボブに伝えることができます。これで両者は共通のキーを持ちます。アリスはパズルを解いたため、ボブはパズルを送信したためです。盗聴者 (たとえばイブ) はより困難なタスクを負います。アリスがどのパズルを解いたかがわからないからです。彼女にとって最善の戦略はすべてのパズルを解くことですが、パズルの数が多いため、イブの計算コストはアリスよりも高くなります。
高レベルの説明
- ボブは、「これはメッセージ X です。これは対称キー Y です」という内容の 2 N 個のメッセージを生成します。ここで、X はランダムに生成された識別子、Y は対称暗号化用のランダムに生成された秘密キーです。したがって、X と Y はどちらも各メッセージに固有です。すべてのメッセージは、ユーザーが各メッセージに対してブルート フォース攻撃をある程度困難に実行できるような方法で暗号化されます。ボブは暗号化されたすべてのメッセージをアリスに送信します。
- アリスは暗号化されたメッセージをすべて受信し、ランダムに 1 つのメッセージを選択してブルート フォース攻撃を行います。アリスは、そのメッセージ内の識別子 X と秘密鍵 Y の両方を発見した後、秘密鍵 Y を使用してクリア テキストを暗号化し、その識別子 (クリア テキスト) を暗号テキストとともにボブに送信します。
- ボブは、その識別子とペアになっている秘密鍵を検索します。最初にその秘密鍵を生成したのはボブだからです。そして、その秘密鍵を使ってアリスの暗号文を解読します。
盗聴者イブは、アリスからボブに（平文で）送り返された識別子 X を読み取ることができますが、各メッセージ内の X の値はランダムに生成されたため、それをボブとアリスが現在進行中の通信に使用している秘密鍵 Y にマッピングする方法がないことに注意してください。
複雑性とセキュリティ分析
パズル ゲームのパラメータは、盗聴者がコードを解読する方が当事者が通信するよりもかなり困難になるように選択できますが、Merkle パズルでは、現代の暗号のセキュリティに必要な (およびセキュリティを定義する) 難易度の大きな質的差異は提供されません。
ボブが送信したパズルの数がmで、1 つのパズルを解くのにボブとアリスの両方がnステップの計算を必要とするとします。この場合、両者はO ( m+n ) の時間計算量で共通のセッション キーを推測できます。一方、イブはすべてのパズルを解く必要があり、それには O( mn ) の時間がかかります。m ≈ n の場合、イブの労力はアリスとボブに比べてほぼ 2 乗の計算量になります。つまり、イブの計算時間は彼らの計算時間の 2 乗のオーダーになります。したがって、n は、 アリスとボブが計算を実行できる程度の大きさでありながらイブの能力を超えているように、十分に大きい値に選択する必要があります。
二次複雑度は、通常、実際の暗号アプリケーションでは、攻撃者に対して十分に安全であるとは考えられていません (または、反対に、m,n が大きい場合は、参加者にとって十分に便利であるとは考えられていません)。ただし、この方式は、公開鍵暗号の最初の例の 1 つであるという特徴があり、離散対数問題に依存する、はるかに高い複雑度を持つDiffie-Hellman鍵交換プロトコルのインスピレーションとなりました。
2008 年に、Boaz Barakと Mohammad Mahmoody-Ghidary は、この二次境界は改善できないことを示しました (「Merkle パズルは最適です」)。
参考文献
- Merkle, RC (1978年4 月)。「安全でないチャネルでの安全な通信」。Communications of the ACM。21 ( 4 ) : 294–299。CiteSeerX 10.1.1.364.5157。doi :10.1145/359460.359473。 [pdf]
外部リンク
- ラルフ・マークル『安全でないチャネルでの安全な通信』（1974年）：アイデアとその出版の歴史、1995年のインタビュー付き、アーンド・ウェーバー編
- Ralph Merkle、カリフォルニア大学バークレー校の CS 244 の 1974 年プロジェクト提案。
- ラルフ・マークル、1975 年 12 月 7 日、「安全でないチャネルでの安全な通信」