公開鍵暗号
公開鍵暗号とは
公開鍵暗号は,公開鍵と秘密鍵という異なる2つの鍵を用意しておき,暗号化の際には公開されている通信相手(復号者)の公開鍵を用い,復号には自分の秘密鍵を用いる.
このため,事前に鍵を共有する必要がなく,自分の秘密鍵のみを秘密にしておくだけでよい.ここで,公開鍵と秘密鍵はある数学的な関係を持った数値であり,暗号アルゴリズムに基づき生成されるものである.
このとき,どのような送信メッセージ(平文)に対しても,暗号化鍵(公開鍵)によって暗号化されたメッセージ(暗号文)が復号鍵(秘密鍵)によって復号され,元の平文を得られることが前提になる.
暗号化鍵は公開されているので,ネットワーク内のどの相手に対しても平文を暗号化して送信することができる.ただし,暗号化鍵と復号鍵は逆写像の関係にあるので,安全性を保持するためには,暗号化鍵から復号鍵を求めることが困難でなければならない.
公開鍵暗号方式の概念は,W. DiffieとM. Hellmanにより以下のように説明されている.
平文のメッセージ空間 $\{M\}$ における2種類の可換な変換方式
$E_K : \{M\} \rightarrow \{M\}$
$D_K : \{M\} \rightarrow \{M\}$
で,以下のような性質を満たす $E_K$ と $D_K$ があれば,$E_K$ を暗号化アルゴリズム,$D_K$ を復号アルゴリズムとする公開鍵暗号が実現できる. ここで ,$K$ は鍵 (暗号化鍵と復号鍵)である.
- すべての $K$ に対して,$E_K$ と $D_K$ は逆変換である.
- すべての $K$ および $M$ に対して,$E_K$ と $D_K$ の計算は容易である.
- ほとんどすべての $K$ に対して,$E_K$ から $D_K$ を求めるのは困難である.
- すべての $K$ に対して,$K$ から $E_K$ と $D_K$ の組を求めるのは容易である.
上述の性質を満たすために,公開鍵暗号方式では一方向性関数と呼ばれる関数を利用する.これは,この関数を $f$ とした時,平文 $M$ から暗号文 $C = f(M)$ を求めるのは簡単であるが,暗号文 $C$ から平文 $M
= f^{-1}(C)$ を求めるのは極めて困難であるという性質をもつ関数である.
上記の一方向性を満足する関数を実現する代表的な数学上の問題として,以下の問題が公開鍵暗号の基盤として用いられている.
- 素因数分解問題
合成数からその素因数を求める問題である.
RSA暗号では,合成数 $n (= pq)$ が公開鍵,素因数 $p$,$q$ が秘密鍵に対応する.
- 有限体上の離散対数問題
$y = g^x \bmod p$ の $y$ から $x$ を求める問題 ($p$ は素数,$g$ は有限体 $F_p$ の原始元)を離散対数問題という.
$y$ が公開鍵,$x$ が秘密鍵 ($g$,$p$ は公開システムパラメータ)に対応する.
- 楕円曲線上の離散対数問題
$Y = x G$ の $Y$ から $x$ を求める問題 ($Y$,$G$ は有限 $F_q$ 上の楕円曲線上の点,$x G$ は $G$ をスカラー倍 ($x$ 倍)する演算)である.
$Y$ が公開鍵,$x$ が秘密鍵 ($G$ は公開システムパラメータ)に対応する.
パディング
共通鍵暗号におけるパディングの主な目的は,平文メッセージの長さを一定長(ブロック長)にすることである.
これに対し,公開鍵暗号におけるパディングの目的は以下の2点にある.
- 暗号文に乱数性を持たせる
RSA暗号のような確定的な暗号では鍵とメッセージが定まった場合,その暗号文は固定的に定まる.メッセージが限定された空間から選ばれた場合,暗号文から元のメッセージを求めることが容易になる.これを避けるためには,メッセージに乱数成分を含めることが有効になる.すなわち,メッセージに乱数をパディングすることが行われる.
同様に,ディジタル署名の生成においても,安全性の向上や署名鍵の長さとの関係から一般に署名対象データに対してパディングが行なわれる.
- 暗号化処理が正しく行われたことを確認する手段を設ける
不正に作成された暗号文を排除することができる.
例えば,RSA署名ではメッセージのハッシュ値を署名鍵で暗号化することで署名値を生成するので,攻撃者がメッセージのハッシュ値を暗号化メッセージに見せかけて送付して相手に復号させることにより,復号の実行者の関知の埒外でRSA署名を生成させることができてしまう.
この対策として,暗号化の前にパディングによって平文メッセージに特定の「マーク」をつけ,復号処理に際して「マーク」が復元されなかった場合には,不正な暗号文として復号結果を破棄する方法がある.これにより,復号の実行者は正規の暗号文とハッシュ値とを区別することができるので,暗号文に見せかけてハッシュ値を送付する攻撃を回避することが可能となる.
復号されたデータや署名データから,パディングしたデータを取り除く処理が必要になるが,この処理を曖昧性がなく一意に行なえることが必要である.
このようなパディング処理の方法として,幾つかパディングのフォーマットが規定されている.
暗号ライブラリを利用する場合,一般的にはこのパディング方式をパラメータとして指定することになる(あるいは,パディング方式を含んだアルゴリズムを指定する).
以下に,主なパディング方法を示す.
- PKCS#1v1.5
PKCS#1v1.5 では,RSA公開鍵暗号に適用可能なパディングアルゴリズムを規定している. PKCS#1v1.5
によるパディングアルゴリズムは,3バイトの固定バイト(マーク)と8バイト以上の乱数バイトを平文メッセージに追加するものである.
- OAEP
PKCS#1v1.5 のような単純なパディングアルゴリズムでは,選択暗号文攻撃を許す危険性があることが指摘され,パディングアルゴリズムに選択暗号文攻撃に対する耐性が求められるようになった.PKCS#1v2.0
で規定されている OAEP は,暗号文の乱数性と暗号文の検査の機能を与えた上で,PKCS#1v1.5 で規定されていたパディングアルゴリズムの脆弱性を修正し,選択暗号文攻撃に対して証明可能な安全性を提供する.
公開鍵暗号は,その利用目的からは次の3つに分類される.
- 署名
署名機能とは,電子情報の正当性を確認する機能である(ディジタル署名と呼ばれる).
ディジタル署名機能を用いて認証機能が実現できる.
- 暗号(守秘)
送信者と受信者の間で,秘密裏に任意の情報を共有する機能が守秘機能である. すなわち,メッセージを暗号化する機能である.
公開鍵暗号では,暗号鍵など短いデータの暗号化に利用する.
- 鍵共有
共通鍵暗号の鍵共有のためのアルゴリズムを実現する.
これらの機能を定式化して示す (具体的なアルゴリズムは,公開鍵暗号アルゴリズムを参照).
署名
- メッセージ復元署名方式
公開関数 $ψ_P$ と秘密関数 $ψ_S$ の組に対し,
$ψ_P(ψ_S(m)) = m$
が成立つことに基づく方式である.
署名の生成と復元は次のようになる.
- 署名生成: $s = ψ_S(m)$
秘密関数でメッセ-ジ $m$ から署名 $s$ を生成する.
- メッセージ復元: $m = ψ_P(s)$
公開関数で署名 $s$ からメッセージ $m$ を生成する.
- 確率的メッセージ復元署名方式
公開関数 $ψ_P$ と秘密関数 $ψ_S$ の組に対し,
$ψ_P(ψ_S(r, m)) = m$
が成立つことに基づく方式である.ここで,$r$ は乱数である.
署名の生成と復元は次のようになる.
- 署名生成:$s = ψ_S(r, m)$
乱数 $r$ を生成し,秘密関数でメッセージ $m$ から署名 $s$ を生成する.
- メッセージ復元:$m = ψ_P(s)$
公開関数で署名 $s$ からメッセージ $m$ を生成する.
- 署名方式
公開関数 $ψ_P$ と秘密関数 $ψ_S$ の組に対し,
$ψ_P(m, ψ_S(m)) = 1$
が成立つことに基づく方式である.
署名の生成と検証は次のようになる.
- 署名生成:$s = ψ_S(m)$
秘密関数でメッセージ $m$ から署名 $s$ を生成する.
- 署名検証: $ψ_P(m, s) = 1\ ?$
公開関数でメッセージ $m$ と署名 $s$ から署名の正当性の検証を行う.
- 確率的署名方式
公開関数
$ψ_P$ と秘密関数 $ψ_S$ の組に対し,
$ψ_P(m, ψ_S(r, m)) = 1$
が成立つことに基づく方式である.
署名の生成と検証は次のようになる.
- 署名生成:$s = ψ_S(r, m)$
乱数 $r$ を生成し,秘密関数でメッセージ $m$ と $r$ から署名 $s$ を生成する.
- 署名検証:$ψ_P(m, s) = 1\ ?$
公開関数でメッセージ $m$ と署名 $s$ から署名の正当性の検証を行う.
暗号(守秘)
- 暗号方式
公開関数 $ψ_P$ と秘密関数 $ψ_S$ の組に対し,
$ψ_S(ψ_P(m)) = m$
が成立つことに基づく方式である.
暗号化と復号は次のようになる.
- 暗号化: $c = ψ_P(m)$
公開関数を用いて,平文 $m$ から暗号文 $c$ を生成する.
- 復号 : $m = ψ_S(c)$
秘密関数を用いて,暗号文 $c$ から元の平文 $m$ を生成する.
- 確率的暗号方式
公開関数 $ψ_P$ と秘密関数 $ψ_S$ の組に対し,
$ψ_S(ψ_P(r, m)) = m$
が成立つことに基づく方式である.ここで,$r$ は乱数である.
暗号化と復号は次のようになる.
- 暗号化:$c = ψ_P(r, m)$
乱数 $r$ を生成し,公開関数により平文 $m$ を暗号化し暗号文 $c$ を生成する.
- 復号 :$m = ψ_S(c)$
秘密関数を用いて,暗号文 $c$ から元の平文 $m$ を生成する.
鍵共有
公開関数 $ψ_P$ と秘密関数 $ψ_S$ の組および一方向性関数 $φ$ に対し,
$ψ_P(r) = ψ_S(φ(r))$
が成立つことに基づく方式である.
鍵共有の手順は次のようになる.
- 公開鍵処理
- 乱数 $r$ を生成
- 中間鍵 $c = φ(r)$ を生成
- 中間鍵 $c$ を鍵共有相手に送信
- 共有鍵 $k = ψ_P(r)$ を生成
- 秘密鍵処理
- 中間鍵 $c$ を取得
- 共有鍵 $k = ψ_S(c)$ を生成
上記の公開鍵処理と秘密鍵処理をそれぞれ鍵共有を行う者同士で実行することにより,同一の鍵 $k$ が得られる.
- NESSIE
欧州の暗号評価危難であるNESSIEは暗号アルゴリズムを評価し,推奨暗号として公表している(
NESSIE Project Announces Final Selection of Crypto Algorithm
, February 27, 2003).
公開鍵暗号とディジタル署名に対する推奨アルゴリズムは次のものである.
- 公開鍵暗号
- ACE Encrypt
IBM Zurich Research Laboratory, Switzerland
- PSEC-KEM
Nippon Telegraph and Telephone Corp., Japan
- RSA-KEM
Draft of ISO/IEC 18033-2
- 署名アルゴリズム
- ECDSA
Certicom Corp., USA and Certicom Corp., Canada
- RSA-PSS
RSA Laboratories, USA
- SFLASH
Schlumberger, France
- 政府推奨暗号
2013年3月1日に総務省・経済産業省から共通鍵暗号に対して以下の電子政府推奨暗号リスト(CRYPTREC 暗号リスト) が提示されている.
- 電子政府推奨暗号リスト
安全性及び実装性能が確認され,市場における利用実績が十分であるか,今後の普及が見込まれ当該技術の利用を推奨するもの
- 署名
- DSA
- ECDSA
- RSA-PSS
- RSASSA-PKCS1-v1_5
- 守秘
- 鍵共有
- 推奨候補暗号リスト
安全性及び実装性能が確認され,今後,電子政府推奨暗号リストに掲載される可能性のあるもの