なぜなに RC5

鍵の管理をちゃんとすれば問題ないけど、ちょっと不安ですね。
秘密鍵暗号の場合は、 暗号を送る人だけじゃなく受け取る人も同じ鍵を使う必要があるから、 鍵をぬすまれる可能性は大きくなります。
また、鍵を盗まれてしまうと、 鍵を盗んだ人が他人になりすまして暗号を送ることも出来ちゃいます。

最近では、暗号化する時に使う鍵と、普通文に戻す時に使う鍵を別にする 公開鍵暗号というのもよく使われています。 この場合は、普通文に戻すための鍵を公開するんだけど、 暗号化する鍵さえしっかりと管理しておけば、 他人になり済ますことは出来なくなります。
だから、正当な送り主であることを証明するための、 デジタル署名なんかに良く使われています。

説明しましょう。
RC5 っていうのは M.I.T. の Ronald L. Rivest という人が 1994 年に発明した、暗号化アルゴリズムです。
いま私たちが解読しようとしているのは、 RC5-32/12/8 というもので、 8 バイトつまり 64 ビットのキーを使うので通称 RC5-64 って言われています。
RC5-32/12/7 つまり RC5-56 は、1997 年に 265 日掛けて解読に成功しています。

キーの長さはそのまま暗号の強度になります。
例えば 64 ビットの暗号の場合、 全部で 1844京6744兆737億955万1616 とおりの可能性があるから、 もし一秒間に 400 億個のキーを調べることが出来たとしても、 解読するまでには 15 年かかることになります。
RSA の Webには RC5-32/12/16 (RC5-128) まで問題が出ているから、 興味のある人は調べておくように。

(むっ！)

能天気は置いといて、説明を続けます。
暗号化するのにキーを使うんだけど、 実際のキーを RC5 ではこのまま使わずに細工をしてから使います。

まず最初にキーを展開します。 展開する場所は、32 ビットで適当な大きさの配列ね。 実は大きさは RC5 の複雑さによって変わります。 RC5-32/12/8 って言った場合の 32 が一度に処理するビットの数、 12 が複雑さを示しているのですが、 この複雑さの倍よりちょっと大きな配列を用意します。
まぁ、複雑さを大きくすると暗号化にかかる計算時間が長くなるから、 暗号の強度とのトレードオフといったところかしら。 32 ビットの場合最低 12 、 64 ビットの場合最低 16 は欲しいっていわれているわ。

キーを展開する前に、配列に初期値をいれておきます。 これには、自然対数の底 e (=2.71828 ...) と黄金分割比 φ (=1.61803 ...)の小数部分を 2 進数で表現したものを使います。 つまり最初の数値が、 0.71828 ... で一つ増えるごとに 0.61803 ... づつ足していきます。
あ、もし e や φ を 2 進数で表した結果が偶数になった時は奇数になるよう に繰り上げてから計算します。 だから、この配列は、奇数、偶数、奇数、偶数という順に並びます。 ちなみに 32 ビットの場合には、 e (の小数部)=0xb7e15163 と φ(の小数部)=0x9e3779b9 という数値をつかいます。
また、足した結果が 1 を越える様な場合は、結果の小数部分だけ使います。 RC5-64 の場合は 2*(12+1)-1 回足して、全部で 26個つくります。

準備ができたら、この初期値と実際のキーを混ぜ合わせます。
混ぜ合わせる方法は、ビットローテートっていう方法です。 そうね、本の頭の方からページを切り取って、最後に張り付ける操作 っていったら分かりやすいかしら。 これで、ぐるぐるかき回すわけね。

この操作を、配列の大きさとキーの大きさのうちの大きい方の 3 倍回繰り返します。 RC5-64 の場合は、配列の大きさが 26 で、キーの大きさが 2 だから、 大きいほうの 26 の 3 倍、つまり 78 回繰り返します。 注意して欲しいのは、準備した配列は 3 回、 実際のキーだった物は 36 回書き換えられているということです。 この操作をし終った後に、配列に入っていたものが、 この次の暗号化の時に使用するキーになります。 これでやっと、暗号化する準備が整ったわけね。

暗号にする文章なんだけど、あらかじめ 32 ビットごとに分割しておきます。 そして、分割した物から2個取り出します。 暗号化は、2個つまり 8 バイトごとに行なわれるから、 今から述べる操作を文章すべてに行なわないと暗号にならないのね。

