RSA暗号におけるフェルマーの小定理の利用

Question

RSA暗号においてフェルマーの小定理はどのように利用されているのでしょうか？

自分で調べてみたのですが、フェルマーの小定理を用いたRSA暗号の証明はよく取り上げられているのですが、具体的にどのようなことを実現するためにフェルマーの小定理が利用されているのかが解説されていることが少なく、数学が得意な方、ぜひ解説をお願いします。

参考にした説明・証明例

説明

1. メッセージを受け取る側の準備

・大きな素数p,qを用意し、n = pqとする
・(p-1)(q-1)をn'とし、n'と互いに素な整数k1をとってくる
・k1･k2 ≡ １ (mod n')となるk2を計算する
・nとk1を公開する,k2は公開しない

1. 暗号化方法

・送りたいメッセージをmとする。ただしmはn未満の正の整数とする
・公開鍵を用いてM^k1 ≡ C (mod n)を計算する(Cが暗号文)

1. 復号方法

・暗号分Cと秘密鍵k2を用いてC^k2をnで割った余を計算すると、これがMと一致する。

証明例

M^k1･k2 ≡ M (mod n)を証明すればよい
n = p･q であるため、M^k1･k2 ≡ M (mod p)を証明すれば十分(対称性より mod qも同様)。
mとpの倍数の時は両辺共にpの倍数であるため自明
mがpの倍数でない時k1･k2 -1が(p -1)の倍数になるように計算したため、整数Nを用いてk1･k2 = 1 + (p -1)nとおける。よって、
m^k1･k2 = m ･ (m^p-1)^n ≡ m ･ 1^n = m
ただし、途中の≡はmod pであり、フェルマーの小定理を用いた
↑この部分がよくわかりません

参考にしたサイト
(説明に不足があれば上のサイトをみてください)

Comments

[maisumakun]

「フェルマーの小定理を用いたRSA暗号の証明」がある（すでに使われている）のに「どのようなことを実現するためにフェルマーの小定理が利用されているのかが」わからない、という状況がわからないのですが、具体的に証明例をご提示いただけないでしょうか。

Answer 1

この部分がよくわかりません

文字通りの意味です。「mとpが互いに素な場合に、m**(p-1)≡1（mod p）」というのが、フェルマーの小定理そのものです。

Comments

[maisumakun]

やはり、何を把握できていないのかが理解できない状況です。

[boom]

回答ありがとうございます。
ベストアンサーは別の方を選ばせていただきましたが、こちらの回答も非常に参考になりました。

[maisumakun]

「別の方」とは、誰のことなのでしょうか。