Source file src/crypto/internal/fips140/nistec/p256_ordinv.go

     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  package nistec
     6  
     7  import "math/bits"
     8  
     9  // P256OrdInverse sets k to the inverse of k modulo ord(G). k is encoded as four
    10  // uint64 limbs in little-endian order, and must be reduced. If k is zero, the
    11  // result is zero.
    12  func P256OrdInverse(k *[4]uint64) {
    13  	// Inversion is implemented as exponentiation by n - 2, per Fermat's little theorem.
    14  	//
    15  	// The sequence of 38 multiplications and 254 squarings is derived from
    16  	// https://briansmith.org/ecc-inversion-addition-chains-01#p256_scalar_inversion
    17  	_1 := new(p256OrdMontElement)
    18  	_11 := new(p256OrdMontElement)
    19  	_101 := new(p256OrdMontElement)
    20  	_111 := new(p256OrdMontElement)
    21  	_1111 := new(p256OrdMontElement)
    22  	_10101 := new(p256OrdMontElement)
    23  	_101111 := new(p256OrdMontElement)
    24  	x := new(p256OrdMontElement)
    25  	t := new(p256OrdMontElement)
    26  
    27  	j := (*p256OrdElement)(k)
    28  	p256OrdToMontgomery(_1, j) // _1
    29  	p256OrdSqr(x, _1, 1)       // _10
    30  	p256OrdMul(_11, x, _1)     // _11
    31  	p256OrdMul(_101, x, _11)   // _101
    32  	p256OrdMul(_111, x, _101)  // _111
    33  	p256OrdSqr(x, _101, 1)     // _1010
    34  	p256OrdMul(_1111, _101, x) // _1111
    35  
    36  	p256OrdSqr(t, x, 1)          // _10100
    37  	p256OrdMul(_10101, t, _1)    // _10101
    38  	p256OrdSqr(x, _10101, 1)     // _101010
    39  	p256OrdMul(_101111, _101, x) // _101111
    40  	p256OrdMul(x, _10101, x)     // _111111 = x6
    41  	p256OrdSqr(t, x, 2)          // _11111100
    42  	p256OrdMul(t, t, _11)        // _11111111 = x8
    43  	p256OrdSqr(x, t, 8)          // _ff00
    44  	p256OrdMul(x, x, t)          // _ffff = x16
    45  	p256OrdSqr(t, x, 16)         // _ffff0000
    46  	p256OrdMul(t, t, x)          // _ffffffff = x32
    47  
    48  	p256OrdSqr(x, t, 64)
    49  	p256OrdMul(x, x, t)
    50  	p256OrdSqr(x, x, 32)
    51  	p256OrdMul(x, x, t)
    52  
    53  	sqrs := []int{
    54  		6, 5, 4, 5, 5,
    55  		4, 3, 3, 5, 9,
    56  		6, 2, 5, 6, 5,
    57  		4, 5, 5, 3, 10,
    58  		2, 5, 5, 3, 7, 6}
    59  	muls := []*p256OrdMontElement{
    60  		_101111, _111, _11, _1111, _10101,
    61  		_101, _101, _101, _111, _101111,
    62  		_1111, _1, _1, _1111, _111,
    63  		_111, _111, _101, _11, _101111,
    64  		_11, _11, _11, _1, _10101, _1111}
    65  
    66  	for i, s := range sqrs {
    67  		p256OrdSqr(x, x, s)
    68  		p256OrdMul(x, x, muls[i])
    69  	}
    70  
    71  	p256OrdFromMontgomery(j, x)
    72  }
    73  
    74  // The code below was generated by Fiat Cryptography v0.1.6-63-g92ee794c2, and
    75  // then manually formatted and optimized.
    76  //
    77  //	word-by-word-montgomery --lang Go --no-wide-int
    78  //	--relax-primitive-carry-to-bitwidth 32,64 --cmovznz-by-mul --static
    79  //	--package-case flatcase --private-function-case camelCase --private-type-case
    80  //	camelCase --no-prefix-fiat --package-name nistec p256Ord 64
    81  //	2^256-2^224+2^192-89188191075325690597107910205041859247
    82  //  mul square from_montgomery to_montgomery
    83  //
    84  // https://mit-plv.github.io/fiat-crypto/
    85  //
    86  //	 Copyright (c) 2015-2020 the fiat-crypto authors (see the AUTHORS file)
    87  //	 All rights reserved.
    88  //
    89  //	 Redistribution and use in source and binary forms, with or without
    90  //	 modification, are permitted provided that the following conditions are
    91  //	 met:
    92  //
    93  //	 	1. Redistributions of source code must retain the above copyright
    94  //	 	notice, this list of conditions and the following disclaimer.
    95  //
    96  //	 THIS SOFTWARE IS PROVIDED BY the fiat-crypto authors "AS IS"
    97  //	 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
    98  //	 THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
    99  //	 PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL Berkeley Software Design,
   100  //	 Inc. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   101  //	 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   102  //	 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
   103  //	 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
   104  //	 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
   105  //	 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   106  //	 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   107  //
   108  
   109  // p256OrdMontElement is a scalar field element in the Montgomery domain, as
   110  // four uint64 limbs in little-endian order. It must be strictly less than
   111  // ord(G) and in Montgomery form (with R 2²⁵⁶).
   112  type p256OrdMontElement [4]uint64
   113  
   114  // p256OrdMul multiplies two field elements in the Montgomery domain.
   115  func p256OrdMul(out1 *p256OrdMontElement, arg1 *p256OrdMontElement, arg2 *p256OrdMontElement) {
   116  	x1 := arg1[1]
   117  	x2 := arg1[2]
   118  	x3 := arg1[3]
   119  	x4 := arg1[0]
   120  	x6, x5 := bits.Mul64(x4, arg2[3])
   121  	x8, x7 := bits.Mul64(x4, arg2[2])
   122  	x10, x9 := bits.Mul64(x4, arg2[1])
   123  	x12, x11 := bits.Mul64(x4, arg2[0])
   124  	x13, x14 := bits.Add64(x12, x9, 0)
   125  	x15, x16 := bits.Add64(x10, x7, x14)
   126  	x17, x18 := bits.Add64(x8, x5, x16)
   127  	x19 := x18 + x6
   128  	_, x20 := bits.Mul64(x11, 0xccd1c8aaee00bc4f)
   129  	// x20 * 0xffffffff00000000 = x20 * (2^64 - 2^32)
   130  	x22, b22 := bits.Sub64(0, x20<<32, 0)
   131  	x23 := x20 - (x20 >> 32) - b22
   132  	// x20 * 0xffffffffffffffff = x20 * (2^64 - 1)
   133  	x24, b24 := bits.Sub64(0, x20, 0)
   134  	x25 := x20 - b24
   135  	x27, x26 := bits.Mul64(x20, 0xbce6faada7179e84)
   136  	x29, x28 := bits.Mul64(x20, 0xf3b9cac2fc632551)
   137  	x30, x31 := bits.Add64(x29, x26, 0)
   138  	x32, x33 := bits.Add64(x27, x24, x31)
   139  	x34, x35 := bits.Add64(x25, x22, x33)
   140  	x36 := x35 + x23
   141  	_, x38 := bits.Add64(x11, x28, 0)
   142  	x39, x40 := bits.Add64(x13, x30, x38)
   143  	x41, x42 := bits.Add64(x15, x32, x40)
   144  	x43, x44 := bits.Add64(x17, x34, x42)
   145  	x45, x46 := bits.Add64(x19, x36, x44)
   146  	x48, x47 := bits.Mul64(x1, arg2[3])
   147  	x50, x49 := bits.Mul64(x1, arg2[2])
   148  	x52, x51 := bits.Mul64(x1, arg2[1])
   149  	x54, x53 := bits.Mul64(x1, arg2[0])
   150  	x55, x56 := bits.Add64(x54, x51, 0)
   151  	x57, x58 := bits.Add64(x52, x49, x56)
   152  	x59, x60 := bits.Add64(x50, x47, x58)
   153  	x61 := x60 + x48
   154  	x62, x63 := bits.Add64(x39, x53, 0)
   155  	x64, x65 := bits.Add64(x41, x55, x63)
   156  	x66, x67 := bits.Add64(x43, x57, x65)
   157  	x68, x69 := bits.Add64(x45, x59, x67)
   158  	x70, x71 := bits.Add64(x46, x61, x69)
   159  	_, x72 := bits.Mul64(x62, 0xccd1c8aaee00bc4f)
   160  	x74, b74 := bits.Sub64(0, x72<<32, 0)
   161  	x75 := x72 - (x72 >> 32) - b74
   162  	x76, b76 := bits.Sub64(0, x72, 0)
   163  	x77 := x72 - b76
   164  	x79, x78 := bits.Mul64(x72, 0xbce6faada7179e84)
   165  	x81, x80 := bits.Mul64(x72, 0xf3b9cac2fc632551)
   166  	x82, x83 := bits.Add64(x81, x78, 0)
   167  	x84, x85 := bits.Add64(x79, x76, x83)
   168  	x86, x87 := bits.Add64(x77, x74, x85)
   169  	x88 := x87 + x75
   170  	_, x90 := bits.Add64(x62, x80, 0)
   171  	x91, x92 := bits.Add64(x64, x82, x90)
   172  	x93, x94 := bits.Add64(x66, x84, x92)
   173  	x95, x96 := bits.Add64(x68, x86, x94)
   174  	x97, x98 := bits.Add64(x70, x88, x96)
   175  	x99 := x98 + x71
   176  	x101, x100 := bits.Mul64(x2, arg2[3])
   177  	x103, x102 := bits.Mul64(x2, arg2[2])
   178  	x105, x104 := bits.Mul64(x2, arg2[1])
   179  	x107, x106 := bits.Mul64(x2, arg2[0])
   180  	x108, x109 := bits.Add64(x107, x104, 0)
   181  	x110, x111 := bits.Add64(x105, x102, x109)
   182  	x112, x113 := bits.Add64(x103, x100, x111)
   183  	x114 := x113 + x101
   184  	x115, x116 := bits.Add64(x91, x106, 0)
   185  	x117, x118 := bits.Add64(x93, x108, x116)
   186  	x119, x120 := bits.Add64(x95, x110, x118)
   187  	x121, x122 := bits.Add64(x97, x112, x120)
   188  	x123, x124 := bits.Add64(x99, x114, x122)
   189  	_, x125 := bits.Mul64(x115, 0xccd1c8aaee00bc4f)
   190  	x127, b127 := bits.Sub64(0, x125<<32, 0)
   191  	x128 := x125 - (x125 >> 32) - b127
   192  	x129, b129 := bits.Sub64(0, x125, 0)
   193  	x130 := x125 - b129
   194  	x132, x131 := bits.Mul64(x125, 0xbce6faada7179e84)
   195  	x134, x133 := bits.Mul64(x125, 0xf3b9cac2fc632551)
   196  	x135, x136 := bits.Add64(x134, x131, 0)
   197  	x137, x138 := bits.Add64(x132, x129, x136)
   198  	x139, x140 := bits.Add64(x130, x127, x138)
   199  	x141 := x140 + x128
   200  	_, x143 := bits.Add64(x115, x133, 0)
   201  	x144, x145 := bits.Add64(x117, x135, x143)
   202  	x146, x147 := bits.Add64(x119, x137, x145)
   203  	x148, x149 := bits.Add64(x121, x139, x147)
   204  	x150, x151 := bits.Add64(x123, x141, x149)
   205  	x152 := x151 + x124
   206  	x154, x153 := bits.Mul64(x3, arg2[3])
   207  	x156, x155 := bits.Mul64(x3, arg2[2])
   208  	x158, x157 := bits.Mul64(x3, arg2[1])
   209  	x160, x159 := bits.Mul64(x3, arg2[0])
   210  	x161, x162 := bits.Add64(x160, x157, 0)
   211  	x163, x164 := bits.Add64(x158, x155, x162)
   212  	x165, x166 := bits.Add64(x156, x153, x164)
   213  	x167 := x166 + x154
   214  	x168, x169 := bits.Add64(x144, x159, 0)
   215  	x170, x171 := bits.Add64(x146, x161, x169)
   216  	x172, x173 := bits.Add64(x148, x163, x171)
   217  	x174, x175 := bits.Add64(x150, x165, x173)
   218  	x176, x177 := bits.Add64(x152, x167, x175)
   219  	_, x178 := bits.Mul64(x168, 0xccd1c8aaee00bc4f)
   220  	x180, b180 := bits.Sub64(0, x178<<32, 0)
   221  	x181 := x178 - (x178 >> 32) - b180
   222  	x182, b182 := bits.Sub64(0, x178, 0)
   223  	x183 := x178 - b182
   224  	x185, x184 := bits.Mul64(x178, 0xbce6faada7179e84)
   225  	x187, x186 := bits.Mul64(x178, 0xf3b9cac2fc632551)
   226  	x188, x189 := bits.Add64(x187, x184, 0)
   227  	x190, x191 := bits.Add64(x185, x182, x189)
   228  	x192, x193 := bits.Add64(x183, x180, x191)
   229  	x194 := x193 + x181
   230  	_, x196 := bits.Add64(x168, x186, 0)
   231  	x197, x198 := bits.Add64(x170, x188, x196)
   232  	x199, x200 := bits.Add64(x172, x190, x198)
   233  	x201, x202 := bits.Add64(x174, x192, x200)
   234  	x203, x204 := bits.Add64(x176, x194, x202)
   235  	x205 := x204 + x177
   236  	x206, x207 := bits.Sub64(x197, 0xf3b9cac2fc632551, 0)
   237  	x208, x209 := bits.Sub64(x199, 0xbce6faada7179e84, x207)
   238  	x210, x211 := bits.Sub64(x201, 0xffffffffffffffff, x209)
   239  	x212, x213 := bits.Sub64(x203, 0xffffffff00000000, x211)
   240  	_, x215 := bits.Sub64(x205, 0, x213)
   241  	mask, _ := bits.Sub64(0, 0, x215)
   242  	out1[0] = x206&^mask | x197&mask
   243  	out1[1] = x208&^mask | x199&mask
   244  	out1[2] = x210&^mask | x201&mask
   245  	out1[3] = x212&^mask | x203&mask
   246  }
   247  
   248  // p256OrdSqr squares n times a field element in the Montgomery domain.
   249  func p256OrdSqr(out1 *p256OrdMontElement, arg1 *p256OrdMontElement, n int) {
   250  	x1 := arg1[1]
   251  	x2 := arg1[2]
   252  	x3 := arg1[3]
   253  	x4 := arg1[0]
   254  	for range n {
   255  		x6, x5 := bits.Mul64(x4, x3)
   256  		x8, x7 := bits.Mul64(x4, x2)
   257  		x10, x9 := bits.Mul64(x4, x1)
   258  		x12, x11 := bits.Mul64(x4, x4)
   259  		x13, x14 := bits.Add64(x12, x9, 0)
   260  		x15, x16 := bits.Add64(x10, x7, x14)
   261  		x17, x18 := bits.Add64(x8, x5, x16)
   262  		x19 := x18 + x6
   263  		_, x20 := bits.Mul64(x11, 0xccd1c8aaee00bc4f)
   264  		x22, b22 := bits.Sub64(0, x20<<32, 0)
   265  		x23 := x20 - (x20 >> 32) - b22
   266  		x24, b24 := bits.Sub64(0, x20, 0)
   267  		x25 := x20 - b24
   268  		x27, x26 := bits.Mul64(x20, 0xbce6faada7179e84)
   269  		x29, x28 := bits.Mul64(x20, 0xf3b9cac2fc632551)
   270  		x30, x31 := bits.Add64(x29, x26, 0)
   271  		x32, x33 := bits.Add64(x27, x24, x31)
   272  		x34, x35 := bits.Add64(x25, x22, x33)
   273  		x36 := x35 + x23
   274  		_, x38 := bits.Add64(x11, x28, 0)
   275  		x39, x40 := bits.Add64(x13, x30, x38)
   276  		x41, x42 := bits.Add64(x15, x32, x40)
   277  		x43, x44 := bits.Add64(x17, x34, x42)
   278  		x45, x46 := bits.Add64(x19, x36, x44)
   279  		x48, x47 := bits.Mul64(x1, x3)
   280  		x50, x49 := bits.Mul64(x1, x2)
   281  		x52, x51 := bits.Mul64(x1, x1)
   282  		x54, x53 := bits.Mul64(x1, x4)
   283  		x55, x56 := bits.Add64(x54, x51, 0)
   284  		x57, x58 := bits.Add64(x52, x49, x56)
   285  		x59, x60 := bits.Add64(x50, x47, x58)
   286  		x61 := x60 + x48
   287  		x62, x63 := bits.Add64(x39, x53, 0)
   288  		x64, x65 := bits.Add64(x41, x55, x63)
   289  		x66, x67 := bits.Add64(x43, x57, x65)
   290  		x68, x69 := bits.Add64(x45, x59, x67)
   291  		x70, x71 := bits.Add64(x46, x61, x69)
   292  		_, x72 := bits.Mul64(x62, 0xccd1c8aaee00bc4f)
   293  		x74, b74 := bits.Sub64(0, x72<<32, 0)
   294  		x75 := x72 - (x72 >> 32) - b74
   295  		x76, b76 := bits.Sub64(0, x72, 0)
   296  		x77 := x72 - b76
   297  		x79, x78 := bits.Mul64(x72, 0xbce6faada7179e84)
   298  		x81, x80 := bits.Mul64(x72, 0xf3b9cac2fc632551)
   299  		x82, x83 := bits.Add64(x81, x78, 0)
   300  		x84, x85 := bits.Add64(x79, x76, x83)
   301  		x86, x87 := bits.Add64(x77, x74, x85)
   302  		x88 := x87 + x75
   303  		_, x90 := bits.Add64(x62, x80, 0)
   304  		x91, x92 := bits.Add64(x64, x82, x90)
   305  		x93, x94 := bits.Add64(x66, x84, x92)
   306  		x95, x96 := bits.Add64(x68, x86, x94)
   307  		x97, x98 := bits.Add64(x70, x88, x96)
   308  		x99 := x98 + x71
   309  		x101, x100 := bits.Mul64(x2, x3)
   310  		x103, x102 := bits.Mul64(x2, x2)
   311  		x105, x104 := bits.Mul64(x2, x1)
   312  		x107, x106 := bits.Mul64(x2, x4)
   313  		x108, x109 := bits.Add64(x107, x104, 0)
   314  		x110, x111 := bits.Add64(x105, x102, x109)
   315  		x112, x113 := bits.Add64(x103, x100, x111)
   316  		x114 := x113 + x101
   317  		x115, x116 := bits.Add64(x91, x106, 0)
   318  		x117, x118 := bits.Add64(x93, x108, x116)
   319  		x119, x120 := bits.Add64(x95, x110, x118)
   320  		x121, x122 := bits.Add64(x97, x112, x120)
   321  		x123, x124 := bits.Add64(x99, x114, x122)
   322  		_, x125 := bits.Mul64(x115, 0xccd1c8aaee00bc4f)
   323  		x127, b127 := bits.Sub64(0, x125<<32, 0)
   324  		x128 := x125 - (x125 >> 32) - b127
   325  		x129, b129 := bits.Sub64(0, x125, 0)
   326  		x130 := x125 - b129
   327  		x132, x131 := bits.Mul64(x125, 0xbce6faada7179e84)
   328  		x134, x133 := bits.Mul64(x125, 0xf3b9cac2fc632551)
   329  		x135, x136 := bits.Add64(x134, x131, 0)
   330  		x137, x138 := bits.Add64(x132, x129, x136)
   331  		x139, x140 := bits.Add64(x130, x127, x138)
   332  		x141 := x140 + x128
   333  		_, x143 := bits.Add64(x115, x133, 0)
   334  		x144, x145 := bits.Add64(x117, x135, x143)
   335  		x146, x147 := bits.Add64(x119, x137, x145)
   336  		x148, x149 := bits.Add64(x121, x139, x147)
   337  		x150, x151 := bits.Add64(x123, x141, x149)
   338  		x152 := x151 + x124
   339  		x154, x153 := bits.Mul64(x3, x3)
   340  		x156, x155 := bits.Mul64(x3, x2)
   341  		x158, x157 := bits.Mul64(x3, x1)
   342  		x160, x159 := bits.Mul64(x3, x4)
   343  		x161, x162 := bits.Add64(x160, x157, 0)
   344  		x163, x164 := bits.Add64(x158, x155, x162)
   345  		x165, x166 := bits.Add64(x156, x153, x164)
   346  		x167 := x166 + x154
   347  		x168, x169 := bits.Add64(x144, x159, 0)
   348  		x170, x171 := bits.Add64(x146, x161, x169)
   349  		x172, x173 := bits.Add64(x148, x163, x171)
   350  		x174, x175 := bits.Add64(x150, x165, x173)
   351  		x176, x177 := bits.Add64(x152, x167, x175)
   352  		_, x178 := bits.Mul64(x168, 0xccd1c8aaee00bc4f)
   353  		x180, b180 := bits.Sub64(0, x178<<32, 0)
   354  		x181 := x178 - (x178 >> 32) - b180
   355  		x182, b182 := bits.Sub64(0, x178, 0)
   356  		x183 := x178 - b182
   357  		x185, x184 := bits.Mul64(x178, 0xbce6faada7179e84)
   358  		x187, x186 := bits.Mul64(x178, 0xf3b9cac2fc632551)
   359  		x188, x189 := bits.Add64(x187, x184, 0)
   360  		x190, x191 := bits.Add64(x185, x182, x189)
   361  		x192, x193 := bits.Add64(x183, x180, x191)
   362  		x194 := x193 + x181
   363  		_, x196 := bits.Add64(x168, x186, 0)
   364  		x197, x198 := bits.Add64(x170, x188, x196)
   365  		x199, x200 := bits.Add64(x172, x190, x198)
   366  		x201, x202 := bits.Add64(x174, x192, x200)
   367  		x203, x204 := bits.Add64(x176, x194, x202)
   368  		x205 := x204 + x177
   369  		x206, x207 := bits.Sub64(x197, 0xf3b9cac2fc632551, 0)
   370  		x208, x209 := bits.Sub64(x199, 0xbce6faada7179e84, x207)
   371  		x210, x211 := bits.Sub64(x201, 0xffffffffffffffff, x209)
   372  		x212, x213 := bits.Sub64(x203, 0xffffffff00000000, x211)
   373  		_, x215 := bits.Sub64(x205, 0, x213)
   374  		mask, _ := bits.Sub64(0, 0, x215)
   375  		x4 = x206&^mask | x197&mask
   376  		x1 = x208&^mask | x199&mask
   377  		x2 = x210&^mask | x201&mask
   378  		x3 = x212&^mask | x203&mask
   379  	}
   380  	out1[0] = x4
   381  	out1[1] = x1
   382  	out1[2] = x2
   383  	out1[3] = x3
   384  }
   385  
   386  // p256OrdFromMontgomery translates a field element out of the Montgomery domain.
   387  func p256OrdFromMontgomery(out1 *p256OrdElement, arg1 *p256OrdMontElement) {
   388  	x1 := arg1[0]
   389  	_, x2 := bits.Mul64(x1, 0xccd1c8aaee00bc4f)
   390  	x5, x4 := bits.Mul64(x2, 0xffffffff00000000)
   391  	x7, x6 := bits.Mul64(x2, 0xffffffffffffffff)
   392  	x9, x8 := bits.Mul64(x2, 0xbce6faada7179e84)
   393  	x11, x10 := bits.Mul64(x2, 0xf3b9cac2fc632551)
   394  	x12, x13 := bits.Add64(x11, x8, 0)
   395  	x14, x15 := bits.Add64(x9, x6, x13)
   396  	x16, x17 := bits.Add64(x7, x4, x15)
   397  	_, x19 := bits.Add64(x1, x10, 0)
   398  	x20, x21 := bits.Add64(0, x12, x19)
   399  	x22, x23 := bits.Add64(0, x14, x21)
   400  	x24, x25 := bits.Add64(0, x16, x23)
   401  	x26, x27 := bits.Add64(x20, arg1[1], 0)
   402  	x28, x29 := bits.Add64(x22, 0, x27)
   403  	x30, x31 := bits.Add64(x24, 0, x29)
   404  	_, x32 := bits.Mul64(x26, 0xccd1c8aaee00bc4f)
   405  	x35, x34 := bits.Mul64(x32, 0xffffffff00000000)
   406  	x37, x36 := bits.Mul64(x32, 0xffffffffffffffff)
   407  	x39, x38 := bits.Mul64(x32, 0xbce6faada7179e84)
   408  	x41, x40 := bits.Mul64(x32, 0xf3b9cac2fc632551)
   409  	x42, x43 := bits.Add64(x41, x38, 0)
   410  	x44, x45 := bits.Add64(x39, x36, x43)
   411  	x46, x47 := bits.Add64(x37, x34, x45)
   412  	_, x49 := bits.Add64(x26, x40, 0)
   413  	x50, x51 := bits.Add64(x28, x42, x49)
   414  	x52, x53 := bits.Add64(x30, x44, x51)
   415  	x54, x55 := bits.Add64(x31+(x25+(x17+x5)), x46, x53)
   416  	x56, x57 := bits.Add64(x50, arg1[2], 0)
   417  	x58, x59 := bits.Add64(x52, 0, x57)
   418  	x60, x61 := bits.Add64(x54, 0, x59)
   419  	_, x62 := bits.Mul64(x56, 0xccd1c8aaee00bc4f)
   420  	x65, x64 := bits.Mul64(x62, 0xffffffff00000000)
   421  	x67, x66 := bits.Mul64(x62, 0xffffffffffffffff)
   422  	x69, x68 := bits.Mul64(x62, 0xbce6faada7179e84)
   423  	x71, x70 := bits.Mul64(x62, 0xf3b9cac2fc632551)
   424  	x72, x73 := bits.Add64(x71, x68, 0)
   425  	x74, x75 := bits.Add64(x69, x66, x73)
   426  	x76, x77 := bits.Add64(x67, x64, x75)
   427  	_, x79 := bits.Add64(x56, x70, 0)
   428  	x80, x81 := bits.Add64(x58, x72, x79)
   429  	x82, x83 := bits.Add64(x60, x74, x81)
   430  	x84, x85 := bits.Add64(x61+(x55+(x47+x35)), x76, x83)
   431  	x86, x87 := bits.Add64(x80, arg1[3], 0)
   432  	x88, x89 := bits.Add64(x82, 0, x87)
   433  	x90, x91 := bits.Add64(x84, 0, x89)
   434  	_, x92 := bits.Mul64(x86, 0xccd1c8aaee00bc4f)
   435  	x95, x94 := bits.Mul64(x92, 0xffffffff00000000)
   436  	x97, x96 := bits.Mul64(x92, 0xffffffffffffffff)
   437  	x99, x98 := bits.Mul64(x92, 0xbce6faada7179e84)
   438  	x101, x100 := bits.Mul64(x92, 0xf3b9cac2fc632551)
   439  	x102, x103 := bits.Add64(x101, x98, 0)
   440  	x104, x105 := bits.Add64(x99, x96, x103)
   441  	x106, x107 := bits.Add64(x97, x94, x105)
   442  	_, x109 := bits.Add64(x86, x100, 0)
   443  	x110, x111 := bits.Add64(x88, x102, x109)
   444  	x112, x113 := bits.Add64(x90, x104, x111)
   445  	x114, x115 := bits.Add64(x91+(x85+(x77+x65)), x106, x113)
   446  	x116 := x115 + (x107 + x95)
   447  	x117, x118 := bits.Sub64(x110, 0xf3b9cac2fc632551, 0)
   448  	x119, x120 := bits.Sub64(x112, 0xbce6faada7179e84, x118)
   449  	x121, x122 := bits.Sub64(x114, 0xffffffffffffffff, x120)
   450  	x123, x124 := bits.Sub64(x116, 0xffffffff00000000, x122)
   451  	mask, _ := bits.Sub64(0, 0, x124)
   452  	out1[0] = x117&^mask | x110&mask
   453  	out1[1] = x119&^mask | x112&mask
   454  	out1[2] = x121&^mask | x114&mask
   455  	out1[3] = x123&^mask | x116&mask
   456  }
   457  
   458  // p256OrdToMontgomery translates a field element into the Montgomery domain.
   459  func p256OrdToMontgomery(out1 *p256OrdMontElement, arg1 *p256OrdElement) {
   460  	x1 := arg1[1]
   461  	x2 := arg1[2]
   462  	x3 := arg1[3]
   463  	x4 := arg1[0]
   464  	x6, x5 := bits.Mul64(x4, 0x66e12d94f3d95620)
   465  	x8, x7 := bits.Mul64(x4, 0x2845b2392b6bec59)
   466  	x10, x9 := bits.Mul64(x4, 0x4699799c49bd6fa6)
   467  	x12, x11 := bits.Mul64(x4, 0x83244c95be79eea2)
   468  	x13, x14 := bits.Add64(x12, x9, 0)
   469  	x15, x16 := bits.Add64(x10, x7, x14)
   470  	x17, x18 := bits.Add64(x8, x5, x16)
   471  	_, x19 := bits.Mul64(x11, 0xccd1c8aaee00bc4f)
   472  	x22, x21 := bits.Mul64(x19, 0xffffffff00000000)
   473  	x24, x23 := bits.Mul64(x19, 0xffffffffffffffff)
   474  	x26, x25 := bits.Mul64(x19, 0xbce6faada7179e84)
   475  	x28, x27 := bits.Mul64(x19, 0xf3b9cac2fc632551)
   476  	x29, x30 := bits.Add64(x28, x25, 0)
   477  	x31, x32 := bits.Add64(x26, x23, x30)
   478  	x33, x34 := bits.Add64(x24, x21, x32)
   479  	_, x36 := bits.Add64(x11, x27, 0)
   480  	x37, x38 := bits.Add64(x13, x29, x36)
   481  	x39, x40 := bits.Add64(x15, x31, x38)
   482  	x41, x42 := bits.Add64(x17, x33, x40)
   483  	x43, x44 := bits.Add64(x18+x6, x34+x22, x42)
   484  	x46, x45 := bits.Mul64(x1, 0x66e12d94f3d95620)
   485  	x48, x47 := bits.Mul64(x1, 0x2845b2392b6bec59)
   486  	x50, x49 := bits.Mul64(x1, 0x4699799c49bd6fa6)
   487  	x52, x51 := bits.Mul64(x1, 0x83244c95be79eea2)
   488  	x53, x54 := bits.Add64(x52, x49, 0)
   489  	x55, x56 := bits.Add64(x50, x47, x54)
   490  	x57, x58 := bits.Add64(x48, x45, x56)
   491  	x59, x60 := bits.Add64(x37, x51, 0)
   492  	x61, x62 := bits.Add64(x39, x53, x60)
   493  	x63, x64 := bits.Add64(x41, x55, x62)
   494  	x65, x66 := bits.Add64(x43, x57, x64)
   495  	_, x67 := bits.Mul64(x59, 0xccd1c8aaee00bc4f)
   496  	x70, x69 := bits.Mul64(x67, 0xffffffff00000000)
   497  	x72, x71 := bits.Mul64(x67, 0xffffffffffffffff)
   498  	x74, x73 := bits.Mul64(x67, 0xbce6faada7179e84)
   499  	x76, x75 := bits.Mul64(x67, 0xf3b9cac2fc632551)
   500  	x77, x78 := bits.Add64(x76, x73, 0)
   501  	x79, x80 := bits.Add64(x74, x71, x78)
   502  	x81, x82 := bits.Add64(x72, x69, x80)
   503  	_, x84 := bits.Add64(x59, x75, 0)
   504  	x85, x86 := bits.Add64(x61, x77, x84)
   505  	x87, x88 := bits.Add64(x63, x79, x86)
   506  	x89, x90 := bits.Add64(x65, x81, x88)
   507  	x91, x92 := bits.Add64(x66+x44+(x58+x46), x82+x70, x90)
   508  	x94, x93 := bits.Mul64(x2, 0x66e12d94f3d95620)
   509  	x96, x95 := bits.Mul64(x2, 0x2845b2392b6bec59)
   510  	x98, x97 := bits.Mul64(x2, 0x4699799c49bd6fa6)
   511  	x100, x99 := bits.Mul64(x2, 0x83244c95be79eea2)
   512  	x101, x102 := bits.Add64(x100, x97, 0)
   513  	x103, x104 := bits.Add64(x98, x95, x102)
   514  	x105, x106 := bits.Add64(x96, x93, x104)
   515  	x107, x108 := bits.Add64(x85, x99, 0)
   516  	x109, x110 := bits.Add64(x87, x101, x108)
   517  	x111, x112 := bits.Add64(x89, x103, x110)
   518  	x113, x114 := bits.Add64(x91, x105, x112)
   519  	_, x115 := bits.Mul64(x107, 0xccd1c8aaee00bc4f)
   520  	x118, x117 := bits.Mul64(x115, 0xffffffff00000000)
   521  	x120, x119 := bits.Mul64(x115, 0xffffffffffffffff)
   522  	x122, x121 := bits.Mul64(x115, 0xbce6faada7179e84)
   523  	x124, x123 := bits.Mul64(x115, 0xf3b9cac2fc632551)
   524  	x125, x126 := bits.Add64(x124, x121, 0)
   525  	x127, x128 := bits.Add64(x122, x119, x126)
   526  	x129, x130 := bits.Add64(x120, x117, x128)
   527  	_, x132 := bits.Add64(x107, x123, 0)
   528  	x133, x134 := bits.Add64(x109, x125, x132)
   529  	x135, x136 := bits.Add64(x111, x127, x134)
   530  	x137, x138 := bits.Add64(x113, x129, x136)
   531  	x139, x140 := bits.Add64(x114+x92+(x106+x94), x130+x118, x138)
   532  	x142, x141 := bits.Mul64(x3, 0x66e12d94f3d95620)
   533  	x144, x143 := bits.Mul64(x3, 0x2845b2392b6bec59)
   534  	x146, x145 := bits.Mul64(x3, 0x4699799c49bd6fa6)
   535  	x148, x147 := bits.Mul64(x3, 0x83244c95be79eea2)
   536  	x149, x150 := bits.Add64(x148, x145, 0)
   537  	x151, x152 := bits.Add64(x146, x143, x150)
   538  	x153, x154 := bits.Add64(x144, x141, x152)
   539  	x155, x156 := bits.Add64(x133, x147, 0)
   540  	x157, x158 := bits.Add64(x135, x149, x156)
   541  	x159, x160 := bits.Add64(x137, x151, x158)
   542  	x161, x162 := bits.Add64(x139, x153, x160)
   543  	_, x163 := bits.Mul64(x155, 0xccd1c8aaee00bc4f)
   544  	x166, x165 := bits.Mul64(x163, 0xffffffff00000000)
   545  	x168, x167 := bits.Mul64(x163, 0xffffffffffffffff)
   546  	x170, x169 := bits.Mul64(x163, 0xbce6faada7179e84)
   547  	x172, x171 := bits.Mul64(x163, 0xf3b9cac2fc632551)
   548  	x173, x174 := bits.Add64(x172, x169, 0)
   549  	x175, x176 := bits.Add64(x170, x167, x174)
   550  	x177, x178 := bits.Add64(x168, x165, x176)
   551  	_, x180 := bits.Add64(x155, x171, 0)
   552  	x181, x182 := bits.Add64(x157, x173, x180)
   553  	x183, x184 := bits.Add64(x159, x175, x182)
   554  	x185, x186 := bits.Add64(x161, x177, x184)
   555  	x187, x188 := bits.Add64(x162+x140+(x154+x142), x178+x166, x186)
   556  	x189, x190 := bits.Sub64(x181, 0xf3b9cac2fc632551, 0)
   557  	x191, x192 := bits.Sub64(x183, 0xbce6faada7179e84, x190)
   558  	x193, x194 := bits.Sub64(x185, 0xffffffffffffffff, x192)
   559  	x195, x196 := bits.Sub64(x187, 0xffffffff00000000, x194)
   560  	_, x198 := bits.Sub64(x188, 0, x196)
   561  	mask, _ := bits.Sub64(0, 0, x198)
   562  	out1[0] = x189&^mask | x181&mask
   563  	out1[1] = x191&^mask | x183&mask
   564  	out1[2] = x193&^mask | x185&mask
   565  	out1[3] = x195&^mask | x187&mask
   566  }
   567  

View as plain text