ESIGN 署名方式詳細評価報告書

2001 年 12 月 14 日

ESIGN 署名方式詳細評価報告書
2001.12.14
概要
本報告書は、CRYPTREC からの依頼に基づき、ESIGN 署名の安全性評価を行ったものである。本報告書の構成は次の通りである。第 2 章で ESIGN
署名提案者自身による自己評価の概要をまとめる。第 3 章で e 乗根近似問
題について、第 4 章で素因数分解問題について考察する。第 5 章で ESIGN署名の補助関数であるハッシュ関数について述べる。第 6 章で数多くある
ESIGN 署名のバージョンの違いについて整理する。最後に、第 7 章において ESIGN 署名の安全性評価を総括する。

1

1 はじめに
本報告書は、CRYPTREC からの依頼に基づき、ESIGN 署名の安全性評価を行ったものである。
CRYPTREC からの評価依頼書には、次の 5 つの安全性評価項目がリストされている。

 e 乗根近似問題
 電子署名および認証業務に関する法律に基づく特定認証業務の認定に係る指針案における推奨パラメータ: e  8 、jnj  1024 の安全性評価
 昨年度 CRYPTREC への応募における応募者による推奨パラメータ: e  8、jpj = jqj  320、jnj  960 の安全性評価
 昨年度 CRYPTREC におけるソフトウエア実装評価時の応募者による採用パラメータ: e =2 、jpj = jqj = 384 、jnj  1152 の安全性評価
 Vallee らの攻撃 [VGT88a] の拡張可能性について
10

本稿の以下の章では、これらの評価項目を以下の 3 つのカテゴ リーに分類して評価を行う。

 e 乗根近似仮定に関して
 素因数分解仮定に関して
 その他に関して

2 自己評価書の概要
ESIGN 署名提案者自身による自己評価 [NTT01b] の概要をまとめる。

2.1 設計方針
提案者により示されている設計方針の大きな柱は 2 つあり、それらは次の通りである。

1. 適切な仮定のもとで、安全性に関して高い信頼性を保持すること
2. 代表的署名方式である RSA 署名よりも、実装性能において優れていること

2.1.1 安全性に関して
ESIGN 署名には 、いくつかのバージョンが存在し 、IEEE P1361a[IEEE] に採録されたバージョンでは、ディジタル署名における最強の意味での安全性、すなわち、\ある仮定のもとで適応的選択文書攻撃に対して存在的偽造不可" であることの証明がついている。しかし 、今年度
CRYPTREC に投稿したバージョンは、IEEE バージョンとは異なる仕様で、現時点では前述のような安全性の証明はついていない。
安全性の証明がついていないことに関する提案者の主張は次の通りである。

2 今年度 CRYPTREC 投稿バージョンは 15 年以上の使用実績があり、現時点では最強の意
味での安全性に関する攻撃は発見されておらず、heuristic な設計での安全性の証明はない
が 、現在知られている攻撃法の観点では安全である

2.1.2 速度性能に関して提案者自身の実装では、Celeron 800MHz において、ESIGN 署名の法 n が 1152 ビット、安全性パラメータ e が e = 210 の時、鍵生成生成 610ms 、署名生成 1.04ms 、署名検証 0.70ms とのことである。RSA 署名や楕円曲線 DSA 署名と比べて、速度的に優秀と提案者は主張している。

3 e 乗根近似問題
定義

1 (AER 問題) G を ESIGN の鍵生成とする。e 乗根近似問題 (AER 問題) とは 、pk :=fn; eg Gen(1k ) と y R f0; 1gk; が与えられたとき、0jjy = [xe mod n]k となるような
x 2 (Z=nZ) n pZ を見つける問題である。
12 (AER)

仮定 どのような確率的多項式時間アルゴ リズム Adv に対しても、全ての定数 c 、
定義
十分大きな値 k に対して、

Pr[Adv(k; n; e; y) ! x] < 1=kcjjGが成立するとき、e 乗根近似問題は難しいという。ここで、0 y = [xe mod n]k であり、確率はと Adv の確率空間上で取られる。e 乗根近似問題が難しいという仮定は、e 乗根近似仮定 (AER仮定) と呼ばれる。

