Pebble Coding

ソフトウェアエンジニアによるIT関連技術や数学の備忘録

楕円曲線における離散対数問題

例として、
 F_{43}
 y^{2} = x^{3} + 7
を考えます。
有理点の数(群位数)は31で素数です。
点の加法群の位数が31ということは部分群が存在せず、巡回群つまり一つの元を足し合わせることで全ての元が表現できるということです。
全ての点が位数31となります。
ちなみに、無限遠点O以外の30個の点(x, y)を図にしたものがこちらです。
f:id:pebble8888:20190103191502p:plain

P1:(2,12)
P2:(2,31)
P3:(7,7)
P4:(7,36)
P5:(12,12)
P6:(12,31)
P7:(13,21)
P8:(13,22)
P9:(20,3)
P10:(20,40)
P11:(21,18)
P12:(21,25)
P13:(25,18)
P14:(25,25)
P15:(29,12)
P16:(29,31)
P17:(32,3)
P18:(32,40)
P19:(34,3)
P20:(34,40)
P21:(35,21)
P22:(35,22)
P23:(37,7)
P24:(37,36)
P25:(38,21)
P26:(38,22)
P27:(40,18)
P28:(40,25)
P29:(42,7)
P30:(42,36)
O

まず、どれでもよいので基準の点をO以外から選びます。これをベースポイントと呼びます。
ここでは、P13:(25, 18)を選びます。
この点を点の加算公式を用いて整数倍していった結果がこちらです。

P13:(25,18)
2*P13:(34,40) = P20
3*P13:(42,36) = P30
4*P13:(35,22) = P22
5*P13:(21,18) = P11
6*P13:(40,25) = P28
7*P13:(13,22) = P8
8*P13:(29,12) = P15
9*P13:(2,12) = P1
10*P13:(32,40) = P18
11*P13:(38,21) = P25
12*P13:(20,3) = P9
13*P13:(7,36) = P4
14*P13:(12,12) = P5
15*P13:(37,36) = P24
16*P13:(37,7) = P23
17*P13:(12,31) = P6
18*P13:(7,7) = P3
19*P13:(20,40) = P10
20*P13:(38,22) = P26
21*P13:(32,3) = P17
22*P13:(2,31) = P2
23*P13:(29,31) = P16
24*P13:(13,21) = P7
25*P13:(40,18) = P27
26*P13:(21,25) = P12
27*P13:(35,21) = P21
28*P13:(42,7) = P29
29*P13:(34,3) = P19
30*P13:(25,25) = P14
31*P13:O

右辺の点は全て重複がありません。
整数を使った離散対数問題と同じように、
 n \times P = Q
としたとき、Qの点を与えたときにnの値を求めるのは時間的に困難となります。
これが楕円曲線における離散対数問題です。
同じ楕円曲線  y^{2} = x^{3} + 7 を用いて F_{2^{256} - 2^{32} - 977}
ベースポイント
(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)
としたのがsecp256k1の楕円曲線です。
群位数は 115792089237316195423570985008687907852837564279074904382605163141518161494337
で素数です。

プライバシーポリシー

お問い合わせ

スポンサーリンク