// 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 fieldimport ()// 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.typeElementstruct {// 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) - 1var feZero = &Element{0, 0, 0, 0, 0}// Zero sets v = 0, and returns v.func ( *Element) () *Element { * = *feZeroreturn}var feOne = &Element{1, 0, 0, 0, 0}// One sets v = 1, and returns v.func ( *Element) () *Element { * = *feOnereturn}// 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 & maskLow51Bitsreturn}// 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) - .l4return .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^1for := 0; < 4; ++ { .Square(&) // 2^10 - 2^5 } .Multiply(&, &) // 2^10 - 2^0 .Square(&) // 2^11 - 2^1for := 0; < 9; ++ { .Square(&) // 2^20 - 2^10 } .Multiply(&, &) // 2^20 - 2^0 .Square(&) // 2^21 - 2^1for := 0; < 19; ++ { .Square(&) // 2^40 - 2^20 } .Multiply(&, &) // 2^40 - 2^0 .Square(&) // 2^41 - 2^1for := 0; < 9; ++ { .Square(&) // 2^50 - 2^10 } .Multiply(&, &) // 2^50 - 2^0 .Square(&) // 2^51 - 2^1for := 0; < 49; ++ { .Square(&) // 2^100 - 2^50 } .Multiply(&, &) // 2^100 - 2^0 .Square(&) // 2^101 - 2^1for := 0; < 99; ++ { .Square(&) // 2^200 - 2^100 } .Multiply(&, &) // 2^200 - 2^0 .Square(&) // 2^201 - 2^1for := 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^5return .Multiply(&, &) // 2^255 - 21}// Set sets v = a, and returns v.func ( *Element) ( *Element) *Element { * = *return}// SetBytes sets v to x, where x is a 32-byte little-endian encoding. If x is// not of the right length, SetBytes returns nil and an error, and the// receiver is unchanged.//// 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, but// consistent with most Ed25519 implementations.func ( *Element) ( []byte) (*Element, error) {iflen() != 32 {returnnil, errors.New("edwards25519: invalid field element input size") }// Bits 0:51 (bytes 0:8, bits 0:64, shift 0, mask 51). .l0 = byteorder.LeUint64([0:8]) .l0 &= maskLow51Bits// Bits 51:102 (bytes 6:14, bits 48:112, shift 3, mask 51). .l1 = byteorder.LeUint64([6:14]) >> 3 .l1 &= maskLow51Bits// Bits 102:153 (bytes 12:20, bits 96:160, shift 6, mask 51). .l2 = byteorder.LeUint64([12:20]) >> 6 .l2 &= maskLow51Bits// Bits 153:204 (bytes 19:27, bits 152:216, shift 1, mask 51). .l3 = byteorder.LeUint64([19:27]) >> 1 .l3 &= maskLow51Bits// Bits 204:255 (bytes 24:32, bits 192:256, shift 12, mask 51). // Note: not bytes 25:33, shift 4, to avoid overread. .l4 = byteorder.LeUint64([24:32]) >> 12 .l4 &= maskLow51Bitsreturn , nil}// 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]bytereturn .bytes(&)}func ( *Element) ( *[32]byte) []byte { := * .reduce()var [8]bytefor , := range [5]uint64{.l0, .l1, .l2, .l3, .l4} { := * 51byteorder.LePutUint64([:], <<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()returnsubtle.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 {returnint(.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^62for := 1; < 5; ++ { // x^992 .Square(&) } .Multiply(&, &) // x^1023 -> 1023 = 2^10 - 1 .Square(&) // 2^11 - 2for := 1; < 10; ++ { // 2^20 - 2^10 .Square(&) } .Multiply(&, &) // 2^20 - 1 .Square(&) // 2^21 - 2for := 1; < 20; ++ { // 2^40 - 2^20 .Square(&) } .Multiply(&, &) // 2^40 - 1 .Square(&) // 2^41 - 2for := 1; < 10; ++ { // 2^50 - 2^10 .Square(&) } .Multiply(&, &) // 2^50 - 1 .Square(&) // 2^51 - 2for := 1; < 50; ++ { // 2^100 - 2^50 .Square(&) } .Multiply(&, &) // 2^100 - 1 .Square(&) // 2^101 - 2for := 1; < 100; ++ { // 2^200 - 2^100 .Square(&) } .Multiply(&, &) // 2^200 - 1 .Square(&) // 2^201 - 2for := 1; < 50; ++ { // 2^250 - 2^50 .Square(&) } .Multiply(&, &) // 2^250 - 1 .Square(&) // 2^251 - 2 .Square(&) // 2^252 - 4return .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) { := new(Element)// r = (u * v3) * (u * v7)^((p-5)/8) := new(Element).Square() := new(Element).Multiply(, .Multiply(, )) := new(Element).Multiply(, .Square()) := new(Element).Multiply(, .Pow22523()) := new(Element).Multiply(, .Square()) // check = v * r^2 := new(Element).Negate() := .Equal() := .Equal() := .Equal(.Multiply(, sqrtM1)) := new(Element).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 , | }
The pages are generated with Goldsv0.6.9-preview. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds.