gfp6.go 5.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296
  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. // For details of the algorithms used, see "Multiplication and Squaring on
  6. // Pairing-Friendly Fields, Devegili et al.
  7. // http://eprint.iacr.org/2006/471.pdf.
  8. import (
  9. "math/big"
  10. )
  11. // gfP6 implements the field of size p⁶ as a cubic extension of gfP2 where τ³=ξ
  12. // and ξ=i+3.
  13. type gfP6 struct {
  14. x, y, z *gfP2 // value is xτ² + yτ + z
  15. }
  16. func newGFp6(pool *bnPool) *gfP6 {
  17. return &gfP6{newGFp2(pool), newGFp2(pool), newGFp2(pool)}
  18. }
  19. func (e *gfP6) String() string {
  20. return "(" + e.x.String() + "," + e.y.String() + "," + e.z.String() + ")"
  21. }
  22. func (e *gfP6) Put(pool *bnPool) {
  23. e.x.Put(pool)
  24. e.y.Put(pool)
  25. e.z.Put(pool)
  26. }
  27. func (e *gfP6) Set(a *gfP6) *gfP6 {
  28. e.x.Set(a.x)
  29. e.y.Set(a.y)
  30. e.z.Set(a.z)
  31. return e
  32. }
  33. func (e *gfP6) SetZero() *gfP6 {
  34. e.x.SetZero()
  35. e.y.SetZero()
  36. e.z.SetZero()
  37. return e
  38. }
  39. func (e *gfP6) SetOne() *gfP6 {
  40. e.x.SetZero()
  41. e.y.SetZero()
  42. e.z.SetOne()
  43. return e
  44. }
  45. func (e *gfP6) Minimal() {
  46. e.x.Minimal()
  47. e.y.Minimal()
  48. e.z.Minimal()
  49. }
  50. func (e *gfP6) IsZero() bool {
  51. return e.x.IsZero() && e.y.IsZero() && e.z.IsZero()
  52. }
  53. func (e *gfP6) IsOne() bool {
  54. return e.x.IsZero() && e.y.IsZero() && e.z.IsOne()
  55. }
  56. func (e *gfP6) Negative(a *gfP6) *gfP6 {
  57. e.x.Negative(a.x)
  58. e.y.Negative(a.y)
  59. e.z.Negative(a.z)
  60. return e
  61. }
  62. func (e *gfP6) Frobenius(a *gfP6, pool *bnPool) *gfP6 {
  63. e.x.Conjugate(a.x)
  64. e.y.Conjugate(a.y)
  65. e.z.Conjugate(a.z)
  66. e.x.Mul(e.x, xiTo2PMinus2Over3, pool)
  67. e.y.Mul(e.y, xiToPMinus1Over3, pool)
  68. return e
  69. }
  70. // FrobeniusP2 computes (xτ²+yτ+z)^(p²) = xτ^(2p²) + yτ^(p²) + z
  71. func (e *gfP6) FrobeniusP2(a *gfP6) *gfP6 {
  72. // τ^(2p²) = τ²τ^(2p²-2) = τ²ξ^((2p²-2)/3)
  73. e.x.MulScalar(a.x, xiTo2PSquaredMinus2Over3)
  74. // τ^(p²) = ττ^(p²-1) = τξ^((p²-1)/3)
  75. e.y.MulScalar(a.y, xiToPSquaredMinus1Over3)
  76. e.z.Set(a.z)
  77. return e
  78. }
  79. func (e *gfP6) Add(a, b *gfP6) *gfP6 {
  80. e.x.Add(a.x, b.x)
  81. e.y.Add(a.y, b.y)
  82. e.z.Add(a.z, b.z)
  83. return e
  84. }
  85. func (e *gfP6) Sub(a, b *gfP6) *gfP6 {
  86. e.x.Sub(a.x, b.x)
  87. e.y.Sub(a.y, b.y)
  88. e.z.Sub(a.z, b.z)
  89. return e
  90. }
  91. func (e *gfP6) Double(a *gfP6) *gfP6 {
  92. e.x.Double(a.x)
  93. e.y.Double(a.y)
  94. e.z.Double(a.z)
  95. return e
  96. }
  97. func (e *gfP6) Mul(a, b *gfP6, pool *bnPool) *gfP6 {
  98. // "Multiplication and Squaring on Pairing-Friendly Fields"
  99. // Section 4, Karatsuba method.
  100. // http://eprint.iacr.org/2006/471.pdf
  101. v0 := newGFp2(pool)
  102. v0.Mul(a.z, b.z, pool)
  103. v1 := newGFp2(pool)
  104. v1.Mul(a.y, b.y, pool)
  105. v2 := newGFp2(pool)
  106. v2.Mul(a.x, b.x, pool)
  107. t0 := newGFp2(pool)
  108. t0.Add(a.x, a.y)
  109. t1 := newGFp2(pool)
  110. t1.Add(b.x, b.y)
  111. tz := newGFp2(pool)
  112. tz.Mul(t0, t1, pool)
  113. tz.Sub(tz, v1)
  114. tz.Sub(tz, v2)
  115. tz.MulXi(tz, pool)
  116. tz.Add(tz, v0)
  117. t0.Add(a.y, a.z)
  118. t1.Add(b.y, b.z)
  119. ty := newGFp2(pool)
  120. ty.Mul(t0, t1, pool)
  121. ty.Sub(ty, v0)
  122. ty.Sub(ty, v1)
  123. t0.MulXi(v2, pool)
  124. ty.Add(ty, t0)
  125. t0.Add(a.x, a.z)
  126. t1.Add(b.x, b.z)
  127. tx := newGFp2(pool)
  128. tx.Mul(t0, t1, pool)
  129. tx.Sub(tx, v0)
  130. tx.Add(tx, v1)
  131. tx.Sub(tx, v2)
  132. e.x.Set(tx)
  133. e.y.Set(ty)
  134. e.z.Set(tz)
  135. t0.Put(pool)
  136. t1.Put(pool)
  137. tx.Put(pool)
  138. ty.Put(pool)
  139. tz.Put(pool)
  140. v0.Put(pool)
  141. v1.Put(pool)
  142. v2.Put(pool)
  143. return e
  144. }
  145. func (e *gfP6) MulScalar(a *gfP6, b *gfP2, pool *bnPool) *gfP6 {
  146. e.x.Mul(a.x, b, pool)
  147. e.y.Mul(a.y, b, pool)
  148. e.z.Mul(a.z, b, pool)
  149. return e
  150. }
  151. func (e *gfP6) MulGFP(a *gfP6, b *big.Int) *gfP6 {
  152. e.x.MulScalar(a.x, b)
  153. e.y.MulScalar(a.y, b)
  154. e.z.MulScalar(a.z, b)
  155. return e
  156. }
  157. // MulTau computes τ·(aτ²+bτ+c) = bτ²+cτ+aξ
  158. func (e *gfP6) MulTau(a *gfP6, pool *bnPool) {
  159. tz := newGFp2(pool)
  160. tz.MulXi(a.x, pool)
  161. ty := newGFp2(pool)
  162. ty.Set(a.y)
  163. e.y.Set(a.z)
  164. e.x.Set(ty)
  165. e.z.Set(tz)
  166. tz.Put(pool)
  167. ty.Put(pool)
  168. }
  169. func (e *gfP6) Square(a *gfP6, pool *bnPool) *gfP6 {
  170. v0 := newGFp2(pool).Square(a.z, pool)
  171. v1 := newGFp2(pool).Square(a.y, pool)
  172. v2 := newGFp2(pool).Square(a.x, pool)
  173. c0 := newGFp2(pool).Add(a.x, a.y)
  174. c0.Square(c0, pool)
  175. c0.Sub(c0, v1)
  176. c0.Sub(c0, v2)
  177. c0.MulXi(c0, pool)
  178. c0.Add(c0, v0)
  179. c1 := newGFp2(pool).Add(a.y, a.z)
  180. c1.Square(c1, pool)
  181. c1.Sub(c1, v0)
  182. c1.Sub(c1, v1)
  183. xiV2 := newGFp2(pool).MulXi(v2, pool)
  184. c1.Add(c1, xiV2)
  185. c2 := newGFp2(pool).Add(a.x, a.z)
  186. c2.Square(c2, pool)
  187. c2.Sub(c2, v0)
  188. c2.Add(c2, v1)
  189. c2.Sub(c2, v2)
  190. e.x.Set(c2)
  191. e.y.Set(c1)
  192. e.z.Set(c0)
  193. v0.Put(pool)
  194. v1.Put(pool)
  195. v2.Put(pool)
  196. c0.Put(pool)
  197. c1.Put(pool)
  198. c2.Put(pool)
  199. xiV2.Put(pool)
  200. return e
  201. }
  202. func (e *gfP6) Invert(a *gfP6, pool *bnPool) *gfP6 {
  203. // See "Implementing cryptographic pairings", M. Scott, section 3.2.
  204. // ftp://136.206.11.249/pub/crypto/pairings.pdf
  205. // Here we can give a short explanation of how it works: let j be a cubic root of
  206. // unity in GF(p²) so that 1+j+j²=0.
  207. // Then (xτ² + yτ + z)(xj²τ² + yjτ + z)(xjτ² + yj²τ + z)
  208. // = (xτ² + yτ + z)(Cτ²+Bτ+A)
  209. // = (x³ξ²+y³ξ+z³-3ξxyz) = F is an element of the base field (the norm).
  210. //
  211. // On the other hand (xj²τ² + yjτ + z)(xjτ² + yj²τ + z)
  212. // = τ²(y²-ξxz) + τ(ξx²-yz) + (z²-ξxy)
  213. //
  214. // So that's why A = (z²-ξxy), B = (ξx²-yz), C = (y²-ξxz)
  215. t1 := newGFp2(pool)
  216. A := newGFp2(pool)
  217. A.Square(a.z, pool)
  218. t1.Mul(a.x, a.y, pool)
  219. t1.MulXi(t1, pool)
  220. A.Sub(A, t1)
  221. B := newGFp2(pool)
  222. B.Square(a.x, pool)
  223. B.MulXi(B, pool)
  224. t1.Mul(a.y, a.z, pool)
  225. B.Sub(B, t1)
  226. C := newGFp2(pool)
  227. C.Square(a.y, pool)
  228. t1.Mul(a.x, a.z, pool)
  229. C.Sub(C, t1)
  230. F := newGFp2(pool)
  231. F.Mul(C, a.y, pool)
  232. F.MulXi(F, pool)
  233. t1.Mul(A, a.z, pool)
  234. F.Add(F, t1)
  235. t1.Mul(B, a.x, pool)
  236. t1.MulXi(t1, pool)
  237. F.Add(F, t1)
  238. F.Invert(F, pool)
  239. e.x.Mul(C, F, pool)
  240. e.y.Mul(B, F, pool)
  241. e.z.Mul(A, F, pool)
  242. t1.Put(pool)
  243. A.Put(pool)
  244. B.Put(pool)
  245. C.Put(pool)
  246. F.Put(pool)
  247. return e
  248. }