TakuLabo

【DISCLAIMER】
学生時代の卒研のゼミで聞いた先生の雑談がベースになっていて、僕自身暗号理論には全く詳しくないので、その旨ご了承を。
(ただ、その時聞いた話が僕的にはわかりやすく、是非その知識もここで共有しておきたいなということで、その時聞いた話をそのまま小ネタノートにまとめている次第です。)

まず要素数7の型を定義してその上に加減乗除を定義する

aaa

f7 という関数は一見無意味なものに見えるが、数値リテラルを Finite_7 型として型推論させるのに役立つ。
以下はその使用例。

aaa
この抽象的な数の構造の何が面白いのかといえば、「割り算」が定義できることである。

続いて要素数を 4091 個まで増やして同じことを考えたいが、先ほどの Finite_7 と同様にして「終対象同士の余積を(4091-1)回とって得られる型」を出発点に考えるというのは、できないことはないが常軌を逸している。

aaa

blah

(GHCi で実行する場合、f4091_quotTable の要素が参照されて初めてそのインデックスまでのリストが生成されるため、その表データの大部分の生成が要求されることになる decrypt の初回実行時は多くの時間を要する場合が多い。但し一度表データの計算が済んだそれ以降はその表データがキャッシュされるのか実行速度は大幅に向上する。)

blah

AさんがBさんに誰もが読むことが可能な掲示板を介して、秘密のメッセージのやり取りを行うことを考える。(もしくは、通信が傍受されている状態で、生データのやり取りを行うの方がわかりやすいかな aaa)

1. まず Aさんが公開する鍵 w と秘密の鍵 a を 上で定義した 0以外の Finite_4091 型の数字としてそれぞれ適当に考える
2. Aさんが、「w と \(w^a\)」の値の対を掲示板に書き込む
3. 続いてBさんもBさん側で適当に1つ秘密の鍵を 0以外の Finite_4091 型の数字として考える。
4. Bさんが、「\(w^b\)」の値を掲示板に書き込む
5. Aさんは「\((w^b)^a\)」、Bさんは「\((w^a)^b\)」という値を計算する
6. 2人の間で「\(w^{a\cdot b}\)」という値が共有される。
7. Aさんがその共有された Finite_4091 型の数字を使って、文章を適当に暗号化し、その暗号化された文字列を掲示板上に書き込む
8. Bさんがその共有された Finite_4091 型の数字を使って、掲示板上に書き込まれた暗号された文字列を解読する

有限体の持つ対数の計算 (離散対数) が困難であること (離散対数を効率的に解くアルゴリズムが現状見つかってない？) を信用し、「離散対数を計算しない限り各々が保有する秘密のカギを第三者が取得することはできない」という状況の下で、同じ鍵を共有ための手続きを公の場で行っているわけであるが、「要素が有限」である以上 Brute-force で攻める要素の数が少ないと、簡単に鍵が第三者に取得されてしまう。

例えばこの場合、使用している有限体の要素数は (理想的には) 4091 個であるので、0 から 4090 まで総当たりをすれば、公開されている鍵と、その公開されている鍵で解読しづらくした上で一緒に公開したAさんが所有している秘密の鍵の2つの情報からAさんが持つ秘密の鍵を求めることができてしまう。

デモ

■ 掲示板上でのやり取り
[1] Aさん:
(1922, 901)
[2] Bさん:
1310
[3] Aさん:
77104425597907171809503472347757382245200701302774833562681845880713480977833068391838846150030892915122782575738612968074413396903990886923672447103874151206263134727824722798692318436991702469242672191493360359987248582193438948809795896940464044070409377478392930246281390913700730282168691655364692373722836927798480599321336888512009679063914286311

■ Aさんサイド
1. なんとなく「公開用の鍵: 1922, 自身の秘密の鍵: 2095」と決める。
2. 冪 \(1922^{2095}\) を計算させたら 901 が出力された。ということで、掲示板に (1922,901) を書き込む。

