1// Copyright 2022 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//go:build (amd64 || arm64) && !purego 6 7package nistec 8 9import "errors" 10 11// Montgomery multiplication modulo org(G). Sets res = in1 * in2 * R⁻¹. 12// 13//go:noescape 14func p256OrdMul(res, in1, in2 *p256OrdElement) 15 16// Montgomery square modulo org(G), repeated n times (n >= 1). 17// 18//go:noescape 19func p256OrdSqr(res, in *p256OrdElement, n int) 20 21func P256OrdInverse(k []byte) ([]byte, error) { 22 if len(k) != 32 { 23 return nil, errors.New("invalid scalar length") 24 } 25 26 x := new(p256OrdElement) 27 p256OrdBigToLittle(x, (*[32]byte)(k)) 28 p256OrdReduce(x) 29 30 // Inversion is implemented as exponentiation by n - 2, per Fermat's little theorem. 31 // 32 // The sequence of 38 multiplications and 254 squarings is derived from 33 // https://briansmith.org/ecc-inversion-addition-chains-01#p256_scalar_inversion 34 _1 := new(p256OrdElement) 35 _11 := new(p256OrdElement) 36 _101 := new(p256OrdElement) 37 _111 := new(p256OrdElement) 38 _1111 := new(p256OrdElement) 39 _10101 := new(p256OrdElement) 40 _101111 := new(p256OrdElement) 41 t := new(p256OrdElement) 42 43 // This code operates in the Montgomery domain where R = 2²⁵⁶ mod n and n is 44 // the order of the scalar field. Elements in the Montgomery domain take the 45 // form a×R and p256OrdMul calculates (a × b × R⁻¹) mod n. RR is R in the 46 // domain, or R×R mod n, thus p256OrdMul(x, RR) gives x×R, i.e. converts x 47 // into the Montgomery domain. 48 RR := &p256OrdElement{0x83244c95be79eea2, 0x4699799c49bd6fa6, 49 0x2845b2392b6bec59, 0x66e12d94f3d95620} 50 51 p256OrdMul(_1, x, RR) // _1 52 p256OrdSqr(x, _1, 1) // _10 53 p256OrdMul(_11, x, _1) // _11 54 p256OrdMul(_101, x, _11) // _101 55 p256OrdMul(_111, x, _101) // _111 56 p256OrdSqr(x, _101, 1) // _1010 57 p256OrdMul(_1111, _101, x) // _1111 58 59 p256OrdSqr(t, x, 1) // _10100 60 p256OrdMul(_10101, t, _1) // _10101 61 p256OrdSqr(x, _10101, 1) // _101010 62 p256OrdMul(_101111, _101, x) // _101111 63 p256OrdMul(x, _10101, x) // _111111 = x6 64 p256OrdSqr(t, x, 2) // _11111100 65 p256OrdMul(t, t, _11) // _11111111 = x8 66 p256OrdSqr(x, t, 8) // _ff00 67 p256OrdMul(x, x, t) // _ffff = x16 68 p256OrdSqr(t, x, 16) // _ffff0000 69 p256OrdMul(t, t, x) // _ffffffff = x32 70 71 p256OrdSqr(x, t, 64) 72 p256OrdMul(x, x, t) 73 p256OrdSqr(x, x, 32) 74 p256OrdMul(x, x, t) 75 76 sqrs := []int{ 77 6, 5, 4, 5, 5, 78 4, 3, 3, 5, 9, 79 6, 2, 5, 6, 5, 80 4, 5, 5, 3, 10, 81 2, 5, 5, 3, 7, 6} 82 muls := []*p256OrdElement{ 83 _101111, _111, _11, _1111, _10101, 84 _101, _101, _101, _111, _101111, 85 _1111, _1, _1, _1111, _111, 86 _111, _111, _101, _11, _101111, 87 _11, _11, _11, _1, _10101, _1111} 88 89 for i, s := range sqrs { 90 p256OrdSqr(x, x, s) 91 p256OrdMul(x, x, muls[i]) 92 } 93 94 // Montgomery multiplication by R⁻¹, or 1 outside the domain as R⁻¹×R = 1, 95 // converts a Montgomery value out of the domain. 96 one := &p256OrdElement{1} 97 p256OrdMul(x, x, one) 98 99 var xOut [32]byte 100 p256OrdLittleToBig(&xOut, x) 101 return xOut[:], nil 102} 103