RSA暗号 - akashisnの日記

公開鍵暗号 - RSA - 基礎より

はじめにパラメータ ${p,q}$ を決める。 ${p,q}$ はそれぞれ十分に巨大な素数で、その積が ${n}$ となる。 \begin{align} n = pq \end{align} 平文 ${m}$ について、 \begin{align} m < n \end{align} となるような ${m}$ を選択する（大きい場合は分割したりする）。また、 \begin{align} \mathrm{gcd}((p-1)(q-1),e) = 1 \end{align} となる ${e}$ を定義する。つまり ${(p-1)(q-1)}$ と ${e}$ は互いに素である。 ${p,q,n,e}$ から値 ${d}$ を計算する。この値は、 \begin{align} d \equiv e^{-1} \pmod{\ (p-1)(q-1)} \end{align} で計算される。ただし ${e^{-1}}$ は法 ${(p-1)(q-1)}$ 上での ${e}$ の逆元を表している。

逆元とは？

これから群論を学ぶ方のための入門講座 – びりあるの研究ノート - 逆元より

例えば、 ${7}$ を法として ${2}$ の逆元 ${x}$ とは、 ${0 \le x \le 7}$ であり、 ${2x}$ を ${7}$ で割ったあまりが ${1}$ になる数 ${x}$ 。つまり以下のように計算されて、 \begin{align} 2 \times 1 &= 2 \\ 2 \times 2 &= 4 \\ 2 \times 3 &= 6 \\ 2 \times 4 &= 8 \equiv 1 \bmod 7 \\ 2 \times 5 &= 10 \equiv 3 \bmod 7 \\ 2 \times 6 &= 12 \equiv 5 \bmod 7 \\ \end{align}

${2}$ に ${4}$ を掛けて ${7}$ で割ったあまりが ${1}$ になるので、 ${7}$ を法とした ${2}$ の逆元は ${4}$ である。

${(p-1)(q-1)}$ と ${e}$ が互いに素ではない場合、法 ${(p-1)(q-1)}$ 上での逆元を計算することができない（つまり、 ${d}$ の計算ができない）。

これらのパラメータのうち、 ${(e,n)}$ を公開鍵、 ${(d,n)}$ を秘密鍵とする。 ${p,q}$ がわかってしまうと ${d}$ を計算することができてしまうため、 ${d}$ の生成後に破棄されるのが望ましい。

暗号化

平文を ${m}$ 、暗号文を ${c}$ とした時、RSAの暗号化関数 ${\mathrm{Enc}(m)}$ は以下のように定義される。

\begin{align} c = \mathrm{Enc}(m) = m^{e} \bmod n \end{align}

復号

逆に暗号文を ${c}$ とした時、以下のように定義されたRSAの復号関数 ${\mathrm{Dec(c)}}$ により平文 ${m}$ が求まる。

\begin{align} m = \mathrm{Dec}(c) = c^{d} \bmod n \end{align}

根拠

フェルマーの小定理は素数の性質についての定理である。

フェルマーの小定理

${p}$ を素数とし、 ${a}$ を ${p}$ の倍数でない整数（ ${a}$ と ${p}$ は互いに素）とするときに、 \begin{align} a^{p-1} \equiv 1 \pmod{\ p} \end{align} すなわち、 ${a}$ の ${{p-1}}$ 乗を ${p}$ で割ったあまりは ${1}$ であるというもの。

フェルマーの小定理の一般化がオイラーの定理である。

オイラーの定理

${n}$ が正の整数で ${a}$ を ${n}$ と互いに素な正の整数としたとき、 \begin{align} a^{\phi(n)} \equiv 1 \pmod{\ n} \end{align} が成立する。ここで ${\phi(n)}$ はオイラーの ${\phi}$ 関数である。

オイラーの ${\phi}$ 関数は ${n}$ までの自然数のうち ${n}$ と互いに素なものの個数である。

オイラーの ${\phi}$ 関数

オイラーの ${\phi}$ 関数（トーシェント関数） ${\phi(n)}$ は正の整数 ${n}$ に対して、 ${1}$ から ${n}$ までの自然数のうち ${n}$ と互いに素なものの個数返す関数である。

