数学
中学生
解決済み

超激むずです なるべく早めにお願いします🙇‍♂️
整数の問題だと思うのですが今日学校の授業を休んでしまってわかりません
誰か教えてくれませんか?本当にお願いします🤲

【5】 異なる2つの素数を p=11,q=23 とし, RSA 暗号を用いて"32'を暗号化するとき, その暗号文を求めなさい. ただし暗号鍵は 19とする。

回答

✨ ベストアンサー ✨

中学生が普通にやるような話ではなさそうですが、結局は合同式の活用とかの話に帰着するようですね。
p=11, q=23が与えられているので、公開鍵(暗号鍵)nとeのうち、nはこれらの積
n=11×23=253
となり、eは
(p-1)(q-1)=10×22=220=2²×5×11
と互いに素な自然数のうちの一つとして、19にするよう問題が指示してきています。
さて、平文(ひらぶん)32を暗号文に変えるロジックは、
32を19乗し、253で割った余りが、32の暗号文
のようです。
普通にやるとしんどいので、工夫を試みます。
まず、32=2⁵なので、
32¹⁹=(2⁵)¹⁹=2⁹⁵
です。また、
2⁸=256=253+3となりますので、
2⁹⁵=(2⁸)¹¹×2⁷
と書いたとき、それを253で割った余りは、2⁸を3におきかえて
3¹¹×2⁷を253で割ったあまりに等しくなります。
ここで
3⁵=243=253-10なので
3¹⁰=(3⁵)²=(253-10)²=253²-253×10×2+10²
を253で割った余りは10²=100となります。
したがって、
3¹¹×2⁷=3¹⁰×3×2⁷を253で割った余りは
100×3×2⁷を253で割った余りに等しくなります。
ここまでいけば正攻法で良く、
100×3×2⁷=38400を253で割った余りは筆算でもして197となります。
この197が題意の暗号文のはずです。

なお、復号のほうはもっと厄介で、復号のための秘密鍵のひとつが139となり、エクセルを工夫して駆使して、197の139乗を253で割った余りが32に戻ることは確認できました。

この回答にコメントする
疑問は解決しましたか?