optate.go 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395
  1. // Copyright 2012 The Go Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style
  3. // license that can be found in the LICENSE file.
  4. package bn256
  5. func lineFunctionAdd(r, p *twistPoint, q *curvePoint, r2 *gfP2, pool *bnPool) (a, b, c *gfP2, rOut *twistPoint) {
  6. // See the mixed addition algorithm from "Faster Computation of the
  7. // Tate Pairing", http://arxiv.org/pdf/0904.0854v3.pdf
  8. B := newGFp2(pool).Mul(p.x, r.t, pool)
  9. D := newGFp2(pool).Add(p.y, r.z)
  10. D.Square(D, pool)
  11. D.Sub(D, r2)
  12. D.Sub(D, r.t)
  13. D.Mul(D, r.t, pool)
  14. H := newGFp2(pool).Sub(B, r.x)
  15. I := newGFp2(pool).Square(H, pool)
  16. E := newGFp2(pool).Add(I, I)
  17. E.Add(E, E)
  18. J := newGFp2(pool).Mul(H, E, pool)
  19. L1 := newGFp2(pool).Sub(D, r.y)
  20. L1.Sub(L1, r.y)
  21. V := newGFp2(pool).Mul(r.x, E, pool)
  22. rOut = newTwistPoint(pool)
  23. rOut.x.Square(L1, pool)
  24. rOut.x.Sub(rOut.x, J)
  25. rOut.x.Sub(rOut.x, V)
  26. rOut.x.Sub(rOut.x, V)
  27. rOut.z.Add(r.z, H)
  28. rOut.z.Square(rOut.z, pool)
  29. rOut.z.Sub(rOut.z, r.t)
  30. rOut.z.Sub(rOut.z, I)
  31. t := newGFp2(pool).Sub(V, rOut.x)
  32. t.Mul(t, L1, pool)
  33. t2 := newGFp2(pool).Mul(r.y, J, pool)
  34. t2.Add(t2, t2)
  35. rOut.y.Sub(t, t2)
  36. rOut.t.Square(rOut.z, pool)
  37. t.Add(p.y, rOut.z)
  38. t.Square(t, pool)
  39. t.Sub(t, r2)
  40. t.Sub(t, rOut.t)
  41. t2.Mul(L1, p.x, pool)
  42. t2.Add(t2, t2)
  43. a = newGFp2(pool)
  44. a.Sub(t2, t)
  45. c = newGFp2(pool)
  46. c.MulScalar(rOut.z, q.y)
  47. c.Add(c, c)
  48. b = newGFp2(pool)
  49. b.SetZero()
  50. b.Sub(b, L1)
  51. b.MulScalar(b, q.x)
  52. b.Add(b, b)
  53. B.Put(pool)
  54. D.Put(pool)
  55. H.Put(pool)
  56. I.Put(pool)
  57. E.Put(pool)
  58. J.Put(pool)
  59. L1.Put(pool)
  60. V.Put(pool)
  61. t.Put(pool)
  62. t2.Put(pool)
  63. return
  64. }
  65. func lineFunctionDouble(r *twistPoint, q *curvePoint, pool *bnPool) (a, b, c *gfP2, rOut *twistPoint) {
  66. // See the doubling algorithm for a=0 from "Faster Computation of the
  67. // Tate Pairing", http://arxiv.org/pdf/0904.0854v3.pdf
  68. A := newGFp2(pool).Square(r.x, pool)
  69. B := newGFp2(pool).Square(r.y, pool)
  70. C := newGFp2(pool).Square(B, pool)
  71. D := newGFp2(pool).Add(r.x, B)
  72. D.Square(D, pool)
  73. D.Sub(D, A)
  74. D.Sub(D, C)
  75. D.Add(D, D)
  76. E := newGFp2(pool).Add(A, A)
  77. E.Add(E, A)
  78. G := newGFp2(pool).Square(E, pool)
  79. rOut = newTwistPoint(pool)
  80. rOut.x.Sub(G, D)
  81. rOut.x.Sub(rOut.x, D)
  82. rOut.z.Add(r.y, r.z)
  83. rOut.z.Square(rOut.z, pool)
  84. rOut.z.Sub(rOut.z, B)
  85. rOut.z.Sub(rOut.z, r.t)
  86. rOut.y.Sub(D, rOut.x)
  87. rOut.y.Mul(rOut.y, E, pool)
  88. t := newGFp2(pool).Add(C, C)
  89. t.Add(t, t)
  90. t.Add(t, t)
  91. rOut.y.Sub(rOut.y, t)
  92. rOut.t.Square(rOut.z, pool)
  93. t.Mul(E, r.t, pool)
  94. t.Add(t, t)
  95. b = newGFp2(pool)
  96. b.SetZero()
  97. b.Sub(b, t)
  98. b.MulScalar(b, q.x)
  99. a = newGFp2(pool)
  100. a.Add(r.x, E)
  101. a.Square(a, pool)
  102. a.Sub(a, A)
  103. a.Sub(a, G)
  104. t.Add(B, B)
  105. t.Add(t, t)
  106. a.Sub(a, t)
  107. c = newGFp2(pool)
  108. c.Mul(rOut.z, r.t, pool)
  109. c.Add(c, c)
  110. c.MulScalar(c, q.y)
  111. A.Put(pool)
  112. B.Put(pool)
  113. C.Put(pool)
  114. D.Put(pool)
  115. E.Put(pool)
  116. G.Put(pool)
  117. t.Put(pool)
  118. return
  119. }
  120. func mulLine(ret *gfP12, a, b, c *gfP2, pool *bnPool) {
  121. a2 := newGFp6(pool)
  122. a2.x.SetZero()
  123. a2.y.Set(a)
  124. a2.z.Set(b)
  125. a2.Mul(a2, ret.x, pool)
  126. t3 := newGFp6(pool).MulScalar(ret.y, c, pool)
  127. t := newGFp2(pool)
  128. t.Add(b, c)
  129. t2 := newGFp6(pool)
  130. t2.x.SetZero()
  131. t2.y.Set(a)
  132. t2.z.Set(t)
  133. ret.x.Add(ret.x, ret.y)
  134. ret.y.Set(t3)
  135. ret.x.Mul(ret.x, t2, pool)
  136. ret.x.Sub(ret.x, a2)
  137. ret.x.Sub(ret.x, ret.y)
  138. a2.MulTau(a2, pool)
  139. ret.y.Add(ret.y, a2)
  140. a2.Put(pool)
  141. t3.Put(pool)
  142. t2.Put(pool)
  143. t.Put(pool)
  144. }
  145. // sixuPlus2NAF is 6u+2 in non-adjacent form.
  146. var sixuPlus2NAF = []int8{0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, -1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, -1, 0, 1, 0, 0, 0, 1, 0, -1, 0, 0, 0, -1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, -1, 0, -1, 0, 0, 0, 0, 1, 0, 0, 0, 1}
  147. // miller implements the Miller loop for calculating the Optimal Ate pairing.
  148. // See algorithm 1 from http://cryptojedi.org/papers/dclxvi-20100714.pdf
  149. func miller(q *twistPoint, p *curvePoint, pool *bnPool) *gfP12 {
  150. ret := newGFp12(pool)
  151. ret.SetOne()
  152. aAffine := newTwistPoint(pool)
  153. aAffine.Set(q)
  154. aAffine.MakeAffine(pool)
  155. bAffine := newCurvePoint(pool)
  156. bAffine.Set(p)
  157. bAffine.MakeAffine(pool)
  158. minusA := newTwistPoint(pool)
  159. minusA.Negative(aAffine, pool)
  160. r := newTwistPoint(pool)
  161. r.Set(aAffine)
  162. r2 := newGFp2(pool)
  163. r2.Square(aAffine.y, pool)
  164. for i := len(sixuPlus2NAF) - 1; i > 0; i-- {
  165. a, b, c, newR := lineFunctionDouble(r, bAffine, pool)
  166. if i != len(sixuPlus2NAF)-1 {
  167. ret.Square(ret, pool)
  168. }
  169. mulLine(ret, a, b, c, pool)
  170. a.Put(pool)
  171. b.Put(pool)
  172. c.Put(pool)
  173. r.Put(pool)
  174. r = newR
  175. switch sixuPlus2NAF[i-1] {
  176. case 1:
  177. a, b, c, newR = lineFunctionAdd(r, aAffine, bAffine, r2, pool)
  178. case -1:
  179. a, b, c, newR = lineFunctionAdd(r, minusA, bAffine, r2, pool)
  180. default:
  181. continue
  182. }
  183. mulLine(ret, a, b, c, pool)
  184. a.Put(pool)
  185. b.Put(pool)
  186. c.Put(pool)
  187. r.Put(pool)
  188. r = newR
  189. }
  190. // In order to calculate Q1 we have to convert q from the sextic twist
  191. // to the full GF(p^12) group, apply the Frobenius there, and convert
  192. // back.
  193. //
  194. // The twist isomorphism is (x', y') -> (xω², yω³). If we consider just
  195. // x for a moment, then after applying the Frobenius, we have x̄ω^(2p)
  196. // where x̄ is the conjugate of x. If we are going to apply the inverse
  197. // isomorphism we need a value with a single coefficient of ω² so we
  198. // rewrite this as x̄ω^(2p-2)ω². ξ⁶ = ω and, due to the construction of
  199. // p, 2p-2 is a multiple of six. Therefore we can rewrite as
  200. // x̄ξ^((p-1)/3)ω² and applying the inverse isomorphism eliminates the
  201. // ω².
  202. //
  203. // A similar argument can be made for the y value.
  204. q1 := newTwistPoint(pool)
  205. q1.x.Conjugate(aAffine.x)
  206. q1.x.Mul(q1.x, xiToPMinus1Over3, pool)
  207. q1.y.Conjugate(aAffine.y)
  208. q1.y.Mul(q1.y, xiToPMinus1Over2, pool)
  209. q1.z.SetOne()
  210. q1.t.SetOne()
  211. // For Q2 we are applying the p² Frobenius. The two conjugations cancel
  212. // out and we are left only with the factors from the isomorphism. In
  213. // the case of x, we end up with a pure number which is why
  214. // xiToPSquaredMinus1Over3 is ∈ GF(p). With y we get a factor of -1. We
  215. // ignore this to end up with -Q2.
  216. minusQ2 := newTwistPoint(pool)
  217. minusQ2.x.MulScalar(aAffine.x, xiToPSquaredMinus1Over3)
  218. minusQ2.y.Set(aAffine.y)
  219. minusQ2.z.SetOne()
  220. minusQ2.t.SetOne()
  221. r2.Square(q1.y, pool)
  222. a, b, c, newR := lineFunctionAdd(r, q1, bAffine, r2, pool)
  223. mulLine(ret, a, b, c, pool)
  224. a.Put(pool)
  225. b.Put(pool)
  226. c.Put(pool)
  227. r.Put(pool)
  228. r = newR
  229. r2.Square(minusQ2.y, pool)
  230. a, b, c, newR = lineFunctionAdd(r, minusQ2, bAffine, r2, pool)
  231. mulLine(ret, a, b, c, pool)
  232. a.Put(pool)
  233. b.Put(pool)
  234. c.Put(pool)
  235. r.Put(pool)
  236. r = newR
  237. aAffine.Put(pool)
  238. bAffine.Put(pool)
  239. minusA.Put(pool)
  240. r.Put(pool)
  241. r2.Put(pool)
  242. return ret
  243. }
  244. // finalExponentiation computes the (p¹²-1)/Order-th power of an element of
  245. // GF(p¹²) to obtain an element of GT (steps 13-15 of algorithm 1 from
  246. // http://cryptojedi.org/papers/dclxvi-20100714.pdf)
  247. func finalExponentiation(in *gfP12, pool *bnPool) *gfP12 {
  248. t1 := newGFp12(pool)
  249. // This is the p^6-Frobenius
  250. t1.x.Negative(in.x)
  251. t1.y.Set(in.y)
  252. inv := newGFp12(pool)
  253. inv.Invert(in, pool)
  254. t1.Mul(t1, inv, pool)
  255. t2 := newGFp12(pool).FrobeniusP2(t1, pool)
  256. t1.Mul(t1, t2, pool)
  257. fp := newGFp12(pool).Frobenius(t1, pool)
  258. fp2 := newGFp12(pool).FrobeniusP2(t1, pool)
  259. fp3 := newGFp12(pool).Frobenius(fp2, pool)
  260. fu, fu2, fu3 := newGFp12(pool), newGFp12(pool), newGFp12(pool)
  261. fu.Exp(t1, u, pool)
  262. fu2.Exp(fu, u, pool)
  263. fu3.Exp(fu2, u, pool)
  264. y3 := newGFp12(pool).Frobenius(fu, pool)
  265. fu2p := newGFp12(pool).Frobenius(fu2, pool)
  266. fu3p := newGFp12(pool).Frobenius(fu3, pool)
  267. y2 := newGFp12(pool).FrobeniusP2(fu2, pool)
  268. y0 := newGFp12(pool)
  269. y0.Mul(fp, fp2, pool)
  270. y0.Mul(y0, fp3, pool)
  271. y1, y4, y5 := newGFp12(pool), newGFp12(pool), newGFp12(pool)
  272. y1.Conjugate(t1)
  273. y5.Conjugate(fu2)
  274. y3.Conjugate(y3)
  275. y4.Mul(fu, fu2p, pool)
  276. y4.Conjugate(y4)
  277. y6 := newGFp12(pool)
  278. y6.Mul(fu3, fu3p, pool)
  279. y6.Conjugate(y6)
  280. t0 := newGFp12(pool)
  281. t0.Square(y6, pool)
  282. t0.Mul(t0, y4, pool)
  283. t0.Mul(t0, y5, pool)
  284. t1.Mul(y3, y5, pool)
  285. t1.Mul(t1, t0, pool)
  286. t0.Mul(t0, y2, pool)
  287. t1.Square(t1, pool)
  288. t1.Mul(t1, t0, pool)
  289. t1.Square(t1, pool)
  290. t0.Mul(t1, y1, pool)
  291. t1.Mul(t1, y0, pool)
  292. t0.Square(t0, pool)
  293. t0.Mul(t0, t1, pool)
  294. inv.Put(pool)
  295. t1.Put(pool)
  296. t2.Put(pool)
  297. fp.Put(pool)
  298. fp2.Put(pool)
  299. fp3.Put(pool)
  300. fu.Put(pool)
  301. fu2.Put(pool)
  302. fu3.Put(pool)
  303. fu2p.Put(pool)
  304. fu3p.Put(pool)
  305. y0.Put(pool)
  306. y1.Put(pool)
  307. y2.Put(pool)
  308. y3.Put(pool)
  309. y4.Put(pool)
  310. y5.Put(pool)
  311. y6.Put(pool)
  312. return t0
  313. }
  314. func optimalAte(a *twistPoint, b *curvePoint, pool *bnPool) *gfP12 {
  315. e := miller(a, b, pool)
  316. ret := finalExponentiation(e, pool)
  317. e.Put(pool)
  318. if a.IsInfinity() || b.IsInfinity() {
  319. ret.SetOne()
  320. }
  321. return ret
  322. }