講義(3)Advanced Topics in Cryptography

講義紹介シリーズ第3回。
Advanced Topics in Cryptographyなる講義。
暗号(Cryptography)についての話。
Advancedと謳ってはいるが英語で講義を聞くというのが一番の目的で
初歩的な話をされる、ということになっている。

使っている教科書はこちら。

A Computational Introduction to Number Theory and Algebra

外国の専門書はこんなふうにフリーでダウンロードできるものがあるんですね。
iPadに入れて使っています。
また一つiPadの有用性が上がりました。

話が逸れました。
この講義、最終的にはRandomness extractorなるものに行き着くようです。
Randomness extractorとは、semi-randomなインプットから
完全にランダムなアウトプットを得る関数のこと。
暗号の分野においては、鍵を得るために重要な役割を果たすようです。

暗号の鍵というのは暗号を復号(decrypt)するためのとっかかりのようなものです。
たとえば。
小学生の時、かわいらしいたぬきのイラストが入った手紙がまわってきましたよね。（いやないか）
その文が次のようなものだったとします。
「すたずきはさとうたがたすき」
この文から「た」を抜いて読むと
「すずきはさとうがすき」
鈴木さんという女の子が、どうも佐藤くんという男の子の事が好きらしい、という
子供らしい、微笑ましい（？）内容です。
この場合は「た」を抜く、たぬきが鍵だったわけです。

もう少しまともな例を。
シーザー暗号というものがあります。
これはどのようなものかというと
ルールに従ってあるアルファベットを別のアルファベットに置き換えます。
たとえば、aというアルファベットを意味する文字はb、bを意味する文字はc
と、ある文字を意味するとき、1つ次の文字に置き換えることにします。
＜a,b,・・・,z＞→＜b,c,・・・,a＞
なので「code」という平文は「dpef」という暗号文になります。
このとき、このシーザー暗号の鍵は「1」です。
ある暗号文がシーザー暗号によって暗号化されているとわかっている場合
何文字次の文字に置き換わっているかということがわかれば復号することができます。
この数がシーザー暗号の「鍵」です。

ある暗号文について
(1)何の暗号を使っているのか
(2)鍵は何か
ということがわかれば復号できます。
使える暗号は限られていますので、鍵をわかりにくくすることが非常に重要なのです。
そこで先述のRandomness extractorを使いましょう、ということになったのですね。



ところで、ランダムって何でしょう？
よく無作為の意味で使われています。
たとえば私には1/10000秒を知覚する能力はありませんので
ストップウォッチのスタートボタンを押して、少し経ってからストップボタンを押したとき
表示された時間の1/10000秒の桁の数字はランダムに得られたと言えます。
得られた数字を記録し、同じことを繰り返せば数のリスト（乱数表）が得られます。
私はこのリストの数がランダムに得られたものだということを知っていますが
この数の生成過程を知らない別の人が見た時
どうやってそれが乱数表だとわかるのでしょうか？
つまり、ランダムの判定法は存在するのでしょうか？
ランダム判定法を作ろうと思ったら
ランダムの定義は、無作為だけでは不十分です。

岩波数学入門辞典には
「一般には、独立で同じ分布に従う確率変数の実現値とみなせる数列」
となっており、生成課程を知らなければランダムか否か判断できないことになっています。

擬似乱数の生成アルゴリズム、なんてものもあるらしいので
ランダムについて、何かわかっていることがあるのだろうと思います。
その辺もおいおい勉強していきたいなぁ、とは思いますが、いつになることやら。
私は基礎がなっていないので、まずは基礎を勉強します。