- RSA暗号を勉強しました
- 暗号文 $C$ を $C \equiv M^e \pmod n$ で暗号化する時、元の文 $M$ が $M \equiv C^d \pmod n$ で復号できる理由を確認したのでmemo
前提：RSA暗号について
- 以下3つの数字を用意
- 異なる素数 $p$、$q$
- $(p-1)(q-1)$と互いに素な自然数 $e$
- この時、元の文 $M$ を暗号文 $C$ に変換する式が $C \equiv M^e \pmod n$
- この時元の文 $M$ を復号する式が $M \equiv C^d \pmod n$
- ただし、$n$、$d$は
- $n = pq$
- $de - k(p-1)(q-1) = 1$を満たす自然数$d$、$e$
復号化の仕組み
- 確認したいこと：$M \equiv C^d \pmod n$で復号できる仕組み
- $C^d \pmod n$が$M$になることが計算できれば良い
$C^d$を計算する
$C^d \pmod n \equiv M$を計算する流れは以下となる。
$(1)$、$(4)$の計算の詳細は後述にて解説する。
$(2)$は既出 $de - k(p-1)(q-1) = 1$ から $de = 1 + k(p-1)(q-1)$を代入
$(3)$は指数の1を前に出した
$$
\begin{align}
C^d \pmod n &\equiv M^{ed} \pmod n \cdots(1) \\
&\equiv M^{k(p-1)(q-1) + 1} \pmod n \cdots(2) \\
&\equiv M \cdot M^{k(p-1)(q-1)} \pmod n \cdots(3) \\
&\equiv M \cdots(4)
\end{align}
$$
$(1)$ $C^d \pmod n \equiv M^{ed} \pmod n$
$C \equiv M^e \pmod n$の時、$C = M^e + nx$と表現できる($x$は任意の整数)。
この時、
$$
\begin{aligned}
C^d &= (M^e + nx)^d \\
&= M^{ed} + {}_d \mathrm{C}_1M^{e(d-1)}nx + {}_d \mathrm{C}_2M^{e(d-2)}(nx)^2 + \cdots
\end{aligned}
$$
となる。初項$M^{ed}$を除く全ての項に$n$が含まれているため、$n$で割り切れる。よって
$$
C^d \pmod n \equiv M^{ed} \pmod n
$$
となる
$(2)$ $M \cdot M^{k(p-1)(q-1)} \pmod n \equiv M \cdot 1 \pmod n$
以下の順序で計算していく。
- $(2-1)$ $M^{(p-1)(q-1)} \equiv 1 \pmod n$を計算
-
$(2-2)$ $M^{(p-1)(q-1)} \equiv 1 \pmod n$ の時、
$M^{k(p-1)(q-1)} \equiv 1 \pmod n$ となる
-
$(2-3)$ $M^{k(p-1)(q-1)} \equiv 1 \pmod n$ の時、
$M \cdot M^{k(p-1)(q-1)} \pmod n \equiv M \cdot 1 \pmod n$ となる
$(2-1)$ $M^{(p-1)(q-1)} \equiv 1 \pmod n$を計算する
フェルマーの小定理より素数$p$、$p$の倍数でない正の整数$a$は
$$
a^{p-1} \equiv 1 \pmod p
$$
となる。この性質を利用する
フェルマーの小定理より
$M^{(p-1)(q-1)} = (M^{(q-1)})^{(p-1)} \equiv 1 \pmod p$
$M^{(p-1)(q-1)} = (M^{(p-1)})^{(q-1)} \equiv 1 \pmod q$
となる。これらの式が成立する時 $pq = n$ の$n$に対して、
$$
M^{(p-1)(q-1)} \equiv 1 \pmod n
$$
が成立する。またこの時、
$$
M^{k(p-1)(q-1)} \equiv 1 \pmod n
$$
となる。
$M^{(p-1)(q-1)} \equiv 1 \pmod n$が成立する理由
$M^{(p-1)(q-1)} \equiv 1 \pmod p$ より $M^{(p-1)(q-1)} = pX + 1$
$M^{(p-1)(q-1)} \equiv 1 \pmod q$ より$M^{(p-1)(q-1)} = qY + 1$
※$X$、$Y$は任意の整数
これらの式より
$$
\begin{aligned}
pX + 1 &= qY + 1 \\
pX &= qY
\end{aligned}
$$
$p$と$q$は異なる素数のため、この式が成立するためには$X$は$q$の、$Y$は$p$の整数倍でなければならない。
これより
$M^{(p-1)(q-1)} \equiv 1 \pmod p$
$M^{(p-1)(q-1)} \equiv 1 \pmod q$
が成立する時、
$$
M^{(p-1)(q-1)} \equiv 1 \pmod n
$$
となる。
$(2-2)$ $M^{(p-1)(q-1)} \equiv 1 \pmod n$ の時、$M^{k(p-1)(q-1)} \equiv 1 \pmod n$ となる
※考え方は 「$C^d \pmod n = M^{ed} \pmod n$ の理由」と同じ
$M^{(p-1)(q-1)} \equiv 1 \pmod n$より、$M^{(p-1)(q-1)} = nx + 1$
$$
\begin{aligned}
M^{k(p-1)(q-1)} &= (1 + nx)^k \\
&= (1)^k + {}_k \mathrm{C}_11^{(k-1)}nx + {}_k \mathrm{C}_21^{(k-2)}(nx)^2 + \cdots + (nx)^k \\
&= 1 + {}_k \mathrm{C}_1nx + {}_k \mathrm{C}_2(nx)^2 + \cdots + (nx)^k
\end{aligned}
$$
これより、$M^{k(p-1)(q-1)}$は初項 $1$ を除くと、$n$の倍数になるため、
$M^{(p-1)(q-1)} \equiv 1 \pmod n$ の時、
$$
M^{k(p-1)(q-1)} \equiv 1 \pmod n
$$
となる。
$(2-3)$ $M^{k(p-1)(q-1)} \equiv 1 \pmod n$ の時、 $M \cdot M^{k(p-1)(q-1)} \pmod n \equiv M \cdot 1 \pmod n$ となる
$M^{k(p-1)(q-1)} \equiv 1 \pmod n$より、$M^{k(p-1)(q-1)} = nx + 1$
※$x$は任意の自然数
これより、
$$
\begin{aligned}
M \cdot M^{k(p-1)(q-1)} \pmod n &\equiv M(nx + 1) \pmod n \\
&\equiv Mnx + M \pmod n \\
&\equiv M
\end{aligned}
$$
まとめ
以上より$C \equiv M^e \pmod n$で暗号化した元の文$M$が$C^d \pmod n \equiv M$で復号できることを確認した。
終わりに
- RSA暗号の仕組み解説には色々な定理や方法論が用いられますが、今回はなるべくその部分も順序立てて計算しました。
- フェルマーの小定理は証明だけ理解して、使用しました
(^_^;)
- フェルマーの小定理は証明だけ理解して、使用しました
- こういった計算をしっかりするのは久しぶりだったため、厳密性がなかったり、誤りがある箇所があるかもしれません。
- そういった箇所は発見次第、修正していきます
今後の展望
- 今回は暗号化の式ありきで、復号がなぜ同じ式でできるのかを確認しました。
- RSA暗号の仕組みを使用して、暗号化・復号化のコードを書こうとした時に、復号化がなぜこの式でできるのか疑問に感じたため
- 今後はこの理解した内容を踏まえて、RSA暗号の仕組みを使ったコーディングを進めたいです
-
機会があれば、復号化の式に限らず、もう少しRSA暗号について、深掘りをしたいです
- フェルマーの小定理で端折ったところの追記
- 暗号化の式について
など
コメント