椭圆曲线的点群、子群和阶

群，子群和椭圆曲线的阶

我能从一条椭圆曲线中得到两个点群吗？嗯，对于一条设计良好的椭圆曲线，如果我选择曲线上一个基点，我会得到一个点群，如果我选择另一个基点，我会得到另一个点群。

我知道用于椭圆曲线密码学（ECC）的离散对数问题可以被 Shor 算法破解。但是，在我们的传统计算方法面前，经过二十多年的尝试破解，它仍然像以往一样强大。对我来说，ECC 很美妙，而 Twisted Edwards 曲线最美的结构之一是：

By Krishnavedala — Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=15285390

由于阶定义了可能的点的数量，这将定义我们所使用的曲线的安全性。如果我们的阶是 256，那么曲线的安全性将是 8 比特。

找到点

在使用（mod p）的椭圆曲线中，并非所有点都是可能的。为此，我们定义曲线的阶（n），它等于可能的点的数量。在这种情况下，我们将使用 Baby Jubjub 曲线，它使用 Twisted Edwards 曲线：

a. x ²+ y ²=1+ d. x ². y ²

其中 a =168,700 并且 d =168,696。为此，你应该选择一个起始 y 轴点，然后此程序将确定对于此 y 值是否存在有效的（x，y）点。我们应该能够看到并非每个点都是可能的，如果我们投入整个范围，我们会发现有效点的数量是 n[ 这里]：

package main

import (
    "fmt"
    "github.com/iden3/go-iden3-crypto/v2/babyjub"
    "math/big"
    "strconv"
    "os"

)

func main() {

    start:=0
    points:=10

    valid_points:=0

    argCount := len(os.Args[1:])

    if argCount > 0 {
        start,_ = strconv.Atoi(os.Args[1])
    }

    if argCount > 1 {
        points,_ = strconv.Atoi(os.Args[2])
    }

    if (points>50) {
        fmt.Printf("Too many points") // 点数过多
        return
    }

    end:=start+points

    y:=big.NewInt(int64(start))

    for i:=start;i<end;i++ {
        y = y.Add(y,big.NewInt(1))

        P,err:= babyjub.PointFromSignAndY(true,y)

        if (err==nil) {

            fmt.Printf("P Point (%s, %s)\n",P.X.String(),P.Y.String())
            valid_points=valid_points+1
        } else {
            fmt.Printf(" No point at y=%d. Error: %v\n", y,err) // 在 y=%d 处没有点。 错误：%v
        }

    }
    fmt.Printf("\nNumber of valid points: %d\n", valid_points) // 有效点数：%d

}

如果我们从 y =0 开始，我们会得到 [ 这里]：

P Point (18930368022820495955728484915491405972470733850014661777449844430438130630919, 0)
P Point (0, 1)
 No point at y=2. Error: x is not a square mod q  // 在 y=2 处没有点。 错误：x 不是 q 的平方模
P Point (12576558175125128246374296641007938322302911659474853157208587689687229831284, 3)
 No point at y=4. Error: x is not a square mod q // 在 y=4 处没有点。 错误：x 不是 q 的平方模
P Point (18869612826929474874643025262839512853875949931275176402223244870011103237908, 5)
 No point at y=6. Error: x is not a square mod q // 在 y=6 处没有点。 错误：x 不是 q 的平方模
P Point (13552511770995215854247011058222321713336597779070880882063415558668852854304, 7)
 No point at y=8. Error: x is not a square mod q // 在 y=8 处没有点。 错误：x 不是 q 的平方模
P Point (21832387548399618524654259550049888664079925088284364012476905620075906709633, 9)
 No point at y=10. Error: x is not a square mod q // 在 y=10 处没有点。 错误：x 不是 q 的平方模
 No point at y=11. Error: x is not a square mod q // 在 y=11 处没有点。 错误：x 不是 q 的平方模
P Point (20700028309656759080031942785057991999284636687631686688510770226861229369633, 12)
P Point (19763400273586758549882294695966112539108188722254631372974345487113325868230, 13)
 No point at y=14. Error: x is not a square mod q // 在 y=14 处没有点。 错误：x 不是 q 的平方模
 No point at y=15. Error: x is not a square mod q // 在 y=15 处没有点。 错误：x 不是 q 的平方模
