7章.　付録

• 1.　安全性の根拠となる数論
  • 1.1.　素因数分解問題
    • 1.1.1　素因数分解問題の解法
  • 1.2.　離散対数問題
    • 1.2.1.　有限体上の離散対数問題
    • 1.2.2.　有限体上の離散対数問題(DLP)に対する解法
    • 1.2.3.　楕円曲線上の離散対数問題
    • 1.2.4.　楕円曲線上の離散対数問題(EDLP)に対する解法
• 2.　ユークリッドの互除法
  • 2.1.　互除法
  • 2.2.　互除法のアルゴリズム証明
  • 2.3.　拡張ユークリッドの互除法
    • 2.3.1.　最大公約数の性質
    • 2.3.2.　拡張ユークリッドの互除法
• 3.　接触型ICカード

1.　安全性の根拠となる数論

1.1. 素因数分解問題

素因数分解問題とは、整数 n( ＞ 1)が与えられた時、n = pq となるような 1 より大きな整数(素因数)p、q を求める問題である。

1.1.1.　素因数分解問題の解法

素因数分解問題の主な解法を表1-1 に示す。

表において、上4つの解法は解読計算量が素因数の性質に依存する解法であり、その他の解法は解読計算量が合成数 n のサイズのみによって決まる解法である。
表から n を 2 素数 p、q の積とする時、(p±1)、(q±1) がそれぞれ大きな素因数をもち、かつ |p-q| が大きい場合、現時点で最強の解法は、数体ふるい法でとされている。

1.2. 離散対数問題

離散対数問題とは、有限群 G の 2 つの元 g、y ∈ G について、y = g^xを満たす指数 x を求める問題である。

1.2.1.　有限体上の離散対数問題

Y(=g^x mod p)、g、p(ここで p は素数または素数のべき、g は有限体F_pの原始元)から x を求める問題である。

1.2.2.　有限体上の離散対数問題(DLP)に対する解法

有限体上の離散対数問題に対する主な解法を表1-2 に示す。

表から (p-1) が大きな素因数をもつ場合、離散対数問題に対する現時点で最強の解法は数体ふるい法であるとされている。

1.2.3.　楕円曲線上の離散対数問題

楕円曲線とは、三次の多項式 f(x) = a₃x³ + a₂x² + a₁x + a₀ が重解を持たない場合において E; y² = f(x) で表される曲線のことをいう。また、式を成り立たせる x、y が、共に有理数である時、点(x, y)を有理点という。
この式を満たす有理点(x, y)をすべて集めると、滑らかな1 本あるいは2 本の曲線となる(f(x) が重解を持つ時、途中で折れ曲がった、あるいは交わりのある1 本の曲線となるため、重解を持つ場合は除く)。

楕円曲線E(F_p)に関する離散対数問題は、以下のように記述される。
任意の点P ∈ E(F_p)に対して、[P] = {０, P, 2P, 3P,…}は有限巡回群となる。この巡回群の位数を q とすると，任意の[P] の要素(点)に対して、xP = Q となる x ∈ Z_qが常にただ一つ存在する。従って、Q ∈ [P] が与えられた時に、xP = Q となる x ∈ Z_qを求める問題である。

1.2.4.　惰円曲線上の離散対数問題(EDLP)に対する解法

楕円曲線上の離散対数問題に対する主な解法を表1-3 に示す。

MOV-Reduction法、および、Smartおよび佐藤−荒木の攻撃法の適用を受けない楕円曲線を利用する場合、楕円曲線上の離散対数問題に対する現時点での最強の解読法は、Pohig-Hellman法であるとされている。
このことから、楕円曲線に基づく暗号・署名方式では、従来の素因数分解問題や有限体上の離散対数問題に基づく暗号・署名方式に比べて鍵サイズを小さくでき、処理を高速に行えると見られている。

2.　ユークリッドの互除法

ユークリッドの互除法を利用すると、二つの整数a、b それぞれの素因数分解を知らなくても、それらの最大公約数 gcd(a, b) を容易に求めることができる。

2.1. 互除法

ユークリッドの互除法のアルゴリズムは、以下のように与えられる。

[入力]

0でない二つの整数 a₀、a₁。但し、a₀ ≧ a₁と仮定する。

[出力]

gcd(a₀, a₁)

[アルゴリズム]

a₂ = a₀ mod a₁、a₃ = a₁ mod a₂ … という処理を繰り返す。

まず、i = 1 とおく。次に、a_i ≠ 0 である間、以下を実行する。

a_i+1 = a_i-1 mod a_i、i ← i + 1

a_i = 0 になった時、a_i-1が gcd(a₀, a₁) である。

(例題.1)　ユークリッドの互除法を使い、gcd(10, 7)を求めると、表1-1より、a₄ = 0 なので、a₃ = 1 がgcd(10, 7)である。

2.2.　互除法のアルゴリズム証明

ユークリッドの互除法のアルゴリズムの正しさは、以下の定理に基づいている。

a を b で割った余りを c とした時、gcd(a, b) = gcd(b, c) である。

[証明]

i. gcd(a, b) ≧ gcd(b, c) を示す。a を b で割った余りが c なので、以下の式が書ける。

a = qb + c

※　但し、q は商である。

