Pebble Coding

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

secp256k1のベースポイントの謎

secp256k1

secp256k1のベースポイントの性質をみていきます。
有理点(x, y)はおよそ256ビットの範囲内で均等に値がばらけていると考えられます。
ベースポイントGの倍数 を計算したときのx, yの値はおよそ256ビットの値がランダムに並んだようになりますが、たまたま端っこによった場合は、
0にすごく近かったり、群の位数に近かったりしますが、確率としては低いです。

sage: E = EllipticCurve(GF(2 ** 256 - 2 ** 32 - 977), [0, 7])
sage: G = E([55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424])
sage: Integer(E.cardinality()).hex()
'fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141'
sage: Integer(G[0]).hex()
'79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798'
sage: Integer(G[1]).hex()
'483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8'

cardinality(群の位数)の先頭にffが続いているのはコンピュータ計算を高速に行うために2のべきから近い値にするためであり当然の結果です。

Gの倍数をSageMathで少し計算してみます。

sage: Integer((2 * G)[0]).hex()
'c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5'
sage: Integer((2 * G)[1]).hex()
'1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a'
sage: Integer((3 * G)[0]).hex()
'f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9'
sage: Integer((3 * G)[1]).hex()
'388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672'

特におかしなところはないですね。 次に以下を試してみましょう。

G * Integer((E.cardinality()+1)/2)
(86918276961810349294276103416548851884759982251107 : 87194829221142880348582938487511785107150118762739500766654458540580527283772 : 1)
Integer((G * Integer((E.cardinality()+1)/2))[0]).hex()
'3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63'

nを群位数(奇数)として G * (n+1)/2 の点のxの値が凄く小さいです。
これは16進数で書くと'00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63'
であり、取りうる範囲に対して0に凄く近いです。

また、この点Pは 2P = G の関係を満たすことが以下の計算で確認できます。

sage: P = G * Integer((E.cardinality()+1)/2)
sage: P
(86918276961810349294276103416548851884759982251107 : 87194829221142880348582938487511785107150118762739500766654458540580527283772 : 1)
sage: 2 * P
(55066263022277343669578718895168534326250603453777594175500187360389116729240 : 32670510020758816978083085130507043184471273380659243275938904335757337482424 : 1)
sage: G
(55066263022277343669578718895168534326250603453777594175500187360389116729240 : 32670510020758816978083085130507043184471273380659243275938904335757337482424 : 1)

なぜこのようなことがおきるかというとベースポイントGは166bitに相当する文字列のx値の点を2倍して定められたからです。
secp256k1だけでなく、secp224k1も同じようにベースポイントが定められたようです。

試しに、Gを倍にしてxの値が200bit以下のものを見つけようとしてみましたが、簡単には見つかりません。
これにより、Pのxの値が0に近いのが特別なことであることがわかります。

E = EllipticCurve(GF(2 ** 256 - 2 ** 32 - 977), [0, 7])
G = E([55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424])
i = 1
t = 2 ** 200
while True:
    P = i * G
    if Integer(P[0]) < t:
        print i, P
        break
    if i % 1000 == 0:
        print i
    i = i + 1

参考: The most repeated R value on the blockchain

この記事は別の以下の論文を読んでいて発見しました。

https://eprint.iacr.org/2019/023.pdf

ECDSAのnonceの値がフルランダム(256ビットの精度)でない場合は、ある攻撃方法によってECDSAが破られるよという内容です。
160bit以下のランダムネスだと危ないよということらしいです。
なぜそんな実装になるのか謎すぎますが、このような脆弱性指摘論文はなかなか面白く、暗号分野の研究が活発で健全だなあという印象です。