P Point (15748337355548863464573462419217453654716274042001512547627587014880279733734, 16)
 No point at y=17. Error: x is not a square mod q // 在 y=17 处没有点。 错误：x 不是 q 的平方模
 No point at y=18. Error: x is not a square mod q // 在 y=18 处没有点。 错误：x 不是 q 的平方模
 No point at y=19. Error: x is not a square mod q // 在 y=19 处没有点。 错误：x 不是 q 的平方模
P Point (12885783778712725087112153787120726436432163732495266492799399218038199472891, 20)
 No point at y=21. Error: x is not a square mod q // 在 y=21 处没有点。 错误：x 不是 q 的平方模
 No point at y=22. Error: x is not a square mod q // 在 y=22 处没有点。 错误：x 不是 q 的平方模
P Point (16299723954774684209268815758404022127334551363443293523975044728264168417401, 23)
P Point (18071280701900071808027146573140633253438909650212067123562327773539929264713, 24)
P Point (16559579109203325663861520886565339001072125920805205920565984160921043146134, 25)
P Point (19239793330815039927176551878568151477607084724089260965429607203123487397925, 26)
P Point (18916323097528214550190828516685481300272936250205860869273475329114600242787, 27)
P Point (16057035405780878121212855035139245734114126576386437295288500975032244938760, 28)
P Point (13992374993914214579575201281844112773720693717070684339221259981788339098074, 29)
 No point at y=30. Error: x is not a square mod q  // 在 y=30 处没有点。 错误：x 不是 q 的平方模
P Point (16254272338426510215042424859693243274925862877313168958028271352072227906985, 31)
P Point (15352575468909817215543364638732708113777501617606490688061718284764591286166, 32)
P Point (18952366491620607375015834639126503796299078485847531297503893890767000557200, 33)
 No point at y=34. Error: x is not a square mod q  // 在 y=34 处没有点。 错误：x 不是 q 的平方模
 No point at y=35. Error: x is not a square mod q  // 在 y=35 处没有点。 错误：x 不是 q 的平方模
P Point (15210086647189413171207504583018919291853676733289618730398235358169928471169, 36)
 No point at y=37. Error: x is not a square mod q  // 在 y=37 处没有点。 错误：x 不是 q 的平方模
 No point at y=38. Error: x is not a square mod q  // 在 y=38 处没有点。 错误：x 不是 q 的平方模
P Point (12790678898297491670394418391098069117938733212782394815001098217425267277359, 39)

Number of valid points: 22 // 有效点数：22

我们看到在 40 个点中有 22 个有效点。在（0,1）处的点被称为单位元。总的来说，如果我们继续计数，我们会确定有 21888242871839275222246405745257275088614511777268538073601725287587578984328 个有效点。这为我们提供了大约 254 比特的安全性。

那么我们如何访问所有有效点呢？好吧，为此，我们选择一个生成器值，它将使我们能够访问子群中的每个点。对于 Baby Jubjub，生成器点（G）是：

 x_g,_ := new(big.Int).SetString("995203441582195749578291179787384436505546430278305826713579947235728471134",10 )
 y_g,_ := new(big.Int).SetString("5472060717959818805561601436314318772137091100104008585924551046643952123905",10)

此生成器点将使我们能够访问 n 个点：

G, 2G, 3G … (n)G.

如果我们使用这个程序，我们将得到前 16 个：

package main

import (
 "fmt"
 "github.com/iden3/go-iden3-crypto/v2/babyjub"
 "math/big"

)

func main() {

 x_g,_ := new(big.Int).SetString("995203441582195749578291179787384436505546430278305826713579947235728471134",10 )
 y_g,_ := new(big.Int).SetString("5472060717959818805561601436314318772137091100104008585924551046643952123905",10)

 x_b,_ := new(big.Int).SetString("5299619240641551281634865583518297030282874472190772894086521144482721001553",10 )
 y_b,_ := new(big.Int).SetString("16950150798460657717958625567821834550301663161624707787222815936182638968203",10)

 G := &babyjub.Point{X: x_g, Y: y_g}
 B := &babyjub.Point{X: x_b, Y: y_b}

 fmt.Printf("G (%s, %s)\n",G.X.String(),G.Y.String())
 fmt.Printf("B (%s, %s)\n",B.X.String(),B.Y.String())

 for i:=0;i<16;i++ {
  s:=new(big.Int).SetInt64(int64(i))
  sG := babyjub.NewPoint().Mul(s, G)

  fmt.Printf("(%s).G Point (%s, %s)\n",s.String(),sG.X.String(),sG.Y.String())

 }

}

结果是:

