-
angel_p_57
- 2610
- 5
- 1
- 0
-
- いいね！0
angel (as ㌵㌤の猫)
@angel_p_57
で、残りのモジュラー逆数の計算もサクっと終わる。 pic.twitter.com/aw9G9IV5t5
2022-09-19 17:46:14
拡大
angel (as ㌵㌤の猫)
@angel_p_57
では続いてべき剰余の計算に移る。ここはそれなりに大変なんだけど、でも 2桁 の計算になっているのでやってみるとそれ程でもないことが分かる。 pic.twitter.com/GC2xAETTiJ
2022-09-19 17:46:58
拡大
angel (as ㌵㌤の猫)
@angel_p_57
ただ、それでも計算回数は減らしたいので、敢えて逆数を持ち出したりしている。( 31じゃなくて-5を採用しているのがそれ ) まあ、手計算は臨機応変に工夫ということで。
2022-09-19 17:47:15
angel (as ㌵㌤の猫)
@angel_p_57
もう一方のべき剰余の計算が一番重いところだった。ここでも回数を減らすため逆数を使ってるけど。まあそれでもバイナリ法が効いてるのでそんな大したことにはなっていない。 pic.twitter.com/5fAR5EuE7u
2022-09-19 17:47:40
拡大
angel (as ㌵㌤の猫)
@angel_p_57
そして最後の計算を立て続けに行って、ちゃんと 1526 と正しい答えが得られた。 pic.twitter.com/PjhTYwHSdw
2022-09-19 17:48:01
拡大
最後に
angel (as ㌵㌤の猫)
@angel_p_57
ちなみに、全体通じて手計算で10分程度しか使ってない。これがナイーブな方法で4桁の計算の繰り返しだと、自分の計算能力だとちょっとやる気しなかったところだ。
2022-09-19 17:48:17
angel (as ㌵㌤の猫)
@angel_p_57
なので、手順自体が増えているにしても、計算を細かく分けることの効果は十分に出ていたことになる。これ実は現実のRSAをコンピュータで計算する場合にも同じように有効なのだ。
2022-09-19 17:48:32
angel (as ㌵㌤の猫)
@angel_p_57
なぜかと言うと、RSAで使うような数は数百桁にも及ぶので、CPUの計算単位 ( 32bitとか64bit ) とかにはそもそも収まらない。なので数式では単なる掛け算や割り算であっても、内部的に何度も計算を繰り返すんだけど、桁数が多い程その計算量がとても多くなっていく。
2022-09-19 17:48:43
angel (as ㌵㌤の猫)
@angel_p_57
結果として、計算を分割した方が、桁数が減ったことによる計算量の削減の恩恵を得られて、トータルでの計算量が減ることになるから、というのが理由になる。大体1/4程度の計算量になるらしい。
2022-09-19 17:48:54
angel (as ㌵㌤の猫)
@angel_p_57
なお、計算で出てきた dp, dq, qinv の3数だけど、これは都度計算する必要はないため、鍵を作る時に一度計算すればおわり。で、秘密鍵ファイルの中にこれら3数が保存されている。
2022-09-19 17:49:04
angel (as ㌵㌤の猫)
@angel_p_57
ということで、大体こんなところなんだけど。「なんでそんな計算できるの?」というと。規格に載ってる計算、そのままやってるだけなんだよね。身も蓋もないことを言うと。
2022-09-19 17:49:17
angel (as ㌵㌤の猫)
@angel_p_57
大分昔の規格になるけど、PKCS#1 v2.0 ( RFC2437 ) というRSAの規格の、3.2章 ( 秘密鍵に含まれるデータの内容 )、5.1.2章 ( 秘密鍵を使った復号の計算内容 ) にそのまま書いてある。 ietf.org/rfc/rfc2437.txt
2022-09-19 17:49:29
angel (as ㌵㌤の猫)
@angel_p_57
まあ、それだけだとなんなので、自分なりに「どうしてそれで巧くいくの?」というのは簡単にまとめてはいるけど。以下の記事の終わりの方で。 qiita.com/angel_p_57/ite…
2022-09-19 17:49:45
angel (as ㌵㌤の猫)
@angel_p_57
過去の記事の内容の焼き直しと言えばそうなんだけど、あまりにRSAの話題の中で目にしないのでちょっと取り上げてみた、ということで。
2022-09-19 17:50:01