curve.go 4.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239
  1. package bn256
  2. import (
  3. "math/big"
  4. )
  5. // curvePoint implements the elliptic curve y²=x³+3. Points are kept in Jacobian
  6. // form and t=z² when valid. G₁ is the set of points of this curve on GF(p).
  7. type curvePoint struct {
  8. x, y, z, t gfP
  9. }
  10. var curveB = newGFp(3)
  11. // curveGen is the generator of G₁.
  12. var curveGen = &curvePoint{
  13. x: *newGFp(1),
  14. y: *newGFp(2),
  15. z: *newGFp(1),
  16. t: *newGFp(1),
  17. }
  18. func (c *curvePoint) String() string {
  19. c.MakeAffine()
  20. x, y := &gfP{}, &gfP{}
  21. montDecode(x, &c.x)
  22. montDecode(y, &c.y)
  23. return "(" + x.String() + ", " + y.String() + ")"
  24. }
  25. func (c *curvePoint) Set(a *curvePoint) {
  26. c.x.Set(&a.x)
  27. c.y.Set(&a.y)
  28. c.z.Set(&a.z)
  29. c.t.Set(&a.t)
  30. }
  31. // IsOnCurve returns true iff c is on the curve.
  32. func (c *curvePoint) IsOnCurve() bool {
  33. c.MakeAffine()
  34. if c.IsInfinity() {
  35. return true
  36. }
  37. y2, x3 := &gfP{}, &gfP{}
  38. gfpMul(y2, &c.y, &c.y)
  39. gfpMul(x3, &c.x, &c.x)
  40. gfpMul(x3, x3, &c.x)
  41. gfpAdd(x3, x3, curveB)
  42. return *y2 == *x3
  43. }
  44. func (c *curvePoint) SetInfinity() {
  45. c.x = gfP{0}
  46. c.y = *newGFp(1)
  47. c.z = gfP{0}
  48. c.t = gfP{0}
  49. }
  50. func (c *curvePoint) IsInfinity() bool {
  51. return c.z == gfP{0}
  52. }
  53. func (c *curvePoint) Add(a, b *curvePoint) {
  54. if a.IsInfinity() {
  55. c.Set(b)
  56. return
  57. }
  58. if b.IsInfinity() {
  59. c.Set(a)
  60. return
  61. }
  62. // See http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/addition/add-2007-bl.op3
  63. // Normalize the points by replacing a = [x1:y1:z1] and b = [x2:y2:z2]
  64. // by [u1:s1:z1·z2] and [u2:s2:z1·z2]
  65. // where u1 = x1·z2², s1 = y1·z2³ and u1 = x2·z1², s2 = y2·z1³
  66. z12, z22 := &gfP{}, &gfP{}
  67. gfpMul(z12, &a.z, &a.z)
  68. gfpMul(z22, &b.z, &b.z)
  69. u1, u2 := &gfP{}, &gfP{}
  70. gfpMul(u1, &a.x, z22)
  71. gfpMul(u2, &b.x, z12)
  72. t, s1 := &gfP{}, &gfP{}
  73. gfpMul(t, &b.z, z22)
  74. gfpMul(s1, &a.y, t)
  75. s2 := &gfP{}
  76. gfpMul(t, &a.z, z12)
  77. gfpMul(s2, &b.y, t)
  78. // Compute x = (2h)²(s²-u1-u2)
  79. // where s = (s2-s1)/(u2-u1) is the slope of the line through
  80. // (u1,s1) and (u2,s2). The extra factor 2h = 2(u2-u1) comes from the value of z below.
  81. // This is also:
  82. // 4(s2-s1)² - 4h²(u1+u2) = 4(s2-s1)² - 4h³ - 4h²(2u1)
  83. // = r² - j - 2v
  84. // with the notations below.
  85. h := &gfP{}
  86. gfpSub(h, u2, u1)
  87. xEqual := *h == gfP{0}
  88. gfpAdd(t, h, h)
  89. // i = 4h²
  90. i := &gfP{}
  91. gfpMul(i, t, t)
  92. // j = 4h³
  93. j := &gfP{}
  94. gfpMul(j, h, i)
  95. gfpSub(t, s2, s1)
  96. yEqual := *t == gfP{0}
  97. if xEqual && yEqual {
  98. c.Double(a)
  99. return
  100. }
  101. r := &gfP{}
  102. gfpAdd(r, t, t)
  103. v := &gfP{}
  104. gfpMul(v, u1, i)
  105. // t4 = 4(s2-s1)²
  106. t4, t6 := &gfP{}, &gfP{}
  107. gfpMul(t4, r, r)
  108. gfpAdd(t, v, v)
  109. gfpSub(t6, t4, j)
  110. gfpSub(&c.x, t6, t)
  111. // Set y = -(2h)³(s1 + s*(x/4h²-u1))
  112. // This is also
  113. // y = - 2·s1·j - (s2-s1)(2x - 2i·u1) = r(v-x) - 2·s1·j
  114. gfpSub(t, v, &c.x) // t7
  115. gfpMul(t4, s1, j) // t8
  116. gfpAdd(t6, t4, t4) // t9
  117. gfpMul(t4, r, t) // t10
  118. gfpSub(&c.y, t4, t6)
  119. // Set z = 2(u2-u1)·z1·z2 = 2h·z1·z2
  120. gfpAdd(t, &a.z, &b.z) // t11
  121. gfpMul(t4, t, t) // t12
  122. gfpSub(t, t4, z12) // t13
  123. gfpSub(t4, t, z22) // t14
  124. gfpMul(&c.z, t4, h)
  125. }
  126. func (c *curvePoint) Double(a *curvePoint) {
  127. // See http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/doubling/dbl-2009-l.op3
  128. A, B, C := &gfP{}, &gfP{}, &gfP{}
  129. gfpMul(A, &a.x, &a.x)
  130. gfpMul(B, &a.y, &a.y)
  131. gfpMul(C, B, B)
  132. t, t2 := &gfP{}, &gfP{}
  133. gfpAdd(t, &a.x, B)
  134. gfpMul(t2, t, t)
  135. gfpSub(t, t2, A)
  136. gfpSub(t2, t, C)
  137. d, e, f := &gfP{}, &gfP{}, &gfP{}
  138. gfpAdd(d, t2, t2)
  139. gfpAdd(t, A, A)
  140. gfpAdd(e, t, A)
  141. gfpMul(f, e, e)
  142. gfpAdd(t, d, d)
  143. gfpSub(&c.x, f, t)
  144. gfpAdd(t, C, C)
  145. gfpAdd(t2, t, t)
  146. gfpAdd(t, t2, t2)
  147. gfpSub(&c.y, d, &c.x)
  148. gfpMul(t2, e, &c.y)
  149. gfpSub(&c.y, t2, t)
  150. gfpMul(t, &a.y, &a.z)
  151. gfpAdd(&c.z, t, t)
  152. }
  153. func (c *curvePoint) Mul(a *curvePoint, scalar *big.Int) {
  154. precomp := [1 << 2]*curvePoint{nil, {}, {}, {}}
  155. precomp[1].Set(a)
  156. precomp[2].Set(a)
  157. gfpMul(&precomp[2].x, &precomp[2].x, xiTo2PSquaredMinus2Over3)
  158. precomp[3].Add(precomp[1], precomp[2])
  159. multiScalar := curveLattice.Multi(scalar)
  160. sum := &curvePoint{}
  161. sum.SetInfinity()
  162. t := &curvePoint{}
  163. for i := len(multiScalar) - 1; i >= 0; i-- {
  164. t.Double(sum)
  165. if multiScalar[i] == 0 {
  166. sum.Set(t)
  167. } else {
  168. sum.Add(t, precomp[multiScalar[i]])
  169. }
  170. }
  171. c.Set(sum)
  172. }
  173. func (c *curvePoint) MakeAffine() {
  174. if c.z == *newGFp(1) {
  175. return
  176. } else if c.z == *newGFp(0) {
  177. c.x = gfP{0}
  178. c.y = *newGFp(1)
  179. c.t = gfP{0}
  180. return
  181. }
  182. zInv := &gfP{}
  183. zInv.Invert(&c.z)
  184. t, zInv2 := &gfP{}, &gfP{}
  185. gfpMul(t, &c.y, zInv)
  186. gfpMul(zInv2, zInv, zInv)
  187. gfpMul(&c.x, &c.x, zInv2)
  188. gfpMul(&c.y, t, zInv2)
  189. c.z = *newGFp(1)
  190. c.t = *newGFp(1)
  191. }
  192. func (c *curvePoint) Neg(a *curvePoint) {
  193. c.x.Set(&a.x)
  194. gfpNeg(&c.y, &a.y)
  195. c.z.Set(&a.z)
  196. c.t = gfP{0}
  197. }