質問: 暗号化されたデータを鍵無しで復号(クラック)する場合、 何をもってして復号完了と判断できるんでしょうか。 南京錠ならU字が外れますし、ダイヤル金庫ならカチャ!っとイイ音がするw と思うんですが、 暗号を破る場合、何を答えとして目指すんでしょうか。 特定の暗号化アルゴリズム限定ででも構いませんし、 クラック復号のアルゴリズムについてというのがあれば(こっちのがいい)そ れでも構いません。
回答: 暗号屋見習いが, 勝手に補足と回答に参りました. 1. makotonyaさんの回答の補足 2. Sampoさんの回答の補足 3. 本題 と三部構成です. 長いです. #### makotonyaさんの回答について. 4. makotonyaさんの説明が*不正確*なので, 補足しておきます. google:RSA暗号で調べれば一発ですが. まずmakotonyaさんの説明では, 共通鍵暗号と公開鍵暗号が同じものとして扱われています. しかし, 共通鍵暗号と公開鍵暗号は, **違うもの**です. 素因数分解が出てくることから, 公開鍵暗号の中でも特にRSA暗号のことを話されていると思われます. 正しく書き直すと以下の通りです. ##### makotonyaさんの回答の書き直し RSA方式~~この方式~~では公開鍵~~共通鍵~~と秘密鍵を使います. 公開鍵~~共通鍵~~は公開し, 秘密鍵は自分だけの秘密です. 公開鍵を使って暗号化すると, 秘密鍵でしか復号できません. 作り方. 1. 大きな素数p, qを用意します. 2. これを掛け合わせてn=pqとします. 3. φ(n)=(p-1)(q-1)を計算します. 4. 適当な自然数, eを選びます. 5. de ≡ 1 (mod φ(n))を満たす, 自然数dを求めます. 6. 公開鍵は(n,e), 秘密鍵はdです (または秘密鍵として, (p,q)の場合も). (本当は, 素数p,qや秘密鍵にも条件があるのですが, 省略します) * 暗号化 + 平文をm(自然数)とする. 暗号文は!m^{e} \bmod{n}. * 復号 + 暗号文cとする. 平文は!c^{d} \bmod{n}. 参考リンク先として, を挙げておきます. JavaScriptでの実装例があります. この方式では, 公開鍵~~共通鍵~~の解析に成功すれば, 秘密鍵を作れます. nを素因数分解できる→p,qが分かるのでφ(n)が計算できる→eとφ(n)からdを計算できる. 公開鍵~~共通鍵~~を構成する巨大な数値の素因数分解(数学の用語)に成功することが, クラックの成功を意味します. (嘘です. 「RSAを解読できるならばnの素因数分解ができる」ということはRSA発祥以来, 未だに示されていません. 暗号学上の重要な未解決問題です.) 公開鍵の一部~~共通鍵~~には, 二つの素数を掛けた値が含まれています. (n=pq) 公開鍵~~共通鍵~~の解析とは, 二つの素数を特定することです (先に挙げたようにこの行は嘘です). この素因数分解に成功すれば, 秘密鍵を作れます (これは正しい). 秘密鍵の作り方は, 長くなるので, ここでは触れませんが, 共通鍵暗号方式をネットで検索すれば, 分かり易いホームページが見つかります. 共通鍵で検索して, RSAが引っかかるんですかね? #### Sampoさんの回答の勝手な補足. 公開鍵暗号の暗号化関数をEと, 復号関数をDと書きます. また, 公開鍵暗号の公開鍵をpkと, 秘密鍵をskと書きます. nekotenさんがコメントに書かれているのは, 「共通鍵Kを公開鍵暗号pkで暗号化したC=E(K,pk)を貰って, 共通鍵K'を求めた場合に, K'=Kかどうかを確かめる手段はあるのか?」 という話です. Sampoさんが言われているのは, 公開鍵pkから秘密鍵(らしきもの)sk'を求めた場合, 適当な平文mを持ってきてm=D(E(m,pk),sk')かどうかを確かめるという話です. これを何回か行っても大丈夫ならば, sk'=skということになり, 正しい秘密鍵が求められたことになるでしょう. 従って, D(C,sk)=Kとして, K'=Kかどうかを確かめればよいということになります. > > 逆にすぐ入手できる公開鍵を使って秘密鍵も求められる > > > ということはそうそうありません. 勿論, ダメな暗号ならそういうこともありますが(; ́Д`) #### 本題 理論では, 目標を大きく四つに分けます. 1. 完全に解読できる or 秘密鍵を得る 2. 一部の暗号文なら解読できる 3. 二つの暗号文を見分けられる (解読すらしていない場合がある) 4. ある暗号文から別の暗号文を作ることができる (こちらも解読すらしていない場合がある) 安全性を定義するときに, このような目標を使うんですが, これには勿論I/Oが必要です. 定義を挙げてから, 何故それが必要か述べます. 3に関する定義の例を挙げます. 敵A=(A1,A2)は以下の動作をする. * A1 + Input1: pk + Output1: m0 , m1, s - m0, m1は平文. sはA2への引継ぎ情報 * A2 + Input2: C=E(mβ, pk), m0, m1, s - ただしβは0 または 1. 確率1/2 + Output2: β' = 0 or 1 Aが解読(正確には識別)に成功するとは, !\Pr\[\beta'=\beta]である確率が高いと定義する. (Output2で出てきたβ'がβと等しいならば, 敵Aは二つの暗号文を見分けている) さて, A2へのInput2を作る際に, βを選ばなくてはならず, 暗号化も行う必要があります. これはI/Oを必要としています. どうしてこんなことをするかというと, 仮定なしには, 安全な公開鍵暗号が存在しないからです (おそらくP!=NP問題が解決するまで). 一般的に公開鍵暗号の安全性を示す場合には, なんらかの数学的な仮定(例:素因数分解は難しい)を置いて, 「暗号が解読できる→数学的な問題が解ける」という帰着を使います. (対偶を取れば「数学的な問題が解けない→暗号が解読できない」になります). この帰着では, コンピュータが, 先ほど挙げた敵Aを使いながら数学的な問題を解きます. このコンピュータは大抵の場合, 敵Aが成功したかどうかを判断したり, 先ほどの暗号文Cに数学的な問題を埋め込みます. 敵Aが自分ひとりで何から何までしてしまった場合には, 帰着も何もコンピュータは手出しできません. 従って, 敵Aの定義にはI/Oが存在するわけです. #### 追伸: 最近のスタンダードはIND-CCA2という安全性です. これは, 先ほどの敵Aがいつでも復号オラクルを使えます (復号オラクルは暗号文を質問すると平文を教えてくれる. ただしInput2中のCは質問できない). 実際, 「素因数分解が出来ない」や「離散対数問題が解けない」といった仮定から, IND-CCA2安全な公開鍵暗号が構成できます. こういった安全性の関係が知りたい場合には, M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway. "Relations among notions of security for publickey encryption schemes." In CRYPTO '98 を参照してください. 定義もすっきりしています. Full PaperはBellareのサイトにあります. 日本語の専門書だと ![現代暗号 (シリーズ・情報科学の数学)]( "現代暗号 (シリーズ・情報科学の数学)") 現代暗号 (シリーズ・情報科学の数学) * 作者: 岡本 龍明 山本 博資 * 出版社/メーカー: 産業図書 * メディア: 単行本(ソフトカバー) ![現代暗号の基礎数理 (電子情報通信レクチャーシリーズ)](http://ecx.images-amazon.com/images/I/41T04JDZ4GL._SL160_.jpg "現代暗号の基礎数理 (電子情報通信レクチャーシリーズ)") 現代暗号の基礎数理 (電子情報通信レクチャーシリーズ) * 作者: 黒沢 馨 尾形 わかは * 出版社/メーカー: コロナ社 * メディア: 単行本 辺りに専門的な話が載っていたと思います. 長文ですいません(; ́Д`)