Strong Diﬃe-Hellman Problem

(1)

修士論文要旨

(2013

年度)

Strong Diﬃe-Hellman Problem を難しくする群位数の選び方に関する考察

On the Distribution of Secure Strong Diﬃe-Hellman Parameters

電気電子情報通信工学専攻恩田泰則

Yasunori ONDA

1

序論

近年，情報化社会の発展に伴い，インターネットを利用した様々なサービスが提供され，我々の生活に不可欠なものとなっている．その一方で，マルウェアなどのサイバー攻撃が大きな社会問題となっている．サイバー攻撃に対する対策技術は広く研究されているが，

なかでも安全な暗号プロトコルの構築はその基礎となる重要技術である．本研究では，安全な暗号プロトコルの構築を実現するために必要となる構成要素に関し，

3

つの研究を行った．本稿ではその

1

つについて記述する．

楕円曲線暗号を含む公開鍵暗号方式や暗号プロトコルの中には，その安全性を

Strong Diﬃe-Hellman (SDH)

Problem

に依存しているものがある．そのような方式

としては例えば

[1],[2]

などがある．しかし，

SDH

に依存する方式を使う場合，適切なパラメータ設定をしないと安全性を大幅に落とすことになる．本稿では

SDH

を考慮した楕円曲線上のパラメータを求め，その中で安全なパラメータの分布と割合を示す．

本稿の構成は以下の通りである．2章では，Strong

Diﬃe-Hellman Problem

などについて説明する．3章では，行ったパラメータの探索の内容とその結果について述べ，4章でまとめる．

2

数学的準備

本章では数学的準備として，楕円曲線と

Strong Diﬃe-Hellman Problem，及び SDH

を難しくする条件について簡単に述べる．

2.1

楕円曲線

1980

年代に開発された楕円曲線暗号は，

RSA

暗号より短いビット長で同程度の安全性を持つ公開鍵暗号であり，その研究や実用化が進められている．楕円曲線暗号は，鍵長

160bit

で

RSA

暗号の鍵長

1024bit

に相当する安全性を持つ．楕円曲線暗号は

Diﬃe-Hellman

鍵共有プロトコルや

DSA

署名などの暗号方式を拡張して構成されているため，楕円曲線暗号の安全性はベースにしている楕円曲線上の問題の困難性に依存する．

素体

F

pの楕円曲線を次のように定義する．

定義

1 (楕円曲線).

方程式

E : y

²

= x

³

+ ax + b (a, b ∈ F

p

, ∆

E

= 4a

³

+ 27b

²

̸ = 0) (1)

で定義される曲線を素体

F

p上の楕円曲線という．また，

楕円曲線

E

の有理点の数を

N

とし，有理点

G = [x, y]

の位数を

q

とする，

楕円曲線においては，他の攻撃を避けるために以下の条件を満たすことが推奨される．

• N ̸ = p

SSSA

攻撃

[3]

を避けるための条件である．

• p

ⁱ

− 1(i

は

100

未満)が有理点の位数

q

で割り切れない

FR

帰着法及び

MOV

帰着法

[4]

を避けるための条件である．

2.2 Strong Diﬃe-Hellman Problem

ℓ-Strong Diﬃe-Hellman Problem

を次に示す．

(2)

定義

2 (ℓ-Strong Diﬃe-Hellman Problem). G

を群位数

q

の可換群とし，gを

G

の生成元とする．α

∈ Z

qとし，gと

g

^αⁱ

(i = 1, 2, . . . , ℓ)

が与えられたとき，g^α^ℓ+1 を求める問題である．

[5]

では，SDH以外の問題も以下の問題が示されている．

• Discrete Logarithm (DL) Problem

• Computation Diﬃe-Hellman (CDH) Problem

• Decisional Diﬃe-Hellman (DDH) Problem

• ℓ-weak Diﬃe-Hellman (ℓ-wDH) Problem

• ℓ-Bilinear Diﬃe-Hellman Inversion (ℓ-BDHI) Problem

• ℓ-Bilinear Diﬃe-Hellman Exponent (ℓ-BDHE) Problem

また，それぞれの問題の難しさの関係は以下のようになっている．

DL ≥ CDH ≥ DDH ≥ ℓ-wDH ≥ ℓ-SDH ≥ ℓ-BDHI, (ℓ + 1)-BDHE

SDH

に関しては，次の定理が知られている

[5]．

定理

1. d

を

p − 1

の因数とし，g，g^α，g^α^d が与えられたとき，α を求めるのに必要な計算量は

