Pythonianの計算機科学学習物語

今まで触れてこなかった数学、計算機科学、統計に社会人になってから惹かれた人間の物語

色で学ぶ IT, 計算機科学, 暗号技術, ハッキング

プロローグ

林檎に歯を当てるとサクッと音がなり、かすかに感じる雪の香りは、遠い故郷を思い出します。すみれは上京して大学の情報科に入ったはいいものの、所属する研究室は恋愛禁止で、同級生であり密かに交際している道彦とは常に息の詰まる思いで過ごさなくてはいけません。先日、交際一年記念日に道彦から秋の花をあしらった花束をもらい、大事に部屋に飾っていますが、愛でるたびに胸が苦しくなります。

研究室の教授はかなり厳しく、彼が交際の証拠をつかんだとき、そのカップルを即座に退学処分にします。自分にも厳しい教授はもし冤罪をかけたとき、その責任を取るため辞職するそうです。これまで教授が冤罪をかけたことはなく、研究室内のかつてのカップルは皆確かな証拠をつかまれ蝉のごとく虚しい愛の抜け殻のみが世に放たれているといいます。すみれはこの息苦しさを少しでも癒すべく、どうにか道彦とイチャイチャする方法を考えます。想いを伝えるための方法としてはモールス信号や手話などありますがすぐにばれるでしょう。すみれはどうしたらいいのでしょうか。


一章. Color

秋朝の肌寒さに嫌気がさしても外に出れば紅葉が目の前に広がり、お店には色豊かな果実が売り出され、夜になれば綺麗な月が浮かびます。この色の癒しは自然からの慰めのように感じます。すみれは色を使って想いを交わす方法を思いつき以下の対応表を作成して道彦に提案しました。

意味
#191970
疲れた
#d2691e
休憩
#87ceeb
気楽に行こう
#228b22
帰ろう
#ffd700
了解
#dc143c
最高
#708090
悲しい
#adff2f
嬉しい
#b22222
おこ
#fff352
楽勝
#6b395f
無理
#f39800
それな
#ff69b4
愛してる

独自の信号を定義することで、なにかしらのメッセージだと悟られてもその内容まではわからないと考えたのです。これならチャットで色によるコミュニケーションが可能です。#(シャープ)から始まる文字に気が付いたでしょうか。これについては、あとで解説します。


ある日、教授は偶然対応表を発見し、道彦とすみれを交際容疑にかけました。対応表は秘匿されていなかったのです。教授は二人の色をやりとりを監視することにしました。「愛してる」のやりとりを発見したとき、それを証拠として退学させます。

一方で、対応表の存在が知れたとわかってもすみれと道彦は冷静でした。なぜなら、二人の色のやりとりは対応表にない色だったからです。

二人のチャット

すみれ 道彦
ふ~やっと終わった!
#51843c
今日の探索アルゴリズムできた?
おつかれさま
#183641
#f4c1f5
#80971e
そういえば「アレ」もうそろ始まるらしい!
#def031
そうなんだ
#af1b22
それで思い出したけど前話してたやつ考えといてね!
#8cd81e
#af1b22
今日はつかれたな~
本当におつかれ
#51843c
#51843c

二章. Order

もうすぐ日が暮れようとしていますが、その感覚と時計の針の位置は一致しません。もう外は薄暗いのに道端の小さな公園ではしゃぐ子どもたちは未だに帰ろうとしません。不調和な感覚でコンピュータを眺める教授はしかめっ面でいまのところの推理をまとめます。

道彦とすみれは、対応表が見つかると盗聴されることがわかっていたので色フィルムのようなものを用意しました。色のメッセージを送る際はそのフィルムを重ね、色を受け取った側はフィルムを取ることでメッセージを認識します。これなら誰かが送信中の色を盗んでも、フィルムの色がわからなければ、本来の色を知られることはありません。

このコミュニケーションを具体例で説明します。

勉強で暗記のために参考書に緑のマーカーを引いて、赤シート(暗記シート)で隠すというようなことをやったことがあるのではないでしょうか。ここでは、緑のマーカーが色のメッセージ、赤シートが色フィルムになります。送信する際は赤シートを重ね、受信したほうは赤シートを取ります。