AER 問題は、e = 2 と e = 3 の場合に lattice basis reduction 法によって解かれている [BD85]。
e  4 の場合は、現時点では効率的解法は知られておらず、知られている唯一の解法においては、

法 n を素因数分解することが必要となる。

3.1 e > 230 について
CRYPTREC からの評価依頼項目の 1 つである、\ESIGN 署名が安全であるためには e > 230 であることが必要か?"に関して考察する。これは、2000 年度評価報告書 (の 1 つ)[Cr00] の中で記述されている事項に関連している。

3.1.1 2000 年度報告書の概要
2000 年度詳細評価書 [Cr00] の中で、Vallee らの攻撃の拡張可能性に関する指摘がなされている。その指摘の概要は次の通りである。

3

1. Brickel の方法は e  4 に適用できないことが分かっているが、Vallee らの方法を e  4 に適用できるかど うかは不明であり、Vallee らの方法を拡張できる可能性が残されている。
2. Vallee らの方法の理論的限界はわかっていないが、Vallee らの方法は LLL アルゴ リズムを使うため、LLL アルゴ リズムの限界を考えれば Vallee らの方法の適用限界を推定できる。
3. Vallee らの方法の時間計算量は O(e3 ) である。
4. Vallee らの方法の空間計算量は O(e2 ) である。
5. Vallee らの方法を並列実行できた場合、時間計算量は O(e2 ) になる可能性がある。
6. 時間計算量 O(2128 ) 程度の安全性を保証するためには、e > 264 程度にする必要がある。
7. O(260 ) 程度の記憶域を用意することは物理的に困難であると仮定すると、e > 230 程度で安全となる。

8. Vallee らの方法を拡張できるかどうかは知られていないが、もし拡張できたとしても、e > 230程度であれば 、e 乗根近似問題は解けないことになる。

3.1.2 2000 年度報告書に関する考察
前節の \e > 230 "に関して考察する。
まず初めに注意しなければならないことは、e > 230 という数値の算出の根拠には多くの仮定が置かれていることである。LLL アルゴ リズムの時間計算量として漸近評価式を用い、また、空間計算量としても漸近評価式を用いている。これらの漸近評価式から、e > 230 という speci c な数値がはじき出されている。つまり、オーダの比例係数は、実際に計算機実験をすれば数倍変わることもあり、それに伴って 230 という数値も変化する。
したがって、e > 230 という数値には正当な根拠はあまりないと言える。しかしこのことは、eのいくつかの推奨パラメータ (8 、210 など ) に対しても言えることである。
実際の実装による ESIGN 署名解読実験は、いくつかの例 [AA97, AA99] があるものの、素因数分解実験や、楕円離散対数計算実験ほどには多くの例がない。次章の素因数分解問題においても指摘するように 、LLL アルゴ リズムを実際に実装し 、オーダによる漸近評価だけでなく、計算機実験を行うことが有益であると思われる。日本においてはディジタル署名の法的お墨付きにESIGN 署名が使われる可能性があることから、実際の解読可能性を把握することは重要である。
素因数分解や楕円離散対数のように、解読コンテストを実施することも有効であろう。

4 素因数分解問題

素因数分解問題とは、与えられた整数 n からその素因数を求める問題であるが 、ESIGN 署名の場合、n = p2 q (n は ESIGN の法) 、p と q はビット長が同じ 素数、という設定に関する問題となる。素因数分解問題を解く 2 つの代表的アルゴ リズム、数体ふるい法 [LL93] と楕円曲線法[Le87, Mo87] に対する ESIGN 署名の素因数分解問題に関して考察する。
計算量評価には、次式のような漸近的計算量評価式がしばしば用いられる。

Lx[u; v] = ev

(logx)u (log log x)1;u(1)あるアルゴ リズムが Lx [0; v ] という実行時間であれば 、それは多項式時間であると言い、計算4量は 、アルゴ リズムへの入力の大きさに関するある多項式で抑えられる。あるアルゴ リズムがLx[1; v] という実行時間であれば 、それは指数時間であると言い、計算量はアルゴ リズムへの入力の大きさに関するある指数関数で抑えられる。0 < u < 1 の時、準指数時間と呼ばれる。
数体ふるい法の計算量は、素因数分解したい整数の大きさに関する準指数時間で、次の計算量をもつ。