まず 26 個に展開したキーから最初の2個を取り出します。 そして、それぞれ暗号化する文書から取り出した2個に足しちゃいます。 これが初期値になるわけね。
そして、それぞれをビットローテートでぐるぐる回して、 展開したキーから 2 個づつ順番にとりだして、足していきます。 これを 12 回繰り返した結果、 下の図でいうと、中間結果 25 と 26 に相当するものが 暗号文になるわけです。

本当は、さらに初期化ベクトルっていうのを用意して、 元の文をちょっと細工してから暗号化するんだけど、 こっちはあまり本質ではないわね。

ちなみに RC5 を更に改良した RC6 というアルゴリズムが既に開発されているわ。 RC5 は 2 個ずつ処理するのが基本だけど、 RC6 は 4 個ずつ取り出して、その 4 個を順繰りにしながら、 RC5 のような暗号化プロセスをおこないます。 いま、アメリカ政府で現在の標準暗号化アルゴリズム DES の後継として AES (Advanced Encryption Standard)というのが選定作業中なんだけど、 RC6 は AES の最有力候補といわれているわ。 もっとも、それは暗号としての性能だけじゃなくて、 政治的なものも絡んでいるから複雑だけど。

ひじょーに良い質問ね。

今説明した通り、 RC5 の計算は大半がビットローテートと足し算からなっています。 だから、これらの命令の実行時間が短いプロセッサが有利なの。 例えば、x86 プロセッサでは他の RISC プロセッサと比べて、 ビットローテートが高速なの。 だから、x86 は速いのです。 逆に 64 ビットのプロセッサでは、 32 ビットのビットローテートをするのに、 かなりのコストがかかります。 だから、Alpha は遅いわけね。

もう一つ速度に関係しているのは、複数の命令を同時実行できるかどうかね。 最近のプロセッサは、スーパースカラーといって 複数の命令を実行できるようになってます。 とはいってもどんな命令も並列実行できるわけじゃなくて、 多少の制限があるんだけど、 この制限がプロセッサによって違うのね。 ビットローテートを２個同時実行できるのもあれば、 ビットローテートと加算なら同時実行できるものもあるし、 全然同時実行出来ないものもあるわ。 当然同時にビットローテートと加算をたくさんできるプロセッサが速いわけね。

さっきのアルゴリズムをそのままコードにすると、 データ依存性が高いので全く並列実行できません。 これを解決するために Distributed.Net の rc5 コードでは、 同時に 2 個のキーを調べるようにして、命令の並列度をあげているわ。
MMX をつかって 4 個のキーを同時にしらべるようにしたものもあるわね。

正解。
あなた、ぼーっとしている割には鋭いのね。

先程、RC5-56 が 265 日で解読出来たといいましたが、 解読したのは、Distributed.Net というグループです。 このグループは、RC5-56 のキーを小わけにして、 それを世界中の計算機に配って、それぞれで計算してもらったのね。 まあ、地球規模の超大規模並列計算機といったところね。 RC5-64 もいくつかのグループが解読を試みているけど、 Disteibuetd.Net が最有力候補かしら。
良く「RC5-64 コンテストに参加してます。」って聞くけど、 Distributed.Net の一員として参加している人がほとんどね。 何人かで、「チーム」ってのを作ることもできるので、 チームの間の処理速度の競争も激しいものがあるわ。
まぁ、競争によって能力を引き出そうというのは、 資本主義社会の常套手段みたいなものね。

さて、Disteibuetd.Net では、RC5-64 の 1844京6744兆737億955万1616個あるキーを、 2億6843万5456づつ小わけにして、参加者に配っています。 この小わけにしたものを「ブロック」と呼んでいるんだけど、 全部でブロックの数は、687億1947万6736個もあります。 いま調べ終ったブロックの数は大体 20 億個だから、 まだ 3% にも満たないわね。
1998 年 10 月の時点で、 Distributed.Net には 大体 1 秒間に 400 億のキーを計算する能力があります。 これは世界最速のスーパーコンピュータをはるかに凌ぎます。

おばさんで悪かったわね。

もちろん、現在の能力ではそのくらいかかるわけだけど、 技術も進歩するでしょうし、参加者も増えるでしょう。
実際に Distributed.Net の処理能力は、2 ヵ月で 5 割近く上昇しているの。 まぁ、この調子でふえたら何とか 20 世紀中には解読できると思うわ。