Pebble's Diary

プログラマーの作業メモ

RSA暗号の原理を理解するための数学知識

RSA暗号に関する文章を読んでいてもその数学的な原理がさっぱり理解できなかったのですが、色々読んでいるうちになんとなく分かってきましたので、メモしておきます。

 a = b \mod n, \\
c = d \mod n 

のとき、

 a + c = b + d \mod n

 a * c = b * d \mod n

 a^{m} = b^{m} \mod n

である。

 ef = eg \mod n で gcd(e, n) = 1 ならば
 f = g \mod n
である。

合同式の意味とよく使う6つの性質 | 高校数学の美しい物語

オイラーの定理

nが正の整数で、gcd(a, n) = 1 のとき、  a^{\phi(n)} = 1 \mod n である。
ここで、gcd は greatest common divider の略で最大公約数を意味する。
 \phi(n) は1からnまでの自然数のうちgcd(b, n)=1となる数bの個数を意味する関数とする。

nが素数の場合は、bは1, 2, 3, … , n-1となり、 \phi(p) = p-1 となる。

また、p, qが素数の場合、2つをかけた合成数 pq に対して \phi(pq) = (p-1)(q-1)が成り立つ。

RSA暗号の世界 | サルにも分かるRSA暗号

RSAのひ・み・つ - 小人さんの妄想

オイラーのφ関数 - Wikipedia

中国人剰余定理によりgcd(p, q) = 1のとき、
 m = n \mod p
 m = n \mod q
であれば
 m = n \mod pq   である。

中国剰余定理の証明と例題(二元の場合) | 高校数学の美しい物語

エドワード曲線における加法

エドワード曲線 
x^{2} + y^{2} = a^{2} + a^{2}x^{2}y^{2}

において、曲線上の2つの点  (x_{1}, y_{1}), (x_{2}, y_{2}) の加算後の点を次のように定義する。

 \displaystyle X = \frac {1} {a} \cdot \frac {x_{1} y_{2} + x_{2} y_{1}} {1 + x_{1} x_{2} y_{1} y_{2}}

 \displaystyle Y = \frac {1} {a} \cdot \frac {y_{1} y_{2} - x_{1} x_{2}} {1 - x_{1} x_{2} y_{1} y_{2}}

この点は代数計算によって、エドワード曲線上の点になることを確かめることができる。
が、計算は長く厄介なので、計算方法を記しておく。  

 A = X^{2} + Y^{2} - a^{2}X^{2}Y^{2}を計算し、 a^{2}に等しくなることを示す方針で行く。

代入すると  \displaystyle a^{2} A = \frac {1} {(1 + x_{1} x_{2} y_{1} y_{2})^{2}} \cdot \frac {1} {(1 - x_{1} x_{2} y_{1} y_{2})^{2}} \cdot ( \\ (x_{1}y_{2} + x_{2}y_{1})^{2}(1- x_{1}x_{2}y_{1}y_{2})^{2} \\ + (y_{1}y_{2} - x_{1}x_{2})^{2} (1 + x_{1} x_{2} y_{1} y_{2})^{2} \\ - (x_{1}y_{2} + x_{2}y_{1})^{2} (y_{1}y_{2} - x_{1}x_{2})^{2})

ここで、

 \displaystyle a^{2}A(1 - x_{1}^{2} x_{2}^{2} y_{1}^{2} y_{2}^{2}) = B + C + Dと置く。

B + C + Dを全て展開し、 x_{1}, x_{2}, y_{1}, y_{2}の順番で並べると、7つほどペアが消える。

 B + C + D = x_{1}^{2}y_{2}^{2} + x_{2}^{2}y_{1}^{2} + x_{1}^{4}x_{2}^{2}y_{1}^{2}y_{2}^{4} + x_{1}^{2}x_{2}^{4}y_{1}^{4}y_{2}^{2} \\
+ y_{1}^{2}y_{2}^{2} + x_{1}^{2}x_{2}^{2} - 4 x_{1}^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2} + x_{1}^{2}x_{2}^{2}y_{1}^{4}y_{2}^{4} + x_{1}^{4}x_{2}^{4}y_{1}^{2}y_{2}^{2} \\
- x_{1}^{2}y_{1}^{2}y_{2}^{4} - x_{2}^{2}y_{1}^{4}y_{2}^{2} - x_{1}^{4}x_{2}^{2}y_{2}^{2} - x_{1}^{2}x_{2}^{4}y_{1}^{2}  \\
= E_{4} + E_{8} + E_{12}

