RSA 暗号

1977年に発表された公開鍵暗号であり，発明者である Ron Rivest，Adi Shamir， Len Adleman の頭文字を採って命名された．暗号化・復号とディジタル署名を実現できる公開鍵暗号アルゴリズムとして最初に公開されたものである． RSA 暗号は，大きな数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の1つである．

RSA 暗号のアルゴリズムは，RSA Security 社がライセンスを独占していたが，特許期間満了に伴い 2000年9月6日からは自由に使用できるようになっている．

RSA 暗号鍵の生成

任意の異なる 2 つの大きな素数 $p$ と $q$ を選びその積 $n$ を計算する ($n = pq$)．
現在，$n$ のビット数としては，1024 または 2048 が多く用いられている（$p,\ q$ はその半分）．
$p - 1$ と $q - 1$ の最小公倍数 $\lambda(n)$ を計算し，$\lambda(n)$ と互いに素で $\lambda(n)$ より小さな任意の整数 $e$ を選ぶ． \[ \lambda(n) = \mathrm{lcm}(p-1, q-1) \] \[ e \in Z_{\lambda(n)}\ (3 \le e \le n - 1,\ \gcd(e, \lambda(n)) = 1) \]
$ed \equiv 1 \pmod{\lambda(n)}$ を満たす $d$ を求める． \[ d = 1/e \bmod \lambda(n) \]
$n$，$e$ を公開鍵，$d$ (または $p$，$q$) を秘密鍵とする．
公開鍵 $e$ は，すべての環境において共通にすることができる（このとき，他の公開鍵である法 $n$ は共通にはできない）．これにより，実際に配布する公開鍵の長さを減らすことができる．
公開鍵 $e$ は大きくあるべきであるが，処理時間や使用メモリ量の観点からは効率的に指数計算ができることが望ましい．固定的な $e$ を用いるときには，次のフェルマー数 $F_4$ の利用が効果的である． \[ F_4 = 2^{2^4} + 1 = 65537 \] この $e$ 値は，17回の乗算で指数の計算ができ，平均的に 30倍復号より高速になる．

RSA 暗号プリミティブ

数学的に定義される基本的な暗号の演算アルゴリズムを暗号プリミティブと言う．

RSA 暗号は「落とし戸付き一方向性関数」を用いて暗号化を行っている．この関数は，変換(暗号化)することは容易であるが，元に戻す(復号する)ことは極めて困難な関数である．しかし，あるヒント(落とし戸)を知っていれば容易に元に戻せるような関数である．

暗号化・復号
- 暗号化
  対象データ $M$ と公開鍵 $n,\ e$ より，暗号化データ $C = M^e \bmod n$ を生成する．ここで， $C$ は $n$ 未満の整数である．
- 復号
  暗号文 $C$ と秘密鍵 $d$ より，復号データ $M = C^d \bmod n$ を生成する．
ディジタル署名
RSA 暗号においては平文と暗号文の定義域が同じ（平文空間＝暗号文空間）であるため，任意のメッセージを暗号文とみなして復号することができる．すなわち，秘密鍵を用いて任意のメッセージに対して署名を生成でき，公開鍵を用いてその署名データを復号して元の文書と一致するかを調べることで署名の検証ができる．
- 署名生成
  署名対象データ $M$ と秘密鍵 $d$ より，署名 $S = M^d \bmod n$ を生成する．ここで，$S$ は $n$ 未満の整数である．
- 署名検証
  署名対象データ $M$，署名 $S$ および公開鍵 $e$ より，署名の正当性を以下の関係が成立するか否かで判定する． \[ M = S^e \bmod n \]

暗号プリミティブの制約

RSA 暗号の入力は，公開鍵を $n$ とすると $0 \sim (n - 1)$ の範囲の整数である必要があり (法 $n$ での剰余演算)，$n$ 以上の値の平文を暗号化するには，平文を $n$ 以下の値に分割して処理しなければならない．しかし，RSA暗号処理は共通鍵暗号に比べて処理時間がかかるため，このような分割処理は通常は行われない (共通鍵などの $n$ 以下の短いデータのみを暗号化対象とする)．ディジタル署名の場合には，対象データをハッシュ関数で処理することで，$n$ 以下の値にして処理される．
平文 $M$ が $M^e \lt n$ の場合，暗号文は $C = M^e$ となり，$C$ の $e$ 乗根を計算するだけで平文 $M$ が復元できてしまう. そのため，実際の暗号への応用においては，$M$ の高位ビットに 1 を挿入することでこの状況を避けるようにする (パディング処理)．

CRT 鍵による復号の高速化

RSA暗号において，CRT (中国人剰余定理) を使うと復号および署名生成 ($M = C^d \bmod n$) 演算を高速化できる．

RSA暗号の秘密鍵を

\[ dP = d \bmod (p-1) \] \[ dQ = d \bmod (q-1) \] \[ qI = 1/q \bmod p \]

として，$p,\ q,\ dP,\ dQ,\ qI$ として保持していると，復号時に中国人剰余定理を使って処理を高速化できる．中国人剰余定理で使用する定数を事前に計算し鍵として保持するものである．

すなわち，復号時には以下の処理を行う (暗号文を C とする)．

