| 1 |
// Copyright (c) 2017 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 field implements fast arithmetic modulo 2^255-19. |
| 6 |
package field |
| 7 |
|
| 8 |
import ( |
| 9 |
"crypto/subtle" |
| 10 |
"encoding/binary" |
| 11 |
"math/bits" |
| 12 |
) |
| 13 |
|
| 14 |
// Element represents an element of the field GF(2^255-19). Note that this |
| 15 |
// is not a cryptographically secure group, and should only be used to interact |
| 16 |
// with edwards25519.Point coordinates. |
| 17 |
// |
| 18 |
// This type works similarly to math/big.Int, and all arguments and receivers |
| 19 |
// are allowed to alias. |
| 20 |
// |
| 21 |
// The zero value is a valid zero element. |
| 22 |
type Element struct { |
| 23 |
// An element t represents the integer |
| 24 |
// t.l0 + t.l1*2^51 + t.l2*2^102 + t.l3*2^153 + t.l4*2^204 |
| 25 |
// |
| 26 |
// Between operations, all limbs are expected to be lower than 2^52. |
| 27 |
l0 uint64 |
| 28 |
l1 uint64 |
| 29 |
l2 uint64 |
| 30 |
l3 uint64 |
| 31 |
l4 uint64 |
| 32 |
} |
| 33 |
|
| 34 |
const maskLow51Bits uint64 = (1 << 51) - 1 |
| 35 |
|
| 36 |
var feZero = &Element{0, 0, 0, 0, 0} |
| 37 |
|
| 38 |
// Zero sets v = 0, and returns v. |
| 39 |
func (v *Element) Zero() *Element { |
| 40 |
*v = *feZero |
| 41 |
return v |
| 42 |
} |
| 43 |
|
| 44 |
var feOne = &Element{1, 0, 0, 0, 0} |
| 45 |
|
| 46 |
// One sets v = 1, and returns v. |
| 47 |
func (v *Element) One() *Element { |
| 48 |
*v = *feOne |
| 49 |
return v |
| 50 |
} |
| 51 |
|
| 52 |
// reduce reduces v modulo 2^255 - 19 and returns it. |
| 53 |
func (v *Element) reduce() *Element { |
| 54 |
v.carryPropagate() |
| 55 |
|
| 56 |
// After the light reduction we now have a field element representation |
| 57 |
// v < 2^255 + 2^13 * 19, but need v < 2^255 - 19. |
| 58 |
|
| 59 |
// If v >= 2^255 - 19, then v + 19 >= 2^255, which would overflow 2^255 - 1, |
| 60 |
// generating a carry. That is, c will be 0 if v < 2^255 - 19, and 1 otherwise. |
| 61 |
c := (v.l0 + 19) >> 51 |
| 62 |
c = (v.l1 + c) >> 51 |
| 63 |
c = (v.l2 + c) >> 51 |
| 64 |
c = (v.l3 + c) >> 51 |
| 65 |
c = (v.l4 + c) >> 51 |
| 66 |
|
| 67 |
// If v < 2^255 - 19 and c = 0, this will be a no-op. Otherwise, it's |
| 68 |
// effectively applying the reduction identity to the carry. |
| 69 |
v.l0 += 19 * c |
| 70 |
|
| 71 |
v.l1 += v.l0 >> 51 |
| 72 |
v.l0 = v.l0 & maskLow51Bits |
| 73 |
v.l2 += v.l1 >> 51 |
| 74 |
v.l1 = v.l1 & maskLow51Bits |
| 75 |
v.l3 += v.l2 >> 51 |
| 76 |
v.l2 = v.l2 & maskLow51Bits |
| 77 |
v.l4 += v.l3 >> 51 |
| 78 |
v.l3 = v.l3 & maskLow51Bits |
| 79 |
// no additional carry |
| 80 |
v.l4 = v.l4 & maskLow51Bits |
| 81 |
|
| 82 |
return v |
| 83 |
} |
| 84 |
|
| 85 |
// Add sets v = a + b, and returns v. |
| 86 |
func (v *Element) Add(a, b *Element) *Element { |
| 87 |
v.l0 = a.l0 + b.l0 |
| 88 |
v.l1 = a.l1 + b.l1 |
| 89 |
v.l2 = a.l2 + b.l2 |
| 90 |
v.l3 = a.l3 + b.l3 |
| 91 |
v.l4 = a.l4 + b.l4 |
| 92 |
// Using the generic implementation here is actually faster than the |
| 93 |
// assembly. Probably because the body of this function is so simple that |
| 94 |
// the compiler can figure out better optimizations by inlining the carry |
| 95 |
// propagation. |
| 96 |
return v.carryPropagateGeneric() |
| 97 |
} |
| 98 |
|
| 99 |
// Subtract sets v = a - b, and returns v. |
| 100 |
func (v *Element) Subtract(a, b *Element) *Element { |
| 101 |
// We first add 2 * p, to guarantee the subtraction won't underflow, and |
| 102 |
// then subtract b (which can be up to 2^255 + 2^13 * 19). |
| 103 |
v.l0 = (a.l0 + 0xFFFFFFFFFFFDA) - b.l0 |
| 104 |
v.l1 = (a.l1 + 0xFFFFFFFFFFFFE) - b.l1 |
| 105 |
v.l2 = (a.l2 + 0xFFFFFFFFFFFFE) - b.l2 |
| 106 |
v.l3 = (a.l3 + 0xFFFFFFFFFFFFE) - b.l3 |
| 107 |
v.l4 = (a.l4 + 0xFFFFFFFFFFFFE) - b.l4 |
| 108 |
return v.carryPropagate() |
| 109 |
} |
| 110 |
|
| 111 |
// Negate sets v = -a, and returns v. |
| 112 |
func (v *Element) Negate(a *Element) *Element { |
| 113 |
return v.Subtract(feZero, a) |
| 114 |
} |
| 115 |
|
| 116 |
// Invert sets v = 1/z mod p, and returns v. |
| 117 |
// |
| 118 |
// If z == 0, Invert returns v = 0. |
| 119 |
func (v *Element) Invert(z *Element) *Element { |
| 120 |
// Inversion is implemented as exponentiation with exponent p − 2. It uses the |
| 121 |
// same sequence of 255 squarings and 11 multiplications as [Curve25519]. |
| 122 |
var z2, z9, z11, z2_5_0, z2_10_0, z2_20_0, z2_50_0, z2_100_0, t Element |
| 123 |
|
| 124 |
z2.Square(z) // 2 |
| 125 |
t.Square(&z2) // 4 |
| 126 |
t.Square(&t) // 8 |
| 127 |
z9.Multiply(&t, z) // 9 |
| 128 |
z11.Multiply(&z9, &z2) // 11 |
| 129 |
t.Square(&z11) // 22 |
| 130 |
z2_5_0.Multiply(&t, &z9) // 31 = 2^5 - 2^0 |
| 131 |
|
| 132 |
t.Square(&z2_5_0) // 2^6 - 2^1 |
| 133 |
for i := 0; i < 4; i++ { |
| 134 |
t.Square(&t) // 2^10 - 2^5 |
| 135 |
} |
| 136 |
z2_10_0.Multiply(&t, &z2_5_0) // 2^10 - 2^0 |
| 137 |
|
| 138 |
t.Square(&z2_10_0) // 2^11 - 2^1 |
| 139 |
for i := 0; i < 9; i++ { |
| 140 |
t.Square(&t) // 2^20 - 2^10 |
| 141 |
} |
| 142 |
z2_20_0.Multiply(&t, &z2_10_0) // 2^20 - 2^0 |
| 143 |
|
| 144 |
t.Square(&z2_20_0) // 2^21 - 2^1 |
| 145 |
for i := 0; i < 19; i++ { |
| 146 |
t.Square(&t) // 2^40 - 2^20 |
| 147 |
} |
| 148 |
t.Multiply(&t, &z2_20_0) // 2^40 - 2^0 |
| 149 |
|
| 150 |
t.Square(&t) // 2^41 - 2^1 |
| 151 |
for i := 0; i < 9; i++ { |
| 152 |
t.Square(&t) // 2^50 - 2^10 |
| 153 |
} |
| 154 |
z2_50_0.Multiply(&t, &z2_10_0) // 2^50 - 2^0 |
| 155 |
|
| 156 |
t.Square(&z2_50_0) // 2^51 - 2^1 |
| 157 |
for i := 0; i < 49; i++ { |
| 158 |
t.Square(&t) // 2^100 - 2^50 |
| 159 |
} |
| 160 |
z2_100_0.Multiply(&t, &z2_50_0) // 2^100 - 2^0 |
| 161 |
|
| 162 |
t.Square(&z2_100_0) // 2^101 - 2^1 |
| 163 |
for i := 0; i < 99; i++ { |
| 164 |
t.Square(&t) // 2^200 - 2^100 |
| 165 |
} |
| 166 |
t.Multiply(&t, &z2_100_0) // 2^200 - 2^0 |
| 167 |
|
| 168 |
t.Square(&t) // 2^201 - 2^1 |
| 169 |
for i := 0; i < 49; i++ { |
| 170 |
t.Square(&t) // 2^250 - 2^50 |
| 171 |
} |
| 172 |
t.Multiply(&t, &z2_50_0) // 2^250 - 2^0 |
| 173 |
|
| 174 |
t.Square(&t) // 2^251 - 2^1 |
| 175 |
t.Square(&t) // 2^252 - 2^2 |
| 176 |
t.Square(&t) // 2^253 - 2^3 |
| 177 |
t.Square(&t) // 2^254 - 2^4 |
| 178 |
t.Square(&t) // 2^255 - 2^5 |
| 179 |
|
| 180 |
return v.Multiply(&t, &z11) // 2^255 - 21 |
| 181 |
} |
| 182 |
|
| 183 |
// Set sets v = a, and returns v. |
| 184 |
func (v *Element) Set(a *Element) *Element { |
| 185 |
*v = *a |
| 186 |
return v |
| 187 |
} |
| 188 |
|
| 189 |
// SetBytes sets v to x, which must be a 32-byte little-endian encoding. |
| 190 |
// |
| 191 |
// Consistent with RFC 7748, the most significant bit (the high bit of the |
| 192 |
// last byte) is ignored, and non-canonical values (2^255-19 through 2^255-1) |
| 193 |
// are accepted. Note that this is laxer than specified by RFC 8032. |
| 194 |
func (v *Element) SetBytes(x []byte) *Element { |
| 195 |
if len(x) != 32 { |
| 196 |
panic("edwards25519: invalid field element input size") |
| 197 |
} |
| 198 |
|
| 199 |
// Bits 0:51 (bytes 0:8, bits 0:64, shift 0, mask 51). |
| 200 |
v.l0 = binary.LittleEndian.Uint64(x[0:8]) |
| 201 |
v.l0 &= maskLow51Bits |
| 202 |
// Bits 51:102 (bytes 6:14, bits 48:112, shift 3, mask 51). |
| 203 |
v.l1 = binary.LittleEndian.Uint64(x[6:14]) >> 3 |
| 204 |
v.l1 &= maskLow51Bits |
| 205 |
// Bits 102:153 (bytes 12:20, bits 96:160, shift 6, mask 51). |
| 206 |
v.l2 = binary.LittleEndian.Uint64(x[12:20]) >> 6 |
| 207 |
v.l2 &= maskLow51Bits |
| 208 |
// Bits 153:204 (bytes 19:27, bits 152:216, shift 1, mask 51). |
| 209 |
v.l3 = binary.LittleEndian.Uint64(x[19:27]) >> 1 |
| 210 |
v.l3 &= maskLow51Bits |
| 211 |
// Bits 204:251 (bytes 24:32, bits 192:256, shift 12, mask 51). |
| 212 |
// Note: not bytes 25:33, shift 4, to avoid overread. |
| 213 |
v.l4 = binary.LittleEndian.Uint64(x[24:32]) >> 12 |
| 214 |
v.l4 &= maskLow51Bits |
| 215 |
|
| 216 |
return v |
| 217 |
} |
| 218 |
|
| 219 |
// Bytes returns the canonical 32-byte little-endian encoding of v. |
| 220 |
func (v *Element) Bytes() []byte { |
| 221 |
// This function is outlined to make the allocations inline in the caller |
| 222 |
// rather than happen on the heap. |
| 223 |
var out [32]byte |
| 224 |
return v.bytes(&out) |
| 225 |
} |
| 226 |
|
| 227 |
func (v *Element) bytes(out *[32]byte) []byte { |
| 228 |
t := *v |
| 229 |
t.reduce() |
| 230 |
|
| 231 |
var buf [8]byte |
| 232 |
for i, l := range [5]uint64{t.l0, t.l1, t.l2, t.l3, t.l4} { |
| 233 |
bitsOffset := i * 51 |
| 234 |
binary.LittleEndian.PutUint64(buf[:], l<<uint(bitsOffset%8)) |
| 235 |
for i, bb := range buf { |
| 236 |
off := bitsOffset/8 + i |
| 237 |
if off >= len(out) { |
| 238 |
break |
| 239 |
} |
| 240 |
out[off] |= bb |
| 241 |
} |
| 242 |
} |
| 243 |
|
| 244 |
return out[:] |
| 245 |
} |
| 246 |
|
| 247 |
// Equal returns 1 if v and u are equal, and 0 otherwise. |
| 248 |
func (v *Element) Equal(u *Element) int { |
| 249 |
sa, sv := u.Bytes(), v.Bytes() |
| 250 |
return subtle.ConstantTimeCompare(sa, sv) |
| 251 |
} |
| 252 |
|
| 253 |
// mask64Bits returns 0xffffffff if cond is 1, and 0 otherwise. |
| 254 |
func mask64Bits(cond int) uint64 { return ^(uint64(cond) - 1) } |
| 255 |
|
| 256 |
// Select sets v to a if cond == 1, and to b if cond == 0. |
| 257 |
func (v *Element) Select(a, b *Element, cond int) *Element { |
| 258 |
m := mask64Bits(cond) |
| 259 |
v.l0 = (m & a.l0) | (^m & b.l0) |
| 260 |
v.l1 = (m & a.l1) | (^m & b.l1) |
| 261 |
v.l2 = (m & a.l2) | (^m & b.l2) |
| 262 |
v.l3 = (m & a.l3) | (^m & b.l3) |
| 263 |
v.l4 = (m & a.l4) | (^m & b.l4) |
| 264 |
return v |
| 265 |
} |
| 266 |
|
| 267 |
// Swap swaps v and u if cond == 1 or leaves them unchanged if cond == 0, and returns v. |
| 268 |
func (v *Element) Swap(u *Element, cond int) { |
| 269 |
m := mask64Bits(cond) |
| 270 |
t := m & (v.l0 ^ u.l0) |
| 271 |
v.l0 ^= t |
| 272 |
u.l0 ^= t |
| 273 |
t = m & (v.l1 ^ u.l1) |
| 274 |
v.l1 ^= t |
| 275 |
u.l1 ^= t |
| 276 |
t = m & (v.l2 ^ u.l2) |
| 277 |
v.l2 ^= t |
| 278 |
u.l2 ^= t |
| 279 |
t = m & (v.l3 ^ u.l3) |
| 280 |
v.l3 ^= t |
| 281 |
u.l3 ^= t |
| 282 |
t = m & (v.l4 ^ u.l4) |
| 283 |
v.l4 ^= t |
| 284 |
u.l4 ^= t |
| 285 |
} |
| 286 |
|
| 287 |
// IsNegative returns 1 if v is negative, and 0 otherwise. |
| 288 |
func (v *Element) IsNegative() int { |
| 289 |
return int(v.Bytes()[0] & 1) |
| 290 |
} |
| 291 |
|
| 292 |
// Absolute sets v to |u|, and returns v. |
| 293 |
func (v *Element) Absolute(u *Element) *Element { |
| 294 |
return v.Select(new(Element).Negate(u), u, u.IsNegative()) |
| 295 |
} |
| 296 |
|
| 297 |
// Multiply sets v = x * y, and returns v. |
| 298 |
func (v *Element) Multiply(x, y *Element) *Element { |
| 299 |
feMul(v, x, y) |
| 300 |
return v |
| 301 |
} |
| 302 |
|
| 303 |
// Square sets v = x * x, and returns v. |
| 304 |
func (v *Element) Square(x *Element) *Element { |
| 305 |
feSquare(v, x) |
| 306 |
return v |
| 307 |
} |
| 308 |
|
| 309 |
// Mult32 sets v = x * y, and returns v. |
| 310 |
func (v *Element) Mult32(x *Element, y uint32) *Element { |
| 311 |
x0lo, x0hi := mul51(x.l0, y) |
| 312 |
x1lo, x1hi := mul51(x.l1, y) |
| 313 |
x2lo, x2hi := mul51(x.l2, y) |
| 314 |
x3lo, x3hi := mul51(x.l3, y) |
| 315 |
x4lo, x4hi := mul51(x.l4, y) |
| 316 |
v.l0 = x0lo + 19*x4hi // carried over per the reduction identity |
| 317 |
v.l1 = x1lo + x0hi |
| 318 |
v.l2 = x2lo + x1hi |
| 319 |
v.l3 = x3lo + x2hi |
| 320 |
v.l4 = x4lo + x3hi |
| 321 |
// The hi portions are going to be only 32 bits, plus any previous excess, |
| 322 |
// so we can skip the carry propagation. |
| 323 |
return v |
| 324 |
} |
| 325 |
|
| 326 |
// mul51 returns lo + hi * 2⁵¹ = a * b. |
| 327 |
func mul51(a uint64, b uint32) (lo uint64, hi uint64) { |
| 328 |
mh, ml := bits.Mul64(a, uint64(b)) |
| 329 |
lo = ml & maskLow51Bits |
| 330 |
hi = (mh << 13) | (ml >> 51) |
| 331 |
return |
| 332 |
} |
| 333 |
|
| 334 |
// Pow22523 set v = x^((p-5)/8), and returns v. (p-5)/8 is 2^252-3. |
| 335 |
func (v *Element) Pow22523(x *Element) *Element { |
| 336 |
var t0, t1, t2 Element |
| 337 |
|
| 338 |
t0.Square(x) // x^2 |
| 339 |
t1.Square(&t0) // x^4 |
| 340 |
t1.Square(&t1) // x^8 |
| 341 |
t1.Multiply(x, &t1) // x^9 |
| 342 |
t0.Multiply(&t0, &t1) // x^11 |
| 343 |
t0.Square(&t0) // x^22 |
| 344 |
t0.Multiply(&t1, &t0) // x^31 |
| 345 |
t1.Square(&t0) // x^62 |
| 346 |
for i := 1; i < 5; i++ { // x^992 |
| 347 |
t1.Square(&t1) |
| 348 |
} |
| 349 |
t0.Multiply(&t1, &t0) // x^1023 -> 1023 = 2^10 - 1 |
| 350 |
t1.Square(&t0) // 2^11 - 2 |
| 351 |
for i := 1; i < 10; i++ { // 2^20 - 2^10 |
| 352 |
t1.Square(&t1) |
| 353 |
} |
| 354 |
t1.Multiply(&t1, &t0) // 2^20 - 1 |
| 355 |
t2.Square(&t1) // 2^21 - 2 |
| 356 |
for i := 1; i < 20; i++ { // 2^40 - 2^20 |
| 357 |
t2.Square(&t2) |
| 358 |
} |
| 359 |
t1.Multiply(&t2, &t1) // 2^40 - 1 |
| 360 |
t1.Square(&t1) // 2^41 - 2 |
| 361 |
for i := 1; i < 10; i++ { // 2^50 - 2^10 |
| 362 |
t1.Square(&t1) |
| 363 |
} |
| 364 |
t0.Multiply(&t1, &t0) // 2^50 - 1 |
| 365 |
t1.Square(&t0) // 2^51 - 2 |
| 366 |
for i := 1; i < 50; i++ { // 2^100 - 2^50 |
| 367 |
t1.Square(&t1) |
| 368 |
} |
| 369 |
t1.Multiply(&t1, &t0) // 2^100 - 1 |
| 370 |
t2.Square(&t1) // 2^101 - 2 |
| 371 |
for i := 1; i < 100; i++ { // 2^200 - 2^100 |
| 372 |
t2.Square(&t2) |
| 373 |
} |
| 374 |
t1.Multiply(&t2, &t1) // 2^200 - 1 |
| 375 |
t1.Square(&t1) // 2^201 - 2 |
| 376 |
for i := 1; i < 50; i++ { // 2^250 - 2^50 |
| 377 |
t1.Square(&t1) |
| 378 |
} |
| 379 |
t0.Multiply(&t1, &t0) // 2^250 - 1 |
| 380 |
t0.Square(&t0) // 2^251 - 2 |
| 381 |
t0.Square(&t0) // 2^252 - 4 |
| 382 |
return v.Multiply(&t0, x) // 2^252 - 3 -> x^(2^252-3) |
| 383 |
} |
| 384 |
|
| 385 |
// sqrtM1 is 2^((p-1)/4), which squared is equal to -1 by Euler's Criterion. |
| 386 |
var sqrtM1 = &Element{1718705420411056, 234908883556509, |
| 387 |
2233514472574048, 2117202627021982, 765476049583133} |
| 388 |
|
| 389 |
// SqrtRatio sets r to the non-negative square root of the ratio of u and v. |
| 390 |
// |
| 391 |
// If u/v is square, SqrtRatio returns r and 1. If u/v is not square, SqrtRatio |
| 392 |
// sets r according to Section 4.3 of draft-irtf-cfrg-ristretto255-decaf448-00, |
| 393 |
// and returns r and 0. |
| 394 |
func (r *Element) SqrtRatio(u, v *Element) (rr *Element, wasSquare int) { |
| 395 |
var a, b Element |
| 396 |
|
| 397 |
// r = (u * v3) * (u * v7)^((p-5)/8) |
| 398 |
v2 := a.Square(v) |
| 399 |
uv3 := b.Multiply(u, b.Multiply(v2, v)) |
| 400 |
uv7 := a.Multiply(uv3, a.Square(v2)) |
| 401 |
r.Multiply(uv3, r.Pow22523(uv7)) |
| 402 |
|
| 403 |
check := a.Multiply(v, a.Square(r)) // check = v * r^2 |
| 404 |
|
| 405 |
uNeg := b.Negate(u) |
| 406 |
correctSignSqrt := check.Equal(u) |
| 407 |
flippedSignSqrt := check.Equal(uNeg) |
| 408 |
flippedSignSqrtI := check.Equal(uNeg.Multiply(uNeg, sqrtM1)) |
| 409 |
|
| 410 |
rPrime := b.Multiply(r, sqrtM1) // r_prime = SQRT_M1 * r |
| 411 |
// r = CT_SELECT(r_prime IF flipped_sign_sqrt | flipped_sign_sqrt_i ELSE r) |
| 412 |
r.Select(rPrime, r, flippedSignSqrt|flippedSignSqrtI) |
| 413 |
|
| 414 |
r.Absolute(r) // Choose the nonnegative square root. |
| 415 |
return r, correctSignSqrt | flippedSignSqrt |
| 416 |
} |