Ln[1=3; 1:9292 + o(1)](2)一般化数体ふるい法によって実際に素因数分解された数の記録は 512 ビットである。
楕円曲線法の計算量は、素因数分解したい整数 n のもっとも小さい素因数を p とすれば 、
pLp[1=2; 1=2];(3)となる。楕円曲線法によって分解されたもっとも大きな素因数は、(643 1)42 + 1 という数の54 decimal digit の素数である。
また、Boneh らが大きい r に対する n = pr q の素因数分解問題を解くアルゴ リズムを示している [BDG99]。そこでは、LLL アルゴ リズムが利用されている。Boneh らのアルゴ リズムは、r が大きい場合 ( r = (log p)1=2 ) に有効であり、n = p2 q に対する素因数分解は、数体ふるい法や楕円曲線法よりも効率が悪い。
現時点では、ESIGN 署名の法 n = p2 q の大きさが 1024 ビット以上であれば 、数体ふるい法に対しても楕円曲線法に対しても安全、すなわち現実的時間、記憶域量で素因数分解することは不可能であると思われる。しかしながら、アルゴ リズムの計算量評価は前記の式のような漸近的評価であり、実際に素因数分解を実行した場合、どの程度の実時間、実記憶域量を要するかを見積もることは容易ではない。ESIGN 署名のような n = p2 q の形の合成数に対する素因数分解が、どの程度のビット長の時、数体ふるい法と楕円曲線法とど ちらが有効に働くかを、実際に素因数分解実験を行って確かめることも有益であると思われる。

jj

5 ハッシュ関数
ESIGN 署名は、他の多くのディジタル署名スキームと同様、スキームの補助関数としてハッシュ関数が必要である。ハッシュ関数の ESIGN 署名提案者による推奨は、SHA-1 である [NTT01a]。
最近 NIST において、SHA-1 に代わる新しいハッシュ関数の標準化が進められている。すなわ
ち、SHA-1 のハッシュ値は 160 ビットであるが、より大きいハッシュサイズのハッシュ関数が作られている。その関数は SHA-256 、SHA-384 、SHA-512 と呼ばれ 、それぞれハッシュサイズは256 ビット、384 ビット、512 ビットである。
コリジョンサーチによるハッシュ関数の攻撃の計算量は、ハッシュサイズの平方根となる。ハッシュ関数へのコリジョンサーチ攻撃と、素因数分解攻撃とのバランスを考えると、数体ふるい法による素因数分解攻撃の計算量評価式が式 (2) であるとすれば 、ハッシュ値 160 ビットと法 1024ビットとがだいたいバランスすることになる。
したがって、ディジタル署名のセキュリティレベルを 1024 ビット以上に求めるならば 、ESIGN
署名の法サイズを 1024 ビット以上にするとともに、ハッシュ関数も SHA-1 の代わりに、SHA-256 、SHA-384 、SHA-512 にすることも検討しなければならない。

5

6 各標準化機関における ESIGN 署名の仕様
ESIGN 署名は、CRYPTREC 以外にも様々な標準化機関へ投稿されている。その仕様名は、最初に ESIGN 署名が発表されて以来、何度かの変更が行われている [NTT01a]。参考までにそれらの仕様の違いを次表にまとめる。年数経過とともに、推奨パラメータはより大きくなっており、また安全性理論研究の進展によって、デ ィジタル署名における最強の意味での安全性を (ある仮定のもとで) 証明できるスキームに変更されている。より安全サイドに最も寄った仕様は、IEEEP1363a と NESSIE である。
表 1: 各標準化機関へ投稿されている ESIGN の比較
標準化機関
推奨パラメータ
エンコーデ ィング方法
電子署名法

jnj  1024、e  8
e  4、n は規定なし

ISO 14888-3
IEEE P1363a
規定なし
NESSIE
jnj = 1152、e = 210
CRYPTREC 2000 jnj  960 、e  8
CRYPTREC 2001 jnj = 1152 、e = 210

EMSA|
EMSA5
EMSA5|EMSA