ここで、m = gcd(b, c)とおくと、以下のことが言える。

�@　m = gcd(b, c)なので、b は m で割り切れる。

�A　m = gcd(b, c)なので、b、c は共に m で割り切れる。従って、qb + c は m で割り切れる。また、a = qb + c なので、a は m で割り切れる。

�@、�Aより、m は (a, b)の公約数と言える。

また、一般に、(a, b)の公約数　≦ (a, b)の最大公約数であるから、m ≦ gcd(a, b)である。故に、gcd(b, c) ≦ gcd(a, b)が成り立つ。

ii. gcd(a, b) ≦ gcd(b, c) を示す。m' = gcd(a, b)とおき、c = a - qb とする。

i. と同様に、

�@　m' = gcd(a, b)なので、a は m' で割り切れる。

�A　m' = gcd(a, b)なので、a、b は共に m' で割り切れる。従って、a - qb は m' で割り切れる。また、c = a- qb なので、c は m' で割り切れる。

�@、�Aより、m' は (b, c)の公約数と言える。

i. と同様で、m' ≦ gcd(b, c)である。故に、gcd(a, b) ≦ gcd(b, c)が成り立つ。

∴　i. ii.より、gcd(a, b) = gcd(b, c)となる。

定理より、a₀ を a₁ で割った余りを c とすると、gcd(a₀, a₁) = gcd(a₁, a₂) である。また、a₁ を a₂ で割った余りを a₃ とすると、gcd(a₁, a₂) = gcd(a₂, a₃) である。この処理を続けると、

a₀ ＞ a₁ ＞ a₂ ＞ a₃ ＞ …

なので、ついに余りは 0 となる。今、a₂ が a₃ で割り切れると仮定すると、gcd(a₂, a₃) = a₃ である。従って、

gcd(a₀, a₁) = gcd(a₁, a₂) = gcd(a₂, a₃) = a₃

となる。これがユークリッドの互除法である。

2.3. 拡張ユークリッドの互除法

2.3.1.　最大公約数の性質

0 でない二つの整数 a、b の最大公約数 d = gcd(a, b) は、ある二つの整数 x、y を使って、以下の式のように書くことができる。

d = ax + by

(例題.2)　20 と 12 の最大公約数は、d = gcd(20, 12) = 4 である。この時、

4 = 20 × 2 + 12 × (-3)

と書ける。従って、x = 2、y = -3 である。

2.3.2.　拡張ユークリッドの互除法

二つの整数 a、b から d = gcd(a, b) かつ d = ax + by となる整数 x、y を求めるアルゴリズムを拡張ユークリッドの互除法といい、以下のアルゴリズムによって与えられる。

[入力]

0でない二つの整数 a、b である。但し、a ≧ b と仮定する。

[出力]

d = gcd(a, b) かつ d = ax + by となる(d, x, y)である。

[アルゴリズム]

�@　まず、i = 1、かつ

(a₀, x₀, y₀) = (a, 1, 0)

(a₁, x₁, y₁) = (b, 0, 1)

とおく。

�A　次に、a_i ≠ 0 である間、以下を実行する。

q_i+1 = a_i-1を a_iで割った商

(a_i+1, x_i+1, y_i+1) = (a_i-1, x_i-1, y_i-1) - q_i+1 × (a_i, x_i, y_i)

i ← i + 1

(a_i-1について整理すると、a_i-1 = q_i+1a_i + a_i+1 と書ける。すなわち、a_i-1をa_iで割った余りがa_i+1である。)

�B　a_i = 0 になった時、(a_i-1, x_i-1, y_i-1) を (d, x, y) として出力する。

(例題.3)　拡張ユークリッドの互除法を、a₀ = 10、a₁ = 7 に適用してみると、表2-2 が得られる。

まず、10 を 7 で割った商は 1 なので q₂ = 1 である。また、

(a₀, x₀, y₀) - 1 × (a₁, x₁, y₁) = (3, 1, -1)

なので、(a₂, x₂, y₂) = (3, 1, -1)である。最後に、a₄ = 0 なので、(a₃, x₃, y₃₁) = (1, -2, -3) が (d, x, y) である。この時、確かに、

1 = gcd(10, 7) = 10 × (-2) + 7 × 3

が成り立っている。

拡張ユークリッドの互除法の正しさは、以下のようにして分かる。

まず、アルゴリズムの{a_i}に関する部分は、ユークリッドの互除法そのものである。従って、まず、d = gcd(a₀, s₁) であることが分かる。
次に、明らかに、

a₀ = a₀x₀ + a₁y₀

a₁ = a₀x₁ + a₁y₁

である。ここで、数学的帰納法を利用すると、各 i に対し、

a_i = a₀x_i + a₁y_i

が成り立つことを示せる(表3-1 を参照)。従って、

d = a₀x + a₁y

が成り立つことになる。

3.　接触型ICカード

ここでは、ICカードに本当に耐タンパ性が備わっているかをETCカード(接触型ICカード)を例に検討する。

図7-1　分解する前

図7-2　表面剥離後

今回は接触型のICカードを用いてる。
接触型は専用のリーダ・ライタ(ここでは車載端末)を用いることが必要だが、
非接触型のICカードでは普通ICチップの周りにアンテナが埋め込まれている。