3. Bさんからの応答を待つ。
4. 暗号化されたBさんの秘密の鍵の情報 q(=2467) が掲示板に書き込まれたら、\(q^{2095}\) を計算する。結果1310になった。

5. 鍵 1310 を使って適当にメッセージを暗号化し、その暗号化により得られた文字列を掲示板に投稿する。

■ Bさんサイド
1. なんとなく「自身の秘密の鍵: 221」と決める。
2. Aさんが掲示板に公開用の鍵を書き込むのを待つ。
3. 公開用の鍵と暗号化されたAさんの秘密の鍵の情報 p(=901) が書き込まれたら、まず\(p^{221}\) を計算する。結果 1310 になった。

4. 続いて冪 \(1922^{221}\) を計算する。結果 2467 が得られたので、それを掲示板に書き込む。

5. Aさんが暗号化した文字列を投稿するのを待つ。
6. Aさんが投稿した暗号を、鍵 1310 を使って復号する。すると「Hi, I'm looking forward to hanging out with you next Saturday!」というメッセージが得られた。

先ほどのやり取りを何も知らない第三者が見れば通常は「なにやってるんだろう...」で終わってしまうかもしれないが、実はこの程度の脆弱な暗号化ならば簡単に解読することが可能である。
特に、ここでは暗号化や復号化に用いている関数はオープンソースにしてしまっているため、尚更難しいことを考えることなしに解読される。

まず一つ目の方法は、誰もが思いつく力技で
「掲示板上に書き込まれた暗号化された文章に対して、とりあえずよくわからないけど様々な鍵で復号化をかけて強引に暗号化される前の文章を総当たりで探し出す」
という方法。(俗にいう Brute-force method)

以下 1から4090までの全ての鍵を使って総当たりで解読するコード

出力を全て表示するとページが非常にごちゃごちゃになってしまうので、1300 から 1350 までの範囲の出力だけ切り取ったものを載せておく。上に書いてあるように 1310 が暗号化に用いた鍵であり、行頭の数字が「1310」になっている行を見てみると、暗号化したメッセージが見つけられてしまっている。

先ほどは、暗号化された文章に対して、使用され得る全ての鍵を一つずつ使って総当たりで解読するという方法をとったが、そもそも「離散対数」の方を力技で求めてしまう方が、より確実かつシンプルに解読することができてしまう。

この方法は「鍵を行列にすることで少し複雑にしたバージョンの暗号文」に対しても有効なので、実際に離散対数を求めることで以下の謎のやり取りを解析する例を紹介する。

■ 掲示板上でのやり取り
[1] Aさん:
([1922,123,234,345], [957,2421,3608,1747])
[2] Bさん:
[2471,1541,3231,1938]
[3] Aさん:
539952015664944056884679006621635438025012612196690463284025690034444996909444080712637025364478125086313720131947018520211842297151992005605032221602604818770751095081071038528110758818254716239207122450746056039972004091122563205525514643586760435059069270705834087325374645175923517617047722706283773835970740111365833784870503944952569

見ての通り、公開用の鍵が行列になってしまったことで、先ほどのような暗号文を総当たりで解読するためには、4090 回の行列積の計算をするか、200兆以上にも及ぶ鍵の全パターンを直接愚直に調べることなどが必要となる。

という関係式が成り立ってしまうため、この事実を上手く使えば、行列が使用されていたとしてもAさんの持つ鍵を先ほどの行列でないバージョンと同様の手間 (単なる4090回のF4091型の数の冪の総当たり) で求めることができる。(見方を変えれば行列演算というのは、非常に良い性質を持つ整然としたものということ)

まず、公開用の鍵 \(W\) として与えられている行列のデターミナントを求める。

続いて、公開されているAさんの鍵の情報を含んだ行列 \(W^a\) のデターミナントも求める。

が成り立つわけなので、この離散対数を総当たりで解いてしまう。

