![見出し画像](https://assets.st-note.com/production/uploads/images/110513613/rectangle_large_type_2_c624e31d5c36a5255a5d34ac49ca5a41.png?width=1200)
公開鍵暗号の仕組みと数学的背景
公開鍵暗号の代表のひとつである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 平文=平文}$$となり、たしかに、平文を得ることができる。
最後までお読みいただきありがとうございます。「スキ」をしていただけるととても励みになります。