7 まとめ
ESIGN 署名は、適切なパラメータを選択すれば、現段階では安全であると考えられる。しかし 、ESIGN 署名が安全性の根拠として帰着してるいる e 乗根近似問題の解法研究は、素因数分解問題や離散対数問題の解法研究ほど活発に行われているとは言い難い。ESIGN 署名は、日本における電子署名法の署名方式の 1 つに指定されていることや、国際的にも IEEE や ISO や NESSIE(1ststage) へ採録されるなど 、知名度は高いと思われる。したがって、今後より活発に行われる研究対象になる可能性がある。活発に研究が行われた場合、予期せぬブレークスルーが生じ 、ESIGN署名の安全性が致命的に崩壊する可能性は否定できない。今後の研究動向を注意深くフォローする必要がある。

参考文献[AA97] 安藤 心, 荒木 純道, \LLL アルゴ リズムによる ESIGN の偽造確率に関する数値的検討,"
1997 年電子情報通信学会 基礎境界ソサイエティ大会, A-7-15,p.140 (1997)[AA99] 安藤 心, 荒木 純道, \有限環上の 2 次不等式解法に関する数値的検討," 1999 年電子情報通信学会 総合大会, A-7-3,p.231 (1999)[BD85] E. Brickel, J. DeLaurentis, \An Attack on a Signature Scheme proposed byOkamode and Shisaishi," Advances in Cryptology { CRYPTO'85, LNCS, 218 (1986),Springer-Verlag, 28{32.
6[BDG99] D. Boneh, G. Durfee, N. Howgrave-Graham, \Factoring N = pr q for large r,"Advances in Cryptology { CRYPTO'99, LNCS, 1666 (1999), Springer-Verlag, 326{337.
[Co96a] D. Coppersmith, \Finding a Small Root of a Univeriate Modular Equation," Advances in Cryptology { EUROCRYPT'96, LNCS, 1070 (1996), Springer-Verlag, 155{
165.
[Co96b] D. Coppersmith, \Finding a Small Root of a Bivariate Integer Equation; Factoringwith High Bits Known," Advances in Cryptology { EUROCRYPT'96, LNCS, 1070(1996), Springer-Verlag, 178{189.
[Cr00] \ESIGN 署名攻撃評価報告書," 2000 年度 CRYPTREC 詳細評価報告書, (2000)[IEEE] \IEEEP1363aDraft
Version9Standard
Speci cations
for Public Key Cryptography: Additional Techniques," IEEE (2001), available fromhttp://grouper.ieee.org/groups/1363[Le87] H.W. Lenstra, Jr, \Factoring Integers with Elliptic Curves," Ann. of Math., (2) 126(1987), 649{673.
[LL93] A.K. Lenstra, H.W. Lenstra, Jr, \The Development of the number eld sieve,"
Lecture Note in Mathematics, 1554 (1993), Springer-Verlag.
[Mo87] P. L. Montgomery, \Speeding the Pollard and Elliptic Curve Methods of Factorization,"
Mathematics of Computation, 48 (1987), 243{264.
[NTT01a] NTT 情報流通プ ラットフォーム研究所, \ESIGN 仕様書," (2001), available fromhttp://info.isl.ntt.co.jp/esign/CRYPTREC/index-j.html[NTT01b] NTT 情報流通プラットフォーム研究所, \ESIGN 自己評価書," 2001 年度 CRYPTREC
応募書類, (2001)[VGT88a] B. Vallee, M. Girault, P. Toffin, \How to Break Okamoto's Cryptosystem
by Reducing lattice Bases," Advances in Cryptology { EUROCRYPT'88, LNCS, 330(1988), Springer-Verlag, 281{291.
[VGT88b] B. Vallee, M. Girault, P. Toffin, \How to Guess lth Roots Modulo n by
Reducing Lattice Bases," AAECC-6, LNCS, 357 (1988), Springer-Verlag, 427{442.

A ESIGN 署名の仕様
2001 年度 CRYPTREC 投稿版 [NTT01a] の ESIGN 署名の仕様の概略を記述する。

7

A.1 鍵生成:

入力:

出力:

処理手順

Step 1
Step 2
Step 3pLen セキュリティパラメータ (正整数)e
8 以上の指数 (正整数)
PK 公開鍵 (n; pLen; e)
SK 秘密鍵 (p; q)
pLen ビットの 2 つの素数 p、q を選ぶ
n = p q を計算する
PK = (n; pLen; e)、SK = (p; q) を出力する2A.2 署名生成プリミティブ
SP-ESIGN
入力:
SK:

出力
処理手順

Step 1
Step 2
Step 3
Step 4:

Step 5
Step 6PKfs

秘密鍵 (p; q )公開鍵 (n; pLen; e)
メッセージ 、0 f < 2pLen;1 である整数
署名、0 s < n である整数



GCD(r; n) = 1 を満たす r 2 f1; 2;    ; pq ; 1g をランダムに選ぶz = f  22pLen を計算する= (zl ; mre ) mod n とする
w0 = pq を計算する
t = erwe0;1 mod p とし 、s = r + tpq を計算する

s を出力する

A.3 署名検証プリミティブ

VP-ESIGN
入力:
PK 公開鍵 (n; pLen; e)
:

出力
処理手順

Step 1
Step 2
Step 3
Step 4:sf

署名、0 s < n である整数
検証データ、0 f < 2pLen;1 である整数

T = s modn を計算する
T
f = 2pLenを計算する
f が 0  f < 2pLen; でなかったら、\invalid"と出力して終了
f を出力する
2218

A.4 署名生成スキーム

SSA-ESIGN-Sign
入力:
SK 秘密鍵 (p; q)
:

出力
処理手順

Step 1:

Step 2PKMs

公開鍵 (n; pLen; e)
署名対象メッセージ、オクテット列
署名

EMSA-ESIGN-Encode を用いて、メッセージ M を整数 f に変換する
f = EMSA-ESIGN-Encode(M; pLen)
SP-ESIGN を用いて、鍵 SK 、PK と整数 f から整数 s を得る
s = SP-ESIGN(SK; PK; f )s を出力する

Step 3

A.5 署名検証スキーム

SSA-ESIGN-Verify
入力:
PK 公開鍵 (n; pLen; e)
:

出力
処理手順

Step 1
Step 2
Step 3:

Mss

検証対象メッセージ、オクテット列
検証対象署名\署名は有効"または \署名は無効"

VP-ESIGN を用いて、公開鍵 PK と整数 s から整数 f 0 を得る
f 0 = VP-ESIGN(PK; s)
EMSA-ESIGN-Verify を用いて、f 0 が M の正しいエンコード 結果であるか調べる
Result = EMSA-ESIGN-Verify(M; f 0 ; pLen)
Result が \矛盾しない"ならば \署名は有効"を出力する。
そうでなければ \署名は無効"を出力する。

9A.6 エンコーディング処理

EMSA-ESIGN-Encode
オプション :
ハッシュ関数H ashhLen:

入力:Ml

ハッシュ関数の出力長、ビット長
エンコード 対象のメッセージ
出力長 (ビット長)
エンコード 結果

出力
処理手順

f

Step 1
Step 2

エラー処理:l 16 hLen ならば \エラー"を出力して終了
M にハッシュ関数を作用させ、ビット列に変換したものを H とする
H = OS2BSP(H ash(M ); hLen)(OS2BSP はオクテット列をビット列に変換する関数)
ビット長 l 16 hLen の任意のビット列を P S とする
ただし BS2OSP(P S; l 16 hLen) は各オクテットに 255 を含まないものとする
各列を連結して F とする
F = OS2BSP(0; 8) P S OS2BSP(255; 8) H
F を整数に変換する
f = B S 2 I P (F )(BS2IP はビット列を整数に変換する関数)
f を出力する:; ;; ;

Step 3
Step 4; ;jj jj

Step 5

Step 6jj

A.7 検証処理

EMSA-ESIGN-Verify:
ハッシュ関数オプション

H ashhLen:

入力

Mf:l

出力
処理手順

Step 1

Step 2

Step 3:f

ハッシュ関数の出力長、ビット長メッセージ、オクテット列
検証データ
f の有効ビット長\矛盾しない"または \不正"検証データ f をビット列 T へ変換する
T = I2BSP(f; l )(I2BSP は整数をビット列へ変換する関数)
0
T の下位 hLen ビットを取り出してオクテット列へ変換したものを M とする
0
M = BS2OSP([T ]hLen ; hLen)(BS2OSP はビット列をオクテット列に変換する関数)
0
H ash(M ) と M が同じならば \矛盾しない "を出力する
そうでなければ \不正"を出力する

10