ここでE_{i}はx,yの個数を表すが、それぞれ別々に計算してゆくと、 E_{4}, E_{8}, E_{12}には、  x_{1}^{2} + y_{1}^{2},  x_{2}^{2} + y_{2}^{2}が2つ以上出てくるので、  x_{1}^{2} + y_{1}^{2} = a^{2} ( 1 + x_{1}^2 y_{1}^2)
 x_{2}^{2} + y_{2}^{2} = a^{2} ( 1 + x_{2}^2 y_{2}^2) に置き換える。

ここで、  \frac {1} {a^{4}} (E_{4} + E_{8} + E_{12})を計算すると、5つほどペアが消え、  1 - 2 x_{1}^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2} +  x_{1}^{4}x_{2}^{4}y_{1}^{4}y_{2}^{4}が残る。 あとは簡単である。

エドワード曲線とツイストエドワード曲線

2007年のエドワードさんの論文(http://www.ams.org/journals/bull/2007-44-03/S0273-0979-07-01153-6/S0273-0979-07-01153-6.pdf)

から、エドワード曲線と名付けられた


x^{2} + y^{2} = a^{2}(1 + x^{2} y^{2})

がどのような形をしているのか見てみましょう。

まずはa=1.0

2本の直線になってしまいました。。

次にa=1.1

次にa=0.9

おっと丸くなりました。

次に、ツイストエドワード曲線(http://eprint.iacr.org/2008/013.pdf)


a x^{2} + y^{2} = 1 + d x^{2} y^{2}

をみてみましょう。

a=1, d= -50

a=-1, d=-50

a=-1, d=5

楕円曲線の形

楕円曲線の一般的な形は以下のように表せます。


y^{2} = x^{3} + ax^{2} + bx + c

暗号理論に用いる楕円曲線は特異でない形のものだけを扱います。
特異でない形のものは2つのパターンに分けられます。
1) yが0の時のxの値が3つある場合
2) yが0の時のxの値が1つだけしかない場合
それぞれの例を挙げます。

1) 
y^{2} = x^{3} + x^{2} - x

これは、左の曲線が閉じているパターンです。

2) 
y^{2} = x^{3} + x^{2} + 1

これは開いているパターン。

このグラフのイメージを掴んでおくと、楕円曲線の理論がとても理解しやすくなります。

a) この曲線上の2つの点を結ぶ直線を引くと、曲線と交わる3番目の点は必ず存在します。
b) xをプラスの無限大に持っていくと、yがプラスの無限大とマイナスの無限大に近づきます。

楕円曲線論入門

楕円曲線論入門

群、体の定義

群(group)の定義

ある要素の集まりに対して、一つの演算規則 f を決め、演算結果はまた要素の集まりの一つになっているとします。
a, b, c を要素とします。

1) 全ての要素に対して、結合法則が成り立つ
f(f(a, b), c) = f(a, f(b, c))
2) 全ての要素に対して、単位元が存在する
3) 全ての要素に対して、逆元が存在する

体(field)の定義

ある要素の集まりに対して、加算 f と乗算 g を決め、演算結果はまた要素の集まりの一つになっているとします。
a, b, cを要素とします。
1) 加算について可換群
2) 乗算について可換群
3) 加算、乗算について分配法則が成り立つ
f(f(a, b), c) = f(a, f(b, c))
g(f(a, b), c) = g(a, g(b, c))

体の元の数を位数と呼びます。

ガロア体(galois field)

整数の集合に対して、
加算を「整数の加算後に素数pで割った余り」、乗算を「整数の乗算後に素数pで割った余り」とした場合、
これは位数 p の体となることが知られています。
つまり、全ての要素に対して逆元が存在します。 この体をGF(p)と書きます。

離散対数問題とは

RSA暗号の安全性が大きな数の因数分解の計算量の多さに元にしているのと同様、
楕円関数暗号の安全性は大きな数の離散対数の計算量の多さを元にしています。