実際に実行してみればわかるが、総当たりする数が非常に少ない分、1秒もかからぬ間にAさんの持つ鍵「2095」が取得できる。

あとは、Bさんが公開している \(W^b\) を用いて \((W^b)^a\) を求めれば、AさんとBさんが共有している秘密の行列が以下のようにして第三者によって取得されることになる。

得られた鍵を復号化用の関数の引数に渡してあげれば解読が完了である。

あああ

以下の解読を困難にさせる小細工を2点追加する
・掲示板上でのやり取りに使用する有限体のサイズを超巨大にする。具体的には \(2^{1279}-1\) 個にしたため、1つ当たりの計算に要する時間を \(3.3 \times {10}^{-12}\) 秒程度と見積もったとしても、総当たりに要する時間は1000億年とかそういう次元ではなく、\(1.1\times 10^{366}\) 年以上かかる。
・計算コストの大きい「鍵から行列を生成する関数」を用いて、共有した鍵それ自体ではなく、その関数を使って生成される行列を使って暗号化を行うことで、さらに総当たりを困難にする。(ちなみに僕の低スペックPCでは、genKeyで行列を生成するのに約3分程かかる。)

デモ2

■ 掲示板上でのやり取り
[1] Aさん:
(4323660658413665489080977455466615497073106608077519640809706763820186332620788656758741789002187781595198884215013494760277552450616114631113576227143502163034487326597845146330310725669364369699748371318511148719875220313497756298210351781962441303719564955995442174543341836373679265902025706861082632346368148860660622356381268504010225960524119642588524926836809055023993016893532, 1175855229597196446878480308674346474763046389543454835786303271587723196048831914149979453653667682477461314330661270893548199529474235759058370781105864075516242415006660186946845246923980894460902623461890150947816416893965168105879489549019777451334246881978826680077308090414337797608249485351730609439660449684476459749605583731332585396678702463344060876882351958243600266196237)
[2] Bさん:
10000256990836362893781679900109303280442746199821157549001109860448412434663150994106301540761533547769345659005910567449724927678590208297522613227036057729078868993543753424758520181952969391227400328672211669820819149526881069071770473517438047270212435633014303915300913566029877423724136154875994784999931086520700730228927074384068502705612450326567545875558766779951703772288849
[3] Aさん:
939972568540494443828708307317605838113392940345463723986715421081375238506544033374443226384497335743802157880451152405907075954468467801144133764650587598933597092227375563492957261939152259552988399270536372921406619140527893809092573658384701863758017243134841506151239163895021150225172273772520291946817259651853214854192254897
■ Aさんサイド
1. なんとなく「公開用の鍵: (1922^1922 mod 2^1279-1), 自身の秘密の鍵: (2095^2095 mod 2^1279-1)」と決める。
2. 公開用の鍵と以下の計算の出力の対を掲示板に書き込む。

3. Bさんからの応答を待つ。
4. 暗号化されたBさんの秘密の鍵の情報 q が掲示板に書き込まれたら、以下を計算する。

5. 上の鍵から行列を生成する。

6. 生成した行列を使って適当にメッセージを暗号化し、その暗号化により得られた文字列を掲示板に投稿する。

■ Bさんサイド
1. なんとなく「自身の秘密の鍵: (221^221 mod 2^1279-1)」と決める。
2. Aさんが掲示板に公開用の鍵を書き込むのを待つ。
3. 公開用の鍵と暗号化されたAさんの秘密の鍵の情報 p が書き込まれたら、まず以下を計算する。

4. 続いて以下を計算する。そしてその結果を掲示板に書き込む。

5. Aさんが暗号化した文字列を投稿するのを待つ。
6. 上で求めた鍵から行列を生成する。

7. Aさんが投稿した暗号を、生成した行列を使って復号する。すると「Hi, I'm looking forward to hanging out with you next Saturday!」というメッセージが得られた。

おまけとして、今回使ったコードを載せておく。
使い捨てコードのつもりで書いたため、識別子名の付け方やコードの組み方は本当に乱雑で適当。

