2
0

ecp_nistz256.c 50 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508
  1. /*
  2. * Copyright 2014-2023 The OpenSSL Project Authors. All Rights Reserved.
  3. * Copyright (c) 2014, Intel Corporation. All Rights Reserved.
  4. * Copyright (c) 2015, CloudFlare, Inc.
  5. *
  6. * Licensed under the Apache License 2.0 (the "License"). You may not use
  7. * this file except in compliance with the License. You can obtain a copy
  8. * in the file LICENSE in the source distribution or at
  9. * https://www.openssl.org/source/license.html
  10. *
  11. * Originally written by Shay Gueron (1, 2), and Vlad Krasnov (1, 3)
  12. * (1) Intel Corporation, Israel Development Center, Haifa, Israel
  13. * (2) University of Haifa, Israel
  14. * (3) CloudFlare, Inc.
  15. *
  16. * Reference:
  17. * S.Gueron and V.Krasnov, "Fast Prime Field Elliptic Curve Cryptography with
  18. * 256 Bit Primes"
  19. */
  20. /*
  21. * ECDSA low level APIs are deprecated for public use, but still ok for
  22. * internal use.
  23. */
  24. #include "internal/deprecated.h"
  25. #include <string.h>
  26. #include "internal/cryptlib.h"
  27. #include "crypto/bn.h"
  28. #include "ec_local.h"
  29. #include "internal/refcount.h"
  30. #if BN_BITS2 != 64
  31. # define TOBN(hi,lo) lo,hi
  32. #else
  33. # define TOBN(hi,lo) ((BN_ULONG)hi<<32|lo)
  34. #endif
  35. #define ALIGNPTR(p,N) ((unsigned char *)p+N-(size_t)p%N)
  36. #define P256_LIMBS (256/BN_BITS2)
  37. typedef unsigned short u16;
  38. typedef struct {
  39. BN_ULONG X[P256_LIMBS];
  40. BN_ULONG Y[P256_LIMBS];
  41. BN_ULONG Z[P256_LIMBS];
  42. } P256_POINT;
  43. typedef struct {
  44. BN_ULONG X[P256_LIMBS];
  45. BN_ULONG Y[P256_LIMBS];
  46. } P256_POINT_AFFINE;
  47. typedef P256_POINT_AFFINE PRECOMP256_ROW[64];
  48. /* structure for precomputed multiples of the generator */
  49. struct nistz256_pre_comp_st {
  50. const EC_GROUP *group; /* Parent EC_GROUP object */
  51. size_t w; /* Window size */
  52. /*
  53. * Constant time access to the X and Y coordinates of the pre-computed,
  54. * generator multiplies, in the Montgomery domain. Pre-calculated
  55. * multiplies are stored in affine form.
  56. */
  57. PRECOMP256_ROW *precomp;
  58. void *precomp_storage;
  59. CRYPTO_REF_COUNT references;
  60. };
  61. /* Functions implemented in assembly */
  62. /*
  63. * Most of below mentioned functions *preserve* the property of inputs
  64. * being fully reduced, i.e. being in [0, modulus) range. Simply put if
  65. * inputs are fully reduced, then output is too. Note that reverse is
  66. * not true, in sense that given partially reduced inputs output can be
  67. * either, not unlikely reduced. And "most" in first sentence refers to
  68. * the fact that given the calculations flow one can tolerate that
  69. * addition, 1st function below, produces partially reduced result *if*
  70. * multiplications by 2 and 3, which customarily use addition, fully
  71. * reduce it. This effectively gives two options: a) addition produces
  72. * fully reduced result [as long as inputs are, just like remaining
  73. * functions]; b) addition is allowed to produce partially reduced
  74. * result, but multiplications by 2 and 3 perform additional reduction
  75. * step. Choice between the two can be platform-specific, but it was a)
  76. * in all cases so far...
  77. */
  78. /* Modular add: res = a+b mod P */
  79. void ecp_nistz256_add(BN_ULONG res[P256_LIMBS],
  80. const BN_ULONG a[P256_LIMBS],
  81. const BN_ULONG b[P256_LIMBS]);
  82. /* Modular mul by 2: res = 2*a mod P */
  83. void ecp_nistz256_mul_by_2(BN_ULONG res[P256_LIMBS],
  84. const BN_ULONG a[P256_LIMBS]);
  85. /* Modular mul by 3: res = 3*a mod P */
  86. void ecp_nistz256_mul_by_3(BN_ULONG res[P256_LIMBS],
  87. const BN_ULONG a[P256_LIMBS]);
  88. /* Modular div by 2: res = a/2 mod P */
  89. void ecp_nistz256_div_by_2(BN_ULONG res[P256_LIMBS],
  90. const BN_ULONG a[P256_LIMBS]);
  91. /* Modular sub: res = a-b mod P */
  92. void ecp_nistz256_sub(BN_ULONG res[P256_LIMBS],
  93. const BN_ULONG a[P256_LIMBS],
  94. const BN_ULONG b[P256_LIMBS]);
  95. /* Modular neg: res = -a mod P */
  96. void ecp_nistz256_neg(BN_ULONG res[P256_LIMBS], const BN_ULONG a[P256_LIMBS]);
  97. /* Montgomery mul: res = a*b*2^-256 mod P */
  98. void ecp_nistz256_mul_mont(BN_ULONG res[P256_LIMBS],
  99. const BN_ULONG a[P256_LIMBS],
  100. const BN_ULONG b[P256_LIMBS]);
  101. /* Montgomery sqr: res = a*a*2^-256 mod P */
  102. void ecp_nistz256_sqr_mont(BN_ULONG res[P256_LIMBS],
  103. const BN_ULONG a[P256_LIMBS]);
  104. /* Convert a number from Montgomery domain, by multiplying with 1 */
  105. void ecp_nistz256_from_mont(BN_ULONG res[P256_LIMBS],
  106. const BN_ULONG in[P256_LIMBS]);
  107. /* Convert a number to Montgomery domain, by multiplying with 2^512 mod P*/
  108. void ecp_nistz256_to_mont(BN_ULONG res[P256_LIMBS],
  109. const BN_ULONG in[P256_LIMBS]);
  110. /* Functions that perform constant time access to the precomputed tables */
  111. void ecp_nistz256_scatter_w5(P256_POINT *val,
  112. const P256_POINT *in_t, int idx);
  113. void ecp_nistz256_gather_w5(P256_POINT *val,
  114. const P256_POINT *in_t, int idx);
  115. void ecp_nistz256_scatter_w7(P256_POINT_AFFINE *val,
  116. const P256_POINT_AFFINE *in_t, int idx);
  117. void ecp_nistz256_gather_w7(P256_POINT_AFFINE *val,
  118. const P256_POINT_AFFINE *in_t, int idx);
  119. /* One converted into the Montgomery domain */
  120. static const BN_ULONG ONE[P256_LIMBS] = {
  121. TOBN(0x00000000, 0x00000001), TOBN(0xffffffff, 0x00000000),
  122. TOBN(0xffffffff, 0xffffffff), TOBN(0x00000000, 0xfffffffe)
  123. };
  124. static NISTZ256_PRE_COMP *ecp_nistz256_pre_comp_new(const EC_GROUP *group);
  125. /* Precomputed tables for the default generator */
  126. extern const PRECOMP256_ROW ecp_nistz256_precomputed[37];
  127. /* Recode window to a signed digit, see ecp_nistputil.c for details */
  128. static unsigned int _booth_recode_w5(unsigned int in)
  129. {
  130. unsigned int s, d;
  131. s = ~((in >> 5) - 1);
  132. d = (1 << 6) - in - 1;
  133. d = (d & s) | (in & ~s);
  134. d = (d >> 1) + (d & 1);
  135. return (d << 1) + (s & 1);
  136. }
  137. static unsigned int _booth_recode_w7(unsigned int in)
  138. {
  139. unsigned int s, d;
  140. s = ~((in >> 7) - 1);
  141. d = (1 << 8) - in - 1;
  142. d = (d & s) | (in & ~s);
  143. d = (d >> 1) + (d & 1);
  144. return (d << 1) + (s & 1);
  145. }
  146. static void copy_conditional(BN_ULONG dst[P256_LIMBS],
  147. const BN_ULONG src[P256_LIMBS], BN_ULONG move)
  148. {
  149. BN_ULONG mask1 = 0-move;
  150. BN_ULONG mask2 = ~mask1;
  151. dst[0] = (src[0] & mask1) ^ (dst[0] & mask2);
  152. dst[1] = (src[1] & mask1) ^ (dst[1] & mask2);
  153. dst[2] = (src[2] & mask1) ^ (dst[2] & mask2);
  154. dst[3] = (src[3] & mask1) ^ (dst[3] & mask2);
  155. if (P256_LIMBS == 8) {
  156. dst[4] = (src[4] & mask1) ^ (dst[4] & mask2);
  157. dst[5] = (src[5] & mask1) ^ (dst[5] & mask2);
  158. dst[6] = (src[6] & mask1) ^ (dst[6] & mask2);
  159. dst[7] = (src[7] & mask1) ^ (dst[7] & mask2);
  160. }
  161. }
  162. static BN_ULONG is_zero(BN_ULONG in)
  163. {
  164. in |= (0 - in);
  165. in = ~in;
  166. in >>= BN_BITS2 - 1;
  167. return in;
  168. }
  169. static BN_ULONG is_equal(const BN_ULONG a[P256_LIMBS],
  170. const BN_ULONG b[P256_LIMBS])
  171. {
  172. BN_ULONG res;
  173. res = a[0] ^ b[0];
  174. res |= a[1] ^ b[1];
  175. res |= a[2] ^ b[2];
  176. res |= a[3] ^ b[3];
  177. if (P256_LIMBS == 8) {
  178. res |= a[4] ^ b[4];
  179. res |= a[5] ^ b[5];
  180. res |= a[6] ^ b[6];
  181. res |= a[7] ^ b[7];
  182. }
  183. return is_zero(res);
  184. }
  185. static BN_ULONG is_one(const BIGNUM *z)
  186. {
  187. BN_ULONG res = 0;
  188. BN_ULONG *a = bn_get_words(z);
  189. if (bn_get_top(z) == (P256_LIMBS - P256_LIMBS / 8)) {
  190. res = a[0] ^ ONE[0];
  191. res |= a[1] ^ ONE[1];
  192. res |= a[2] ^ ONE[2];
  193. res |= a[3] ^ ONE[3];
  194. if (P256_LIMBS == 8) {
  195. res |= a[4] ^ ONE[4];
  196. res |= a[5] ^ ONE[5];
  197. res |= a[6] ^ ONE[6];
  198. /*
  199. * no check for a[7] (being zero) on 32-bit platforms,
  200. * because value of "one" takes only 7 limbs.
  201. */
  202. }
  203. res = is_zero(res);
  204. }
  205. return res;
  206. }
  207. /*
  208. * For reference, this macro is used only when new ecp_nistz256 assembly
  209. * module is being developed. For example, configure with
  210. * -DECP_NISTZ256_REFERENCE_IMPLEMENTATION and implement only functions
  211. * performing simplest arithmetic operations on 256-bit vectors. Then
  212. * work on implementation of higher-level functions performing point
  213. * operations. Then remove ECP_NISTZ256_REFERENCE_IMPLEMENTATION
  214. * and never define it again. (The correct macro denoting presence of
  215. * ecp_nistz256 module is ECP_NISTZ256_ASM.)
  216. */
  217. #ifndef ECP_NISTZ256_REFERENCE_IMPLEMENTATION
  218. void ecp_nistz256_point_double(P256_POINT *r, const P256_POINT *a);
  219. void ecp_nistz256_point_add(P256_POINT *r,
  220. const P256_POINT *a, const P256_POINT *b);
  221. void ecp_nistz256_point_add_affine(P256_POINT *r,
  222. const P256_POINT *a,
  223. const P256_POINT_AFFINE *b);
  224. #else
  225. /* Point double: r = 2*a */
  226. static void ecp_nistz256_point_double(P256_POINT *r, const P256_POINT *a)
  227. {
  228. BN_ULONG S[P256_LIMBS];
  229. BN_ULONG M[P256_LIMBS];
  230. BN_ULONG Zsqr[P256_LIMBS];
  231. BN_ULONG tmp0[P256_LIMBS];
  232. const BN_ULONG *in_x = a->X;
  233. const BN_ULONG *in_y = a->Y;
  234. const BN_ULONG *in_z = a->Z;
  235. BN_ULONG *res_x = r->X;
  236. BN_ULONG *res_y = r->Y;
  237. BN_ULONG *res_z = r->Z;
  238. ecp_nistz256_mul_by_2(S, in_y);
  239. ecp_nistz256_sqr_mont(Zsqr, in_z);
  240. ecp_nistz256_sqr_mont(S, S);
  241. ecp_nistz256_mul_mont(res_z, in_z, in_y);
  242. ecp_nistz256_mul_by_2(res_z, res_z);
  243. ecp_nistz256_add(M, in_x, Zsqr);
  244. ecp_nistz256_sub(Zsqr, in_x, Zsqr);
  245. ecp_nistz256_sqr_mont(res_y, S);
  246. ecp_nistz256_div_by_2(res_y, res_y);
  247. ecp_nistz256_mul_mont(M, M, Zsqr);
  248. ecp_nistz256_mul_by_3(M, M);
  249. ecp_nistz256_mul_mont(S, S, in_x);
  250. ecp_nistz256_mul_by_2(tmp0, S);
  251. ecp_nistz256_sqr_mont(res_x, M);
  252. ecp_nistz256_sub(res_x, res_x, tmp0);
  253. ecp_nistz256_sub(S, S, res_x);
  254. ecp_nistz256_mul_mont(S, S, M);
  255. ecp_nistz256_sub(res_y, S, res_y);
  256. }
  257. /* Point addition: r = a+b */
  258. static void ecp_nistz256_point_add(P256_POINT *r,
  259. const P256_POINT *a, const P256_POINT *b)
  260. {
  261. BN_ULONG U2[P256_LIMBS], S2[P256_LIMBS];
  262. BN_ULONG U1[P256_LIMBS], S1[P256_LIMBS];
  263. BN_ULONG Z1sqr[P256_LIMBS];
  264. BN_ULONG Z2sqr[P256_LIMBS];
  265. BN_ULONG H[P256_LIMBS], R[P256_LIMBS];
  266. BN_ULONG Hsqr[P256_LIMBS];
  267. BN_ULONG Rsqr[P256_LIMBS];
  268. BN_ULONG Hcub[P256_LIMBS];
  269. BN_ULONG res_x[P256_LIMBS];
  270. BN_ULONG res_y[P256_LIMBS];
  271. BN_ULONG res_z[P256_LIMBS];
  272. BN_ULONG in1infty, in2infty;
  273. const BN_ULONG *in1_x = a->X;
  274. const BN_ULONG *in1_y = a->Y;
  275. const BN_ULONG *in1_z = a->Z;
  276. const BN_ULONG *in2_x = b->X;
  277. const BN_ULONG *in2_y = b->Y;
  278. const BN_ULONG *in2_z = b->Z;
  279. /*
  280. * Infinity in encoded as (,,0)
  281. */
  282. in1infty = (in1_z[0] | in1_z[1] | in1_z[2] | in1_z[3]);
  283. if (P256_LIMBS == 8)
  284. in1infty |= (in1_z[4] | in1_z[5] | in1_z[6] | in1_z[7]);
  285. in2infty = (in2_z[0] | in2_z[1] | in2_z[2] | in2_z[3]);
  286. if (P256_LIMBS == 8)
  287. in2infty |= (in2_z[4] | in2_z[5] | in2_z[6] | in2_z[7]);
  288. in1infty = is_zero(in1infty);
  289. in2infty = is_zero(in2infty);
  290. ecp_nistz256_sqr_mont(Z2sqr, in2_z); /* Z2^2 */
  291. ecp_nistz256_sqr_mont(Z1sqr, in1_z); /* Z1^2 */
  292. ecp_nistz256_mul_mont(S1, Z2sqr, in2_z); /* S1 = Z2^3 */
  293. ecp_nistz256_mul_mont(S2, Z1sqr, in1_z); /* S2 = Z1^3 */
  294. ecp_nistz256_mul_mont(S1, S1, in1_y); /* S1 = Y1*Z2^3 */
  295. ecp_nistz256_mul_mont(S2, S2, in2_y); /* S2 = Y2*Z1^3 */
  296. ecp_nistz256_sub(R, S2, S1); /* R = S2 - S1 */
  297. ecp_nistz256_mul_mont(U1, in1_x, Z2sqr); /* U1 = X1*Z2^2 */
  298. ecp_nistz256_mul_mont(U2, in2_x, Z1sqr); /* U2 = X2*Z1^2 */
  299. ecp_nistz256_sub(H, U2, U1); /* H = U2 - U1 */
  300. /*
  301. * The formulae are incorrect if the points are equal so we check for
  302. * this and do doubling if this happens.
  303. *
  304. * Points here are in Jacobian projective coordinates (Xi, Yi, Zi)
  305. * that are bound to the affine coordinates (xi, yi) by the following
  306. * equations:
  307. * - xi = Xi / (Zi)^2
  308. * - y1 = Yi / (Zi)^3
  309. *
  310. * For the sake of optimization, the algorithm operates over
  311. * intermediate variables U1, U2 and S1, S2 that are derived from
  312. * the projective coordinates:
  313. * - U1 = X1 * (Z2)^2 ; U2 = X2 * (Z1)^2
  314. * - S1 = Y1 * (Z2)^3 ; S2 = Y2 * (Z1)^3
  315. *
  316. * It is easy to prove that is_equal(U1, U2) implies that the affine
  317. * x-coordinates are equal, or either point is at infinity.
  318. * Likewise is_equal(S1, S2) implies that the affine y-coordinates are
  319. * equal, or either point is at infinity.
  320. *
  321. * The special case of either point being the point at infinity (Z1 or Z2
  322. * is zero), is handled separately later on in this function, so we avoid
  323. * jumping to point_double here in those special cases.
  324. *
  325. * When both points are inverse of each other, we know that the affine
  326. * x-coordinates are equal, and the y-coordinates have different sign.
  327. * Therefore since U1 = U2, we know H = 0, and therefore Z3 = H*Z1*Z2
  328. * will equal 0, thus the result is infinity, if we simply let this
  329. * function continue normally.
  330. *
  331. * We use bitwise operations to avoid potential side-channels introduced by
  332. * the short-circuiting behaviour of boolean operators.
  333. */
  334. if (is_equal(U1, U2) & ~in1infty & ~in2infty & is_equal(S1, S2)) {
  335. /*
  336. * This is obviously not constant-time but it should never happen during
  337. * single point multiplication, so there is no timing leak for ECDH or
  338. * ECDSA signing.
  339. */
  340. ecp_nistz256_point_double(r, a);
  341. return;
  342. }
  343. ecp_nistz256_sqr_mont(Rsqr, R); /* R^2 */
  344. ecp_nistz256_mul_mont(res_z, H, in1_z); /* Z3 = H*Z1*Z2 */
  345. ecp_nistz256_sqr_mont(Hsqr, H); /* H^2 */
  346. ecp_nistz256_mul_mont(res_z, res_z, in2_z); /* Z3 = H*Z1*Z2 */
  347. ecp_nistz256_mul_mont(Hcub, Hsqr, H); /* H^3 */
  348. ecp_nistz256_mul_mont(U2, U1, Hsqr); /* U1*H^2 */
  349. ecp_nistz256_mul_by_2(Hsqr, U2); /* 2*U1*H^2 */
  350. ecp_nistz256_sub(res_x, Rsqr, Hsqr);
  351. ecp_nistz256_sub(res_x, res_x, Hcub);
  352. ecp_nistz256_sub(res_y, U2, res_x);
  353. ecp_nistz256_mul_mont(S2, S1, Hcub);
  354. ecp_nistz256_mul_mont(res_y, R, res_y);
  355. ecp_nistz256_sub(res_y, res_y, S2);
  356. copy_conditional(res_x, in2_x, in1infty);
  357. copy_conditional(res_y, in2_y, in1infty);
  358. copy_conditional(res_z, in2_z, in1infty);
  359. copy_conditional(res_x, in1_x, in2infty);
  360. copy_conditional(res_y, in1_y, in2infty);
  361. copy_conditional(res_z, in1_z, in2infty);
  362. memcpy(r->X, res_x, sizeof(res_x));
  363. memcpy(r->Y, res_y, sizeof(res_y));
  364. memcpy(r->Z, res_z, sizeof(res_z));
  365. }
  366. /* Point addition when b is known to be affine: r = a+b */
  367. static void ecp_nistz256_point_add_affine(P256_POINT *r,
  368. const P256_POINT *a,
  369. const P256_POINT_AFFINE *b)
  370. {
  371. BN_ULONG U2[P256_LIMBS], S2[P256_LIMBS];
  372. BN_ULONG Z1sqr[P256_LIMBS];
  373. BN_ULONG H[P256_LIMBS], R[P256_LIMBS];
  374. BN_ULONG Hsqr[P256_LIMBS];
  375. BN_ULONG Rsqr[P256_LIMBS];
  376. BN_ULONG Hcub[P256_LIMBS];
  377. BN_ULONG res_x[P256_LIMBS];
  378. BN_ULONG res_y[P256_LIMBS];
  379. BN_ULONG res_z[P256_LIMBS];
  380. BN_ULONG in1infty, in2infty;
  381. const BN_ULONG *in1_x = a->X;
  382. const BN_ULONG *in1_y = a->Y;
  383. const BN_ULONG *in1_z = a->Z;
  384. const BN_ULONG *in2_x = b->X;
  385. const BN_ULONG *in2_y = b->Y;
  386. /*
  387. * Infinity in encoded as (,,0)
  388. */
  389. in1infty = (in1_z[0] | in1_z[1] | in1_z[2] | in1_z[3]);
  390. if (P256_LIMBS == 8)
  391. in1infty |= (in1_z[4] | in1_z[5] | in1_z[6] | in1_z[7]);
  392. /*
  393. * In affine representation we encode infinity as (0,0), which is
  394. * not on the curve, so it is OK
  395. */
  396. in2infty = (in2_x[0] | in2_x[1] | in2_x[2] | in2_x[3] |
  397. in2_y[0] | in2_y[1] | in2_y[2] | in2_y[3]);
  398. if (P256_LIMBS == 8)
  399. in2infty |= (in2_x[4] | in2_x[5] | in2_x[6] | in2_x[7] |
  400. in2_y[4] | in2_y[5] | in2_y[6] | in2_y[7]);
  401. in1infty = is_zero(in1infty);
  402. in2infty = is_zero(in2infty);
  403. ecp_nistz256_sqr_mont(Z1sqr, in1_z); /* Z1^2 */
  404. ecp_nistz256_mul_mont(U2, in2_x, Z1sqr); /* U2 = X2*Z1^2 */
  405. ecp_nistz256_sub(H, U2, in1_x); /* H = U2 - U1 */
  406. ecp_nistz256_mul_mont(S2, Z1sqr, in1_z); /* S2 = Z1^3 */
  407. ecp_nistz256_mul_mont(res_z, H, in1_z); /* Z3 = H*Z1*Z2 */
  408. ecp_nistz256_mul_mont(S2, S2, in2_y); /* S2 = Y2*Z1^3 */
  409. ecp_nistz256_sub(R, S2, in1_y); /* R = S2 - S1 */
  410. ecp_nistz256_sqr_mont(Hsqr, H); /* H^2 */
  411. ecp_nistz256_sqr_mont(Rsqr, R); /* R^2 */
  412. ecp_nistz256_mul_mont(Hcub, Hsqr, H); /* H^3 */
  413. ecp_nistz256_mul_mont(U2, in1_x, Hsqr); /* U1*H^2 */
  414. ecp_nistz256_mul_by_2(Hsqr, U2); /* 2*U1*H^2 */
  415. ecp_nistz256_sub(res_x, Rsqr, Hsqr);
  416. ecp_nistz256_sub(res_x, res_x, Hcub);
  417. ecp_nistz256_sub(H, U2, res_x);
  418. ecp_nistz256_mul_mont(S2, in1_y, Hcub);
  419. ecp_nistz256_mul_mont(H, H, R);
  420. ecp_nistz256_sub(res_y, H, S2);
  421. copy_conditional(res_x, in2_x, in1infty);
  422. copy_conditional(res_x, in1_x, in2infty);
  423. copy_conditional(res_y, in2_y, in1infty);
  424. copy_conditional(res_y, in1_y, in2infty);
  425. copy_conditional(res_z, ONE, in1infty);
  426. copy_conditional(res_z, in1_z, in2infty);
  427. memcpy(r->X, res_x, sizeof(res_x));
  428. memcpy(r->Y, res_y, sizeof(res_y));
  429. memcpy(r->Z, res_z, sizeof(res_z));
  430. }
  431. #endif
  432. /* r = in^-1 mod p */
  433. static void ecp_nistz256_mod_inverse(BN_ULONG r[P256_LIMBS],
  434. const BN_ULONG in[P256_LIMBS])
  435. {
  436. /*
  437. * The poly is ffffffff 00000001 00000000 00000000 00000000 ffffffff
  438. * ffffffff ffffffff We use FLT and used poly-2 as exponent
  439. */
  440. BN_ULONG p2[P256_LIMBS];
  441. BN_ULONG p4[P256_LIMBS];
  442. BN_ULONG p8[P256_LIMBS];
  443. BN_ULONG p16[P256_LIMBS];
  444. BN_ULONG p32[P256_LIMBS];
  445. BN_ULONG res[P256_LIMBS];
  446. int i;
  447. ecp_nistz256_sqr_mont(res, in);
  448. ecp_nistz256_mul_mont(p2, res, in); /* 3*p */
  449. ecp_nistz256_sqr_mont(res, p2);
  450. ecp_nistz256_sqr_mont(res, res);
  451. ecp_nistz256_mul_mont(p4, res, p2); /* f*p */
  452. ecp_nistz256_sqr_mont(res, p4);
  453. ecp_nistz256_sqr_mont(res, res);
  454. ecp_nistz256_sqr_mont(res, res);
  455. ecp_nistz256_sqr_mont(res, res);
  456. ecp_nistz256_mul_mont(p8, res, p4); /* ff*p */
  457. ecp_nistz256_sqr_mont(res, p8);
  458. for (i = 0; i < 7; i++)
  459. ecp_nistz256_sqr_mont(res, res);
  460. ecp_nistz256_mul_mont(p16, res, p8); /* ffff*p */
  461. ecp_nistz256_sqr_mont(res, p16);
  462. for (i = 0; i < 15; i++)
  463. ecp_nistz256_sqr_mont(res, res);
  464. ecp_nistz256_mul_mont(p32, res, p16); /* ffffffff*p */
  465. ecp_nistz256_sqr_mont(res, p32);
  466. for (i = 0; i < 31; i++)
  467. ecp_nistz256_sqr_mont(res, res);
  468. ecp_nistz256_mul_mont(res, res, in);
  469. for (i = 0; i < 32 * 4; i++)
  470. ecp_nistz256_sqr_mont(res, res);
  471. ecp_nistz256_mul_mont(res, res, p32);
  472. for (i = 0; i < 32; i++)
  473. ecp_nistz256_sqr_mont(res, res);
  474. ecp_nistz256_mul_mont(res, res, p32);
  475. for (i = 0; i < 16; i++)
  476. ecp_nistz256_sqr_mont(res, res);
  477. ecp_nistz256_mul_mont(res, res, p16);
  478. for (i = 0; i < 8; i++)
  479. ecp_nistz256_sqr_mont(res, res);
  480. ecp_nistz256_mul_mont(res, res, p8);
  481. ecp_nistz256_sqr_mont(res, res);
  482. ecp_nistz256_sqr_mont(res, res);
  483. ecp_nistz256_sqr_mont(res, res);
  484. ecp_nistz256_sqr_mont(res, res);
  485. ecp_nistz256_mul_mont(res, res, p4);
  486. ecp_nistz256_sqr_mont(res, res);
  487. ecp_nistz256_sqr_mont(res, res);
  488. ecp_nistz256_mul_mont(res, res, p2);
  489. ecp_nistz256_sqr_mont(res, res);
  490. ecp_nistz256_sqr_mont(res, res);
  491. ecp_nistz256_mul_mont(res, res, in);
  492. memcpy(r, res, sizeof(res));
  493. }
  494. /*
  495. * ecp_nistz256_bignum_to_field_elem copies the contents of |in| to |out| and
  496. * returns one if it fits. Otherwise it returns zero.
  497. */
  498. __owur static int ecp_nistz256_bignum_to_field_elem(BN_ULONG out[P256_LIMBS],
  499. const BIGNUM *in)
  500. {
  501. return bn_copy_words(out, in, P256_LIMBS);
  502. }
  503. /* r = sum(scalar[i]*point[i]) */
  504. __owur static int ecp_nistz256_windowed_mul(const EC_GROUP *group,
  505. P256_POINT *r,
  506. const BIGNUM **scalar,
  507. const EC_POINT **point,
  508. size_t num, BN_CTX *ctx)
  509. {
  510. size_t i;
  511. int j, ret = 0;
  512. unsigned int idx;
  513. unsigned char (*p_str)[33] = NULL;
  514. const unsigned int window_size = 5;
  515. const unsigned int mask = (1 << (window_size + 1)) - 1;
  516. unsigned int wvalue;
  517. P256_POINT *temp; /* place for 5 temporary points */
  518. const BIGNUM **scalars = NULL;
  519. P256_POINT (*table)[16] = NULL;
  520. void *table_storage = NULL;
  521. if ((num * 16 + 6) > OPENSSL_MALLOC_MAX_NELEMS(P256_POINT)
  522. || (table_storage =
  523. OPENSSL_malloc((num * 16 + 5) * sizeof(P256_POINT) + 64)) == NULL
  524. || (p_str =
  525. OPENSSL_malloc(num * 33 * sizeof(unsigned char))) == NULL
  526. || (scalars = OPENSSL_malloc(num * sizeof(BIGNUM *))) == NULL)
  527. goto err;
  528. table = (void *)ALIGNPTR(table_storage, 64);
  529. temp = (P256_POINT *)(table + num);
  530. for (i = 0; i < num; i++) {
  531. P256_POINT *row = table[i];
  532. /* This is an unusual input, we don't guarantee constant-timeness. */
  533. if ((BN_num_bits(scalar[i]) > 256) || BN_is_negative(scalar[i])) {
  534. BIGNUM *mod;
  535. if ((mod = BN_CTX_get(ctx)) == NULL)
  536. goto err;
  537. if (!BN_nnmod(mod, scalar[i], group->order, ctx)) {
  538. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  539. goto err;
  540. }
  541. scalars[i] = mod;
  542. } else
  543. scalars[i] = scalar[i];
  544. for (j = 0; j < bn_get_top(scalars[i]) * BN_BYTES; j += BN_BYTES) {
  545. BN_ULONG d = bn_get_words(scalars[i])[j / BN_BYTES];
  546. p_str[i][j + 0] = (unsigned char)d;
  547. p_str[i][j + 1] = (unsigned char)(d >> 8);
  548. p_str[i][j + 2] = (unsigned char)(d >> 16);
  549. p_str[i][j + 3] = (unsigned char)(d >>= 24);
  550. if (BN_BYTES == 8) {
  551. d >>= 8;
  552. p_str[i][j + 4] = (unsigned char)d;
  553. p_str[i][j + 5] = (unsigned char)(d >> 8);
  554. p_str[i][j + 6] = (unsigned char)(d >> 16);
  555. p_str[i][j + 7] = (unsigned char)(d >> 24);
  556. }
  557. }
  558. for (; j < 33; j++)
  559. p_str[i][j] = 0;
  560. if (!ecp_nistz256_bignum_to_field_elem(temp[0].X, point[i]->X)
  561. || !ecp_nistz256_bignum_to_field_elem(temp[0].Y, point[i]->Y)
  562. || !ecp_nistz256_bignum_to_field_elem(temp[0].Z, point[i]->Z)) {
  563. ERR_raise(ERR_LIB_EC, EC_R_COORDINATES_OUT_OF_RANGE);
  564. goto err;
  565. }
  566. /*
  567. * row[0] is implicitly (0,0,0) (the point at infinity), therefore it
  568. * is not stored. All other values are actually stored with an offset
  569. * of -1 in table.
  570. */
  571. ecp_nistz256_scatter_w5 (row, &temp[0], 1);
  572. ecp_nistz256_point_double(&temp[1], &temp[0]); /*1+1=2 */
  573. ecp_nistz256_scatter_w5 (row, &temp[1], 2);
  574. ecp_nistz256_point_add (&temp[2], &temp[1], &temp[0]); /*2+1=3 */
  575. ecp_nistz256_scatter_w5 (row, &temp[2], 3);
  576. ecp_nistz256_point_double(&temp[1], &temp[1]); /*2*2=4 */
  577. ecp_nistz256_scatter_w5 (row, &temp[1], 4);
  578. ecp_nistz256_point_double(&temp[2], &temp[2]); /*2*3=6 */
  579. ecp_nistz256_scatter_w5 (row, &temp[2], 6);
  580. ecp_nistz256_point_add (&temp[3], &temp[1], &temp[0]); /*4+1=5 */
  581. ecp_nistz256_scatter_w5 (row, &temp[3], 5);
  582. ecp_nistz256_point_add (&temp[4], &temp[2], &temp[0]); /*6+1=7 */
  583. ecp_nistz256_scatter_w5 (row, &temp[4], 7);
  584. ecp_nistz256_point_double(&temp[1], &temp[1]); /*2*4=8 */
  585. ecp_nistz256_scatter_w5 (row, &temp[1], 8);
  586. ecp_nistz256_point_double(&temp[2], &temp[2]); /*2*6=12 */
  587. ecp_nistz256_scatter_w5 (row, &temp[2], 12);
  588. ecp_nistz256_point_double(&temp[3], &temp[3]); /*2*5=10 */
  589. ecp_nistz256_scatter_w5 (row, &temp[3], 10);
  590. ecp_nistz256_point_double(&temp[4], &temp[4]); /*2*7=14 */
  591. ecp_nistz256_scatter_w5 (row, &temp[4], 14);
  592. ecp_nistz256_point_add (&temp[2], &temp[2], &temp[0]); /*12+1=13*/
  593. ecp_nistz256_scatter_w5 (row, &temp[2], 13);
  594. ecp_nistz256_point_add (&temp[3], &temp[3], &temp[0]); /*10+1=11*/
  595. ecp_nistz256_scatter_w5 (row, &temp[3], 11);
  596. ecp_nistz256_point_add (&temp[4], &temp[4], &temp[0]); /*14+1=15*/
  597. ecp_nistz256_scatter_w5 (row, &temp[4], 15);
  598. ecp_nistz256_point_add (&temp[2], &temp[1], &temp[0]); /*8+1=9 */
  599. ecp_nistz256_scatter_w5 (row, &temp[2], 9);
  600. ecp_nistz256_point_double(&temp[1], &temp[1]); /*2*8=16 */
  601. ecp_nistz256_scatter_w5 (row, &temp[1], 16);
  602. }
  603. idx = 255;
  604. wvalue = p_str[0][(idx - 1) / 8];
  605. wvalue = (wvalue >> ((idx - 1) % 8)) & mask;
  606. /*
  607. * We gather to temp[0], because we know it's position relative
  608. * to table
  609. */
  610. ecp_nistz256_gather_w5(&temp[0], table[0], _booth_recode_w5(wvalue) >> 1);
  611. memcpy(r, &temp[0], sizeof(temp[0]));
  612. while (idx >= 5) {
  613. for (i = (idx == 255 ? 1 : 0); i < num; i++) {
  614. unsigned int off = (idx - 1) / 8;
  615. wvalue = p_str[i][off] | p_str[i][off + 1] << 8;
  616. wvalue = (wvalue >> ((idx - 1) % 8)) & mask;
  617. wvalue = _booth_recode_w5(wvalue);
  618. ecp_nistz256_gather_w5(&temp[0], table[i], wvalue >> 1);
  619. ecp_nistz256_neg(temp[1].Y, temp[0].Y);
  620. copy_conditional(temp[0].Y, temp[1].Y, (wvalue & 1));
  621. ecp_nistz256_point_add(r, r, &temp[0]);
  622. }
  623. idx -= window_size;
  624. ecp_nistz256_point_double(r, r);
  625. ecp_nistz256_point_double(r, r);
  626. ecp_nistz256_point_double(r, r);
  627. ecp_nistz256_point_double(r, r);
  628. ecp_nistz256_point_double(r, r);
  629. }
  630. /* Final window */
  631. for (i = 0; i < num; i++) {
  632. wvalue = p_str[i][0];
  633. wvalue = (wvalue << 1) & mask;
  634. wvalue = _booth_recode_w5(wvalue);
  635. ecp_nistz256_gather_w5(&temp[0], table[i], wvalue >> 1);
  636. ecp_nistz256_neg(temp[1].Y, temp[0].Y);
  637. copy_conditional(temp[0].Y, temp[1].Y, wvalue & 1);
  638. ecp_nistz256_point_add(r, r, &temp[0]);
  639. }
  640. ret = 1;
  641. err:
  642. OPENSSL_free(table_storage);
  643. OPENSSL_free(p_str);
  644. OPENSSL_free(scalars);
  645. return ret;
  646. }
  647. /* Coordinates of G, for which we have precomputed tables */
  648. static const BN_ULONG def_xG[P256_LIMBS] = {
  649. TOBN(0x79e730d4, 0x18a9143c), TOBN(0x75ba95fc, 0x5fedb601),
  650. TOBN(0x79fb732b, 0x77622510), TOBN(0x18905f76, 0xa53755c6)
  651. };
  652. static const BN_ULONG def_yG[P256_LIMBS] = {
  653. TOBN(0xddf25357, 0xce95560a), TOBN(0x8b4ab8e4, 0xba19e45c),
  654. TOBN(0xd2e88688, 0xdd21f325), TOBN(0x8571ff18, 0x25885d85)
  655. };
  656. /*
  657. * ecp_nistz256_is_affine_G returns one if |generator| is the standard, P-256
  658. * generator.
  659. */
  660. static int ecp_nistz256_is_affine_G(const EC_POINT *generator)
  661. {
  662. return (bn_get_top(generator->X) == P256_LIMBS) &&
  663. (bn_get_top(generator->Y) == P256_LIMBS) &&
  664. is_equal(bn_get_words(generator->X), def_xG) &&
  665. is_equal(bn_get_words(generator->Y), def_yG) &&
  666. is_one(generator->Z);
  667. }
  668. __owur static int ecp_nistz256_mult_precompute(EC_GROUP *group, BN_CTX *ctx)
  669. {
  670. /*
  671. * We precompute a table for a Booth encoded exponent (wNAF) based
  672. * computation. Each table holds 64 values for safe access, with an
  673. * implicit value of infinity at index zero. We use window of size 7, and
  674. * therefore require ceil(256/7) = 37 tables.
  675. */
  676. const BIGNUM *order;
  677. EC_POINT *P = NULL, *T = NULL;
  678. const EC_POINT *generator;
  679. NISTZ256_PRE_COMP *pre_comp;
  680. BN_CTX *new_ctx = NULL;
  681. int i, j, k, ret = 0;
  682. size_t w;
  683. PRECOMP256_ROW *preComputedTable = NULL;
  684. unsigned char *precomp_storage = NULL;
  685. /* if there is an old NISTZ256_PRE_COMP object, throw it away */
  686. EC_pre_comp_free(group);
  687. generator = EC_GROUP_get0_generator(group);
  688. if (generator == NULL) {
  689. ERR_raise(ERR_LIB_EC, EC_R_UNDEFINED_GENERATOR);
  690. return 0;
  691. }
  692. if (ecp_nistz256_is_affine_G(generator)) {
  693. /*
  694. * No need to calculate tables for the standard generator because we
  695. * have them statically.
  696. */
  697. return 1;
  698. }
  699. if ((pre_comp = ecp_nistz256_pre_comp_new(group)) == NULL)
  700. return 0;
  701. if (ctx == NULL) {
  702. ctx = new_ctx = BN_CTX_new_ex(group->libctx);
  703. if (ctx == NULL)
  704. goto err;
  705. }
  706. BN_CTX_start(ctx);
  707. order = EC_GROUP_get0_order(group);
  708. if (order == NULL)
  709. goto err;
  710. if (BN_is_zero(order)) {
  711. ERR_raise(ERR_LIB_EC, EC_R_UNKNOWN_ORDER);
  712. goto err;
  713. }
  714. w = 7;
  715. if ((precomp_storage =
  716. OPENSSL_malloc(37 * 64 * sizeof(P256_POINT_AFFINE) + 64)) == NULL)
  717. goto err;
  718. preComputedTable = (void *)ALIGNPTR(precomp_storage, 64);
  719. P = EC_POINT_new(group);
  720. T = EC_POINT_new(group);
  721. if (P == NULL || T == NULL)
  722. goto err;
  723. /*
  724. * The zero entry is implicitly infinity, and we skip it, storing other
  725. * values with -1 offset.
  726. */
  727. if (!EC_POINT_copy(T, generator))
  728. goto err;
  729. for (k = 0; k < 64; k++) {
  730. if (!EC_POINT_copy(P, T))
  731. goto err;
  732. for (j = 0; j < 37; j++) {
  733. P256_POINT_AFFINE temp;
  734. /*
  735. * It would be faster to use EC_POINTs_make_affine and
  736. * make multiple points affine at the same time.
  737. */
  738. if (group->meth->make_affine == NULL
  739. || !group->meth->make_affine(group, P, ctx))
  740. goto err;
  741. if (!ecp_nistz256_bignum_to_field_elem(temp.X, P->X) ||
  742. !ecp_nistz256_bignum_to_field_elem(temp.Y, P->Y)) {
  743. ERR_raise(ERR_LIB_EC, EC_R_COORDINATES_OUT_OF_RANGE);
  744. goto err;
  745. }
  746. ecp_nistz256_scatter_w7(preComputedTable[j], &temp, k);
  747. for (i = 0; i < 7; i++) {
  748. if (!EC_POINT_dbl(group, P, P, ctx))
  749. goto err;
  750. }
  751. }
  752. if (!EC_POINT_add(group, T, T, generator, ctx))
  753. goto err;
  754. }
  755. pre_comp->group = group;
  756. pre_comp->w = w;
  757. pre_comp->precomp = preComputedTable;
  758. pre_comp->precomp_storage = precomp_storage;
  759. precomp_storage = NULL;
  760. SETPRECOMP(group, nistz256, pre_comp);
  761. pre_comp = NULL;
  762. ret = 1;
  763. err:
  764. BN_CTX_end(ctx);
  765. BN_CTX_free(new_ctx);
  766. EC_nistz256_pre_comp_free(pre_comp);
  767. OPENSSL_free(precomp_storage);
  768. EC_POINT_free(P);
  769. EC_POINT_free(T);
  770. return ret;
  771. }
  772. __owur static int ecp_nistz256_set_from_affine(EC_POINT *out, const EC_GROUP *group,
  773. const P256_POINT_AFFINE *in,
  774. BN_CTX *ctx)
  775. {
  776. int ret = 0;
  777. if ((ret = bn_set_words(out->X, in->X, P256_LIMBS))
  778. && (ret = bn_set_words(out->Y, in->Y, P256_LIMBS))
  779. && (ret = bn_set_words(out->Z, ONE, P256_LIMBS)))
  780. out->Z_is_one = 1;
  781. return ret;
  782. }
  783. /* r = scalar*G + sum(scalars[i]*points[i]) */
  784. __owur static int ecp_nistz256_points_mul(const EC_GROUP *group,
  785. EC_POINT *r,
  786. const BIGNUM *scalar,
  787. size_t num,
  788. const EC_POINT *points[],
  789. const BIGNUM *scalars[], BN_CTX *ctx)
  790. {
  791. int i = 0, ret = 0, no_precomp_for_generator = 0, p_is_infinity = 0;
  792. unsigned char p_str[33] = { 0 };
  793. const PRECOMP256_ROW *preComputedTable = NULL;
  794. const NISTZ256_PRE_COMP *pre_comp = NULL;
  795. const EC_POINT *generator = NULL;
  796. const BIGNUM **new_scalars = NULL;
  797. const EC_POINT **new_points = NULL;
  798. unsigned int idx = 0;
  799. const unsigned int window_size = 7;
  800. const unsigned int mask = (1 << (window_size + 1)) - 1;
  801. unsigned int wvalue;
  802. ALIGN32 union {
  803. P256_POINT p;
  804. P256_POINT_AFFINE a;
  805. } t, p;
  806. BIGNUM *tmp_scalar;
  807. if ((num + 1) == 0 || (num + 1) > OPENSSL_MALLOC_MAX_NELEMS(void *)) {
  808. ERR_raise(ERR_LIB_EC, ERR_R_PASSED_INVALID_ARGUMENT);
  809. return 0;
  810. }
  811. memset(&p, 0, sizeof(p));
  812. BN_CTX_start(ctx);
  813. if (scalar) {
  814. generator = EC_GROUP_get0_generator(group);
  815. if (generator == NULL) {
  816. ERR_raise(ERR_LIB_EC, EC_R_UNDEFINED_GENERATOR);
  817. goto err;
  818. }
  819. /* look if we can use precomputed multiples of generator */
  820. pre_comp = group->pre_comp.nistz256;
  821. if (pre_comp) {
  822. /*
  823. * If there is a precomputed table for the generator, check that
  824. * it was generated with the same generator.
  825. */
  826. EC_POINT *pre_comp_generator = EC_POINT_new(group);
  827. if (pre_comp_generator == NULL)
  828. goto err;
  829. ecp_nistz256_gather_w7(&p.a, pre_comp->precomp[0], 1);
  830. if (!ecp_nistz256_set_from_affine(pre_comp_generator,
  831. group, &p.a, ctx)) {
  832. EC_POINT_free(pre_comp_generator);
  833. goto err;
  834. }
  835. if (0 == EC_POINT_cmp(group, generator, pre_comp_generator, ctx))
  836. preComputedTable = (const PRECOMP256_ROW *)pre_comp->precomp;
  837. EC_POINT_free(pre_comp_generator);
  838. }
  839. if (preComputedTable == NULL && ecp_nistz256_is_affine_G(generator)) {
  840. /*
  841. * If there is no precomputed data, but the generator is the
  842. * default, a hardcoded table of precomputed data is used. This
  843. * is because applications, such as Apache, do not use
  844. * EC_KEY_precompute_mult.
  845. */
  846. preComputedTable = ecp_nistz256_precomputed;
  847. }
  848. if (preComputedTable) {
  849. BN_ULONG infty;
  850. if ((BN_num_bits(scalar) > 256)
  851. || BN_is_negative(scalar)) {
  852. if ((tmp_scalar = BN_CTX_get(ctx)) == NULL)
  853. goto err;
  854. if (!BN_nnmod(tmp_scalar, scalar, group->order, ctx)) {
  855. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  856. goto err;
  857. }
  858. scalar = tmp_scalar;
  859. }
  860. for (i = 0; i < bn_get_top(scalar) * BN_BYTES; i += BN_BYTES) {
  861. BN_ULONG d = bn_get_words(scalar)[i / BN_BYTES];
  862. p_str[i + 0] = (unsigned char)d;
  863. p_str[i + 1] = (unsigned char)(d >> 8);
  864. p_str[i + 2] = (unsigned char)(d >> 16);
  865. p_str[i + 3] = (unsigned char)(d >>= 24);
  866. if (BN_BYTES == 8) {
  867. d >>= 8;
  868. p_str[i + 4] = (unsigned char)d;
  869. p_str[i + 5] = (unsigned char)(d >> 8);
  870. p_str[i + 6] = (unsigned char)(d >> 16);
  871. p_str[i + 7] = (unsigned char)(d >> 24);
  872. }
  873. }
  874. for (; i < 33; i++)
  875. p_str[i] = 0;
  876. /* First window */
  877. wvalue = (p_str[0] << 1) & mask;
  878. idx += window_size;
  879. wvalue = _booth_recode_w7(wvalue);
  880. ecp_nistz256_gather_w7(&p.a, preComputedTable[0],
  881. wvalue >> 1);
  882. ecp_nistz256_neg(p.p.Z, p.p.Y);
  883. copy_conditional(p.p.Y, p.p.Z, wvalue & 1);
  884. /*
  885. * Since affine infinity is encoded as (0,0) and
  886. * Jacobian is (,,0), we need to harmonize them
  887. * by assigning "one" or zero to Z.
  888. */
  889. infty = (p.p.X[0] | p.p.X[1] | p.p.X[2] | p.p.X[3] |
  890. p.p.Y[0] | p.p.Y[1] | p.p.Y[2] | p.p.Y[3]);
  891. if (P256_LIMBS == 8)
  892. infty |= (p.p.X[4] | p.p.X[5] | p.p.X[6] | p.p.X[7] |
  893. p.p.Y[4] | p.p.Y[5] | p.p.Y[6] | p.p.Y[7]);
  894. infty = 0 - is_zero(infty);
  895. infty = ~infty;
  896. p.p.Z[0] = ONE[0] & infty;
  897. p.p.Z[1] = ONE[1] & infty;
  898. p.p.Z[2] = ONE[2] & infty;
  899. p.p.Z[3] = ONE[3] & infty;
  900. if (P256_LIMBS == 8) {
  901. p.p.Z[4] = ONE[4] & infty;
  902. p.p.Z[5] = ONE[5] & infty;
  903. p.p.Z[6] = ONE[6] & infty;
  904. p.p.Z[7] = ONE[7] & infty;
  905. }
  906. for (i = 1; i < 37; i++) {
  907. unsigned int off = (idx - 1) / 8;
  908. wvalue = p_str[off] | p_str[off + 1] << 8;
  909. wvalue = (wvalue >> ((idx - 1) % 8)) & mask;
  910. idx += window_size;
  911. wvalue = _booth_recode_w7(wvalue);
  912. ecp_nistz256_gather_w7(&t.a,
  913. preComputedTable[i], wvalue >> 1);
  914. ecp_nistz256_neg(t.p.Z, t.a.Y);
  915. copy_conditional(t.a.Y, t.p.Z, wvalue & 1);
  916. ecp_nistz256_point_add_affine(&p.p, &p.p, &t.a);
  917. }
  918. } else {
  919. p_is_infinity = 1;
  920. no_precomp_for_generator = 1;
  921. }
  922. } else
  923. p_is_infinity = 1;
  924. if (no_precomp_for_generator) {
  925. /*
  926. * Without a precomputed table for the generator, it has to be
  927. * handled like a normal point.
  928. */
  929. new_scalars = OPENSSL_malloc((num + 1) * sizeof(BIGNUM *));
  930. if (new_scalars == NULL)
  931. goto err;
  932. new_points = OPENSSL_malloc((num + 1) * sizeof(EC_POINT *));
  933. if (new_points == NULL)
  934. goto err;
  935. memcpy(new_scalars, scalars, num * sizeof(BIGNUM *));
  936. new_scalars[num] = scalar;
  937. memcpy(new_points, points, num * sizeof(EC_POINT *));
  938. new_points[num] = generator;
  939. scalars = new_scalars;
  940. points = new_points;
  941. num++;
  942. }
  943. if (num) {
  944. P256_POINT *out = &t.p;
  945. if (p_is_infinity)
  946. out = &p.p;
  947. if (!ecp_nistz256_windowed_mul(group, out, scalars, points, num, ctx))
  948. goto err;
  949. if (!p_is_infinity)
  950. ecp_nistz256_point_add(&p.p, &p.p, out);
  951. }
  952. /* Not constant-time, but we're only operating on the public output. */
  953. if (!bn_set_words(r->X, p.p.X, P256_LIMBS) ||
  954. !bn_set_words(r->Y, p.p.Y, P256_LIMBS) ||
  955. !bn_set_words(r->Z, p.p.Z, P256_LIMBS)) {
  956. goto err;
  957. }
  958. r->Z_is_one = is_one(r->Z) & 1;
  959. ret = 1;
  960. err:
  961. BN_CTX_end(ctx);
  962. OPENSSL_free(new_points);
  963. OPENSSL_free(new_scalars);
  964. return ret;
  965. }
  966. __owur static int ecp_nistz256_get_affine(const EC_GROUP *group,
  967. const EC_POINT *point,
  968. BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
  969. {
  970. BN_ULONG z_inv2[P256_LIMBS];
  971. BN_ULONG z_inv3[P256_LIMBS];
  972. BN_ULONG x_aff[P256_LIMBS];
  973. BN_ULONG y_aff[P256_LIMBS];
  974. BN_ULONG point_x[P256_LIMBS], point_y[P256_LIMBS], point_z[P256_LIMBS];
  975. BN_ULONG x_ret[P256_LIMBS], y_ret[P256_LIMBS];
  976. if (EC_POINT_is_at_infinity(group, point)) {
  977. ERR_raise(ERR_LIB_EC, EC_R_POINT_AT_INFINITY);
  978. return 0;
  979. }
  980. if (!ecp_nistz256_bignum_to_field_elem(point_x, point->X) ||
  981. !ecp_nistz256_bignum_to_field_elem(point_y, point->Y) ||
  982. !ecp_nistz256_bignum_to_field_elem(point_z, point->Z)) {
  983. ERR_raise(ERR_LIB_EC, EC_R_COORDINATES_OUT_OF_RANGE);
  984. return 0;
  985. }
  986. ecp_nistz256_mod_inverse(z_inv3, point_z);
  987. ecp_nistz256_sqr_mont(z_inv2, z_inv3);
  988. ecp_nistz256_mul_mont(x_aff, z_inv2, point_x);
  989. if (x != NULL) {
  990. ecp_nistz256_from_mont(x_ret, x_aff);
  991. if (!bn_set_words(x, x_ret, P256_LIMBS))
  992. return 0;
  993. }
  994. if (y != NULL) {
  995. ecp_nistz256_mul_mont(z_inv3, z_inv3, z_inv2);
  996. ecp_nistz256_mul_mont(y_aff, z_inv3, point_y);
  997. ecp_nistz256_from_mont(y_ret, y_aff);
  998. if (!bn_set_words(y, y_ret, P256_LIMBS))
  999. return 0;
  1000. }
  1001. return 1;
  1002. }
  1003. static NISTZ256_PRE_COMP *ecp_nistz256_pre_comp_new(const EC_GROUP *group)
  1004. {
  1005. NISTZ256_PRE_COMP *ret = NULL;
  1006. if (!group)
  1007. return NULL;
  1008. ret = OPENSSL_zalloc(sizeof(*ret));
  1009. if (ret == NULL)
  1010. return ret;
  1011. ret->group = group;
  1012. ret->w = 6; /* default */
  1013. if (!CRYPTO_NEW_REF(&ret->references, 1)) {
  1014. OPENSSL_free(ret);
  1015. return NULL;
  1016. }
  1017. return ret;
  1018. }
  1019. NISTZ256_PRE_COMP *EC_nistz256_pre_comp_dup(NISTZ256_PRE_COMP *p)
  1020. {
  1021. int i;
  1022. if (p != NULL)
  1023. CRYPTO_UP_REF(&p->references, &i);
  1024. return p;
  1025. }
  1026. void EC_nistz256_pre_comp_free(NISTZ256_PRE_COMP *pre)
  1027. {
  1028. int i;
  1029. if (pre == NULL)
  1030. return;
  1031. CRYPTO_DOWN_REF(&pre->references, &i);
  1032. REF_PRINT_COUNT("EC_nistz256", pre);
  1033. if (i > 0)
  1034. return;
  1035. REF_ASSERT_ISNT(i < 0);
  1036. OPENSSL_free(pre->precomp_storage);
  1037. CRYPTO_FREE_REF(&pre->references);
  1038. OPENSSL_free(pre);
  1039. }
  1040. static int ecp_nistz256_window_have_precompute_mult(const EC_GROUP *group)
  1041. {
  1042. /* There is a hard-coded table for the default generator. */
  1043. const EC_POINT *generator = EC_GROUP_get0_generator(group);
  1044. if (generator != NULL && ecp_nistz256_is_affine_G(generator)) {
  1045. /* There is a hard-coded table for the default generator. */
  1046. return 1;
  1047. }
  1048. return HAVEPRECOMP(group, nistz256);
  1049. }
  1050. #if defined(__x86_64) || defined(__x86_64__) || \
  1051. defined(_M_AMD64) || defined(_M_X64) || \
  1052. defined(__powerpc64__) || defined(_ARCH_PP64) || \
  1053. defined(__aarch64__)
  1054. /*
  1055. * Montgomery mul modulo Order(P): res = a*b*2^-256 mod Order(P)
  1056. */
  1057. void ecp_nistz256_ord_mul_mont(BN_ULONG res[P256_LIMBS],
  1058. const BN_ULONG a[P256_LIMBS],
  1059. const BN_ULONG b[P256_LIMBS]);
  1060. void ecp_nistz256_ord_sqr_mont(BN_ULONG res[P256_LIMBS],
  1061. const BN_ULONG a[P256_LIMBS],
  1062. BN_ULONG rep);
  1063. static int ecp_nistz256_inv_mod_ord(const EC_GROUP *group, BIGNUM *r,
  1064. const BIGNUM *x, BN_CTX *ctx)
  1065. {
  1066. /* RR = 2^512 mod ord(p256) */
  1067. static const BN_ULONG RR[P256_LIMBS] = {
  1068. TOBN(0x83244c95,0xbe79eea2), TOBN(0x4699799c,0x49bd6fa6),
  1069. TOBN(0x2845b239,0x2b6bec59), TOBN(0x66e12d94,0xf3d95620)
  1070. };
  1071. /* The constant 1 (unlike ONE that is one in Montgomery representation) */
  1072. static const BN_ULONG one[P256_LIMBS] = {
  1073. TOBN(0,1), TOBN(0,0), TOBN(0,0), TOBN(0,0)
  1074. };
  1075. /*
  1076. * We don't use entry 0 in the table, so we omit it and address
  1077. * with -1 offset.
  1078. */
  1079. BN_ULONG table[15][P256_LIMBS];
  1080. BN_ULONG out[P256_LIMBS], t[P256_LIMBS];
  1081. int i, ret = 0;
  1082. enum {
  1083. i_1 = 0, i_10, i_11, i_101, i_111, i_1010, i_1111,
  1084. i_10101, i_101010, i_101111, i_x6, i_x8, i_x16, i_x32
  1085. };
  1086. /*
  1087. * Catch allocation failure early.
  1088. */
  1089. if (bn_wexpand(r, P256_LIMBS) == NULL) {
  1090. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  1091. goto err;
  1092. }
  1093. if ((BN_num_bits(x) > 256) || BN_is_negative(x)) {
  1094. BIGNUM *tmp;
  1095. if ((tmp = BN_CTX_get(ctx)) == NULL
  1096. || !BN_nnmod(tmp, x, group->order, ctx)) {
  1097. ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
  1098. goto err;
  1099. }
  1100. x = tmp;
  1101. }
  1102. if (!ecp_nistz256_bignum_to_field_elem(t, x)) {
  1103. ERR_raise(ERR_LIB_EC, EC_R_COORDINATES_OUT_OF_RANGE);
  1104. goto err;
  1105. }
  1106. ecp_nistz256_ord_mul_mont(table[0], t, RR);
  1107. #if 0
  1108. /*
  1109. * Original sparse-then-fixed-window algorithm, retained for reference.
  1110. */
  1111. for (i = 2; i < 16; i += 2) {
  1112. ecp_nistz256_ord_sqr_mont(table[i-1], table[i/2-1], 1);
  1113. ecp_nistz256_ord_mul_mont(table[i], table[i-1], table[0]);
  1114. }
  1115. /*
  1116. * The top 128bit of the exponent are highly redudndant, so we
  1117. * perform an optimized flow
  1118. */
  1119. ecp_nistz256_ord_sqr_mont(t, table[15-1], 4); /* f0 */
  1120. ecp_nistz256_ord_mul_mont(t, t, table[15-1]); /* ff */
  1121. ecp_nistz256_ord_sqr_mont(out, t, 8); /* ff00 */
  1122. ecp_nistz256_ord_mul_mont(out, out, t); /* ffff */
  1123. ecp_nistz256_ord_sqr_mont(t, out, 16); /* ffff0000 */
  1124. ecp_nistz256_ord_mul_mont(t, t, out); /* ffffffff */
  1125. ecp_nistz256_ord_sqr_mont(out, t, 64); /* ffffffff0000000000000000 */
  1126. ecp_nistz256_ord_mul_mont(out, out, t); /* ffffffff00000000ffffffff */
  1127. ecp_nistz256_ord_sqr_mont(out, out, 32); /* ffffffff00000000ffffffff00000000 */
  1128. ecp_nistz256_ord_mul_mont(out, out, t); /* ffffffff00000000ffffffffffffffff */
  1129. /*
  1130. * The bottom 128 bit of the exponent are processed with fixed 4-bit window
  1131. */
  1132. for (i = 0; i < 32; i++) {
  1133. /* expLo - the low 128 bits of the exponent we use (ord(p256) - 2),
  1134. * split into nibbles */
  1135. static const unsigned char expLo[32] = {
  1136. 0xb,0xc,0xe,0x6,0xf,0xa,0xa,0xd,0xa,0x7,0x1,0x7,0x9,0xe,0x8,0x4,
  1137. 0xf,0x3,0xb,0x9,0xc,0xa,0xc,0x2,0xf,0xc,0x6,0x3,0x2,0x5,0x4,0xf
  1138. };
  1139. ecp_nistz256_ord_sqr_mont(out, out, 4);
  1140. /* The exponent is public, no need in constant-time access */
  1141. ecp_nistz256_ord_mul_mont(out, out, table[expLo[i]-1]);
  1142. }
  1143. #else
  1144. /*
  1145. * https://briansmith.org/ecc-inversion-addition-chains-01#p256_scalar_inversion
  1146. *
  1147. * Even though this code path spares 12 squarings, 4.5%, and 13
  1148. * multiplications, 25%, on grand scale sign operation is not that
  1149. * much faster, not more that 2%...
  1150. */
  1151. /* pre-calculate powers */
  1152. ecp_nistz256_ord_sqr_mont(table[i_10], table[i_1], 1);
  1153. ecp_nistz256_ord_mul_mont(table[i_11], table[i_1], table[i_10]);
  1154. ecp_nistz256_ord_mul_mont(table[i_101], table[i_11], table[i_10]);
  1155. ecp_nistz256_ord_mul_mont(table[i_111], table[i_101], table[i_10]);
  1156. ecp_nistz256_ord_sqr_mont(table[i_1010], table[i_101], 1);
  1157. ecp_nistz256_ord_mul_mont(table[i_1111], table[i_1010], table[i_101]);
  1158. ecp_nistz256_ord_sqr_mont(table[i_10101], table[i_1010], 1);
  1159. ecp_nistz256_ord_mul_mont(table[i_10101], table[i_10101], table[i_1]);
  1160. ecp_nistz256_ord_sqr_mont(table[i_101010], table[i_10101], 1);
  1161. ecp_nistz256_ord_mul_mont(table[i_101111], table[i_101010], table[i_101]);
  1162. ecp_nistz256_ord_mul_mont(table[i_x6], table[i_101010], table[i_10101]);
  1163. ecp_nistz256_ord_sqr_mont(table[i_x8], table[i_x6], 2);
  1164. ecp_nistz256_ord_mul_mont(table[i_x8], table[i_x8], table[i_11]);
  1165. ecp_nistz256_ord_sqr_mont(table[i_x16], table[i_x8], 8);
  1166. ecp_nistz256_ord_mul_mont(table[i_x16], table[i_x16], table[i_x8]);
  1167. ecp_nistz256_ord_sqr_mont(table[i_x32], table[i_x16], 16);
  1168. ecp_nistz256_ord_mul_mont(table[i_x32], table[i_x32], table[i_x16]);
  1169. /* calculations */
  1170. ecp_nistz256_ord_sqr_mont(out, table[i_x32], 64);
  1171. ecp_nistz256_ord_mul_mont(out, out, table[i_x32]);
  1172. for (i = 0; i < 27; i++) {
  1173. static const struct { unsigned char p, i; } chain[27] = {
  1174. { 32, i_x32 }, { 6, i_101111 }, { 5, i_111 },
  1175. { 4, i_11 }, { 5, i_1111 }, { 5, i_10101 },
  1176. { 4, i_101 }, { 3, i_101 }, { 3, i_101 },
  1177. { 5, i_111 }, { 9, i_101111 }, { 6, i_1111 },
  1178. { 2, i_1 }, { 5, i_1 }, { 6, i_1111 },
  1179. { 5, i_111 }, { 4, i_111 }, { 5, i_111 },
  1180. { 5, i_101 }, { 3, i_11 }, { 10, i_101111 },
  1181. { 2, i_11 }, { 5, i_11 }, { 5, i_11 },
  1182. { 3, i_1 }, { 7, i_10101 }, { 6, i_1111 }
  1183. };
  1184. ecp_nistz256_ord_sqr_mont(out, out, chain[i].p);
  1185. ecp_nistz256_ord_mul_mont(out, out, table[chain[i].i]);
  1186. }
  1187. #endif
  1188. ecp_nistz256_ord_mul_mont(out, out, one);
  1189. /*
  1190. * Can't fail, but check return code to be consistent anyway.
  1191. */
  1192. if (!bn_set_words(r, out, P256_LIMBS))
  1193. goto err;
  1194. ret = 1;
  1195. err:
  1196. return ret;
  1197. }
  1198. #else
  1199. # define ecp_nistz256_inv_mod_ord NULL
  1200. #endif
  1201. const EC_METHOD *EC_GFp_nistz256_method(void)
  1202. {
  1203. static const EC_METHOD ret = {
  1204. EC_FLAGS_DEFAULT_OCT,
  1205. NID_X9_62_prime_field,
  1206. ossl_ec_GFp_mont_group_init,
  1207. ossl_ec_GFp_mont_group_finish,
  1208. ossl_ec_GFp_mont_group_clear_finish,
  1209. ossl_ec_GFp_mont_group_copy,
  1210. ossl_ec_GFp_mont_group_set_curve,
  1211. ossl_ec_GFp_simple_group_get_curve,
  1212. ossl_ec_GFp_simple_group_get_degree,
  1213. ossl_ec_group_simple_order_bits,
  1214. ossl_ec_GFp_simple_group_check_discriminant,
  1215. ossl_ec_GFp_simple_point_init,
  1216. ossl_ec_GFp_simple_point_finish,
  1217. ossl_ec_GFp_simple_point_clear_finish,
  1218. ossl_ec_GFp_simple_point_copy,
  1219. ossl_ec_GFp_simple_point_set_to_infinity,
  1220. ossl_ec_GFp_simple_point_set_affine_coordinates,
  1221. ecp_nistz256_get_affine,
  1222. 0, 0, 0,
  1223. ossl_ec_GFp_simple_add,
  1224. ossl_ec_GFp_simple_dbl,
  1225. ossl_ec_GFp_simple_invert,
  1226. ossl_ec_GFp_simple_is_at_infinity,
  1227. ossl_ec_GFp_simple_is_on_curve,
  1228. ossl_ec_GFp_simple_cmp,
  1229. ossl_ec_GFp_simple_make_affine,
  1230. ossl_ec_GFp_simple_points_make_affine,
  1231. ecp_nistz256_points_mul, /* mul */
  1232. ecp_nistz256_mult_precompute, /* precompute_mult */
  1233. ecp_nistz256_window_have_precompute_mult, /* have_precompute_mult */
  1234. ossl_ec_GFp_mont_field_mul,
  1235. ossl_ec_GFp_mont_field_sqr,
  1236. 0, /* field_div */
  1237. ossl_ec_GFp_mont_field_inv,
  1238. ossl_ec_GFp_mont_field_encode,
  1239. ossl_ec_GFp_mont_field_decode,
  1240. ossl_ec_GFp_mont_field_set_to_one,
  1241. ossl_ec_key_simple_priv2oct,
  1242. ossl_ec_key_simple_oct2priv,
  1243. 0, /* set private */
  1244. ossl_ec_key_simple_generate_key,
  1245. ossl_ec_key_simple_check_key,
  1246. ossl_ec_key_simple_generate_public_key,
  1247. 0, /* keycopy */
  1248. 0, /* keyfinish */
  1249. ossl_ecdh_simple_compute_key,
  1250. ossl_ecdsa_simple_sign_setup,
  1251. ossl_ecdsa_simple_sign_sig,
  1252. ossl_ecdsa_simple_verify_sig,
  1253. ecp_nistz256_inv_mod_ord, /* can be #define-d NULL */
  1254. 0, /* blind_coordinates */
  1255. 0, /* ladder_pre */
  1256. 0, /* ladder_step */
  1257. 0 /* ladder_post */
  1258. };
  1259. return &ret;
  1260. }