Pebble Coding

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

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

例として、
 F_{43}
 y^{2} = x^{3} + 7
を考えます。
 F_{43}というのは数として、43で割った余り、つまり、0,1,2,3,...,42 だけの世界を考えるということです。
x, y の値として0,1,2,3,...,42だけを考えます。
42よりも大きな値は43で割った余りと同一の値であるとみなします。
すると y^{2} = x^{3} + 7の式を満たすx, yの値は有限個に限られます。
例えば、 12^{2} = 144 = 43 * 3 + 15 = 15
 2^{3} + 7 = 9 + 7 = 15
なので(x, y) = (2, 12)は上の式を満たします。
上の式を満たす点(x, y)のことを有理点と呼びます。

上の式を満たす点の数は下に示すように31個あります。
これらの点に対して加法を定義することができます。
点Pと点Qを加えて点Rとなる(P+Q=R)時、点P,Q,Rは全てこの式を満たします。
この加法は群をなします。

有理点の数(群位数)は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
で素数です。

DLPとECDLPはどのくらい安全なのか

離散対数問題(DLP)および楕円曲線上の離散対数問題(ECDLP)は安全性を保つため、常時問題が出されています。
Wikipediaに現在の記録が載っています。

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

WikipediaにDLP(Discrete Logarithm Problem)とECDLP(Discrete Logarithm Problem)の2019年でのレコードが載っていたので見てみる。

DLP:有限群 GF(2^{30750}), 2019年7月。
DLP:素数でのmoduloで素数が768bit, 2016年6月。 ECDLP:117bit, FPGA, ポラードのロー法, 計算時間6ヶ月, 2016年2月。

DLPは2種類のっていますが、素数でのmodulo演算の場合は768bitです。
ECDLPは117bitです。
secp256k1は256bitありますので、少なくともあと20年くらいは大丈夫かなという気がします。
256bitが破られるとしたら、量子コンピューターによるものではなく、
新たな数学アルゴリズムによるものではないかという気がします。

プライバシーポリシー

お問い合わせ

スポンサーリンク