難しい（？）暗号の問題です
基礎があれば分かるらしいのですが、まったく手も足も出ず。
分かる方いらっしゃいますか？
以下、問題文です。
--
2 → 18
3 → 9
5 → 3
7 → 17
11 → 11
13 → 7
15 → 5
20 → 4
3 is private.
17 → ？
ログインして回答する
みんなの回答
-
匿名質問者
Hint1: The private number should not be known, though it is not a secret itself.
だそうです。3 のことだと思うのですが、ぜんぜん意味が分かりません。それ自体は秘密ではないけれど、知られるべきではない数字？どういう意味なんでしょう？
この質問へのコメント
質問の情報
- 登録日時
- 2023-03-26 16:32:20
- 終了日時
- 2023-04-02 16:35:05
- 回答条件
- 1人5回まで
この質問のカテゴリ
人気の質問
-
ツイッターの観覧人数の数はどうのように統計されますか？ 人がそツイッターをクリックした…
iquestion
1
-
こんばんは フリーソフトオープン思想の発祥を1000年以上前の哲学者に見出した記事がありました。 知的財産…
そさん
1
11
-
勉強教えてほしいです 問題 次の言葉から、言葉の頭やあとについて意味をそえる部分を書きなさい ①ごきげ…匿名質問者11
-
東海林さだおに詳しい方ご教示ください。 さだおさんが、カレーを食べたいのになかなかカレーにたどり着け…匿名質問者22
-
プリ小説に関しての質問です 少し前からプリ小説にハマって、自分でも小説を出してみたいなとは思っている…匿名質問者21
RSA暗号では
・秘密鍵は、2つの素数。
・公開鍵は、秘密鍵の積と、暗号化時の指数。
・(暗号化された数)=((元の数)^(暗号化時の指数)) % (秘密鍵の積)
・(元の数)=((暗号化された数)^(復号化時の指数)) % (秘密鍵の積)
・複合化時の指数は、公開鍵と秘密鍵から容易に計算可能。
・秘密鍵の積から秘密鍵を計算することは困難。
・(暗号化時の指数)*(複合化時の指数) - ((秘密鍵1つ目)-1)*((秘j密鍵2つ目)-1)*N = 1
です。
「Hint1: The private number should not be known, though it is not a secret itself.」から、3は秘密鍵それ自体ではなく、それを元に計算されるもの、つまり複合化時の指数なのではないかとアタリを付けます。
試しに→の右にある数を、いくつか3乗してみます。
さらに、その数字を秘密鍵の積で割った余りが、一番左の数字と等しくなるはずですので、逆に一番左の数字を引けば、秘密鍵の積で割り切れるようになります。
5 → 3 → 3^3 = 27 → 27-5 = 22
20 → 4 → 4^3 = 64 → 64-20 = 44
15 → 5 → 5^3 = 125 → 125-15 = 110
（以下略）
いずれも 22 で割り切れます。これが秘密鍵の積でしょう。
これを素因数分解すると秘密鍵が分かります。
2 と 11 です。
さらに、これらから暗号化時の指数を求めます。
(暗号化時の指数)*3 -(2-1)*(11-1)*N=1
これを満たす暗号化時の指数とNは無数にありますが、そのうちのもっとも小さいものは、N=2、暗号化時の指数=7 です。
問題文の左側の数字（＝平文）を 7 乗して、22 で割った余りを求めたものが、右側の数字（＝暗号文）です。
さらに、右側の数字（＝暗号文）を 3 乗して、22 で割ったあまりを求めたものが、左側の数字（＝平文）になります。
よって、
17→(17^3)%22 = 19
が答えです。
19を3乗して、22で割った余りを求めると、ちゃんと17に戻りますよ。
最後はタイポしてました。
17→(17^7)%22 = 19
でした。