RSA暗号についての素朴な疑問

質問

RSA暗号について勉強中のものですが、これまでのところ
（１）送信側はは公開鍵(e,n)で平文aを b = a^e mod n で暗号文bを作成する。
（２）受信側は秘密鍵dを知っており、上記暗号文bからb^d mod n で元の平文aが求まる。
（３）暗号としてのキモは、(e,n)からでは復号できない。dを求めることも困難（nの素因数分解が困難）
というのが私の理解したところです。数式等もある程度理解しました。
ただ、ここで素朴な疑問があります。dをしらなくてもbのべき乗を繰り返していけば復号できるのでは？ということです。自分が送信側で平文aを暗号化してbを作る。bから　bxb→b'　b'xb→b''　b''xb→b''' 　と計算していけば平文aにたどり着くのでは？　（その結果dもわかったことになる）
平文が現れたかのチェック時間は余分にかかると思いますが、dを知っていてbのd乗を計算するのと上記のように２乗、３乗...と繰り返すのと大きな違いがあるのでしょうか？

長文ですいません。

回答No.2

Tacosan · ベストアンサー

そんな感じ. d がわかっていれば復号の時間はほんのわずかで済むんだけど, d を知らずに解読しようとするとおそろしく時間がかかる. たいていの情報には「賞味期限」があるので, その「賞味期限」の間だけ秘密にできれば十分, ってことですね.

なお, 公開鍵暗号系の中でも RSA は「わりと弱い」システムです. なので 1024ビットくらいの値が必要 (今ではこれでも不十分で 2048ビットじゃないとダメとかいう話もある) なんですが, 方法によっては 1/4 とか 1/6 とかの長さ (つまり 250ビットとか 160ビットとかその辺) の値で同程度の強度を持つものもあります.

お礼

回答ありがとうございました。
個々のフェーズの具体的なアルゴリズムも勉強しようと思います。

回答No.1

Tacosan

たしかに「d を知らなくても b のべき乗を繰り返していけば復号できる」というのは正しい.

ところで, 「現実的に」用いられる RSA に出てくる数値がどのくらいの大きさかは知っていますか?

補足

早速の回答ありがとうございます。

私の使っている教科書は数学寄りで原理的な数式がほとんどです。小さな数値で例が載ってますが、そのせいで計算量の感覚がなかなかつかめません。
いろいろとググッてみると、nは1024ビット（10進で300桁）以上でdもnとほぼ同じサイズと説明しているのがありました、eは意外に小さいのですね。（この非対称も興味がわくところですが）
10^300回数のべき乗計算ということは途方もない計算量で実質不可能なわけですね。で、dがわかるとなぜ計算できるのか調べてみると、バイナリー法というのを使うとビット数の1.5倍程度で計算できるようです。
以下のようなイメージでしょうか？
b b^2→b' b'^2→b'' b''^2→b'''　bの2乗、4乗、8乗・・・(2^1024)乗と求めてゆきd乗に必要な項を掛けていく。(dがわかっているから必要な項がわかる）
これだと確かに、ビット数分の乗算と必要な各項の乗算（平均でビット長の1/2？）で済みますね。
具体的には1500回くらい。　この理解で正しいでしょうか？