Source file src/crypto/internal/edwards25519/scalar.go
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 "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. 22 type 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. 57 func 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. 63 func (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. 70 func (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. 77 func (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. 84 func (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. 91 func (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. 98 func (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. 109 func (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. 137 var scalarTwo168 = &Scalar{s: [4]uint64{0x5b8ab432eac74798, 0x38afddd6de59d5d7, 138 0xa2c131b399411b7c, 0x6329a7ed9ce5a30}} 139 var 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. 144 func (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. 158 func (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. 173 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} 174 175 // isReduced returns whether the given scalar in 32-byte little endian encoded 176 // form is reduced modulo l. 177 func 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. 204 func (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. 224 func (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 231 func (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. 239 func (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. 256 func (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 321 func (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