■掲示板に戻る■ 全部 1- 101- 201- 最新50 [PR]ぜろちゃんねるプラス[PR]  

夜限定で算数・数学の話でも

113 ：１０７ ◆Dnhm9Q9euc ：2011/07/02(土) 00:28:00 ID:kt3aICwI

サイエンス0でRSA暗号をやっていたので、
私の復習のために書いてみることにする。

1st step:鍵をつくる
1)「巨大」な素数 p, q を用意し、
n := pq とおくと φ(n) = (p - 1)(q - 1) （オイラー関数）である。
2)φ(n) と最大公約数が 1 になる自然数 e をえらぶ。
3) de ≡ 1 (mod φ(n))となる d をえらぶ。
4)(e, n) は公開し、(p, q, d) を秘密にする。

2nd step:情報のやりとり
鍵を作り(e, n)を公開したAさん と 情報 M(自然数)を伝えたいBさんがいたとする。
Bさんは公開鍵を元に C ≡ M^e (mod n) をAさんに送ってやる。

3rd step:復元
Aさんは送られてきた C について C^d ≡ M (mod n) で復元する。
復元可能の根拠はオイラーの定理である。