Haskell は標準モジュール (Prelude) だけでも色々なコードがかけるんだぞということを色々な人たちにも認識してほしくて、敢えてそれ以外のモジュールは一切読み込まずに書いた。(「暗号化・復号化の仕組みを実践的に理解するための玩具」なのでパフォーマンスのことは一旦置いておき、標準モジュール以外のモジュールを使わずに書いているけれど、「実用向けのツール」を Haskell で書きたいのであれば言うまでもなく用途に応じたモジュールを探して活用するのが得策。)

【encrypt 関数】
1. 文字と整数を結び付け、その対応を用いて文字列を整数のリストに変換する。この時、その整数の最大値を格納するのに必要になる最小ビット数をpiyopiyoとする。
2. そのリスト内の整数を全て「長さpiyopiyoの2進数表記した文字列」に書き換え、さらにそれらすべての文字列を連結させる。
3. あるビット数 piyopiyo2 があって、そのビットを使って表現可能な整数の最大値をオーバーフローさせることなく Finite_4901 型の数として読み取れるもの内、最小のものを求める。
4. 連結して得られた文字列内の1と0を全て反転させた後、vacuous(piyopiyo2) という関数 (詳細は後述) を用いてビット列の保護を行う。
5. piyopiyo2 毎にビット列を区切り、その区切られたビットをそれぞれ Finite_4091 型の数として読み取る。
6. 鍵 を k としたとき、得られた Finite_4091 型の数のリストの (i-1)番目の要素に k^(((i-1) mod 256)+1) を掛ける。
7. 掛け算を終えたリスト内の全ての数の総和をとる。
8. 「リストの i 番目の要素」を「リスト内にある i 番目以外の数を全て足し合わせた数 (つまりは総和から自身を引いた値)」に変換する。
9. リスト内のFinite_4091 型の数を全て (piyopiyo2+1) 長のビット列に変換し、それらを全て連結する。(piyopiyo2+1: Finite_4091 型の数の最大値が格納できる最小ビット数)
10. vacuous(piyopiyo2+1) を用いてビット列の保護を行う。
11. 保護処理が施されたビット列を32ビット毎に区切ってそれぞれを整数として読み取る。この時末尾に区切りの悪いビットが残る場合は、必要分をダミーの0で埋めたものを整数として読み取る。
12. リスト内の整数を固定幅の文字列に変換する。
13. それらの文字列を全て連結して得られる文字列の先頭に'1'を添えたものを整数として読み取る。
14. その整数を9で割った時の整数部と余りに分解し、その余りに1を加えた値を文字列化したものと整数部を文字列したものとを連結して得られる文字列が最終出力となる。
(変更を加えたので以下に載せてあるコードとは異なる点がいくつか存在する)

【vacuous 関数】
建前としては、「暗号化の過程で実行している Finite_4091 型の足し算引き算によってリスト末尾に零が現れる場合があるのだが、そうなるとその後ビットの末尾に添えられる可能性のあるダミーの零の羅列との区別が付けられなくなる。この関数はその問題を回避できるようにビット列を保護するもの」。でも必要な処理以外にも余計な処理を含めている。以下詳細。

1. 入力された文字列を奇数番目の文字と偶数番目の文字に分解し、それらを連結する。
2. 連結された文字列を (width-1)文字毎に区切る。この時末尾に区切りの悪い文字列が現れる場合は、その文字列を blah と置く。
3. 区切ったそれぞれ文字列の先頭に "1" を付けて再度連結する。(こうして得られる文字列を A と置く。)
4. blah が空でない場合、blah 内の文字 c をそれぞれ「c に '0' 以外の文字を1文字以上含むようなwidth-1の長さのダミー文字列を連結した文字列」に変換し、それらをさらに全て連結する。(こうして得られる文字列を B と置く。) その後、A と B を間に「width の長さの '0'」を挟んで連結する。