- angel_p_57
- 2556
- 5
- 1
- 0
導入
ここ最近、久しぶりにRSA暗号に触れてるんだけど。RSA暗号と言えばアニメ映画の「サマーウォーズ」ということらしくて、こういう動画が1年前に作られてて。最近も色んな人が見てるようなんだよね。 youtu.be/kvC55N4k9ng
2022-09-19 17:35:46個人的にサマーウォーズには「あー、NEC製スパコンっぽいの出てたな」位で、特に思うところはないんだけど。それはともかく。
2022-09-19 17:36:08で、劇中の暗号なんて、もちろん手計算はおろか今のスーパーコンピュータでも解けないんだけど。( 主人公の少年が解いてるのは、まあ、そこは作り話なので )
2022-09-19 17:36:40でも、この動画に出てきたRSAの復号計算 ( n=pq の素因数分解の結果が分かっている前提 ) なら、効率的な方法があって、n が4桁位なら普通に手でも計算できるんだよね。
2022-09-19 17:37:08ちなみに最近のまとめでやってた復号計算デモの中で言ってた「実際にはこうは計算しない」ってのは、現実ではその「効率的な計算」の方を採用してるから。 togetter.com/li/1944444
2022-09-19 17:37:45動画で出た問題
ではまず問題から。動画中のQ2で出てきている問題。このような 4桁の n でのRSAの例になっている。 pic.twitter.com/jCrBNnHOrg
2022-09-19 17:38:48それに対して、ありがちな説明というか、ナイーブな解法だとこういう2ステップでの計算になる。ちなみに答えは 1526 だ。 pic.twitter.com/fOnKw11oxl
2022-09-19 17:39:29もちろん、ここに出てくる d は秘密鍵の一部なので、現実に活用されているRSAでは、最初の計算は鍵生成時に済ませているものなんだけど。それはさておき。
2022-09-19 17:40:00動画でもこの解法で計算しているようで、手計算で1時間弱かかったらしい。まあ、4桁の掛け算・割り算を何度も行うわけなので、確かにかなり辛いだろう。
2022-09-19 17:40:26余談: 効率的なべき剰余計算
とここで、ちょっと余談なんだけど。2番目に出てくる319乗というべき剰余計算。これ、流石に1乗ずつ先に進めるようなことはしていないと思う。
2022-09-19 17:40:48それだけの計算してたら流石に1時間でも終わらないし、もし現実レベルのRSA暗号でべき剰余を1乗ずつ計算してたら、それこそコンピュータでも計算が終わらない。 pic.twitter.com/wd9TXKmyOp
2022-09-19 17:41:23なので、こういうべき剰余の計算では、「バイナリ法」が有効。つまり、2乗、4乗、8乗、16乗、…と、指数を倍々にして計算して、その結果を組み合わせるということ。 pic.twitter.com/8gvGyGftuu
2022-09-19 17:41:58ちなみに、319乗の場合だと、地道に1乗ずつ進めたら318ステップ手順がかかるのに対し、バイナリ法だと 2乗~256乗の結果を求める8ステップと、最後の結果の計算で出てくる×の分の6ステップ、計14ステップで済む。
2022-09-19 17:42:18現実のRSAだと、公開鍵のパラメータ e=65537=2^16+1 ( c≡M^e mod n として使う ) がほぼ固定になってるんだけど。これは最後の結果を組み合わせる部分の手順が少なくなるというメリットがある数値になっている。
2022-09-19 17:42:44効率的な方法と実例
さて、では本題の「効率的な解法」だけど。この方針のように、計算を小さく分解して処理する。 pic.twitter.com/OCgYkMsBDL
2022-09-19 17:43:26「やること増えて面倒では?」と思うかも知れないけど、各手順で行う計算はどれも2桁で済むものなので、慣れた人なら暗算で全然問題ないレベルに難易度が落ちるのである。
2022-09-19 17:43:47まずは、モジュラー逆数の計算が幾つか来る。最初の1つはこんな感じ。 なお、最終結果は 31 と出てるけど、後の計算では1ステップ前の-5を採用している。そちらの方が楽なので。手計算だとガチガチに機械的にやらなくても良いので、その影響と言うか。 pic.twitter.com/DAiZWaIGF5
2022-09-19 17:44:47モジュラー逆数を求める方法については、つい先日この記事でまとめたばかりなんだけど。 …今回の計算で使うつもりが、フィーリングだけで済んでしまったので、出番が無くなってしまった…。 qiita.com/angel_p_57/ite…
2022-09-19 17:45:21まあ、幾つか候補を試してる内に逆数が見つかることもままあるので。プログラミングで独自にやるなら方法として知ってないといけないけど、毎回使う必要はないって感じ。
2022-09-19 17:45:42