単純に色フィルムを重ねるのであれば規則性があるので、内容の予測は可能なはずです。

暗記シートの例で言えば、赤シートを重ねた際、緑の部分は暗くなりますが、周りは赤っぽくなります。ここから、フィルムは赤色で、暗いところは緑だという予測ができます。

色フィルムを重ねるということが二つの意味を持つということも解説しておきます。

色には二通りの混色法があります。色を重ねると明るくなる(加色)か暗くなる(減色)かです。光は加色法、絵具は減色法です。暗記シートは減色法になります。

ここでは加色法を「色の足し算」、減色法を「色の引き算」とします。

ここで#(シャープ)がついた文字の意味について解説します。

#がついた文字の意味

これは、文字(数値)で表された色です。

文字
191970
#191970

文字を三つに分解し、それぞれが光の三原色、赤、緑、青となります。

文字
191970 19 19 70
#191970

数字が大きくなるほど、その色の成分が強くなります。

文字
191970 19 19 ff
#1919ff

加色法なので、他の色を大きくすると明るくなります。

文字
191970 99 99 ff
#9999ff

fという文字に気がついたでしょうか。これは十六進法と呼ばれる数字の数え方をしたときの数です。

私たちは 0,1,2,3,4,5,6,7,8,9 の十個の数字(十進法)で物を数えていますが、コンピュータの世界では桁数を少なくするために十六進法を使うことがあります。

十六進法では0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,fの十六個の数字を使います。a(十六進法) = 10(十進法), f(十六進法) = 15(十進法)です。

数なので引き算、足し算が可能です。

  • f - 5 = a

十六進法の繰り上がりは少し馴染みづらいかもしれません。私たちが普段使う数字の場合、9の次の数は、繰り上がって9は0に戻り、二桁目に突入します。

  • 9の次は10

十六進法では、fの次が繰り上がりです。繰り上がりのとき、fは0に戻り、二桁目に突入します。

  • 9の次はa

  • fの次が10

  • 十六進法における10は、f = 15(十進法)なので16(十進法)です。

混乱しているかもしれませんが、二桁目や三桁目がfに近づくほど数は大きいということは認識しておいてください。

ff(十六進法)255(十進法)ということも覚えておくといいかもしれません。


教授の推理に戻ります。

実際に色フィルムを重ねてみましょう。

赤、緑、青それぞれで足し算もしくは引き算をします。

色フィルム
#362606
処理 結果
#4f692e + #362606 #858f34
#4f692e 4f 69 2e
+ #362606 36 26 06
= #858f34 85 8f 34

いろいろな例でやってみます。

足し算

処理 結果
#4f692e + #362606 #858f34
#1ba136 + #362606 #51c73c
#444891 + #362606 #7a6e97
#827f3c + #362606 #b8a542

引き算

処理 結果
#4f692e - #362606 #194328
#1ba136 - #362606 #007b30
#444891 - #362606 #0e228b
#827f3c - #362606 #4c5936

チャットで使われた色から、全体的に何かの色味が増したり、明るくなったり、暗くなったりしているでしょうか。

二人のチャット

すみれ 道彦
ふ~やっと終わった!
#51843c
今日の探索アルゴリズムできた?
おつかれさま
#183641
#f4c1f5
#80971e
そういえば「アレ」もうそろ始まるらしい!
#def031
そうなんだ
#af1b22
それで思い出したけど前話してたやつ考えといてね!
#8cd81e
#af1b22
今日はつかれたな~
本当におつかれ
#51843c
#51843c

まず、チャットにはとても明るい色ととても暗い色があります。全てが足し算もしくは引き算という可能性はなさそうです。足し算と引き算を併用しているかもしれません。複数のフィルムを使っている可能性もあります。

色の足し算、引き算について長々と解説しましたが、当てはまらないようです。

ですが、どのような演算をしたらチャットのような色になるのでしょうか。