離散対数問題をここで解説してみます。

p : 素数

これは説明不要ですね。 2,3,5,7,11,…のように自分自身の値未満の数で割り切れる値が1だけな正の整数値です。

mod : モジュラ演算

a mod b = c

整数aを整数bで割った余りがcであることを表します。 例えば、

7を3で割った余りは1
7 mod 3 = 1

8を3で割った余りは2
8 mod 3 = 2

9を3で割った余りは0
9 mod 3 = 0

余りは必ず、0からb-1の値のどれかになる性質があります。

原始根

3以上の素数 p と 1 以上 p-1 以下の整数 r が以下の性質を満たすとき r を mod p の原始根と呼ぶ。

r, r^{2}, ⋯, r^{p−2}
のいずれもが p で割って余り 1 でない。」

p=13の場合、原始根は2,6,7,11であることが知られていますが、原始根2の場合で計算してみます。

 2 \bmod 13 = 2

 2^{2} \bmod 13  = 4

 2^{3} \bmod 13 = 8

 2^{4} \bmod 13 = 16 \bmod 13 = 3

 2^{5} \bmod 13 = 32 \bmod 13 = 6

 2^{6} \bmod 13  = 64 \bmod 13 = 12

 2^{7} \bmod 13 = 128 \bmod 13 = 11

 2^{8} \bmod 13 = 256 \bmod 13 = 9

 2^{9} \bmod 13 = 512 \bmod 13 = 5

 2^{10} \bmod 13 = 1024 \bmod 13 =10

 2^{11} \bmod 13 = 2048 \bmod 13 = 7

余りがいずれも1ではないことは確認できましたが、それ以外に何か気がついたでしょうか?
右辺の計算結果が2から12までの数字になっていて重複がないですね。このことを巡回していると言ったりします。
さらに、対応に規則性はないように見えますね。

同様に、原始根6の場合でも試してみましょう。

 6 \bmod 13 = 6

 6^{2} \bmod 13 = 36 \bmod 13 = 10

 6^{3} \bmod 13 = 216 \bmod 13 = 8

 6^{4} \bmod 13 = 1,296 \bmod 13 = 9

 6^{5} \bmod 13 = 7,776 \bmod 13 = 2

 6^{6} \bmod 13 = 46,656 \bmod 13 = 12

 6^{7} \bmod 13 = 279,936 \bmod 13 = 7

 6^{8} \bmod 13 = 1,679,616 \bmod 13 = 3

 6^{9} \bmod 13 =  10,077,696 \bmod 13 = 5

 6^{10} \bmod 13 = 60,466,176 \bmod 13 = 4

 6^{11} \bmod 13 = 362,797,056 \bmod 13 = 11

原始根6の場合もやはり重複していませんし、対応に規則性も見えません。

原始根を使うと、この数式の右辺の値(=2からp-1までの値)と、左辺のべき乗の値が一対一対応させられるという性質があります。つまり、

p:素数、g:原始根、A: { 2, 3, 4, …, p-1 }(右辺値)、r: { 1, 2, 3, …, p-2 } (べき乗値)
 g^{r} \bmod p = A

と書いた時に、rとAが一対一対応するということになります。

ここで計算したように、Aの値を与えた時に、対応するrの値を求めるには、べき乗計算とモジュラ計算を、
(計算量が少なくなるように)次数の少ない方から順番に計算し、余りがAになるまで繰り返す必要があります。
これを簡単に計算する方法は見つかっていないそうです。
これが、離散対数問題と呼ばれるものです。

Aの値を与えた時に、べき乗の値を返す関数を一般に対数関数と呼びますが、
ここで、rのことを底gについてのAの離散対数と呼びます。

一対一対応する値のペアがあり、計算が難しいということは、暗号に使えそうな気がしてきますね。

参考:
原始根の定義と具体例(高校生向け) | 高校数学の美しい物語

暗号理論入門 原書第3版

暗号理論入門 原書第3版

安全素数

pが素数であり、2p+1=qも素数である場合、qを安全素数(safe prime)と呼ぶ。
安全という名前は暗号理論に由来する。

https://en.wikipedia.org/wiki/Safe_prime

https://ja.wikipedia.org/wiki/安全素数