field.gno
3.72 Kb · 150 lines
1package drand
2
3import (
4 "crypto/modexp"
5 "encoding/binary"
6 "math/bits"
7)
8
9// fe is an element of the BN254 base field, as four little-endian 64-bit
10// limbs, always fully reduced (< p).
11//
12// All the heavy arithmetic (squaring, inverse, square root, reducing a wide
13// integer) goes to the native modexp; gno code only does limb additions.
14type fe [4]uint64
15
16var (
17 pLimbs = fe{0x3c208c16d87cfd47, 0x97816a916871ca8d, 0xb85045b68181585d, 0x30644e72e131a029}
18 pBytes = mustHex("30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47")
19
20 // Exponents: p-2 (inverse), (p+1)/4 (square root, p = 3 mod 4).
21 expInverse = mustHex("30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd45")
22 expSqrt = mustHex("0c19139cb84c680a6e14116da060561765e05aa45a1c72a34f082305b61f3f52")
23
24 expOne = []byte{1}
25 expTwo = []byte{2}
26 expThree = []byte{3}
27)
28
29func feFromUint(v uint64) fe { return fe{v, 0, 0, 0} }
30
31// feFromBytes reduces a big-endian integer of up to 64 bytes mod p.
32func feFromBytes(b []byte) fe {
33 return feFromCanonicalUnchecked(modexp.ModExp(b, expOne, pBytes))
34}
35
36// feFromCanonical decodes exactly 32 big-endian bytes and reports whether the
37// value is already reduced.
38func feFromCanonical(b []byte) (fe, bool) {
39 e := feFromCanonicalUnchecked(b)
40 return e, e.lt(pLimbs)
41}
42
43func feFromCanonicalUnchecked(b []byte) fe {
44 be := binary.BigEndian
45 return fe{be.Uint64(b[24:]), be.Uint64(b[16:]), be.Uint64(b[8:]), be.Uint64(b[0:])}
46}
47
48// bytes returns the 32-byte big-endian encoding.
49func (a fe) bytes() []byte {
50 out := make([]byte, 32)
51 be := binary.BigEndian
52 be.PutUint64(out[0:], a[3])
53 be.PutUint64(out[8:], a[2])
54 be.PutUint64(out[16:], a[1])
55 be.PutUint64(out[24:], a[0])
56 return out
57}
58
59func (a fe) isZero() bool { return a[0]|a[1]|a[2]|a[3] == 0 }
60
61func (a fe) isOdd() bool { return a[0]&1 == 1 }
62
63func (a fe) lt(b fe) bool {
64 for i := 3; i >= 0; i-- {
65 if a[i] != b[i] {
66 return a[i] < b[i]
67 }
68 }
69 return false
70}
71
72func feAdd(a, b fe) fe {
73 r := rawAdd(a, b) // p < 2^254, so a+b never overflows 256 bits.
74 if !r.lt(pLimbs) {
75 r = rawSub(r, pLimbs)
76 }
77 return r
78}
79
80func feSub(a, b fe) fe {
81 if a.lt(b) {
82 return rawSub(rawAdd(a, pLimbs), b)
83 }
84 return rawSub(a, b)
85}
86
87func feNeg(a fe) fe {
88 if a.isZero() {
89 return a
90 }
91 return rawSub(pLimbs, a)
92}
93
94func rawAdd(a, b fe) fe {
95 var r fe
96 var c uint64
97 r[0], c = bits.Add64(a[0], b[0], 0)
98 r[1], c = bits.Add64(a[1], b[1], c)
99 r[2], c = bits.Add64(a[2], b[2], c)
100 r[3], _ = bits.Add64(a[3], b[3], c)
101 return r
102}
103
104func rawSub(a, b fe) fe {
105 var r fe
106 var c uint64
107 r[0], c = bits.Sub64(a[0], b[0], 0)
108 r[1], c = bits.Sub64(a[1], b[1], c)
109 r[2], c = bits.Sub64(a[2], b[2], c)
110 r[3], _ = bits.Sub64(a[3], b[3], c)
111 return r
112}
113
114// feMul uses quarter-squares, ab = ((a+b)/2)^2 - ((a-b)/2)^2, so the only
115// heavy work is two squarings done by the native modexp. A schoolbook
116// 256x256 product interpreted by the VM costs several times more.
117func feMul(a, b fe) fe {
118 return feSub(feSquare(feHalf(feAdd(a, b))), feSquare(feHalf(feSub(a, b))))
119}
120
121// feHalf returns a/2 mod p.
122func feHalf(a fe) fe {
123 if a.isOdd() {
124 a = rawAdd(a, pLimbs) // < 2^255, no overflow
125 }
126 a[0] = a[0]>>1 | a[1]<<63
127 a[1] = a[1]>>1 | a[2]<<63
128 a[2] = a[2]>>1 | a[3]<<63
129 a[3] >>= 1
130 return a
131}
132
133func feSquare(a fe) fe { return feExp(a, expTwo) }
134
135func feExp(a fe, e []byte) fe {
136 return feFromCanonicalUnchecked(modexp.ModExp(a.bytes(), e, pBytes))
137}
138
139// feInv returns a^-1, and 0 for 0 (same convention as RFC 9380 inv0).
140func feInv(a fe) fe { return feExp(a, expInverse) }
141
142// feSqrt returns a square root of a and whether a is a non-zero square.
143// Zero is reported as a non-square, matching drand/kyber's legendre check.
144func feSqrt(a fe) (fe, bool) {
145 if a.isZero() {
146 return a, false
147 }
148 r := feExp(a, expSqrt)
149 return r, feSquare(r) == a
150}