色ごとに別のフィルムを使ったり、足し算と引き算を併用していたとして、それらのパターンすべてが彼らの頭の中にある場合見破る方法はありません。完全に秘匿されています。すべて暗記することは不可能ではありませんが効率も悪いですし大変でしょう。その力を研究に使ってほしいものです。

二人がカップルである可能性は高いですがなかなか証拠をつかめません。文脈から当てはまりそうな色はありますが、確証は持てません。 頭を抱えていると道彦からメールが来ました。

「使っているフィルムは一つですよ。」

少し考えた後、教授はうすうす感じていたことを確信に変えました。彼らの本当の目的は冤罪をかけさせることだと。


三章. Lover

遠くから眺める紅葉は色豊かで綺麗ですが、落葉を近くで見ると黒い斑点がブツブツ見えます。近くで見ると案外汚いものなのでしょうか。否、この少し汚い斑点こそが遠くで見たときの紅葉の色に深みをもたらしていると考えられます。ちょっとした「ノイズ」が深みを持たせているのです。

そんな仮説をブツブツ呟く道彦は、色のメッセージによるコミュニケーションは名案だと思いながらも、やはり不安を抱いていたので、送信する前に色を変える方法を模索していました。

色とメッセージの対応を定義したとしても、対応表がばれたら意味がありませんし、規則性がわからないように色を変えるにしてもさまざまなパターンを覚えるのは無理がありました。

そもそも、在学しながらカップルでいられる方法はもう一つあります。

教授が辞職することです。自分にも厳しい教授に冤罪をかけさせ辞職に追い込めばいいのです。

道彦は色フィルムを作成し、「排他的論理和」という演算で色を変える方法をすみれに提案しました。

排他的論理和」とは、数学の論理演算で、ある二つの命題のうち、片方だけが真の時に真とする論理演算です。

命題1 命題2 結果
× × ×
×
×
×

この演算の性質として、命題1 → 命題2 → 結果と読んだとき、逆から読んでも排他的論理和が成立する性質があります。

結果 → 命題2 → 命題1

結果 命題2 命題1
× × ×
×
×
×

この演算を一体どのように今回の色変えに置き換えるのでしょうか。

色を数字で表すことはできましたが、数字は○×ではありません。

一応、形式として流れを示しておきます。

色(命題1) → 色フィルム(命題2) → 暗号色(結果)

逆から読んでも成り立てば、良さそうです。

暗号色(結果) → 色フィルム(命題2) → 色(命題1)

一体どういうことでしょうか。

色を○×に置き換える

コンピュータは0か1しかわからないというのを聞いたことがあるのではないでしょうか。

コンピュータは、0と1で、二進法と呼ばれる数え方で数を定義しています。

1の次の数は、すぐに繰り上がり、10となります。(= 2(十進法))

10の次の数は、11です。(= 3(十進法))

11の次の数は繰り上がって100となります。(= 4(十進法))

二進法はそういう数え方をします。

一方で、0と1を×と○として見ることも可能です。

コンピュータは0か1しか分かりませんが、0と1でいろんなことを定義することが可能なのです。

もちろん、色も0と1で定義しています。

ここで、0を×、1を○としましょう。そうすると排他的論理和は以下のように表せます。

命題1 命題2 結果
0 0 0
1 0 1
0 1 1
1 1 0

これらの考え方をミックスすることで、数字を○×に置き換え、排他的論理和を求めることができます。

十六進法 十進法 二進法 ○×
命題1 e 14 1110 ○○○×
命題2 b 11 1011 ○×○○
結果 5 5 0101 ×○×○

足りない分は0で埋めます。

そして、○×のそれぞれの桁同士で排他的論理和を求めます。

色は十六進法の数で表せるので、○×に置き換えて、排他的論理和を求めることが可能なことが分かります。

色(命題1) → 色フィルム(命題2) → 暗号色(結果)

暗号色(結果) → 色フィルム(命題2) → 色(命題1)

道彦は、色フィルムとして絶対に忘れない二人だけの色を決め、それを「鍵」としました。色を送る前に一度、メッセージの色と鍵の色の排他的論理和を求めます。その結果が暗号色です。

