p256.go raw
1 /*
2 Copyright Suzhou Tongji Fintech Research Institute 2017 All Rights Reserved.
3 Licensed under the Apache License, Version 2.0 (the "License");
4 you may not use this file except in compliance with the License.
5 You may obtain a copy of the License at
6
7 http://www.apache.org/licenses/LICENSE-2.0
8
9 Unless required by applicable law or agreed to in writing, software
10 distributed under the License is distributed on an "AS IS" BASIS,
11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 See the License for the specific language governing permissions and
13 limitations under the License.
14 */
15
16 package sm2
17
18 import (
19 "crypto/elliptic"
20 "math/big"
21 "sync"
22 )
23
24 /** 学习标准库p256的优化方法实现sm2的快速版本
25 * 标准库的p256的代码实现有些晦涩难懂，当然sm2的同样如此，有兴趣的大家可以研究研究，最后神兽压阵。。。
26 *
27 * ━━━━━━animal━━━━━━
28 * ┏┓ ┏┓
29 * ┏┛┻━━━┛┻┓
30 * ┃ ┃
31 * ┃ ━ ┃
32 * ┃ ┳┛ ┗┳ ┃
33 * ┃ ┃
34 * ┃ ┻ ┃
35 * ┃ ┃
36 * ┗━┓ ┏━┛
37 * ┃ ┃
38 * ┃ ┃
39 * ┃ ┗━━━┓
40 * ┃ ┣┓
41 * ┃ ┏┛
42 * ┗┓┓┏━┳┓┏┛
43 * ┃┫┫ ┃┫┫
44 * ┗┻┛ ┗┻┛
45 *
46 * ━━━━━Kawaii ━━━━━━
47 */
48
49 type sm2P256Curve struct {
50 RInverse *big.Int
51 *elliptic.CurveParams
52 a, b, gx, gy sm2P256FieldElement
53 }
54
55 var initonce sync.Once
56 var sm2P256 sm2P256Curve
57
58 type sm2P256FieldElement [9]uint32
59 type sm2P256LargeFieldElement [17]uint64
60
61 const (
62 bottom28Bits = 0xFFFFFFF
63 bottom29Bits = 0x1FFFFFFF
64 )
65
66 func initP256Sm2() {
67 sm2P256.CurveParams = &elliptic.CurveParams{Name: "SM2-P-256"} // sm2
68 A, _ := new(big.Int).SetString("FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC", 16)
69 //SM2椭 椭 圆 曲 线 公 钥 密 码 算 法 推 荐 曲 线 参 数
70 sm2P256.P, _ = new(big.Int).SetString("FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF", 16)
71 sm2P256.N, _ = new(big.Int).SetString("FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123", 16)
72 sm2P256.B, _ = new(big.Int).SetString("28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93", 16)
73 sm2P256.Gx, _ = new(big.Int).SetString("32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7", 16)
74 sm2P256.Gy, _ = new(big.Int).SetString("BC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0", 16)
75 sm2P256.RInverse, _ = new(big.Int).SetString("7ffffffd80000002fffffffe000000017ffffffe800000037ffffffc80000002", 16)
76 sm2P256.BitSize = 256
77 sm2P256FromBig(&sm2P256.a, A)
78 sm2P256FromBig(&sm2P256.gx, sm2P256.Gx)
79 sm2P256FromBig(&sm2P256.gy, sm2P256.Gy)
80 sm2P256FromBig(&sm2P256.b, sm2P256.B)
81 }
82
83 func P256Sm2() elliptic.Curve {
84 initonce.Do(initP256Sm2)
85 return sm2P256
86 }
87
88 func (curve sm2P256Curve) Params() *elliptic.CurveParams {
89 return sm2P256.CurveParams
90 }
91
92 // y^2 = x^3 + ax + b
93 func (curve sm2P256Curve) IsOnCurve(X, Y *big.Int) bool {
94 var a, x, y, y2, x3 sm2P256FieldElement
95
96 sm2P256FromBig(&x, X)
97 sm2P256FromBig(&y, Y)
98
99 sm2P256Square(&x3, &x) // x3 = x ^ 2
100 sm2P256Mul(&x3, &x3, &x) // x3 = x ^ 2 * x
101 sm2P256Mul(&a, &curve.a, &x) // a = a * x
102 sm2P256Add(&x3, &x3, &a)
103 sm2P256Add(&x3, &x3, &curve.b)
104
105 sm2P256Square(&y2, &y) // y2 = y ^ 2
106 return sm2P256ToBig(&x3).Cmp(sm2P256ToBig(&y2)) == 0
107 }
108
109 func zForAffine(x, y *big.Int) *big.Int {
110 z := new(big.Int)
111 if x.Sign() != 0 || y.Sign() != 0 {
112 z.SetInt64(1)
113 }
114 return z
115 }
116
117 func (curve sm2P256Curve) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
118 var X1, Y1, Z1, X2, Y2, Z2, X3, Y3, Z3 sm2P256FieldElement
119
120 z1 := zForAffine(x1, y1)
121 z2 := zForAffine(x2, y2)
122 sm2P256FromBig(&X1, x1)
123 sm2P256FromBig(&Y1, y1)
124 sm2P256FromBig(&Z1, z1)
125 sm2P256FromBig(&X2, x2)
126 sm2P256FromBig(&Y2, y2)
127 sm2P256FromBig(&Z2, z2)
128 sm2P256PointAdd(&X1, &Y1, &Z1, &X2, &Y2, &Z2, &X3, &Y3, &Z3)
129 return sm2P256ToAffine(&X3, &Y3, &Z3)
130 }
131
132 func (curve sm2P256Curve) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
133 var X1, Y1, Z1 sm2P256FieldElement
134
135 z1 := zForAffine(x1, y1)
136 sm2P256FromBig(&X1, x1)
137 sm2P256FromBig(&Y1, y1)
138 sm2P256FromBig(&Z1, z1)
139 sm2P256PointDouble(&X1, &Y1, &Z1, &X1, &Y1, &Z1)
140 return sm2P256ToAffine(&X1, &Y1, &Z1)
141 }
142
143 func (curve sm2P256Curve) ScalarMult(x1, y1 *big.Int, k []byte) (*big.Int, *big.Int) {
144 var X, Y, Z, X1, Y1 sm2P256FieldElement
145 sm2P256FromBig(&X1, x1)
146 sm2P256FromBig(&Y1, y1)
147 scalar := sm2GenrateWNaf(k)
148 scalarReversed := WNafReversed(scalar)
149 sm2P256ScalarMult(&X, &Y, &Z, &X1, &Y1, scalarReversed)
150 return sm2P256ToAffine(&X, &Y, &Z)
151 }
152
153 func (curve sm2P256Curve) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {
154 var scalarReversed [32]byte
155 var X, Y, Z sm2P256FieldElement
156
157 sm2P256GetScalar(&scalarReversed, k)
158 sm2P256ScalarBaseMult(&X, &Y, &Z, &scalarReversed)
159 return sm2P256ToAffine(&X, &Y, &Z)
160 }
161
162 var sm2P256Precomputed = [9 * 2 * 15 * 2]uint32{
163 0x830053d, 0x328990f, 0x6c04fe1, 0xc0f72e5, 0x1e19f3c, 0x666b093, 0x175a87b, 0xec38276, 0x222cf4b,
164 0x185a1bba, 0x354e593, 0x1295fac1, 0xf2bc469, 0x47c60fa, 0xc19b8a9, 0xf63533e, 0x903ae6b, 0xc79acba,
165 0x15b061a4, 0x33e020b, 0xdffb34b, 0xfcf2c8, 0x16582e08, 0x262f203, 0xfb34381, 0xa55452, 0x604f0ff,
166 0x41f1f90, 0xd64ced2, 0xee377bf, 0x75f05f0, 0x189467ae, 0xe2244e, 0x1e7700e8, 0x3fbc464, 0x9612d2e,
167 0x1341b3b8, 0xee84e23, 0x1edfa5b4, 0x14e6030, 0x19e87be9, 0x92f533c, 0x1665d96c, 0x226653e, 0xa238d3e,
168 0xf5c62c, 0x95bb7a, 0x1f0e5a41, 0x28789c3, 0x1f251d23, 0x8726609, 0xe918910, 0x8096848, 0xf63d028,
169 0x152296a1, 0x9f561a8, 0x14d376fb, 0x898788a, 0x61a95fb, 0xa59466d, 0x159a003d, 0x1ad1698, 0x93cca08,
170 0x1b314662, 0x706e006, 0x11ce1e30, 0x97b710, 0x172fbc0d, 0x8f50158, 0x11c7ffe7, 0xd182cce, 0xc6ad9e8,
171 0x12ea31b2, 0xc4e4f38, 0x175b0d96, 0xec06337, 0x75a9c12, 0xb001fdf, 0x93e82f5, 0x34607de, 0xb8035ed,
172 0x17f97924, 0x75cf9e6, 0xdceaedd, 0x2529924, 0x1a10c5ff, 0xb1a54dc, 0x19464d8, 0x2d1997, 0xde6a110,
173 0x1e276ee5, 0x95c510c, 0x1aca7c7a, 0xfe48aca, 0x121ad4d9, 0xe4132c6, 0x8239b9d, 0x40ea9cd, 0x816c7b,
174 0x632d7a4, 0xa679813, 0x5911fcf, 0x82b0f7c, 0x57b0ad5, 0xbef65, 0xd541365, 0x7f9921f, 0xc62e7a,
175 0x3f4b32d, 0x58e50e1, 0x6427aed, 0xdcdda67, 0xe8c2d3e, 0x6aa54a4, 0x18df4c35, 0x49a6a8e, 0x3cd3d0c,
176 0xd7adf2, 0xcbca97, 0x1bda5f2d, 0x3258579, 0x606b1e6, 0x6fc1b5b, 0x1ac27317, 0x503ca16, 0xa677435,
177 0x57bc73, 0x3992a42, 0xbab987b, 0xfab25eb, 0x128912a4, 0x90a1dc4, 0x1402d591, 0x9ffbcfc, 0xaa48856,
178 0x7a7c2dc, 0xcefd08a, 0x1b29bda6, 0xa785641, 0x16462d8c, 0x76241b7, 0x79b6c3b, 0x204ae18, 0xf41212b,
179 0x1f567a4d, 0xd6ce6db, 0xedf1784, 0x111df34, 0x85d7955, 0x55fc189, 0x1b7ae265, 0xf9281ac, 0xded7740,
180 0xf19468b, 0x83763bb, 0x8ff7234, 0x3da7df8, 0x9590ac3, 0xdc96f2a, 0x16e44896, 0x7931009, 0x99d5acc,
181 0x10f7b842, 0xaef5e84, 0xc0310d7, 0xdebac2c, 0x2a7b137, 0x4342344, 0x19633649, 0x3a10624, 0x4b4cb56,
182 0x1d809c59, 0xac007f, 0x1f0f4bcd, 0xa1ab06e, 0xc5042cf, 0x82c0c77, 0x76c7563, 0x22c30f3, 0x3bf1568,
183 0x7a895be, 0xfcca554, 0x12e90e4c, 0x7b4ab5f, 0x13aeb76b, 0x5887e2c, 0x1d7fe1e3, 0x908c8e3, 0x95800ee,
184 0xb36bd54, 0xf08905d, 0x4e73ae8, 0xf5a7e48, 0xa67cb0, 0x50e1067, 0x1b944a0a, 0xf29c83a, 0xb23cfb9,
185 0xbe1db1, 0x54de6e8, 0xd4707f2, 0x8ebcc2d, 0x2c77056, 0x1568ce4, 0x15fcc849, 0x4069712, 0xe2ed85f,
186 0x2c5ff09, 0x42a6929, 0x628e7ea, 0xbd5b355, 0xaf0bd79, 0xaa03699, 0xdb99816, 0x4379cef, 0x81d57b,
187 0x11237f01, 0xe2a820b, 0xfd53b95, 0x6beb5ee, 0x1aeb790c, 0xe470d53, 0x2c2cfee, 0x1c1d8d8, 0xa520fc4,
188 0x1518e034, 0xa584dd4, 0x29e572b, 0xd4594fc, 0x141a8f6f, 0x8dfccf3, 0x5d20ba3, 0x2eb60c3, 0x9f16eb0,
189 0x11cec356, 0xf039f84, 0x1b0990c1, 0xc91e526, 0x10b65bae, 0xf0616e8, 0x173fa3ff, 0xec8ccf9, 0xbe32790,
190 0x11da3e79, 0xe2f35c7, 0x908875c, 0xdacf7bd, 0x538c165, 0x8d1487f, 0x7c31aed, 0x21af228, 0x7e1689d,
191 0xdfc23ca, 0x24f15dc, 0x25ef3c4, 0x35248cd, 0x99a0f43, 0xa4b6ecc, 0xd066b3, 0x2481152, 0x37a7688,
192 0x15a444b6, 0xb62300c, 0x4b841b, 0xa655e79, 0xd53226d, 0xbeb348a, 0x127f3c2, 0xb989247, 0x71a277d,
193 0x19e9dfcb, 0xb8f92d0, 0xe2d226c, 0x390a8b0, 0x183cc462, 0x7bd8167, 0x1f32a552, 0x5e02db4, 0xa146ee9,
194 0x1a003957, 0x1c95f61, 0x1eeec155, 0x26f811f, 0xf9596ba, 0x3082bfb, 0x96df083, 0x3e3a289, 0x7e2d8be,
195 0x157a63e0, 0x99b8941, 0x1da7d345, 0xcc6cd0, 0x10beed9a, 0x48e83c0, 0x13aa2e25, 0x7cad710, 0x4029988,
196 0x13dfa9dd, 0xb94f884, 0x1f4adfef, 0xb88543, 0x16f5f8dc, 0xa6a67f4, 0x14e274e2, 0x5e56cf4, 0x2f24ef,
197 0x1e9ef967, 0xfe09bad, 0xfe079b3, 0xcc0ae9e, 0xb3edf6d, 0x3e961bc, 0x130d7831, 0x31043d6, 0xba986f9,
198 0x1d28055, 0x65240ca, 0x4971fa3, 0x81b17f8, 0x11ec34a5, 0x8366ddc, 0x1471809, 0xfa5f1c6, 0xc911e15,
199 0x8849491, 0xcf4c2e2, 0x14471b91, 0x39f75be, 0x445c21e, 0xf1585e9, 0x72cc11f, 0x4c79f0c, 0xe5522e1,
200 0x1874c1ee, 0x4444211, 0x7914884, 0x3d1b133, 0x25ba3c, 0x4194f65, 0x1c0457ef, 0xac4899d, 0xe1fa66c,
201 0x130a7918, 0x9b8d312, 0x4b1c5c8, 0x61ccac3, 0x18c8aa6f, 0xe93cb0a, 0xdccb12c, 0xde10825, 0x969737d,
202 0xf58c0c3, 0x7cee6a9, 0xc2c329a, 0xc7f9ed9, 0x107b3981, 0x696a40e, 0x152847ff, 0x4d88754, 0xb141f47,
203 0x5a16ffe, 0x3a7870a, 0x18667659, 0x3b72b03, 0xb1c9435, 0x9285394, 0xa00005a, 0x37506c, 0x2edc0bb,
204 0x19afe392, 0xeb39cac, 0x177ef286, 0xdf87197, 0x19f844ed, 0x31fe8, 0x15f9bfd, 0x80dbec, 0x342e96e,
205 0x497aced, 0xe88e909, 0x1f5fa9ba, 0x530a6ee, 0x1ef4e3f1, 0x69ffd12, 0x583006d, 0x2ecc9b1, 0x362db70,
206 0x18c7bdc5, 0xf4bb3c5, 0x1c90b957, 0xf067c09, 0x9768f2b, 0xf73566a, 0x1939a900, 0x198c38a, 0x202a2a1,
207 0x4bbf5a6, 0x4e265bc, 0x1f44b6e7, 0x185ca49, 0xa39e81b, 0x24aff5b, 0x4acc9c2, 0x638bdd3, 0xb65b2a8,
208 0x6def8be, 0xb94537a, 0x10b81dee, 0xe00ec55, 0x2f2cdf7, 0xc20622d, 0x2d20f36, 0xe03c8c9, 0x898ea76,
209 0x8e3921b, 0x8905bff, 0x1e94b6c8, 0xee7ad86, 0x154797f2, 0xa620863, 0x3fbd0d9, 0x1f3caab, 0x30c24bd,
210 0x19d3892f, 0x59c17a2, 0x1ab4b0ae, 0xf8714ee, 0x90c4098, 0xa9c800d, 0x1910236b, 0xea808d3, 0x9ae2f31,
211 0x1a15ad64, 0xa48c8d1, 0x184635a4, 0xb725ef1, 0x11921dcc, 0x3f866df, 0x16c27568, 0xbdf580a, 0xb08f55c,
212 0x186ee1c, 0xb1627fa, 0x34e82f6, 0x933837e, 0xf311be5, 0xfedb03b, 0x167f72cd, 0xa5469c0, 0x9c82531,
213 0xb92a24b, 0x14fdc8b, 0x141980d1, 0xbdc3a49, 0x7e02bb1, 0xaf4e6dd, 0x106d99e1, 0xd4616fc, 0x93c2717,
214 0x1c0a0507, 0xc6d5fed, 0x9a03d8b, 0xa1d22b0, 0x127853e3, 0xc4ac6b8, 0x1a048cf7, 0x9afb72c, 0x65d485d,
215 0x72d5998, 0xe9fa744, 0xe49e82c, 0x253cf80, 0x5f777ce, 0xa3799a5, 0x17270cbb, 0xc1d1ef0, 0xdf74977,
216 0x114cb859, 0xfa8e037, 0xb8f3fe5, 0xc734cc6, 0x70d3d61, 0xeadac62, 0x12093dd0, 0x9add67d, 0x87200d6,
217 0x175bcbb, 0xb29b49f, 0x1806b79c, 0x12fb61f, 0x170b3a10, 0x3aaf1cf, 0xa224085, 0x79d26af, 0x97759e2,
218 0x92e19f1, 0xb32714d, 0x1f00d9f1, 0xc728619, 0x9e6f627, 0xe745e24, 0x18ea4ace, 0xfc60a41, 0x125f5b2,
219 0xc3cf512, 0x39ed486, 0xf4d15fa, 0xf9167fd, 0x1c1f5dd5, 0xc21a53e, 0x1897930, 0x957a112, 0x21059a0,
220 0x1f9e3ddc, 0xa4dfced, 0x8427f6f, 0x726fbe7, 0x1ea658f8, 0x2fdcd4c, 0x17e9b66f, 0xb2e7c2e, 0x39923bf,
221 0x1bae104, 0x3973ce5, 0xc6f264c, 0x3511b84, 0x124195d7, 0x11996bd, 0x20be23d, 0xdc437c4, 0x4b4f16b,
222 0x11902a0, 0x6c29cc9, 0x1d5ffbe6, 0xdb0b4c7, 0x10144c14, 0x2f2b719, 0x301189, 0x2343336, 0xa0bf2ac,
223 }
224
225 func sm2P256GetScalar(b *[32]byte, a []byte) {
226 var scalarBytes []byte
227
228 n := new(big.Int).SetBytes(a)
229 if n.Cmp(sm2P256.N) >= 0 {
230 n.Mod(n, sm2P256.N)
231 scalarBytes = n.Bytes()
232 } else {
233 scalarBytes = a
234 }
235 for i, v := range scalarBytes {
236 b[len(scalarBytes)-(1+i)] = v
237 }
238 }
239
240 func sm2P256PointAddMixed(xOut, yOut, zOut, x1, y1, z1, x2, y2 *sm2P256FieldElement) {
241 var z1z1, z1z1z1, s2, u2, h, i, j, r, rr, v, tmp sm2P256FieldElement
242
243 sm2P256Square(&z1z1, z1)
244 sm2P256Add(&tmp, z1, z1)
245
246 sm2P256Mul(&u2, x2, &z1z1)
247 sm2P256Mul(&z1z1z1, z1, &z1z1)
248 sm2P256Mul(&s2, y2, &z1z1z1)
249 sm2P256Sub(&h, &u2, x1)
250 sm2P256Add(&i, &h, &h)
251 sm2P256Square(&i, &i)
252 sm2P256Mul(&j, &h, &i)
253 sm2P256Sub(&r, &s2, y1)
254 sm2P256Add(&r, &r, &r)
255 sm2P256Mul(&v, x1, &i)
256
257 sm2P256Mul(zOut, &tmp, &h)
258 sm2P256Square(&rr, &r)
259 sm2P256Sub(xOut, &rr, &j)
260 sm2P256Sub(xOut, xOut, &v)
261 sm2P256Sub(xOut, xOut, &v)
262
263 sm2P256Sub(&tmp, &v, xOut)
264 sm2P256Mul(yOut, &tmp, &r)
265 sm2P256Mul(&tmp, y1, &j)
266 sm2P256Sub(yOut, yOut, &tmp)
267 sm2P256Sub(yOut, yOut, &tmp)
268 }
269
270 // sm2P256CopyConditional sets out=in if mask = 0xffffffff in constant time.
271 //
272 // On entry: mask is either 0 or 0xffffffff.
273 func sm2P256CopyConditional(out, in *sm2P256FieldElement, mask uint32) {
274 for i := 0; i < 9; i++ {
275 tmp := mask & (in[i] ^ out[i])
276 out[i] ^= tmp
277 }
278 }
279
280 // sm2P256SelectAffinePoint sets {out_x,out_y} to the index'th entry of table.
281 // On entry: index < 16, table[0] must be zero.
282 func sm2P256SelectAffinePoint(xOut, yOut *sm2P256FieldElement, table []uint32, index uint32) {
283 for i := range xOut {
284 xOut[i] = 0
285 }
286 for i := range yOut {
287 yOut[i] = 0
288 }
289
290 for i := uint32(1); i < 16; i++ {
291 mask := i ^ index
292 mask |= mask >> 2
293 mask |= mask >> 1
294 mask &= 1
295 mask--
296 for j := range xOut {
297 xOut[j] |= table[0] & mask
298 table = table[1:]
299 }
300 for j := range yOut {
301 yOut[j] |= table[0] & mask
302 table = table[1:]
303 }
304 }
305 }
306
307 // sm2P256SelectJacobianPoint sets {out_x,out_y,out_z} to the index'th entry of
308 // table.
309 // On entry: index < 16, table[0] must be zero.
310 func sm2P256SelectJacobianPoint(xOut, yOut, zOut *sm2P256FieldElement, table *[16][3]sm2P256FieldElement, index uint32) {
311 for i := range xOut {
312 xOut[i] = 0
313 }
314 for i := range yOut {
315 yOut[i] = 0
316 }
317 for i := range zOut {
318 zOut[i] = 0
319 }
320
321 // The implicit value at index 0 is all zero. We don't need to perform that
322 // iteration of the loop because we already set out_* to zero.
323 for i := uint32(1); i < 16; i++ {
324 mask := i ^ index
325 mask |= mask >> 2
326 mask |= mask >> 1
327 mask &= 1
328 mask--
329 for j := range xOut {
330 xOut[j] |= table[i][0][j] & mask
331 }
332 for j := range yOut {
333 yOut[j] |= table[i][1][j] & mask
334 }
335 for j := range zOut {
336 zOut[j] |= table[i][2][j] & mask
337 }
338 }
339 }
340
341 // sm2P256GetBit returns the bit'th bit of scalar.
342 func sm2P256GetBit(scalar *[32]uint8, bit uint) uint32 {
343 return uint32(((scalar[bit>>3]) >> (bit & 7)) & 1)
344 }
345
346 // sm2P256ScalarBaseMult sets {xOut,yOut,zOut} = scalar*G where scalar is a
347 // little-endian number. Note that the value of scalar must be less than the
348 // order of the group.
349 func sm2P256ScalarBaseMult(xOut, yOut, zOut *sm2P256FieldElement, scalar *[32]uint8) {
350 nIsInfinityMask := ^uint32(0)
351 var px, py, tx, ty, tz sm2P256FieldElement
352 var pIsNoninfiniteMask, mask, tableOffset uint32
353
354 for i := range xOut {
355 xOut[i] = 0
356 }
357 for i := range yOut {
358 yOut[i] = 0
359 }
360 for i := range zOut {
361 zOut[i] = 0
362 }
363
364 // The loop adds bits at positions 0, 64, 128 and 192, followed by
365 // positions 32,96,160 and 224 and does this 32 times.
366 for i := uint(0); i < 32; i++ {
367 if i != 0 {
368 sm2P256PointDouble(xOut, yOut, zOut, xOut, yOut, zOut)
369 }
370 tableOffset = 0
371 for j := uint(0); j <= 32; j += 32 {
372 bit0 := sm2P256GetBit(scalar, 31-i+j)
373 bit1 := sm2P256GetBit(scalar, 95-i+j)
374 bit2 := sm2P256GetBit(scalar, 159-i+j)
375 bit3 := sm2P256GetBit(scalar, 223-i+j)
376 index := bit0 | (bit1 << 1) | (bit2 << 2) | (bit3 << 3)
377
378 sm2P256SelectAffinePoint(&px, &py, sm2P256Precomputed[tableOffset:], index)
379 tableOffset += 30 * 9
380
381 // Since scalar is less than the order of the group, we know that
382 // {xOut,yOut,zOut} != {px,py,1}, unless both are zero, which we handle
383 // below.
384 sm2P256PointAddMixed(&tx, &ty, &tz, xOut, yOut, zOut, &px, &py)
385 // The result of pointAddMixed is incorrect if {xOut,yOut,zOut} is zero
386 // (a.k.a. the point at infinity). We handle that situation by
387 // copying the point from the table.
388 sm2P256CopyConditional(xOut, &px, nIsInfinityMask)
389 sm2P256CopyConditional(yOut, &py, nIsInfinityMask)
390 sm2P256CopyConditional(zOut, &sm2P256Factor[1], nIsInfinityMask)
391
392 // Equally, the result is also wrong if the point from the table is
393 // zero, which happens when the index is zero. We handle that by
394 // only copying from {tx,ty,tz} to {xOut,yOut,zOut} if index != 0.
395 pIsNoninfiniteMask = nonZeroToAllOnes(index)
396 mask = pIsNoninfiniteMask & ^nIsInfinityMask
397 sm2P256CopyConditional(xOut, &tx, mask)
398 sm2P256CopyConditional(yOut, &ty, mask)
399 sm2P256CopyConditional(zOut, &tz, mask)
400 // If p was not zero, then n is now non-zero.
401 nIsInfinityMask &^= pIsNoninfiniteMask
402 }
403 }
404 }
405
406 func sm2P256PointToAffine(xOut, yOut, x, y, z *sm2P256FieldElement) {
407 var zInv, zInvSq sm2P256FieldElement
408
409 zz := sm2P256ToBig(z)
410 zz.ModInverse(zz, sm2P256.P)
411 sm2P256FromBig(&zInv, zz)
412
413 sm2P256Square(&zInvSq, &zInv)
414 sm2P256Mul(xOut, x, &zInvSq)
415 sm2P256Mul(&zInv, &zInv, &zInvSq)
416 sm2P256Mul(yOut, y, &zInv)
417 }
418
419 func sm2P256ToAffine(x, y, z *sm2P256FieldElement) (xOut, yOut *big.Int) {
420 var xx, yy sm2P256FieldElement
421
422 sm2P256PointToAffine(&xx, &yy, x, y, z)
423 return sm2P256ToBig(&xx), sm2P256ToBig(&yy)
424 }
425
426 var sm2P256Factor = []sm2P256FieldElement{
427 sm2P256FieldElement{0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0},
428 sm2P256FieldElement{0x2, 0x0, 0x1FFFFF00, 0x7FF, 0x0, 0x0, 0x0, 0x2000000, 0x0},
429 sm2P256FieldElement{0x4, 0x0, 0x1FFFFE00, 0xFFF, 0x0, 0x0, 0x0, 0x4000000, 0x0},
430 sm2P256FieldElement{0x6, 0x0, 0x1FFFFD00, 0x17FF, 0x0, 0x0, 0x0, 0x6000000, 0x0},
431 sm2P256FieldElement{0x8, 0x0, 0x1FFFFC00, 0x1FFF, 0x0, 0x0, 0x0, 0x8000000, 0x0},
432 sm2P256FieldElement{0xA, 0x0, 0x1FFFFB00, 0x27FF, 0x0, 0x0, 0x0, 0xA000000, 0x0},
433 sm2P256FieldElement{0xC, 0x0, 0x1FFFFA00, 0x2FFF, 0x0, 0x0, 0x0, 0xC000000, 0x0},
434 sm2P256FieldElement{0xE, 0x0, 0x1FFFF900, 0x37FF, 0x0, 0x0, 0x0, 0xE000000, 0x0},
435 sm2P256FieldElement{0x10, 0x0, 0x1FFFF800, 0x3FFF, 0x0, 0x0, 0x0, 0x0, 0x01},
436 }
437
438 func sm2P256Scalar(b *sm2P256FieldElement, a int) {
439 sm2P256Mul(b, b, &sm2P256Factor[a])
440 }
441
442 // (x3, y3, z3) = (x1, y1, z1) + (x2, y2, z2)
443 func sm2P256PointAdd(x1, y1, z1, x2, y2, z2, x3, y3, z3 *sm2P256FieldElement) {
444 var u1, u2, z22, z12, z23, z13, s1, s2, h, h2, r, r2, tm sm2P256FieldElement
445
446 if sm2P256ToBig(z1).Sign() == 0 {
447 sm2P256Dup(x3, x2)
448 sm2P256Dup(y3, y2)
449 sm2P256Dup(z3, z2)
450 return
451 }
452
453 if sm2P256ToBig(z2).Sign() == 0 {
454 sm2P256Dup(x3, x1)
455 sm2P256Dup(y3, y1)
456 sm2P256Dup(z3, z1)
457 return
458 }
459
460 sm2P256Square(&z12, z1) // z12 = z1 ^ 2
461 sm2P256Square(&z22, z2) // z22 = z2 ^ 2
462
463 sm2P256Mul(&z13, &z12, z1) // z13 = z1 ^ 3
464 sm2P256Mul(&z23, &z22, z2) // z23 = z2 ^ 3
465
466 sm2P256Mul(&u1, x1, &z22) // u1 = x1 * z2 ^ 2
467 sm2P256Mul(&u2, x2, &z12) // u2 = x2 * z1 ^ 2
468
469 sm2P256Mul(&s1, y1, &z23) // s1 = y1 * z2 ^ 3
470 sm2P256Mul(&s2, y2, &z13) // s2 = y2 * z1 ^ 3
471
472 if sm2P256ToBig(&u1).Cmp(sm2P256ToBig(&u2)) == 0 &&
473 sm2P256ToBig(&s1).Cmp(sm2P256ToBig(&s2)) == 0 {
474 sm2P256PointDouble(x1, y1, z1, x1, y1, z1)
475 }
476
477 sm2P256Sub(&h, &u2, &u1) // h = u2 - u1
478 sm2P256Sub(&r, &s2, &s1) // r = s2 - s1
479
480 sm2P256Square(&r2, &r) // r2 = r ^ 2
481 sm2P256Square(&h2, &h) // h2 = h ^ 2
482
483 sm2P256Mul(&tm, &h2, &h) // tm = h ^ 3
484 sm2P256Sub(x3, &r2, &tm)
485 sm2P256Mul(&tm, &u1, &h2)
486 sm2P256Scalar(&tm, 2) // tm = 2 * (u1 * h ^ 2)
487 sm2P256Sub(x3, x3, &tm) // x3 = r ^ 2 - h ^ 3 - 2 * u1 * h ^ 2
488
489 sm2P256Mul(&tm, &u1, &h2) // tm = u1 * h ^ 2
490 sm2P256Sub(&tm, &tm, x3) // tm = u1 * h ^ 2 - x3
491 sm2P256Mul(y3, &r, &tm)
492 sm2P256Mul(&tm, &h2, &h) // tm = h ^ 3
493 sm2P256Mul(&tm, &tm, &s1) // tm = s1 * h ^ 3
494 sm2P256Sub(y3, y3, &tm) // y3 = r * (u1 * h ^ 2 - x3) - s1 * h ^ 3
495
496 sm2P256Mul(z3, z1, z2)
497 sm2P256Mul(z3, z3, &h) // z3 = z1 * z3 * h
498 }
499
500 // (x3, y3, z3) = (x1, y1, z1)- (x2, y2, z2)
501 func sm2P256PointSub(x1, y1, z1, x2, y2, z2, x3, y3, z3 *sm2P256FieldElement) {
502 var u1, u2, z22, z12, z23, z13, s1, s2, h, h2, r, r2, tm sm2P256FieldElement
503 y:=sm2P256ToBig(y2)
504 zero:=new(big.Int).SetInt64(0)
505 y.Sub(zero,y)
506 sm2P256FromBig(y2,y)
507
508 if sm2P256ToBig(z1).Sign() == 0 {
509 sm2P256Dup(x3, x2)
510 sm2P256Dup(y3, y2)
511 sm2P256Dup(z3, z2)
512 return
513 }
514
515 if sm2P256ToBig(z2).Sign() == 0 {
516 sm2P256Dup(x3, x1)
517 sm2P256Dup(y3, y1)
518 sm2P256Dup(z3, z1)
519 return
520 }
521
522 sm2P256Square(&z12, z1) // z12 = z1 ^ 2
523 sm2P256Square(&z22, z2) // z22 = z2 ^ 2
524
525 sm2P256Mul(&z13, &z12, z1) // z13 = z1 ^ 3
526 sm2P256Mul(&z23, &z22, z2) // z23 = z2 ^ 3
527
528 sm2P256Mul(&u1, x1, &z22) // u1 = x1 * z2 ^ 2
529 sm2P256Mul(&u2, x2, &z12) // u2 = x2 * z1 ^ 2
530
531 sm2P256Mul(&s1, y1, &z23) // s1 = y1 * z2 ^ 3
532 sm2P256Mul(&s2, y2, &z13) // s2 = y2 * z1 ^ 3
533
534 if sm2P256ToBig(&u1).Cmp(sm2P256ToBig(&u2)) == 0 &&
535 sm2P256ToBig(&s1).Cmp(sm2P256ToBig(&s2)) == 0 {
536 sm2P256PointDouble(x1, y1, z1, x1, y1, z1)
537 }
538
539 sm2P256Sub(&h, &u2, &u1) // h = u2 - u1
540 sm2P256Sub(&r, &s2, &s1) // r = s2 - s1
541
542 sm2P256Square(&r2, &r) // r2 = r ^ 2
543 sm2P256Square(&h2, &h) // h2 = h ^ 2
544
545 sm2P256Mul(&tm, &h2, &h) // tm = h ^ 3
546 sm2P256Sub(x3, &r2, &tm)
547 sm2P256Mul(&tm, &u1, &h2)
548 sm2P256Scalar(&tm, 2) // tm = 2 * (u1 * h ^ 2)
549 sm2P256Sub(x3, x3, &tm) // x3 = r ^ 2 - h ^ 3 - 2 * u1 * h ^ 2
550
551 sm2P256Mul(&tm, &u1, &h2) // tm = u1 * h ^ 2
552 sm2P256Sub(&tm, &tm, x3) // tm = u1 * h ^ 2 - x3
553 sm2P256Mul(y3, &r, &tm)
554 sm2P256Mul(&tm, &h2, &h) // tm = h ^ 3
555 sm2P256Mul(&tm, &tm, &s1) // tm = s1 * h ^ 3
556 sm2P256Sub(y3, y3, &tm) // y3 = r * (u1 * h ^ 2 - x3) - s1 * h ^ 3
557
558 sm2P256Mul(z3, z1, z2)
559 sm2P256Mul(z3, z3, &h) // z3 = z1 * z3 * h
560 }
561
562 func sm2P256PointDouble(x3, y3, z3, x, y, z *sm2P256FieldElement) {
563 var s, m, m2, x2, y2, z2, z4, y4, az4 sm2P256FieldElement
564
565 sm2P256Square(&x2, x) // x2 = x ^ 2
566 sm2P256Square(&y2, y) // y2 = y ^ 2
567 sm2P256Square(&z2, z) // z2 = z ^ 2
568
569 sm2P256Square(&z4, z) // z4 = z ^ 2
570 sm2P256Mul(&z4, &z4, z) // z4 = z ^ 3
571 sm2P256Mul(&z4, &z4, z) // z4 = z ^ 4
572
573 sm2P256Square(&y4, y) // y4 = y ^ 2
574 sm2P256Mul(&y4, &y4, y) // y4 = y ^ 3
575 sm2P256Mul(&y4, &y4, y) // y4 = y ^ 4
576 sm2P256Scalar(&y4, 8) // y4 = 8 * y ^ 4
577
578 sm2P256Mul(&s, x, &y2)
579 sm2P256Scalar(&s, 4) // s = 4 * x * y ^ 2
580
581 sm2P256Dup(&m, &x2)
582 sm2P256Scalar(&m, 3)
583 sm2P256Mul(&az4, &sm2P256.a, &z4)
584 sm2P256Add(&m, &m, &az4) // m = 3 * x ^ 2 + a * z ^ 4
585
586 sm2P256Square(&m2, &m) // m2 = m ^ 2
587
588 sm2P256Add(z3, y, z)
589 sm2P256Square(z3, z3)
590 sm2P256Sub(z3, z3, &z2)
591 sm2P256Sub(z3, z3, &y2) // z' = (y + z) ^2 - z ^ 2 - y ^ 2
592
593 sm2P256Sub(x3, &m2, &s)
594 sm2P256Sub(x3, x3, &s) // x' = m2 - 2 * s
595
596 sm2P256Sub(y3, &s, x3)
597 sm2P256Mul(y3, y3, &m)
598 sm2P256Sub(y3, y3, &y4) // y' = m * (s - x') - 8 * y ^ 4
599 }
600
601 // p256Zero31 is 0 mod p.
602 var sm2P256Zero31 = sm2P256FieldElement{0x7FFFFFF8, 0x3FFFFFFC, 0x800003FC, 0x3FFFDFFC, 0x7FFFFFFC, 0x3FFFFFFC, 0x7FFFFFFC, 0x37FFFFFC, 0x7FFFFFFC}
603
604 // c = a + b
605 func sm2P256Add(c, a, b *sm2P256FieldElement) {
606 carry := uint32(0)
607 for i := 0; ; i++ {
608 c[i] = a[i] + b[i]
609 c[i] += carry
610 carry = c[i] >> 29
611 c[i] &= bottom29Bits
612 i++
613 if i == 9 {
614 break
615 }
616 c[i] = a[i] + b[i]
617 c[i] += carry
618 carry = c[i] >> 28
619 c[i] &= bottom28Bits
620 }
621 sm2P256ReduceCarry(c, carry)
622 }
623
624 // c = a - b
625 func sm2P256Sub(c, a, b *sm2P256FieldElement) {
626 var carry uint32
627
628 for i := 0; ; i++ {
629 c[i] = a[i] - b[i]
630 c[i] += sm2P256Zero31[i]
631 c[i] += carry
632 carry = c[i] >> 29
633 c[i] &= bottom29Bits
634 i++
635 if i == 9 {
636 break
637 }
638 c[i] = a[i] - b[i]
639 c[i] += sm2P256Zero31[i]
640 c[i] += carry
641 carry = c[i] >> 28
642 c[i] &= bottom28Bits
643 }
644 sm2P256ReduceCarry(c, carry)
645 }
646
647 // c = a * b
648 func sm2P256Mul(c, a, b *sm2P256FieldElement) {
649 var tmp sm2P256LargeFieldElement
650
651 tmp[0] = uint64(a[0]) * uint64(b[0])
652 tmp[1] = uint64(a[0])*(uint64(b[1])<<0) +
653 uint64(a[1])*(uint64(b[0])<<0)
654 tmp[2] = uint64(a[0])*(uint64(b[2])<<0) +
655 uint64(a[1])*(uint64(b[1])<<1) +
656 uint64(a[2])*(uint64(b[0])<<0)
657 tmp[3] = uint64(a[0])*(uint64(b[3])<<0) +
658 uint64(a[1])*(uint64(b[2])<<0) +
659 uint64(a[2])*(uint64(b[1])<<0) +
660 uint64(a[3])*(uint64(b[0])<<0)
661 tmp[4] = uint64(a[0])*(uint64(b[4])<<0) +
662 uint64(a[1])*(uint64(b[3])<<1) +
663 uint64(a[2])*(uint64(b[2])<<0) +
664 uint64(a[3])*(uint64(b[1])<<1) +
665 uint64(a[4])*(uint64(b[0])<<0)
666 tmp[5] = uint64(a[0])*(uint64(b[5])<<0) +
667 uint64(a[1])*(uint64(b[4])<<0) +
668 uint64(a[2])*(uint64(b[3])<<0) +
669 uint64(a[3])*(uint64(b[2])<<0) +
670 uint64(a[4])*(uint64(b[1])<<0) +
671 uint64(a[5])*(uint64(b[0])<<0)
672 tmp[6] = uint64(a[0])*(uint64(b[6])<<0) +
673 uint64(a[1])*(uint64(b[5])<<1) +
674 uint64(a[2])*(uint64(b[4])<<0) +
675 uint64(a[3])*(uint64(b[3])<<1) +
676 uint64(a[4])*(uint64(b[2])<<0) +
677 uint64(a[5])*(uint64(b[1])<<1) +
678 uint64(a[6])*(uint64(b[0])<<0)
679 tmp[7] = uint64(a[0])*(uint64(b[7])<<0) +
680 uint64(a[1])*(uint64(b[6])<<0) +
681 uint64(a[2])*(uint64(b[5])<<0) +
682 uint64(a[3])*(uint64(b[4])<<0) +
683 uint64(a[4])*(uint64(b[3])<<0) +
684 uint64(a[5])*(uint64(b[2])<<0) +
685 uint64(a[6])*(uint64(b[1])<<0) +
686 uint64(a[7])*(uint64(b[0])<<0)
687 // tmp[8] has the greatest value but doesn't overflow. See logic in
688 // p256Square.
689 tmp[8] = uint64(a[0])*(uint64(b[8])<<0) +
690 uint64(a[1])*(uint64(b[7])<<1) +
691 uint64(a[2])*(uint64(b[6])<<0) +
692 uint64(a[3])*(uint64(b[5])<<1) +
693 uint64(a[4])*(uint64(b[4])<<0) +
694 uint64(a[5])*(uint64(b[3])<<1) +
695 uint64(a[6])*(uint64(b[2])<<0) +
696 uint64(a[7])*(uint64(b[1])<<1) +
697 uint64(a[8])*(uint64(b[0])<<0)
698 tmp[9] = uint64(a[1])*(uint64(b[8])<<0) +
699 uint64(a[2])*(uint64(b[7])<<0) +
700 uint64(a[3])*(uint64(b[6])<<0) +
701 uint64(a[4])*(uint64(b[5])<<0) +
702 uint64(a[5])*(uint64(b[4])<<0) +
703 uint64(a[6])*(uint64(b[3])<<0) +
704 uint64(a[7])*(uint64(b[2])<<0) +
705 uint64(a[8])*(uint64(b[1])<<0)
706 tmp[10] = uint64(a[2])*(uint64(b[8])<<0) +
707 uint64(a[3])*(uint64(b[7])<<1) +
708 uint64(a[4])*(uint64(b[6])<<0) +
709 uint64(a[5])*(uint64(b[5])<<1) +
710 uint64(a[6])*(uint64(b[4])<<0) +
711 uint64(a[7])*(uint64(b[3])<<1) +
712 uint64(a[8])*(uint64(b[2])<<0)
713 tmp[11] = uint64(a[3])*(uint64(b[8])<<0) +
714 uint64(a[4])*(uint64(b[7])<<0) +
715 uint64(a[5])*(uint64(b[6])<<0) +
716 uint64(a[6])*(uint64(b[5])<<0) +
717 uint64(a[7])*(uint64(b[4])<<0) +
718 uint64(a[8])*(uint64(b[3])<<0)
719 tmp[12] = uint64(a[4])*(uint64(b[8])<<0) +
720 uint64(a[5])*(uint64(b[7])<<1) +
721 uint64(a[6])*(uint64(b[6])<<0) +
722 uint64(a[7])*(uint64(b[5])<<1) +
723 uint64(a[8])*(uint64(b[4])<<0)
724 tmp[13] = uint64(a[5])*(uint64(b[8])<<0) +
725 uint64(a[6])*(uint64(b[7])<<0) +
726 uint64(a[7])*(uint64(b[6])<<0) +
727 uint64(a[8])*(uint64(b[5])<<0)
728 tmp[14] = uint64(a[6])*(uint64(b[8])<<0) +
729 uint64(a[7])*(uint64(b[7])<<1) +
730 uint64(a[8])*(uint64(b[6])<<0)
731 tmp[15] = uint64(a[7])*(uint64(b[8])<<0) +
732 uint64(a[8])*(uint64(b[7])<<0)
733 tmp[16] = uint64(a[8]) * (uint64(b[8]) << 0)
734 sm2P256ReduceDegree(c, &tmp)
735 }
736
737 // b = a * a
738 func sm2P256Square(b, a *sm2P256FieldElement) {
739 var tmp sm2P256LargeFieldElement
740
741 tmp[0] = uint64(a[0]) * uint64(a[0])
742 tmp[1] = uint64(a[0]) * (uint64(a[1]) << 1)
743 tmp[2] = uint64(a[0])*(uint64(a[2])<<1) +
744 uint64(a[1])*(uint64(a[1])<<1)
745 tmp[3] = uint64(a[0])*(uint64(a[3])<<1) +
746 uint64(a[1])*(uint64(a[2])<<1)
747 tmp[4] = uint64(a[0])*(uint64(a[4])<<1) +
748 uint64(a[1])*(uint64(a[3])<<2) +
749 uint64(a[2])*uint64(a[2])
750 tmp[5] = uint64(a[0])*(uint64(a[5])<<1) +
751 uint64(a[1])*(uint64(a[4])<<1) +
752 uint64(a[2])*(uint64(a[3])<<1)
753 tmp[6] = uint64(a[0])*(uint64(a[6])<<1) +
754 uint64(a[1])*(uint64(a[5])<<2) +
755 uint64(a[2])*(uint64(a[4])<<1) +
756 uint64(a[3])*(uint64(a[3])<<1)
757 tmp[7] = uint64(a[0])*(uint64(a[7])<<1) +
758 uint64(a[1])*(uint64(a[6])<<1) +
759 uint64(a[2])*(uint64(a[5])<<1) +
760 uint64(a[3])*(uint64(a[4])<<1)
761 // tmp[8] has the greatest value of 2**61 + 2**60 + 2**61 + 2**60 + 2**60,
762 // which is < 2**64 as required.
763 tmp[8] = uint64(a[0])*(uint64(a[8])<<1) +
764 uint64(a[1])*(uint64(a[7])<<2) +
765 uint64(a[2])*(uint64(a[6])<<1) +
766 uint64(a[3])*(uint64(a[5])<<2) +
767 uint64(a[4])*uint64(a[4])
768 tmp[9] = uint64(a[1])*(uint64(a[8])<<1) +
769 uint64(a[2])*(uint64(a[7])<<1) +
770 uint64(a[3])*(uint64(a[6])<<1) +
771 uint64(a[4])*(uint64(a[5])<<1)
772 tmp[10] = uint64(a[2])*(uint64(a[8])<<1) +
773 uint64(a[3])*(uint64(a[7])<<2) +
774 uint64(a[4])*(uint64(a[6])<<1) +
775 uint64(a[5])*(uint64(a[5])<<1)
776 tmp[11] = uint64(a[3])*(uint64(a[8])<<1) +
777 uint64(a[4])*(uint64(a[7])<<1) +
778 uint64(a[5])*(uint64(a[6])<<1)
779 tmp[12] = uint64(a[4])*(uint64(a[8])<<1) +
780 uint64(a[5])*(uint64(a[7])<<2) +
781 uint64(a[6])*uint64(a[6])
782 tmp[13] = uint64(a[5])*(uint64(a[8])<<1) +
783 uint64(a[6])*(uint64(a[7])<<1)
784 tmp[14] = uint64(a[6])*(uint64(a[8])<<1) +
785 uint64(a[7])*(uint64(a[7])<<1)
786 tmp[15] = uint64(a[7]) * (uint64(a[8]) << 1)
787 tmp[16] = uint64(a[8]) * uint64(a[8])
788 sm2P256ReduceDegree(b, &tmp)
789 }
790
791 // nonZeroToAllOnes returns:
792 // 0xffffffff for 0 < x <= 2**31
793 // 0 for x == 0 or x > 2**31.
794 func nonZeroToAllOnes(x uint32) uint32 {
795 return ((x - 1) >> 31) - 1
796 }
797
798 var sm2P256Carry = [8 * 9]uint32{
799 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
800 0x2, 0x0, 0x1FFFFF00, 0x7FF, 0x0, 0x0, 0x0, 0x2000000, 0x0,
801 0x4, 0x0, 0x1FFFFE00, 0xFFF, 0x0, 0x0, 0x0, 0x4000000, 0x0,
802 0x6, 0x0, 0x1FFFFD00, 0x17FF, 0x0, 0x0, 0x0, 0x6000000, 0x0,
803 0x8, 0x0, 0x1FFFFC00, 0x1FFF, 0x0, 0x0, 0x0, 0x8000000, 0x0,
804 0xA, 0x0, 0x1FFFFB00, 0x27FF, 0x0, 0x0, 0x0, 0xA000000, 0x0,
805 0xC, 0x0, 0x1FFFFA00, 0x2FFF, 0x0, 0x0, 0x0, 0xC000000, 0x0,
806 0xE, 0x0, 0x1FFFF900, 0x37FF, 0x0, 0x0, 0x0, 0xE000000, 0x0,
807 }
808
809 // carry < 2 ^ 3
810 func sm2P256ReduceCarry(a *sm2P256FieldElement, carry uint32) {
811 a[0] += sm2P256Carry[carry*9+0]
812 a[2] += sm2P256Carry[carry*9+2]
813 a[3] += sm2P256Carry[carry*9+3]
814 a[7] += sm2P256Carry[carry*9+7]
815 }
816
817
818 func sm2P256ReduceDegree(a *sm2P256FieldElement, b *sm2P256LargeFieldElement) {
819 var tmp [18]uint32
820 var carry, x, xMask uint32
821
822 // tmp
823 // 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 ...
824 // 29 | 28 | 29 | 28 | 29 | 28 | 29 | 28 | 29 | 28 | 29 ...
825 tmp[0] = uint32(b[0]) & bottom29Bits
826 tmp[1] = uint32(b[0]) >> 29
827 tmp[1] |= (uint32(b[0]>>32) << 3) & bottom28Bits
828 tmp[1] += uint32(b[1]) & bottom28Bits
829 carry = tmp[1] >> 28
830 tmp[1] &= bottom28Bits
831 for i := 2; i < 17; i++ {
832 tmp[i] = (uint32(b[i-2] >> 32)) >> 25
833 tmp[i] += (uint32(b[i-1])) >> 28
834 tmp[i] += (uint32(b[i-1]>>32) << 4) & bottom29Bits
835 tmp[i] += uint32(b[i]) & bottom29Bits
836 tmp[i] += carry
837 carry = tmp[i] >> 29
838 tmp[i] &= bottom29Bits
839
840 i++
841 if i == 17 {
842 break
843 }
844 tmp[i] = uint32(b[i-2]>>32) >> 25
845 tmp[i] += uint32(b[i-1]) >> 29
846 tmp[i] += ((uint32(b[i-1] >> 32)) << 3) & bottom28Bits
847 tmp[i] += uint32(b[i]) & bottom28Bits
848 tmp[i] += carry
849 carry = tmp[i] >> 28
850 tmp[i] &= bottom28Bits
851 }
852 tmp[17] = uint32(b[15]>>32) >> 25
853 tmp[17] += uint32(b[16]) >> 29
854 tmp[17] += uint32(b[16]>>32) << 3
855 tmp[17] += carry
856
857 for i := 0; ; i += 2 {
858
859 tmp[i+1] += tmp[i] >> 29
860 x = tmp[i] & bottom29Bits
861 tmp[i] = 0
862 if x > 0 {
863 set4 := uint32(0)
864 set7 := uint32(0)
865 xMask = nonZeroToAllOnes(x)
866 tmp[i+2] += (x << 7) & bottom29Bits
867 tmp[i+3] += x >> 22
868 if tmp[i+3] < 0x10000000 {
869 set4 = 1
870 tmp[i+3] += 0x10000000 & xMask
871 tmp[i+3] -= (x << 10) & bottom28Bits
872 } else {
873 tmp[i+3] -= (x << 10) & bottom28Bits
874 }
875 if tmp[i+4] < 0x20000000 {
876 tmp[i+4] += 0x20000000 & xMask
877 tmp[i+4] -= set4 // 借位
878 tmp[i+4] -= x >> 18
879 if tmp[i+5] < 0x10000000 {
880 tmp[i+5] += 0x10000000 & xMask
881 tmp[i+5] -= 1 // 借位
882 if tmp[i+6] < 0x20000000 {
883 set7 = 1
884 tmp[i+6] += 0x20000000 & xMask
885 tmp[i+6] -= 1 // 借位
886 } else {
887 tmp[i+6] -= 1 // 借位
888 }
889 } else {
890 tmp[i+5] -= 1
891 }
892 } else {
893 tmp[i+4] -= set4 // 借位
894 tmp[i+4] -= x >> 18
895 }
896 if tmp[i+7] < 0x10000000 {
897 tmp[i+7] += 0x10000000 & xMask
898 tmp[i+7] -= set7
899 tmp[i+7] -= (x << 24) & bottom28Bits
900 tmp[i+8] += (x << 28) & bottom29Bits
901 if tmp[i+8] < 0x20000000 {
902 tmp[i+8] += 0x20000000 & xMask
903 tmp[i+8] -= 1
904 tmp[i+8] -= x >> 4
905 tmp[i+9] += ((x >> 1) - 1) & xMask
906 } else {
907 tmp[i+8] -= 1
908 tmp[i+8] -= x >> 4
909 tmp[i+9] += (x >> 1) & xMask
910 }
911 } else {
912 tmp[i+7] -= set7 // 借位
913 tmp[i+7] -= (x << 24) & bottom28Bits
914 tmp[i+8] += (x << 28) & bottom29Bits
915 if tmp[i+8] < 0x20000000 {
916 tmp[i+8] += 0x20000000 & xMask
917 tmp[i+8] -= x >> 4
918 tmp[i+9] += ((x >> 1) - 1) & xMask
919 } else {
920 tmp[i+8] -= x >> 4
921 tmp[i+9] += (x >> 1) & xMask
922 }
923 }
924
925 }
926
927 if i+1 == 9 {
928 break
929 }
930
931 tmp[i+2] += tmp[i+1] >> 28
932 x = tmp[i+1] & bottom28Bits
933 tmp[i+1] = 0
934 if x > 0 {
935 set5 := uint32(0)
936 set8 := uint32(0)
937 set9 := uint32(0)
938 xMask = nonZeroToAllOnes(x)
939 tmp[i+3] += (x << 7) & bottom28Bits
940 tmp[i+4] += x >> 21
941 if tmp[i+4] < 0x20000000 {
942 set5 = 1
943 tmp[i+4] += 0x20000000 & xMask
944 tmp[i+4] -= (x << 11) & bottom29Bits
945 } else {
946 tmp[i+4] -= (x << 11) & bottom29Bits
947 }
948 if tmp[i+5] < 0x10000000 {
949 tmp[i+5] += 0x10000000 & xMask
950 tmp[i+5] -= set5 // 借位
951 tmp[i+5] -= x >> 18
952 if tmp[i+6] < 0x20000000 {
953 tmp[i+6] += 0x20000000 & xMask
954 tmp[i+6] -= 1 // 借位
955 if tmp[i+7] < 0x10000000 {
956 set8 = 1
957 tmp[i+7] += 0x10000000 & xMask
958 tmp[i+7] -= 1 // 借位
959 } else {
960 tmp[i+7] -= 1 // 借位
961 }
962 } else {
963 tmp[i+6] -= 1 // 借位
964 }
965 } else {
966 tmp[i+5] -= set5 // 借位
967 tmp[i+5] -= x >> 18
968 }
969 if tmp[i+8] < 0x20000000 {
970 set9 = 1
971 tmp[i+8] += 0x20000000 & xMask
972 tmp[i+8] -= set8
973 tmp[i+8] -= (x << 25) & bottom29Bits
974 } else {
975 tmp[i+8] -= set8
976 tmp[i+8] -= (x << 25) & bottom29Bits
977 }
978 if tmp[i+9] < 0x10000000 {
979 tmp[i+9] += 0x10000000 & xMask
980 tmp[i+9] -= set9 // 借位
981 tmp[i+9] -= x >> 4
982 tmp[i+10] += (x - 1) & xMask
983 } else {
984 tmp[i+9] -= set9 // 借位
985 tmp[i+9] -= x >> 4
986 tmp[i+10] += x & xMask
987 }
988 }
989 }
990
991 carry = uint32(0)
992 for i := 0; i < 8; i++ {
993 a[i] = tmp[i+9]
994 a[i] += carry
995 a[i] += (tmp[i+10] << 28) & bottom29Bits
996 carry = a[i] >> 29
997 a[i] &= bottom29Bits
998
999 i++
1000 a[i] = tmp[i+9] >> 1
1001 a[i] += carry
1002 carry = a[i] >> 28
1003 a[i] &= bottom28Bits
1004 }
1005 a[8] = tmp[17]
1006 a[8] += carry
1007 carry = a[8] >> 29
1008 a[8] &= bottom29Bits
1009 sm2P256ReduceCarry(a, carry)
1010 }
1011
1012 // b = a
1013 func sm2P256Dup(b, a *sm2P256FieldElement) {
1014 *b = *a
1015 }
1016
1017 // X = a * R mod P
1018 func sm2P256FromBig(X *sm2P256FieldElement, a *big.Int) {
1019 x := new(big.Int).Lsh(a, 257)
1020 x.Mod(x, sm2P256.P)
1021 for i := 0; i < 9; i++ {
1022 if bits := x.Bits(); len(bits) > 0 {
1023 X[i] = uint32(bits[0]) & bottom29Bits
1024 } else {
1025 X[i] = 0
1026 }
1027 x.Rsh(x, 29)
1028 i++
1029 if i == 9 {
1030 break
1031 }
1032 if bits := x.Bits(); len(bits) > 0 {
1033 X[i] = uint32(bits[0]) & bottom28Bits
1034 } else {
1035 X[i] = 0
1036 }
1037 x.Rsh(x, 28)
1038 }
1039 }
1040
1041 // X = r * R mod P
1042 // r = X * R' mod P
1043 func sm2P256ToBig(X *sm2P256FieldElement) *big.Int {
1044 r, tm := new(big.Int), new(big.Int)
1045 r.SetInt64(int64(X[8]))
1046 for i := 7; i >= 0; i-- {
1047 if (i & 1) == 0 {
1048 r.Lsh(r, 29)
1049 } else {
1050 r.Lsh(r, 28)
1051 }
1052 tm.SetInt64(int64(X[i]))
1053 r.Add(r, tm)
1054 }
1055 r.Mul(r, sm2P256.RInverse)
1056 r.Mod(r, sm2P256.P)
1057 return r
1058 }
1059 func WNafReversed(wnaf []int8) []int8 {
1060 wnafRev := make([]int8, len(wnaf), len(wnaf))
1061 for i, v := range wnaf {
1062 wnafRev[len(wnaf)-(1+i)] = v
1063 }
1064 return wnafRev
1065 }
1066 func sm2GenrateWNaf(b []byte) []int8 {
1067 n:= new(big.Int).SetBytes(b)
1068 var k *big.Int
1069 if n.Cmp(sm2P256.N) >= 0 {
1070 n.Mod(n, sm2P256.N)
1071 k = n
1072 } else {
1073 k = n
1074 }
1075 wnaf := make([]int8, k.BitLen()+1, k.BitLen()+1)
1076 if k.Sign() == 0 {
1077 return wnaf
1078 }
1079 var width, pow2, sign int
1080 width, pow2, sign = 4, 16, 8
1081 var mask int64 = 15
1082 var carry bool
1083 var length, pos int
1084 for pos <= k.BitLen() {
1085 if k.Bit(pos) == boolToUint(carry) {
1086 pos++
1087 continue
1088 }
1089 k.Rsh(k, uint(pos))
1090 var digit int
1091 digit = int(k.Int64() & mask)
1092 if carry {
1093 digit++
1094 }
1095 carry = (digit & sign) != 0
1096 if carry {
1097 digit -= pow2
1098 }
1099 length += pos
1100 wnaf[length] = int8(digit)
1101 pos = int(width)
1102 }
1103 if len(wnaf) > length+1 {
1104 t := make([]int8, length+1, length+1)
1105 copy(t, wnaf[0:length+1])
1106 wnaf = t
1107 }
1108 return wnaf
1109 }
1110 func boolToUint(b bool) uint {
1111 if b {
1112 return 1
1113 }
1114 return 0
1115 }
1116 func abs(a int8) uint32{
1117 if a<0 {
1118 return uint32(-a)
1119 }
1120 return uint32(a)
1121 }
1122
1123 func sm2P256ScalarMult(xOut, yOut, zOut, x, y *sm2P256FieldElement, scalar []int8) {
1124 var precomp [16][3]sm2P256FieldElement
1125 var px, py, pz, tx, ty, tz sm2P256FieldElement
1126 var nIsInfinityMask, index, pIsNoninfiniteMask, mask uint32
1127
1128 // We precompute 0,1,2,... times {x,y}.
1129 precomp[1][0] = *x
1130 precomp[1][1] = *y
1131 precomp[1][2] = sm2P256Factor[1]
1132
1133 for i := 2; i < 8; i += 2 {
1134 sm2P256PointDouble(&precomp[i][0], &precomp[i][1], &precomp[i][2], &precomp[i/2][0], &precomp[i/2][1], &precomp[i/2][2])
1135 sm2P256PointAddMixed(&precomp[i+1][0], &precomp[i+1][1], &precomp[i+1][2], &precomp[i][0], &precomp[i][1], &precomp[i][2], x, y)
1136 }
1137
1138 for i := range xOut {
1139 xOut[i] = 0
1140 }
1141 for i := range yOut {
1142 yOut[i] = 0
1143 }
1144 for i := range zOut {
1145 zOut[i] = 0
1146 }
1147 nIsInfinityMask = ^uint32(0)
1148 var zeroes int16
1149 for i := 0; i<len(scalar); i++ {
1150 if scalar[i] ==0{
1151 zeroes++
1152 continue
1153 }
1154 if(zeroes>0){
1155 for ;zeroes>0;zeroes-- {
1156 sm2P256PointDouble(xOut, yOut, zOut, xOut, yOut, zOut)
1157 }
1158 }
1159 index = abs(scalar[i])
1160 sm2P256PointDouble(xOut, yOut, zOut, xOut, yOut, zOut)
1161 sm2P256SelectJacobianPoint(&px, &py, &pz, &precomp, index)
1162 if scalar[i] > 0 {
1163 sm2P256PointAdd(xOut, yOut, zOut, &px, &py, &pz, &tx, &ty, &tz)
1164 } else {
1165 sm2P256PointSub(xOut, yOut, zOut, &px, &py, &pz, &tx, &ty, &tz)
1166 }
1167 sm2P256CopyConditional(xOut, &px, nIsInfinityMask)
1168 sm2P256CopyConditional(yOut, &py, nIsInfinityMask)
1169 sm2P256CopyConditional(zOut, &pz, nIsInfinityMask)
1170 pIsNoninfiniteMask = nonZeroToAllOnes(index)
1171 mask = pIsNoninfiniteMask & ^nIsInfinityMask
1172 sm2P256CopyConditional(xOut, &tx, mask)
1173 sm2P256CopyConditional(yOut, &ty, mask)
1174 sm2P256CopyConditional(zOut, &tz, mask)
1175 nIsInfinityMask &^= pIsNoninfiniteMask
1176 }
1177 if(zeroes>0){
1178 for ;zeroes>0;zeroes-- {
1179 sm2P256PointDouble(xOut, yOut, zOut, xOut, yOut, zOut)
1180 }
1181 }
1182 }
1183