DSA 署 名 評 価 報 告 書

２００１年度株式会社 日立製作所

DSA 署名評価報告書

目次
1

2

3

4

はじめに

3

ディジタル署名3

2.1 デ ィジタル署名の概要 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :2.2 デ ィジタル署名の安全性 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :3
4

ElGamal 署名, DSA 署名の概要

53.1 ElGamal 署名 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :3.2 DSA 署名 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :5
6

DSA 署名の安全性

7

4.1
4.2
4.3
4.4
4.5
5

適応的選択文書攻撃に対する安全性 : : : : : : : : : : : : : : : : : : : : : : : : : ::::::::::::::::::::::::::::::::::::::::::::::::::::::::
乗法群上の離散対数問題について : : : : : : : : : : : : : : : : : : : : : : : : : : :その他の注意事項 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :パラメータ選択に関する安全性

乱数 k (random nonce) について

結論

7
9
9
11
13
13

2

はじめに

1

DSA 署名 (Digital Signature Algorithm) は 1991 年に NIST(National Institute for Standards
and Technology) によって提案され , 1994 年には米国連邦政府のディジタル署名標準となっている方式である ([25]). また, ISO/IEC 14888-3 にも規定されている. DSA 署名では , 署名サイズが大きいという ElGamal 署名の欠点を Schnorr の手法を用いて改善している. 本報告では , DSA 署名のプ リミティブとスキームについて, 安全性証明理論, 離散対数問題, 乱数 (random nonce) などに関し , 安全性の評価を行う.

ディジタル署名2

ここではディジタル署名に関する一般的な解説をする. より詳細は [21], [13] などを参照.

2.1

ディジタル署名の概要

ディジタル署名とは , 文書とその作成者を一意に結びつける署名機能をディジタルの世界で実現する技術のことである. 通常, 署名者は自身固有の (秘密の) データと文書データを用いて第 3 のデータを作成しそれを文書データに対するディジタル署名とする. 一般に , 署名者は自身固有のデー
タ (署名生成鍵, 秘密鍵) のほかに署名検証用データ (署名検証鍵, 公開鍵) を公開する. 署名された文書の検証 (検証項目は下に述べる) は検証用データを用いて誰でも行うことができるようになっている.
デ ィジタル署名の機能には次のものがある.

 署名と署名生成者を一意に特定することができる (署名者認証機能).
 署名対象文書が署名者以外の者に改ざんされた場合, 署名検証機能により改ざんを検知する
ことができる (文書認証機能).

 署名者は署名を生成した事実を後で否定することができない (否認防止機能).
公開鍵暗号方式が "可逆性"を持てば上記機能を実現できる. すなわちメッセージを公開鍵暗号方式において復号化, 暗号化の順に変換して元のメッセージが復元するような公開鍵暗号方式ならばそのままデ ィジタル署名へ転換できる (このような方式としては RSA 暗号, 署名がある). しかし ,このような公開鍵暗号方式は知られているものが少なく, 現在のディジタル署名は署名方式専用として設計されたものが大半を占める.
署名の形態についてもいくつか種類があり, まず , 署名対象データと署名が別々になっているもの(署名添付型) と , 署名データからデータを復元できるもの ( メッセージ回復型) に大別される. さらにそれぞれの型において, 同一の文書に対する署名が常に同一である方式 (確定型) と , 同一の文書に対する署名が異なることがある方式 (確率型) がある. DSA 署名方式は確率的署名添付型である.
デ ィジタル署名の安全性について , 現在では安全性の証明が可能であるものが望まれている. こ
こで安全性の証明とは , ディジタル署名方式に対する攻撃 (攻撃法, 安全性のレベルについては次章で簡単に述べる) は , 計算量的に困難とされる数学 (数論) 問題と同等以上に困難であることを証明することをいう.

3

現在, デ ィジタル署名や, 公開鍵暗号などの安全性の根拠になる数論問題としては主に (1) 素因
数分解問題, (2) 乗法群 (有限) 上の離散対数問題, (3) 有限体上で定義された楕円曲線上の離散対数問題 などがある. (1),(2) については様々な解法が研究されてきており, また計算機能力の向上も伴い, 安全性を確保するために数値サイズ (鍵サイズまたは modulus サイズ ) を大きく採らなければならない状況になっている. DSA 署名方式は安全性の根拠を (2) 乗法群上の離散対数問題においている. その安全性証明については 4 章で検証する.

2.2

ディジタル署名の安全性

ここでは , デ ィジタル署名の安全性の分類について簡単に復習する. デ ィジタル署名の安全性評
価は , 2 つの観点で行われる. すなわち偽造のレベルと攻撃法である.
偽造レベルは次のように分類されている.

 一般的偽造不可 (universally unforgeable) 署名の偽造ができない文書が存在する.
 選択的偽造不可 (selectively unforgeable) ある決められた文書以外に対しては署名の偽造ができない.

 存在的偽造不可 (existentially unforgeable) どのような文書に対しても署名の偽造ができない.