排他的論理和の性質から、暗号色と鍵の色でもう一度排他的論理和をとれば、元のメッセージの色を取り出せます。

これで、送信中に誰かに暗号色を見られても、色フィルムの色がわからなければ元の色を求めることはできません。

暗号化と、それを元に戻すとき(復号化)に共通の鍵を使っているため、これはまさに「共通鍵暗号方式」と呼ばれる暗号技術です。

道彦とすみれは、鍵の色として道彦が一年記念日にあげた秋の花束にあった吾亦紅の色を選びました。


四章. Solver

夕食は何を食べようか悩みながら帰り道を歩いていると秋刀魚を焼くいい香りが住宅街を包みます。「これだ」とお腹を鳴らしながら教授は自宅玄関のカギを開けます。

教授は、暗号化に使っている鍵が一つならば、共通鍵暗号方式を採用している可能性があると思い当ります。

色を十六進法の数に置き換え、それを○×に置き換えたとき、○×の数は24個になります。

十六進法 二進法 ○×
#fff352
fff352 111111111111001101010010 ○○○○○○○○○○○○××○○×○×○××○×

○か×の状態が24個あるので、組み合わせ(鍵の総数)は2の24乗通りあります。それは約1677万通りですが、総当たりで鍵を求めたとしてもコンピュータは最も遅くても数秒で特定できます。カタカタとプログラムを書くキーボードの音、PCのファンの音、外の冷たそうな風の音が薄暗い部屋に静かに響き渡ります。

以下が教授が作ったシミュレーションになります。全ての色が対応表にある色の場合、その時の色フィルムが鍵となります。

チェックボックスをチェック状態にしてスタートボタンをクリックすると、総当たりで解析を始めます。 スマホやPCによっては時間がかかるかも知れません。(遅くても1分で終わるとは思います)。途中で止めたい場合は、チェックボックスを外してください。 見つかれば「got it!」というメッセージが出てきます。

対応表

二進法

総当たり

解析する
二進法
鍵: 000000 | 000000000000000000000000
↓ xor
二進法

バックトラック法

今回のような、使われるメッセージがあらかじめわかっている場合は「バックトラック法」と呼ばれるAIで広く使われるアルゴリズムでも解くことができます。

これは簡単に言えば、総当たりと同様、力任せに組み合わせを作って行くアルゴリズムですが、

ある組み合わせがダメだとわかった時点で順調に進んでいたところまで戻り(バックトラック)、別の組み合わせに進みます。

そうやって徐々に答えに近づくのがバックトラック法です。

今回の場合、排他的論理和の性質を使って、バックトラック法による解読ができます。

先ほど、排他的論理和の性質について以下のような説明をしました。

この演算の性質として、命題1 → 命題2 → 結果と読んだとき、逆から読んでも排他的論理和が成立する性質があります。

結果 → 命題2 → 命題1

結果 命題2 命題1
× × ×
×
×
×

実は、結果 → 命題1 → 命題2と呼んでも成立します。

結果 命題1 命題2
× × ×
×
×
×

今回の場合に置き換えると

暗号色 → 色 → 色フィルムとなります。

色フィルムは一つだけですので、下のシミュレーションのように、チャットで使われた色に対してあらゆるメッセージの色を割り当てて行き

それぞれの排他的論理和の結果が全てが同じになれば、その結果が鍵となります。

総当たりと比べると一瞬で終わります。

解析する
暗号色 色フィルム

PCからであれば、本ページのソースからロジックを確認することができます。

エピローグ

秋の昼の雨上がり、日差しの反射で光る落ち葉が公園の道に広がっています。教授は湿気と土臭さを含んだ空気を深く吸いながら昨日の推理と結果を思い返します。

道彦とすみれの暗号は見事に突破されました。

しかし、二人のやりとりに「愛してる」はありませんでした。

教授は肺に溜め込んだ空気を一気に吐きます。

彼らはただ単に教授を辞めさせようとしていたのです。

教授はその本気さに恐ろしさを感じつつも、愛のメッセージがやりとりされていないことに心が痛みました。

今年初めて作った自分のルールがどれだけ人を苦しくしていたか理解しました。

