bn_gf2m.c 27 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029
  1. /* crypto/bn/bn_gf2m.c */
  2. /* ====================================================================
  3. * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  4. *
  5. * The Elliptic Curve Public-Key Crypto Library (ECC Code) included
  6. * herein is developed by SUN MICROSYSTEMS, INC., and is contributed
  7. * to the OpenSSL project.
  8. *
  9. * The ECC Code is licensed pursuant to the OpenSSL open source
  10. * license provided below.
  11. *
  12. * In addition, Sun covenants to all licensees who provide a reciprocal
  13. * covenant with respect to their own patents if any, not to sue under
  14. * current and future patent claims necessarily infringed by the making,
  15. * using, practicing, selling, offering for sale and/or otherwise
  16. * disposing of the ECC Code as delivered hereunder (or portions thereof),
  17. * provided that such covenant shall not apply:
  18. * 1) for code that a licensee deletes from the ECC Code;
  19. * 2) separates from the ECC Code; or
  20. * 3) for infringements caused by:
  21. * i) the modification of the ECC Code or
  22. * ii) the combination of the ECC Code with other software or
  23. * devices where such combination causes the infringement.
  24. *
  25. * The software is originally written by Sheueling Chang Shantz and
  26. * Douglas Stebila of Sun Microsystems Laboratories.
  27. *
  28. */
  29. /* NOTE: This file is licensed pursuant to the OpenSSL license below
  30. * and may be modified; but after modifications, the above covenant
  31. * may no longer apply! In such cases, the corresponding paragraph
  32. * ["In addition, Sun covenants ... causes the infringement."] and
  33. * this note can be edited out; but please keep the Sun copyright
  34. * notice and attribution. */
  35. /* ====================================================================
  36. * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved.
  37. *
  38. * Redistribution and use in source and binary forms, with or without
  39. * modification, are permitted provided that the following conditions
  40. * are met:
  41. *
  42. * 1. Redistributions of source code must retain the above copyright
  43. * notice, this list of conditions and the following disclaimer.
  44. *
  45. * 2. Redistributions in binary form must reproduce the above copyright
  46. * notice, this list of conditions and the following disclaimer in
  47. * the documentation and/or other materials provided with the
  48. * distribution.
  49. *
  50. * 3. All advertising materials mentioning features or use of this
  51. * software must display the following acknowledgment:
  52. * "This product includes software developed by the OpenSSL Project
  53. * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  54. *
  55. * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  56. * endorse or promote products derived from this software without
  57. * prior written permission. For written permission, please contact
  58. * openssl-core@openssl.org.
  59. *
  60. * 5. Products derived from this software may not be called "OpenSSL"
  61. * nor may "OpenSSL" appear in their names without prior written
  62. * permission of the OpenSSL Project.
  63. *
  64. * 6. Redistributions of any form whatsoever must retain the following
  65. * acknowledgment:
  66. * "This product includes software developed by the OpenSSL Project
  67. * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  68. *
  69. * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  70. * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  71. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  72. * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
  73. * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  74. * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  75. * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  76. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  77. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  78. * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  79. * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  80. * OF THE POSSIBILITY OF SUCH DAMAGE.
  81. * ====================================================================
  82. *
  83. * This product includes cryptographic software written by Eric Young
  84. * (eay@cryptsoft.com). This product includes software written by Tim
  85. * Hudson (tjh@cryptsoft.com).
  86. *
  87. */
  88. #include <assert.h>
  89. #include <limits.h>
  90. #include <stdio.h>
  91. #include "cryptlib.h"
  92. #include "bn_lcl.h"
  93. /* Maximum number of iterations before BN_GF2m_mod_solve_quad_arr should fail. */
  94. #define MAX_ITERATIONS 50
  95. static const BN_ULONG SQR_tb[16] =
  96. { 0, 1, 4, 5, 16, 17, 20, 21,
  97. 64, 65, 68, 69, 80, 81, 84, 85 };
  98. /* Platform-specific macros to accelerate squaring. */
  99. #if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
  100. #define SQR1(w) \
  101. SQR_tb[(w) >> 60 & 0xF] << 56 | SQR_tb[(w) >> 56 & 0xF] << 48 | \
  102. SQR_tb[(w) >> 52 & 0xF] << 40 | SQR_tb[(w) >> 48 & 0xF] << 32 | \
  103. SQR_tb[(w) >> 44 & 0xF] << 24 | SQR_tb[(w) >> 40 & 0xF] << 16 | \
  104. SQR_tb[(w) >> 36 & 0xF] << 8 | SQR_tb[(w) >> 32 & 0xF]
  105. #define SQR0(w) \
  106. SQR_tb[(w) >> 28 & 0xF] << 56 | SQR_tb[(w) >> 24 & 0xF] << 48 | \
  107. SQR_tb[(w) >> 20 & 0xF] << 40 | SQR_tb[(w) >> 16 & 0xF] << 32 | \
  108. SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >> 8 & 0xF] << 16 | \
  109. SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF]
  110. #endif
  111. #ifdef THIRTY_TWO_BIT
  112. #define SQR1(w) \
  113. SQR_tb[(w) >> 28 & 0xF] << 24 | SQR_tb[(w) >> 24 & 0xF] << 16 | \
  114. SQR_tb[(w) >> 20 & 0xF] << 8 | SQR_tb[(w) >> 16 & 0xF]
  115. #define SQR0(w) \
  116. SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >> 8 & 0xF] << 16 | \
  117. SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF]
  118. #endif
  119. /* Product of two polynomials a, b each with degree < BN_BITS2 - 1,
  120. * result is a polynomial r with degree < 2 * BN_BITS - 1
  121. * The caller MUST ensure that the variables have the right amount
  122. * of space allocated.
  123. */
  124. #ifdef THIRTY_TWO_BIT
  125. static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, const BN_ULONG b)
  126. {
  127. register BN_ULONG h, l, s;
  128. BN_ULONG tab[8], top2b = a >> 30;
  129. register BN_ULONG a1, a2, a4;
  130. a1 = a & (0x3FFFFFFF); a2 = a1 << 1; a4 = a2 << 1;
  131. tab[0] = 0; tab[1] = a1; tab[2] = a2; tab[3] = a1^a2;
  132. tab[4] = a4; tab[5] = a1^a4; tab[6] = a2^a4; tab[7] = a1^a2^a4;
  133. s = tab[b & 0x7]; l = s;
  134. s = tab[b >> 3 & 0x7]; l ^= s << 3; h = s >> 29;
  135. s = tab[b >> 6 & 0x7]; l ^= s << 6; h ^= s >> 26;
  136. s = tab[b >> 9 & 0x7]; l ^= s << 9; h ^= s >> 23;
  137. s = tab[b >> 12 & 0x7]; l ^= s << 12; h ^= s >> 20;
  138. s = tab[b >> 15 & 0x7]; l ^= s << 15; h ^= s >> 17;
  139. s = tab[b >> 18 & 0x7]; l ^= s << 18; h ^= s >> 14;
  140. s = tab[b >> 21 & 0x7]; l ^= s << 21; h ^= s >> 11;
  141. s = tab[b >> 24 & 0x7]; l ^= s << 24; h ^= s >> 8;
  142. s = tab[b >> 27 & 0x7]; l ^= s << 27; h ^= s >> 5;
  143. s = tab[b >> 30 ]; l ^= s << 30; h ^= s >> 2;
  144. /* compensate for the top two bits of a */
  145. if (top2b & 01) { l ^= b << 30; h ^= b >> 2; }
  146. if (top2b & 02) { l ^= b << 31; h ^= b >> 1; }
  147. *r1 = h; *r0 = l;
  148. }
  149. #endif
  150. #if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
  151. static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, const BN_ULONG b)
  152. {
  153. register BN_ULONG h, l, s;
  154. BN_ULONG tab[16], top3b = a >> 61;
  155. register BN_ULONG a1, a2, a4, a8;
  156. a1 = a & (0x1FFFFFFFFFFFFFFFULL); a2 = a1 << 1; a4 = a2 << 1; a8 = a4 << 1;
  157. tab[ 0] = 0; tab[ 1] = a1; tab[ 2] = a2; tab[ 3] = a1^a2;
  158. tab[ 4] = a4; tab[ 5] = a1^a4; tab[ 6] = a2^a4; tab[ 7] = a1^a2^a4;
  159. tab[ 8] = a8; tab[ 9] = a1^a8; tab[10] = a2^a8; tab[11] = a1^a2^a8;
  160. tab[12] = a4^a8; tab[13] = a1^a4^a8; tab[14] = a2^a4^a8; tab[15] = a1^a2^a4^a8;
  161. s = tab[b & 0xF]; l = s;
  162. s = tab[b >> 4 & 0xF]; l ^= s << 4; h = s >> 60;
  163. s = tab[b >> 8 & 0xF]; l ^= s << 8; h ^= s >> 56;
  164. s = tab[b >> 12 & 0xF]; l ^= s << 12; h ^= s >> 52;
  165. s = tab[b >> 16 & 0xF]; l ^= s << 16; h ^= s >> 48;
  166. s = tab[b >> 20 & 0xF]; l ^= s << 20; h ^= s >> 44;
  167. s = tab[b >> 24 & 0xF]; l ^= s << 24; h ^= s >> 40;
  168. s = tab[b >> 28 & 0xF]; l ^= s << 28; h ^= s >> 36;
  169. s = tab[b >> 32 & 0xF]; l ^= s << 32; h ^= s >> 32;
  170. s = tab[b >> 36 & 0xF]; l ^= s << 36; h ^= s >> 28;
  171. s = tab[b >> 40 & 0xF]; l ^= s << 40; h ^= s >> 24;
  172. s = tab[b >> 44 & 0xF]; l ^= s << 44; h ^= s >> 20;
  173. s = tab[b >> 48 & 0xF]; l ^= s << 48; h ^= s >> 16;
  174. s = tab[b >> 52 & 0xF]; l ^= s << 52; h ^= s >> 12;
  175. s = tab[b >> 56 & 0xF]; l ^= s << 56; h ^= s >> 8;
  176. s = tab[b >> 60 ]; l ^= s << 60; h ^= s >> 4;
  177. /* compensate for the top three bits of a */
  178. if (top3b & 01) { l ^= b << 61; h ^= b >> 3; }
  179. if (top3b & 02) { l ^= b << 62; h ^= b >> 2; }
  180. if (top3b & 04) { l ^= b << 63; h ^= b >> 1; }
  181. *r1 = h; *r0 = l;
  182. }
  183. #endif
  184. /* Product of two polynomials a, b each with degree < 2 * BN_BITS2 - 1,
  185. * result is a polynomial r with degree < 4 * BN_BITS2 - 1
  186. * The caller MUST ensure that the variables have the right amount
  187. * of space allocated.
  188. */
  189. static void bn_GF2m_mul_2x2(BN_ULONG *r, const BN_ULONG a1, const BN_ULONG a0, const BN_ULONG b1, const BN_ULONG b0)
  190. {
  191. BN_ULONG m1, m0;
  192. /* r[3] = h1, r[2] = h0; r[1] = l1; r[0] = l0 */
  193. bn_GF2m_mul_1x1(r+3, r+2, a1, b1);
  194. bn_GF2m_mul_1x1(r+1, r, a0, b0);
  195. bn_GF2m_mul_1x1(&m1, &m0, a0 ^ a1, b0 ^ b1);
  196. /* Correction on m1 ^= l1 ^ h1; m0 ^= l0 ^ h0; */
  197. r[2] ^= m1 ^ r[1] ^ r[3]; /* h0 ^= m1 ^ l1 ^ h1; */
  198. r[1] = r[3] ^ r[2] ^ r[0] ^ m1 ^ m0; /* l1 ^= l0 ^ h0 ^ m0; */
  199. }
  200. /* Add polynomials a and b and store result in r; r could be a or b, a and b
  201. * could be equal; r is the bitwise XOR of a and b.
  202. */
  203. int BN_GF2m_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  204. {
  205. int i;
  206. const BIGNUM *at, *bt;
  207. bn_check_top(a);
  208. bn_check_top(b);
  209. if (a->top < b->top) { at = b; bt = a; }
  210. else { at = a; bt = b; }
  211. bn_wexpand(r, at->top);
  212. for (i = 0; i < bt->top; i++)
  213. {
  214. r->d[i] = at->d[i] ^ bt->d[i];
  215. }
  216. for (; i < at->top; i++)
  217. {
  218. r->d[i] = at->d[i];
  219. }
  220. r->top = at->top;
  221. bn_correct_top(r);
  222. return 1;
  223. }
  224. /* Some functions allow for representation of the irreducible polynomials
  225. * as an int[], say p. The irreducible f(t) is then of the form:
  226. * t^p[0] + t^p[1] + ... + t^p[k]
  227. * where m = p[0] > p[1] > ... > p[k] = 0.
  228. */
  229. /* Performs modular reduction of a and store result in r. r could be a. */
  230. int BN_GF2m_mod_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[])
  231. {
  232. int j, k;
  233. int n, dN, d0, d1;
  234. BN_ULONG zz, *z;
  235. bn_check_top(a);
  236. if (!p[0])
  237. {
  238. /* reduction mod 1 => return 0 */
  239. BN_zero(r);
  240. return 1;
  241. }
  242. /* Since the algorithm does reduction in the r value, if a != r, copy
  243. * the contents of a into r so we can do reduction in r.
  244. */
  245. if (a != r)
  246. {
  247. if (!bn_wexpand(r, a->top)) return 0;
  248. for (j = 0; j < a->top; j++)
  249. {
  250. r->d[j] = a->d[j];
  251. }
  252. r->top = a->top;
  253. }
  254. z = r->d;
  255. /* start reduction */
  256. dN = p[0] / BN_BITS2;
  257. for (j = r->top - 1; j > dN;)
  258. {
  259. zz = z[j];
  260. if (z[j] == 0) { j--; continue; }
  261. z[j] = 0;
  262. for (k = 1; p[k] != 0; k++)
  263. {
  264. /* reducing component t^p[k] */
  265. n = p[0] - p[k];
  266. d0 = n % BN_BITS2; d1 = BN_BITS2 - d0;
  267. n /= BN_BITS2;
  268. z[j-n] ^= (zz>>d0);
  269. if (d0) z[j-n-1] ^= (zz<<d1);
  270. }
  271. /* reducing component t^0 */
  272. n = dN;
  273. d0 = p[0] % BN_BITS2;
  274. d1 = BN_BITS2 - d0;
  275. z[j-n] ^= (zz >> d0);
  276. if (d0) z[j-n-1] ^= (zz << d1);
  277. }
  278. /* final round of reduction */
  279. while (j == dN)
  280. {
  281. d0 = p[0] % BN_BITS2;
  282. zz = z[dN] >> d0;
  283. if (zz == 0) break;
  284. d1 = BN_BITS2 - d0;
  285. if (d0) z[dN] = (z[dN] << d1) >> d1; /* clear up the top d1 bits */
  286. z[0] ^= zz; /* reduction t^0 component */
  287. for (k = 1; p[k] != 0; k++)
  288. {
  289. BN_ULONG tmp_ulong;
  290. /* reducing component t^p[k]*/
  291. n = p[k] / BN_BITS2;
  292. d0 = p[k] % BN_BITS2;
  293. d1 = BN_BITS2 - d0;
  294. z[n] ^= (zz << d0);
  295. tmp_ulong = zz >> d1;
  296. if (d0 && tmp_ulong)
  297. z[n+1] ^= tmp_ulong;
  298. }
  299. }
  300. bn_correct_top(r);
  301. return 1;
  302. }
  303. /* Performs modular reduction of a by p and store result in r. r could be a.
  304. *
  305. * This function calls down to the BN_GF2m_mod_arr implementation; this wrapper
  306. * function is only provided for convenience; for best performance, use the
  307. * BN_GF2m_mod_arr function.
  308. */
  309. int BN_GF2m_mod(BIGNUM *r, const BIGNUM *a, const BIGNUM *p)
  310. {
  311. int ret = 0;
  312. const int max = BN_num_bits(p);
  313. unsigned int *arr=NULL;
  314. bn_check_top(a);
  315. bn_check_top(p);
  316. if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
  317. ret = BN_GF2m_poly2arr(p, arr, max);
  318. if (!ret || ret > max)
  319. {
  320. BNerr(BN_F_BN_GF2M_MOD,BN_R_INVALID_LENGTH);
  321. goto err;
  322. }
  323. ret = BN_GF2m_mod_arr(r, a, arr);
  324. bn_check_top(r);
  325. err:
  326. if (arr) OPENSSL_free(arr);
  327. return ret;
  328. }
  329. /* Compute the product of two polynomials a and b, reduce modulo p, and store
  330. * the result in r. r could be a or b; a could be b.
  331. */
  332. int BN_GF2m_mod_mul_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const unsigned int p[], BN_CTX *ctx)
  333. {
  334. int zlen, i, j, k, ret = 0;
  335. BIGNUM *s;
  336. BN_ULONG x1, x0, y1, y0, zz[4];
  337. bn_check_top(a);
  338. bn_check_top(b);
  339. if (a == b)
  340. {
  341. return BN_GF2m_mod_sqr_arr(r, a, p, ctx);
  342. }
  343. BN_CTX_start(ctx);
  344. if ((s = BN_CTX_get(ctx)) == NULL) goto err;
  345. zlen = a->top + b->top + 4;
  346. if (!bn_wexpand(s, zlen)) goto err;
  347. s->top = zlen;
  348. for (i = 0; i < zlen; i++) s->d[i] = 0;
  349. for (j = 0; j < b->top; j += 2)
  350. {
  351. y0 = b->d[j];
  352. y1 = ((j+1) == b->top) ? 0 : b->d[j+1];
  353. for (i = 0; i < a->top; i += 2)
  354. {
  355. x0 = a->d[i];
  356. x1 = ((i+1) == a->top) ? 0 : a->d[i+1];
  357. bn_GF2m_mul_2x2(zz, x1, x0, y1, y0);
  358. for (k = 0; k < 4; k++) s->d[i+j+k] ^= zz[k];
  359. }
  360. }
  361. bn_correct_top(s);
  362. if (BN_GF2m_mod_arr(r, s, p))
  363. ret = 1;
  364. bn_check_top(r);
  365. err:
  366. BN_CTX_end(ctx);
  367. return ret;
  368. }
  369. /* Compute the product of two polynomials a and b, reduce modulo p, and store
  370. * the result in r. r could be a or b; a could equal b.
  371. *
  372. * This function calls down to the BN_GF2m_mod_mul_arr implementation; this wrapper
  373. * function is only provided for convenience; for best performance, use the
  374. * BN_GF2m_mod_mul_arr function.
  375. */
  376. int BN_GF2m_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx)
  377. {
  378. int ret = 0;
  379. const int max = BN_num_bits(p);
  380. unsigned int *arr=NULL;
  381. bn_check_top(a);
  382. bn_check_top(b);
  383. bn_check_top(p);
  384. if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
  385. ret = BN_GF2m_poly2arr(p, arr, max);
  386. if (!ret || ret > max)
  387. {
  388. BNerr(BN_F_BN_GF2M_MOD_MUL,BN_R_INVALID_LENGTH);
  389. goto err;
  390. }
  391. ret = BN_GF2m_mod_mul_arr(r, a, b, arr, ctx);
  392. bn_check_top(r);
  393. err:
  394. if (arr) OPENSSL_free(arr);
  395. return ret;
  396. }
  397. /* Square a, reduce the result mod p, and store it in a. r could be a. */
  398. int BN_GF2m_mod_sqr_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[], BN_CTX *ctx)
  399. {
  400. int i, ret = 0;
  401. BIGNUM *s;
  402. bn_check_top(a);
  403. BN_CTX_start(ctx);
  404. if ((s = BN_CTX_get(ctx)) == NULL) return 0;
  405. if (!bn_wexpand(s, 2 * a->top)) goto err;
  406. for (i = a->top - 1; i >= 0; i--)
  407. {
  408. s->d[2*i+1] = SQR1(a->d[i]);
  409. s->d[2*i ] = SQR0(a->d[i]);
  410. }
  411. s->top = 2 * a->top;
  412. bn_correct_top(s);
  413. if (!BN_GF2m_mod_arr(r, s, p)) goto err;
  414. bn_check_top(r);
  415. ret = 1;
  416. err:
  417. BN_CTX_end(ctx);
  418. return ret;
  419. }
  420. /* Square a, reduce the result mod p, and store it in a. r could be a.
  421. *
  422. * This function calls down to the BN_GF2m_mod_sqr_arr implementation; this wrapper
  423. * function is only provided for convenience; for best performance, use the
  424. * BN_GF2m_mod_sqr_arr function.
  425. */
  426. int BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
  427. {
  428. int ret = 0;
  429. const int max = BN_num_bits(p);
  430. unsigned int *arr=NULL;
  431. bn_check_top(a);
  432. bn_check_top(p);
  433. if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
  434. ret = BN_GF2m_poly2arr(p, arr, max);
  435. if (!ret || ret > max)
  436. {
  437. BNerr(BN_F_BN_GF2M_MOD_SQR,BN_R_INVALID_LENGTH);
  438. goto err;
  439. }
  440. ret = BN_GF2m_mod_sqr_arr(r, a, arr, ctx);
  441. bn_check_top(r);
  442. err:
  443. if (arr) OPENSSL_free(arr);
  444. return ret;
  445. }
  446. /* Invert a, reduce modulo p, and store the result in r. r could be a.
  447. * Uses Modified Almost Inverse Algorithm (Algorithm 10) from
  448. * Hankerson, D., Hernandez, J.L., and Menezes, A. "Software Implementation
  449. * of Elliptic Curve Cryptography Over Binary Fields".
  450. */
  451. int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
  452. {
  453. BIGNUM *b, *c, *u, *v, *tmp;
  454. int ret = 0;
  455. bn_check_top(a);
  456. bn_check_top(p);
  457. BN_CTX_start(ctx);
  458. b = BN_CTX_get(ctx);
  459. c = BN_CTX_get(ctx);
  460. u = BN_CTX_get(ctx);
  461. v = BN_CTX_get(ctx);
  462. if (v == NULL) goto err;
  463. if (!BN_one(b)) goto err;
  464. if (!BN_GF2m_mod(u, a, p)) goto err;
  465. if (!BN_copy(v, p)) goto err;
  466. if (BN_is_zero(u)) goto err;
  467. while (1)
  468. {
  469. while (!BN_is_odd(u))
  470. {
  471. if (!BN_rshift1(u, u)) goto err;
  472. if (BN_is_odd(b))
  473. {
  474. if (!BN_GF2m_add(b, b, p)) goto err;
  475. }
  476. if (!BN_rshift1(b, b)) goto err;
  477. }
  478. if (BN_abs_is_word(u, 1)) break;
  479. if (BN_num_bits(u) < BN_num_bits(v))
  480. {
  481. tmp = u; u = v; v = tmp;
  482. tmp = b; b = c; c = tmp;
  483. }
  484. if (!BN_GF2m_add(u, u, v)) goto err;
  485. if (!BN_GF2m_add(b, b, c)) goto err;
  486. }
  487. if (!BN_copy(r, b)) goto err;
  488. bn_check_top(r);
  489. ret = 1;
  490. err:
  491. BN_CTX_end(ctx);
  492. return ret;
  493. }
  494. /* Invert xx, reduce modulo p, and store the result in r. r could be xx.
  495. *
  496. * This function calls down to the BN_GF2m_mod_inv implementation; this wrapper
  497. * function is only provided for convenience; for best performance, use the
  498. * BN_GF2m_mod_inv function.
  499. */
  500. int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const unsigned int p[], BN_CTX *ctx)
  501. {
  502. BIGNUM *field;
  503. int ret = 0;
  504. bn_check_top(xx);
  505. BN_CTX_start(ctx);
  506. if ((field = BN_CTX_get(ctx)) == NULL) goto err;
  507. if (!BN_GF2m_arr2poly(p, field)) goto err;
  508. ret = BN_GF2m_mod_inv(r, xx, field, ctx);
  509. bn_check_top(r);
  510. err:
  511. BN_CTX_end(ctx);
  512. return ret;
  513. }
  514. #ifndef OPENSSL_SUN_GF2M_DIV
  515. /* Divide y by x, reduce modulo p, and store the result in r. r could be x
  516. * or y, x could equal y.
  517. */
  518. int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, const BIGNUM *p, BN_CTX *ctx)
  519. {
  520. BIGNUM *xinv = NULL;
  521. int ret = 0;
  522. bn_check_top(y);
  523. bn_check_top(x);
  524. bn_check_top(p);
  525. BN_CTX_start(ctx);
  526. xinv = BN_CTX_get(ctx);
  527. if (xinv == NULL) goto err;
  528. if (!BN_GF2m_mod_inv(xinv, x, p, ctx)) goto err;
  529. if (!BN_GF2m_mod_mul(r, y, xinv, p, ctx)) goto err;
  530. bn_check_top(r);
  531. ret = 1;
  532. err:
  533. BN_CTX_end(ctx);
  534. return ret;
  535. }
  536. #else
  537. /* Divide y by x, reduce modulo p, and store the result in r. r could be x
  538. * or y, x could equal y.
  539. * Uses algorithm Modular_Division_GF(2^m) from
  540. * Chang-Shantz, S. "From Euclid's GCD to Montgomery Multiplication to
  541. * the Great Divide".
  542. */
  543. int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, const BIGNUM *p, BN_CTX *ctx)
  544. {
  545. BIGNUM *a, *b, *u, *v;
  546. int ret = 0;
  547. bn_check_top(y);
  548. bn_check_top(x);
  549. bn_check_top(p);
  550. BN_CTX_start(ctx);
  551. a = BN_CTX_get(ctx);
  552. b = BN_CTX_get(ctx);
  553. u = BN_CTX_get(ctx);
  554. v = BN_CTX_get(ctx);
  555. if (v == NULL) goto err;
  556. /* reduce x and y mod p */
  557. if (!BN_GF2m_mod(u, y, p)) goto err;
  558. if (!BN_GF2m_mod(a, x, p)) goto err;
  559. if (!BN_copy(b, p)) goto err;
  560. while (!BN_is_odd(a))
  561. {
  562. if (!BN_rshift1(a, a)) goto err;
  563. if (BN_is_odd(u)) if (!BN_GF2m_add(u, u, p)) goto err;
  564. if (!BN_rshift1(u, u)) goto err;
  565. }
  566. do
  567. {
  568. if (BN_GF2m_cmp(b, a) > 0)
  569. {
  570. if (!BN_GF2m_add(b, b, a)) goto err;
  571. if (!BN_GF2m_add(v, v, u)) goto err;
  572. do
  573. {
  574. if (!BN_rshift1(b, b)) goto err;
  575. if (BN_is_odd(v)) if (!BN_GF2m_add(v, v, p)) goto err;
  576. if (!BN_rshift1(v, v)) goto err;
  577. } while (!BN_is_odd(b));
  578. }
  579. else if (BN_abs_is_word(a, 1))
  580. break;
  581. else
  582. {
  583. if (!BN_GF2m_add(a, a, b)) goto err;
  584. if (!BN_GF2m_add(u, u, v)) goto err;
  585. do
  586. {
  587. if (!BN_rshift1(a, a)) goto err;
  588. if (BN_is_odd(u)) if (!BN_GF2m_add(u, u, p)) goto err;
  589. if (!BN_rshift1(u, u)) goto err;
  590. } while (!BN_is_odd(a));
  591. }
  592. } while (1);
  593. if (!BN_copy(r, u)) goto err;
  594. bn_check_top(r);
  595. ret = 1;
  596. err:
  597. BN_CTX_end(ctx);
  598. return ret;
  599. }
  600. #endif
  601. /* Divide yy by xx, reduce modulo p, and store the result in r. r could be xx
  602. * or yy, xx could equal yy.
  603. *
  604. * This function calls down to the BN_GF2m_mod_div implementation; this wrapper
  605. * function is only provided for convenience; for best performance, use the
  606. * BN_GF2m_mod_div function.
  607. */
  608. int BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *yy, const BIGNUM *xx, const unsigned int p[], BN_CTX *ctx)
  609. {
  610. BIGNUM *field;
  611. int ret = 0;
  612. bn_check_top(yy);
  613. bn_check_top(xx);
  614. BN_CTX_start(ctx);
  615. if ((field = BN_CTX_get(ctx)) == NULL) goto err;
  616. if (!BN_GF2m_arr2poly(p, field)) goto err;
  617. ret = BN_GF2m_mod_div(r, yy, xx, field, ctx);
  618. bn_check_top(r);
  619. err:
  620. BN_CTX_end(ctx);
  621. return ret;
  622. }
  623. /* Compute the bth power of a, reduce modulo p, and store
  624. * the result in r. r could be a.
  625. * Uses simple square-and-multiply algorithm A.5.1 from IEEE P1363.
  626. */
  627. int BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const unsigned int p[], BN_CTX *ctx)
  628. {
  629. int ret = 0, i, n;
  630. BIGNUM *u;
  631. bn_check_top(a);
  632. bn_check_top(b);
  633. if (BN_is_zero(b))
  634. return(BN_one(r));
  635. if (BN_abs_is_word(b, 1))
  636. return (BN_copy(r, a) != NULL);
  637. BN_CTX_start(ctx);
  638. if ((u = BN_CTX_get(ctx)) == NULL) goto err;
  639. if (!BN_GF2m_mod_arr(u, a, p)) goto err;
  640. n = BN_num_bits(b) - 1;
  641. for (i = n - 1; i >= 0; i--)
  642. {
  643. if (!BN_GF2m_mod_sqr_arr(u, u, p, ctx)) goto err;
  644. if (BN_is_bit_set(b, i))
  645. {
  646. if (!BN_GF2m_mod_mul_arr(u, u, a, p, ctx)) goto err;
  647. }
  648. }
  649. if (!BN_copy(r, u)) goto err;
  650. bn_check_top(r);
  651. ret = 1;
  652. err:
  653. BN_CTX_end(ctx);
  654. return ret;
  655. }
  656. /* Compute the bth power of a, reduce modulo p, and store
  657. * the result in r. r could be a.
  658. *
  659. * This function calls down to the BN_GF2m_mod_exp_arr implementation; this wrapper
  660. * function is only provided for convenience; for best performance, use the
  661. * BN_GF2m_mod_exp_arr function.
  662. */
  663. int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx)
  664. {
  665. int ret = 0;
  666. const int max = BN_num_bits(p);
  667. unsigned int *arr=NULL;
  668. bn_check_top(a);
  669. bn_check_top(b);
  670. bn_check_top(p);
  671. if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
  672. ret = BN_GF2m_poly2arr(p, arr, max);
  673. if (!ret || ret > max)
  674. {
  675. BNerr(BN_F_BN_GF2M_MOD_EXP,BN_R_INVALID_LENGTH);
  676. goto err;
  677. }
  678. ret = BN_GF2m_mod_exp_arr(r, a, b, arr, ctx);
  679. bn_check_top(r);
  680. err:
  681. if (arr) OPENSSL_free(arr);
  682. return ret;
  683. }
  684. /* Compute the square root of a, reduce modulo p, and store
  685. * the result in r. r could be a.
  686. * Uses exponentiation as in algorithm A.4.1 from IEEE P1363.
  687. */
  688. int BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[], BN_CTX *ctx)
  689. {
  690. int ret = 0;
  691. BIGNUM *u;
  692. bn_check_top(a);
  693. if (!p[0])
  694. {
  695. /* reduction mod 1 => return 0 */
  696. BN_zero(r);
  697. return 1;
  698. }
  699. BN_CTX_start(ctx);
  700. if ((u = BN_CTX_get(ctx)) == NULL) goto err;
  701. if (!BN_set_bit(u, p[0] - 1)) goto err;
  702. ret = BN_GF2m_mod_exp_arr(r, a, u, p, ctx);
  703. bn_check_top(r);
  704. err:
  705. BN_CTX_end(ctx);
  706. return ret;
  707. }
  708. /* Compute the square root of a, reduce modulo p, and store
  709. * the result in r. r could be a.
  710. *
  711. * This function calls down to the BN_GF2m_mod_sqrt_arr implementation; this wrapper
  712. * function is only provided for convenience; for best performance, use the
  713. * BN_GF2m_mod_sqrt_arr function.
  714. */
  715. int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
  716. {
  717. int ret = 0;
  718. const int max = BN_num_bits(p);
  719. unsigned int *arr=NULL;
  720. bn_check_top(a);
  721. bn_check_top(p);
  722. if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
  723. ret = BN_GF2m_poly2arr(p, arr, max);
  724. if (!ret || ret > max)
  725. {
  726. BNerr(BN_F_BN_GF2M_MOD_SQRT,BN_R_INVALID_LENGTH);
  727. goto err;
  728. }
  729. ret = BN_GF2m_mod_sqrt_arr(r, a, arr, ctx);
  730. bn_check_top(r);
  731. err:
  732. if (arr) OPENSSL_free(arr);
  733. return ret;
  734. }
  735. /* Find r such that r^2 + r = a mod p. r could be a. If no r exists returns 0.
  736. * Uses algorithms A.4.7 and A.4.6 from IEEE P1363.
  737. */
  738. int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a_, const unsigned int p[], BN_CTX *ctx)
  739. {
  740. int ret = 0, count = 0;
  741. unsigned int j;
  742. BIGNUM *a, *z, *rho, *w, *w2, *tmp;
  743. bn_check_top(a_);
  744. if (!p[0])
  745. {
  746. /* reduction mod 1 => return 0 */
  747. BN_zero(r);
  748. return 1;
  749. }
  750. BN_CTX_start(ctx);
  751. a = BN_CTX_get(ctx);
  752. z = BN_CTX_get(ctx);
  753. w = BN_CTX_get(ctx);
  754. if (w == NULL) goto err;
  755. if (!BN_GF2m_mod_arr(a, a_, p)) goto err;
  756. if (BN_is_zero(a))
  757. {
  758. BN_zero(r);
  759. ret = 1;
  760. goto err;
  761. }
  762. if (p[0] & 0x1) /* m is odd */
  763. {
  764. /* compute half-trace of a */
  765. if (!BN_copy(z, a)) goto err;
  766. for (j = 1; j <= (p[0] - 1) / 2; j++)
  767. {
  768. if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) goto err;
  769. if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) goto err;
  770. if (!BN_GF2m_add(z, z, a)) goto err;
  771. }
  772. }
  773. else /* m is even */
  774. {
  775. rho = BN_CTX_get(ctx);
  776. w2 = BN_CTX_get(ctx);
  777. tmp = BN_CTX_get(ctx);
  778. if (tmp == NULL) goto err;
  779. do
  780. {
  781. if (!BN_rand(rho, p[0], 0, 0)) goto err;
  782. if (!BN_GF2m_mod_arr(rho, rho, p)) goto err;
  783. BN_zero(z);
  784. if (!BN_copy(w, rho)) goto err;
  785. for (j = 1; j <= p[0] - 1; j++)
  786. {
  787. if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) goto err;
  788. if (!BN_GF2m_mod_sqr_arr(w2, w, p, ctx)) goto err;
  789. if (!BN_GF2m_mod_mul_arr(tmp, w2, a, p, ctx)) goto err;
  790. if (!BN_GF2m_add(z, z, tmp)) goto err;
  791. if (!BN_GF2m_add(w, w2, rho)) goto err;
  792. }
  793. count++;
  794. } while (BN_is_zero(w) && (count < MAX_ITERATIONS));
  795. if (BN_is_zero(w))
  796. {
  797. BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR,BN_R_TOO_MANY_ITERATIONS);
  798. goto err;
  799. }
  800. }
  801. if (!BN_GF2m_mod_sqr_arr(w, z, p, ctx)) goto err;
  802. if (!BN_GF2m_add(w, z, w)) goto err;
  803. if (BN_GF2m_cmp(w, a))
  804. {
  805. BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR, BN_R_NO_SOLUTION);
  806. goto err;
  807. }
  808. if (!BN_copy(r, z)) goto err;
  809. bn_check_top(r);
  810. ret = 1;
  811. err:
  812. BN_CTX_end(ctx);
  813. return ret;
  814. }
  815. /* Find r such that r^2 + r = a mod p. r could be a. If no r exists returns 0.
  816. *
  817. * This function calls down to the BN_GF2m_mod_solve_quad_arr implementation; this wrapper
  818. * function is only provided for convenience; for best performance, use the
  819. * BN_GF2m_mod_solve_quad_arr function.
  820. */
  821. int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
  822. {
  823. int ret = 0;
  824. const int max = BN_num_bits(p);
  825. unsigned int *arr=NULL;
  826. bn_check_top(a);
  827. bn_check_top(p);
  828. if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) *
  829. max)) == NULL) goto err;
  830. ret = BN_GF2m_poly2arr(p, arr, max);
  831. if (!ret || ret > max)
  832. {
  833. BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD,BN_R_INVALID_LENGTH);
  834. goto err;
  835. }
  836. ret = BN_GF2m_mod_solve_quad_arr(r, a, arr, ctx);
  837. bn_check_top(r);
  838. err:
  839. if (arr) OPENSSL_free(arr);
  840. return ret;
  841. }
  842. /* Convert the bit-string representation of a polynomial
  843. * ( \sum_{i=0}^n a_i * x^i , where a_0 is *not* zero) into an array
  844. * of integers corresponding to the bits with non-zero coefficient.
  845. * Up to max elements of the array will be filled. Return value is total
  846. * number of coefficients that would be extracted if array was large enough.
  847. */
  848. int BN_GF2m_poly2arr(const BIGNUM *a, unsigned int p[], int max)
  849. {
  850. int i, j, k = 0;
  851. BN_ULONG mask;
  852. if (BN_is_zero(a) || !BN_is_bit_set(a, 0))
  853. /* a_0 == 0 => return error (the unsigned int array
  854. * must be terminated by 0)
  855. */
  856. return 0;
  857. for (i = a->top - 1; i >= 0; i--)
  858. {
  859. if (!a->d[i])
  860. /* skip word if a->d[i] == 0 */
  861. continue;
  862. mask = BN_TBIT;
  863. for (j = BN_BITS2 - 1; j >= 0; j--)
  864. {
  865. if (a->d[i] & mask)
  866. {
  867. if (k < max) p[k] = BN_BITS2 * i + j;
  868. k++;
  869. }
  870. mask >>= 1;
  871. }
  872. }
  873. return k;
  874. }
  875. /* Convert the coefficient array representation of a polynomial to a
  876. * bit-string. The array must be terminated by 0.
  877. */
  878. int BN_GF2m_arr2poly(const unsigned int p[], BIGNUM *a)
  879. {
  880. int i;
  881. bn_check_top(a);
  882. BN_zero(a);
  883. for (i = 0; p[i] != 0; i++)
  884. {
  885. if (BN_set_bit(a, p[i]) == 0)
  886. return 0;
  887. }
  888. BN_set_bit(a, 0);
  889. bn_check_top(a);
  890. return 1;
  891. }