package ristretto import ( "crypto/rand" "crypto/sha512" "encoding/base64" "encoding/binary" "fmt" // Required for FieldElement.[Set]BigInt(). Obviously not used for actual // implementation, as operations on big.Ints are not constant-time. "math/big" ) // A number modulo the prime l, where l is the order of the Ristretto group // over Edwards25519. // // The scalar s is represented as an array s[0], ... s[7] with 0 <= s[i] < 2^32 // and s = s[0] + s[1] * 2^32 + s[2] * 2^64 + ... + s[7] * 2^224. type Scalar [8]uint32 var ( scZero Scalar scOne = Scalar{ 1, 0, 0, 0, 0, 0, 0, 0, } scL = Scalar{ 0x5cf5d3ed, 0x5812631a, 0xa2f79cd6, 0x14def9de, 0x00000000, 0x00000000, 0x00000000, 0x10000000, } ) // Encode s little endian into buf. Returns s. func (s *Scalar) BytesInto(buf *[32]byte) *Scalar { buf[0] = uint8(s[0]) buf[1] = uint8(s[0] >> 8) buf[2] = uint8(s[0] >> 16) buf[3] = uint8(s[0] >> 24) buf[4] = uint8(s[1]) buf[5] = uint8(s[1] >> 8) buf[6] = uint8(s[1] >> 16) buf[7] = uint8(s[1] >> 24) buf[8] = uint8(s[2]) buf[9] = uint8(s[2] >> 8) buf[10] = uint8(s[2] >> 16) buf[11] = uint8(s[2] >> 24) buf[12] = uint8(s[3]) buf[13] = uint8(s[3] >> 8) buf[14] = uint8(s[3] >> 16) buf[15] = uint8(s[3] >> 24) buf[16] = uint8(s[4]) buf[17] = uint8(s[4] >> 8) buf[18] = uint8(s[4] >> 16) buf[19] = uint8(s[4] >> 24) buf[20] = uint8(s[5]) buf[21] = uint8(s[5] >> 8) buf[22] = uint8(s[5] >> 16) buf[23] = uint8(s[5] >> 24) buf[24] = uint8(s[6]) buf[25] = uint8(s[6] >> 8) buf[26] = uint8(s[6] >> 16) buf[27] = uint8(s[6] >> 24) buf[28] = uint8(s[7]) buf[29] = uint8(s[7] >> 8) buf[30] = uint8(s[7] >> 16) buf[31] = uint8(s[7] >> 24) return s } // Bytes() returns a little-endian packed version of s. See also BytesInto(). func (s *Scalar) Bytes() []byte { var ret [32]byte s.BytesInto(&ret) return ret[:] } // Sets s to x mod l, where x is interpreted little endian and the // top 3 bits are ignored. Returns s. func (s *Scalar) SetBytes(x *[32]byte) *Scalar { s[0] = load4u32(x[0:]) s[1] = load4u32(x[4:]) s[2] = load4u32(x[8:]) s[3] = load4u32(x[12:]) s[4] = load4u32(x[16:]) s[5] = load4u32(x[20:]) s[6] = load4u32(x[24:]) s[7] = load4u32(x[28:]) & 0x1fffffff return s.Sub(s, &scL) } // Sets s to -a. Returns s. func (s *Scalar) Neg(a *Scalar) *Scalar { return s.Sub(&scZero, a) } // Sets s to a + b. Returns s. func (s *Scalar) Add(a, b *Scalar) *Scalar { carry := uint64(a[0]) + uint64(b[0]) s[0] = uint32(carry) carry = uint64(a[1]) + uint64(b[1]) + (carry >> 32) s[1] = uint32(carry) carry = uint64(a[2]) + uint64(b[2]) + (carry >> 32) s[2] = uint32(carry) carry = uint64(a[3]) + uint64(b[3]) + (carry >> 32) s[3] = uint32(carry) carry = uint64(a[4]) + uint64(b[4]) + (carry >> 32) s[4] = uint32(carry) carry = uint64(a[5]) + uint64(b[5]) + (carry >> 32) s[5] = uint32(carry) carry = uint64(a[6]) + uint64(b[6]) + (carry >> 32) s[6] = uint32(carry) carry = uint64(a[7]) + uint64(b[7]) + (carry >> 32) s[7] = uint32(carry) return s.Sub(s, &scL) } // Sets s to a - b. Returns s. func (s *Scalar) Sub(a, b *Scalar) *Scalar { borrow := uint64(a[0]) - uint64(b[0]) s0 := uint32(borrow) borrow = uint64(a[1]) - uint64(b[1]) - (borrow >> 63) s1 := uint32(borrow) borrow = uint64(a[2]) - uint64(b[2]) - (borrow >> 63) s2 := uint32(borrow) borrow = uint64(a[3]) - uint64(b[3]) - (borrow >> 63) s3 := uint32(borrow) borrow = uint64(a[4]) - uint64(b[4]) - (borrow >> 63) s4 := uint32(borrow) borrow = uint64(a[5]) - uint64(b[5]) - (borrow >> 63) s5 := uint32(borrow) borrow = uint64(a[6]) - uint64(b[6]) - (borrow >> 63) s6 := uint32(borrow) borrow = uint64(a[7]) - uint64(b[7]) - (borrow >> 63) s7 := uint32(borrow) // Add l if underflown ufMask := ((borrow >> 63) ^ 1) - 1 carry := uint64(s0) + (ufMask & uint64(0x5CF5D3ED)) s0 = uint32(carry) carry = uint64(s1) + (carry >> 32) + (ufMask & uint64(0x5812631A)) s1 = uint32(carry) carry = uint64(s2) + (carry >> 32) + (ufMask & uint64(0xA2F79CD6)) s2 = uint32(carry) carry = uint64(s3) + (carry >> 32) + (ufMask & uint64(0x14DEF9DE)) s3 = uint32(carry) carry = uint64(s4) + (carry >> 32) s4 = uint32(carry) carry = uint64(s5) + (carry >> 32) s5 = uint32(carry) carry = uint64(s6) + (carry >> 32) s6 = uint32(carry) carry = uint64(s7) + (carry >> 32) + (ufMask & 0x10000000) s7 = uint32(carry) s[0] = s0 s[1] = s1 s[2] = s2 s[3] = s3 s[4] = s4 s[5] = s5 s[6] = s6 s[7] = s7 return s } // Returns s as a big.Int. // // Warning: operations on big.Ints are not constant-time: do not use them // for cryptography unless you're sure this is not an issue. func (s *Scalar) BigInt() *big.Int { var ret big.Int var buf, rBuf [32]byte s.BytesInto(&buf) for i := 0; i < 32; i++ { rBuf[i] = buf[31-i] } return ret.SetBytes(rBuf[:]) } // Sets s to x modulo l. // // Warning: operations on big.Ints are not constant-time: do not use them // for cryptography unless you're sure this is not an issue. func (s *Scalar) SetBigInt(x *big.Int) *Scalar { var v, biL big.Int biL.SetString( "1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed", 16) buf := v.Mod(x, &biL).Bytes() var rBuf [32]byte for i := 0; i < len(buf) && i < 32; i++ { rBuf[i] = buf[len(buf)-i-1] } return s.SetBytes(&rBuf) } // Sets s to x. func (s *Scalar) SetUint64(x uint64) *Scalar { var rBuf [32]byte binary.LittleEndian.PutUint64(rBuf[:], x) return s.SetBytes(&rBuf) } // Sets s to t. Returns s. func (s *Scalar) Set(t *Scalar) *Scalar { copy(s[:], t[:]) return s } // Sets s to 0. Returns s. func (s *Scalar) SetZero() *Scalar { return s.Set(&scZero) } // Sets s to 1. Returns s. func (s *Scalar) SetOne() *Scalar { return s.Set(&scOne) } // Sets s to a * b - c. Returns s. func (s *Scalar) MulSub(a, b, c *Scalar) *Scalar { a0 := int64(a[0] & 0x1fffff) a1 := int64(((a[0] >> 21) | (a[1] << 11)) & 0x1fffff) a2 := int64((a[1] >> 10) & 0x1fffff) a3 := int64(((a[1] >> 31) | (a[2] << 1)) & 0x1fffff) a4 := int64(((a[2] >> 20) | (a[3] << 12)) & 0x1fffff) a5 := int64((a[3] >> 9) & 0x1fffff) a6 := int64(((a[3] >> 30) | (a[4] << 2)) & 0x1fffff) a7 := int64(((a[4] >> 19) | (a[5] << 13)) & 0x1fffff) a8 := int64((a[5] >> 8) & 0x1fffff) a9 := int64(((a[5] >> 29) | (a[6] << 3)) & 0x1fffff) a10 := int64(((a[6] >> 18) | (a[7] << 14)) & 0x1fffff) a11 := int64((a[7] >> 7)) b0 := int64(b[0] & 0x1fffff) b1 := int64(((b[0] >> 21) | (b[1] << 11)) & 0x1fffff) b2 := int64((b[1] >> 10) & 0x1fffff) b3 := int64(((b[1] >> 31) | (b[2] << 1)) & 0x1fffff) b4 := int64(((b[2] >> 20) | (b[3] << 12)) & 0x1fffff) b5 := int64((b[3] >> 9) & 0x1fffff) b6 := int64(((b[3] >> 30) | (b[4] << 2)) & 0x1fffff) b7 := int64(((b[4] >> 19) | (b[5] << 13)) & 0x1fffff) b8 := int64((b[5] >> 8) & 0x1fffff) b9 := int64(((b[5] >> 29) | (b[6] << 3)) & 0x1fffff) b10 := int64(((b[6] >> 18) | (b[7] << 14)) & 0x1fffff) b11 := int64((b[7] >> 7)) c0 := int64(c[0] & 0x1fffff) c1 := int64(((c[0] >> 21) | (c[1] << 11)) & 0x1fffff) c2 := int64((c[1] >> 10) & 0x1fffff) c3 := int64(((c[1] >> 31) | (c[2] << 1)) & 0x1fffff) c4 := int64(((c[2] >> 20) | (c[3] << 12)) & 0x1fffff) c5 := int64((c[3] >> 9) & 0x1fffff) c6 := int64(((c[3] >> 30) | (c[4] << 2)) & 0x1fffff) c7 := int64(((c[4] >> 19) | (c[5] << 13)) & 0x1fffff) c8 := int64((c[5] >> 8) & 0x1fffff) c9 := int64(((c[5] >> 29) | (c[6] << 3)) & 0x1fffff) c10 := int64(((c[6] >> 18) | (c[7] << 14)) & 0x1fffff) c11 := int64((c[7] >> 7)) return s.reduceAfterMul( -c0+a0*b0, -c1+a0*b1+a1*b0, -c2+a0*b2+a1*b1+a2*b0, -c3+a0*b3+a1*b2+a2*b1+a3*b0, -c4+a0*b4+a1*b3+a2*b2+a3*b1+a4*b0, -c5+a0*b5+a1*b4+a2*b3+a3*b2+a4*b1+a5*b0, -c6+a0*b6+a1*b5+a2*b4+a3*b3+a4*b2+a5*b1+a6*b0, -c7+a0*b7+a1*b6+a2*b5+a3*b4+a4*b3+a5*b2+a6*b1+a7*b0, -c8+a0*b8+a1*b7+a2*b6+a3*b5+a4*b4+a5*b3+a6*b2+a7*b1+a8*b0, -c9+a0*b9+a1*b8+a2*b7+a3*b6+a4*b5+a5*b4+a6*b3+a7*b2+a8*b1+a9*b0, -c10+a0*b10+a1*b9+a2*b8+a3*b7+a4*b6+a5*b5+a6*b4+a7*b3+a8*b2+a9*b1+a10*b0, -c11+a0*b11+a1*b10+a2*b9+a3*b8+a4*b7+a5*b6+a6*b5+a7*b4+a8*b3+a9*b2+a10*b1+a11*b0, a1*b11+a2*b10+a3*b9+a4*b8+a5*b7+a6*b6+a7*b5+a8*b4+a9*b3+a10*b2+a11*b1, a2*b11+a3*b10+a4*b9+a5*b8+a6*b7+a7*b6+a8*b5+a9*b4+a10*b3+a11*b2, a3*b11+a4*b10+a5*b9+a6*b8+a7*b7+a8*b6+a9*b5+a10*b4+a11*b3, a4*b11+a5*b10+a6*b9+a7*b8+a8*b7+a9*b6+a10*b5+a11*b4, a5*b11+a6*b10+a7*b9+a8*b8+a9*b7+a10*b6+a11*b5, a6*b11+a7*b10+a8*b9+a9*b8+a10*b7+a11*b6, a7*b11+a8*b10+a9*b9+a10*b8+a11*b7, a8*b11+a9*b10+a10*b9+a11*b8, a9*b11+a10*b10+a11*b9, a10*b11+a11*b10, a11*b11) } // Sets s to a * b + c. Returns s. func (s *Scalar) MulAdd(a, b, c *Scalar) *Scalar { a0 := int64(a[0] & 0x1fffff) a1 := int64(((a[0] >> 21) | (a[1] << 11)) & 0x1fffff) a2 := int64((a[1] >> 10) & 0x1fffff) a3 := int64(((a[1] >> 31) | (a[2] << 1)) & 0x1fffff) a4 := int64(((a[2] >> 20) | (a[3] << 12)) & 0x1fffff) a5 := int64((a[3] >> 9) & 0x1fffff) a6 := int64(((a[3] >> 30) | (a[4] << 2)) & 0x1fffff) a7 := int64(((a[4] >> 19) | (a[5] << 13)) & 0x1fffff) a8 := int64((a[5] >> 8) & 0x1fffff) a9 := int64(((a[5] >> 29) | (a[6] << 3)) & 0x1fffff) a10 := int64(((a[6] >> 18) | (a[7] << 14)) & 0x1fffff) a11 := int64((a[7] >> 7)) b0 := int64(b[0] & 0x1fffff) b1 := int64(((b[0] >> 21) | (b[1] << 11)) & 0x1fffff) b2 := int64((b[1] >> 10) & 0x1fffff) b3 := int64(((b[1] >> 31) | (b[2] << 1)) & 0x1fffff) b4 := int64(((b[2] >> 20) | (b[3] << 12)) & 0x1fffff) b5 := int64((b[3] >> 9) & 0x1fffff) b6 := int64(((b[3] >> 30) | (b[4] << 2)) & 0x1fffff) b7 := int64(((b[4] >> 19) | (b[5] << 13)) & 0x1fffff) b8 := int64((b[5] >> 8) & 0x1fffff) b9 := int64(((b[5] >> 29) | (b[6] << 3)) & 0x1fffff) b10 := int64(((b[6] >> 18) | (b[7] << 14)) & 0x1fffff) b11 := int64((b[7] >> 7)) c0 := int64(c[0] & 0x1fffff) c1 := int64(((c[0] >> 21) | (c[1] << 11)) & 0x1fffff) c2 := int64((c[1] >> 10) & 0x1fffff) c3 := int64(((c[1] >> 31) | (c[2] << 1)) & 0x1fffff) c4 := int64(((c[2] >> 20) | (c[3] << 12)) & 0x1fffff) c5 := int64((c[3] >> 9) & 0x1fffff) c6 := int64(((c[3] >> 30) | (c[4] << 2)) & 0x1fffff) c7 := int64(((c[4] >> 19) | (c[5] << 13)) & 0x1fffff) c8 := int64((c[5] >> 8) & 0x1fffff) c9 := int64(((c[5] >> 29) | (c[6] << 3)) & 0x1fffff) c10 := int64(((c[6] >> 18) | (c[7] << 14)) & 0x1fffff) c11 := int64((c[7] >> 7)) return s.reduceAfterMul( c0+a0*b0, c1+a0*b1+a1*b0, c2+a0*b2+a1*b1+a2*b0, c3+a0*b3+a1*b2+a2*b1+a3*b0, c4+a0*b4+a1*b3+a2*b2+a3*b1+a4*b0, c5+a0*b5+a1*b4+a2*b3+a3*b2+a4*b1+a5*b0, c6+a0*b6+a1*b5+a2*b4+a3*b3+a4*b2+a5*b1+a6*b0, c7+a0*b7+a1*b6+a2*b5+a3*b4+a4*b3+a5*b2+a6*b1+a7*b0, c8+a0*b8+a1*b7+a2*b6+a3*b5+a4*b4+a5*b3+a6*b2+a7*b1+a8*b0, c9+a0*b9+a1*b8+a2*b7+a3*b6+a4*b5+a5*b4+a6*b3+a7*b2+a8*b1+a9*b0, c10+a0*b10+a1*b9+a2*b8+a3*b7+a4*b6+a5*b5+a6*b4+a7*b3+a8*b2+a9*b1+a10*b0, c11+a0*b11+a1*b10+a2*b9+a3*b8+a4*b7+a5*b6+a6*b5+a7*b4+a8*b3+a9*b2+a10*b1+a11*b0, a1*b11+a2*b10+a3*b9+a4*b8+a5*b7+a6*b6+a7*b5+a8*b4+a9*b3+a10*b2+a11*b1, a2*b11+a3*b10+a4*b9+a5*b8+a6*b7+a7*b6+a8*b5+a9*b4+a10*b3+a11*b2, a3*b11+a4*b10+a5*b9+a6*b8+a7*b7+a8*b6+a9*b5+a10*b4+a11*b3, a4*b11+a5*b10+a6*b9+a7*b8+a8*b7+a9*b6+a10*b5+a11*b4, a5*b11+a6*b10+a7*b9+a8*b8+a9*b7+a10*b6+a11*b5, a6*b11+a7*b10+a8*b9+a9*b8+a10*b7+a11*b6, a7*b11+a8*b10+a9*b9+a10*b8+a11*b7, a8*b11+a9*b10+a10*b9+a11*b8, a9*b11+a10*b10+a11*b9, a10*b11+a11*b10, a11*b11) } // Derive sets s to the half-length scalar derived from the given buffer // using SHA512. Returns s // // Warning: half-length scalars are insecure in almost every application. func (s *Scalar) DeriveShort(buf []byte) *Scalar { h := sha512.Sum512(buf) s[0] = load4u32(h[0:]) s[1] = load4u32(h[4:]) s[2] = load4u32(h[8:]) s[3] = load4u32(h[12:]) s[4] = 0 s[5] = 0 s[6] = 0 s[7] = 0 return s } // Derive sets s to the scalar derived from the given buffer using SHA512 and // Scalar.SetReduced() Returns s. func (s *Scalar) Derive(buf []byte) *Scalar { var sBuf [64]byte h := sha512.Sum512(buf) copy(sBuf[:], h[:]) return s.SetReduced(&sBuf) } // Sets s to t mod l, where t is interpreted little endian. Returns s. func (s *Scalar) SetReduced(t *[64]byte) *Scalar { t0 := 0x1FFFFF & load3(t[:]) t1 := 0x1FFFFF & (load4(t[2:]) >> 5) t2 := 0x1FFFFF & (load3(t[5:]) >> 2) t3 := 0x1FFFFF & (load4(t[7:]) >> 7) t4 := 0x1FFFFF & (load4(t[10:]) >> 4) t5 := 0x1FFFFF & (load3(t[13:]) >> 1) t6 := 0x1FFFFF & (load4(t[15:]) >> 6) t7 := 0x1FFFFF & (load3(t[18:]) >> 3) t8 := 0x1FFFFF & load3(t[21:]) t9 := 0x1FFFFF & (load4(t[23:]) >> 5) t10 := 0x1FFFFF & (load3(t[26:]) >> 2) t11 := 0x1FFFFF & (load4(t[28:]) >> 7) t12 := 0x1FFFFF & (load4(t[31:]) >> 4) t13 := 0x1FFFFF & (load3(t[34:]) >> 1) t14 := 0x1FFFFF & (load4(t[36:]) >> 6) t15 := 0x1FFFFF & (load3(t[39:]) >> 3) t16 := 0x1FFFFF & load3(t[42:]) t17 := 0x1FFFFF & (load4(t[44:]) >> 5) t18 := 0x1FFFFF & (load3(t[47:]) >> 2) t19 := 0x1FFFFF & (load4(t[49:]) >> 7) t20 := 0x1FFFFF & (load4(t[52:]) >> 4) t21 := 0x1FFFFF & (load3(t[55:]) >> 1) t22 := 0x1FFFFF & (load4(t[57:]) >> 6) t23 := (load4(t[60:]) >> 3) t11 += t23 * 666643 t12 += t23 * 470296 t13 += t23 * 654183 t14 -= t23 * 997805 t15 += t23 * 136657 t16 -= t23 * 683901 t23 = 0 t10 += t22 * 666643 t11 += t22 * 470296 t12 += t22 * 654183 t13 -= t22 * 997805 t14 += t22 * 136657 t15 -= t22 * 683901 t22 = 0 t9 += t21 * 666643 t10 += t21 * 470296 t11 += t21 * 654183 t12 -= t21 * 997805 t13 += t21 * 136657 t14 -= t21 * 683901 t21 = 0 t8 += t20 * 666643 t9 += t20 * 470296 t10 += t20 * 654183 t11 -= t20 * 997805 t12 += t20 * 136657 t13 -= t20 * 683901 t20 = 0 t7 += t19 * 666643 t8 += t19 * 470296 t9 += t19 * 654183 t10 -= t19 * 997805 t11 += t19 * 136657 t12 -= t19 * 683901 t19 = 0 t6 += t18 * 666643 t7 += t18 * 470296 t8 += t18 * 654183 t9 -= t18 * 997805 t10 += t18 * 136657 t11 -= t18 * 683901 t18 = 0 var carry [17]int64 carry[6] = (t6 + (1 << 20)) >> 21 t7 += carry[6] t6 -= carry[6] << 21 carry[8] = (t8 + (1 << 20)) >> 21 t9 += carry[8] t8 -= carry[8] << 21 carry[10] = (t10 + (1 << 20)) >> 21 t11 += carry[10] t10 -= carry[10] << 21 carry[12] = (t12 + (1 << 20)) >> 21 t13 += carry[12] t12 -= carry[12] << 21 carry[14] = (t14 + (1 << 20)) >> 21 t15 += carry[14] t14 -= carry[14] << 21 carry[16] = (t16 + (1 << 20)) >> 21 t17 += carry[16] t16 -= carry[16] << 21 carry[7] = (t7 + (1 << 20)) >> 21 t8 += carry[7] t7 -= carry[7] << 21 carry[9] = (t9 + (1 << 20)) >> 21 t10 += carry[9] t9 -= carry[9] << 21 carry[11] = (t11 + (1 << 20)) >> 21 t12 += carry[11] t11 -= carry[11] << 21 carry[13] = (t13 + (1 << 20)) >> 21 t14 += carry[13] t13 -= carry[13] << 21 carry[15] = (t15 + (1 << 20)) >> 21 t16 += carry[15] t15 -= carry[15] << 21 t5 += t17 * 666643 t6 += t17 * 470296 t7 += t17 * 654183 t8 -= t17 * 997805 t9 += t17 * 136657 t10 -= t17 * 683901 t17 = 0 t4 += t16 * 666643 t5 += t16 * 470296 t6 += t16 * 654183 t7 -= t16 * 997805 t8 += t16 * 136657 t9 -= t16 * 683901 t16 = 0 t3 += t15 * 666643 t4 += t15 * 470296 t5 += t15 * 654183 t6 -= t15 * 997805 t7 += t15 * 136657 t8 -= t15 * 683901 t15 = 0 t2 += t14 * 666643 t3 += t14 * 470296 t4 += t14 * 654183 t5 -= t14 * 997805 t6 += t14 * 136657 t7 -= t14 * 683901 t14 = 0 t1 += t13 * 666643 t2 += t13 * 470296 t3 += t13 * 654183 t4 -= t13 * 997805 t5 += t13 * 136657 t6 -= t13 * 683901 t13 = 0 t0 += t12 * 666643 t1 += t12 * 470296 t2 += t12 * 654183 t3 -= t12 * 997805 t4 += t12 * 136657 t5 -= t12 * 683901 t12 = 0 carry[0] = (t0 + (1 << 20)) >> 21 t1 += carry[0] t0 -= carry[0] << 21 carry[2] = (t2 + (1 << 20)) >> 21 t3 += carry[2] t2 -= carry[2] << 21 carry[4] = (t4 + (1 << 20)) >> 21 t5 += carry[4] t4 -= carry[4] << 21 carry[6] = (t6 + (1 << 20)) >> 21 t7 += carry[6] t6 -= carry[6] << 21 carry[8] = (t8 + (1 << 20)) >> 21 t9 += carry[8] t8 -= carry[8] << 21 carry[10] = (t10 + (1 << 20)) >> 21 t11 += carry[10] t10 -= carry[10] << 21 carry[1] = (t1 + (1 << 20)) >> 21 t2 += carry[1] t1 -= carry[1] << 21 carry[3] = (t3 + (1 << 20)) >> 21 t4 += carry[3] t3 -= carry[3] << 21 carry[5] = (t5 + (1 << 20)) >> 21 t6 += carry[5] t5 -= carry[5] << 21 carry[7] = (t7 + (1 << 20)) >> 21 t8 += carry[7] t7 -= carry[7] << 21 carry[9] = (t9 + (1 << 20)) >> 21 t10 += carry[9] t9 -= carry[9] << 21 carry[11] = (t11 + (1 << 20)) >> 21 t12 += carry[11] t11 -= carry[11] << 21 t0 += t12 * 666643 t1 += t12 * 470296 t2 += t12 * 654183 t3 -= t12 * 997805 t4 += t12 * 136657 t5 -= t12 * 683901 t12 = 0 carry[0] = t0 >> 21 t1 += carry[0] t0 -= carry[0] << 21 carry[1] = t1 >> 21 t2 += carry[1] t1 -= carry[1] << 21 carry[2] = t2 >> 21 t3 += carry[2] t2 -= carry[2] << 21 carry[3] = t3 >> 21 t4 += carry[3] t3 -= carry[3] << 21 carry[4] = t4 >> 21 t5 += carry[4] t4 -= carry[4] << 21 carry[5] = t5 >> 21 t6 += carry[5] t5 -= carry[5] << 21 carry[6] = t6 >> 21 t7 += carry[6] t6 -= carry[6] << 21 carry[7] = t7 >> 21 t8 += carry[7] t7 -= carry[7] << 21 carry[8] = t8 >> 21 t9 += carry[8] t8 -= carry[8] << 21 carry[9] = t9 >> 21 t10 += carry[9] t9 -= carry[9] << 21 carry[10] = t10 >> 21 t11 += carry[10] t10 -= carry[10] << 21 carry[11] = t11 >> 21 t12 += carry[11] t11 -= carry[11] << 21 t0 += t12 * 666643 t1 += t12 * 470296 t2 += t12 * 654183 t3 -= t12 * 997805 t4 += t12 * 136657 t5 -= t12 * 683901 t12 = 0 carry[0] = t0 >> 21 t1 += carry[0] t0 -= carry[0] << 21 carry[1] = t1 >> 21 t2 += carry[1] t1 -= carry[1] << 21 carry[2] = t2 >> 21 t3 += carry[2] t2 -= carry[2] << 21 carry[3] = t3 >> 21 t4 += carry[3] t3 -= carry[3] << 21 carry[4] = t4 >> 21 t5 += carry[4] t4 -= carry[4] << 21 carry[5] = t5 >> 21 t6 += carry[5] t5 -= carry[5] << 21 carry[6] = t6 >> 21 t7 += carry[6] t6 -= carry[6] << 21 carry[7] = t7 >> 21 t8 += carry[7] t7 -= carry[7] << 21 carry[8] = t8 >> 21 t9 += carry[8] t8 -= carry[8] << 21 carry[9] = t9 >> 21 t10 += carry[9] t9 -= carry[9] << 21 carry[10] = t10 >> 21 t11 += carry[10] t10 -= carry[10] << 21 s[0] = uint32(t0) | uint32(t1<<21) s[1] = uint32(t1>>11) | uint32(t2<<10) | uint32(t3<<31) s[2] = uint32(t3>>1) | uint32(t4<<20) s[3] = uint32(t4>>12) | uint32(t5<<9) | uint32(t6<<30) s[4] = uint32(t6>>2) | uint32(t7<<19) s[5] = uint32(t7>>13) | uint32(t8<<8) | uint32(t9<<29) s[6] = uint32(t9>>3) | uint32(t10<<18) s[7] = uint32(t10>>14) | uint32(t11<<7) return s } // Sets s to a random scalar. Returns s. func (s *Scalar) Rand() *Scalar { var buf [64]byte if _, err := rand.Read(buf[:]); err != nil { panic(err) } return s.SetReduced(&buf) } // Sets s to a*a. Returns s. func (s *Scalar) Square(a *Scalar) *Scalar { a0 := int64(a[0] & 0x1fffff) a1 := int64(((a[0] >> 21) | (a[1] << 11)) & 0x1fffff) a2 := int64((a[1] >> 10) & 0x1fffff) a3 := int64(((a[1] >> 31) | (a[2] << 1)) & 0x1fffff) a4 := int64(((a[2] >> 20) | (a[3] << 12)) & 0x1fffff) a5 := int64((a[3] >> 9) & 0x1fffff) a6 := int64(((a[3] >> 30) | (a[4] << 2)) & 0x1fffff) a7 := int64(((a[4] >> 19) | (a[5] << 13)) & 0x1fffff) a8 := int64((a[5] >> 8) & 0x1fffff) a9 := int64(((a[5] >> 29) | (a[6] << 3)) & 0x1fffff) a10 := int64(((a[6] >> 18) | (a[7] << 14)) & 0x1fffff) a11 := int64((a[7] >> 7)) return s.reduceAfterMul( a0*a0, 2*a0*a1, 2*a0*a2+a1*a1, 2*(a0*a3+a1*a2), 2*(a0*a4+a1*a3)+a2*a2, 2*(a0*a5+a1*a4+a2*a3), 2*(a0*a6+a1*a5+a2*a4)+a3*a3, 2*(a0*a7+a1*a6+a2*a5+a3*a4), 2*(a0*a8+a1*a7+a2*a6+a3*a5)+a4*a4, 2*(a0*a9+a1*a8+a2*a7+a3*a6+a4*a5), 2*(a0*a10+a1*a9+a2*a8+a3*a7+a4*a6)+a5*a5, 2*(a0*a11+a1*a10+a2*a9+a3*a8+a4*a7+a5*a6), 2*(a1*a11+a2*a10+a3*a9+a4*a8+a5*a7)+a6*a6, 2*(a2*a11+a3*a10+a4*a9+a5*a8+a6*a7), 2*(a3*a11+a4*a10+a5*a9+a6*a8)+a7*a7, 2*(a4*a11+a5*a10+a6*a9+a7*a8), 2*(a5*a11+a6*a10+a7*a9)+a8*a8, 2*(a6*a11+a7*a10+a8*a9), 2*(a7*a11+a8*a10)+a9*a9, 2*(a8*a11+a9*a10), 2*a9*a11+a10*a10, 2*a10*a11, a11*a11) } // Sets s to a * b. Returns s. func (s *Scalar) Mul(a, b *Scalar) *Scalar { a0 := int64(a[0] & 0x1fffff) a1 := int64(((a[0] >> 21) | (a[1] << 11)) & 0x1fffff) a2 := int64((a[1] >> 10) & 0x1fffff) a3 := int64(((a[1] >> 31) | (a[2] << 1)) & 0x1fffff) a4 := int64(((a[2] >> 20) | (a[3] << 12)) & 0x1fffff) a5 := int64((a[3] >> 9) & 0x1fffff) a6 := int64(((a[3] >> 30) | (a[4] << 2)) & 0x1fffff) a7 := int64(((a[4] >> 19) | (a[5] << 13)) & 0x1fffff) a8 := int64((a[5] >> 8) & 0x1fffff) a9 := int64(((a[5] >> 29) | (a[6] << 3)) & 0x1fffff) a10 := int64(((a[6] >> 18) | (a[7] << 14)) & 0x1fffff) a11 := int64((a[7] >> 7)) b0 := int64(b[0] & 0x1fffff) b1 := int64(((b[0] >> 21) | (b[1] << 11)) & 0x1fffff) b2 := int64((b[1] >> 10) & 0x1fffff) b3 := int64(((b[1] >> 31) | (b[2] << 1)) & 0x1fffff) b4 := int64(((b[2] >> 20) | (b[3] << 12)) & 0x1fffff) b5 := int64((b[3] >> 9) & 0x1fffff) b6 := int64(((b[3] >> 30) | (b[4] << 2)) & 0x1fffff) b7 := int64(((b[4] >> 19) | (b[5] << 13)) & 0x1fffff) b8 := int64((b[5] >> 8) & 0x1fffff) b9 := int64(((b[5] >> 29) | (b[6] << 3)) & 0x1fffff) b10 := int64(((b[6] >> 18) | (b[7] << 14)) & 0x1fffff) b11 := int64((b[7] >> 7)) return s.reduceAfterMul( a0*b0, a0*b1+a1*b0, a0*b2+a1*b1+a2*b0, a0*b3+a1*b2+a2*b1+a3*b0, a0*b4+a1*b3+a2*b2+a3*b1+a4*b0, a0*b5+a1*b4+a2*b3+a3*b2+a4*b1+a5*b0, a0*b6+a1*b5+a2*b4+a3*b3+a4*b2+a5*b1+a6*b0, a0*b7+a1*b6+a2*b5+a3*b4+a4*b3+a5*b2+a6*b1+a7*b0, a0*b8+a1*b7+a2*b6+a3*b5+a4*b4+a5*b3+a6*b2+a7*b1+a8*b0, a0*b9+a1*b8+a2*b7+a3*b6+a4*b5+a5*b4+a6*b3+a7*b2+a8*b1+a9*b0, a0*b10+a1*b9+a2*b8+a3*b7+a4*b6+a5*b5+a6*b4+a7*b3+a8*b2+a9*b1+a10*b0, a0*b11+a1*b10+a2*b9+a3*b8+a4*b7+a5*b6+a6*b5+a7*b4+a8*b3+a9*b2+a10*b1+a11*b0, a1*b11+a2*b10+a3*b9+a4*b8+a5*b7+a6*b6+a7*b5+a8*b4+a9*b3+a10*b2+a11*b1, a2*b11+a3*b10+a4*b9+a5*b8+a6*b7+a7*b6+a8*b5+a9*b4+a10*b3+a11*b2, a3*b11+a4*b10+a5*b9+a6*b8+a7*b7+a8*b6+a9*b5+a10*b4+a11*b3, a4*b11+a5*b10+a6*b9+a7*b8+a8*b7+a9*b6+a10*b5+a11*b4, a5*b11+a6*b10+a7*b9+a8*b8+a9*b7+a10*b6+a11*b5, a6*b11+a7*b10+a8*b9+a9*b8+a10*b7+a11*b6, a7*b11+a8*b10+a9*b9+a10*b8+a11*b7, a8*b11+a9*b10+a10*b9+a11*b8, a9*b11+a10*b10+a11*b9, a10*b11+a11*b10, a11*b11) } // Sets s to 1/t. Returns s. func (s *Scalar) Inverse(t *Scalar) *Scalar { var t0, t1, t2, t3, t4, t5 Scalar t1.Square(t) t2.Mul(t, &t1) t0.Mul(&t1, &t2) t1.Square(&t0) t3.Square(&t1) t1.Mul(&t2, &t3) t2.Square(&t1) t3.Mul(&t0, &t2) t0.Square(&t3) t2.Mul(&t1, &t0) t0.Square(&t2) t1.Mul(&t2, &t0) t0.Square(&t1) t1.Mul(&t3, &t0) t0.Square(&t1) t3.Square(&t0) t0.Mul(&t1, &t3) t3.Mul(&t2, &t0) t0.Square(&t3) t2.Mul(&t1, &t0) t0.Square(&t2) t1.Mul(&t3, &t0) t0.Square(&t1) t3.Mul(&t1, &t0) t0.Mul(&t2, &t3) t2.Mul(&t1, &t0) t1.Square(&t2) t3.Square(&t1) t4.Square(&t3) t3.Mul(&t1, &t4) t1.Mul(&t0, &t3) t0.Mul(&t2, &t1) t2.Mul(&t1, &t0) t1.Square(&t2) t3.Square(&t1) t1.Mul(&t0, &t3) t0.Square(&t1) t3.Square(&t0) t0.Mul(&t1, &t3) t3.Mul(&t2, &t0) t0.Square(&t3) t2.Mul(&t1, &t0) t0.Square(&t2) t1.Square(&t0) t0.Mul(&t2, &t1) t1.Mul(&t3, &t0) t0.Square(&t1) t3.Square(&t0) t0.Square(&t3) t3.Square(&t0) t0.Square(&t3) t3.Square(&t0) t0.Mul(&t1, &t3) t3.Mul(&t2, &t0) t0.Square(&t3) t2.Mul(&t1, &t0) t0.Square(&t2) t1.Mul(&t2, &t0) t0.Square(&t1) t4.Mul(&t2, &t0) t0.Square(&t4) t4.Square(&t0) t0.Mul(&t1, &t4) t1.Mul(&t3, &t0) t0.Square(&t1) t3.Mul(&t1, &t0) t0.Square(&t3) t4.Square(&t0) t0.Mul(&t3, &t4) t3.Mul(&t2, &t0) t0.Square(&t3) t2.Square(&t0) t0.Square(&t2) t2.Mul(&t1, &t0) t0.Square(&t2) t1.Mul(&t3, &t0) t0.Mul(&t2, &t1) t2.Mul(&t1, &t0) t1.Square(&t2) t3.Square(&t1) t1.Mul(&t0, &t3) t0.Square(&t1) t3.Mul(&t2, &t0) t0.Mul(&t1, &t3) t1.Square(&t0) t2.Square(&t1) t1.Mul(&t0, &t2) t2.Mul(&t3, &t1) t1.Mul(&t0, &t2) t0.Mul(&t2, &t1) t2.Square(&t0) t3.Mul(&t0, &t2) t2.Square(&t3) t3.Mul(&t1, &t2) t1.Mul(&t0, &t3) t0.Square(&t1) t2.Mul(&t1, &t0) t0.Square(&t2) t4.Mul(&t2, &t0) t0.Square(&t4) t4.Square(&t0) t5.Square(&t4) t4.Square(&t5) t5.Square(&t4) t4.Square(&t5) t5.Mul(&t0, &t4) t0.Mul(&t2, &t5) t2.Mul(&t3, &t0) t0.Mul(&t1, &t2) t1.Square(&t0) t3.Mul(&t0, &t1) t1.Square(&t3) t4.Mul(&t0, &t1) t1.Square(&t4) t4.Square(&t1) t1.Square(&t4) t4.Mul(&t3, &t1) t1.Mul(&t2, &t4) t2.Square(&t1) t3.Square(&t2) t4.Square(&t3) t3.Mul(&t2, &t4) t2.Mul(&t1, &t3) t3.Mul(&t0, &t2) t0.Square(&t3) t2.Square(&t0) t0.Square(&t2) t2.Mul(&t1, &t0) t0.Mul(&t3, &t2) t1.Square(&t0) t3.Square(&t1) t4.Mul(&t1, &t3) t3.Square(&t4) t4.Square(&t3) t3.Mul(&t1, &t4) t1.Mul(&t2, &t3) t2.Square(&t1) t3.Square(&t2) t2.Mul(&t0, &t3) t0.Square(&t2) t3.Mul(&t1, &t0) t0.Square(&t3) t1.Mul(&t2, &t0) t0.Mul(&t3, &t1) t2.Square(&t0) t3.Square(&t2) t2.Square(&t3) t3.Square(&t2) t2.Mul(&t1, &t3) t1.Mul(&t0, &t2) t0.Square(&t1) t3.Square(&t0) t4.Square(&t3) t3.Mul(&t0, &t4) t0.Mul(&t1, &t3) t3.Mul(&t2, &t0) t0.Square(&t3) t2.Square(&t0) t0.Mul(&t1, &t2) t1.Square(&t0) t2.Mul(&t3, &t1) t1.Mul(&t0, &t2) t0.Square(&t1) t3.Mul(&t2, &t0) t0.Square(&t3) t2.Square(&t0) t0.Mul(&t1, &t2) t1.Mul(&t3, &t0) t2.Square(&t1) t3.Mul(&t0, &t2) t0.Mul(&t1, &t3) t1.Square(&t0) t2.Square(&t1) t4.Square(&t2) t2.Mul(&t1, &t4) t4.Square(&t2) t2.Square(&t4) t4.Square(&t2) t2.Mul(&t1, &t4) t1.Mul(&t3, &t2) t2.Square(&t1) t3.Square(&t2) t2.Mul(&t1, &t3) t3.Square(&t2) t2.Square(&t3) t3.Mul(&t1, &t2) t2.Mul(&t0, &t3) t0.Square(&t2) t3.Mul(&t2, &t0) t0.Square(&t3) t4.Square(&t0) t0.Mul(&t3, &t4) t3.Mul(&t1, &t0) t0.Square(&t3) t1.Mul(&t3, &t0) t0.Mul(&t2, &t1) for i := 0; i < 126; i++ { t0.Square(&t0) } s.Mul(&t3, &t0) return s } // IsNonZeroI returns 1 if s is non-zero and 0 otherwise. func (s *Scalar) IsNonZeroI() int32 { ret := s[0] | s[1] | s[2] | s[3] | s[4] | s[5] | s[6] | s[7] ret |= ret >> 16 ret |= ret >> 8 ret |= ret >> 4 ret |= ret >> 2 ret |= ret >> 1 return int32(ret & 1) } // EqualsI returns 1 if s is equal to a, otherwise 0. func (s *Scalar) EqualsI(a *Scalar) int32 { var b Scalar return 1 - b.Sub(s, a).IsNonZeroI() } // Equals returns whether s is equal to a. func (s *Scalar) Equals(a *Scalar) bool { var b Scalar return b.Sub(s, a).IsNonZeroI() == 0 } // Implements encoding/BinaryUnmarshaler. Use SetBytes, if convenient, instead. func (s *Scalar) UnmarshalBinary(data []byte) error { if len(data) != 32 { return fmt.Errorf("ristretto.Scalar should be 32 bytes; not %d", len(data)) } var buf [32]byte copy(buf[:], data) s.SetBytes(&buf) return nil } // Implements encoding/BinaryMarshaler. Use BytesInto, if convenient, instead. func (s *Scalar) MarshalBinary() ([]byte, error) { var buf [32]byte s.BytesInto(&buf) return buf[:], nil } func (s *Scalar) MarshalText() ([]byte, error) { enc := base64.RawURLEncoding var buf [32]byte s.BytesInto(&buf) ret := make([]byte, enc.EncodedLen(32)) enc.Encode(ret, buf[:]) return ret, nil } func (s *Scalar) UnmarshalText(txt []byte) error { enc := base64.RawURLEncoding var buf [32]byte n, err := enc.Decode(buf[:], txt) if err != nil { return err } if n != 32 { return fmt.Errorf("ristretto.Scalar should be 32 bytes; not %d", n) } s.SetBytes(&buf) return nil } func (s Scalar) String() string { text, _ := s.MarshalText() return string(text) } // Interprets a 3-byte unsigned little endian byte-slice as int64 func load3(in []byte) int64 { var r int64 r = int64(in[0]) r |= int64(in[1]) << 8 r |= int64(in[2]) << 16 return r } // Interprets a 4-byte unsigned little endian byte-slice as int64 func load4(in []byte) int64 { var r int64 r = int64(in[0]) r |= int64(in[1]) << 8 r |= int64(in[2]) << 16 r |= int64(in[3]) << 24 return r } // Interprets a 4-byte unsigned little endian byte-slice as uint32 func load4u32(in []byte) uint32 { return (uint32(in[0]) | (uint32(in[1]) << 8) | (uint32(in[2]) << 16) | (uint32(in[3]) << 24)) } // Sets s to s0 + s1 * 2^21 + s2 * 2^(21*2) + ... + s22 * s^(21*22) modulo l. // Requires |s_i| to be sufficiently small (< ~2^42). Used in Mul, Square, etc. func (s *Scalar) reduceAfterMul(s0, s1, s2, s3, s4, s5, s6, s7, s8, s9, s10, s11, s12, s13, s14, s15, s16, s17, s18, s19, s20, s21, s22 int64) *Scalar { var s23 int64 = 0 var carry [23]int64 carry[0] = (s0 + (1 << 20)) >> 21 s1 += carry[0] s0 -= carry[0] << 21 carry[2] = (s2 + (1 << 20)) >> 21 s3 += carry[2] s2 -= carry[2] << 21 carry[4] = (s4 + (1 << 20)) >> 21 s5 += carry[4] s4 -= carry[4] << 21 carry[6] = (s6 + (1 << 20)) >> 21 s7 += carry[6] s6 -= carry[6] << 21 carry[8] = (s8 + (1 << 20)) >> 21 s9 += carry[8] s8 -= carry[8] << 21 carry[10] = (s10 + (1 << 20)) >> 21 s11 += carry[10] s10 -= carry[10] << 21 carry[12] = (s12 + (1 << 20)) >> 21 s13 += carry[12] s12 -= carry[12] << 21 carry[14] = (s14 + (1 << 20)) >> 21 s15 += carry[14] s14 -= carry[14] << 21 carry[16] = (s16 + (1 << 20)) >> 21 s17 += carry[16] s16 -= carry[16] << 21 carry[18] = (s18 + (1 << 20)) >> 21 s19 += carry[18] s18 -= carry[18] << 21 carry[20] = (s20 + (1 << 20)) >> 21 s21 += carry[20] s20 -= carry[20] << 21 carry[22] = (s22 + (1 << 20)) >> 21 s23 += carry[22] s22 -= carry[22] << 21 carry[1] = (s1 + (1 << 20)) >> 21 s2 += carry[1] s1 -= carry[1] << 21 carry[3] = (s3 + (1 << 20)) >> 21 s4 += carry[3] s3 -= carry[3] << 21 carry[5] = (s5 + (1 << 20)) >> 21 s6 += carry[5] s5 -= carry[5] << 21 carry[7] = (s7 + (1 << 20)) >> 21 s8 += carry[7] s7 -= carry[7] << 21 carry[9] = (s9 + (1 << 20)) >> 21 s10 += carry[9] s9 -= carry[9] << 21 carry[11] = (s11 + (1 << 20)) >> 21 s12 += carry[11] s11 -= carry[11] << 21 carry[13] = (s13 + (1 << 20)) >> 21 s14 += carry[13] s13 -= carry[13] << 21 carry[15] = (s15 + (1 << 20)) >> 21 s16 += carry[15] s15 -= carry[15] << 21 carry[17] = (s17 + (1 << 20)) >> 21 s18 += carry[17] s17 -= carry[17] << 21 carry[19] = (s19 + (1 << 20)) >> 21 s20 += carry[19] s19 -= carry[19] << 21 carry[21] = (s21 + (1 << 20)) >> 21 s22 += carry[21] s21 -= carry[21] << 21 s11 += s23 * 666643 s12 += s23 * 470296 s13 += s23 * 654183 s14 -= s23 * 997805 s15 += s23 * 136657 s16 -= s23 * 683901 s23 = 0 s10 += s22 * 666643 s11 += s22 * 470296 s12 += s22 * 654183 s13 -= s22 * 997805 s14 += s22 * 136657 s15 -= s22 * 683901 s22 = 0 s9 += s21 * 666643 s10 += s21 * 470296 s11 += s21 * 654183 s12 -= s21 * 997805 s13 += s21 * 136657 s14 -= s21 * 683901 s21 = 0 s8 += s20 * 666643 s9 += s20 * 470296 s10 += s20 * 654183 s11 -= s20 * 997805 s12 += s20 * 136657 s13 -= s20 * 683901 s20 = 0 s7 += s19 * 666643 s8 += s19 * 470296 s9 += s19 * 654183 s10 -= s19 * 997805 s11 += s19 * 136657 s12 -= s19 * 683901 s19 = 0 s6 += s18 * 666643 s7 += s18 * 470296 s8 += s18 * 654183 s9 -= s18 * 997805 s10 += s18 * 136657 s11 -= s18 * 683901 s18 = 0 carry[6] = (s6 + (1 << 20)) >> 21 s7 += carry[6] s6 -= carry[6] << 21 carry[8] = (s8 + (1 << 20)) >> 21 s9 += carry[8] s8 -= carry[8] << 21 carry[10] = (s10 + (1 << 20)) >> 21 s11 += carry[10] s10 -= carry[10] << 21 carry[12] = (s12 + (1 << 20)) >> 21 s13 += carry[12] s12 -= carry[12] << 21 carry[14] = (s14 + (1 << 20)) >> 21 s15 += carry[14] s14 -= carry[14] << 21 carry[16] = (s16 + (1 << 20)) >> 21 s17 += carry[16] s16 -= carry[16] << 21 carry[7] = (s7 + (1 << 20)) >> 21 s8 += carry[7] s7 -= carry[7] << 21 carry[9] = (s9 + (1 << 20)) >> 21 s10 += carry[9] s9 -= carry[9] << 21 carry[11] = (s11 + (1 << 20)) >> 21 s12 += carry[11] s11 -= carry[11] << 21 carry[13] = (s13 + (1 << 20)) >> 21 s14 += carry[13] s13 -= carry[13] << 21 carry[15] = (s15 + (1 << 20)) >> 21 s16 += carry[15] s15 -= carry[15] << 21 s5 += s17 * 666643 s6 += s17 * 470296 s7 += s17 * 654183 s8 -= s17 * 997805 s9 += s17 * 136657 s10 -= s17 * 683901 s17 = 0 s4 += s16 * 666643 s5 += s16 * 470296 s6 += s16 * 654183 s7 -= s16 * 997805 s8 += s16 * 136657 s9 -= s16 * 683901 s16 = 0 s3 += s15 * 666643 s4 += s15 * 470296 s5 += s15 * 654183 s6 -= s15 * 997805 s7 += s15 * 136657 s8 -= s15 * 683901 s15 = 0 s2 += s14 * 666643 s3 += s14 * 470296 s4 += s14 * 654183 s5 -= s14 * 997805 s6 += s14 * 136657 s7 -= s14 * 683901 s14 = 0 s1 += s13 * 666643 s2 += s13 * 470296 s3 += s13 * 654183 s4 -= s13 * 997805 s5 += s13 * 136657 s6 -= s13 * 683901 s13 = 0 s0 += s12 * 666643 s1 += s12 * 470296 s2 += s12 * 654183 s3 -= s12 * 997805 s4 += s12 * 136657 s5 -= s12 * 683901 s12 = 0 carry[0] = (s0 + (1 << 20)) >> 21 s1 += carry[0] s0 -= carry[0] << 21 carry[2] = (s2 + (1 << 20)) >> 21 s3 += carry[2] s2 -= carry[2] << 21 carry[4] = (s4 + (1 << 20)) >> 21 s5 += carry[4] s4 -= carry[4] << 21 carry[6] = (s6 + (1 << 20)) >> 21 s7 += carry[6] s6 -= carry[6] << 21 carry[8] = (s8 + (1 << 20)) >> 21 s9 += carry[8] s8 -= carry[8] << 21 carry[10] = (s10 + (1 << 20)) >> 21 s11 += carry[10] s10 -= carry[10] << 21 carry[1] = (s1 + (1 << 20)) >> 21 s2 += carry[1] s1 -= carry[1] << 21 carry[3] = (s3 + (1 << 20)) >> 21 s4 += carry[3] s3 -= carry[3] << 21 carry[5] = (s5 + (1 << 20)) >> 21 s6 += carry[5] s5 -= carry[5] << 21 carry[7] = (s7 + (1 << 20)) >> 21 s8 += carry[7] s7 -= carry[7] << 21 carry[9] = (s9 + (1 << 20)) >> 21 s10 += carry[9] s9 -= carry[9] << 21 carry[11] = (s11 + (1 << 20)) >> 21 s12 += carry[11] s11 -= carry[11] << 21 s0 += s12 * 666643 s1 += s12 * 470296 s2 += s12 * 654183 s3 -= s12 * 997805 s4 += s12 * 136657 s5 -= s12 * 683901 s12 = 0 carry[0] = s0 >> 21 s1 += carry[0] s0 -= carry[0] << 21 carry[1] = s1 >> 21 s2 += carry[1] s1 -= carry[1] << 21 carry[2] = s2 >> 21 s3 += carry[2] s2 -= carry[2] << 21 carry[3] = s3 >> 21 s4 += carry[3] s3 -= carry[3] << 21 carry[4] = s4 >> 21 s5 += carry[4] s4 -= carry[4] << 21 carry[5] = s5 >> 21 s6 += carry[5] s5 -= carry[5] << 21 carry[6] = s6 >> 21 s7 += carry[6] s6 -= carry[6] << 21 carry[7] = s7 >> 21 s8 += carry[7] s7 -= carry[7] << 21 carry[8] = s8 >> 21 s9 += carry[8] s8 -= carry[8] << 21 carry[9] = s9 >> 21 s10 += carry[9] s9 -= carry[9] << 21 carry[10] = s10 >> 21 s11 += carry[10] s10 -= carry[10] << 21 carry[11] = s11 >> 21 s12 += carry[11] s11 -= carry[11] << 21 s0 += s12 * 666643 s1 += s12 * 470296 s2 += s12 * 654183 s3 -= s12 * 997805 s4 += s12 * 136657 s5 -= s12 * 683901 s12 = 0 carry[0] = s0 >> 21 s1 += carry[0] s0 -= carry[0] << 21 carry[1] = s1 >> 21 s2 += carry[1] s1 -= carry[1] << 21 carry[2] = s2 >> 21 s3 += carry[2] s2 -= carry[2] << 21 carry[3] = s3 >> 21 s4 += carry[3] s3 -= carry[3] << 21 carry[4] = s4 >> 21 s5 += carry[4] s4 -= carry[4] << 21 carry[5] = s5 >> 21 s6 += carry[5] s5 -= carry[5] << 21 carry[6] = s6 >> 21 s7 += carry[6] s6 -= carry[6] << 21 carry[7] = s7 >> 21 s8 += carry[7] s7 -= carry[7] << 21 carry[8] = s8 >> 21 s9 += carry[8] s8 -= carry[8] << 21 carry[9] = s9 >> 21 s10 += carry[9] s9 -= carry[9] << 21 carry[10] = s10 >> 21 s11 += carry[10] s10 -= carry[10] << 21 s[0] = uint32(s0) | uint32(s1<<21) s[1] = uint32(s1>>11) | uint32(s2<<10) | uint32(s3<<31) s[2] = uint32(s3>>1) | uint32(s4<<20) s[3] = uint32(s4>>12) | uint32(s5<<9) | uint32(s6<<30) s[4] = uint32(s6>>2) | uint32(s7<<19) s[5] = uint32(s7>>13) | uint32(s8<<8) | uint32(s9<<29) s[6] = uint32(s9>>3) | uint32(s10<<18) s[7] = uint32(s10>>14) | uint32(s11<<7) return s } // Set s to t if b=1 in constant-time. b must be either 0 or 1. func (s *Scalar) ConditionalSet(t *Scalar, b int32) { m := uint32(-b) s[0] ^= m & (s[0] ^ t[0]) s[1] ^= m & (s[1] ^ t[1]) s[2] ^= m & (s[2] ^ t[2]) s[3] ^= m & (s[3] ^ t[3]) s[4] ^= m & (s[4] ^ t[4]) s[5] ^= m & (s[5] ^ t[5]) s[6] ^= m & (s[6] ^ t[6]) s[7] ^= m & (s[7] ^ t[7]) }