下に行くほど 安全性が高い. 攻撃法については次のように分類されている.

 受動攻撃 (passive attack) 公開データ (署名検証鍵) のみを用いて署名の偽造を行う攻撃.
 一般選択文書攻撃 (generic chosen-message attack) 攻撃者が事前に選んだ文書に対して, 正
当な署名者に署名させた後, その情報を用いて別の文書に対する署名を偽造する攻撃.

 適応的選択文書攻撃 (adaptive chosen-message attack) 攻撃者が適応的に選んだ文書に対して正当な署名者に署名させた後, 最終的に得られた情報を用いて別の文書に対する署名を偽造する攻撃.

下に行くほど 強力な攻撃になっている. 一般選択文書攻撃では , 正当な署名者に署名させる文書
はあらかじめ攻撃者が選んでおき, (一括して) 署名させたものを攻撃の材料にするのに対し , 適応的選択文書攻撃では , 署名させた文書をもとに検討し , それを踏まえて新に選択した別の文書に署名をさせることが可能な状況下で行う攻撃である.
デ ィジタル署名の安全性はこれら偽造レベルと攻撃法の組み合わせで評価される. 従って, 適応的選択文書攻撃のもとで存在的偽造不可であるような方式がもっとも安全で望ましいことになる.
本報告では , このような性質を単に "安全"ということもある.
昨今のディジタル署名では , "安全"性を証明できるような方式が要求されている. 無論, 無条件
で安全性証明可能である方式が望ましいが , 現在そのような方式は知られていない. いまのところ
安全性証明可能といえば , , 簡単にいうと, 古くから研究されてきて (計算量的に ) 困難であることが信じられている数学問題 (素因数分解問題, 離散対数問題など ) と比べ, そのディジタル署名方式をある攻撃法のもとで偽造することの困難さが同等以上であることを理論的に説明できることをいう. 対偶的に述べるならば , そのデ ィジタル署名方式の偽造が効率的に (無視できない確率以上で )できるアルゴ リズムが存在するならば , その数学問題を効率的に計算できるアルゴ リズムを構築できるということである.

4

ElGamal 署名, DSA 署名の概要

3

DSA 署名は本質的に ElGamal 署名をもとに考案された方式である. 従ってここでは , DSA 署名
のみならず , ElGamal 署名についてもそのアルゴ リズム, 特徴などの概要を述べることにする. 詳
しい仕様などは [25], [21] などを参照されたい.
自然数 n に対し , 整数 a の属す法 n の剰余類を a mod n とかき, 法 n の剰余全体のなす環, ま
たは加法のみに注目した加法群を Z=nZ とあらわす. 乗法群とは可逆な剰余類 ( a mod n が可逆とは , ある b mod n が存在して, ab = 1 mod n となることをいう) 全体のなす (乗法に関する) 群
を (Z=nZ) とかく.
3.1

ElGamal 署名

ElGamal 署名は , T. ElGamal によって 1980 年代初頭に考案された方式 ([8]) で , 乗法群 (有限素体の乗法群) における離散対数問題 (4.4 節参照) の困難性を安全性の根拠においた初めての方式である.
本報告では, 以下に紹介するアルゴ リズムを ElGamal 署名とする ([21]). (いくつかのバリエー
ションのうち一般的と思われる形である.)【 鍵生成 】



素数 p と , p を法とした剰余環の乗法群 (Z=pZ) の原始根値としてもよい). p

