1 // Package fp25519 provides prime field arithmetic over GF(2^255-19).
2 package fp25519
3
4 import (
5 "errors"
6
7 "github.com/cloudflare/circl/internal/conv"
8 )
9
10 // Size in bytes of an element.
11 const Size = 32
12
13 // Elt is a prime field element.
14 type Elt [Size]byte
15
16 func (e Elt) String() string { return conv.BytesLe2Hex(e[:]) }
17
18 // p is the prime modulus 2^255-19.
19 var p = Elt{
20 0xed, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
21 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
22 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
23 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f,
24 }
25
26 // P returns the prime modulus 2^255-19.
27 func P() Elt { return p }
28
29 // ToBytes stores in b the little-endian byte representation of x.
30 func ToBytes(b []byte, x *Elt) error {
31 if len(b) != Size {
32 return errors.New("wrong size")
33 }
34 Modp(x)
35 copy(b, x[:])
36 return nil
37 }
38
39 // IsZero returns true if x is equal to 0.
40 func IsZero(x *Elt) bool { Modp(x); return *x == Elt{} }
41
42 // SetOne assigns x=1.
43 func SetOne(x *Elt) { *x = Elt{}; x[0] = 1 }
44
45 // Neg calculates z = -x.
46 func Neg(z, x *Elt) { Sub(z, &p, x) }
47
48 // InvSqrt calculates z = sqrt(x/y) iff x/y is a quadratic-residue, which is
49 // indicated by returning isQR = true. Otherwise, when x/y is a quadratic
50 // non-residue, z will have an undetermined value and isQR = false.
51 func InvSqrt(z, x, y *Elt) (isQR bool) {
52 sqrtMinusOne := &Elt{
53 0xb0, 0xa0, 0x0e, 0x4a, 0x27, 0x1b, 0xee, 0xc4,
54 0x78, 0xe4, 0x2f, 0xad, 0x06, 0x18, 0x43, 0x2f,
55 0xa7, 0xd7, 0xfb, 0x3d, 0x99, 0x00, 0x4d, 0x2b,
56 0x0b, 0xdf, 0xc1, 0x4f, 0x80, 0x24, 0x83, 0x2b,
57 }
58 t0, t1, t2, t3 := &Elt{}, &Elt{}, &Elt{}, &Elt{}
59
60 Mul(t0, x, y) // t0 = u*v
61 Sqr(t1, y) // t1 = v^2
62 Mul(t2, t0, t1) // t2 = u*v^3
63 Sqr(t0, t1) // t0 = v^4
64 Mul(t1, t0, t2) // t1 = u*v^7
65
66 var Tab [4]*Elt
67 Tab[0] = &Elt{}
68 Tab[1] = &Elt{}
69 Tab[2] = t3
70 Tab[3] = t1
71
72 *Tab[0] = *t1
73 Sqr(Tab[0], Tab[0])
74 Sqr(Tab[1], Tab[0])
75 Sqr(Tab[1], Tab[1])
76 Mul(Tab[1], Tab[1], Tab[3])
77 Mul(Tab[0], Tab[0], Tab[1])
78 Sqr(Tab[0], Tab[0])
79 Mul(Tab[0], Tab[0], Tab[1])
80 Sqr(Tab[1], Tab[0])
81 for i := 0; i < 4; i++ {
82 Sqr(Tab[1], Tab[1])
83 }
84 Mul(Tab[1], Tab[1], Tab[0])
85 Sqr(Tab[2], Tab[1])
86 for i := 0; i < 4; i++ {
87 Sqr(Tab[2], Tab[2])
88 }
89 Mul(Tab[2], Tab[2], Tab[0])
90 Sqr(Tab[1], Tab[2])
91 for i := 0; i < 14; i++ {
92 Sqr(Tab[1], Tab[1])
93 }
94 Mul(Tab[1], Tab[1], Tab[2])
95 Sqr(Tab[2], Tab[1])
96 for i := 0; i < 29; i++ {
97 Sqr(Tab[2], Tab[2])
98 }
99 Mul(Tab[2], Tab[2], Tab[1])
100 Sqr(Tab[1], Tab[2])
101 for i := 0; i < 59; i++ {
102 Sqr(Tab[1], Tab[1])
103 }
104 Mul(Tab[1], Tab[1], Tab[2])
105 for i := 0; i < 5; i++ {
106 Sqr(Tab[1], Tab[1])
107 }
108 Mul(Tab[1], Tab[1], Tab[0])
109 Sqr(Tab[2], Tab[1])
110 for i := 0; i < 124; i++ {
111 Sqr(Tab[2], Tab[2])
112 }
113 Mul(Tab[2], Tab[2], Tab[1])
114 Sqr(Tab[2], Tab[2])
115 Sqr(Tab[2], Tab[2])
116 Mul(Tab[2], Tab[2], Tab[3])
117
118 Mul(z, t3, t2) // z = xy^(p+3)/8 = xy^3*(xy^7)^(p-5)/8
119 // Checking whether y z^2 == x
120 Sqr(t0, z) // t0 = z^2
121 Mul(t0, t0, y) // t0 = yz^2
122 Sub(t1, t0, x) // t1 = t0-u
123 Add(t2, t0, x) // t2 = t0+u
124 if IsZero(t1) {
125 return true
126 } else if IsZero(t2) {
127 Mul(z, z, sqrtMinusOne) // z = z*sqrt(-1)
128 return true
129 } else {
130 return false
131 }
132 }
133
134 // Inv calculates z = 1/x mod p.
135 func Inv(z, x *Elt) {
136 x0, x1, x2 := &Elt{}, &Elt{}, &Elt{}
137 Sqr(x1, x)
138 Sqr(x0, x1)
139 Sqr(x0, x0)
140 Mul(x0, x0, x)
141 Mul(z, x0, x1)
142 Sqr(x1, z)
143 Mul(x0, x0, x1)
144 Sqr(x1, x0)
145 for i := 0; i < 4; i++ {
146 Sqr(x1, x1)
147 }
148 Mul(x0, x0, x1)
149 Sqr(x1, x0)
150 for i := 0; i < 9; i++ {
151 Sqr(x1, x1)
152 }
153 Mul(x1, x1, x0)
154 Sqr(x2, x1)
155 for i := 0; i < 19; i++ {
156 Sqr(x2, x2)
157 }
158 Mul(x2, x2, x1)
159 for i := 0; i < 10; i++ {
160 Sqr(x2, x2)
161 }
162 Mul(x2, x2, x0)
163 Sqr(x0, x2)
164 for i := 0; i < 49; i++ {
165 Sqr(x0, x0)
166 }
167 Mul(x0, x0, x2)
168 Sqr(x1, x0)
169 for i := 0; i < 99; i++ {
170 Sqr(x1, x1)
171 }
172 Mul(x1, x1, x0)
173 for i := 0; i < 50; i++ {
174 Sqr(x1, x1)
175 }
176 Mul(x1, x1, x2)
177 for i := 0; i < 5; i++ {
178 Sqr(x1, x1)
179 }
180 Mul(z, z, x1)
181 }
182
183 // Cmov assigns y to x if n is 1.
184 func Cmov(x, y *Elt, n uint) { cmov(x, y, n) }
185
186 // Cswap interchanges x and y if n is 1.
187 func Cswap(x, y *Elt, n uint) { cswap(x, y, n) }
188
189 // Add calculates z = x+y mod p.
190 func Add(z, x, y *Elt) { add(z, x, y) }
191
192 // Sub calculates z = x-y mod p.
193 func Sub(z, x, y *Elt) { sub(z, x, y) }
194
195 // AddSub calculates (x,y) = (x+y mod p, x-y mod p).
196 func AddSub(x, y *Elt) { addsub(x, y) }
197
198 // Mul calculates z = x*y mod p.
199 func Mul(z, x, y *Elt) { mul(z, x, y) }
200
201 // Sqr calculates z = x^2 mod p.
202 func Sqr(z, x *Elt) { sqr(z, x) }
203
204 // Modp ensures that z is between [0,p-1].
205 func Modp(z *Elt) { modp(z) }
206