楕円曲線暗号
を読み進めながら疑問に思ったことをまとめ,解消する
素体の積の逆元が存在することの証明
背理法でpが素数であることに矛盾
素体上の楕円曲線の定義
$ y^2 = x^3 + a x + b……1-1
$ 4a^3 + 27b^2≠ $ 0……1-2
1-2は1-1の右辺が重解を持たない条件.つまり$ (x-\alpha)^2(x-\beta)に因数分解されない条件
楕円曲線の加法公式 R = P + Q
https://gyazo.com/9659e0e8a3aeaf0a5cd9c6067228e97b
$ y^2 = x^3 + a x + b……2-1
$ y- y_P = \lambda (x - x_P)……2-2 の共有点が-Rの座標
2-2の二乗を2-1に代入して$ y^2を消去して整理すると
$ x^3 - \lambda^2 x^2 + (a + 2\lambda^2 x_P)x-\lambda^2 x_P^2-y_P^2+2x_P y_P \lambda =0
左辺は$ (x-x_P)(x - x_Q)(x - x_R)と恒等
二次の項を比較すると$ x_R = \lambda^2 - x_P - x_Q
2-2は$ (x_R, -y_R)を満たすので,$ y_R = \lambda(x_P - x_R) - y_P
素体上での楕円曲線の加法はなぜ閉じているのか?(存在性)
有理数は素体の数と対応するので,3次方程式の解が有理数となればよい
3つの解のうち,2つの有理数解(PとQ)が存在するので,もう一つの解(R)も有理数解
素体が体をなし,その演算で楕円曲線上の加法が定義されるから
$ x_P = x_Qのパターンで$ y_P = 0が考えられるが,それは$ y_P = -y_Qの場合に内包
Hasse-Weilの定理
楕円曲線上のどの点をベースポイントに選んでも, その点の点位数は群位数の約数になることが知 られています 要証明 巡回群になるのか? → すべての楕円曲線で巡回群になるわけではないようだ
有限体 Fq 上の楕円曲線 E の Mordell-Weil 群を E(Fq) とかくとき, E(Fq) は 2 つの巡回群 C1, C2 の 直積になる, つまり$ E(F_q) \simeq C_1 \times C_2 (\#C_1|\#C_2)
$ F_q上の楕円曲線の有理点群$ E(F_q)は巡回群,あるいは以下のような二つの巡回群の直積である.
$ E(F_q) \simeq Z/m_1Z \times Z/m_2Z \ (m_1| m_2, m_1|q -1)
なぜなら,有限可換群の構造定理により,$ E(F_q)は一意的に以下のようにs個の巡回群の直積に分解される.
$ E(F_q) \simeq Z/m_1Z \times \cdots \times Z/m_sZ \ (m_i|m_{i+1})
したがって,$ m_1等分点の数は$ m_1^s個ある.しかし一方で楕円曲線の$ m_1等分点は高々$ m_1^2しかないので,s=2となるしかない.さらにたとえばヴァイユペアリングの性質を使うと$ m_1|q-1も証明できる.
なお楕円曲線暗号では, E(Fq) が素数位数の巡回群になる (つまり E(Fq) ≃ C1) となるような楕円曲線を使用することが多いです.
ウィンドウ法:m進展開をして,m個の点をあらかじめ計算しておき,ハッシュテーブル的に利用
符号付き2進展開法
NAFにおいて$ \pm 1がなぜ連続して現れないのか? 要証明 2章は離散対数問題の解法アルゴリズムなので省略
ECDSA署名
Alice が Bob に署名を送 ることで, Bob はメッセージ m の内容が改竄されていないことを検証できる.
よりもメッセージに対する署名をデータとして渡せる
つまり,(離散対数問題が効率的に解かれていなければ)メッセージmと秘密鍵dによってのみ作成できる検証可能なデータが作れる
P: 素体$ F_p状の楕円曲線状のベースポイント,$ l: Pの点位数
$ d_A: アリスの秘密鍵,$ P = d_A * P: アリスの公開鍵
アリスによる署名作成
r: 乱数,$ U = r*P = (x_U, y_U),m: メッセージ,H(m): メッセージのハッシュ値
$ u= x_Umod $ l, $ v = (H(m) + u\times d_A)/ r mod$ l
Bobに署名(u.v)を送る
ボブによる署名検証
$ d = 1/v mod$ l, $ V = d \times H(m) * P + d \times u * P_A = (x_V, y_V)
$ u = x_V mod $ lなら検証成功
式展開
$ d = \frac{1}{v} = \frac{r}{H(m) + u \times d_A}
$ V = d \times H(m) * P + d \times u * P_A = \frac{r \times H(m) * P + r\times u * P_A}{H(m) + u \times d_A} = \frac{H(m) * U + r\times u \times d_A * P}{H(m) + u \times d_A}
$ = \frac{H(m) * U + u \times d_A * U}{H(m) + u \times d_A} = \frac{(H(m) + u \times d_A) * U}{H(m) + u \times d_A} = U
よって $ u = x_U = x_Vとなる
これ,楕円曲線上のスカラー倍と数の積がごっちゃになってるかも要確認 パラメータ生成方法は第2章理解した後で
Schnorr署名
M: メッセージ
$ (r, K): 鍵ペア $ K = rG
署名者 $ (M, r) \rightarrow Pair:(e, s) = \sigma
$ Q = aG, a: nonce
$ e = H(M||Q) H: keccakハッシュ関数, ||: 文字列の結合
$ s = a - er
検証者 $ (M, K, \sigma) \rightarrow Bool
$ Q' = sG + eK
$ if (e == e':= H(M||Q')) \iff if (Q == Q')
証明
$ Q' = sG + eK
$ = (a-er)G + erG
$ = aG - erG + erG
$ = aG = Q
公開鍵リスト $ R = <K_0, K_1, \ldots , K_\pi, \ldots, K_n>
署名者の鍵ペア $ (r_\pi, K_\pi) $ K_\pi = r_\piG
メッセージ M
署名者 Rに対して$ r_\piで署名
検証者 Rのうちのどれかに対応した秘密鍵で署名されたことを検証 (どれに対応するのかはわからない)
リングの大きさ = 3の場合
署名者の鍵ペア $ (r_1, K_1) ($ \pi =1)
署名者 $ (M, r_\pi, R) \rightarrow \sigma := (e_0, s_0, s_1, s_2)
$ u: nonce
$ e_2 = H(M||uG) $ (2 = \pi+1)
*$ s_2: nonce
*$ e_0 = H(M||s_2G + e_2K_2)
*$ s_0: nonce
$ e_1 = H(M||s_0G + e_0K_0)
*$ s_1 = u-e_1r_1
検証者 $ (R, M, \sigma) \rightarrow Bool
$ e_1 := H(M||s_0G + e_0K_0)
$ e_2' := H(M||s_1G + e_1K_1)
$ e_0' := H(M||s_2G + e_2'K_0)
$ if (e_0 == e_0') \iff if(e_2 == e_2') \iff if(uG == s_1G + e_1K_1)
証明
( 右辺 )$ = s_1G+e_1K_1
$ = (u-e_1r_1)G + e_1(r_1K_1)
$ = uG - e_1r_1G + e_1r_1G
$ = uG
一般で解釈
$ s: ほとんどnonce
$ e_m = H(M||s_{m-1}G+e_{m-1}K)
$ s_\piでずれる $ \iff e_{\pi+1}でずれる
ずれたところが対応した鍵ペアとなるが,検証者はそれはわからない
追加
$ \infinはy軸と平行な直線が共通の点で交わると考え、その点を仮想的に$ \infinとかく。
楕円曲線上の加算はアーベル群(可換群)
演算について閉じている 上で示したOK
単位元の存在 定義上$ \infinという仮想点が単位元
逆元の存在 x軸対称点が逆元
交換法則 定義上自明
結合法則
代数 交叉理論を使うと綺麗に示せるかも
(有限体上は)数式処理システムでゴリゴリやればいける