// Copyright (c) 2017 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package field implements fast arithmetic modulo 2^255-19.
package field import ( ) // Element represents an element of the field GF(2^255-19). Note that this // is not a cryptographically secure group, and should only be used to interact // with edwards25519.Point coordinates. // // This type works similarly to math/big.Int, and all arguments and receivers // are allowed to alias. // // The zero value is a valid zero element. type Element struct { // An element t represents the integer // t.l0 + t.l1*2^51 + t.l2*2^102 + t.l3*2^153 + t.l4*2^204 // // Between operations, all limbs are expected to be lower than 2^52. l0 uint64 l1 uint64 l2 uint64 l3 uint64 l4 uint64 } const maskLow51Bits uint64 = (1 << 51) - 1 var feZero = &Element{0, 0, 0, 0, 0} // Zero sets v = 0, and returns v. func ( *Element) () *Element { * = *feZero return } var feOne = &Element{1, 0, 0, 0, 0} // One sets v = 1, and returns v. func ( *Element) () *Element { * = *feOne return } // reduce reduces v modulo 2^255 - 19 and returns it. func ( *Element) () *Element { .carryPropagate() // After the light reduction we now have a field element representation // v < 2^255 + 2^13 * 19, but need v < 2^255 - 19. // If v >= 2^255 - 19, then v + 19 >= 2^255, which would overflow 2^255 - 1, // generating a carry. That is, c will be 0 if v < 2^255 - 19, and 1 otherwise. := (.l0 + 19) >> 51 = (.l1 + ) >> 51 = (.l2 + ) >> 51 = (.l3 + ) >> 51 = (.l4 + ) >> 51 // If v < 2^255 - 19 and c = 0, this will be a no-op. Otherwise, it's // effectively applying the reduction identity to the carry. .l0 += 19 * .l1 += .l0 >> 51 .l0 = .l0 & maskLow51Bits .l2 += .l1 >> 51 .l1 = .l1 & maskLow51Bits .l3 += .l2 >> 51 .l2 = .l2 & maskLow51Bits .l4 += .l3 >> 51 .l3 = .l3 & maskLow51Bits // no additional carry .l4 = .l4 & maskLow51Bits return } // Add sets v = a + b, and returns v. func ( *Element) (, *Element) *Element { .l0 = .l0 + .l0 .l1 = .l1 + .l1 .l2 = .l2 + .l2 .l3 = .l3 + .l3 .l4 = .l4 + .l4 // Using the generic implementation here is actually faster than the // assembly. Probably because the body of this function is so simple that // the compiler can figure out better optimizations by inlining the carry // propagation. return .carryPropagateGeneric() } // Subtract sets v = a - b, and returns v. func ( *Element) (, *Element) *Element { // We first add 2 * p, to guarantee the subtraction won't underflow, and // then subtract b (which can be up to 2^255 + 2^13 * 19). .l0 = (.l0 + 0xFFFFFFFFFFFDA) - .l0 .l1 = (.l1 + 0xFFFFFFFFFFFFE) - .l1 .l2 = (.l2 + 0xFFFFFFFFFFFFE) - .l2 .l3 = (.l3 + 0xFFFFFFFFFFFFE) - .l3 .l4 = (.l4 + 0xFFFFFFFFFFFFE) - .l4 return .carryPropagate() } // Negate sets v = -a, and returns v. func ( *Element) ( *Element) *Element { return .Subtract(feZero, ) } // Invert sets v = 1/z mod p, and returns v. // // If z == 0, Invert returns v = 0. func ( *Element) ( *Element) *Element { // Inversion is implemented as exponentiation with exponent p − 2. It uses the // same sequence of 255 squarings and 11 multiplications as [Curve25519]. var , , , , , , , , Element .Square() // 2 .Square(&) // 4 .Square(&) // 8 .Multiply(&, ) // 9 .Multiply(&, &) // 11 .Square(&) // 22 .Multiply(&, &) // 31 = 2^5 - 2^0 .Square(&) // 2^6 - 2^1 for := 0; < 4; ++ { .Square(&) // 2^10 - 2^5 } .Multiply(&, &) // 2^10 - 2^0 .Square(&) // 2^11 - 2^1 for := 0; < 9; ++ { .Square(&) // 2^20 - 2^10 } .Multiply(&, &) // 2^20 - 2^0 .Square(&) // 2^21 - 2^1 for := 0; < 19; ++ { .Square(&) // 2^40 - 2^20 } .Multiply(&, &) // 2^40 - 2^0 .Square(&) // 2^41 - 2^1 for := 0; < 9; ++ { .Square(&) // 2^50 - 2^10 } .Multiply(&, &) // 2^50 - 2^0 .Square(&) // 2^51 - 2^1 for := 0; < 49; ++ { .Square(&) // 2^100 - 2^50 } .Multiply(&, &) // 2^100 - 2^0 .Square(&) // 2^101 - 2^1 for := 0; < 99; ++ { .Square(&) // 2^200 - 2^100 } .Multiply(&, &) // 2^200 - 2^0 .Square(&) // 2^201 - 2^1 for := 0; < 49; ++ { .Square(&) // 2^250 - 2^50 } .Multiply(&, &) // 2^250 - 2^0 .Square(&) // 2^251 - 2^1 .Square(&) // 2^252 - 2^2 .Square(&) // 2^253 - 2^3 .Square(&) // 2^254 - 2^4 .Square(&) // 2^255 - 2^5 return .Multiply(&, &) // 2^255 - 21 } // Set sets v = a, and returns v. func ( *Element) ( *Element) *Element { * = * return } // SetBytes sets v to x, which must be a 32-byte little-endian encoding. // // Consistent with RFC 7748, the most significant bit (the high bit of the // last byte) is ignored, and non-canonical values (2^255-19 through 2^255-1) // are accepted. Note that this is laxer than specified by RFC 8032. func ( *Element) ( []byte) *Element { if len() != 32 { panic("edwards25519: invalid field element input size") } // Bits 0:51 (bytes 0:8, bits 0:64, shift 0, mask 51). .l0 = binary.LittleEndian.Uint64([0:8]) .l0 &= maskLow51Bits // Bits 51:102 (bytes 6:14, bits 48:112, shift 3, mask 51). .l1 = binary.LittleEndian.Uint64([6:14]) >> 3 .l1 &= maskLow51Bits // Bits 102:153 (bytes 12:20, bits 96:160, shift 6, mask 51). .l2 = binary.LittleEndian.Uint64([12:20]) >> 6 .l2 &= maskLow51Bits // Bits 153:204 (bytes 19:27, bits 152:216, shift 1, mask 51). .l3 = binary.LittleEndian.Uint64([19:27]) >> 1 .l3 &= maskLow51Bits // Bits 204:251 (bytes 24:32, bits 192:256, shift 12, mask 51). // Note: not bytes 25:33, shift 4, to avoid overread. .l4 = binary.LittleEndian.Uint64([24:32]) >> 12 .l4 &= maskLow51Bits return } // Bytes returns the canonical 32-byte little-endian encoding of v. func ( *Element) () []byte { // This function is outlined to make the allocations inline in the caller // rather than happen on the heap. var [32]byte return .bytes(&) } func ( *Element) ( *[32]byte) []byte { := * .reduce() var [8]byte for , := range [5]uint64{.l0, .l1, .l2, .l3, .l4} { := * 51 binary.LittleEndian.PutUint64([:], <<uint(%8)) for , := range { := /8 + if >= len() { break } [] |= } } return [:] } // Equal returns 1 if v and u are equal, and 0 otherwise. func ( *Element) ( *Element) int { , := .Bytes(), .Bytes() return subtle.ConstantTimeCompare(, ) } // mask64Bits returns 0xffffffff if cond is 1, and 0 otherwise. func mask64Bits( int) uint64 { return ^(uint64() - 1) } // Select sets v to a if cond == 1, and to b if cond == 0. func ( *Element) (, *Element, int) *Element { := mask64Bits() .l0 = ( & .l0) | (^ & .l0) .l1 = ( & .l1) | (^ & .l1) .l2 = ( & .l2) | (^ & .l2) .l3 = ( & .l3) | (^ & .l3) .l4 = ( & .l4) | (^ & .l4) return } // Swap swaps v and u if cond == 1 or leaves them unchanged if cond == 0, and returns v. func ( *Element) ( *Element, int) { := mask64Bits() := & (.l0 ^ .l0) .l0 ^= .l0 ^= = & (.l1 ^ .l1) .l1 ^= .l1 ^= = & (.l2 ^ .l2) .l2 ^= .l2 ^= = & (.l3 ^ .l3) .l3 ^= .l3 ^= = & (.l4 ^ .l4) .l4 ^= .l4 ^= } // IsNegative returns 1 if v is negative, and 0 otherwise. func ( *Element) () int { return int(.Bytes()[0] & 1) } // Absolute sets v to |u|, and returns v. func ( *Element) ( *Element) *Element { return .Select(new(Element).Negate(), , .IsNegative()) } // Multiply sets v = x * y, and returns v. func ( *Element) (, *Element) *Element { feMul(, , ) return } // Square sets v = x * x, and returns v. func ( *Element) ( *Element) *Element { feSquare(, ) return } // Mult32 sets v = x * y, and returns v. func ( *Element) ( *Element, uint32) *Element { , := mul51(.l0, ) , := mul51(.l1, ) , := mul51(.l2, ) , := mul51(.l3, ) , := mul51(.l4, ) .l0 = + 19* // carried over per the reduction identity .l1 = + .l2 = + .l3 = + .l4 = + // The hi portions are going to be only 32 bits, plus any previous excess, // so we can skip the carry propagation. return } // mul51 returns lo + hi * 2⁵¹ = a * b. func mul51( uint64, uint32) ( uint64, uint64) { , := bits.Mul64(, uint64()) = & maskLow51Bits = ( << 13) | ( >> 51) return } // Pow22523 set v = x^((p-5)/8), and returns v. (p-5)/8 is 2^252-3. func ( *Element) ( *Element) *Element { var , , Element .Square() // x^2 .Square(&) // x^4 .Square(&) // x^8 .Multiply(, &) // x^9 .Multiply(&, &) // x^11 .Square(&) // x^22 .Multiply(&, &) // x^31 .Square(&) // x^62 for := 1; < 5; ++ { // x^992 .Square(&) } .Multiply(&, &) // x^1023 -> 1023 = 2^10 - 1 .Square(&) // 2^11 - 2 for := 1; < 10; ++ { // 2^20 - 2^10 .Square(&) } .Multiply(&, &) // 2^20 - 1 .Square(&) // 2^21 - 2 for := 1; < 20; ++ { // 2^40 - 2^20 .Square(&) } .Multiply(&, &) // 2^40 - 1 .Square(&) // 2^41 - 2 for := 1; < 10; ++ { // 2^50 - 2^10 .Square(&) } .Multiply(&, &) // 2^50 - 1 .Square(&) // 2^51 - 2 for := 1; < 50; ++ { // 2^100 - 2^50 .Square(&) } .Multiply(&, &) // 2^100 - 1 .Square(&) // 2^101 - 2 for := 1; < 100; ++ { // 2^200 - 2^100 .Square(&) } .Multiply(&, &) // 2^200 - 1 .Square(&) // 2^201 - 2 for := 1; < 50; ++ { // 2^250 - 2^50 .Square(&) } .Multiply(&, &) // 2^250 - 1 .Square(&) // 2^251 - 2 .Square(&) // 2^252 - 4 return .Multiply(&, ) // 2^252 - 3 -> x^(2^252-3) } // sqrtM1 is 2^((p-1)/4), which squared is equal to -1 by Euler's Criterion. var sqrtM1 = &Element{1718705420411056, 234908883556509, 2233514472574048, 2117202627021982, 765476049583133} // SqrtRatio sets r to the non-negative square root of the ratio of u and v. // // If u/v is square, SqrtRatio returns r and 1. If u/v is not square, SqrtRatio // sets r according to Section 4.3 of draft-irtf-cfrg-ristretto255-decaf448-00, // and returns r and 0. func ( *Element) (, *Element) ( *Element, int) { var , Element // r = (u * v3) * (u * v7)^((p-5)/8) := .Square() := .Multiply(, .Multiply(, )) := .Multiply(, .Square()) .Multiply(, .Pow22523()) := .Multiply(, .Square()) // check = v * r^2 := .Negate() := .Equal() := .Equal() := .Equal(.Multiply(, sqrtM1)) := .Multiply(, sqrtM1) // r_prime = SQRT_M1 * r // r = CT_SELECT(r_prime IF flipped_sign_sqrt | flipped_sign_sqrt_i ELSE r) .Select(, , |) .Absolute() // Choose the nonnegative square root. return , | }