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