概要 #
RSA暗号は現在普及している公開鍵暗号の基礎となる暗号技術である。説明しているサイトは色々あるが、他人が書いたものなので読みにくかった。私にとって分かりやすいように書く。Wikipediaの同項目を参考にした。
証明中で用いたオイラーのφ関数とフェルマーの小定理については後半で解説した。
暗号化と復号 #
0以上n未満の整数の集合を \(\mathbb{Z}_n\)とおく。
異なる２つの素数 \(p, q\) をとり、\( n:=p,q\) を定義する。
\( (p-1)(q-1)\)と互いに素であるような \( e\)（公開鍵）を任意に設定する。
このとき、秘密鍵 \( d \in \mathbb{Z}_n\)は
$$ d \equiv e^{-1} \pmod n $$、すなわち \( e\) のモジュラ逆数となるように作成される。\( e\) のみから導くのは困難だが、 \(p, q\) が既知であれば、ユークリッドの互除法によって導出できる。
平文 \( a \in \mathbb{Z}_n-\{0\}\) について、暗号文 \( b\) は、
$$ b = \{ z \in \mathbb{Z}_n | z \equiv a^e \pmod n \} $$と算出できる。これを復号したものを ( a’]とすると、
$$ a' = \{ z \in \mathbb{Z}_n | z \equiv b^d \pmod n \} $$とかけ、 \( a' = a\) である。
原理の証明 #
\( e\) と \( \phi(n)=(p-1)(q-1)\)（オイラーのφ関数）は互いに素だから、任意の正の整数 \( d\)について、
$$ de -x\phi(n)= 1 $$となるような正の整数 \( x\)が存在する。
定義より
$$ a' \equiv a^{de} \pmod n = a^{x\phi(n)+1} = (a^\phi(n))^x \cdot a \tag{1} $$である。したがって、
$$ a' \equiv (a^\phi(n))^x \cdot a \pmod p \tag{2} \\ a' \equiv (a^\phi(n))^x \cdot a \pmod q \tag{3} $$が成立する。
\( a\)は \( n\)未満であることから、以下の( i )( ii )( iii )によって、すべての場合を扱える。以下では式(1),(2),(3)を用いる。
( i ) \( a\)が \( p,q\)のそれぞれと互いに素であるとき
フェルマーの小定理より
$$ a^{\phi(n)} \equiv 1 \pmod p \tag{3} \\\ a^\phi(n) \equiv 1 \pmod q \tag{4} $$が成立する。式(3),(4)より
$$ a^{\phi(n)} \equiv 1 \pmod n $$であるから、
$$ a' = (a^{\phi(n)})^x \cdot a \equiv a \pmod n $$が成立する。
( ii ) \( a\) が \( p\) の倍数であるとき
$$ a \equiv 0 \pmod p $$であるから、
$$ a' = a^\phi(n) \cdot a \equiv a \pmod p \tag{5} $$である。
\( a\) は \( q\) と互いに素だから、フェルマーの小定理より、
$$ a^{q-1} \equiv 1 \pmod q $$が成立する。よって、
$$ a^\phi(n) = a^{(p-1)(q-1)} \equiv 1 \pmod q $$であることから、
$$ a' = (a^\phi(n))^x \cdot a \equiv a \pmod q \tag{6} $$となる。式(5),(6)より、
$$ a' \equiv a \pmod n $$が成立する。
( iii ) \( a\) が \( q\) の倍数であるとき
( ii )と同様にして
$$ (a^\phi(n))^x \cdot a \equiv a \pmod n $$が示される。
( i )( ii )( iii )より、すべての場合について
$$ a' \equiv a \pmod n $$が成立する。
\( a,a' \in \mathbb{Z}_n-\{0\}\) であるから、 \( a'=a\) である。
オイラーのφ関数 #
正の整数 \( n\) に対して、 \( n\) と互いに素である \( 1\) 以上 \( n\) 以下の整数の個数 \( \phi(n)\) のことをこう呼ぶ。
したがって、 \( n\) が素数ならば \( \phi(n)=n-1\) である。
異なる２つの素数 \(p, q\) について \( n:=pq\) を定義したとき、
$$ \phi(n) = (p-1)(q-1) $$が成り立つ。
フェルマーの小定理 #
任意の素数 \( p\) と、 \( p\) の倍数でない任意の整数 \( a\) について、
$$ a^p \equiv a \pmod p $$が成立する。
証明 #
任意の素数 \( p\) と任意の正の整数 \( m\) をおく。二項定理より、
$$ (m+1)^p=m^p+{}_p\mathrm{C}_1 m^{p-1} + {}_p\mathrm{C}_2 m^{p-2} + \cdots + {}_p\mathrm{C}_{p-1} m + 1 \tag{★} $$が成り立つ。
\( p\) が素数であるため、 \( p\) 未満の正の整数 \( k\) について \( {}_p\mathrm{C}_k\) が \( p\) の倍数となることから、
$$ (m+1)^p \equiv m^p+1 \pmod p $$が成立する。
( i ) 式(★)に \( m=1\) を代入すると、
$$ 2^p \equiv 2 \pmod p $$となり、 \( a=2\) において命題は成り立つ。
( ii ) 命題が \( a=k (k = 2,3,\cdots) \) において成立すると仮定する。
このとき、式(★)から、
$$ (k+1)^p \equiv k^p+1 \pmod p $$であり、仮定より、
$$ k^p \equiv k \pmod p $$であることを踏まえると、
$$ (k+1)^p \equiv k+1 \pmod p $$となり、 \( a = (k+1) \) においても命題が成立する。
( i )と( ii )より、題意は示された。
まとめ #
楽しかった。せっかく原理を学んだので、RSAで平文を暗号化するツールを作りたい。