O(log p · √

(p − 1)/d + √

d)

であり，必要なメモリ量は

O(max { √

(p − 1)/d, √

d } )

である．

定理

2. d

を

p+ 1

の因数とし，

g， g

^αⁱ

(i = 1, 2, . . . , 2d)

が与えられたとき，αを求めるのに必要な計算量は

O(log p · ( √

(p + 1)/d + d))

であり，必要なメモリ量は

O(max { √

(p + 1)/d, √

d } )

である．

定理

1,2

より

α

が求まる．

SDH

に基づく方式の例として，Gap-Diﬃe-Hellman 仮定のブラインド署名や

ElGamal

暗号がある

[5]．ま

た，

[5]

では，楕円曲線の標準的なパラメータ

[6]

を用いてブロードキャスト暗号

[7]

を構成した場合，ユーザーの数が

2

³²人のときに

SDH

を破る計算量は

O(2

⁵⁹

)

であり，2⁶⁴人のときに

SDH

を破る計算量は

O(2

⁴²

)

であることが示されている．

2013/12/9

1

q, (q-1)/2, (q+1)/2

の関係

ݍ

ݍ + 1 2 ݍ − 1

qは素数なので 2 6m-1or 6m+1

6m-1

偶 3m-1

ݍ = 6m+1 6m-1 6m+1

3m 3m 3m+1

௤±ଵ ଶ=

奇偶奇奇偶奇偶

連続するため、両者は偶数と奇数

m= 2m’+1 2m’ 2m’ 2m’+1 2m’+1 2m’ 2m’+1 2m’

2(3m’+1)

௤±ଵ

ଶ= 2x3m’ 2x3m’ 2(3m’+2)

6m’-1 3(2m’+1) 3(2m’+1) 6m’+1

ݍ = 12m’+5 12m’-1 12m’+1 12m’+7 12m’+5 12m’-1 12m’+1 12m’+7

・q を12で割った余りの値に応じて、(q-1)/2 , (q+1)/2 の因数は異なる。

・(q-1)/2 x (q+1)/2 は必ず6で割れる。

結論:

図

1: q, (q − 1)/2, (q + 1)/2

の関係

2.3 Strong Diﬃe-Hellman Problem

を難しくする条件

Strong Diﬃe-Hellman Problem

を難しくするための理想としては以下が考えられる．

•

位数

q, (q − 1)/2, (q + 1)/2

がすべて素数になるしかし，qに関しては次の定理が成り立つ．

定理

3.

位数

q

を

12

で割った余りに応じて

(q − 1)/2, (q + 1)/2

のどちらかに必ず

2, 3

の因数が含まれる．

定理

3

より，上記の条件を満たすことは不可能である．

q, (q − 1)/2, (q + 1)/2

の関係を図

1

に示す．qが素数の場合，q

= 6m − 1

か

q = 6m + 1

と表すことができ，(q

− 1)/2, (q + 1)/2

は偶数と奇数のペアになってそれぞれ

(q − 1)/2 = 3m − 1

か

(q − 1)/2 = 3m，

(q + 1)/2 = 3m

か

(q + 1)/2 = 3m + 1

と表すことができる．さらに

m

は

m = 2m

^′ か

m = 2m

^′

+ 1

のいずれかで表すことができ，q,

(q − 1)/2, (q + 1)/2

を

m

^′ を用いて表すことができる．

そこで，qは素数であるものを選ぶとして，以下の条件を満たすものを探す必要がある．

• (q − 1)/2, (q + 1)/2

に小さな素因数が少し含まれ，

残りが大きな素因数

1

つになる

ここで，(q

− 1)/2, (q + 1)/2

の小さな素因数の積が

2 × log

₂

q

ビット以下となる

q

を

Acceptable , (q −

(3)

1)/2, (q + 1)/2

の小さな素因数の積が

8

以下のものを

Semiperfect

と呼ぶことにし，(q

− 1)/2, (q + 1)/2

の小さな素因数がそれぞれ

2

と

3

のみである

q

を

Perfect

と呼ぶことにする．

Perfect

なパターンより

SDH

を難しくするパターンは理論上存在しない．

3

章では，上記の条件を満たすパラメータを探索する．

3

パラメータの探索

本章では，行った探索の内容とその結果について述べる．

3.1

内容

楕円曲線

E

において，2.3章で述べた条件を満たすパラメータを探索した．

探索に用いたプログラムは数値計算ソフトの

