ecp_nistz256.c 51 KB

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