G (995203441582195749578291179787384436505546430278305826713579947235728471134, 5472060717959818805561601436314318772137091100104008585924551046643952123905)
B (5299619240641551281634865583518297030282874472190772894086521144482721001553, 16950150798460657717958625567821834550301663161624707787222815936182638968203)

(0).G Point (0, 1)
(1).G Point (995203441582195749578291179787384436505546430278305826713579947235728471134, 5472060717959818805561601436314318772137091100104008585924551046643952123905)
(2).G Point (1676417244152142056454616115823988517566305896059373631785843290555309632953, 11563908930482997415800970727888501192209530935490958274440594569809848042842)
(3).G Point (7097975954760038507620802111344412063519509458421529194055316108847963502077, 20460065127209391267340990691555311927812546314818552928162547469063110481889)
(4).G Point (11940103558519948654707819768822978214526419610986575349872581173462370334209, 16133537043833109864904997878990023239769440361381525375236540405234196921159)
(5).G Point (6596525632027871303917340722484633386471481257783514271586100162990006259443, 2401314402411604810048797209571032759642296996510148205741885142964302854310)
(6).G Point (7858363331252785333490649116238209123171552717097571400552495106666244250382, 16060263446859325087364714122290348893867851455223446357551439979039963525393)
(7).G Point (6512601452299603416622270706270885416756227315987058185406313722742707189941, 1671809120602383274197644355756654760992995477255686896534411762289051708357)
(8).G Point (5299619240641551281634865583518297030282874472190772894086521144482721001553, 16950150798460657717958625567821834550301663161624707787222815936182638968203)
(9).G Point (14805543388578810117460687107379140748822348273316260688573060998934016770136, 13589798946988221969763682225123791336245855044059976312385135587934609470572)
(10).G Point (7527094730269662911877883566715218406070212284970737093711359320128673855732, 15059929179582363986985620109926997886787716284051647376602607978411750252415)
(11).G Point (10824658094301123372100575511793302704254845342209561012292883196698875972962, 1813325013087464583678493200260128285825318076247231789833266423468527250766)
(12).G Point (3600894317465611590823497143274368665002726726859963684033119097945650894582, 18692248084533880904541331028020360764470554554954147910164365744311729096438)
(13).G Point (15255704706666363154761644163850713004133053552231826906104025767490433417034, 14943481887252643221839631022513881220288808450216563280348242277363819134145)
(14).G Point (14416521790304421324082593824069419528382948527025438930053329044922391819161, 2640539198602143979842395862503255766518403467149574503008973201966889687153)
(15).G Point (12012258259621508927176356144574867271437016873848478571462447321096148382284, 7679300193588055143652649676292857030268804168447451110920212173180664295168)

然而，基点(B) 将使我们能够访问阶 l=2736030358979909402780800718157159386076813972158567259200215660948447373041 的点的子群：

 x_b,_ := new(big.Int).SetString("5299619240641551281634865583518297030282874472190772894086521144482721001553",10 )
 y_b,_ := new(big.Int).SetString("16950150798460657717958625567821834550301663161624707787222815936182638968203",10)

此基点将使我们能够访问 l 个点的子群：

B, 2G, 3G … (l)B.

然后我们可以使用这个程序来确定组中的前16个标量点：

package main

import (
 "fmt"
 "github.com/iden3/go-iden3-crypto/v2/babyjub"
 "math/big"

)

func main() {

 x_g,_ := new(big.Int).SetString("995203441582195749578291179787384436505546430278305826713579947235728471134",10 )
 y_g,_ := new(big.Int).SetString("5472060717959818805561601436314318772137091100104008585924551046643952123905",10)

 x_b,_ := new(big.Int).SetString("5299619240641551281634865583518297030282874472190772894086521144482721001553",10 )
 y_b,_ := new(big.Int).SetString("16950150798460657717958625567821834550301663161624707787222815936182638968203",10)

 G := &babyjub.Point{X: x_g, Y: y_g}
 B := &babyjub.Point{X: x_b, Y: y_b}

 fmt.Printf("G (%s, %s)\n",G.X.String(),G.Y.String())
 fmt.Printf("B (%s, %s)\n\n",B.X.String(),B.Y.String())

 for i:=0;i<16;i++ {
  s:=new(big.Int).SetInt64(int64(i))
  sB := babyjub.NewPoint().Mul(s, B)

  fmt.Printf("(%d).B

>- 原文链接： [billatnapier.medium.com/...](https://billatnapier.medium.com/groups-subgroups-and-orders-of-an-elliptic-curve-308d63b1828c)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～