RSA暗号の問題について教えてください。

Question

RSA暗号についての質問です。

①赤丸の部分の解き方を教えてください。

②下線部のところに書いてある高速に計算できるアルゴリズムとは何でしょうか？調べたらバイナリ法というものがありましたが、それでしょうか？

③答えが29と35になっている所は自力で計算しましたが、もっと効率よく計算できる方法はないのでしょうか？自分が解いたときは、L=48とeの倍数をどんどん書いていきe(modL)=1になるようにしました。

宜しくお願い致します。

Answer 1

この問題の背景として、a,b,c,d,m,nを整数として、mを法として(つまり、以下≡はmod mを意味する)
a≡c,b≡dの時、ab≡cd,a^n≡c^nが成り立ちます。つまり、
余りの計算は、余り同士の計算でできるということです。
① 赤丸の答えはその次の「bのd乗をnで割った余り」と同じで、
そちらのほうが簡単なので、こちらを解きます。
b^2=225なので、n=221を法として、
b^2≡4,b^4=(b^2)^2≡4^2=16,
b^8=(b^4)^2≡16^2=256≡35,
b^16=(b^8)^2≡35^2=1225≡120,
b^29=b^16 * b^8 * b^4 * b≡1203516*15=1008000≡19(答え)

② こういうのだと思います。
上記①例を、最後の掛け算を逆順に行うような手法です。
1615=240≡19
3519=665≡2
120*2=240≡19

③ 私もまだ理解できていませんが、たぶんこれ
ed≡1(mod L)はkを整数としてed = kL + 1と書け、移項して
ed - kL = 1となる。これは数学Aで登場する不定方程式であり、
eとLのユークリッド互除法を利用して解ける。

Comments

[codetaisei]

すごく助かりました。
本当にありがとうございます。