forked from dedis/kyber
-
Notifications
You must be signed in to change notification settings - Fork 10
/
gfp.go
142 lines (119 loc) · 2.77 KB
/
gfp.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
package bn254
import (
"errors"
"fmt"
"math/big"
)
type gfP [4]uint64
func newGFp(x int64) (out *gfP) {
if x >= 0 {
out = &gfP{uint64(x)}
} else {
out = &gfP{uint64(-x)}
gfpNeg(out, out)
}
montEncode(out, out)
return out
}
func newGFpFromBase10(x string) *gfP {
bx, _ := new(big.Int).SetString(x, 10)
bx = bx.Mod(bx, p)
out := &gfP{}
out.Unmarshal(zeroPadBytes(bx.Bytes(), 32))
montEncode(out, out)
return out
}
func (e *gfP) String() string {
c := &gfP{}
c.Set(e)
montDecode(c, c)
return fmt.Sprintf("%16.16x%16.16x%16.16x%16.16x", c[3], c[2], c[1], c[0])
}
func (e *gfP) Set(f *gfP) {
e[0] = f[0]
e[1] = f[1]
e[2] = f[2]
e[3] = f[3]
}
func (e *gfP) Invert(f *gfP) {
bits := [4]uint64{0x3c208c16d87cfd45, 0x97816a916871ca8d, 0xb85045b68181585d, 0x30644e72e131a029}
sum, power := &gfP{}, &gfP{}
sum.Set(rN1)
power.Set(f)
for word := 0; word < 4; word++ {
for bit := uint(0); bit < 64; bit++ {
if (bits[word]>>bit)&1 == 1 {
gfpMul(sum, sum, power)
}
gfpMul(power, power, power)
}
}
gfpMul(sum, sum, r3)
e.Set(sum)
}
// Borrowed from: https://github.com/cloudflare/bn256/blob/master/gfp.go#L63
func (e *gfP) Exp(f *gfP, bits [4]uint64) {
sum, power := &gfP{}, &gfP{}
sum.Set(rN1)
power.Set(f)
for word := 0; word < 4; word++ {
for bit := uint(0); bit < 64; bit++ {
if (bits[word]>>bit)&1 == 1 {
gfpMul(sum, sum, power)
}
gfpMul(power, power, power)
}
}
gfpMul(sum, sum, r3)
e.Set(sum)
}
// Borrowed from: https://github.com/cloudflare/bn256/blob/master/gfp.go#L85
func (e *gfP) Sqrt(f *gfP) {
// Since p = 4k+3, then e = f^(k+1) is a root of f.
e.Exp(f, pPlus1Over4)
}
func (e *gfP) Marshal(out []byte) {
for w := uint(0); w < 4; w++ {
for b := uint(0); b < 8; b++ {
out[8*w+b] = byte(e[3-w] >> (56 - 8*b))
}
}
}
func (e *gfP) Unmarshal(in []byte) error {
// Unmarshal the bytes into little endian form
for w := uint(0); w < 4; w++ {
e[3-w] = 0
for b := uint(0); b < 8; b++ {
e[3-w] += uint64(in[8*w+b]) << (56 - 8*b)
}
}
// Ensure the point respects the curve modulus
for i := 3; i >= 0; i-- {
if e[i] < p2[i] {
return nil
}
if e[i] > p2[i] {
return errors.New("bn254: coordinate exceeds modulus")
}
}
return errors.New("bn254: coordinate equals modulus")
}
func montEncode(c, a *gfP) { gfpMul(c, a, r2) }
func montDecode(c, a *gfP) { gfpMul(c, a, &gfP{1}) }
// https://datatracker.ietf.org/doc/html/rfc9380/#name-the-sgn0-function
func sgn0(e *gfP) int {
x := &gfP{}
montDecode(x, e)
return int(x[0] & 1)
}
// Borrowed from: https://github.com/cloudflare/bn256/blob/master/gfp.go#L123
func legendre(e *gfP) int {
f := &gfP{}
// Since p = 4k+3, then e^(2k+1) is the Legendre symbol of e.
f.Exp(e, pMinus1Over2)
montDecode(f, f)
if *f != [4]uint64{} {
return 2*int(f[0]&1) - 1
}
return 0
}