質問編集履歴
1
不足点の加筆
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -1,3 +1,33 @@
|
|
|
1
1
|
### RSA暗号においてフェルマーの小定理はどのように利用されているのでしょうか？
|
|
2
2
|
自分で調べてみたのですが、フェルマーの小定理を用いたRSA暗号の証明はよく取り上げられているのですが、具体的にどのようなことを実現するためにフェルマーの小定理が利用されているのかが解説されていることが少なく、数学が得意な方、ぜひ解説をお願いします。
|
|
3
3
|
|
|
4
|
+
**参考にした説明・証明例**
|
|
5
|
+
|
|
6
|
+
説明
|
|
7
|
+
1. メッセージを受け取る側の準備
|
|
8
|
+
・大きな素数p,qを用意し、n = pqとする
|
|
9
|
+
・(p-1)(q-1)をn'とし、n'と互いに素な整数k1をとってくる
|
|
10
|
+
・k1･k2 ≡ １ (mod n')となるk2を計算する
|
|
11
|
+
・nとk1を公開する,k2は公開しない
|
|
12
|
+
|
|
13
|
+
2. 暗号化方法
|
|
14
|
+
・送りたいメッセージをmとする。ただしmはn未満の正の整数とする
|
|
15
|
+
・公開鍵を用いてM^k1 ≡ C (mod n)を計算する(Cが暗号文)
|
|
16
|
+
|
|
17
|
+
3. 復号方法
|
|
18
|
+
・暗号分Cと秘密鍵k2を用いてC^k2をnで割った余を計算すると、これがMと一致する。
|
|
19
|
+
|
|
20
|
+
|
|
21
|
+
|
|
22
|
+
証明例
|
|
23
|
+
|
|
24
|
+
M^k1･k2 ≡ M (mod n)を証明すればよい
|
|
25
|
+
n = p･q であるため、M^k1･k2 ≡ M (mod p)を証明すれば十分(対称性より mod qも同様)。
|
|
26
|
+
mとpの倍数の時は両辺共にpの倍数であるため自明
|
|
27
|
+
mがpの倍数でない時k1･k2 -1が(p -1)の倍数になるように計算したため、整数Nを用いてk1･k2 = 1 + (p -1)nとおける。よって、
|
|
28
|
+
m^k1･k2 = m ･ (m^p-1)^n ≡ m ･ 1^n = m
|
|
29
|
+
**ただし、途中の≡はmod pであり、フェルマーの小定理を用いた**
|
|
30
|
+
↑この部分がよくわかりません
|
|
31
|
+
|
|
32
|
+
[参考にしたサイト](https://manabitimes.jp/math/1146)
|
|
33
|
+
(説明に不足があれば上のサイトをみてください)
|