PARI/GP(http://pari.math.u-bordeaux.fr)

である．

使用したパラメータの詳細は以下の通りである．

• p, a:[8]

の推奨パラメータ

• x = 0

• b = y

²

G = [x, y]

が楕円曲線上に必ず乗るようにする

ため．

• N :楕円曲線 E

上の有理点の数

• q:楕円曲線 E

上の有理点

G = [x, y]

の位数

q

が素数になることが条件である．

• h = N/q:有理点の数と位数の比

ハッシュ関数などを使って群に写像する場合，h が小さい方が群に写像されやすくなる．

3.1.1

探索の手順

y = 1

から

y = (q − 1)/2

まで，以下の手順を繰り返す．

1. b = y

²

mod q

を計算する．

2. (4a

³

+ 27b

²

) ̸ = 0

ならば次へ進む

3.

楕円曲線

E

上の有理点の数

N

を求める．

4.

楕円曲線

E

上の有理点

G

のオーダー

q

を求める．

5.

オーダー

q

が素数ならば次へ進む．

6. h = N/q

を求める．

7.

素体上では

P

ⁱ

− 1 mod q ̸ = 0

をチェックする（i は

100

未満）．GF

(2

^m

)

上では

2

ⁱ

− 1 mod q ̸ = 0

をチェックする（iは

100m

未満）．

3.2

結果

3.2.1 GF (p)

上の

160bit

位数

探索した結果を表

1

に示す．ここで，Candidatesは

q

が素数で

h = 1

且つ安全な曲線の数を表す．

表

1:

探索の結果

(GF (p)

上の

160bit

位数)

Range(y) Candidates Acceptable Semiperfect Perfect

1-500000 2428 30 1 1

500000-1000000 2469 20 1 1

1000000-2000000 5039 44 1 0

2000000-3000000 4940 37 1 1

3000000-4000000 5010 24 2 0

4000000-5000000 5028 43 1 0

合計 24914 198 7 3

Perfect

なものの例として，次のものが見つかった．

p =1461501637330902918203684832716283019 653785059327

a =1461501637330902918203684832716283019 653785059324

b =1111088889 y =33333

q =1461501637330902918203686034250499499 783141301797

(q − 1)/2 =2 × 3653754093327257295509215085626248 74945785325449

(q + 1)/2 =3 × 2435836062218171530339476723750832

49963856883633

(4)

3.2.2 GF (q)

上の

192bit

位数

2

に示す．

表

2:

探索の結果

(GF (q)

上の

192bit

位数)

Range(y) Candidates Acceptable SECver2 Semiperfect Perfect

1-8000000 26600 161 54 4 1

3.2.3 GF (2

¹⁶³

)

上の

163bit

位数

3

に示す．

表

3:

探索の結果

(GF (2

¹⁶³

)

上の

163bit

位数)

Range(y) Candidate Acceptable SECver2 Semiperfect Perfect

1-1000000 11581 75 21 2 0

1000000-2000000 11890 72 14 0 0

2000000-3000000 11665 62 11 0 0

3000000-4000000 11585 84 10 0 0

4000000-5000000 11674 84 15 1 0

4

まとめ

本稿では，楕円曲線上の

Strong Diﬃe-Hellman

Problem

を難しくする群位数の選び方について考察

を行った．

Strong Diﬃe-Hellman Problem

を難しくするための理想は，位数

q, (q − 1)/2, (q + 1)/2

がすべて素数になることである．しかし，それらを満たすことは不可能であるため，(q

− 1)/2, (q + 1)/2

にそれぞれ小さな素因数が少し含まれ，残りが大きな素因数

1

つになるパラメータを探索した．その結果として，探索した曲線の数における安全なパラメータの分布と割合を示し，また

Perfect

なパラメータが実在することを示した．

今後の課題として，より大きなサイズのパラメータについても探索することが挙げられる．

謝辞

本研究は，産業技術総合研究所セキュアシステム研究部門との共同研究として行われました．関係者の皆様に深く感謝すると共にこの場を借りて厚く御礼申し上げます．

研究業績

1. 恩田泰則，辛星漢，古原和邦，今井秀樹，“パスワードのオンライン攻撃とミスタイプを切り分け可能な2要素認証方式,”

2010年暗号と情報セキュリティシンポジウム(SCIS2010)，

2010年1月．

2. Y. Onda, S. Shin, K. Kobara, and H. Imai, “How to distinguish on-line dictionary attacks and password mis- typing in two-factor authentication,” Proc. of 2010 In- ternational Symposium on Information Theory and its Applications, pp.571–576, 2010.

3. 恩田泰則，辛星漢，古原和邦，今井秀樹，“クラウド環境に適したオンラインデータ分散管理方式,” 2011年暗号と情報セキュリティシンポジウム(SCIS2011)，2011年1月．

4. 恩田泰則，辛星漢，古原和邦，今井秀樹，“ Strong Diﬃe- Hellman Problemを難しくする群位数の選び方に関する考察,”

2014年暗号と情報セキュリティシンポジウム(SCIS2014)，

2014年1月．

参考文献

[1] D. Boneh and X. Boyen, “Short signatures without random oracles,” Eurocrypt 2004, LNCS, vol.3027, pp.56–73, Springer-Verlag, 2004.

[2] D. Boneh and X. Boyen, “Eﬃcient selective-id secure identity-based encryption without random oracles,” Euro- crypt 2004, LNCS, vol.3027, pp.223–238, Springer-Verlag, 2004.

[3] T. Satoh and K. Araki, “Fermat quotients and the poly- nomial time discrete log algorithm for anomalous elliptic curves,” Commentarii Math. Univ Sancti Pauli, vol.47, pp.81–92, 1998.

[4] A. Menezes, T. Okamoto, and S. Vanstone, “Reducing elliptic curve logarithms to logarithms in a ﬁnite ﬁeld,” IEEE Transactions to Information Theory, vol.39, pp.1639–1646, 1993.

[5] J.H. Cheon, “Security analysis of the strong diﬃe-hellman problem,” Advances in Cryptology - EUROCRYPT 2006, Lecture Notes in Computer Science, vol.4004, pp.1–11, Springer-Verlag, 2006.

[6] D. Boneh, B. Lynn, and H. Shacham, “Short signatures from the weil pairing,” Journal of Cryptology, vol.17, no.4, pp.297–319, 2004.

[7] D. Boneh, C. Gentry, and B. Waters, “Collusion resis- tant broadcast encryption with short ciphertexts and pri- vate keys,” Advances in Cryptology - CRYPTO 2005, Lec- ture Notes in Computer Science, vol.3621, pp.258–275, Springer-Verlag, 2005.

[8] Standards for Eﬃcient Cryptography Group (SECG), “Sec 2: Recommended elliptic curve domain parameters,” Sept.

2000. http://www.secg.org/collateral/sec2 ﬁnal.pdf

Strong Diﬃe-Hellman Problem

(2013

Strong Diﬃe-Hellman Problem を難しくする群位数の選び方に関 する考察

On the Distribution of Secure Strong Diﬃe-Hellman Parameters

Yasunori ONDA

1

3

1

Strong Diﬃe-Hellman (SDH)

Problem

[1],[2]

SDH

SDH

Diﬃe-Hellman Problem

2

Strong Diﬃe-Hellman Problem，及び SDH

2.1

1980

RSA

160bit

RSA

1024bit

Diﬃe-Hellman

DSA

F

1 (楕円曲線).

E : y

= x

+ ax + b (a, b ∈ F

, ∆

= 4a

+ 27b

̸ = 0) (1)

F

E

N

G = [x, y]

q

• N ̸ = p

SSSA

[3]

• p

− 1(i

100

q

FR

MOV

[4]

2.2 Strong Diﬃe-Hellman Problem

ℓ-Strong Diﬃe-Hellman Problem

2 (ℓ-Strong Diﬃe-Hellman Problem). G

q

G

∈ Z

g

(i = 1, 2, . . . , ℓ)

[5]

• Discrete Logarithm (DL) Problem

• Computation Diﬃe-Hellman (CDH) Problem

• Decisional Diﬃe-Hellman (DDH) Problem

• ℓ-weak Diﬃe-Hellman (ℓ-wDH) Problem

• ℓ-Bilinear Diﬃe-Hellman Inversion (ℓ-BDHI) Problem

• ℓ-Bilinear Diﬃe-Hellman Exponent (ℓ-BDHE) Problem

DL ≥ CDH ≥ DDH ≥ ℓ-wDH ≥ ℓ-SDH ≥ ℓ-BDHI, (ℓ + 1)-BDHE

SDH

[5]．

1. d

p − 1

O(log p · √

(p − 1)/d + √

d)

O(max { √

(p − 1)/d, √

d } )

2. d

p+ 1

g， g

(i = 1, 2, . . . , 2d)

O(log p · ( √

(p + 1)/d + d))

Strong Diﬃe-Hellman Problem を難しくする群位数の選び方に関する考察