暗号鍵の生成
共通鍵暗号も公開鍵暗号もそれを利用するには鍵が必要である.共通鍵暗号の場合は,一般的には鍵は指定された長さの任意の乱数でよいが,公開鍵暗号の場合はそのアルゴリズムに応じて素数であることなどの条件が付く.
共通鍵暗号
鍵長の選択
暗号解読アルゴリズムの動向や暗号攻撃に利用できる計算機の処理能力により異なるが,現状の一般的な利用形態では次の鍵長が推奨されている.
弱い鍵
鍵を使った暗号アルゴリズムでは,ある特定の鍵を使うとその暗号強度が他の鍵より弱くなることがある.これを弱い鍵と呼ぶ.弱い鍵が存在するか否かは,各暗号アルゴリズムに固有の問題である.
DESでは,4 つの弱い鍵 (weak key) と 12 のやや弱い鍵 (semiweak key) が知られている.同じ鍵で平文を 2 回暗号化したとき出力が平文に戻る鍵を弱い鍵,鍵を反転したもので暗号化したとき暗号文が平文に戻る鍵がやや弱い鍵である.
すなわち,弱い鍵 K は,暗号化(E)と復号(D)に対して次の関係になる.
EK(EK(P)) = P,または EK = DK
やや弱い鍵は,鍵 K1 を使った暗号化が反転した鍵 K2 を使った復号と等価になる.すなわち,以下の関係がある.
EK2(EK1(P)) = P, または EK1 = DK2
DES の弱い鍵は以下である.
Weak Keys
0101 0101 0101 0101
1F1F 1F1F E0E0 E0E0
E0E0 E0E0 1F1F 1F1F
FEFE FEFE FEFE FEFE
DES Semi-Weak Keys
01FE 01FE 01FE 01FE
1FE0 1FE0 0EF1 0EF1
01E0 01E0 01F1 01F1
1FFE 1FFE 0EFE 0EFE
011F 011F 010E 010E
E0FE E0FE F1FE F1FE
FE01 FE01 FE01 FE01
E01F E01F F10E F10E
E001 E001 F101 F101
FE1F FE1F FE0E FE0E
1F01 1F01 0E01 0E01
FEE0 FEE0 FEF1 FEF1
なお,ランダムに鍵を選んでも,弱い鍵ややや弱い鍵を選ぶ確率は極めて低いといえる(16/256 の確率).
パスワード生成
米国防総省(The United States Department of Defense : DoD)は,パスワードの生成を次のように推奨している. DES暗号をOFBモードで次のように用いるものである.
- 初期ベクトルの生成
初期ベクトルを,システムクロック,システムID,ユーザID,日付けと時刻などから生成する.
- 鍵の生成
システム割り込みレジスタ,システム状態レジスタ,システムカウンタから鍵を生成する.
- 平文
システム管理者によって入力された8文字のような外部からランダムに生成された64ビットを平文とする.
パスワードは,64ビットの OFBモードで生成された 64ビットの DES暗号化テキストから生成する.これらの 64ビットから必要とされるビットを取り出し,人が覚える場合は,さらに発音し易い語や句,または覚えやすい他の形式に拡張してパスワードとする.
X9.17鍵生成
ANSI(American National Standards Institute)は共通鍵暗号用の鍵の系列を生成する方法を次のように規定している.
s0 : 64ビットの初期乱数種
gn : 生成される 64ビット鍵系列
k : この鍵系列を生成するためのランダムな予約鍵
t : できるだけ精度の高い鍵が生成された時刻 (64ビットまで)
DES(K, Q) : 鍵 K によるデータ Q の DES暗号化
gn = DES (k, DES (k, t) xor sn)
sn+1 = DES (k, DES (k, t) xor gn)
公開鍵暗号
鍵長の選択
- 公開鍵暗号の安全性
現状(2010年代前半)の公開鍵暗号の安全性の目安は,次のように考えられている.
- 素因数分解問題
合成数 n の素因数分解問題に関しては,n = pq については |p| = |q| かつ |n| ≧ 1024 で,n = p2q については |p| = |q| かつ |n| ≧ 1024 でそれぞれ安全と考えられる.
- 離散対数問題
素体 Fp の部分群(位数 q)の離散対数問題に関しては,|p| ≧ 1024 かつ |q| ≧ 160 で安全と考えられる.
- 楕円曲線上の離散対数問題
楕円曲線上の離散対数問題に関しては,例外的な楕円曲線を除けばベースポイントの位数が 160 ビット以上の素因子をもてば安全と考えられる.
- 公開鍵暗号の鍵長
暗号解読アルゴリズムの動向や暗号攻撃に利用できる計算機の処理能力により異なるが,現状の一般的な利用形態では次の鍵長が推奨されている.
- 素因数分解問題に基づく暗号
1024ビット以上 (安全性を重視する場合,2048ビット以上)
- 離散対数問題に基づく暗号
1024ビット以上 (安全性を重視する場合,2048ビット以上)
- 楕円離散対数問題に基づく暗号
160ビット程度以上 (安全性を重視する場合,200ビット以上)
暗号パラメータ
暗号機能を利用する場合,暗号アルゴリズムによっては動作内容を規定する特定のパラメータを指定する必要がある.
- 離散対数型暗号
離散対数型暗号では,素数 p と位数が p の元 g (原始元)がシステムパラメータである.
- 楕円曲線暗号
楕円曲線暗号の場合,利用する楕円曲線を指定するパラメータが必要である. 一般的には,楕円曲線を表すパラメータは以下のものからなる.
- 有限体 GF(qm) を定義する q,m
- 次数 m の既約多項式
- 楕円曲線の係数 a,b
- ベースポイント P
- P の位数
これらの楕円曲線を指定するパラメータは,楕円曲線上の演算を実行するベースとなる代数体により異なるが,これらの推奨パラメータが ANSI や NIST 等で提示されており,代数体やビット数を含む名称で識別できるようになっている.
- 素体 GF(p)
NIST-P192,X9.62, P-192V2など
- 標数2の体 GF(2m)
NIST-K163,X9.62, C2-PNB163V1など
RSA鍵
- 鍵の生成
RSA暗号では,次のように鍵を生成する.
- 任意の異なる2つの大きな素数 p と q を選びその積 n を計算する.
- p - 1 と q - 1 の最小公倍数 L を計算し, L と互いに素で L より小さな任意の整数 e を選ぶ.
- ed ≡ 1 (mod L) を満たす d を求める.
ここで,
n, e が公開鍵であり,p, q, d が秘密鍵になる.
RSA暗号の安全性は,この公開鍵 n の素因数分解の困難性にある.多くの素因数分解を実行するアルゴリズムが知られており,p と q を注意深く選択することにより現在知られている手法による素因数分解を難しくする必要がある.
X509には,RSA暗号鍵が持つべき条件として鍵がランダムな大きな素数であることの他に次のような条件が推奨されている.
- |p - q| が大きくなければならない.
- (p + 1) が大きな素因数を持たねばならない.
- (q + 1) が大きな素因数を持たねばならない.
- (p - 1) が大きな素因数 r を持たねばならない.
- (q - 1) が大きな素因数 s を持たねばならない.
- (r - 1) が大きな素因数を持たねばならない.
- (s - 1) が大きな素因数を持たねばならない.
ただし,上記の条件がすべての素因数分解法に対して有効であるというわけではない.すべての素因数分解法を考慮した素数を生成するのは困難であるため,単にランダムに大きな素数を選ぶことが,現実的な方法とも言える.
- 公開鍵 e
公開鍵 e は,すべての環境において共通にすることができる(このとき,他の公開鍵である法 n は共通にはできない).これにより,実際に配布する公開鍵の長さを減らすことができる.
公開鍵 e は大きくあるべきであるが,処理時間や使用メモリに関して効率的にその指数計算ができるべきである.固定的な e を用いるときには,次のフェルマー数 F4 の利用が効果的である.
F4 = 224 + 1 = 65537
この e 値は,17回の乗算で指数の計算ができ,平均的に 30倍復号より高速になる.