セルオートマトン暗号(未完)

遅刻してますが、この記事はセルオートマトンアドベントカレンダーの23日目の記事です。

あらまし

 離散的な力学系であるところのセルオートマトンは、カオス的なふるまいをすることで知られています。カオス的であるなら、そのふるまいを暗号学的なアレとかソレとかに利用できるのでは…、とはもう研究があるようですがここでは割愛。いっぽうで、セルオートマトンの中には可逆性をもつものがあります(ここらへんも研究がありますが割愛)。

 あとは…わかるね?

 ということでとりあえずElementary Cellular Automataを用いてガッとメッセージの暗号化・複合化を実装しようとしたけど3時間ではだめでした、という残念な記事です。ざんねん。

ソースコード

文字をつらつら書くほど内容はないのでさっさとソースコードを示します。ひさしぶりにビット演算をキメた気がする。以下のことはできています:

  • 局所遷移関数をルール番号から生成(コンパイル時に)
  • 周期的境界条件(キアイで)
  • なんとなく様相を指定回数ぶん遷移
  • ファイルをビットベクタにしてECAの様相に変換しブンまわす

gist.github.com

使用感

 なんとなくこんな感じになります。

CL-USER> (let ((vec (vector 0 0 0 1 0 0 0 1 0)))
           (run 10 vec (make-array (length vec))
                (make-local-transition-fn-from-rule 150)))
#*000100010
#*001110111
#*110100010
#*000110110
#*001000001
#*111100011
#*111010101
#*110010100
#*001110111
#*110100010
#(0 0 0 1 1 0 1 1 0)

 なんとなく大域遷移はできていそう。Roswellスクリプトにしておいたので、引数にファイル名を与えるとファイルの内容で遷移してくれます。しかしビットベクタをバイトベクタとして書き出してしまっているので出力はおかしいですがもうつかれました。

まとめ

 このセルオートマトンという分野、人工生命というだけではなく暗号学の方面の研究もあり、さらに情報の圧縮や、果ては様相の遷移を群と見なして解析する純粋数学的な分野もあり、とてもたのしそうです。やりたい。

参考文献