bn256.go 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404
  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 implements a particular bilinear group at the 128-bit security level.
  5. //
  6. // Bilinear groups are the basis of many of the new cryptographic protocols
  7. // that have been proposed over the past decade. They consist of a triplet of
  8. // groups (G₁, G₂ and GT) such that there exists a function e(g₁ˣ,g₂ʸ)=gTˣʸ
  9. // (where gₓ is a generator of the respective group). That function is called
  10. // a pairing function.
  11. //
  12. // This package specifically implements the Optimal Ate pairing over a 256-bit
  13. // Barreto-Naehrig curve as described in
  14. // http://cryptojedi.org/papers/dclxvi-20100714.pdf. Its output is compatible
  15. // with the implementation described in that paper.
  16. package bn256 // import "golang.org/x/crypto/bn256"
  17. import (
  18. "crypto/rand"
  19. "io"
  20. "math/big"
  21. )
  22. // BUG(agl): this implementation is not constant time.
  23. // TODO(agl): keep GF(p²) elements in Mongomery form.
  24. // G1 is an abstract cyclic group. The zero value is suitable for use as the
  25. // output of an operation, but cannot be used as an input.
  26. type G1 struct {
  27. p *curvePoint
  28. }
  29. // RandomG1 returns x and g₁ˣ where x is a random, non-zero number read from r.
  30. func RandomG1(r io.Reader) (*big.Int, *G1, error) {
  31. var k *big.Int
  32. var err error
  33. for {
  34. k, err = rand.Int(r, Order)
  35. if err != nil {
  36. return nil, nil, err
  37. }
  38. if k.Sign() > 0 {
  39. break
  40. }
  41. }
  42. return k, new(G1).ScalarBaseMult(k), nil
  43. }
  44. func (g *G1) String() string {
  45. return "bn256.G1" + g.p.String()
  46. }
  47. // ScalarBaseMult sets e to g*k where g is the generator of the group and
  48. // then returns e.
  49. func (e *G1) ScalarBaseMult(k *big.Int) *G1 {
  50. if e.p == nil {
  51. e.p = newCurvePoint(nil)
  52. }
  53. e.p.Mul(curveGen, k, new(bnPool))
  54. return e
  55. }
  56. // ScalarMult sets e to a*k and then returns e.
  57. func (e *G1) ScalarMult(a *G1, k *big.Int) *G1 {
  58. if e.p == nil {
  59. e.p = newCurvePoint(nil)
  60. }
  61. e.p.Mul(a.p, k, new(bnPool))
  62. return e
  63. }
  64. // Add sets e to a+b and then returns e.
  65. // BUG(agl): this function is not complete: a==b fails.
  66. func (e *G1) Add(a, b *G1) *G1 {
  67. if e.p == nil {
  68. e.p = newCurvePoint(nil)
  69. }
  70. e.p.Add(a.p, b.p, new(bnPool))
  71. return e
  72. }
  73. // Neg sets e to -a and then returns e.
  74. func (e *G1) Neg(a *G1) *G1 {
  75. if e.p == nil {
  76. e.p = newCurvePoint(nil)
  77. }
  78. e.p.Negative(a.p)
  79. return e
  80. }
  81. // Marshal converts n to a byte slice.
  82. func (n *G1) Marshal() []byte {
  83. n.p.MakeAffine(nil)
  84. xBytes := new(big.Int).Mod(n.p.x, p).Bytes()
  85. yBytes := new(big.Int).Mod(n.p.y, p).Bytes()
  86. // Each value is a 256-bit number.
  87. const numBytes = 256 / 8
  88. ret := make([]byte, numBytes*2)
  89. copy(ret[1*numBytes-len(xBytes):], xBytes)
  90. copy(ret[2*numBytes-len(yBytes):], yBytes)
  91. return ret
  92. }
  93. // Unmarshal sets e to the result of converting the output of Marshal back into
  94. // a group element and then returns e.
  95. func (e *G1) Unmarshal(m []byte) (*G1, bool) {
  96. // Each value is a 256-bit number.
  97. const numBytes = 256 / 8
  98. if len(m) != 2*numBytes {
  99. return nil, false
  100. }
  101. if e.p == nil {
  102. e.p = newCurvePoint(nil)
  103. }
  104. e.p.x.SetBytes(m[0*numBytes : 1*numBytes])
  105. e.p.y.SetBytes(m[1*numBytes : 2*numBytes])
  106. if e.p.x.Sign() == 0 && e.p.y.Sign() == 0 {
  107. // This is the point at infinity.
  108. e.p.y.SetInt64(1)
  109. e.p.z.SetInt64(0)
  110. e.p.t.SetInt64(0)
  111. } else {
  112. e.p.z.SetInt64(1)
  113. e.p.t.SetInt64(1)
  114. if !e.p.IsOnCurve() {
  115. return nil, false
  116. }
  117. }
  118. return e, true
  119. }
  120. // G2 is an abstract cyclic group. The zero value is suitable for use as the
  121. // output of an operation, but cannot be used as an input.
  122. type G2 struct {
  123. p *twistPoint
  124. }
  125. // RandomG1 returns x and g₂ˣ where x is a random, non-zero number read from r.
  126. func RandomG2(r io.Reader) (*big.Int, *G2, error) {
  127. var k *big.Int
  128. var err error
  129. for {
  130. k, err = rand.Int(r, Order)
  131. if err != nil {
  132. return nil, nil, err
  133. }
  134. if k.Sign() > 0 {
  135. break
  136. }
  137. }
  138. return k, new(G2).ScalarBaseMult(k), nil
  139. }
  140. func (g *G2) String() string {
  141. return "bn256.G2" + g.p.String()
  142. }
  143. // ScalarBaseMult sets e to g*k where g is the generator of the group and
  144. // then returns out.
  145. func (e *G2) ScalarBaseMult(k *big.Int) *G2 {
  146. if e.p == nil {
  147. e.p = newTwistPoint(nil)
  148. }
  149. e.p.Mul(twistGen, k, new(bnPool))
  150. return e
  151. }
  152. // ScalarMult sets e to a*k and then returns e.
  153. func (e *G2) ScalarMult(a *G2, k *big.Int) *G2 {
  154. if e.p == nil {
  155. e.p = newTwistPoint(nil)
  156. }
  157. e.p.Mul(a.p, k, new(bnPool))
  158. return e
  159. }
  160. // Add sets e to a+b and then returns e.
  161. // BUG(agl): this function is not complete: a==b fails.
  162. func (e *G2) Add(a, b *G2) *G2 {
  163. if e.p == nil {
  164. e.p = newTwistPoint(nil)
  165. }
  166. e.p.Add(a.p, b.p, new(bnPool))
  167. return e
  168. }
  169. // Marshal converts n into a byte slice.
  170. func (n *G2) Marshal() []byte {
  171. n.p.MakeAffine(nil)
  172. xxBytes := new(big.Int).Mod(n.p.x.x, p).Bytes()
  173. xyBytes := new(big.Int).Mod(n.p.x.y, p).Bytes()
  174. yxBytes := new(big.Int).Mod(n.p.y.x, p).Bytes()
  175. yyBytes := new(big.Int).Mod(n.p.y.y, p).Bytes()
  176. // Each value is a 256-bit number.
  177. const numBytes = 256 / 8
  178. ret := make([]byte, numBytes*4)
  179. copy(ret[1*numBytes-len(xxBytes):], xxBytes)
  180. copy(ret[2*numBytes-len(xyBytes):], xyBytes)
  181. copy(ret[3*numBytes-len(yxBytes):], yxBytes)
  182. copy(ret[4*numBytes-len(yyBytes):], yyBytes)
  183. return ret
  184. }
  185. // Unmarshal sets e to the result of converting the output of Marshal back into
  186. // a group element and then returns e.
  187. func (e *G2) Unmarshal(m []byte) (*G2, bool) {
  188. // Each value is a 256-bit number.
  189. const numBytes = 256 / 8
  190. if len(m) != 4*numBytes {
  191. return nil, false
  192. }
  193. if e.p == nil {
  194. e.p = newTwistPoint(nil)
  195. }
  196. e.p.x.x.SetBytes(m[0*numBytes : 1*numBytes])
  197. e.p.x.y.SetBytes(m[1*numBytes : 2*numBytes])
  198. e.p.y.x.SetBytes(m[2*numBytes : 3*numBytes])
  199. e.p.y.y.SetBytes(m[3*numBytes : 4*numBytes])
  200. if e.p.x.x.Sign() == 0 &&
  201. e.p.x.y.Sign() == 0 &&
  202. e.p.y.x.Sign() == 0 &&
  203. e.p.y.y.Sign() == 0 {
  204. // This is the point at infinity.
  205. e.p.y.SetOne()
  206. e.p.z.SetZero()
  207. e.p.t.SetZero()
  208. } else {
  209. e.p.z.SetOne()
  210. e.p.t.SetOne()
  211. if !e.p.IsOnCurve() {
  212. return nil, false
  213. }
  214. }
  215. return e, true
  216. }
  217. // GT is an abstract cyclic group. The zero value is suitable for use as the
  218. // output of an operation, but cannot be used as an input.
  219. type GT struct {
  220. p *gfP12
  221. }
  222. func (g *GT) String() string {
  223. return "bn256.GT" + g.p.String()
  224. }
  225. // ScalarMult sets e to a*k and then returns e.
  226. func (e *GT) ScalarMult(a *GT, k *big.Int) *GT {
  227. if e.p == nil {
  228. e.p = newGFp12(nil)
  229. }
  230. e.p.Exp(a.p, k, new(bnPool))
  231. return e
  232. }
  233. // Add sets e to a+b and then returns e.
  234. func (e *GT) Add(a, b *GT) *GT {
  235. if e.p == nil {
  236. e.p = newGFp12(nil)
  237. }
  238. e.p.Mul(a.p, b.p, new(bnPool))
  239. return e
  240. }
  241. // Neg sets e to -a and then returns e.
  242. func (e *GT) Neg(a *GT) *GT {
  243. if e.p == nil {
  244. e.p = newGFp12(nil)
  245. }
  246. e.p.Invert(a.p, new(bnPool))
  247. return e
  248. }
  249. // Marshal converts n into a byte slice.
  250. func (n *GT) Marshal() []byte {
  251. n.p.Minimal()
  252. xxxBytes := n.p.x.x.x.Bytes()
  253. xxyBytes := n.p.x.x.y.Bytes()
  254. xyxBytes := n.p.x.y.x.Bytes()
  255. xyyBytes := n.p.x.y.y.Bytes()
  256. xzxBytes := n.p.x.z.x.Bytes()
  257. xzyBytes := n.p.x.z.y.Bytes()
  258. yxxBytes := n.p.y.x.x.Bytes()
  259. yxyBytes := n.p.y.x.y.Bytes()
  260. yyxBytes := n.p.y.y.x.Bytes()
  261. yyyBytes := n.p.y.y.y.Bytes()
  262. yzxBytes := n.p.y.z.x.Bytes()
  263. yzyBytes := n.p.y.z.y.Bytes()
  264. // Each value is a 256-bit number.
  265. const numBytes = 256 / 8
  266. ret := make([]byte, numBytes*12)
  267. copy(ret[1*numBytes-len(xxxBytes):], xxxBytes)
  268. copy(ret[2*numBytes-len(xxyBytes):], xxyBytes)
  269. copy(ret[3*numBytes-len(xyxBytes):], xyxBytes)
  270. copy(ret[4*numBytes-len(xyyBytes):], xyyBytes)
  271. copy(ret[5*numBytes-len(xzxBytes):], xzxBytes)
  272. copy(ret[6*numBytes-len(xzyBytes):], xzyBytes)
  273. copy(ret[7*numBytes-len(yxxBytes):], yxxBytes)
  274. copy(ret[8*numBytes-len(yxyBytes):], yxyBytes)
  275. copy(ret[9*numBytes-len(yyxBytes):], yyxBytes)
  276. copy(ret[10*numBytes-len(yyyBytes):], yyyBytes)
  277. copy(ret[11*numBytes-len(yzxBytes):], yzxBytes)
  278. copy(ret[12*numBytes-len(yzyBytes):], yzyBytes)
  279. return ret
  280. }
  281. // Unmarshal sets e to the result of converting the output of Marshal back into
  282. // a group element and then returns e.
  283. func (e *GT) Unmarshal(m []byte) (*GT, bool) {
  284. // Each value is a 256-bit number.
  285. const numBytes = 256 / 8
  286. if len(m) != 12*numBytes {
  287. return nil, false
  288. }
  289. if e.p == nil {
  290. e.p = newGFp12(nil)
  291. }
  292. e.p.x.x.x.SetBytes(m[0*numBytes : 1*numBytes])
  293. e.p.x.x.y.SetBytes(m[1*numBytes : 2*numBytes])
  294. e.p.x.y.x.SetBytes(m[2*numBytes : 3*numBytes])
  295. e.p.x.y.y.SetBytes(m[3*numBytes : 4*numBytes])
  296. e.p.x.z.x.SetBytes(m[4*numBytes : 5*numBytes])
  297. e.p.x.z.y.SetBytes(m[5*numBytes : 6*numBytes])
  298. e.p.y.x.x.SetBytes(m[6*numBytes : 7*numBytes])
  299. e.p.y.x.y.SetBytes(m[7*numBytes : 8*numBytes])
  300. e.p.y.y.x.SetBytes(m[8*numBytes : 9*numBytes])
  301. e.p.y.y.y.SetBytes(m[9*numBytes : 10*numBytes])
  302. e.p.y.z.x.SetBytes(m[10*numBytes : 11*numBytes])
  303. e.p.y.z.y.SetBytes(m[11*numBytes : 12*numBytes])
  304. return e, true
  305. }
  306. // Pair calculates an Optimal Ate pairing.
  307. func Pair(g1 *G1, g2 *G2) *GT {
  308. return &GT{optimalAte(g2.p, g1.p, new(bnPool))}
  309. }
  310. // bnPool implements a tiny cache of *big.Int objects that's used to reduce the
  311. // number of allocations made during processing.
  312. type bnPool struct {
  313. bns []*big.Int
  314. count int
  315. }
  316. func (pool *bnPool) Get() *big.Int {
  317. if pool == nil {
  318. return new(big.Int)
  319. }
  320. pool.count++
  321. l := len(pool.bns)
  322. if l == 0 {
  323. return new(big.Int)
  324. }
  325. bn := pool.bns[l-1]
  326. pool.bns = pool.bns[:l-1]
  327. return bn
  328. }
  329. func (pool *bnPool) Put(bn *big.Int) {
  330. if pool == nil {
  331. return
  332. }
  333. pool.bns = append(pool.bns, bn)
  334. pool.count--
  335. }
  336. func (pool *bnPool) Count() int {
  337. return pool.count
  338. }