1 // Copyright (c) 2016 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 5 package edwards25519
6 7 import (
8 "crypto/internal/fips140deps/byteorder"
9 "errors"
10 "math/bits"
11 )
12 13 // A Scalar is an integer modulo
14 //
15 // l = 2^252 + 27742317777372353535851937790883648493
16 //
17 // which is the prime order of the edwards25519 group.
18 //
19 // This type works similarly to math/big.Int, and all arguments and
20 // receivers are allowed to alias.
21 //
22 // The zero value is a valid zero element.
23 type Scalar struct {
24 // s is the scalar in the Montgomery domain, in the format of the
25 // fiat-crypto implementation.
26 s fiatScalarMontgomeryDomainFieldElement
27 }
28 29 // The field implementation in scalar_fiat.go is generated by the fiat-crypto
30 // project (https://github.com/mit-plv/fiat-crypto) at version v0.0.9 (23d2dbc)
31 // from a formally verified model.
32 //
33 // fiat-crypto code comes under the following license.
34 //
35 // Copyright (c) 2015-2020 The fiat-crypto Authors. All rights reserved.
36 //
37 // Redistribution and use in source and binary forms, with or without
38 // modification, are permitted provided that the following conditions are
39 // met:
40 //
41 // 1. Redistributions of source code must retain the above copyright
42 // notice, this list of conditions and the following disclaimer.
43 //
44 // THIS SOFTWARE IS PROVIDED BY the fiat-crypto authors "AS IS"
45 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
46 // THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
47 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL Berkeley Software Design,
48 // Inc. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
49 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
50 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
51 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
52 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
53 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
54 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
55 //
56 57 // NewScalar returns a new zero Scalar.
58 func NewScalar() *Scalar {
59 return &Scalar{}
60 }
61 62 // MultiplyAdd sets s = x * y + z mod l, and returns s. It is equivalent to
63 // using Multiply and then Add.
64 func (s *Scalar) MultiplyAdd(x, y, z *Scalar) *Scalar {
65 // Make a copy of z in case it aliases s.
66 zCopy := (&Scalar{}).Set(z)
67 return s.Multiply(x, y).Add(s, zCopy)
68 }
69 70 // Add sets s = x + y mod l, and returns s.
71 func (s *Scalar) Add(x, y *Scalar) *Scalar {
72 // s = 1 * x + y mod l
73 fiatScalarAdd(&s.s, &x.s, &y.s)
74 return s
75 }
76 77 // Subtract sets s = x - y mod l, and returns s.
78 func (s *Scalar) Subtract(x, y *Scalar) *Scalar {
79 // s = -1 * y + x mod l
80 fiatScalarSub(&s.s, &x.s, &y.s)
81 return s
82 }
83 84 // Negate sets s = -x mod l, and returns s.
85 func (s *Scalar) Negate(x *Scalar) *Scalar {
86 // s = -1 * x + 0 mod l
87 fiatScalarOpp(&s.s, &x.s)
88 return s
89 }
90 91 // Multiply sets s = x * y mod l, and returns s.
92 func (s *Scalar) Multiply(x, y *Scalar) *Scalar {
93 // s = x * y + 0 mod l
94 fiatScalarMul(&s.s, &x.s, &y.s)
95 return s
96 }
97 98 // Set sets s = x, and returns s.
99 func (s *Scalar) Set(x *Scalar) *Scalar {
100 *s = *x
101 return s
102 }
103 104 // SetUniformBytes sets s = x mod l, where x is a 64-byte little-endian integer.
105 // If x is not of the right length, SetUniformBytes returns nil and an error,
106 // and the receiver is unchanged.
107 //
108 // SetUniformBytes can be used to set s to a uniformly distributed value given
109 // 64 uniformly distributed random bytes.
110 func (s *Scalar) SetUniformBytes(x []byte) (*Scalar, error) {
111 if len(x) != 64 {
112 return nil, errors.New("edwards25519: invalid SetUniformBytes input length")
113 }
114 115 // We have a value x of 512 bits, but our fiatScalarFromBytes function
116 // expects an input lower than l, which is a little over 252 bits.
117 //
118 // Instead of writing a reduction function that operates on wider inputs, we
119 // can interpret x as the sum of three shorter values a, b, and c.
120 //
121 // x = a + b * 2^168 + c * 2^336 mod l
122 //
123 // We then precompute 2^168 and 2^336 modulo l, and perform the reduction
124 // with two multiplications and two additions.
125 126 s.setShortBytes(x[:21])
127 t := (&Scalar{}).setShortBytes(x[21:42])
128 s.Add(s, t.Multiply(t, scalarTwo168))
129 t.setShortBytes(x[42:])
130 s.Add(s, t.Multiply(t, scalarTwo336))
131 132 return s, nil
133 }
134 135 // scalarTwo168 and scalarTwo336 are 2^168 and 2^336 modulo l, encoded as a
136 // fiatScalarMontgomeryDomainFieldElement, which is a little-endian 4-limb value
137 // in the 2^256 Montgomery domain.
138 var scalarTwo168 = &Scalar{s: [4]uint64{0x5b8ab432eac74798, 0x38afddd6de59d5d7,
139 0xa2c131b399411b7c, 0x6329a7ed9ce5a30}}
140 var scalarTwo336 = &Scalar{s: [4]uint64{0xbd3d108e2b35ecc5, 0x5c3a3718bdf9c90b,
141 0x63aa97a331b4f2ee, 0x3d217f5be65cb5c}}
142 143 // setShortBytes sets s = x mod l, where x is a little-endian integer shorter
144 // than 32 bytes.
145 func (s *Scalar) setShortBytes(x []byte) *Scalar {
146 if len(x) >= 32 {
147 panic("edwards25519: internal error: setShortBytes called with a long string")
148 }
149 var buf [32]byte
150 copy(buf[:], x)
151 fiatScalarFromBytes((*[4]uint64)(&s.s), &buf)
152 fiatScalarToMontgomery(&s.s, (*fiatScalarNonMontgomeryDomainFieldElement)(&s.s))
153 return s
154 }
155 156 // SetCanonicalBytes sets s = x, where x is a 32-byte little-endian encoding of
157 // s, and returns s. If x is not a canonical encoding of s, SetCanonicalBytes
158 // returns nil and an error, and the receiver is unchanged.
159 func (s *Scalar) SetCanonicalBytes(x []byte) (*Scalar, error) {
160 if len(x) != 32 {
161 return nil, errors.New("invalid scalar length")
162 }
163 if !isReduced(x) {
164 return nil, errors.New("invalid scalar encoding")
165 }
166 167 fiatScalarFromBytes((*[4]uint64)(&s.s), (*[32]byte)(x))
168 fiatScalarToMontgomery(&s.s, (*fiatScalarNonMontgomeryDomainFieldElement)(&s.s))
169 170 return s, nil
171 }
172 173 // scalarMinusOneBytes is l - 1 in little endian.
174 var scalarMinusOneBytes = [32]byte{236, 211, 245, 92, 26, 99, 18, 88, 214, 156, 247, 162, 222, 249, 222, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16}
175 176 // isReduced returns whether the given scalar in 32-byte little endian encoded
177 // form is reduced modulo l.
178 func isReduced(s []byte) bool {
179 if len(s) != 32 {
180 return false
181 }
182 183 s0 := byteorder.LEUint64(s[:8])
184 s1 := byteorder.LEUint64(s[8:16])
185 s2 := byteorder.LEUint64(s[16:24])
186 s3 := byteorder.LEUint64(s[24:])
187 188 l0 := byteorder.LEUint64(scalarMinusOneBytes[:8])
189 l1 := byteorder.LEUint64(scalarMinusOneBytes[8:16])
190 l2 := byteorder.LEUint64(scalarMinusOneBytes[16:24])
191 l3 := byteorder.LEUint64(scalarMinusOneBytes[24:])
192 193 // Do a constant time subtraction chain scalarMinusOneBytes - s. If there is
194 // a borrow at the end, then s > scalarMinusOneBytes.
195 _, b := bits.Sub64(l0, s0, 0)
196 _, b = bits.Sub64(l1, s1, b)
197 _, b = bits.Sub64(l2, s2, b)
198 _, b = bits.Sub64(l3, s3, b)
199 return b == 0
200 }
201 202 // SetBytesWithClamping applies the buffer pruning described in RFC 8032,
203 // Section 5.1.5 (also known as clamping) and sets s to the result. The input
204 // must be 32 bytes, and it is not modified. If x is not of the right length,
205 // SetBytesWithClamping returns nil and an error, and the receiver is unchanged.
206 //
207 // Note that since Scalar values are always reduced modulo the prime order of
208 // the curve, the resulting value will not preserve any of the cofactor-clearing
209 // properties that clamping is meant to provide. It will however work as
210 // expected as long as it is applied to points on the prime order subgroup, like
211 // in Ed25519. In fact, it is lost to history why RFC 8032 adopted the
212 // irrelevant RFC 7748 clamping, but it is now required for compatibility.
213 func (s *Scalar) SetBytesWithClamping(x []byte) (*Scalar, error) {
214 // The description above omits the purpose of the high bits of the clamping
215 // for brevity, but those are also lost to reductions, and are also
216 // irrelevant to edwards25519 as they protect against a specific
217 // implementation bug that was once observed in a generic Montgomery ladder.
218 if len(x) != 32 {
219 return nil, errors.New("edwards25519: invalid SetBytesWithClamping input length")
220 }
221 222 // We need to use the wide reduction from SetUniformBytes, since clamping
223 // sets the 2^254 bit, making the value higher than the order.
224 var wideBytes [64]byte
225 copy(wideBytes[:], x[:])
226 wideBytes[0] &= 248
227 wideBytes[31] &= 63
228 wideBytes[31] |= 64
229 return s.SetUniformBytes(wideBytes[:])
230 }
231 232 // Bytes returns the canonical 32-byte little-endian encoding of s.
233 func (s *Scalar) Bytes() []byte {
234 // This function is outlined to make the allocations inline in the caller
235 // rather than happen on the heap.
236 var encoded [32]byte
237 return s.bytes(&encoded)
238 }
239 240 func (s *Scalar) bytes(out *[32]byte) []byte {
241 var ss fiatScalarNonMontgomeryDomainFieldElement
242 fiatScalarFromMontgomery(&ss, &s.s)
243 fiatScalarToBytes(out, (*[4]uint64)(&ss))
244 return out[:]
245 }
246 247 // Equal returns 1 if s and t are equal, and 0 otherwise.
248 func (s *Scalar) Equal(t *Scalar) int {
249 var diff fiatScalarMontgomeryDomainFieldElement
250 fiatScalarSub(&diff, &s.s, &t.s)
251 var nonzero uint64
252 fiatScalarNonzero(&nonzero, (*[4]uint64)(&diff))
253 nonzero |= nonzero >> 32
254 nonzero |= nonzero >> 16
255 nonzero |= nonzero >> 8
256 nonzero |= nonzero >> 4
257 nonzero |= nonzero >> 2
258 nonzero |= nonzero >> 1
259 return int(^nonzero) & 1
260 }
261 262 // nonAdjacentForm computes a width-w non-adjacent form for this scalar.
263 //
264 // w must be between 2 and 8, or nonAdjacentForm will panic.
265 func (s *Scalar) nonAdjacentForm(w uint) [256]int8 {
266 // This implementation is adapted from the one
267 // in curve25519-dalek and is documented there:
268 // https://github.com/dalek-cryptography/curve25519-dalek/blob/f630041af28e9a405255f98a8a93adca18e4315b/src/scalar.rs#L800-L871
269 b := s.Bytes()
270 if b[31] > 127 {
271 panic("scalar has high bit set illegally")
272 }
273 if w < 2 {
274 panic("w must be at least 2 by the definition of NAF")
275 } else if w > 8 {
276 panic("NAF digits must fit in int8")
277 }
278 279 var naf [256]int8
280 var digits [5]uint64
281 282 for i := 0; i < 4; i++ {
283 digits[i] = byteorder.LEUint64(b[i*8:])
284 }
285 286 width := uint64(1 << w)
287 windowMask := uint64(width - 1)
288 289 pos := uint(0)
290 carry := uint64(0)
291 for pos < 256 {
292 indexU64 := pos / 64
293 indexBit := pos % 64
294 var bitBuf uint64
295 if indexBit < 64-w {
296 // This window's bits are contained in a single u64
297 bitBuf = digits[indexU64] >> indexBit
298 } else {
299 // Combine the current 64 bits with bits from the next 64
300 bitBuf = (digits[indexU64] >> indexBit) | (digits[1+indexU64] << (64 - indexBit))
301 }
302 303 // Add carry into the current window
304 window := carry + (bitBuf & windowMask)
305 306 if window&1 == 0 {
307 // If the window value is even, preserve the carry and continue.
308 // Why is the carry preserved?
309 // If carry == 0 and window & 1 == 0,
310 // then the next carry should be 0
311 // If carry == 1 and window & 1 == 0,
312 // then bit_buf & 1 == 1 so the next carry should be 1
313 pos += 1
314 continue
315 }
316 317 if window < width/2 {
318 carry = 0
319 naf[pos] = int8(window)
320 } else {
321 carry = 1
322 naf[pos] = int8(window) - int8(width)
323 }
324 325 pos += w
326 }
327 return naf
328 }
329 330 func (s *Scalar) signedRadix16() [64]int8 {
331 b := s.Bytes()
332 if b[31] > 127 {
333 panic("scalar has high bit set illegally")
334 }
335 336 var digits [64]int8
337 338 // Compute unsigned radix-16 digits:
339 for i := 0; i < 32; i++ {
340 digits[2*i] = int8(b[i] & 15)
341 digits[2*i+1] = int8((b[i] >> 4) & 15)
342 }
343 344 // Recenter coefficients:
345 for i := 0; i < 63; i++ {
346 carry := (digits[i] + 8) >> 4
347 digits[i] -= carry << 4
348 digits[i+1] += carry
349 }
350 351 return digits
352 }
353