| 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 |
"crypto/subtle" |
| 9 |
"encoding/binary" |
| 10 |
"errors" |
| 11 |
) |
| 12 |
|
| 13 |
// A Scalar is an integer modulo |
| 14 |
// |
| 15 |
// l = 2^252 + 27742317777372353535851937790883648493 |
| 16 |
// |
| 17 |
// which is the prime order of the edwards25519 group. |
| 18 |
// |
| 19 |
// This type works similarly to math/big.Int, and all arguments and |
| 20 |
// receivers are allowed to alias. |
| 21 |
// |
| 22 |
// The zero value is a valid zero element. |
| 23 |
type Scalar struct { |
| 24 |
// s is the Scalar value in little-endian. The value is always reduced |
| 25 |
// between operations. |
| 26 |
s [32]byte |
| 27 |
} |
| 28 |
|
| 29 |
var ( |
| 30 |
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}} |
| 31 |
|
| 32 |
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}} |
| 33 |
|
| 34 |
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}} |
| 35 |
) |
| 36 |
|
| 37 |
// NewScalar returns a new zero Scalar. |
| 38 |
func NewScalar() *Scalar { |
| 39 |
return &Scalar{} |
| 40 |
} |
| 41 |
|
| 42 |
// MultiplyAdd sets s = x * y + z mod l, and returns s. |
| 43 |
func (s *Scalar) MultiplyAdd(x, y, z *Scalar) *Scalar { |
| 44 |
scMulAdd(&s.s, &x.s, &y.s, &z.s) |
| 45 |
return s |
| 46 |
} |
| 47 |
|
| 48 |
// Add sets s = x + y mod l, and returns s. |
| 49 |
func (s *Scalar) Add(x, y *Scalar) *Scalar { |
| 50 |
// s = 1 * x + y mod l |
| 51 |
scMulAdd(&s.s, &scOne.s, &x.s, &y.s) |
| 52 |
return s |
| 53 |
} |
| 54 |
|
| 55 |
// Subtract sets s = x - y mod l, and returns s. |
| 56 |
func (s *Scalar) Subtract(x, y *Scalar) *Scalar { |
| 57 |
// s = -1 * y + x mod l |
| 58 |
scMulAdd(&s.s, &scMinusOne.s, &y.s, &x.s) |
| 59 |
return s |
| 60 |
} |
| 61 |
|
| 62 |
// Negate sets s = -x mod l, and returns s. |
| 63 |
func (s *Scalar) Negate(x *Scalar) *Scalar { |
| 64 |
// s = -1 * x + 0 mod l |
| 65 |
scMulAdd(&s.s, &scMinusOne.s, &x.s, &scZero.s) |
| 66 |
return s |
| 67 |
} |
| 68 |
|
| 69 |
// Multiply sets s = x * y mod l, and returns s. |
| 70 |
func (s *Scalar) Multiply(x, y *Scalar) *Scalar { |
| 71 |
// s = x * y + 0 mod l |
| 72 |
scMulAdd(&s.s, &x.s, &y.s, &scZero.s) |
| 73 |
return s |
| 74 |
} |
| 75 |
|
| 76 |
// Set sets s = x, and returns s. |
| 77 |
func (s *Scalar) Set(x *Scalar) *Scalar { |
| 78 |
*s = *x |
| 79 |
return s |
| 80 |
} |
| 81 |
|
| 82 |
// SetUniformBytes sets s to an uniformly distributed value given 64 uniformly |
| 83 |
// distributed random bytes. |
| 84 |
func (s *Scalar) SetUniformBytes(x []byte) *Scalar { |
| 85 |
if len(x) != 64 { |
| 86 |
panic("edwards25519: invalid SetUniformBytes input length") |
| 87 |
} |
| 88 |
var wideBytes [64]byte |
| 89 |
copy(wideBytes[:], x[:]) |
| 90 |
scReduce(&s.s, &wideBytes) |
| 91 |
return s |
| 92 |
} |
| 93 |
|
| 94 |
// SetCanonicalBytes sets s = x, where x is a 32-byte little-endian encoding of |
| 95 |
// s, and returns s. If x is not a canonical encoding of s, SetCanonicalBytes |
| 96 |
// returns nil and an error, and the receiver is unchanged. |
| 97 |
func (s *Scalar) SetCanonicalBytes(x []byte) (*Scalar, error) { |
| 98 |
if len(x) != 32 { |
| 99 |
return nil, errors.New("invalid scalar length") |
| 100 |
} |
| 101 |
ss := &Scalar{} |
| 102 |
copy(ss.s[:], x) |
| 103 |
if !isReduced(ss) { |
| 104 |
return nil, errors.New("invalid scalar encoding") |
| 105 |
} |
| 106 |
s.s = ss.s |
| 107 |
return s, nil |
| 108 |
} |
| 109 |
|
| 110 |
// isReduced returns whether the given scalar is reduced modulo l. |
| 111 |
func isReduced(s *Scalar) bool { |
| 112 |
for i := len(s.s) - 1; i >= 0; i-- { |
| 113 |
switch { |
| 114 |
case s.s[i] > scMinusOne.s[i]: |
| 115 |
return false |
| 116 |
case s.s[i] < scMinusOne.s[i]: |
| 117 |
return true |
| 118 |
} |
| 119 |
} |
| 120 |
return true |
| 121 |
} |
| 122 |
|
| 123 |
// SetBytesWithClamping applies the buffer pruning described in RFC 8032, |
| 124 |
// Section 5.1.5 (also known as clamping) and sets s to the result. The input |
| 125 |
// must be 32 bytes, and it is not modified. |
| 126 |
// |
| 127 |
// Note that since Scalar values are always reduced modulo the prime order of |
| 128 |
// the curve, the resulting value will not preserve any of the cofactor-clearing |
| 129 |
// properties that clamping is meant to provide. It will however work as |
| 130 |
// expected as long as it is applied to points on the prime order subgroup, like |
| 131 |
// in Ed25519. In fact, it is lost to history why RFC 8032 adopted the |
| 132 |
// irrelevant RFC 7748 clamping, but it is now required for compatibility. |
| 133 |
func (s *Scalar) SetBytesWithClamping(x []byte) *Scalar { |
| 134 |
// The description above omits the purpose of the high bits of the clamping |
| 135 |
// for brevity, but those are also lost to reductions, and are also |
| 136 |
// irrelevant to edwards25519 as they protect against a specific |
| 137 |
// implementation bug that was once observed in a generic Montgomery ladder. |
| 138 |
if len(x) != 32 { |
| 139 |
panic("edwards25519: invalid SetBytesWithClamping input length") |
| 140 |
} |
| 141 |
var wideBytes [64]byte |
| 142 |
copy(wideBytes[:], x[:]) |
| 143 |
wideBytes[0] &= 248 |
| 144 |
wideBytes[31] &= 63 |
| 145 |
wideBytes[31] |= 64 |
| 146 |
scReduce(&s.s, &wideBytes) |
| 147 |
return s |
| 148 |
} |
| 149 |
|
| 150 |
// Bytes returns the canonical 32-byte little-endian encoding of s. |
| 151 |
func (s *Scalar) Bytes() []byte { |
| 152 |
buf := make([]byte, 32) |
| 153 |
copy(buf, s.s[:]) |
| 154 |
return buf |
| 155 |
} |
| 156 |
|
| 157 |
// Equal returns 1 if s and t are equal, and 0 otherwise. |
| 158 |
func (s *Scalar) Equal(t *Scalar) int { |
| 159 |
return subtle.ConstantTimeCompare(s.s[:], t.s[:]) |
| 160 |
} |
| 161 |
|
| 162 |
// scMulAdd and scReduce are ported from the public domain, “ref10” |
| 163 |
// implementation of ed25519 from SUPERCOP. |
| 164 |
|
| 165 |
func load3(in []byte) int64 { |
| 166 |
r := int64(in[0]) |
| 167 |
r |= int64(in[1]) << 8 |
| 168 |
r |= int64(in[2]) << 16 |
| 169 |
return r |
| 170 |
} |
| 171 |
|
| 172 |
func load4(in []byte) int64 { |
| 173 |
r := int64(in[0]) |
| 174 |
r |= int64(in[1]) << 8 |
| 175 |
r |= int64(in[2]) << 16 |
| 176 |
r |= int64(in[3]) << 24 |
| 177 |
return r |
| 178 |
} |
| 179 |
|
| 180 |
// Input: |
| 181 |
// a[0]+256*a[1]+...+256^31*a[31] = a |
| 182 |
// b[0]+256*b[1]+...+256^31*b[31] = b |
| 183 |
// c[0]+256*c[1]+...+256^31*c[31] = c |
| 184 |
// |
| 185 |
// Output: |
| 186 |
// s[0]+256*s[1]+...+256^31*s[31] = (ab+c) mod l |
| 187 |
// where l = 2^252 + 27742317777372353535851937790883648493. |
| 188 |
func scMulAdd(s, a, b, c *[32]byte) { |
| 189 |
a0 := 2097151 & load3(a[:]) |
| 190 |
a1 := 2097151 & (load4(a[2:]) >> 5) |
| 191 |
a2 := 2097151 & (load3(a[5:]) >> 2) |
| 192 |
a3 := 2097151 & (load4(a[7:]) >> 7) |
| 193 |
a4 := 2097151 & (load4(a[10:]) >> 4) |
| 194 |
a5 := 2097151 & (load3(a[13:]) >> 1) |
| 195 |
a6 := 2097151 & (load4(a[15:]) >> 6) |
| 196 |
a7 := 2097151 & (load3(a[18:]) >> 3) |
| 197 |
a8 := 2097151 & load3(a[21:]) |
| 198 |
a9 := 2097151 & (load4(a[23:]) >> 5) |
| 199 |
a10 := 2097151 & (load3(a[26:]) >> 2) |
| 200 |
a11 := (load4(a[28:]) >> 7) |
| 201 |
b0 := 2097151 & load3(b[:]) |
| 202 |
b1 := 2097151 & (load4(b[2:]) >> 5) |
| 203 |
b2 := 2097151 & (load3(b[5:]) >> 2) |
| 204 |
b3 := 2097151 & (load4(b[7:]) >> 7) |
| 205 |
b4 := 2097151 & (load4(b[10:]) >> 4) |
| 206 |
b5 := 2097151 & (load3(b[13:]) >> 1) |
| 207 |
b6 := 2097151 & (load4(b[15:]) >> 6) |
| 208 |
b7 := 2097151 & (load3(b[18:]) >> 3) |
| 209 |
b8 := 2097151 & load3(b[21:]) |
| 210 |
b9 := 2097151 & (load4(b[23:]) >> 5) |
| 211 |
b10 := 2097151 & (load3(b[26:]) >> 2) |
| 212 |
b11 := (load4(b[28:]) >> 7) |
| 213 |
c0 := 2097151 & load3(c[:]) |
| 214 |
c1 := 2097151 & (load4(c[2:]) >> 5) |
| 215 |
c2 := 2097151 & (load3(c[5:]) >> 2) |
| 216 |
c3 := 2097151 & (load4(c[7:]) >> 7) |
| 217 |
c4 := 2097151 & (load4(c[10:]) >> 4) |
| 218 |
c5 := 2097151 & (load3(c[13:]) >> 1) |
| 219 |
c6 := 2097151 & (load4(c[15:]) >> 6) |
| 220 |
c7 := 2097151 & (load3(c[18:]) >> 3) |
| 221 |
c8 := 2097151 & load3(c[21:]) |
| 222 |
c9 := 2097151 & (load4(c[23:]) >> 5) |
| 223 |
c10 := 2097151 & (load3(c[26:]) >> 2) |
| 224 |
c11 := (load4(c[28:]) >> 7) |
| 225 |
var carry [23]int64 |
| 226 |
|
| 227 |
s0 := c0 + a0*b0 |
| 228 |
s1 := c1 + a0*b1 + a1*b0 |
| 229 |
s2 := c2 + a0*b2 + a1*b1 + a2*b0 |
| 230 |
s3 := c3 + a0*b3 + a1*b2 + a2*b1 + a3*b0 |
| 231 |
s4 := c4 + a0*b4 + a1*b3 + a2*b2 + a3*b1 + a4*b0 |
| 232 |
s5 := c5 + a0*b5 + a1*b4 + a2*b3 + a3*b2 + a4*b1 + a5*b0 |
| 233 |
s6 := c6 + a0*b6 + a1*b5 + a2*b4 + a3*b3 + a4*b2 + a5*b1 + a6*b0 |
| 234 |
s7 := c7 + a0*b7 + a1*b6 + a2*b5 + a3*b4 + a4*b3 + a5*b2 + a6*b1 + a7*b0 |
| 235 |
s8 := c8 + a0*b8 + a1*b7 + a2*b6 + a3*b5 + a4*b4 + a5*b3 + a6*b2 + a7*b1 + a8*b0 |
| 236 |
s9 := c9 + a0*b9 + a1*b8 + a2*b7 + a3*b6 + a4*b5 + a5*b4 + a6*b3 + a7*b2 + a8*b1 + a9*b0 |
| 237 |
s10 := c10 + a0*b10 + a1*b9 + a2*b8 + a3*b7 + a4*b6 + a5*b5 + a6*b4 + a7*b3 + a8*b2 + a9*b1 + a10*b0 |
| 238 |
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 |
| 239 |
s12 := a1*b11 + a2*b10 + a3*b9 + a4*b8 + a5*b7 + a6*b6 + a7*b5 + a8*b4 + a9*b3 + a10*b2 + a11*b1 |
| 240 |
s13 := a2*b11 + a3*b10 + a4*b9 + a5*b8 + a6*b7 + a7*b6 + a8*b5 + a9*b4 + a10*b3 + a11*b2 |
| 241 |
s14 := a3*b11 + a4*b10 + a5*b9 + a6*b8 + a7*b7 + a8*b6 + a9*b5 + a10*b4 + a11*b3 |
| 242 |
s15 := a4*b11 + a5*b10 + a6*b9 + a7*b8 + a8*b7 + a9*b6 + a10*b5 + a11*b4 |
| 243 |
s16 := a5*b11 + a6*b10 + a7*b9 + a8*b8 + a9*b7 + a10*b6 + a11*b5 |
| 244 |
s17 := a6*b11 + a7*b10 + a8*b9 + a9*b8 + a10*b7 + a11*b6 |
| 245 |
s18 := a7*b11 + a8*b10 + a9*b9 + a10*b8 + a11*b7 |
| 246 |
s19 := a8*b11 + a9*b10 + a10*b9 + a11*b8 |
| 247 |
s20 := a9*b11 + a10*b10 + a11*b9 |
| 248 |
s21 := a10*b11 + a11*b10 |
| 249 |
s22 := a11 * b11 |
| 250 |
s23 := int64(0) |
| 251 |
|
| 252 |
carry[0] = (s0 + (1 << 20)) >> 21 |
| 253 |
s1 += carry[0] |
| 254 |
s0 -= carry[0] << 21 |
| 255 |
carry[2] = (s2 + (1 << 20)) >> 21 |
| 256 |
s3 += carry[2] |
| 257 |
s2 -= carry[2] << 21 |
| 258 |
carry[4] = (s4 + (1 << 20)) >> 21 |
| 259 |
s5 += carry[4] |
| 260 |
s4 -= carry[4] << 21 |
| 261 |
carry[6] = (s6 + (1 << 20)) >> 21 |
| 262 |
s7 += carry[6] |
| 263 |
s6 -= carry[6] << 21 |
| 264 |
carry[8] = (s8 + (1 << 20)) >> 21 |
| 265 |
s9 += carry[8] |
| 266 |
s8 -= carry[8] << 21 |
| 267 |
carry[10] = (s10 + (1 << 20)) >> 21 |
| 268 |
s11 += carry[10] |
| 269 |
s10 -= carry[10] << 21 |
| 270 |
carry[12] = (s12 + (1 << 20)) >> 21 |
| 271 |
s13 += carry[12] |
| 272 |
s12 -= carry[12] << 21 |
| 273 |
carry[14] = (s14 + (1 << 20)) >> 21 |
| 274 |
s15 += carry[14] |
| 275 |
s14 -= carry[14] << 21 |
| 276 |
carry[16] = (s16 + (1 << 20)) >> 21 |
| 277 |
s17 += carry[16] |
| 278 |
s16 -= carry[16] << 21 |
| 279 |
carry[18] = (s18 + (1 << 20)) >> 21 |
| 280 |
s19 += carry[18] |
| 281 |
s18 -= carry[18] << 21 |
| 282 |
carry[20] = (s20 + (1 << 20)) >> 21 |
| 283 |
s21 += carry[20] |
| 284 |
s20 -= carry[20] << 21 |
| 285 |
carry[22] = (s22 + (1 << 20)) >> 21 |
| 286 |
s23 += carry[22] |
| 287 |
s22 -= carry[22] << 21 |
| 288 |
|
| 289 |
carry[1] = (s1 + (1 << 20)) >> 21 |
| 290 |
s2 += carry[1] |
| 291 |
s1 -= carry[1] << 21 |
| 292 |
carry[3] = (s3 + (1 << 20)) >> 21 |
| 293 |
s4 += carry[3] |
| 294 |
s3 -= carry[3] << 21 |
| 295 |
carry[5] = (s5 + (1 << 20)) >> 21 |
| 296 |
s6 += carry[5] |
| 297 |
s5 -= carry[5] << 21 |
| 298 |
carry[7] = (s7 + (1 << 20)) >> 21 |
| 299 |
s8 += carry[7] |
| 300 |
s7 -= carry[7] << 21 |
| 301 |
carry[9] = (s9 + (1 << 20)) >> 21 |
| 302 |
s10 += carry[9] |
| 303 |
s9 -= carry[9] << 21 |
| 304 |
carry[11] = (s11 + (1 << 20)) >> 21 |
| 305 |
s12 += carry[11] |
| 306 |
s11 -= carry[11] << 21 |
| 307 |
carry[13] = (s13 + (1 << 20)) >> 21 |
| 308 |
s14 += carry[13] |
| 309 |
s13 -= carry[13] << 21 |
| 310 |
carry[15] = (s15 + (1 << 20)) >> 21 |
| 311 |
s16 += carry[15] |
| 312 |
s15 -= carry[15] << 21 |
| 313 |
carry[17] = (s17 + (1 << 20)) >> 21 |
| 314 |
s18 += carry[17] |
| 315 |
s17 -= carry[17] << 21 |
| 316 |
carry[19] = (s19 + (1 << 20)) >> 21 |
| 317 |
s20 += carry[19] |
| 318 |
s19 -= carry[19] << 21 |
| 319 |
carry[21] = (s21 + (1 << 20)) >> 21 |
| 320 |
s22 += carry[21] |
| 321 |
s21 -= carry[21] << 21 |
| 322 |
|
| 323 |
s11 += s23 * 666643 |
| 324 |
s12 += s23 * 470296 |
| 325 |
s13 += s23 * 654183 |
| 326 |
s14 -= s23 * 997805 |
| 327 |
s15 += s23 * 136657 |
| 328 |
s16 -= s23 * 683901 |
| 329 |
s23 = 0 |
| 330 |
|
| 331 |
s10 += s22 * 666643 |
| 332 |
s11 += s22 * 470296 |
| 333 |
s12 += s22 * 654183 |
| 334 |
s13 -= s22 * 997805 |
| 335 |
s14 += s22 * 136657 |
| 336 |
s15 -= s22 * 683901 |
| 337 |
s22 = 0 |
| 338 |
|
| 339 |
s9 += s21 * 666643 |
| 340 |
s10 += s21 * 470296 |
| 341 |
s11 += s21 * 654183 |
| 342 |
s12 -= s21 * 997805 |
| 343 |
s13 += s21 * 136657 |
| 344 |
s14 -= s21 * 683901 |
| 345 |
s21 = 0 |
| 346 |
|
| 347 |
s8 += s20 * 666643 |
| 348 |
s9 += s20 * 470296 |
| 349 |
s10 += s20 * 654183 |
| 350 |
s11 -= s20 * 997805 |
| 351 |
s12 += s20 * 136657 |
| 352 |
s13 -= s20 * 683901 |
| 353 |
s20 = 0 |
| 354 |
|
| 355 |
s7 += s19 * 666643 |
| 356 |
s8 += s19 * 470296 |
| 357 |
s9 += s19 * 654183 |
| 358 |
s10 -= s19 * 997805 |
| 359 |
s11 += s19 * 136657 |
| 360 |
s12 -= s19 * 683901 |
| 361 |
s19 = 0 |
| 362 |
|
| 363 |
s6 += s18 * 666643 |
| 364 |
s7 += s18 * 470296 |
| 365 |
s8 += s18 * 654183 |
| 366 |
s9 -= s18 * 997805 |
| 367 |
s10 += s18 * 136657 |
| 368 |
s11 -= s18 * 683901 |
| 369 |
s18 = 0 |
| 370 |
|
| 371 |
carry[6] = (s6 + (1 << 20)) >> 21 |
| 372 |
s7 += carry[6] |
| 373 |
s6 -= carry[6] << 21 |
| 374 |
carry[8] = (s8 + (1 << 20)) >> 21 |
| 375 |
s9 += carry[8] |
| 376 |
s8 -= carry[8] << 21 |
| 377 |
carry[10] = (s10 + (1 << 20)) >> 21 |
| 378 |
s11 += carry[10] |
| 379 |
s10 -= carry[10] << 21 |
| 380 |
carry[12] = (s12 + (1 << 20)) >> 21 |
| 381 |
s13 += carry[12] |
| 382 |
s12 -= carry[12] << 21 |
| 383 |
carry[14] = (s14 + (1 << 20)) >> 21 |
| 384 |
s15 += carry[14] |
| 385 |
s14 -= carry[14] << 21 |
| 386 |
carry[16] = (s16 + (1 << 20)) >> 21 |
| 387 |
s17 += carry[16] |
| 388 |
s16 -= carry[16] << 21 |
| 389 |
|
| 390 |
carry[7] = (s7 + (1 << 20)) >> 21 |
| 391 |
s8 += carry[7] |
| 392 |
s7 -= carry[7] << 21 |
| 393 |
carry[9] = (s9 + (1 << 20)) >> 21 |
| 394 |
s10 += carry[9] |
| 395 |
s9 -= carry[9] << 21 |
| 396 |
carry[11] = (s11 + (1 << 20)) >> 21 |
| 397 |
s12 += carry[11] |
| 398 |
s11 -= carry[11] << 21 |
| 399 |
carry[13] = (s13 + (1 << 20)) >> 21 |
| 400 |
s14 += carry[13] |
| 401 |
s13 -= carry[13] << 21 |
| 402 |
carry[15] = (s15 + (1 << 20)) >> 21 |
| 403 |
s16 += carry[15] |
| 404 |
s15 -= carry[15] << 21 |
| 405 |
|
| 406 |
s5 += s17 * 666643 |
| 407 |
s6 += s17 * 470296 |
| 408 |
s7 += s17 * 654183 |
| 409 |
s8 -= s17 * 997805 |
| 410 |
s9 += s17 * 136657 |
| 411 |
s10 -= s17 * 683901 |
| 412 |
s17 = 0 |
| 413 |
|
| 414 |
s4 += s16 * 666643 |
| 415 |
s5 += s16 * 470296 |
| 416 |
s6 += s16 * 654183 |
| 417 |
s7 -= s16 * 997805 |
| 418 |
s8 += s16 * 136657 |
| 419 |
s9 -= s16 * 683901 |
| 420 |
s16 = 0 |
| 421 |
|
| 422 |
s3 += s15 * 666643 |
| 423 |
s4 += s15 * 470296 |
| 424 |
s5 += s15 * 654183 |
| 425 |
s6 -= s15 * 997805 |
| 426 |
s7 += s15 * 136657 |
| 427 |
s8 -= s15 * 683901 |
| 428 |
s15 = 0 |
| 429 |
|
| 430 |
s2 += s14 * 666643 |
| 431 |
s3 += s14 * 470296 |
| 432 |
s4 += s14 * 654183 |
| 433 |
s5 -= s14 * 997805 |
| 434 |
s6 += s14 * 136657 |
| 435 |
s7 -= s14 * 683901 |
| 436 |
s14 = 0 |
| 437 |
|
| 438 |
s1 += s13 * 666643 |
| 439 |
s2 += s13 * 470296 |
| 440 |
s3 += s13 * 654183 |
| 441 |
s4 -= s13 * 997805 |
| 442 |
s5 += s13 * 136657 |
| 443 |
s6 -= s13 * 683901 |
| 444 |
s13 = 0 |
| 445 |
|
| 446 |
s0 += s12 * 666643 |
| 447 |
s1 += s12 * 470296 |
| 448 |
s2 += s12 * 654183 |
| 449 |
s3 -= s12 * 997805 |
| 450 |
s4 += s12 * 136657 |
| 451 |
s5 -= s12 * 683901 |
| 452 |
s12 = 0 |
| 453 |
|
| 454 |
carry[0] = (s0 + (1 << 20)) >> 21 |
| 455 |
s1 += carry[0] |
| 456 |
s0 -= carry[0] << 21 |
| 457 |
carry[2] = (s2 + (1 << 20)) >> 21 |
| 458 |
s3 += carry[2] |
| 459 |
s2 -= carry[2] << 21 |
| 460 |
carry[4] = (s4 + (1 << 20)) >> 21 |
| 461 |
s5 += carry[4] |
| 462 |
s4 -= carry[4] << 21 |
| 463 |
carry[6] = (s6 + (1 << 20)) >> 21 |
| 464 |
s7 += carry[6] |
| 465 |
s6 -= carry[6] << 21 |
| 466 |
carry[8] = (s8 + (1 << 20)) >> 21 |
| 467 |
s9 += carry[8] |
| 468 |
s8 -= carry[8] << 21 |
| 469 |
carry[10] = (s10 + (1 << 20)) >> 21 |
| 470 |
s11 += carry[10] |
| 471 |
s10 -= carry[10] << 21 |
| 472 |
|
| 473 |
carry[1] = (s1 + (1 << 20)) >> 21 |
| 474 |
s2 += carry[1] |
| 475 |
s1 -= carry[1] << 21 |
| 476 |
carry[3] = (s3 + (1 << 20)) >> 21 |
| 477 |
s4 += carry[3] |
| 478 |
s3 -= carry[3] << 21 |
| 479 |
carry[5] = (s5 + (1 << 20)) >> 21 |
| 480 |
s6 += carry[5] |
| 481 |
s5 -= carry[5] << 21 |
| 482 |
carry[7] = (s7 + (1 << 20)) >> 21 |
| 483 |
s8 += carry[7] |
| 484 |
s7 -= carry[7] << 21 |
| 485 |
carry[9] = (s9 + (1 << 20)) >> 21 |
| 486 |
s10 += carry[9] |
| 487 |
s9 -= carry[9] << 21 |
| 488 |
carry[11] = (s11 + (1 << 20)) >> 21 |
| 489 |
s12 += carry[11] |
| 490 |
s11 -= carry[11] << 21 |
| 491 |
|
| 492 |
s0 += s12 * 666643 |
| 493 |
s1 += s12 * 470296 |
| 494 |
s2 += s12 * 654183 |
| 495 |
s3 -= s12 * 997805 |
| 496 |
s4 += s12 * 136657 |
| 497 |
s5 -= s12 * 683901 |
| 498 |
s12 = 0 |
| 499 |
|
| 500 |
carry[0] = s0 >> 21 |
| 501 |
s1 += carry[0] |
| 502 |
s0 -= carry[0] << 21 |
| 503 |
carry[1] = s1 >> 21 |
| 504 |
s2 += carry[1] |
| 505 |
s1 -= carry[1] << 21 |
| 506 |
carry[2] = s2 >> 21 |
| 507 |
s3 += carry[2] |
| 508 |
s2 -= carry[2] << 21 |
| 509 |
carry[3] = s3 >> 21 |
| 510 |
s4 += carry[3] |
| 511 |
s3 -= carry[3] << 21 |
| 512 |
carry[4] = s4 >> 21 |
| 513 |
s5 += carry[4] |
| 514 |
s4 -= carry[4] << 21 |
| 515 |
carry[5] = s5 >> 21 |
| 516 |
s6 += carry[5] |
| 517 |
s5 -= carry[5] << 21 |
| 518 |
carry[6] = s6 >> 21 |
| 519 |
s7 += carry[6] |
| 520 |
s6 -= carry[6] << 21 |
| 521 |
carry[7] = s7 >> 21 |
| 522 |
s8 += carry[7] |
| 523 |
s7 -= carry[7] << 21 |
| 524 |
carry[8] = s8 >> 21 |
| 525 |
s9 += carry[8] |
| 526 |
s8 -= carry[8] << 21 |
| 527 |
carry[9] = s9 >> 21 |
| 528 |
s10 += carry[9] |
| 529 |
s9 -= carry[9] << 21 |
| 530 |
carry[10] = s10 >> 21 |
| 531 |
s11 += carry[10] |
| 532 |
s10 -= carry[10] << 21 |
| 533 |
carry[11] = s11 >> 21 |
| 534 |
s12 += carry[11] |
| 535 |
s11 -= carry[11] << 21 |
| 536 |
|
| 537 |
s0 += s12 * 666643 |
| 538 |
s1 += s12 * 470296 |
| 539 |
s2 += s12 * 654183 |
| 540 |
s3 -= s12 * 997805 |
| 541 |
s4 += s12 * 136657 |
| 542 |
s5 -= s12 * 683901 |
| 543 |
s12 = 0 |
| 544 |
|
| 545 |
carry[0] = s0 >> 21 |
| 546 |
s1 += carry[0] |
| 547 |
s0 -= carry[0] << 21 |
| 548 |
carry[1] = s1 >> 21 |
| 549 |
s2 += carry[1] |
| 550 |
s1 -= carry[1] << 21 |
| 551 |
carry[2] = s2 >> 21 |
| 552 |
s3 += carry[2] |
| 553 |
s2 -= carry[2] << 21 |
| 554 |
carry[3] = s3 >> 21 |
| 555 |
s4 += carry[3] |
| 556 |
s3 -= carry[3] << 21 |
| 557 |
carry[4] = s4 >> 21 |
| 558 |
s5 += carry[4] |
| 559 |
s4 -= carry[4] << 21 |
| 560 |
carry[5] = s5 >> 21 |
| 561 |
s6 += carry[5] |
| 562 |
s5 -= carry[5] << 21 |
| 563 |
carry[6] = s6 >> 21 |
| 564 |
s7 += carry[6] |
| 565 |
s6 -= carry[6] << 21 |
| 566 |
carry[7] = s7 >> 21 |
| 567 |
s8 += carry[7] |
| 568 |
s7 -= carry[7] << 21 |
| 569 |
carry[8] = s8 >> 21 |
| 570 |
s9 += carry[8] |
| 571 |
s8 -= carry[8] << 21 |
| 572 |
carry[9] = s9 >> 21 |
| 573 |
s10 += carry[9] |
| 574 |
s9 -= carry[9] << 21 |
| 575 |
carry[10] = s10 >> 21 |
| 576 |
s11 += carry[10] |
| 577 |
s10 -= carry[10] << 21 |
| 578 |
|
| 579 |
s[0] = byte(s0 >> 0) |
| 580 |
s[1] = byte(s0 >> 8) |
| 581 |
s[2] = byte((s0 >> 16) | (s1 << 5)) |
| 582 |
s[3] = byte(s1 >> 3) |
| 583 |
s[4] = byte(s1 >> 11) |
| 584 |
s[5] = byte((s1 >> 19) | (s2 << 2)) |
| 585 |
s[6] = byte(s2 >> 6) |
| 586 |
s[7] = byte((s2 >> 14) | (s3 << 7)) |
| 587 |
s[8] = byte(s3 >> 1) |
| 588 |
s[9] = byte(s3 >> 9) |
| 589 |
s[10] = byte((s3 >> 17) | (s4 << 4)) |
| 590 |
s[11] = byte(s4 >> 4) |
| 591 |
s[12] = byte(s4 >> 12) |
| 592 |
s[13] = byte((s4 >> 20) | (s5 << 1)) |
| 593 |
s[14] = byte(s5 >> 7) |
| 594 |
s[15] = byte((s5 >> 15) | (s6 << 6)) |
| 595 |
s[16] = byte(s6 >> 2) |
| 596 |
s[17] = byte(s6 >> 10) |
| 597 |
s[18] = byte((s6 >> 18) | (s7 << 3)) |
| 598 |
s[19] = byte(s7 >> 5) |
| 599 |
s[20] = byte(s7 >> 13) |
| 600 |
s[21] = byte(s8 >> 0) |
| 601 |
s[22] = byte(s8 >> 8) |
| 602 |
s[23] = byte((s8 >> 16) | (s9 << 5)) |
| 603 |
s[24] = byte(s9 >> 3) |
| 604 |
s[25] = byte(s9 >> 11) |
| 605 |
s[26] = byte((s9 >> 19) | (s10 << 2)) |
| 606 |
s[27] = byte(s10 >> 6) |
| 607 |
s[28] = byte((s10 >> 14) | (s11 << 7)) |
| 608 |
s[29] = byte(s11 >> 1) |
| 609 |
s[30] = byte(s11 >> 9) |
| 610 |
s[31] = byte(s11 >> 17) |
| 611 |
} |
| 612 |
|
| 613 |
// Input: |
| 614 |
// s[0]+256*s[1]+...+256^63*s[63] = s |
| 615 |
// |
| 616 |
// Output: |
| 617 |
// s[0]+256*s[1]+...+256^31*s[31] = s mod l |
| 618 |
// where l = 2^252 + 27742317777372353535851937790883648493. |
| 619 |
func scReduce(out *[32]byte, s *[64]byte) { |
| 620 |
s0 := 2097151 & load3(s[:]) |
| 621 |
s1 := 2097151 & (load4(s[2:]) >> 5) |
| 622 |
s2 := 2097151 & (load3(s[5:]) >> 2) |
| 623 |
s3 := 2097151 & (load4(s[7:]) >> 7) |
| 624 |
s4 := 2097151 & (load4(s[10:]) >> 4) |
| 625 |
s5 := 2097151 & (load3(s[13:]) >> 1) |
| 626 |
s6 := 2097151 & (load4(s[15:]) >> 6) |
| 627 |
s7 := 2097151 & (load3(s[18:]) >> 3) |
| 628 |
s8 := 2097151 & load3(s[21:]) |
| 629 |
s9 := 2097151 & (load4(s[23:]) >> 5) |
| 630 |
s10 := 2097151 & (load3(s[26:]) >> 2) |
| 631 |
s11 := 2097151 & (load4(s[28:]) >> 7) |
| 632 |
s12 := 2097151 & (load4(s[31:]) >> 4) |
| 633 |
s13 := 2097151 & (load3(s[34:]) >> 1) |
| 634 |
s14 := 2097151 & (load4(s[36:]) >> 6) |
| 635 |
s15 := 2097151 & (load3(s[39:]) >> 3) |
| 636 |
s16 := 2097151 & load3(s[42:]) |
| 637 |
s17 := 2097151 & (load4(s[44:]) >> 5) |
| 638 |
s18 := 2097151 & (load3(s[47:]) >> 2) |
| 639 |
s19 := 2097151 & (load4(s[49:]) >> 7) |
| 640 |
s20 := 2097151 & (load4(s[52:]) >> 4) |
| 641 |
s21 := 2097151 & (load3(s[55:]) >> 1) |
| 642 |
s22 := 2097151 & (load4(s[57:]) >> 6) |
| 643 |
s23 := (load4(s[60:]) >> 3) |
| 644 |
|
| 645 |
s11 += s23 * 666643 |
| 646 |
s12 += s23 * 470296 |
| 647 |
s13 += s23 * 654183 |
| 648 |
s14 -= s23 * 997805 |
| 649 |
s15 += s23 * 136657 |
| 650 |
s16 -= s23 * 683901 |
| 651 |
s23 = 0 |
| 652 |
|
| 653 |
s10 += s22 * 666643 |
| 654 |
s11 += s22 * 470296 |
| 655 |
s12 += s22 * 654183 |
| 656 |
s13 -= s22 * 997805 |
| 657 |
s14 += s22 * 136657 |
| 658 |
s15 -= s22 * 683901 |
| 659 |
s22 = 0 |
| 660 |
|
| 661 |
s9 += s21 * 666643 |
| 662 |
s10 += s21 * 470296 |
| 663 |
s11 += s21 * 654183 |
| 664 |
s12 -= s21 * 997805 |
| 665 |
s13 += s21 * 136657 |
| 666 |
s14 -= s21 * 683901 |
| 667 |
s21 = 0 |
| 668 |
|
| 669 |
s8 += s20 * 666643 |
| 670 |
s9 += s20 * 470296 |
| 671 |
s10 += s20 * 654183 |
| 672 |
s11 -= s20 * 997805 |
| 673 |
s12 += s20 * 136657 |
| 674 |
s13 -= s20 * 683901 |
| 675 |
s20 = 0 |
| 676 |
|
| 677 |
s7 += s19 * 666643 |
| 678 |
s8 += s19 * 470296 |
| 679 |
s9 += s19 * 654183 |
| 680 |
s10 -= s19 * 997805 |
| 681 |
s11 += s19 * 136657 |
| 682 |
s12 -= s19 * 683901 |
| 683 |
s19 = 0 |
| 684 |
|
| 685 |
s6 += s18 * 666643 |
| 686 |
s7 += s18 * 470296 |
| 687 |
s8 += s18 * 654183 |
| 688 |
s9 -= s18 * 997805 |
| 689 |
s10 += s18 * 136657 |
| 690 |
s11 -= s18 * 683901 |
| 691 |
s18 = 0 |
| 692 |
|
| 693 |
var carry [17]int64 |
| 694 |
|
| 695 |
carry[6] = (s6 + (1 << 20)) >> 21 |
| 696 |
s7 += carry[6] |
| 697 |
s6 -= carry[6] << 21 |
| 698 |
carry[8] = (s8 + (1 << 20)) >> 21 |
| 699 |
s9 += carry[8] |
| 700 |
s8 -= carry[8] << 21 |
| 701 |
carry[10] = (s10 + (1 << 20)) >> 21 |
| 702 |
s11 += carry[10] |
| 703 |
s10 -= carry[10] << 21 |
| 704 |
carry[12] = (s12 + (1 << 20)) >> 21 |
| 705 |
s13 += carry[12] |
| 706 |
s12 -= carry[12] << 21 |
| 707 |
carry[14] = (s14 + (1 << 20)) >> 21 |
| 708 |
s15 += carry[14] |
| 709 |
s14 -= carry[14] << 21 |
| 710 |
carry[16] = (s16 + (1 << 20)) >> 21 |
| 711 |
s17 += carry[16] |
| 712 |
s16 -= carry[16] << 21 |
| 713 |
|
| 714 |
carry[7] = (s7 + (1 << 20)) >> 21 |
| 715 |
s8 += carry[7] |
| 716 |
s7 -= carry[7] << 21 |
| 717 |
carry[9] = (s9 + (1 << 20)) >> 21 |
| 718 |
s10 += carry[9] |
| 719 |
s9 -= carry[9] << 21 |
| 720 |
carry[11] = (s11 + (1 << 20)) >> 21 |
| 721 |
s12 += carry[11] |
| 722 |
s11 -= carry[11] << 21 |
| 723 |
carry[13] = (s13 + (1 << 20)) >> 21 |
| 724 |
s14 += carry[13] |
| 725 |
s13 -= carry[13] << 21 |
| 726 |
carry[15] = (s15 + (1 << 20)) >> 21 |
| 727 |
s16 += carry[15] |
| 728 |
s15 -= carry[15] << 21 |
| 729 |
|
| 730 |
s5 += s17 * 666643 |
| 731 |
s6 += s17 * 470296 |
| 732 |
s7 += s17 * 654183 |
| 733 |
s8 -= s17 * 997805 |
| 734 |
s9 += s17 * 136657 |
| 735 |
s10 -= s17 * 683901 |
| 736 |
s17 = 0 |
| 737 |
|
| 738 |
s4 += s16 * 666643 |
| 739 |
s5 += s16 * 470296 |
| 740 |
s6 += s16 * 654183 |
| 741 |
s7 -= s16 * 997805 |
| 742 |
s8 += s16 * 136657 |
| 743 |
s9 -= s16 * 683901 |
| 744 |
s16 = 0 |
| 745 |
|
| 746 |
s3 += s15 * 666643 |
| 747 |
s4 += s15 * 470296 |
| 748 |
s5 += s15 * 654183 |
| 749 |
s6 -= s15 * 997805 |
| 750 |
s7 += s15 * 136657 |
| 751 |
s8 -= s15 * 683901 |
| 752 |
s15 = 0 |
| 753 |
|
| 754 |
s2 += s14 * 666643 |
| 755 |
s3 += s14 * 470296 |
| 756 |
s4 += s14 * 654183 |
| 757 |
s5 -= s14 * 997805 |
| 758 |
s6 += s14 * 136657 |
| 759 |
s7 -= s14 * 683901 |
| 760 |
s14 = 0 |
| 761 |
|
| 762 |
s1 += s13 * 666643 |
| 763 |
s2 += s13 * 470296 |
| 764 |
s3 += s13 * 654183 |
| 765 |
s4 -= s13 * 997805 |
| 766 |
s5 += s13 * 136657 |
| 767 |
s6 -= s13 * 683901 |
| 768 |
s13 = 0 |
| 769 |
|
| 770 |
s0 += s12 * 666643 |
| 771 |
s1 += s12 * 470296 |
| 772 |
s2 += s12 * 654183 |
| 773 |
s3 -= s12 * 997805 |
| 774 |
s4 += s12 * 136657 |
| 775 |
s5 -= s12 * 683901 |
| 776 |
s12 = 0 |
| 777 |
|
| 778 |
carry[0] = (s0 + (1 << 20)) >> 21 |
| 779 |
s1 += carry[0] |
| 780 |
s0 -= carry[0] << 21 |
| 781 |
carry[2] = (s2 + (1 << 20)) >> 21 |
| 782 |
s3 += carry[2] |
| 783 |
s2 -= carry[2] << 21 |
| 784 |
carry[4] = (s4 + (1 << 20)) >> 21 |
| 785 |
s5 += carry[4] |
| 786 |
s4 -= carry[4] << 21 |
| 787 |
carry[6] = (s6 + (1 << 20)) >> 21 |
| 788 |
s7 += carry[6] |
| 789 |
s6 -= carry[6] << 21 |
| 790 |
carry[8] = (s8 + (1 << 20)) >> 21 |
| 791 |
s9 += carry[8] |
| 792 |
s8 -= carry[8] << 21 |
| 793 |
carry[10] = (s10 + (1 << 20)) >> 21 |
| 794 |
s11 += carry[10] |
| 795 |
s10 -= carry[10] << 21 |
| 796 |
|
| 797 |
carry[1] = (s1 + (1 << 20)) >> 21 |
| 798 |
s2 += carry[1] |
| 799 |
s1 -= carry[1] << 21 |
| 800 |
carry[3] = (s3 + (1 << 20)) >> 21 |
| 801 |
s4 += carry[3] |
| 802 |
s3 -= carry[3] << 21 |
| 803 |
carry[5] = (s5 + (1 << 20)) >> 21 |
| 804 |
s6 += carry[5] |
| 805 |
s5 -= carry[5] << 21 |
| 806 |
carry[7] = (s7 + (1 << 20)) >> 21 |
| 807 |
s8 += carry[7] |
| 808 |
s7 -= carry[7] << 21 |
| 809 |
carry[9] = (s9 + (1 << 20)) >> 21 |
| 810 |
s10 += carry[9] |
| 811 |
s9 -= carry[9] << 21 |
| 812 |
carry[11] = (s11 + (1 << 20)) >> 21 |
| 813 |
s12 += carry[11] |
| 814 |
s11 -= carry[11] << 21 |
| 815 |
|
| 816 |
s0 += s12 * 666643 |
| 817 |
s1 += s12 * 470296 |
| 818 |
s2 += s12 * 654183 |
| 819 |
s3 -= s12 * 997805 |
| 820 |
s4 += s12 * 136657 |
| 821 |
s5 -= s12 * 683901 |
| 822 |
s12 = 0 |
| 823 |
|
| 824 |
carry[0] = s0 >> 21 |
| 825 |
s1 += carry[0] |
| 826 |
s0 -= carry[0] << 21 |
| 827 |
carry[1] = s1 >> 21 |
| 828 |
s2 += carry[1] |
| 829 |
s1 -= carry[1] << 21 |
| 830 |
carry[2] = s2 >> 21 |
| 831 |
s3 += carry[2] |
| 832 |
s2 -= carry[2] << 21 |
| 833 |
carry[3] = s3 >> 21 |
| 834 |
s4 += carry[3] |
| 835 |
s3 -= carry[3] << 21 |
| 836 |
carry[4] = s4 >> 21 |
| 837 |
s5 += carry[4] |
| 838 |
s4 -= carry[4] << 21 |
| 839 |
carry[5] = s5 >> 21 |
| 840 |
s6 += carry[5] |
| 841 |
s5 -= carry[5] << 21 |
| 842 |
carry[6] = s6 >> 21 |
| 843 |
s7 += carry[6] |
| 844 |
s6 -= carry[6] << 21 |
| 845 |
carry[7] = s7 >> 21 |
| 846 |
s8 += carry[7] |
| 847 |
s7 -= carry[7] << 21 |
| 848 |
carry[8] = s8 >> 21 |
| 849 |
s9 += carry[8] |
| 850 |
s8 -= carry[8] << 21 |
| 851 |
carry[9] = s9 >> 21 |
| 852 |
s10 += carry[9] |
| 853 |
s9 -= carry[9] << 21 |
| 854 |
carry[10] = s10 >> 21 |
| 855 |
s11 += carry[10] |
| 856 |
s10 -= carry[10] << 21 |
| 857 |
carry[11] = s11 >> 21 |
| 858 |
s12 += carry[11] |
| 859 |
s11 -= carry[11] << 21 |
| 860 |
|
| 861 |
s0 += s12 * 666643 |
| 862 |
s1 += s12 * 470296 |
| 863 |
s2 += s12 * 654183 |
| 864 |
s3 -= s12 * 997805 |
| 865 |
s4 += s12 * 136657 |
| 866 |
s5 -= s12 * 683901 |
| 867 |
s12 = 0 |
| 868 |
|
| 869 |
carry[0] = s0 >> 21 |
| 870 |
s1 += carry[0] |
| 871 |
s0 -= carry[0] << 21 |
| 872 |
carry[1] = s1 >> 21 |
| 873 |
s2 += carry[1] |
| 874 |
s1 -= carry[1] << 21 |
| 875 |
carry[2] = s2 >> 21 |
| 876 |
s3 += carry[2] |
| 877 |
s2 -= carry[2] << 21 |
| 878 |
carry[3] = s3 >> 21 |
| 879 |
s4 += carry[3] |
| 880 |
s3 -= carry[3] << 21 |
| 881 |
carry[4] = s4 >> 21 |
| 882 |
s5 += carry[4] |
| 883 |
s4 -= carry[4] << 21 |
| 884 |
carry[5] = s5 >> 21 |
| 885 |
s6 += carry[5] |
| 886 |
s5 -= carry[5] << 21 |
| 887 |
carry[6] = s6 >> 21 |
| 888 |
s7 += carry[6] |
| 889 |
s6 -= carry[6] << 21 |
| 890 |
carry[7] = s7 >> 21 |
| 891 |
s8 += carry[7] |
| 892 |
s7 -= carry[7] << 21 |
| 893 |
carry[8] = s8 >> 21 |
| 894 |
s9 += carry[8] |
| 895 |
s8 -= carry[8] << 21 |
| 896 |
carry[9] = s9 >> 21 |
| 897 |
s10 += carry[9] |
| 898 |
s9 -= carry[9] << 21 |
| 899 |
carry[10] = s10 >> 21 |
| 900 |
s11 += carry[10] |
| 901 |
s10 -= carry[10] << 21 |
| 902 |
|
| 903 |
out[0] = byte(s0 >> 0) |
| 904 |
out[1] = byte(s0 >> 8) |
| 905 |
out[2] = byte((s0 >> 16) | (s1 << 5)) |
| 906 |
out[3] = byte(s1 >> 3) |
| 907 |
out[4] = byte(s1 >> 11) |
| 908 |
out[5] = byte((s1 >> 19) | (s2 << 2)) |
| 909 |
out[6] = byte(s2 >> 6) |
| 910 |
out[7] = byte((s2 >> 14) | (s3 << 7)) |
| 911 |
out[8] = byte(s3 >> 1) |
| 912 |
out[9] = byte(s3 >> 9) |
| 913 |
out[10] = byte((s3 >> 17) | (s4 << 4)) |
| 914 |
out[11] = byte(s4 >> 4) |
| 915 |
out[12] = byte(s4 >> 12) |
| 916 |
out[13] = byte((s4 >> 20) | (s5 << 1)) |
| 917 |
out[14] = byte(s5 >> 7) |
| 918 |
out[15] = byte((s5 >> 15) | (s6 << 6)) |
| 919 |
out[16] = byte(s6 >> 2) |
| 920 |
out[17] = byte(s6 >> 10) |
| 921 |
out[18] = byte((s6 >> 18) | (s7 << 3)) |
| 922 |
out[19] = byte(s7 >> 5) |
| 923 |
out[20] = byte(s7 >> 13) |
| 924 |
out[21] = byte(s8 >> 0) |
| 925 |
out[22] = byte(s8 >> 8) |
| 926 |
out[23] = byte((s8 >> 16) | (s9 << 5)) |
| 927 |
out[24] = byte(s9 >> 3) |
| 928 |
out[25] = byte(s9 >> 11) |
| 929 |
out[26] = byte((s9 >> 19) | (s10 << 2)) |
| 930 |
out[27] = byte(s10 >> 6) |
| 931 |
out[28] = byte((s10 >> 14) | (s11 << 7)) |
| 932 |
out[29] = byte(s11 >> 1) |
| 933 |
out[30] = byte(s11 >> 9) |
| 934 |
out[31] = byte(s11 >> 17) |
| 935 |
} |
| 936 |
|
| 937 |
// nonAdjacentForm computes a width-w non-adjacent form for this scalar. |
| 938 |
// |
| 939 |
// w must be between 2 and 8, or nonAdjacentForm will panic. |
| 940 |
func (s *Scalar) nonAdjacentForm(w uint) [256]int8 { |
| 941 |
// This implementation is adapted from the one |
| 942 |
// in curve25519-dalek and is documented there: |
| 943 |
// https://github.com/dalek-cryptography/curve25519-dalek/blob/f630041af28e9a405255f98a8a93adca18e4315b/src/scalar.rs#L800-L871 |
| 944 |
if s.s[31] > 127 { |
| 945 |
panic("scalar has high bit set illegally") |
| 946 |
} |
| 947 |
if w < 2 { |
| 948 |
panic("w must be at least 2 by the definition of NAF") |
| 949 |
} else if w > 8 { |
| 950 |
panic("NAF digits must fit in int8") |
| 951 |
} |
| 952 |
|
| 953 |
var naf [256]int8 |
| 954 |
var digits [5]uint64 |
| 955 |
|
| 956 |
for i := 0; i < 4; i++ { |
| 957 |
digits[i] = binary.LittleEndian.Uint64(s.s[i*8:]) |
| 958 |
} |
| 959 |
|
| 960 |
width := uint64(1 << w) |
| 961 |
windowMask := uint64(width - 1) |
| 962 |
|
| 963 |
pos := uint(0) |
| 964 |
carry := uint64(0) |
| 965 |
for pos < 256 { |
| 966 |
indexU64 := pos / 64 |
| 967 |
indexBit := pos % 64 |
| 968 |
var bitBuf uint64 |
| 969 |
if indexBit < 64-w { |
| 970 |
// This window's bits are contained in a single u64 |
| 971 |
bitBuf = digits[indexU64] >> indexBit |
| 972 |
} else { |
| 973 |
// Combine the current 64 bits with bits from the next 64 |
| 974 |
bitBuf = (digits[indexU64] >> indexBit) | (digits[1+indexU64] << (64 - indexBit)) |
| 975 |
} |
| 976 |
|
| 977 |
// Add carry into the current window |
| 978 |
window := carry + (bitBuf & windowMask) |
| 979 |
|
| 980 |
if window&1 == 0 { |
| 981 |
// If the window value is even, preserve the carry and continue. |
| 982 |
// Why is the carry preserved? |
| 983 |
// If carry == 0 and window & 1 == 0, |
| 984 |
// then the next carry should be 0 |
| 985 |
// If carry == 1 and window & 1 == 0, |
| 986 |
// then bit_buf & 1 == 1 so the next carry should be 1 |
| 987 |
pos += 1 |
| 988 |
continue |
| 989 |
} |
| 990 |
|
| 991 |
if window < width/2 { |
| 992 |
carry = 0 |
| 993 |
naf[pos] = int8(window) |
| 994 |
} else { |
| 995 |
carry = 1 |
| 996 |
naf[pos] = int8(window) - int8(width) |
| 997 |
} |
| 998 |
|
| 999 |
pos += w |
| 1000 |
} |
| 1001 |
return naf |
| 1002 |
} |
| 1003 |
|
| 1004 |
func (s *Scalar) signedRadix16() [64]int8 { |
| 1005 |
if s.s[31] > 127 { |
| 1006 |
panic("scalar has high bit set illegally") |
| 1007 |
} |
| 1008 |
|
| 1009 |
var digits [64]int8 |
| 1010 |
|
| 1011 |
// Compute unsigned radix-16 digits: |
| 1012 |
for i := 0; i < 32; i++ { |
| 1013 |
digits[2*i] = int8(s.s[i] & 15) |
| 1014 |
digits[2*i+1] = int8((s.s[i] >> 4) & 15) |
| 1015 |
} |
| 1016 |
|
| 1017 |
// Recenter coefficients: |
| 1018 |
for i := 0; i < 63; i++ { |
| 1019 |
carry := (digits[i] + 8) >> 4 |
| 1020 |
digits[i] -= carry << 4 |
| 1021 |
digits[i+1] += carry |
| 1022 |
} |
| 1023 |
|
| 1024 |
return digits |
| 1025 |
} |