FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

アルゴリズム勉強記⑦~XORの暗号とたらいまわし関数編~

今回はXORによる暗号とたらいまわし関数です。


ビットごとの排他的論理和は、

a XOR b XOR b = a

という性質があります。
aのビットを反転→ビットを反転と、逆の逆と取っているので元に戻ります。

これを利用して暗号化しようというものです。
kを鍵とすれば、平文をビットごとにkでXORすれば暗号化され、暗号文をkでXORすれば平文に戻ります。

この暗号化はシンプルでわかりやすいので、ちょっとしたゲームのセーブデータの暗号化なんかに使ったことがあったりします。


これをもう少し工夫して、鍵kをそのまま使って暗号化するのではなく、鍵kを鍵の鍵とする方法を今回はやりました。
つまり、kを乱数の種とするのです。Cのrand()は種が同じなら同じ乱数列が生成されるので、最初にkを種としてやれば、kに依存した乱数列が生成されます。
これを順番にXORしていけば、より解読されにくくなります。
別に、暗号化する必要のあるデータなんて扱う機会はないのですが、なんか暗号って燃えますね。つーか面白い。



XORに関連して、事典で始めて知ったなるほどという値の交換法を一つ。
普通2変数x, yの値を交換したければ、

t = x;
x = y;
y = t;

とするのが普通ですが、XORを使えばtを使わないで交換できます。

まず

x ^= y とします。
このとき、x = x XOR y, y = yです。

次に
y ^= x とします。
このとき x = x XOR y, y = y XOR (x XOR y)
結合法則より、
y = x XOR y XOR y = xとなります。

最後に、
x ^= y とします。
このとき、 x = x XOR y XOR x = y

よって、値が交換されます。
いやまったく、よう思いつくわ。
まあtを使った方がわかりやすいんですけどね。



たらい回し関数とは、

tarai(x, y, z)
{
if(x <= y) return y;
return (tarai(x - 1, y, z),
tarai(y - 1, z, x),
tarai(z - 1, x, y));
}

と定義される再帰関数です。
もう挙動を追うのもうんざりするような関数ですが、一応追ってみました。

tarai(x, y, z)から呼び出されるtarai(x - 1, y, z)から呼び出される(x - 2, y, z)……というように、木にしたときの左の子だけをたどっていくと、ひたすらx(一番左の引数)が減っていくので、いずれx <= yを満たし返ります。
そして、真ん中の子と右の子からも、その系列が無数に発生し、というかもうこの先は想像できないんですが、とにかくたくさん呼び出されるんだよ!!(思考放棄)
まあとにかく試してみた方が速いということで、試しに(100, 25, 1)とでも呼び出してみると、応答なしwwww
じゃあ(50,25,1)だ! へんじがないただのばくはつのようだ。……結局(25, 5, 1)でやっと応答。呼び出し回数は……

50626

圧倒的万単位っ……! その時CPUに電流走る……!
それぞれの値を1増やすだけで万単位で増えたり10倍になったりもうやばいです。

事典のコードにはコメントで

「たらいまわし関数。特に用途はない」

とあるのですが、どうやらその処理量の多さから速度テストなどに使われるそうです。

単調増加だとかO(n^2)だとかそんなチャチなもんじゃあ断じてねえ、もっと恐ろしい再帰の深淵を味わったぜ……
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメント

Secret

プロフィール

PON4416

Author:PON4416
職業: 高校生

プログラミング歴: 2年弱

絵描き歴: '09年11月ごろから

趣味: プログラミング(C, C++)、お絵かき、漫画、アニメ、ゲーム

好きなもの: ジョジョ(2=3>1=4=7>5=6)、東方、うみねこ、ガンダム00、イカ娘

妖夢
嫁です(キリッ


Wilesの趣味的な人格。
最近PHPを始めたらしい。→やめたらしい

メール: yoshihiro[dot]hozumi[at]gmail[dot]com
skype: wiles4416

主にpixivで活動しています。
マイピクとか常に大募集してますw
プロフィールはこちらから



にほんブログ村 イラストブログ イラスト練習へ

最新記事
ひとりごと
最新コメント
月別アーカイブ
カテゴリ
ブロとも一覧

Weak's Smaller
割れ厨撲滅
検索フォーム
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。