1 を法とした剰余群 Z=(p名生成, 検証鍵を次のようにする.
[署名生成鍵] x,[署名検証鍵] (y; p; )【 署名生成 】
文書 M に対し , 乱数 k

をとる (これらをシステム固定の

1)Z の元 x を選び , y =xmod p を計算し , 署

1)Z) を生成し ,2 (Z=(pr = (mod p)
t = (h(M ) xr) =k mod (p 1)を計算し , (r; t) を M に対する署名とする. ここで h はハッシュ関数とする.
k【 署名検証 】
次の等式が成立すれば "真", しなければ "偽":h(M )= y r rt mod p:

これらのアルゴ リズムからわかるように , ElGamal 署名には, 署名長が法長の 2 倍になるという短所がある. (すなわち p が 1024-bit ならば署名長は 2048-bit.)
また, (p やが ) 特殊な場合には容易に偽造が行われるということも知られており ([4]), 使用には注意を要する. (4.2 節参照)
さらに ElGamal 署名において, ハッシュ関数の使用は必須である (ElGamal が最初に提案した方式はハッシュを用いないものであった). 実際, ハッシュ関数を用いなければ偽造可能 (一般的偽
造"可能") であることが次のようにして簡単にわかる.

= y r mod p が成り立つよう r,t,M を決めてやればよい. r = yh を用いない場合, 式と置けば , 上記式より r + tb = 0 mod (p 1), M = ta mod (p 1) がなりたてば十分であること
M

r

t

b

5

a

がわかる. よって, まず , a, b を任意にとり, r = y bを計算し , t = r=b mod (p 1) (この際,
b 2 (Z=(p 1)Z) である必要がある), M = ta mod (p 1) と置けば , (r; t) は M に対する署名aとなっている.

ElGamal 署名において , ハッシュ関数 h(M ) を若干変更して h(r; M ) とすると, h が理想的ランダム関数ならば , 離散対数問題の困難性を前提に適応的選択文書攻撃に対して存在的偽造不可であることが証明される ([33], 4 節).
3.2

DSA 署名この ElGamal 署名における, 署名長の短所を, Schnorr の手法 ([38]) により, ある程度改善したのが DSA 署名である. Schnorr の手法は , 用いる Z=pZ の元の乗法的位数を公開してしまい, その位数を法とした元で署名を作成する. 離散対数問題の困難さはその元の位数に依存して決まるので,

p 1 が大きな素因子を含み, それを位数に持つ元を用いることで安全性を落とすことなく, 署名長を短くすることができるという仕組みである.
以下にそのアルゴ リズムを紹介する.
【 鍵生成 】

1 の素因子 q , および (Z=pZ) の位数 q の元 g を固定する. q を法とした剰余群
Z=qZ の元 x を選び , y = gx mod p を計算し , 署名生成, 検証鍵を次のようにする.
[署名生成鍵] x,[署名検証鍵] (y; g; p; q )素数 p と , p【 署名生成 】
文書 M に対し , 乱数 kk

2 (Z=qZ) を生成し ,r = g mod p mod qt = (h(M ) + xr) =k mod qを計算し , (r; t) を M に対する署名とする. ここで h はハッシュ関数1 とする.
【 署名検証 】
次の等式が成立すれば "真", しなければ "偽":

r= g ( ) yh M =tr=t



mod p mod q:

r, t ともに Z=qZ の元であるから, 署名長は q の長さの 2 倍である. 例えば p が 1024-bit で, q が256-bit であるならば , DSA 署名による署名長は 512-bit となり, 署名長が 2048-bit である ElGamal
署名に比べ, 大きく改善されているといえる.
DSA 署名においても, ElGamal 署名と同様, ハッシュ関数は必須である.
すなわち, ハッシュ関数を用いずに h(M ) の部分を単に M に置き換えた方式を考えると , 次のようにして署名の偽造が (自由に ) できる.

1 ハッシュ関数 h について , Digital Signature Standard (DSS [25]) では , SHA-1(Secure Hash Algorithm [24]) を要求している.

6まず , a, b を任意にとり, r =

g y mod p mod q, t = r=b mod q, M = ta mod q とおけば
ab(r; t) は M に対する正しい署名となっている. 実際,


g

M=t

y

r=t



mod p mod p =



=

g y (
a

r= r=b)

mod p mod p
g y mod p mod p
a

b

= r
が成り立ち, 署名検証に通ってしまう.
ハッシュ関数について , ElGamal 署名同様, DSA 署名においても, ハッシュ関数 h(M ) を若干変更して h(r; M ) とすると , h が理想的ランダム関数ならば , 離散対数問題の困難性を前提に適応的選択文書攻撃に対して存在的偽造不可であることが証明される ([33], 4 節). また, "mod q " を理想的ハッシュ関数に置き換えた変更版についても安全性証明可能であることがわかっている. これらについては次節で考察する.

DSA 署名の安全性

4

DSA 署名は ElGamal 署名をもとにしているため, DSA 署名の安全性考察の上で ElGamal 署名の安全性に注目することは重要である. この節では , 最強の攻撃法である, 適応的選択文書攻撃に対するスキームの安全性, 法となる素数 p についての考察 (DSA 特有の弱点, 一般的な離散対数問
題など ) など , いくつかの観点で安全性の考察を行う.

4.1

適応的選択文書攻撃に対する安全性

ここでは , ElGamal 署名, DSA 署名の, 適応的選択文書攻撃に対する安全性について考える.
まず , ElGamal 署名であるが , 最初に提案したハッシュ関数を用いない ("mod q "をハッシュ関数とみてもよい) 形では , 容易に偽造可能であることはすでに述べた.

Poincheval, Stern らは ElGamal 署名を若干変更することにより"安全"であることを証明した([32]).
変更点は次のとおり:【 鍵生成 】 変更なし .

【 署名生成 】 h(M ) を h(M; r) に置き換え , M に対する署名を (r; h(M; r); t) とする.
【 署名検証 】 h(M ) を h(M; r) に置き換え , あとは同じ .
この変更のもとで次のことがわかる ([32] Theorem 9.).
Theorem.

(変更 ElGamal 署名の安全性) ランダ ムオラクルモデル上で , 変更 ElGamal 署名に対する適応的選択文書攻撃を考える. このとき, 無視できない確率で存在的偽造が成功するならば , 離散対数問題を多項式時間内で解くことができる.

"ランダ ムオラクルモデル上"とは , 簡単にいえば , ハッシュ関数を "ランダムオラクル "に置き換えたものである. これは "query"(入力) に対して乱数を返してくれるものであり (同じ query に対しては同じ乱数を返す), 出力から入力の情報は全くわからない, 入力から出力が全く予想できない,
衝突 (collision) を見つけることは出来ない, など , 直感的には , 欠点のないハッシュ関数と考えてよい ([3]).
7

上記 Theorem は , このような理想的な仮定のもとで , ElGamal 署名の"安全"性を証明したものである. 注意することは , 変更 ElGamal 署名に対して証明をつけることができたことである.

r をハッシュ(ランダムオラクル) への入力からはずした, 元の方式では証明できていない. (これが直ちに元の方式が偽造可能であることにはつながらない) これは Theorem の証明中で , 偽造を行うアルゴ リズムの存在を仮定し , それを用いて離散対数問題を解くアルゴ リズムを構成する際に rが入力に必要であるというこであり, 元の方式ではこの論法を使うことができない. これが証明を付けることのできない一つの理由と考えられる.
次に DSA 署名であるが , これも同様に , 変更を加えた DSA 署名に対し , "安全"性の証明をつけることができる ([33]).
変更点は次のとおり:

F を署名長を短縮するための関数とし固定する ("mod q" でもよい.)【 鍵生成 】 変更なし .
【 署名生成 】

M に対し , 乱数 k 2 (Z=qZ) を生成し ,
r = F g mod p
t = (h(M; r) + xr) =k mod qを計算し , (r; t) を M に対する署名とする.
k【 署名検証 】 次を検証する.


r=F g (

h M;r )=t

y

r=t



mod p :

この変更のもとで次のことがわかる ([33] Theorem 6.).

(変更 DSA 署名の安全性) ランダムオラクルモデル上で , 変更 DSA 署名に対する適応的選択文書攻撃を考える. このとき, 無視できない確率で存在的偽造が成功するならば , 離散対数問題を多項式時間内で解くことができる.

Theorem.

すなわち, 変更 DSA 署名に対しても, ある理想的な仮定のもとで離散対数問題の困難性と等価な存在的偽造困難性を持つことが示される.

Brickell, Poincheval, Vaudenay らは , また別の形に変更した DSA 署名についても"安全"性が証明できることを主張している.
それは次のような変更である:H1 , H2 をハッシュ関数とする.
【 鍵生成 】 変更なし .
【 署名生成 】

M に対し , 乱数 k 2 (Z=qZ) を生成し ,r = H2 g mod p
t = (H1 (M ) + xr) =k mod qを計算し , (r; t) を M に対する署名とする.
k【 署名検証 】 次を検証する.

8r = H2 g 1 ( ) y
H

M =t

r=t



mod p :

この変更のもとで同様に次のことがわかる ([33] Theorem 6.).
Theorem.

(変更 DSA 署名 (2) の安全性) ランダ ムオラクルモデル上で , 変更 DSA 署名 (2) に対する適応的選択文書攻撃を考える. このとき, 無視できない確率で存在的偽造が成功するならば , 離散対数問題を多項式時間内で解くことができる.
以上のことから , ElGamal 署名, DSA 署名に関して, 若干の変更を施せば , ある理想的な仮定のもと (ランダムオラクルモデル上) で , 離散対数問題の困難性を前提に , "安全", すなわち適応的選択文書攻撃に対し , 存在的偽造不可であることが示される.
しかし , 無変更のままでは現状では"安全"性が証明されておらず , 使用には注意が必要と考える.

4.2

パラメータ選択に関する安全性

ここではスキーム特有の"弱い"パラメータについて述べる. ElGamal 署名, DSA 署名が安全性の根拠においている, 乗法群上の離散対数問題の困難性についての一般的考察は次節で行う.

ElGamal 署名のパラメータに関し , 次のことが知られている ([4]).

p = 1 mod 4 とし , (Z=pZ) の生成元 (原始根) は p 1 を割る.
 このとき (Z=pZ) は位数

が次を満たすとする:の部分群 S を持つが , S 上の離散対数問題はやさしい.

このとき, 与えられた文書 M に対する署名の偽造が容易にできる. 例えば ,= 2 など ,の値が小さい場合には上記条件が成り立つことに注意.
実際, p

1 = q である場合には , 次のようにして偽造できる.
 t = (p 3)=2, r = q とする.
 qz = yq mod p を満たす z を求める.
( q , y q は S の元なので , 仮定から離散対数問題を解いて z を得ることができる.)
 s = t(h(M ) qz ) mod (p 1) を計算する.
このとき, (r; s) は M に対する正当な署名となる.

4.3

乱数 k (random nonce) について

ElGamal 署名, DSA 署名では , 署名生成の度に新規に乱数 k (nonce) を生成し , 生成された署名は乱数に依存しているため同じ文書に対する署名でも署名の度に異なるという性質を持つ (確率型).
署名スキームの安全性証明などでは, この乱数はいわゆる"真"の乱数を用いることを想定している. しかし , 実際に方式を実装する場合には SHA-1 などのアルゴ リズムを用いてその出力を k として用いることが多く, "擬似"乱数でしかないといえる.
この節では, k の値に依存した攻撃法や, [25] で定められている k の生成法について検討する.

k の値と安全性についての次の結果を紹介する.
9([27]) DSA 署名において, q が p に比べそれほど小さくなく, ハッシュ関数 h の collisionの確率が大きくないとする (これらは現実的な仮定である). このとき, ある個数 (多項式サイズで抑えられる) の文書と nonces k であって, log1=2 q -最下位 bits がわかっている組があれば , これらを元に署名者の秘密鍵を多項式時間で求める確率的アルゴ リズムを構築できる.
このことは, 最上位 bits や, (確率が悪くなるが ) 中間 bits でも成り立つ.
Theorem.

すなわちこの結果は , nonce k のいくつかの bits がわかる場合には秘密鍵がわかってしまうことを主張している.

DSA 署名は , k としてあくまで乱数を使う方式であるから , "乱数でない" k を用いた場合の危険性についてはアルゴ リズムの欠陥ではないが , 先に述べたように , 現実問題として, 実装における kの生成法に注意が必要であることは間違いない.
以下に実装例として [25] に規定されている k の生成法を検討する.

[25] APPENDIX 3 ではまず関数 G を次のように規定している:
SHA-1 における Hi (i = 0; : : : ; 4) を "cyclic shift" する. すなわち

H0

H1 ; : : : ; H3

H4 ; H4

H0 :これを初期値とした SHA-1 を SHA-1' とするとき, G(x) =SHA-1'(x) と定める.

G を用いて k は, 初期値として選んだ seed KKEY (160512-bit) に対し ,k = G(KKEY) mod qで生成される.

この場合, G(KKEY) の乱数性は完全に SHA-1 のそれに依存している. mod q (q : 160-bit) する操作に関して, k > q かつ, ある KKEY0 = KKEY であって, G(KKEY0 ) = k
存在するならば , k

6q となるものがq という値の出現確率は 2 倍となってしまう. しかしながら結局のところ, その結果的な衝突確率は , SHA-1 の衝突確率の高々2 倍になるだけであり, ただちに問題があるとは考えにくく, やはり SHA-1 の性能が本質的である. 従って, SHA-1 の出力の部分 bit 列の予測が困難ならば , 上記の攻撃は適応できないと言える.
また, APPENDIX 3 にはブロック暗号 DES (Data Encryption Standard [23]) を用いた関数 Gの構成法も掲載されている. この場合は KKEY は 160-bit に限られる.

DES を用いた G の構成法は SHA-1 の場合に比べ複雑ではあるが , やはり, 本質的には DES の出
力の乱数性に依存することになる. (構成法の詳細は省略するが , SHA-1 で用いた初期値と , KKEYの値から DES の鍵 (64-bit) と入力 bit(64-bit) を作成, DES の出力の上, 下位 32-bit をシャッフル
する形で排他的論理和をとる. それを 5 つ作成し , その連結 (160-bit) を出力とする.)
すなわち, この場合も DES の出力の部分 bit 列の予測が困難ならば , 上記の攻撃は適応できないと考えられる.
以上をまとめると , SHA-1, DES の入力に対する出力の予想が困難 (「 2 つの入力の"関係"から,対応する出力の"関係"も予想できない」ということも含む) であるならば , 得られる nonce k は署名に使用するために十分な強度を持つと考えられる.

参考までに , 表 1 に SHA-1 の出力に関する実験データをまとめた. SHA-1 に連続したデータ (入力=1 1000000) を入力して, 160-bit の出力の各 bit における 1 の出現確率を測定した. いずれ10

の bit も 1 の出現確率が 1/2 に近い値になっていて , SHA-1 の出力の均等性を支持する結果である.

(また , 各出力における 1 の個数の平均は 80.012 であった.) 無論, これだけの実験で , SHA-1 の出
力の乱数性を保証できるわけではない.
表 1: SHA-1 の出力の各 bit における 1 の出現確率

bit number
1 8
9 16
17 2425 3233 4041 4849 5657 6465 7273 8081 8889 9697104105112113120121128129136
137144145152
153160

4.4

.5062
.4970
.4967
.5025
.4974
.5020
.4988
.5046
.4943
.4921
.4962
.4982
.4957
.4943
.4906
.4951
.5022
.5034
.5001
.5047

.4980
.4979
.4916
.5009
.5008
.5037
.4989
.5073
.5037
.5102
.4952
.5042
.4968
.5023
.5065
.5059
.5063
.5009
.4979
.5032

.5031
.5055
.4896
.5098
.4983
.5098
.5036
.5011
.5078
.4957
.4950
.4959
.4973
.4899
.4961
.5043
.5063
.4999
.5060
.4941

.4985
.5013
.5063
.5033
.4883
.4986
.4976
.4980
.4949
.5009
.5019
.4923
.4984
.4993
.4965
.5050
.5015
.4983
.4922
.5025

.5059
.4950
.4970
.4927
.4992
.4977
.4975
.4992
.4956
.4933
.5022
.4921
.4931
.4940
.4989
.5015
.4995
.5010
.4996
.5069

.5020
.5007
.5040
.4943
.5009
.4990
.5126
.4956
.4951
.4945
.4999
.5003
.5021
.5012
.5107
.4884
.5081
.5000
.5042
.5082

.4881
.4986
.5021
.4929
.5059
.4994
.5056
.5044
.5079
.4992
.5019
.4955
.5005
.5017
.4931
.5028
.5028
.5045
.5010
.5015

prob.
.5015
.4980
.5081
.4972
.5029
.4976
.5018
.5070
.5024
.5032
.4908
.4948
.5026
.5107
.5014
.5001
.5018
.5034
.5008
.4955

乗法群上の離散対数問題について

離散対数問題は一般的には次のような問題である.
有限群 G (演算は乗法的に書く) とその元 g , h に対し , h = g a となる自然数 a が存在するならばそれを求めよ.
このような a を logg h と書き, 底 g に対する h の離散対数と呼ぶ.
有限体の乗法群上の離散対数問題を解くアルゴ リズムは次の 2 種類に大別される.

(1) 底 g の生成する部分群 H = hg i の位数 (g の元としての位数) に依存して離散対数を求める

アルゴ リズム.

(2) 指数計算法 (index calculus method) と呼ばれる手法.
前者に類別されるものとしては , Pohlig-Hellman([31]), Pollard のアルゴ リズムなどが強力である. しかし , 実行時間は , H の位数の最大素因子サイズの準指数オーダとなる. 後者では , 有限体の11

乗法群の場合, Coppersmith, Coppersmith-Odlyzko-Schroeppel, Gordon([14]) のアルゴ リズムがある. これらも体のサイズの準指数オーダの実行時間となる.

(1) の攻撃に対しては , g の位数が大きな素数であればよい. また, (2) に対しても十分大きなサ
イズの有限体 (有限素体の場合には p) をとることで回避できる.

ElGamal 署名, DSA 署名に即して言えば , (1) に対しては , p 1 が大きな素因子 q を持つように
p をとり, (2) に対しては, 十分大きな p をとるということで攻撃から逃れることができる.
計算量の評価としては , まず , (1) に属すアルゴ リズムに対しては , p

1 の素因子が全て O(log p)程度の大きさである場合でなければ効率的に計算できない. 従って, これら (1) に属す攻撃を回避することは簡単である.
問題は (2) に属す攻撃である. Gordon のアルゴ リズムは計算量が一般的には

L [1=3; 2:08008]pと見積もられている. しかし下記の条件を満たす, "特殊"な p に対してはより計算量が低く,

L [2=5; 1:00475]pとなる. p が "特殊"とは , 次の条件2 を満たす多項式 f2 (Z=pZ)[x] が存在することをいう:

1. f の係数は小さい.
2. p1=k 程度の大きさの整数 x, y であって, y k f (x=y ) = 0 mod p を満たすものが存在する.
3. f を整数係数の多項式とみて, その (代数閉包内での) 根の一つを としたとき 環 Z[ ] は一
意分解整域 (Q ( ) の類数は 1).
ここで関数 Ln [a; b] はL [a; b] = exp (b + o(1))(log n) (log log n)1
a

n

a



で定義される関数で , 計算量評価に頻繁に用いられる.

比較のため, RSA 暗号, 署名で用いられている法 N = pq の素因数分解に要する計算量を考える. 素因数分解ではある程度大きな合成数になると , 数体ふるい法と呼ばれるアルゴ リズムが有効
で , その計算量はL [1=3; 1:901]
Nと見積もられている.

(Z=pZ) 上の離散対数問題と , N の素因数分解問題の両者の計算量を比較したのが表 2 である.
ただし , 簡単のため, 評価式中の定数部分 o(1) は無視 (すなわち = 0) した. また, 値は指数部分(すなわち log(L [a; b])) の値である.
以上により, 1024-bit RSA 暗号と同等以上の強度を持つためには "特殊"でない 1024-bit の p を選べばよい.
[25] では , p のサイズは 5121024-bit, q のサイズは 160-bit を推奨しているが , 上記評価を考慮
すると , p に関し , 1024-bit に近いサイズを採用することが望ましいと考える. q に関しては 160-bit
で十分であると考えられる.
2 これらの条件を鍵生成時にチェックすることは容易ではないが , これを満たす p に対する効率的攻撃が存在する以上は考慮すべきことである.

12

表 2: Complexity for Integer Facotirzation(IF) and Discrete Logarithm(DL)4.5

bit-length

512-bit768-bit1024-bit

IF of NDL on (Z=pZ) (general)
DL on (Z=pZ) (special)

43.80647.93230.43452.42757.36637.25659.45465.05442.939

その他の注意事項

ここでは前節までに述べられなかった, 安全性に関わる注意事項をいくつか列挙する (自明な注
意事項も含む).
1.([21]) ElGamal, DSA 署名双方において, 署名の度に乱数 k を替える必要がある. より正確には ,k を 2 つの異なる文書の署名生成に使用した場合, 秘密鍵 (署名生成鍵) が高い確率で求まってしまう.

例えば , ElGamal 署名の場合, k が同じということは , r の値も同じということになり, t1 =(h(M1 ) xr)=k , t2 = (h(M2 ) xr)=k の関係式から xr を消去すれば k = (h(M1 ) h(M2 ))=(t1 t2 )kri )=r によって秘密鍵 (署名生成鍵) を求めることができる. (求められないのは上記式中で逆元が存在しない場合のみ)同様にして DSA 署名の場合も秘密鍵が計算できてしまう.
となり, さらに x = (h(Mi )([21], [4]) ElGamal 署名において, r の値は 0 < r < p を満たさなければならない. そうでない署名を生成すると攻撃者は任意の文書に対して署名を偽造することが可能となってしまう.
DSA 署名に関しても同様に 0 < r < q , 0 < t < q であることが求められる. これらの条件を検証条件に入れる場合もある3 . (ただし , 通常, 剰余は 0 と (法 1) の間でとることが多いので , 本報
告のアルゴ リズムでは省略した.)

2.

5

結論
本報告では, DSA 署名に対して以下の観点から安全性の評価を行った.

(1) スキームの安全性: 適応的選択文書攻撃に対する安全性.
(2) プ リミティブの安全性: 離散対数問題(3) 乱数生成手法に関する考察.
(1) については , 方式を若干変更した DSA 署名について , 適応的選択文書攻撃に対し , ランダム
オラクルモデル上で , 離散対数問題の困難性を前提に , 存在的偽造不可であることを確認した. しかしながら , もともとの方式についてはそのような証明をつけることができていない. したがって,
現在要求されている, いわゆる安全性証明つき方式にこだわるならば , DSA 署名方式は現状では不利な立場にあると言わざ るを得ない. 可能ならば , "変更"版 DSA 署名の使用が望まれる.
(2) は例えば [25] などで推奨されるパラメータサイズのうち, 現在の計算機能力を考慮して 1024bit 程度の法 p を使用することが推奨される. 一般にデ ィジタル署名では , ある程度の期間, その効力を持続することが要求されるので , 将来までの安全性を考慮に入れるならばさらに大きい p を採
3 [25] では含まれている13

用することも検討すべきである. また, DSA 署名特有の弱点や, 一般的な離散対数問題への攻撃法に対抗するための p に対する条件があり, それらを満たすものを用いることが推奨される.

(3) については , 現在知られている攻撃法で非常に強力と思われるものを紹介した. しかしながら , 例えば [25] で述べられている random nonce k の生成法について, SHA-1 や DES の出力予測が困難ならば , この攻撃法に晒されることはないと考える.

14

参考文献
[1] M. Bellare, S. Goldwasser, and D. Micciancio, Pseudo-random, number generation
within cryptographic algorithms: The DSS case, Crypto '97, LNCS 1294, IACR, SpringerVerlag (1997).
[2] M. Bellare and S. Micali, How to sign given any trapdoor permutation, JACM 39, No.1
(1992), 214-233.
[3] M. Bellare and P. Rogaway, Random oracles are practical: a paradigm for designingeÆcient protocols, the 1st ACM Conference on Computer and Communications Security,
ACM Press (1993), 62-73.
[4] D. Bleichenbacher, Generating ElGamal signatures without knowing the secret key,
EUROCRYPT '96, LNCS 1070, Springer-Verlag (1996), 10-18.
[5] E. Brickell, D. Pointcheval, S. Vaudenay, and M. Yung, Design validations fordiscrete logarithm based signature schemes, PKC '2000, LNCS 1751, Springer-Verlag (2000),276-292.
[6] W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Info. Theory
IT-22 (1976), 644-654.
[7] C. Dwork and M. Naor, An eÆcient existentially unforgeable signature scheme and its
applications, Crypto '94, LNCS 839, Y. Desmedt ed., Springer-Verlag (1994).
[8] T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory, 31 (1985), 469-472.
[9] E. El Mahassni, P.Q. Nguyen, and I. E. Shparlinski, The insecurity of NybergRueppel and other DSA-like signature schemes with partially known nonce, Workshop on
Lattices and Cryptography, LNCS, Springer-Verlag, 2001(to appear).
[10] A. Fiat and A. Shamir, How to prove yourself: practical solutions to identi cation andsignature problems, Crypto '86, LNCS 263, A.Odlyzko ed., Springer-Verlag (1986).
[11] A. M. Frieze, J. Hastad, R. Kannan, J. C. Lagarias, and A. Shamir, Reconstructing
truncated integer variables satisfying linear congruences, SIAM J. Comput., 17 (1988), 262280, Special issue on cryptography.
[12] S. Goldwasser, S. Micali and R. Rivest, A digital signature scheme secure against
adaptive chosen-message attacks, SIAM Journal of Computing, 17(2) (1988), 281-308.
[13] S. Goldwasser and M. Bellare, Lecture Notes on Cryptography, http://wwwcse.ucsd.edu/users/mihir/papers/gb.html (1999).
[14] D. M. Gordon, Discrete Logarithms in GF(p) Using the number Field Sieve, SIAM J. on
Discrete Math.

15

[15] N. A. Howgrave-Graham and N. P. Smart, Lattice attacks on digital signature schemes,
Design, Codes and Cryptography, 2001(to appear).
[16] ISO/IEC 9796, Information Technology Security Techniques -Digital Signature Scheme Giving Message Recovery, International Organization for Standards (1991).
[17] H. Kuwakado and H. Tanaka, On the security of the ElGamal-type signature schemewith small parameters, IEICE Transactions on Fundamentals of Electronics, Commun., andComp. Sci., E82-A (1999), 93-97.
[18] A. Lenstra and H. Lenstra(eds.), The development of the number eld sieve, Lecture
Notes in Math. 1554, Springer-Verlag (1993).
[19] H. W. Lenstra, Jr., Integer programming with a xed number of variables, Math. Oper.
Res.,8(4) (1983), 538-548.
[20] H. W. Lenstra, Jr., and L. Lovasz, Factoring polynomials with rational coeÆcients,
Mathematische Ann., 261 (1982), 513-534.
[21] A. Menezes, P. Van Oorschot, and S. Vanstone, Handbook of Applied Cryptography,
CRC Press, 1997.
[22] M. Naor and M. Yung, Universal one-way hash functions and their cryptographic applications, the 21st Annual Symposium on Theory of Computing, ACM (1989).
[23] National Bureau of Standards (U.S.), Data Encryption Standard, Federal Information Processing Standards Publication 46, National Technical Information Services, Spring eld, VA(1977).
[24] National Institute of Standards and Technology(NIST), FIPS Publication 180 : Secure Hash
Standard, May 1993.
[25] National Institute of Standards and Technology(NIST), FIPS Publication 186 : Digital
Signature Standard, May 1994.
[26] P. Q. Nguyen, The dark side of the hidden number problem: Lattice attacks on DSA. In
K. -Y. Lam, I. E. Shparlinski, H. Wang, and C. Xing, editors, Workshop on Cryptography
and Computational Number Theory (CCNT'99), Singapore, Birkhauser (2001), 321-330.
[27] P. Q. Nguyen and I. E. Shparlinski, The insecurity of the Digital Signature Algorithmwith partially known nonces, To appear in J. Cryptology.
[28] P. Q. Nguyen and J. Stern, Lattice reduction in cryptology: An update, In Algorithmic
Number Theory - Proc. of ANTS-IV, LNCS 1838, Springer-Verlag (2000), 85-112.
[29] H. Niederreiter, Quasi-Monte Carlo Methods and Pseudo-random Numbers, Bull, Amer,
Math. Soc., 84 (1978), 957-1041.
[30] H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, CBMSNSF Regional Conference Series in Applied Mathematics, 63, SIAM, Philadelphia (1992).
16

[31] S. Pohlig and M. Hellman, An Improved Algorithm for Computing Logarithms over
GF(p) and Its Cryptographic Signi cance, IEEE Trans. Information Theory, 24 (1978),106-110.
[32] D. Pointcheval and J. Stern, Security proofs for signatures, Eurocrypt '96, LNCS 1070,
U. Maurer ed.,Springer-Verlag (1996).
[33] D. Pointcheval and S. Vaudenay, On Provable Security for Digital Signature Algorithms, Technical Report, Ecole Normale Superieure, LIENS (1996), 96-17.
[34] R. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signature andpublic key cryhptosystems, CACM 21(1978).
[35] M. Rabin, Digital signatures, in Foundations of secure computation, R. A. Millo et. al. eds,
Academic Press, 1978.
[36] M. Rabin, Digital signatures and public key functions as intractable as factorization, MIT
Laboratory for Computer Science Report TR-212, January 1979.
[37] J. Rompel, One-Way Functions are Necessary and SuÆcient for Secure Signatures, the22nd Annual Symposium on Theory of Computing, ACM (1990).
[38] C. P. Schnorr, EÆcient signature generation for smart cards, CRYPTO '89, LNCS 435,
Springer-Verlag (1990), 239-252.
[39] I. E. Shparlinski, On the uniformity of distribution of the ElGamal signature,2000(preprint).
[40] S. Vaudenay, Hidden collisions on DSS, Crypto '96, LNCS 1109, IACR, Springer-Verlag(1996), 83-88.

17