$C_p = C \bmod p$，および　$C_q = C \bmod q$ を計算する．
$M_p = C_p^{dP} \bmod p$，および　$M_q = C_q^{dQ} \bmod q$ を計算する．
中国人剰余定理により，$M = M_p \bmod p$ かつ $M = M_q \bmod q$ を満たす $M$ を求める．

RSA 暗号スキーム

RSA 暗号プリミティブを単純に用いただけでは，強力な攻撃者に対しては暗号として安全ではない．このため，パディング処理やハッシュ関数などを利用してより複雑な手順（暗号スキーム）に変換することにより安全性を高める方式が採られる．これを暗号スキームという．

暗号スキームでは，次のような処理が行われる．

暗号化
鍵とメッセージが定まった場合，その暗号文は固定的に定まる．メッセージが限定された空間から選ばれた場合，暗号文から元のメッセージを求めることが容易になる．これを避けるために，メッセージに乱数成分を含めたパディング処理を行う．
署名
メッセージ $M$ をハッシュした値 $h(M)$ に対して，乱数を含んだある種の変換を行う(エンコード処理)．この変換した値に対して暗号プリミティブを適用するので，メッセージが同じでも署名は異なるようになる．署名検証時には，エンコードデータを戻す処理(デコード処理)が行われ，埋め込まれた乱数等のデータの影響を取り除く．
このエンコードの方法には，何種類かあり，RSA暗号と言ってもエンコードの有無やエンコード方法を指定しないと一意には決まらない．(→ メッセージ・エンコーディング)

以下に，RSA 暗号のスキームの例を示す．

RSA_PKCS (PKCS#1v1.5)
PKCS#1v1.5 では，RSA 公開鍵暗号に適用可能なパディングアルゴリズムを規定している．PKCS#1v1.5 によるパディングアルゴリズムは，3バイトの固定バイト（マーク）と8バイト以上の乱数バイト($PS$) を平文メッセージ $M$ に追加するものである．
\[ EM = 0x00\ ||\ 0x02\ ||\ PS\ ||\ 0x00\ ||\ M \]
RSA_OAEP
PKCS#1v1.5 のような単純なパディングアルゴリズムでは，選択暗号文攻撃を許す危険性があることが指摘され，パディングアルゴリズムに選択暗号文攻撃に対する耐性が求められるようになった．PKCS#1v2.0 で規定されている OAEP は，暗号文の乱数性と暗号文の検査の機能を与えた上で，PKCS#1v1.5 で規定されていたパディングアルゴリズムの脆弱性を修正し，選択暗号文攻撃に対して証明可能な安全性を提供する．

このように，RSA アルゴリズムを用いた暗号化や署名には，スキームの違い（パディング方式やハッシュ方法の違い）により幾つかの方式が存在する．異なる方式間では，互換性はない，

完全性

RSA 暗号の暗号化・復号が正しく行われることの証明は以下のとおりである．

暗号化
$x$ の暗号化：$E(x) = x^e \bmod n = y$
復号
暗号文 $y$ の復号結果：$D(y) = y^d \bmod n$

上記の RSA暗号が正しく暗号文を復号できること，すなわち， \[ D(y) = D(E(x)) = x \] になることを示す．この式は， \[ D(y) = y^d \bmod n = (x^e)^d \bmod n = x^{ed} \bmod n \] となるので，結局 \[ x^{ed} \equiv x \pmod{n} \] を示せばよい．
ここで， \[ ed \equiv 1 \pmod{\varphi(n)} \] より，$ed$ を $\varphi(n)$ で割った商を $k$ とすると，余りは 1 であり \[ ed = \varphi(n) k + 1 \] と書ける．
これより，復号の式は， \[ D(y) = x^{ed} \bmod n = x^{\varphi(n) k + 1} \bmod n \] となる．
$\gcd(x, n) = 1$ のときは，$x^{\varphi(n)} \equiv 1 \pmod{n}$ であるので（オイラーの定理： $n$ が素数の場合はフェルマーの小定理になる）， \[ D(y) = x^{\varphi(n)k + 1} \bmod n = (x^{\varphi(n)})^k ・ x^1 \bmod n = 1^k・x^1 \bmod n = x \] となり， \[ D(y) = D(E(x)) = x \] が成立する．
$\gcd(x, n) \ne 1$ のときは，$n = pq$ なので，$\gcd(x, n) = p$ または，$\gcd(x, n) = q$ である ($x$ が $p$ の倍数または $q$ の倍数)．
また， \[ x^{ed} \equiv x \pmod{n} \] は， \[ x^{ed} \equiv x \pmod{p} \] \[ x^{ed} \equiv x \pmod{q} \] が同時に成り立つのと同値である (これを，各ケースで確認)．
$\gcd(x, n) = p$ すなわち，$x$ が $p$ の倍数のときは， \[ x^{ed} \equiv x \pmod{p} \] は常に成立する． \[ x^{\varphi(n)k + 1} \bmod q = x^{k(p-1)(q-1)+1} = (x^{q-1})^{k(p-1)} x \bmod q = x \] また，$\gcd(x, n) = q$ すなわち，$x$ が $q$ の倍数のときは， \[ x^{ed} \equiv x \pmod{q} \] は常に成立する． \[ x^{\varphi(n)k + 1} \bmod p = x^{k(p-1)(q-1)+1} = (x^{p-1})^{k(q-1)} x \bmod p = x \]