教授は暗号リテラシーを学ばせるため、ばれたら終わりというプレッシャーを与えるためにわざと恋愛禁止ルールとウソの伝説を作りました。もし見破ったとしても退学にはせず、どうすればよかったかを教示するつもりでした。

教授は少し泥のついた美味しそうなさつま芋を3つ買って、研究室に戻ります。


ところで、暗号化に使われた鍵こそが愛のメッセージだったことを教授は知る由もありません。

すみれは、二人だけの特別な色で暗号化するという提案に一番の愛を感じていたのです。


補習

二人はどうすれば暗号を突破されなかったか

○×の個数を増やす

今回の場合、例えば単語ごとに色を対応させます。

単語
I
you(r)
him, he
it(s)
miss
pass
take
check
time
out
easy
difficult

そして三つの単語でメッセージを作ります。

メッセージ
take it easy
it takes time
check it out
difficult to pass

愛のメッセージを伝えるとしたら、"I miss you"でしょうか。

三つの単語であれば、使うフィルムは三色なので、○×の個数は72個になり、特定には時間がかかります。 (2の72乗なので4,722,366,482,869,645,213,696通り)

take him out(彼をヤれ) という文も簡単には特定できないでしょう。

AES(Advanced Encryption Standard)と呼ばれる共通鍵暗号アルゴリズムは、128ビット・192ビット・256ビットのブロック単位でデータを暗号化します。これを突破するには途方もない時間がかかります。

使い捨ての鍵を使う

ワンタイムパッドと呼ばれる手法です。

道彦とすみれの暗号化が不完全な理由として、鍵の大きさが小さいという他に、鍵が一つだけしかないというのがあります。

ランダムな共通鍵で暗号化、復号化を行えば、暗号文から平文を特定することはできません。

全ての鍵が違う場合は、完全な秘匿です。使い回しは、突破される恐れがあります。

暗号化の失敗の国家的な例があります。

1930年代のソビエト連邦は、通信の暗号化にワンタイムパッドを使っていました。しかし鍵につかうbit(◯×)を使い果たしたため、bitの使い回しをするようになりました。イギリスはVENONA計画の中で偶然それを発見し、通信の一部を解読することに成功しました。これにより、ソ連のローゼンバーグ夫妻によるスパイが判明しました(ローゼンバーグ事件)。

Pythonianの計算機科学学習物語

自己紹介

こんぺいとうです。社会人2年目です(2019年10月時点)。

大学では中学の美術教育を学んでいましたが、趣味でプログラミングに触れてその面白さに惹かれたため、プログラマになりました。

社会人2年目で競技プログラミングに出会い、アルゴリズムを学ぶ中でプログラミングと数学の関連性に驚き、プログラミングがもっと好きになってしまって今は学びたいことが多くて追いきれません。

数学については、高校で対数や行列をやらなかったし、大学でも数学は一切やっていなかったので大変ですが学ぶのはとても楽しいです。

これから今勉強している数学のことやアルゴリズムのこと、統計のこと、プログラミングの文化的なところなどを書いていきたいなと思っています。

今勉強していること

1年以内には何かしらの機械学習のアプリを開発したいです。

好きな言語とその理由

意味の通りやすさや新しい表現方法に惹かれます。

プログラミングはあくまでツールという意見はわかりますが、「そんな表現があるのか」と感動することは多いです。

それが私にとってのプログラミングの楽しいところです。

簡単な記述。数学的記述。

右半開区間、内包表記、直積など

ranks = ['A', *map(str, range(2, 11)), 'J', 'Q', 'K']
suits = ['♠︎', '♣︎', '♡', '♢']
deck = [(rank, suit) for rank in ranks for suit in suits]

プログラマーフレンドリーな構文。

class String
  def txt
    self.include?(".txt") ? self : "#{self}.txt"
  end
end

file = "file_name"
puts file.txt

今はHaskellとRustとScalaにも惹かれています。

私の中で関数型言語、メモリ管理、JVMが今はアツイです。

プログラミングについての、思わずうなずくような面白い記事をかけていけたらいいなと思います!