公開鍵暗号アルゴリズム
ペアリング暗号 ::

RSA 暗号

Takami Torao #RSA
  • このエントリーをはてなブックマークに追加

概要

RSA 公開鍵暗号 (RSA public-key encryption) は大きな数の素因数分解の困難性を利用した公開鍵暗号。最初の実用的な公開鍵暗号で 2000 年に特許が切れている。より鍵の小さい楕円曲線暗号に置き換えられつつあるが現在においても広く利用されている。

Table of Contents

  1. 概要
  2. 素因数分解
  3. RSA 暗号
  4. RSA-FDH 署名
  5. Rabin 暗号
  6. 参考文献

素因数分解

RSA 暗号のアルゴリズムは関係式 \(m^{(p-1)(q-1)} \equiv 1 \pmod{pq}\) に基づいている。この式は以下の定理による。

定理. \((n,e)\) を公開鍵、\(d\) をそれに対応する秘密鍵としたとき、任意の整数 \(0 \le m \lt n\) に対して以下の式が成り立つ (\(e\), \(p\), \(n\) の定義は鍵生成参照)。\[ \begin{equation} (m^e)^d \bmod n = m \label{theorem} \end{equation} \]

Proof. \(ed \equiv 1 \pmod{(p-1)(q-1)}\) より、\(ed = l (p-1)(q-1) + 1\) となる整数 \(l\) が存在する。よって \[ (m^e)^d = m^{ed} = m^{(p-1)(q-1)+1} = m(m^{(p-1)(q-1)})^l \] と表すことができる。ここでフェルマーの小定理「\(p\) を素数とし \(a\) を \(p\) の倍数でない整数とするとき \(a^{p-1} \equiv 1 \pmod{p}\) となる」より。\[ \begin{eqnarray*} (m^e)^d & = & m(m^{(p-1)})^{l(q-1)} \equiv m \pmod{p} \\ & = & m(m^{(q-1)})^{l(p-1)} \equiv m \pmod{q} \end{eqnarray*} \] \(0 \le m \lt n\) であり、\(p\) と \(q\) は互いに異なる素数であることから定理 (\(\ref{theorem}\)) が成り立つ。

RSA 暗号

以下に RSA 暗号の鍵生成、暗号化、復号化の手順を示す。

鍵生成

公開鍵 \((n,e)\) と秘密鍵 \(d\) を以下のように求める。

  1. ランダムに 2 つの素数 \(p\) と \(q\) を選択し、それらの積 \(n=pq\) を計算する。
  2. \(1 \lt e \le \varphi(n)\) かつ \(\gcd(e, (p-1)(q-1))=1\) となる自然数 \(e\) を選択する。
  3. \(1 \lt d \lt (p-1)(q-1)\) かつ \(de \equiv 1 \pmod{(p-1)(q-1)}\) となる自然数 \(d\) を選択する。

\(n\) を RSA モジュラス (RSA-modulus)、\(e\) を暗号化指数 (encryption exponent)、\(d\) を復号化指数 (decryption exponent) と呼ぶ。\(e\) は常に奇数である。

暗号化

公開鍵 \((n,e)\) を使用して平文 \(0 \le m \lt n\) を \(c = m^e \bmod n\) で暗号化する。この計算には拘束指数計算法を使用することができる。

バイト配列やアルファベットのような \(N\) 種類の集合 \(\{0,\ldots,N-1\}\) の任意の列にブロック暗号のように使用するには、それらを基数 \(N\) の数値表現と見なし、\(n\) より小さくなるブロックに分割した単位で暗号化を行う (端数は CBC のようなパディングを使用する)。対象とするメッセージは \(0 \le m \le N^k-1 \lt n\) となることから、ブロックの単位となる桁数 \(k\) は \(n\) を基数 \(N\) で表現したときの桁数となり \(k=\lfloor \log_N n \rfloor\) で表すことができる。これより \(m = \sum_{i=1}^k m_i N^{k-i}\) となり求めた暗号値 \(c = m^e \bmod n\) を再び \(N\) 進数で表した \(c = \sum_{i=1}^k c_i N^{k-i}\) となるような \(c_i\) の並びが暗号値の表現となる。

復号化
暗号文 \(c=m^e \bmod n\) より、秘密鍵 \(d\) を使用して \[ c^d \bmod n = (m^e \bmod n)^d \bmod n = (m^e)^d \bmod n = m \] を計算して平文 \(m\) を得る。

RSA-FDH 署名

FDH (full-domain hash) とはハッシュ値が公開鍵と同じ長さとなるハッシュ関数のこと。RSA-FDH 署名は RSA 暗号と FDH 関数を使用して署名を生成する。この署名は RSA 仮定と \(H\) のランダムオラクルモデルの下で安全である。

鍵生成
RSA 暗号と同様に秘密鍵 \(d\)、公開鍵 \((n,e)\) を作成する。また full-domain ハッシュ関数を \(H\) とする。
署名
メッセージ \(m\) のハッシュ値 \(H(m)\) に対して秘密鍵 \(d\) を使った署名 \(s = H(m)^d \bmod n\) を算出する。
検証
署名 \(s\) に対して \(H(m) \equiv s^e \pmod{n}\) が成り立てば署名が正しいことが検証できる。

RSA-FDH 署名は簡単だが \(n\) が大きくなるに伴ってハッシュ値も大きくなるためあまり計算効率は良くない。より効率的な署名アルゴリズムに RSA-PSS 署名 (probabilistic signature scheme) がある。

Rabin 暗号

RSA 暗号スキームは素因数分解の計算困難性に依存しているが、RSA 問題が素因数分解の問題と同等の困難さを持つかは証明されていない。Rabin 暗号は 1979 年に開発された公開鍵暗号システム。1979年にマイケル・ラビンが発表した公開鍵暗号である。選択平文攻撃で解読することと素因数分解問題を解くことが等価であることが証明された初の暗号である。

  • 鍵生成: \(p \equiv q \equiv 3 \bmod 4\) となる 2 つの素数をランダムに選択し \((p, q)\) を秘密鍵とする。\(n=pq\) を公開鍵とする。
  • 暗号化: 平文 \(m \in \{0,\ldots,n-1\}\) に対して \(c = m^2 \bmod n\) を暗号文とする。
  • 復号化: \[ \left\{ \begin{array}{rcl} m_p & = & c^{(p+1)/4} \bmod p \\ m_q & = & c^{(q+1)/4} \bmod q \end{array} \right. \]

参考文献

  1. 辻井重男, 笠原正雄, 有田正剛, 境隆一, 只木孝太郎, 趙晋輝, 松尾和人, "暗号理論と楕円曲線", 森北出版 (2008)
  2. J.A. ブーフマン, "暗号理論入門 原書第3版, 丸善出版 (2012)
  3. 光成滋生, "クラウドを支えるこれからの暗号技術", 秀和システム (2015)