twist.go 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205
  1. package bn256
  2. import (
  3. "math/big"
  4. )
  5. // twistPoint implements the elliptic curve y²=x³+3/ξ over GF(p²). Points are
  6. // kept in Jacobian form and t=z² when valid. The group G₂ is the set of
  7. // n-torsion points of this curve over GF(p²) (where n = Order)
  8. type twistPoint struct {
  9. x, y, z, t gfP2
  10. }
  11. var twistB = &gfP2{
  12. gfP{0x38e7ecccd1dcff67, 0x65f0b37d93ce0d3e, 0xd749d0dd22ac00aa, 0x0141b9ce4a688d4d},
  13. gfP{0x3bf938e377b802a8, 0x020b1b273633535d, 0x26b7edf049755260, 0x2514c6324384a86d},
  14. }
  15. // twistGen is the generator of group G₂.
  16. var twistGen = &twistPoint{
  17. gfP2{
  18. gfP{0xafb4737da84c6140, 0x6043dd5a5802d8c4, 0x09e950fc52a02f86, 0x14fef0833aea7b6b},
  19. gfP{0x8e83b5d102bc2026, 0xdceb1935497b0172, 0xfbb8264797811adf, 0x19573841af96503b},
  20. },
  21. gfP2{
  22. gfP{0x64095b56c71856ee, 0xdc57f922327d3cbb, 0x55f935be33351076, 0x0da4a0e693fd6482},
  23. gfP{0x619dfa9d886be9f6, 0xfe7fd297f59e9b78, 0xff9e1a62231b7dfe, 0x28fd7eebae9e4206},
  24. },
  25. gfP2{*newGFp(0), *newGFp(1)},
  26. gfP2{*newGFp(0), *newGFp(1)},
  27. }
  28. func (c *twistPoint) String() string {
  29. c.MakeAffine()
  30. x, y := gfP2Decode(&c.x), gfP2Decode(&c.y)
  31. return "(" + x.String() + ", " + y.String() + ")"
  32. }
  33. func (c *twistPoint) Set(a *twistPoint) {
  34. c.x.Set(&a.x)
  35. c.y.Set(&a.y)
  36. c.z.Set(&a.z)
  37. c.t.Set(&a.t)
  38. }
  39. // IsOnCurve returns true iff c is on the curve.
  40. func (c *twistPoint) IsOnCurve() bool {
  41. c.MakeAffine()
  42. if c.IsInfinity() {
  43. return true
  44. }
  45. y2, x3 := &gfP2{}, &gfP2{}
  46. y2.Square(&c.y)
  47. x3.Square(&c.x).Mul(x3, &c.x).Add(x3, twistB)
  48. if *y2 != *x3 {
  49. return false
  50. }
  51. cneg := &twistPoint{}
  52. cneg.Mul(c, Order)
  53. return cneg.z.IsZero()
  54. }
  55. func (c *twistPoint) SetInfinity() {
  56. c.x.SetZero()
  57. c.y.SetOne()
  58. c.z.SetZero()
  59. c.t.SetZero()
  60. }
  61. func (c *twistPoint) IsInfinity() bool {
  62. return c.z.IsZero()
  63. }
  64. func (c *twistPoint) Add(a, b *twistPoint) {
  65. // For additional comments, see the same function in curve.go.
  66. if a.IsInfinity() {
  67. c.Set(b)
  68. return
  69. }
  70. if b.IsInfinity() {
  71. c.Set(a)
  72. return
  73. }
  74. // See http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/addition/add-2007-bl.op3
  75. z12 := (&gfP2{}).Square(&a.z)
  76. z22 := (&gfP2{}).Square(&b.z)
  77. u1 := (&gfP2{}).Mul(&a.x, z22)
  78. u2 := (&gfP2{}).Mul(&b.x, z12)
  79. t := (&gfP2{}).Mul(&b.z, z22)
  80. s1 := (&gfP2{}).Mul(&a.y, t)
  81. t.Mul(&a.z, z12)
  82. s2 := (&gfP2{}).Mul(&b.y, t)
  83. h := (&gfP2{}).Sub(u2, u1)
  84. xEqual := h.IsZero()
  85. t.Add(h, h)
  86. i := (&gfP2{}).Square(t)
  87. j := (&gfP2{}).Mul(h, i)
  88. t.Sub(s2, s1)
  89. yEqual := t.IsZero()
  90. if xEqual && yEqual {
  91. c.Double(a)
  92. return
  93. }
  94. r := (&gfP2{}).Add(t, t)
  95. v := (&gfP2{}).Mul(u1, i)
  96. t4 := (&gfP2{}).Square(r)
  97. t.Add(v, v)
  98. t6 := (&gfP2{}).Sub(t4, j)
  99. c.x.Sub(t6, t)
  100. t.Sub(v, &c.x) // t7
  101. t4.Mul(s1, j) // t8
  102. t6.Add(t4, t4) // t9
  103. t4.Mul(r, t) // t10
  104. c.y.Sub(t4, t6)
  105. t.Add(&a.z, &b.z) // t11
  106. t4.Square(t) // t12
  107. t.Sub(t4, z12) // t13
  108. t4.Sub(t, z22) // t14
  109. c.z.Mul(t4, h)
  110. }
  111. func (c *twistPoint) Double(a *twistPoint) {
  112. // See http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/doubling/dbl-2009-l.op3
  113. A := (&gfP2{}).Square(&a.x)
  114. B := (&gfP2{}).Square(&a.y)
  115. C := (&gfP2{}).Square(B)
  116. t := (&gfP2{}).Add(&a.x, B)
  117. t2 := (&gfP2{}).Square(t)
  118. t.Sub(t2, A)
  119. t2.Sub(t, C)
  120. d := (&gfP2{}).Add(t2, t2)
  121. t.Add(A, A)
  122. e := (&gfP2{}).Add(t, A)
  123. f := (&gfP2{}).Square(e)
  124. t.Add(d, d)
  125. c.x.Sub(f, t)
  126. t.Add(C, C)
  127. t2.Add(t, t)
  128. t.Add(t2, t2)
  129. c.y.Sub(d, &c.x)
  130. t2.Mul(e, &c.y)
  131. c.y.Sub(t2, t)
  132. t.Mul(&a.y, &a.z)
  133. c.z.Add(t, t)
  134. }
  135. func (c *twistPoint) Mul(a *twistPoint, scalar *big.Int) {
  136. sum, t := &twistPoint{}, &twistPoint{}
  137. for i := scalar.BitLen(); i >= 0; i-- {
  138. t.Double(sum)
  139. if scalar.Bit(i) != 0 {
  140. sum.Add(t, a)
  141. } else {
  142. sum.Set(t)
  143. }
  144. }
  145. c.Set(sum)
  146. }
  147. func (c *twistPoint) MakeAffine() {
  148. if c.z.IsOne() {
  149. return
  150. } else if c.z.IsZero() {
  151. c.x.SetZero()
  152. c.y.SetOne()
  153. c.t.SetZero()
  154. return
  155. }
  156. zInv := (&gfP2{}).Invert(&c.z)
  157. t := (&gfP2{}).Mul(&c.y, zInv)
  158. zInv2 := (&gfP2{}).Square(zInv)
  159. c.y.Mul(t, zInv2)
  160. t.Mul(&c.x, zInv2)
  161. c.x.Set(t)
  162. c.z.SetOne()
  163. c.t.SetOne()
  164. }
  165. func (c *twistPoint) Neg(a *twistPoint) {
  166. c.x.Set(&a.x)
  167. c.y.Neg(&a.y)
  168. c.z.Set(&a.z)
  169. c.t.SetZero()
  170. }