RSA 暗号

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

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

RSA 暗号鍵の生成

  1. 任意の異なる 2 つの大きな素数 pq を選びその積 n を計算する ( n = p q).
    現在, n のビット数としては,1024 または 2048 が多く用いられている(pq はその半分).
  2. p - 1 と q - 1 の最小公倍数 λ(n) を計算し,λ(n) と互いに素で λ(n) より小さな任意の整数 e を選ぶ.

    λ(n) = LCM (p-1, q-1)

    eZλ(n)  (3 ≦ en - 1,  GCD (e, λ(n)) = 1)

  3. e d = 1 mod λ(n)を満たす d を求める.

    d = 1/e mod λ(n)

  4. n, e を公開鍵,d (または pq) を秘密鍵とする.
    公開鍵 e は,すべての環境において共通にすることができる(このとき,他の公開鍵である法 n は共通にはできない).これにより,実際に配布する公開鍵の長さを減らすことができる.
    公開鍵 e は大きくあるべきであるが,処理時間や使用メモリ量の観点からは効率的に指数計算ができることが望ましい.固定的な e を用いるときには,次のフェルマー数 F4 の利用が効果的である.

    F4 = 224 + 1 = 65537

    この e 値は,17回の乗算で指数の計算ができ,平均的に 30倍復号より高速になる.

RSA 暗号プリミティブ

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

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

暗号プリミティブの制約

CRT 鍵による復号の高速化

RSA暗号において,CRT (中国人剰余定理) を使うと復号および署名生成 (M = Cd mod n) 演算を高速化できる.

RSA暗号の秘密鍵を

 dP = d mod (p-1)

 dQ = d mod (q-1)

 qI = 1/q mod p

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

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

  1. Cp = C mod p,および Cq = C mod q を計算する.
  2. Mp = CpdP mod p,および Mq = CqdQ mod q を計算する.
  3. 中国人剰余定理により,M = Mp mod p かつ M = Mq mod q を満たす M を求める.

RSA 暗号スキーム

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

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

以下に,RSA 暗号のスキームの例を示す.

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

完全性

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

RSA 暗号の安全性

RSA暗号などの暗号を解読するための計算量に安全性の根拠を置く暗号では,解読に投入できる計算機パワーとの兼ね合いで安全性が判断される (計算量的安全性).これは,使用する暗号の鍵長に依存する. RSA社は,RSA暗号解読コンテストを1991年から2007年まで実施しており,最新の計算機環境を使って,768ビットまでの整数が素因数分解されている.鍵長が短い RSA暗号は既に破られているとも言える. 1991年当時は, 330ビットが解読されたので,この間の解読の進展度合いが今後も同じように続くと仮定すると,1024ビットはあと10年程度で解読されることになる (768ビットと1024ビットの解読では,解読計算量(MIPS*YEAR)的には約1500倍違う).

現在,RSA暗号では 1024ビット~4096ビットが使われることが多いが,一般的な利用ではまだこのビット数で10年近くは大丈夫と思われる (1024ビットは推奨されていない). 暗号強度が不足するという事態になれば,さらにビット数を増やすことになるが.RSA暗号のビット数があまり増えるようなことになれば,より少ないビット数で同じ安全性が確保できる楕円曲線暗号方式を使うことが多くなると思われる.

inserted by FC2 system