sekai013's blog

JavaScriptとかを勉強する

RSA暗号について雑にまとめた

RSA とは?

暗号化の方式. 暗号化における鍵配送問題を解決する公開鍵暗号を実現した画期的な方法. 発明者3人の名前から RSA という名前になった.

必要な知識

だいたい wikipedia に載ってる.
- オイラーのΦ関数

ruby で書くとこんな感じ
def euler(n)
  coprimes = (1..n).select {|k|
    n.gcd(k) == 1
  }
  coprimes.size
end

RSA 暗号のしくみ

 {
\left(\array{
m : 平文(もとのメッセージ) \newline
p, q: 十分大きい素数(p \neq q) \newline
n := pq \newline
\phi(n) := {\rm euler}(n) = (p-1)(q-1) \newline
e : \phi(n)\ 未満かつ\ e\ と\ \phi(n)\ は互いに素となるような自然数
}\right.
}

 {
とする.
}

 {
d : de \equiv 1 \mod \phi(n)\ となるような自然数を考えると,\ ^\exists k \in \{0,1,\dots\}\ に対して
}

 {
de = k\phi(n) + 1 \Leftrightarrow de - k\phi(n) = 1\
とかける.
}

 {
ここで,\ e\ と\ \phi(n)\ は互いに素であるから\ {\rm gcd}(e, \phi(n)) = 1
}

 {
よって拡張されたユークリッドの互除法により\ d\ を求めることができる.
}

 {
ここで,\
c = m^e \mod n\
とすると,
}

 {
c^d \equiv (m^e)^d \equiv m^{de} \equiv m^{k\phi(n)+1} \mod n
}

  1.  {m\ と\ n\ が互いに素であるとき}

     {
 オイラーの定理より\ m^{\phi(n)} \equiv 1 \mod n
 }

     {
 よって\ m^{k\phi(n)+1} \equiv 1^k ・ m \mod n
 }

     {
 c\ から\ d,\ n\ によって\ m\ を復元可能.
 }

  2. {{\rm gcd}(m,n) = p\ のとき}

     {
 m^{k\phi(n)+1} \equiv m \equiv 0 \mod p
 }

     {
 m^{k\phi(n)+1} = m^{k(p-1)(q-1)+1} = \left(m^{q-1}\right)^{k(p-1)}・m \equiv 1^{k(p-1)}・m \mod q (オイラーの定理)
 }

     {
 よって\ m^{k\phi(n)+1}\equiv m \mod n\ となり\ c\ から\ d, n\ によって\ m\ を復元可能.
 }

     {
 \left(\array{
 (命題)\ \ \ \ 自然数 n > 1, k > 1, 異なる {\rm 2} つの素数\ p, q\ に対し\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \newline
 n^k \equiv n \mod p\ かつ\ n^k \equiv n \mod q\ であれば\ n^k \equiv n \mod pq である.\newline
 (証明)\ \ \ \ 条件より適当な自然数\ a,b\ を用いて\ n^k - n = pa = qb\ とおける.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \newline
 a = qb/p\ とすると,\ a\ が自然数であることと, p,q\ が異なる素数であることから,\ b\ は\ p\ を因数にもつ
 }\right)
 }

     {
 {\rm gcd}(m,n) = q のときも同様に復元可能
 }

一方  {d} がわからないと  {m} の復元は困難(らしい)

アリスがボブにメッセージ  {m} を安全に送りたいとき

  • ボブは素数 {p, q} と, {(p-1)(q-1)} と互いに素な自然数 {e} を用意して, {n = pq, d} を計算する.

  • ボブは {e, n} を公開する.

  • アリスは {m} に対して {m^e \mod n} を計算してボブに送信する.

  • ここで第三者キャロルにアリスが送信した暗号文を盗み見られたとしても, {d} がわからないキャロルには暗号文を解読できない.

  • 暗号文を受け取った ボブは秘密鍵 {d} を用いて {m} を復元してメッセージを読む.

という感じで安全に送れる. {n} 公開されてるなら {n=pq} だから {p}{q} もわかって {d} もわかるやん!
と言いたくなるけど, 巨大な素数の合成数の素因数分解しようと思ったらめちゃくちゃに時間がかかるのでまあ現実的には無理ということになっている.

思ったより長くなってしまった。見にくいけど腰が痛いのでぶん投げる。間違ってたら教えてください。