公開鍵暗号の仕組みと数学的背景

公開鍵暗号の代表のひとつであるRSA暗号の仕組みを見ていく。
まずは暗号化の手順を見ていき，次に数学的な仕組みを解説します。

RSA暗号の手順

RSA暗号では、公開用の鍵として2つの整数の組$${\left(N,E\right)}$$を作り、秘密鍵として2つの整数の組$${\left(N,D\right)}$$を用意する。
以下、$${N,E,D}$$の作り方を説明する。

まず、$${N}$$は大きな2つの素数の積である。
この素数を$${p}$$と$${q}$$とする。
大きな素数を用意するには、適当な大きな数を作り、フェルマーテスト（フェルマーの小定理の対偶を利用し、素数であるかを簡易的に確かめる方法。ただし、確実ではない）を用いる。
つまり、$${N＝p \times q}$$である。

次に、$${p-1}$$と$${q-1}$$の最小公倍数を$${L}$$とする。
公開用の整数である$${E}$$は1より大きく$${L}$$より小さい、$${L}$$と互いに素であるものとする。
$${E}$$を見つけるには、適当な数に対して、ユークリッドの互除法などで最大公約数を計算するとよい。

秘密鍵に使う$${D}$$も1より大きくLより小さい整数であり、$${E\times D \mod L = 1}$$を満たす整数とする。

平文から暗号文を作るには、$${暗号文＝平文^E \mod N}$$ である。
暗号文を平文に戻すには、$${暗号文^D \mod N}$$を計算すればよい。

RSA暗号の数学的裏付け

この暗号を支えている数学的な裏付けはカーマイケルの定理である。
カーマイケルの定理はフェルマーの小定理の一般化であるオイラーの定理を精密化したものである。

オイラーの定理の主張は以下の通りである。
$${n}$$が正の整数であり、$${a}$$を$${n}$$と互いに素な正の整数としたとき$${a^{\varphi \left( n \right)} =1 \mod n}$$である。
ただし、$${\varphi \left(n\right)}$$は$${n}$$と互いに素な1以上$${n}$$以下の自然数の個数である。

RSA暗号で使用した$${N}$$は2つの素数$${p,q}$$の積であった。
よって、$${N}$$と互いに素でない1以上$${N}$$以下の整数は、$${p}$$の倍数と$${q}$$の倍数のみである。
$${N=p\times q}$$であったことを思い出すと、これらは順に$${p,2p,\ldots,qp}$$の$${q}$$個と$${q,2q,\ldots,pq}$$の$${p}$$個存在し、$${pq \left(=N\right)}$$のみが重複している。
よって、1以上N以下のNと互いに素な数は、$${\varphi \left( n \right) = N-q-p+1=pq-p-q+1= \left( p-1 \right) \left( q-1 \right)}$$である。

カーマイケルの定理(Wikipedia)の詳細を省略するが、$${n=pq}$$と因数分解できたとすると$${\varphi (n)}$$を$${L= \mathrm{LCM} \left( p-1,q-1 \right)}$$で置き換えてもよいことがわかる。
$${E \times D \mod L = 1}$$より、$${E \times D＝xL＋1}$$と表せられるので、$${\left( 平文^E \right) ^D=平文^{E \times D}=平文^{xL+1}=平文^{Lx} \cdot 平文^1}$$となり、$${ \mod  n}$$をとると$${1^x \cdot 平文＝平文}$$となり、たしかに、平文を得ることができる。