RSAの基本的な解説.
巨大な合成数の素因数分解が困難であることを安全性の根拠としたアルゴリズム.
\( (p, q) \rightarrow N (= pq) \): 易しい
\( N \rightarrow (p, q) \): 難しい
[追記 (2019.09.27)] RSAが巨大な合成数の素因数分解が困難であることを安全性の根拠としたアルゴリズムは嘘. 公開鍵と暗号文(\(n, e, c=m^{e}\))(詳しくは後述)から平文\(m\)を求める問題をRSA問題といい, 公開鍵が, あるいくつかの条件を満たしているときにRSA問題は難しいと考えられている. RSA問題が困難であるという仮定をRSA仮定とよぶ. RSA問題は\(n\)が与えられたときに素因数分解するのと同程度に難しいと考えられている.
Algorithm
KeyGen
\(p, q\): prime, \(p \neq q \)
\(N := pq\)
\(e\): public exponent, such that \(GCD(e, (p-1)(q-1) ) = 1\)
\(d\): private exponent, such that \(ed \equiv 1 \, mod \, ( (p-1)(q-1)) \)
Public Key: \( (e, N) \)
Private Key: \(d\)
Enc
\(m\): 平文 (\(m \in (\mathcal{Z}/n\mathcal{Z}) \)見た目の都合上Nをnと書いた)
\(c\): 暗号文
\(c := m^{e} \, mod \, N\)
Dec
\(m^{\prime}\): 復号文
\(m^{\prime} := c^{d} \, mod \, N\)
ここで \(m^{\prime} = m \)
正当性
\(Dec(Enc(m)) = m\)となることを確認する.
オイラーの定理
\(a\)と互いに素な\(N\)に対し, \(a^{\phi(N)} \equiv 1 \, mod \, N \)
\( \phi(N) \)は1 ~ N-1までで, \(N\)と互いに素であるものの個数.
証明
補題1
\(a \equiv b \, mod \, N\), \(a^{\prime} \equiv b^{\prime} \, mod \, N\)のとき, \(aa^{\prime} \equiv bb^{\prime} \, mod \, N\)
証明
上の合同式はそれぞれ\(a = b + kN\), \(a^{\prime} = b^{\prime}+k^{\prime}N\), (\(k, k^{\prime} \in \mathcal{Z} \))と書ける.
\(aa^{\prime} = (b + kN)(b^{\prime} + k^{\prime}N) = bb^{\prime} + N(bk^{\prime} + b^{\prime}k + kk^{\prime}N)\) より, \(aa^{\prime} \equiv bb^{\prime} \, mod \, N\)
証明終わり.
補題2
\(N\)と互いに素な数の集合を\(S := \{r_{1}, r_{2}, ..., r_{\phi(N)}\} \subset \mathcal{Z}/n\mathcal{Z} \)とする.
\(N\)と互いに素な\(a\)について, 写像\(f: r \mapsto ar\)が存在し, \(f(S) = S\)となる.
証明
まずは写像が定義できることを確認する(\(f:S \rightarrow S\)). 背理法を使う.
\(\exists r \in S, f(r) = ar \notin S \)と仮定する. このとき \(c := GCD(ar, N) \neq 1\).
GCDの定義より, \(c| ar\)かつ\(c| N\). また, \(a, r\)はそれぞれ\(N\)と互いに素であるため共通の約数は1しかない. よって\(c=1\)となるが, これは仮定に矛盾する. したがって \(\forall r \in S, f(r) = ar \in S\)となり写像\(f\)が定義できる.
写像\(f\)が単射であるとは, \(f(r) = f(r^{\prime}) \Rightarrow r = r^{\prime} \)を満たす.
\begin{eqnarray} f(r) &=& f(r^{\prime}) \newline ar &=& ar^{\prime} \newline \end{eqnarray}
\(a\)と\(N\)は互いに素なので逆元(\(ax + kN = 1 \)を満たす\(x\))が存在する. 両辺に\(a^{-1}\)をかけると
\begin{eqnarray} r &=& r^{\prime} \newline \end{eqnarray}
よって \(f(r) = f(r^{\prime}) \Rightarrow r = r^{\prime} \)から写像\(f\)は単射であり, \(f(S) = S\)となる.
証明終わり.
補題1,2より, \( (ar_{1})(ar_{2})...(ar_{\phi(N)}) = a^{\phi(N)}r_{1}r_{2}...r_{\phi(N)} \equiv r_{1}r_{2}...r_{\phi(N)} \, mod \, N \).
\( r_{1}r_{2}...r_{\phi(N)} \)は\(\{r_{1}, r_{2}, ..., r_{\phi(N)}\}\)のいずれかと合同になり, \(N\)と互いに素であることから逆元が存在する.
したがって\(a^{\phi(N)} \equiv 1 \, mod \, N \).
オイラーの定理証明終わり.
補題3
1 ~ N-1までの数字で, \(N (= pq)\)と互いに素であるものは\( (p - 1)(q - 1) \)個存在する.
(つまり \( \phi(N) = (p-1)(q-1) \))
証明
愚直に数え上げる.
Nと互いに素でない数は\(p\)か\(q\)の倍数である. (\(GCD(kp, N) = p \neq 1\))
case1: pの倍数
1 ~ N-1までに, pの倍数は\( p, 2p, ..., (q-1) p \)で\( (q-1) \)個.
case2: qの倍数
pの場合と同様に\( (p-1) \)個.
この2つの場合を全体から引けばよいので, \( (N - 1) - (p - 1) - (q - 1) = pq - (p + q) + 1 = (p - 1)(q - 1) \) となり, オイラーのφ関数の計算と一致する.
証明終わり.
\(ed \equiv 1 \, mod \, ( (p-1)(q-1)) \)より, ある整数\(k\)が存在して\(ed = 1 + k(p-1)(q-1) \).
これと補題3, オイラーの定理を使って\(Dec(Enc(m)) = m\)が成り立つことを示す.
\begin{eqnarray} Dec(Enc(m)) &=& (m^{e})^{d} \, mod \, N \newline &=& m^{ed} \newline &=& m^{1 + k(p-1)(q-1)} \newline &=& m^{1} m^{k(p-1)(q-1)} \newline &=& m (m^{(p-1)(q-1)})^{k} \newline &=& m (m^{\phi(N)})^{k} \newline &=& m 1^{k} \newline &=& m \end{eqnarray}
以上.
