効率的なRSAの計算

あまり説明されることのない ( でも現実に使われている ) RSAでの秘密鍵処理 ( 復号計算等 ) の効率的な計算方とその実例
7

導入

angel (as ㌵㌤の猫) @angel_p_57

ここ最近、久しぶりにRSA暗号に触れてるんだけど。RSA暗号と言えばアニメ映画の「サマーウォーズ」ということらしくて、こういう動画が1年前に作られてて。最近も色んな人が見てるようなんだよね。 youtu.be/kvC55N4k9ng

2022-09-19 17:35:46
拡大
angel (as ㌵㌤の猫) @angel_p_57

個人的にサマーウォーズには「あー、NEC製スパコンっぽいの出てたな」位で、特に思うところはないんだけど。それはともかく。

2022-09-19 17:36:08
angel (as ㌵㌤の猫) @angel_p_57

で、劇中の暗号なんて、もちろん手計算はおろか今のスーパーコンピュータでも解けないんだけど。( 主人公の少年が解いてるのは、まあ、そこは作り話なので )

2022-09-19 17:36:40
angel (as ㌵㌤の猫) @angel_p_57

でも、この動画に出てきたRSAの復号計算 ( n=pq の素因数分解の結果が分かっている前提 ) なら、効率的な方法があって、n が4桁位なら普通に手でも計算できるんだよね。

2022-09-19 17:37:08
angel (as ㌵㌤の猫) @angel_p_57

ちなみに最近のまとめでやってた復号計算デモの中で言ってた「実際にはこうは計算しない」ってのは、現実ではその「効率的な計算」の方を採用してるから。 togetter.com/li/1944444

2022-09-19 17:37:45
angel (as ㌵㌤の猫) @angel_p_57

この方法についてちょっと触れてみようかと思う。

2022-09-19 17:38:05

動画で出た問題

angel (as ㌵㌤の猫) @angel_p_57

ではまず問題から。動画中のQ2で出てきている問題。このような 4桁の n でのRSAの例になっている。 pic.twitter.com/jCrBNnHOrg

2022-09-19 17:38:48
拡大
angel (as ㌵㌤の猫) @angel_p_57

それに対して、ありがちな説明というか、ナイーブな解法だとこういう2ステップでの計算になる。ちなみに答えは 1526 だ。 pic.twitter.com/fOnKw11oxl

2022-09-19 17:39:29
拡大
angel (as ㌵㌤の猫) @angel_p_57

もちろん、ここに出てくる d は秘密鍵の一部なので、現実に活用されているRSAでは、最初の計算は鍵生成時に済ませているものなんだけど。それはさておき。

2022-09-19 17:40:00
angel (as ㌵㌤の猫) @angel_p_57

動画でもこの解法で計算しているようで、手計算で1時間弱かかったらしい。まあ、4桁の掛け算・割り算を何度も行うわけなので、確かにかなり辛いだろう。

2022-09-19 17:40:26

余談: 効率的なべき剰余計算

angel (as ㌵㌤の猫) @angel_p_57

とここで、ちょっと余談なんだけど。2番目に出てくる319乗というべき剰余計算。これ、流石に1乗ずつ先に進めるようなことはしていないと思う。

2022-09-19 17:40:48
angel (as ㌵㌤の猫) @angel_p_57

それだけの計算してたら流石に1時間でも終わらないし、もし現実レベルのRSA暗号でべき剰余を1乗ずつ計算してたら、それこそコンピュータでも計算が終わらない。 pic.twitter.com/wd9TXKmyOp

2022-09-19 17:41:23
拡大
angel (as ㌵㌤の猫) @angel_p_57

なので、こういうべき剰余の計算では、「バイナリ法」が有効。つまり、2乗、4乗、8乗、16乗、…と、指数を倍々にして計算して、その結果を組み合わせるということ。 pic.twitter.com/8gvGyGftuu

2022-09-19 17:41:58
拡大
angel (as ㌵㌤の猫) @angel_p_57

ちなみに、319乗の場合だと、地道に1乗ずつ進めたら318ステップ手順がかかるのに対し、バイナリ法だと 2乗~256乗の結果を求める8ステップと、最後の結果の計算で出てくる×の分の6ステップ、計14ステップで済む。

2022-09-19 17:42:18
angel (as ㌵㌤の猫) @angel_p_57

現実のRSAだと、公開鍵のパラメータ e=65537=2^16+1 ( c≡M^e mod n として使う ) がほぼ固定になってるんだけど。これは最後の結果を組み合わせる部分の手順が少なくなるというメリットがある数値になっている。

2022-09-19 17:42:44

効率的な方法と実例

angel (as ㌵㌤の猫) @angel_p_57

さて、では本題の「効率的な解法」だけど。この方針のように、計算を小さく分解して処理する。 pic.twitter.com/OCgYkMsBDL

2022-09-19 17:43:26
拡大
angel (as ㌵㌤の猫) @angel_p_57

「やること増えて面倒では?」と思うかも知れないけど、各手順で行う計算はどれも2桁で済むものなので、慣れた人なら暗算で全然問題ないレベルに難易度が落ちるのである。

2022-09-19 17:43:47
angel (as ㌵㌤の猫) @angel_p_57

では、実際に手動計算した例を挙げる。

2022-09-19 17:44:00
angel (as ㌵㌤の猫) @angel_p_57

まずは、モジュラー逆数の計算が幾つか来る。最初の1つはこんな感じ。 なお、最終結果は 31 と出てるけど、後の計算では1ステップ前の-5を採用している。そちらの方が楽なので。手計算だとガチガチに機械的にやらなくても良いので、その影響と言うか。 pic.twitter.com/DAiZWaIGF5

2022-09-19 17:44:47
拡大
angel (as ㌵㌤の猫) @angel_p_57

モジュラー逆数を求める方法については、つい先日この記事でまとめたばかりなんだけど。 …今回の計算で使うつもりが、フィーリングだけで済んでしまったので、出番が無くなってしまった…。 qiita.com/angel_p_57/ite…

2022-09-19 17:45:21
angel (as ㌵㌤の猫) @angel_p_57

まあ、幾つか候補を試してる内に逆数が見つかることもままあるので。プログラミングで独自にやるなら方法として知ってないといけないけど、毎回使う必要はないって感じ。

2022-09-19 17:45:42