逆転ホームラン！(大阪的な意味で

どうもー。約一ヶ月ぶりの更新です・・。生きてます

ちょっと私生活の方がどたばたしてました。
また少しずつ更新したいと思います。
話は変わりますがここのブログ、一番よく検索されているのが
「データベースの作り方」
なんです。
・・なぜ？
まぁ、mysqlとか一緒に検索されている方もおられるようですし、そのうち時間とって環境の作り方とテーブル構造のtipsでも書こうかなとは思います。sqlのチューニングとかのが需要あるかな？

で、今回はここのところ考えていた暗号アルゴリズムについて書きたいと思います。
最終的には失敗してますが・・

今回考えていたのは、グラフ理論を基にした暗号でした。
エディットグラフアルゴリズムを調べがてらグラフ理論の本を読んでいて、ハミルトン閉路を利用した暗号が出来ないかなーって思ったんです(多分探せばいっぱい出てきそうな気はします)。

つまりある(有向ハミルトン閉路を含む)グラフと任意の有向ハミルトン閉路のセットを鍵とします。
まぁ始点は鍵に含むか、通信でやり取りすればいいです。
グラフの各点には適当な数字がセットされています(連番でもいい)。で、平文を暗号化するときは一文字につき一個ずつノードを手繰ってそこにある数字と排他的論理和をとればいいと思ったんです。
あるグラフがあるとき、そのハミルトン閉路を多項式時間で探すアルゴリズムは一般に知られていませんから。
まぁこの段階では鍵に閉路自体も含まれていますが・・。

で、どうやってハミルトン閉路をひとつ以上含むグラフを生成するか、ということに思い至りました。これは簡単ですね。N個の点を用意して、適当な始点からランダムにほかの点にどんどん(被らないように)移動させていけば。で、最後にダミーとして適当な点同士を引っ付ければいいわけで。

で、まぁ思ったんですよ。
・・つまりこの暗号の強度はこの段階で使用する擬似乱数の強度と等しい、と。
ということは、その擬似乱数列で最初から排他的論理和をとった方が断然計算コストが小さくてすみますよね。ってわけで没

これはもうちょっと考えたい問題ではありますね。そのうち続きを書きたいと思います。
タイトルの大阪は春日歩のことです。逆転ホームランやっ!・・と、言いたい。