12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025 |
- // Copyright (c) 2016 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 edwards25519
- import (
- "crypto/subtle"
- "encoding/binary"
- "errors"
- )
- // A Scalar is an integer modulo
- //
- // l = 2^252 + 27742317777372353535851937790883648493
- //
- // which is the prime order of the edwards25519 group.
- //
- // 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 Scalar struct {
- // s is the Scalar value in little-endian. The value is always reduced
- // between operations.
- s [32]byte
- }
- var (
- scZero = Scalar{[32]byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}
- scOne = Scalar{[32]byte{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}
- scMinusOne = Scalar{[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}}
- )
- // NewScalar returns a new zero Scalar.
- func NewScalar() *Scalar {
- return &Scalar{}
- }
- // MultiplyAdd sets s = x * y + z mod l, and returns s.
- func (s *Scalar) MultiplyAdd(x, y, z *Scalar) *Scalar {
- scMulAdd(&s.s, &x.s, &y.s, &z.s)
- return s
- }
- // Add sets s = x + y mod l, and returns s.
- func (s *Scalar) Add(x, y *Scalar) *Scalar {
- // s = 1 * x + y mod l
- scMulAdd(&s.s, &scOne.s, &x.s, &y.s)
- return s
- }
- // Subtract sets s = x - y mod l, and returns s.
- func (s *Scalar) Subtract(x, y *Scalar) *Scalar {
- // s = -1 * y + x mod l
- scMulAdd(&s.s, &scMinusOne.s, &y.s, &x.s)
- return s
- }
- // Negate sets s = -x mod l, and returns s.
- func (s *Scalar) Negate(x *Scalar) *Scalar {
- // s = -1 * x + 0 mod l
- scMulAdd(&s.s, &scMinusOne.s, &x.s, &scZero.s)
- return s
- }
- // Multiply sets s = x * y mod l, and returns s.
- func (s *Scalar) Multiply(x, y *Scalar) *Scalar {
- // s = x * y + 0 mod l
- scMulAdd(&s.s, &x.s, &y.s, &scZero.s)
- return s
- }
- // Set sets s = x, and returns s.
- func (s *Scalar) Set(x *Scalar) *Scalar {
- *s = *x
- return s
- }
- // SetUniformBytes sets s to an uniformly distributed value given 64 uniformly
- // distributed random bytes.
- func (s *Scalar) SetUniformBytes(x []byte) *Scalar {
- if len(x) != 64 {
- panic("edwards25519: invalid SetUniformBytes input length")
- }
- var wideBytes [64]byte
- copy(wideBytes[:], x[:])
- scReduce(&s.s, &wideBytes)
- return s
- }
- // SetCanonicalBytes sets s = x, where x is a 32-byte little-endian encoding of
- // s, and returns s. If x is not a canonical encoding of s, SetCanonicalBytes
- // returns nil and an error, and the receiver is unchanged.
- func (s *Scalar) SetCanonicalBytes(x []byte) (*Scalar, error) {
- if len(x) != 32 {
- return nil, errors.New("invalid scalar length")
- }
- ss := &Scalar{}
- copy(ss.s[:], x)
- if !isReduced(ss) {
- return nil, errors.New("invalid scalar encoding")
- }
- s.s = ss.s
- return s, nil
- }
- // isReduced returns whether the given scalar is reduced modulo l.
- func isReduced(s *Scalar) bool {
- for i := len(s.s) - 1; i >= 0; i-- {
- switch {
- case s.s[i] > scMinusOne.s[i]:
- return false
- case s.s[i] < scMinusOne.s[i]:
- return true
- }
- }
- return true
- }
- // SetBytesWithClamping applies the buffer pruning described in RFC 8032,
- // Section 5.1.5 (also known as clamping) and sets s to the result. The input
- // must be 32 bytes, and it is not modified.
- //
- // Note that since Scalar values are always reduced modulo the prime order of
- // the curve, the resulting value will not preserve any of the cofactor-clearing
- // properties that clamping is meant to provide. It will however work as
- // expected as long as it is applied to points on the prime order subgroup, like
- // in Ed25519. In fact, it is lost to history why RFC 8032 adopted the
- // irrelevant RFC 7748 clamping, but it is now required for compatibility.
- func (s *Scalar) SetBytesWithClamping(x []byte) *Scalar {
- // The description above omits the purpose of the high bits of the clamping
- // for brevity, but those are also lost to reductions, and are also
- // irrelevant to edwards25519 as they protect against a specific
- // implementation bug that was once observed in a generic Montgomery ladder.
- if len(x) != 32 {
- panic("edwards25519: invalid SetBytesWithClamping input length")
- }
- var wideBytes [64]byte
- copy(wideBytes[:], x[:])
- wideBytes[0] &= 248
- wideBytes[31] &= 63
- wideBytes[31] |= 64
- scReduce(&s.s, &wideBytes)
- return s
- }
- // Bytes returns the canonical 32-byte little-endian encoding of s.
- func (s *Scalar) Bytes() []byte {
- buf := make([]byte, 32)
- copy(buf, s.s[:])
- return buf
- }
- // Equal returns 1 if s and t are equal, and 0 otherwise.
- func (s *Scalar) Equal(t *Scalar) int {
- return subtle.ConstantTimeCompare(s.s[:], t.s[:])
- }
- // scMulAdd and scReduce are ported from the public domain, “ref10”
- // implementation of ed25519 from SUPERCOP.
- func load3(in []byte) int64 {
- r := int64(in[0])
- r |= int64(in[1]) << 8
- r |= int64(in[2]) << 16
- return r
- }
- func load4(in []byte) int64 {
- r := int64(in[0])
- r |= int64(in[1]) << 8
- r |= int64(in[2]) << 16
- r |= int64(in[3]) << 24
- return r
- }
- // Input:
- // a[0]+256*a[1]+...+256^31*a[31] = a
- // b[0]+256*b[1]+...+256^31*b[31] = b
- // c[0]+256*c[1]+...+256^31*c[31] = c
- //
- // Output:
- // s[0]+256*s[1]+...+256^31*s[31] = (ab+c) mod l
- // where l = 2^252 + 27742317777372353535851937790883648493.
- func scMulAdd(s, a, b, c *[32]byte) {
- a0 := 2097151 & load3(a[:])
- a1 := 2097151 & (load4(a[2:]) >> 5)
- a2 := 2097151 & (load3(a[5:]) >> 2)
- a3 := 2097151 & (load4(a[7:]) >> 7)
- a4 := 2097151 & (load4(a[10:]) >> 4)
- a5 := 2097151 & (load3(a[13:]) >> 1)
- a6 := 2097151 & (load4(a[15:]) >> 6)
- a7 := 2097151 & (load3(a[18:]) >> 3)
- a8 := 2097151 & load3(a[21:])
- a9 := 2097151 & (load4(a[23:]) >> 5)
- a10 := 2097151 & (load3(a[26:]) >> 2)
- a11 := (load4(a[28:]) >> 7)
- b0 := 2097151 & load3(b[:])
- b1 := 2097151 & (load4(b[2:]) >> 5)
- b2 := 2097151 & (load3(b[5:]) >> 2)
- b3 := 2097151 & (load4(b[7:]) >> 7)
- b4 := 2097151 & (load4(b[10:]) >> 4)
- b5 := 2097151 & (load3(b[13:]) >> 1)
- b6 := 2097151 & (load4(b[15:]) >> 6)
- b7 := 2097151 & (load3(b[18:]) >> 3)
- b8 := 2097151 & load3(b[21:])
- b9 := 2097151 & (load4(b[23:]) >> 5)
- b10 := 2097151 & (load3(b[26:]) >> 2)
- b11 := (load4(b[28:]) >> 7)
- c0 := 2097151 & load3(c[:])
- c1 := 2097151 & (load4(c[2:]) >> 5)
- c2 := 2097151 & (load3(c[5:]) >> 2)
- c3 := 2097151 & (load4(c[7:]) >> 7)
- c4 := 2097151 & (load4(c[10:]) >> 4)
- c5 := 2097151 & (load3(c[13:]) >> 1)
- c6 := 2097151 & (load4(c[15:]) >> 6)
- c7 := 2097151 & (load3(c[18:]) >> 3)
- c8 := 2097151 & load3(c[21:])
- c9 := 2097151 & (load4(c[23:]) >> 5)
- c10 := 2097151 & (load3(c[26:]) >> 2)
- c11 := (load4(c[28:]) >> 7)
- var carry [23]int64
- s0 := c0 + a0*b0
- s1 := c1 + a0*b1 + a1*b0
- s2 := c2 + a0*b2 + a1*b1 + a2*b0
- s3 := c3 + a0*b3 + a1*b2 + a2*b1 + a3*b0
- s4 := c4 + a0*b4 + a1*b3 + a2*b2 + a3*b1 + a4*b0
- s5 := c5 + a0*b5 + a1*b4 + a2*b3 + a3*b2 + a4*b1 + a5*b0
- s6 := c6 + a0*b6 + a1*b5 + a2*b4 + a3*b3 + a4*b2 + a5*b1 + a6*b0
- s7 := c7 + a0*b7 + a1*b6 + a2*b5 + a3*b4 + a4*b3 + a5*b2 + a6*b1 + a7*b0
- s8 := c8 + a0*b8 + a1*b7 + a2*b6 + a3*b5 + a4*b4 + a5*b3 + a6*b2 + a7*b1 + a8*b0
- s9 := c9 + a0*b9 + a1*b8 + a2*b7 + a3*b6 + a4*b5 + a5*b4 + a6*b3 + a7*b2 + a8*b1 + a9*b0
- s10 := c10 + a0*b10 + a1*b9 + a2*b8 + a3*b7 + a4*b6 + a5*b5 + a6*b4 + a7*b3 + a8*b2 + a9*b1 + a10*b0
- s11 := 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
- s12 := a1*b11 + a2*b10 + a3*b9 + a4*b8 + a5*b7 + a6*b6 + a7*b5 + a8*b4 + a9*b3 + a10*b2 + a11*b1
- s13 := a2*b11 + a3*b10 + a4*b9 + a5*b8 + a6*b7 + a7*b6 + a8*b5 + a9*b4 + a10*b3 + a11*b2
- s14 := a3*b11 + a4*b10 + a5*b9 + a6*b8 + a7*b7 + a8*b6 + a9*b5 + a10*b4 + a11*b3
- s15 := a4*b11 + a5*b10 + a6*b9 + a7*b8 + a8*b7 + a9*b6 + a10*b5 + a11*b4
- s16 := a5*b11 + a6*b10 + a7*b9 + a8*b8 + a9*b7 + a10*b6 + a11*b5
- s17 := a6*b11 + a7*b10 + a8*b9 + a9*b8 + a10*b7 + a11*b6
- s18 := a7*b11 + a8*b10 + a9*b9 + a10*b8 + a11*b7
- s19 := a8*b11 + a9*b10 + a10*b9 + a11*b8
- s20 := a9*b11 + a10*b10 + a11*b9
- s21 := a10*b11 + a11*b10
- s22 := a11 * b11
- s23 := int64(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[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] = byte(s0 >> 0)
- s[1] = byte(s0 >> 8)
- s[2] = byte((s0 >> 16) | (s1 << 5))
- s[3] = byte(s1 >> 3)
- s[4] = byte(s1 >> 11)
- s[5] = byte((s1 >> 19) | (s2 << 2))
- s[6] = byte(s2 >> 6)
- s[7] = byte((s2 >> 14) | (s3 << 7))
- s[8] = byte(s3 >> 1)
- s[9] = byte(s3 >> 9)
- s[10] = byte((s3 >> 17) | (s4 << 4))
- s[11] = byte(s4 >> 4)
- s[12] = byte(s4 >> 12)
- s[13] = byte((s4 >> 20) | (s5 << 1))
- s[14] = byte(s5 >> 7)
- s[15] = byte((s5 >> 15) | (s6 << 6))
- s[16] = byte(s6 >> 2)
- s[17] = byte(s6 >> 10)
- s[18] = byte((s6 >> 18) | (s7 << 3))
- s[19] = byte(s7 >> 5)
- s[20] = byte(s7 >> 13)
- s[21] = byte(s8 >> 0)
- s[22] = byte(s8 >> 8)
- s[23] = byte((s8 >> 16) | (s9 << 5))
- s[24] = byte(s9 >> 3)
- s[25] = byte(s9 >> 11)
- s[26] = byte((s9 >> 19) | (s10 << 2))
- s[27] = byte(s10 >> 6)
- s[28] = byte((s10 >> 14) | (s11 << 7))
- s[29] = byte(s11 >> 1)
- s[30] = byte(s11 >> 9)
- s[31] = byte(s11 >> 17)
- }
- // Input:
- // s[0]+256*s[1]+...+256^63*s[63] = s
- //
- // Output:
- // s[0]+256*s[1]+...+256^31*s[31] = s mod l
- // where l = 2^252 + 27742317777372353535851937790883648493.
- func scReduce(out *[32]byte, s *[64]byte) {
- s0 := 2097151 & load3(s[:])
- s1 := 2097151 & (load4(s[2:]) >> 5)
- s2 := 2097151 & (load3(s[5:]) >> 2)
- s3 := 2097151 & (load4(s[7:]) >> 7)
- s4 := 2097151 & (load4(s[10:]) >> 4)
- s5 := 2097151 & (load3(s[13:]) >> 1)
- s6 := 2097151 & (load4(s[15:]) >> 6)
- s7 := 2097151 & (load3(s[18:]) >> 3)
- s8 := 2097151 & load3(s[21:])
- s9 := 2097151 & (load4(s[23:]) >> 5)
- s10 := 2097151 & (load3(s[26:]) >> 2)
- s11 := 2097151 & (load4(s[28:]) >> 7)
- s12 := 2097151 & (load4(s[31:]) >> 4)
- s13 := 2097151 & (load3(s[34:]) >> 1)
- s14 := 2097151 & (load4(s[36:]) >> 6)
- s15 := 2097151 & (load3(s[39:]) >> 3)
- s16 := 2097151 & load3(s[42:])
- s17 := 2097151 & (load4(s[44:]) >> 5)
- s18 := 2097151 & (load3(s[47:]) >> 2)
- s19 := 2097151 & (load4(s[49:]) >> 7)
- s20 := 2097151 & (load4(s[52:]) >> 4)
- s21 := 2097151 & (load3(s[55:]) >> 1)
- s22 := 2097151 & (load4(s[57:]) >> 6)
- s23 := (load4(s[60:]) >> 3)
- 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
- var carry [17]int64
- 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
- out[0] = byte(s0 >> 0)
- out[1] = byte(s0 >> 8)
- out[2] = byte((s0 >> 16) | (s1 << 5))
- out[3] = byte(s1 >> 3)
- out[4] = byte(s1 >> 11)
- out[5] = byte((s1 >> 19) | (s2 << 2))
- out[6] = byte(s2 >> 6)
- out[7] = byte((s2 >> 14) | (s3 << 7))
- out[8] = byte(s3 >> 1)
- out[9] = byte(s3 >> 9)
- out[10] = byte((s3 >> 17) | (s4 << 4))
- out[11] = byte(s4 >> 4)
- out[12] = byte(s4 >> 12)
- out[13] = byte((s4 >> 20) | (s5 << 1))
- out[14] = byte(s5 >> 7)
- out[15] = byte((s5 >> 15) | (s6 << 6))
- out[16] = byte(s6 >> 2)
- out[17] = byte(s6 >> 10)
- out[18] = byte((s6 >> 18) | (s7 << 3))
- out[19] = byte(s7 >> 5)
- out[20] = byte(s7 >> 13)
- out[21] = byte(s8 >> 0)
- out[22] = byte(s8 >> 8)
- out[23] = byte((s8 >> 16) | (s9 << 5))
- out[24] = byte(s9 >> 3)
- out[25] = byte(s9 >> 11)
- out[26] = byte((s9 >> 19) | (s10 << 2))
- out[27] = byte(s10 >> 6)
- out[28] = byte((s10 >> 14) | (s11 << 7))
- out[29] = byte(s11 >> 1)
- out[30] = byte(s11 >> 9)
- out[31] = byte(s11 >> 17)
- }
- // nonAdjacentForm computes a width-w non-adjacent form for this scalar.
- //
- // w must be between 2 and 8, or nonAdjacentForm will panic.
- func (s *Scalar) nonAdjacentForm(w uint) [256]int8 {
- // This implementation is adapted from the one
- // in curve25519-dalek and is documented there:
- // https://github.com/dalek-cryptography/curve25519-dalek/blob/f630041af28e9a405255f98a8a93adca18e4315b/src/scalar.rs#L800-L871
- if s.s[31] > 127 {
- panic("scalar has high bit set illegally")
- }
- if w < 2 {
- panic("w must be at least 2 by the definition of NAF")
- } else if w > 8 {
- panic("NAF digits must fit in int8")
- }
- var naf [256]int8
- var digits [5]uint64
- for i := 0; i < 4; i++ {
- digits[i] = binary.LittleEndian.Uint64(s.s[i*8:])
- }
- width := uint64(1 << w)
- windowMask := uint64(width - 1)
- pos := uint(0)
- carry := uint64(0)
- for pos < 256 {
- indexU64 := pos / 64
- indexBit := pos % 64
- var bitBuf uint64
- if indexBit < 64-w {
- // This window's bits are contained in a single u64
- bitBuf = digits[indexU64] >> indexBit
- } else {
- // Combine the current 64 bits with bits from the next 64
- bitBuf = (digits[indexU64] >> indexBit) | (digits[1+indexU64] << (64 - indexBit))
- }
- // Add carry into the current window
- window := carry + (bitBuf & windowMask)
- if window&1 == 0 {
- // If the window value is even, preserve the carry and continue.
- // Why is the carry preserved?
- // If carry == 0 and window & 1 == 0,
- // then the next carry should be 0
- // If carry == 1 and window & 1 == 0,
- // then bit_buf & 1 == 1 so the next carry should be 1
- pos += 1
- continue
- }
- if window < width/2 {
- carry = 0
- naf[pos] = int8(window)
- } else {
- carry = 1
- naf[pos] = int8(window) - int8(width)
- }
- pos += w
- }
- return naf
- }
- func (s *Scalar) signedRadix16() [64]int8 {
- if s.s[31] > 127 {
- panic("scalar has high bit set illegally")
- }
- var digits [64]int8
- // Compute unsigned radix-16 digits:
- for i := 0; i < 32; i++ {
- digits[2*i] = int8(s.s[i] & 15)
- digits[2*i+1] = int8((s.s[i] >> 4) & 15)
- }
- // Recenter coefficients:
- for i := 0; i < 63; i++ {
- carry := (digits[i] + 8) >> 4
- digits[i] -= carry << 4
- digits[i+1] += carry
- }
- return digits
- }
|