${p}$ を素数とすると、 ${1}$ から ${p-1}$ のうちに ${p}$ の素因子である ${p}$ を因子として含むものは存在しないから、 ${\phi(p) = p-1}$ が成り立つ。また、 ${m,n}$ を互いに素な自然数とすると、 ${\phi(mn) = \phi(m)\phi(n)}$ が成り立つ。

証明

復号関数がもとの値を必ず復元できるかを証明する。

${c^{d} \pmod{\ n}}$ は、 ${m^{ed} \pmod{\ n}}$ と書ける。つまり、 \begin{align} c^{}\equiv m^{ed} \pmod{\ n} \end{align} となる。ここで、 ${ed}$ は ${(p-1)(q-1)}$ を法として ${1}$ と合同、つまり ${d}$ は ${e}$ の逆元なので、ある定数 ${k}$ が存在し、 \begin{align} ed = 1 + k(p-1)(q-1) \end{align} と表せる。また、オイラーの ${\phi}$ 関数より、 \begin{align} (p-1)(q-1) = \phi(pq) = \phi(n) \end{align} が成り立つ。したがって、 \begin{align} ed = 1 + k\phi(n) \end{align} 先程の式に代入すると、 \begin{align} c^{d} &\equiv m^{1+k\phi(n)} \pmod{\ n} \\ &\equiv m^{1} \cdot m^{k\phi(n)} \pmod{\ n} \end{align} オイラーの定理より、 ${m^{k\phi(n)} \equiv 1^{k} \pmod{\ n}}$ であるので、 \begin{align} \equiv m \pmod{\ n} \end{align} ${m \le n}$ であるので、 \begin{align} = m \end{align} したがって必ず復元できることが証明できた。

環境

$ uname -a
Linux XPS-13-9360 4.13.0-16-generic #19-Ubuntu SMP Wed Oct 11 18:35:14 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 17.10
Release:    17.10
Codename:   artful

Pythonのインストール

この記事において使用するPythonは以下でインストールしたものとする

#
# Python with pyenv
#

# Install dependencies
$ sudo apt install -y make build-essential libssl-dev zlib1g-dev libbz2-dev libreadline-dev\
          libsqlite3-dev wget curl llvm libncurses5-dev libncursesw5-dev xz-utils tk-dev

# Install pyenv-installer
$ curl -L https://raw.githubusercontent.com/pyenv/pyenv-installer/master/bin/pyenv-installer | bash

# Add to env
$ cat <<\EOF >> $HOME/.env
# Initial setting of pyenv.
export PYENV_ROOT=$HOME/.pyenv
export PATH=$PYENV_ROOT/bin:$PATH
eval "$(pyenv init -)"
# Initial setting of pyenv-virtualenv.
eval "$(pyenv virtualenv-init -)"
EOF

# reload .env
$ source $HOME/.env

# Add .env to .bashrc
$ echo "source $HOME/.env" >> $HOME/.bashrc

# Install Python 3.6.3.
$ pyenv install 3.6.3

# Set the system default to Python3.6.2.
$ pyenv global 3.6.3

GMPY2のインストール

plain RSAに対する攻撃手法を実装してみる - ももいろテクノロジーより

Pythonは標準で多倍長整数を扱うことができるため、GNU Multi-Precision Library（GMP）のような多倍長整数ライブラリを持ちなくても大きな整数を扱うことができる。しかし、整数の範囲でのn乗根や拡張ユークリッドの互除法、 ${\bmod n}$ における逆元演算を行うに当たっては、GMPが提供する関数を使うと簡単である。

PythonでGMPを使うにはGMPY2を使うといい。GMPY2にはGMPに加えMPFR(多倍長浮動小数点)やMPC(多倍長複素数)も使うことができる。

GMPY2のドキュメント

$ sudo apt install libgmp3-dev
$ sudo apt install libmpfr-dev libmpfr-doc libmpfr6
$ sudo apt install libmpc-dev
$ pip install gmpy2

ソースコード・実行例

${n,e,c,p,q}$ から平文 ${m}$ を求めるスクリプト

RSA cipher