开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 游戏 > 其他游戏 > 查看源码
bn_gf2m.c
资源名称：wow-313-source.rar　[点击查看]
上传用户：yisoukefu
上传日期：2020-08-09
资源大小：39506k
文件大小：29k
源码类别：

其他游戏

开发平台：

Visual C++

bn_gf2m.c：源码内容
  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.  */
  30. /* NOTE: This file is licensed pursuant to the OpenSSL license below
  31.  * and may be modified; but after modifications, the above covenant
  32.  * may no longer apply!  In such cases, the corresponding paragraph
  33.  * ["In addition, Sun covenants ... causes the infringement."] and
  34.  * this note can be edited out; but please keep the Sun copyright
  35.  * notice and attribution. */
  37. /* ====================================================================
  38.  * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
  39.  *
  40.  * Redistribution and use in source and binary forms, with or without
  41.  * modification, are permitted provided that the following conditions
  42.  * are met:
  43.  *
  44.  * 1. Redistributions of source code must retain the above copyright
  45.  *    notice, this list of conditions and the following disclaimer. 
  46.  *
  47.  * 2. Redistributions in binary form must reproduce the above copyright
  48.  *    notice, this list of conditions and the following disclaimer in
  49.  *    the documentation and/or other materials provided with the
  50.  *    distribution.
  51.  *
  52.  * 3. All advertising materials mentioning features or use of this
  53.  *    software must display the following acknowledgment:
  54.  *    "This product includes software developed by the OpenSSL Project
  55.  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  56.  *
  57.  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  58.  *    endorse or promote products derived from this software without
  59.  *    prior written permission. For written permission, please contact
  60.  *    openssl-core@openssl.org.
  61.  *
  62.  * 5. Products derived from this software may not be called "OpenSSL"
  63.  *    nor may "OpenSSL" appear in their names without prior written
  64.  *    permission of the OpenSSL Project.
  65.  *
  66.  * 6. Redistributions of any form whatsoever must retain the following
  67.  *    acknowledgment:
  68.  *    "This product includes software developed by the OpenSSL Project
  69.  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  70.  *
  71.  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  72.  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  73.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  74.  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  75.  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  76.  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  77.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  78.  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  79.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  80.  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  81.  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  82.  * OF THE POSSIBILITY OF SUCH DAMAGE.
  83.  * ====================================================================
  84.  *
  85.  * This product includes cryptographic software written by Eric Young
  86.  * (eay@cryptsoft.com).  This product includes software written by Tim
  87.  * Hudson (tjh@cryptsoft.com).
  88.  *
  89.  */
  91. #include <assert.h>
  92. #include <limits.h>
  93. #include <stdio.h>
  94. #include "cryptlib.h"
  95. #include "bn_lcl.h"
  97. /* Maximum number of iterations before BN_GF2m_mod_solve_quad_arr should fail. */
  98. #define MAX_ITERATIONS 50
  100. static const BN_ULONG SQR_tb[16] =
  101.   {     0,     1,     4,     5,    16,    17,    20,    21,
  102.        64,    65,    68,    69,    80,    81,    84,    85 };
  103. /* Platform-specific macros to accelerate squaring. */
  104. #if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
  105. #define SQR1(w) 
  106.     SQR_tb[(w) >> 60 & 0xF] << 56 | SQR_tb[(w) >> 56 & 0xF] << 48 | 
  107.     SQR_tb[(w) >> 52 & 0xF] << 40 | SQR_tb[(w) >> 48 & 0xF] << 32 | 
  108.     SQR_tb[(w) >> 44 & 0xF] << 24 | SQR_tb[(w) >> 40 & 0xF] << 16 | 
  109.     SQR_tb[(w) >> 36 & 0xF] <<  8 | SQR_tb[(w) >> 32 & 0xF]
  110. #define SQR0(w) 
  111.     SQR_tb[(w) >> 28 & 0xF] << 56 | SQR_tb[(w) >> 24 & 0xF] << 48 | 
  112.     SQR_tb[(w) >> 20 & 0xF] << 40 | SQR_tb[(w) >> 16 & 0xF] << 32 | 
  113.     SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >>  8 & 0xF] << 16 | 
  114.     SQR_tb[(w) >>  4 & 0xF] <<  8 | SQR_tb[(w)       & 0xF]
  115. #endif
  116. #ifdef THIRTY_TWO_BIT
  117. #define SQR1(w) 
  118.     SQR_tb[(w) >> 28 & 0xF] << 24 | SQR_tb[(w) >> 24 & 0xF] << 16 | 
  119.     SQR_tb[(w) >> 20 & 0xF] <<  8 | SQR_tb[(w) >> 16 & 0xF]
  120. #define SQR0(w) 
  121.     SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >>  8 & 0xF] << 16 | 
  122.     SQR_tb[(w) >>  4 & 0xF] <<  8 | SQR_tb[(w)       & 0xF]
  123. #endif
  124. #ifdef SIXTEEN_BIT
  125. #define SQR1(w) 
  126.     SQR_tb[(w) >> 12 & 0xF] <<  8 | SQR_tb[(w) >>  8 & 0xF]
  127. #define SQR0(w) 
  128.     SQR_tb[(w) >>  4 & 0xF] <<  8 | SQR_tb[(w)       & 0xF]
  129. #endif
  130. #ifdef EIGHT_BIT
  131. #define SQR1(w) 
  132.     SQR_tb[(w) >>  4 & 0xF]
  133. #define SQR0(w) 
  134.     SQR_tb[(w)       & 15]
  135. #endif
  137. /* Product of two polynomials a, b each with degree < BN_BITS2 - 1,
  138.  * result is a polynomial r with degree < 2 * BN_BITS - 1
  139.  * The caller MUST ensure that the variables have the right amount
  140.  * of space allocated.
  141.  */
  142. #ifdef EIGHT_BIT
  143. static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, const BN_ULONG b)
  144. {
  145. register BN_ULONG h, l, s;
  146. BN_ULONG tab[4], top1b = a >> 7;
  147. register BN_ULONG a1, a2;
  149. a1 = a & (0x7F); a2 = a1 << 1;
  151. tab[0] = 0; tab[1] = a1; tab[2] = a2; tab[3] = a1^a2;
  153. s = tab[b      & 0x3]; l  = s;
  154. s = tab[b >> 2 & 0x3]; l ^= s << 2; h  = s >> 6;
  155. s = tab[b >> 4 & 0x3]; l ^= s << 4; h ^= s >> 4;
  156. s = tab[b >> 6      ]; l ^= s << 6; h ^= s >> 2;
  158. /* compensate for the top bit of a */
  160. if (top1b & 01) { l ^= b << 7; h ^= b >> 1; } 
  162. *r1 = h; *r0 = l;
  163. } 
  164. #endif
  165. #ifdef SIXTEEN_BIT
  166. static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, const BN_ULONG b)
  167. {
  168. register BN_ULONG h, l, s;
  169. BN_ULONG tab[4], top1b = a >> 15; 
  170. register BN_ULONG a1, a2;
  172. a1 = a & (0x7FFF); a2 = a1 << 1;
  174. tab[0] = 0; tab[1] = a1; tab[2] = a2; tab[3] = a1^a2;
  176. s = tab[b      & 0x3]; l  = s;
  177. s = tab[b >> 2 & 0x3]; l ^= s <<  2; h  = s >> 14;
  178. s = tab[b >> 4 & 0x3]; l ^= s <<  4; h ^= s >> 12;
  179. s = tab[b >> 6 & 0x3]; l ^= s <<  6; h ^= s >> 10;
  180. s = tab[b >> 8 & 0x3]; l ^= s <<  8; h ^= s >>  8;
  181. s = tab[b >>10 & 0x3]; l ^= s << 10; h ^= s >>  6;
  182. s = tab[b >>12 & 0x3]; l ^= s << 12; h ^= s >>  4;
  183. s = tab[b >>14      ]; l ^= s << 14; h ^= s >>  2;
  185. /* compensate for the top bit of a */
  187. if (top1b & 01) { l ^= b << 15; h ^= b >> 1; } 
  189. *r1 = h; *r0 = l;
  190. } 
  191. #endif
  192. #ifdef THIRTY_TWO_BIT
  193. static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, const BN_ULONG b)
  194. {
  195. register BN_ULONG h, l, s;
  196. BN_ULONG tab[8], top2b = a >> 30; 
  197. register BN_ULONG a1, a2, a4;
  199. a1 = a & (0x3FFFFFFF); a2 = a1 << 1; a4 = a2 << 1;
  201. tab[0] =  0; tab[1] = a1;    tab[2] = a2;    tab[3] = a1^a2;
  202. tab[4] = a4; tab[5] = a1^a4; tab[6] = a2^a4; tab[7] = a1^a2^a4;
  204. s = tab[b       & 0x7]; l  = s;
  205. s = tab[b >>  3 & 0x7]; l ^= s <<  3; h  = s >> 29;
  206. s = tab[b >>  6 & 0x7]; l ^= s <<  6; h ^= s >> 26;
  207. s = tab[b >>  9 & 0x7]; l ^= s <<  9; h ^= s >> 23;
  208. s = tab[b >> 12 & 0x7]; l ^= s << 12; h ^= s >> 20;
  209. s = tab[b >> 15 & 0x7]; l ^= s << 15; h ^= s >> 17;
  210. s = tab[b >> 18 & 0x7]; l ^= s << 18; h ^= s >> 14;
  211. s = tab[b >> 21 & 0x7]; l ^= s << 21; h ^= s >> 11;
  212. s = tab[b >> 24 & 0x7]; l ^= s << 24; h ^= s >>  8;
  213. s = tab[b >> 27 & 0x7]; l ^= s << 27; h ^= s >>  5;
  214. s = tab[b >> 30      ]; l ^= s << 30; h ^= s >>  2;
  216. /* compensate for the top two bits of a */
  218. if (top2b & 01) { l ^= b << 30; h ^= b >> 2; } 
  219. if (top2b & 02) { l ^= b << 31; h ^= b >> 1; } 
  221. *r1 = h; *r0 = l;
  222. } 
  223. #endif
  224. #if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
  225. static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, const BN_ULONG b)
  226. {
  227. register BN_ULONG h, l, s;
  228. BN_ULONG tab[16], top3b = a >> 61;
  229. register BN_ULONG a1, a2, a4, a8;
  231. a1 = a & (0x1FFFFFFFFFFFFFFFULL); a2 = a1 << 1; a4 = a2 << 1; a8 = a4 << 1;
  233. tab[ 0] = 0;     tab[ 1] = a1;       tab[ 2] = a2;       tab[ 3] = a1^a2;
  234. tab[ 4] = a4;    tab[ 5] = a1^a4;    tab[ 6] = a2^a4;    tab[ 7] = a1^a2^a4;
  235. tab[ 8] = a8;    tab[ 9] = a1^a8;    tab[10] = a2^a8;    tab[11] = a1^a2^a8;
  236. tab[12] = a4^a8; tab[13] = a1^a4^a8; tab[14] = a2^a4^a8; tab[15] = a1^a2^a4^a8;
  238. s = tab[b       & 0xF]; l  = s;
  239. s = tab[b >>  4 & 0xF]; l ^= s <<  4; h  = s >> 60;
  240. s = tab[b >>  8 & 0xF]; l ^= s <<  8; h ^= s >> 56;
  241. s = tab[b >> 12 & 0xF]; l ^= s << 12; h ^= s >> 52;
  242. s = tab[b >> 16 & 0xF]; l ^= s << 16; h ^= s >> 48;
  243. s = tab[b >> 20 & 0xF]; l ^= s << 20; h ^= s >> 44;
  244. s = tab[b >> 24 & 0xF]; l ^= s << 24; h ^= s >> 40;
  245. s = tab[b >> 28 & 0xF]; l ^= s << 28; h ^= s >> 36;
  246. s = tab[b >> 32 & 0xF]; l ^= s << 32; h ^= s >> 32;
  247. s = tab[b >> 36 & 0xF]; l ^= s << 36; h ^= s >> 28;
  248. s = tab[b >> 40 & 0xF]; l ^= s << 40; h ^= s >> 24;
  249. s = tab[b >> 44 & 0xF]; l ^= s << 44; h ^= s >> 20;
  250. s = tab[b >> 48 & 0xF]; l ^= s << 48; h ^= s >> 16;
  251. s = tab[b >> 52 & 0xF]; l ^= s << 52; h ^= s >> 12;
  252. s = tab[b >> 56 & 0xF]; l ^= s << 56; h ^= s >>  8;
  253. s = tab[b >> 60      ]; l ^= s << 60; h ^= s >>  4;
  255. /* compensate for the top three bits of a */
  257. if (top3b & 01) { l ^= b << 61; h ^= b >> 3; } 
  258. if (top3b & 02) { l ^= b << 62; h ^= b >> 2; } 
  259. if (top3b & 04) { l ^= b << 63; h ^= b >> 1; } 
  261. *r1 = h; *r0 = l;
  262. } 
  263. #endif
  265. /* Product of two polynomials a, b each with degree < 2 * BN_BITS2 - 1,
  266.  * result is a polynomial r with degree < 4 * BN_BITS2 - 1
  267.  * The caller MUST ensure that the variables have the right amount
  268.  * of space allocated.
  269.  */
  270. 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)
  271. {
  272. BN_ULONG m1, m0;
  273. /* r[3] = h1, r[2] = h0; r[1] = l1; r[0] = l0 */
  274. bn_GF2m_mul_1x1(r+3, r+2, a1, b1);
  275. bn_GF2m_mul_1x1(r+1, r, a0, b0);
  276. bn_GF2m_mul_1x1(&m1, &m0, a0 ^ a1, b0 ^ b1);
  277. /* Correction on m1 ^= l1 ^ h1; m0 ^= l0 ^ h0; */
  278. r[2] ^= m1 ^ r[1] ^ r[3];  /* h0 ^= m1 ^ l1 ^ h1; */
  279. r[1] = r[3] ^ r[2] ^ r[0] ^ m1 ^ m0;  /* l1 ^= l0 ^ h0 ^ m0; */
  280. }
  283. /* Add polynomials a and b and store result in r; r could be a or b, a and b 
  284.  * could be equal; r is the bitwise XOR of a and b.
  285.  */
  286. int BN_GF2m_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  287. {
  288. int i;
  289. const BIGNUM *at, *bt;
  291. bn_check_top(a);
  292. bn_check_top(b);
  294. if (a->top < b->top) { at = b; bt = a; }
  295. else { at = a; bt = b; }
  297. bn_wexpand(r, at->top);
  299. for (i = 0; i < bt->top; i++)
  300. {
  301. r->d[i] = at->d[i] ^ bt->d[i];
  302. }
  303. for (; i < at->top; i++)
  304. {
  305. r->d[i] = at->d[i];
  306. }
  308. r->top = at->top;
  309. bn_correct_top(r);
  311. return 1;
  312. }
  315. /* Some functions allow for representation of the irreducible polynomials
  316.  * as an int[], say p.  The irreducible f(t) is then of the form:
  317.  *     t^p[0] + t^p[1] + ... + t^p[k]
  318.  * where m = p[0] > p[1] > ... > p[k] = 0.
  319.  */
  322. /* Performs modular reduction of a and store result in r.  r could be a. */
  323. int BN_GF2m_mod_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[])
  324. {
  325. int j, k;
  326. int n, dN, d0, d1;
  327. BN_ULONG zz, *z;
  329. bn_check_top(a);
  331. if (!p[0])
  332. {
  333. /* reduction mod 1 => return 0 */
  334. BN_zero(r);
  335. return 1;
  336. }
  338. /* Since the algorithm does reduction in the r value, if a != r, copy
  339.  * the contents of a into r so we can do reduction in r. 
  340.  */
  341. if (a != r)
  342. {
  343. if (!bn_wexpand(r, a->top)) return 0;
  344. for (j = 0; j < a->top; j++)
  345. {
  346. r->d[j] = a->d[j];
  347. }
  348. r->top = a->top;
  349. }
  350. z = r->d;
  352. /* start reduction */
  353. dN = p[0] / BN_BITS2;  
  354. for (j = r->top - 1; j > dN;)
  355. {
  356. zz = z[j];
  357. if (z[j] == 0) { j--; continue; }
  358. z[j] = 0;
  360. for (k = 1; p[k] != 0; k++)
  361. {
  362. /* reducing component t^p[k] */
  363. n = p[0] - p[k];
  364. d0 = n % BN_BITS2;  d1 = BN_BITS2 - d0;
  365. n /= BN_BITS2; 
  366. z[j-n] ^= (zz>>d0);
  367. if (d0) z[j-n-1] ^= (zz<<d1);
  368. }
  370. /* reducing component t^0 */
  371. n = dN;  
  372. d0 = p[0] % BN_BITS2;
  373. d1 = BN_BITS2 - d0;
  374. z[j-n] ^= (zz >> d0);
  375. if (d0) z[j-n-1] ^= (zz << d1);
  376. }
  378. /* final round of reduction */
  379. while (j == dN)
  380. {
  382. d0 = p[0] % BN_BITS2;
  383. zz = z[dN] >> d0;
  384. if (zz == 0) break;
  385. d1 = BN_BITS2 - d0;
  387. if (d0) z[dN] = (z[dN] << d1) >> d1; /* clear up the top d1 bits */
  388. z[0] ^= zz; /* reduction t^0 component */
  390. for (k = 1; p[k] != 0; k++)
  391. {
  392. BN_ULONG tmp_ulong;
  394. /* reducing component t^p[k]*/
  395. n = p[k] / BN_BITS2;   
  396. d0 = p[k] % BN_BITS2;
  397. d1 = BN_BITS2 - d0;
  398. z[n] ^= (zz << d0);
  399. tmp_ulong = zz >> d1;
  400.                         if (d0 && tmp_ulong)
  401.                                 z[n+1] ^= tmp_ulong;
  402. }
  405. }
  407. bn_correct_top(r);
  408. return 1;
  409. }
  411. /* Performs modular reduction of a by p and store result in r.  r could be a.
  412.  *
  413.  * This function calls down to the BN_GF2m_mod_arr implementation; this wrapper
  414.  * function is only provided for convenience; for best performance, use the 
  415.  * BN_GF2m_mod_arr function.
  416.  */
  417. int BN_GF2m_mod(BIGNUM *r, const BIGNUM *a, const BIGNUM *p)
  418. {
  419. int ret = 0;
  420. const int max = BN_num_bits(p);
  421. unsigned int *arr=NULL;
  422. bn_check_top(a);
  423. bn_check_top(p);
  424. if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
  425. ret = BN_GF2m_poly2arr(p, arr, max);
  426. if (!ret || ret > max)
  427. {
  428. BNerr(BN_F_BN_GF2M_MOD,BN_R_INVALID_LENGTH);
  429. goto err;
  430. }
  431. ret = BN_GF2m_mod_arr(r, a, arr);
  432. bn_check_top(r);
  433. err:
  434. if (arr) OPENSSL_free(arr);
  435. return ret;
  436. }
  439. /* Compute the product of two polynomials a and b, reduce modulo p, and store
  440.  * the result in r.  r could be a or b; a could be b.
  441.  */
  442. int BN_GF2m_mod_mul_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const unsigned int p[], BN_CTX *ctx)
  443. {
  444. int zlen, i, j, k, ret = 0;
  445. BIGNUM *s;
  446. BN_ULONG x1, x0, y1, y0, zz[4];
  448. bn_check_top(a);
  449. bn_check_top(b);
  451. if (a == b)
  452. {
  453. return BN_GF2m_mod_sqr_arr(r, a, p, ctx);
  454. }
  456. BN_CTX_start(ctx);
  457. if ((s = BN_CTX_get(ctx)) == NULL) goto err;
  459. zlen = a->top + b->top + 4;
  460. if (!bn_wexpand(s, zlen)) goto err;
  461. s->top = zlen;
  463. for (i = 0; i < zlen; i++) s->d[i] = 0;
  465. for (j = 0; j < b->top; j += 2)
  466. {
  467. y0 = b->d[j];
  468. y1 = ((j+1) == b->top) ? 0 : b->d[j+1];
  469. for (i = 0; i < a->top; i += 2)
  470. {
  471. x0 = a->d[i];
  472. x1 = ((i+1) == a->top) ? 0 : a->d[i+1];
  473. bn_GF2m_mul_2x2(zz, x1, x0, y1, y0);
  474. for (k = 0; k < 4; k++) s->d[i+j+k] ^= zz[k];
  475. }
  476. }
  478. bn_correct_top(s);
  479. if (BN_GF2m_mod_arr(r, s, p))
  480. ret = 1;
  481. bn_check_top(r);
  483. err:
  484. BN_CTX_end(ctx);
  485. return ret;
  486. }
  488. /* Compute the product of two polynomials a and b, reduce modulo p, and store
  489.  * the result in r.  r could be a or b; a could equal b.
  490.  *
  491.  * This function calls down to the BN_GF2m_mod_mul_arr implementation; this wrapper
  492.  * function is only provided for convenience; for best performance, use the 
  493.  * BN_GF2m_mod_mul_arr function.
  494.  */
  495. int BN_GF2m_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx)
  496. {
  497. int ret = 0;
  498. const int max = BN_num_bits(p);
  499. unsigned int *arr=NULL;
  500. bn_check_top(a);
  501. bn_check_top(b);
  502. bn_check_top(p);
  503. if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
  504. ret = BN_GF2m_poly2arr(p, arr, max);
  505. if (!ret || ret > max)
  506. {
  507. BNerr(BN_F_BN_GF2M_MOD_MUL,BN_R_INVALID_LENGTH);
  508. goto err;
  509. }
  510. ret = BN_GF2m_mod_mul_arr(r, a, b, arr, ctx);
  511. bn_check_top(r);
  512. err:
  513. if (arr) OPENSSL_free(arr);
  514. return ret;
  515. }
  518. /* Square a, reduce the result mod p, and store it in a.  r could be a. */
  519. int BN_GF2m_mod_sqr_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[], BN_CTX *ctx)
  520. {
  521. int i, ret = 0;
  522. BIGNUM *s;
  524. bn_check_top(a);
  525. BN_CTX_start(ctx);
  526. if ((s = BN_CTX_get(ctx)) == NULL) return 0;
  527. if (!bn_wexpand(s, 2 * a->top)) goto err;
  529. for (i = a->top - 1; i >= 0; i--)
  530. {
  531. s->d[2*i+1] = SQR1(a->d[i]);
  532. s->d[2*i  ] = SQR0(a->d[i]);
  533. }
  535. s->top = 2 * a->top;
  536. bn_correct_top(s);
  537. if (!BN_GF2m_mod_arr(r, s, p)) goto err;
  538. bn_check_top(r);
  539. ret = 1;
  540. err:
  541. BN_CTX_end(ctx);
  542. return ret;
  543. }
  545. /* Square a, reduce the result mod p, and store it in a.  r could be a.
  546.  *
  547.  * This function calls down to the BN_GF2m_mod_sqr_arr implementation; this wrapper
  548.  * function is only provided for convenience; for best performance, use the 
  549.  * BN_GF2m_mod_sqr_arr function.
  550.  */
  551. int BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
  552. {
  553. int ret = 0;
  554. const int max = BN_num_bits(p);
  555. unsigned int *arr=NULL;
  557. bn_check_top(a);
  558. bn_check_top(p);
  559. if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
  560. ret = BN_GF2m_poly2arr(p, arr, max);
  561. if (!ret || ret > max)
  562. {
  563. BNerr(BN_F_BN_GF2M_MOD_SQR,BN_R_INVALID_LENGTH);
  564. goto err;
  565. }
  566. ret = BN_GF2m_mod_sqr_arr(r, a, arr, ctx);
  567. bn_check_top(r);
  568. err:
  569. if (arr) OPENSSL_free(arr);
  570. return ret;
  571. }
  574. /* Invert a, reduce modulo p, and store the result in r. r could be a. 
  575.  * Uses Modified Almost Inverse Algorithm (Algorithm 10) from
  576.  *     Hankerson, D., Hernandez, J.L., and Menezes, A.  "Software Implementation
  577.  *     of Elliptic Curve Cryptography Over Binary Fields".
  578.  */
  579. int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
  580. {
  581. BIGNUM *b, *c, *u, *v, *tmp;
  582. int ret = 0;
  584. bn_check_top(a);
  585. bn_check_top(p);
  587. BN_CTX_start(ctx);
  589. b = BN_CTX_get(ctx);
  590. c = BN_CTX_get(ctx);
  591. u = BN_CTX_get(ctx);
  592. v = BN_CTX_get(ctx);
  593. if (v == NULL) goto err;
  595. if (!BN_one(b)) goto err;
  596. if (!BN_GF2m_mod(u, a, p)) goto err;
  597. if (!BN_copy(v, p)) goto err;
  599. if (BN_is_zero(u)) goto err;
  601. while (1)
  602. {
  603. while (!BN_is_odd(u))
  604. {
  605. if (!BN_rshift1(u, u)) goto err;
  606. if (BN_is_odd(b))
  607. {
  608. if (!BN_GF2m_add(b, b, p)) goto err;
  609. }
  610. if (!BN_rshift1(b, b)) goto err;
  611. }
  613. if (BN_abs_is_word(u, 1)) break;
  615. if (BN_num_bits(u) < BN_num_bits(v))
  616. {
  617. tmp = u; u = v; v = tmp;
  618. tmp = b; b = c; c = tmp;
  619. }
  621. if (!BN_GF2m_add(u, u, v)) goto err;
  622. if (!BN_GF2m_add(b, b, c)) goto err;
  623. }
  626. if (!BN_copy(r, b)) goto err;
  627. bn_check_top(r);
  628. ret = 1;
  630. err:
  631.    BN_CTX_end(ctx);
  632. return ret;
  633. }
  635. /* Invert xx, reduce modulo p, and store the result in r. r could be xx. 
  636.  *
  637.  * This function calls down to the BN_GF2m_mod_inv implementation; this wrapper
  638.  * function is only provided for convenience; for best performance, use the 
  639.  * BN_GF2m_mod_inv function.
  640.  */
  641. int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const unsigned int p[], BN_CTX *ctx)
  642. {
  643. BIGNUM *field;
  644. int ret = 0;
  646. bn_check_top(xx);
  647. BN_CTX_start(ctx);
  648. if ((field = BN_CTX_get(ctx)) == NULL) goto err;
  649. if (!BN_GF2m_arr2poly(p, field)) goto err;
  651. ret = BN_GF2m_mod_inv(r, xx, field, ctx);
  652. bn_check_top(r);
  654. err:
  655. BN_CTX_end(ctx);
  656. return ret;
  657. }
  660. #ifndef OPENSSL_SUN_GF2M_DIV
  661. /* Divide y by x, reduce modulo p, and store the result in r. r could be x 
  662.  * or y, x could equal y.
  663.  */
  664. int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, const BIGNUM *p, BN_CTX *ctx)
  665. {
  666. BIGNUM *xinv = NULL;
  667. int ret = 0;
  669. bn_check_top(y);
  670. bn_check_top(x);
  671. bn_check_top(p);
  673. BN_CTX_start(ctx);
  674. xinv = BN_CTX_get(ctx);
  675. if (xinv == NULL) goto err;
  677. if (!BN_GF2m_mod_inv(xinv, x, p, ctx)) goto err;
  678. if (!BN_GF2m_mod_mul(r, y, xinv, p, ctx)) goto err;
  679. bn_check_top(r);
  680. ret = 1;
  682. err:
  683. BN_CTX_end(ctx);
  684. return ret;
  685. }
  686. #else
  687. /* Divide y by x, reduce modulo p, and store the result in r. r could be x 
  688.  * or y, x could equal y.
  689.  * Uses algorithm Modular_Division_GF(2^m) from 
  690.  *     Chang-Shantz, S.  "From Euclid's GCD to Montgomery Multiplication to 
  691.  *     the Great Divide".
  692.  */
  693. int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, const BIGNUM *p, BN_CTX *ctx)
  694. {
  695. BIGNUM *a, *b, *u, *v;
  696. int ret = 0;
  698. bn_check_top(y);
  699. bn_check_top(x);
  700. bn_check_top(p);
  702. BN_CTX_start(ctx);
  704. a = BN_CTX_get(ctx);
  705. b = BN_CTX_get(ctx);
  706. u = BN_CTX_get(ctx);
  707. v = BN_CTX_get(ctx);
  708. if (v == NULL) goto err;
  710. /* reduce x and y mod p */
  711. if (!BN_GF2m_mod(u, y, p)) goto err;
  712. if (!BN_GF2m_mod(a, x, p)) goto err;
  713. if (!BN_copy(b, p)) goto err;
  715. while (!BN_is_odd(a))
  716. {
  717. if (!BN_rshift1(a, a)) goto err;
  718. if (BN_is_odd(u)) if (!BN_GF2m_add(u, u, p)) goto err;
  719. if (!BN_rshift1(u, u)) goto err;
  720. }
  722. do
  723. {
  724. if (BN_GF2m_cmp(b, a) > 0)
  725. {
  726. if (!BN_GF2m_add(b, b, a)) goto err;
  727. if (!BN_GF2m_add(v, v, u)) goto err;
  728. do
  729. {
  730. if (!BN_rshift1(b, b)) goto err;
  731. if (BN_is_odd(v)) if (!BN_GF2m_add(v, v, p)) goto err;
  732. if (!BN_rshift1(v, v)) goto err;
  733. } while (!BN_is_odd(b));
  734. }
  735. else if (BN_abs_is_word(a, 1))
  736. break;
  737. else
  738. {
  739. if (!BN_GF2m_add(a, a, b)) goto err;
  740. if (!BN_GF2m_add(u, u, v)) goto err;
  741. do
  742. {
  743. if (!BN_rshift1(a, a)) goto err;
  744. if (BN_is_odd(u)) if (!BN_GF2m_add(u, u, p)) goto err;
  745. if (!BN_rshift1(u, u)) goto err;
  746. } while (!BN_is_odd(a));
  747. }
  748. } while (1);
  750. if (!BN_copy(r, u)) goto err;
  751. bn_check_top(r);
  752. ret = 1;
  754. err:
  755.    BN_CTX_end(ctx);
  756. return ret;
  757. }
  758. #endif
  760. /* Divide yy by xx, reduce modulo p, and store the result in r. r could be xx 
  761.  * or yy, xx could equal yy.
  762.  *
  763.  * This function calls down to the BN_GF2m_mod_div implementation; this wrapper
  764.  * function is only provided for convenience; for best performance, use the 
  765.  * BN_GF2m_mod_div function.
  766.  */
  767. int BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *yy, const BIGNUM *xx, const unsigned int p[], BN_CTX *ctx)
  768. {
  769. BIGNUM *field;
  770. int ret = 0;
  772. bn_check_top(yy);
  773. bn_check_top(xx);
  775. BN_CTX_start(ctx);
  776. if ((field = BN_CTX_get(ctx)) == NULL) goto err;
  777. if (!BN_GF2m_arr2poly(p, field)) goto err;
  779. ret = BN_GF2m_mod_div(r, yy, xx, field, ctx);
  780. bn_check_top(r);
  782. err:
  783. BN_CTX_end(ctx);
  784. return ret;
  785. }
  788. /* Compute the bth power of a, reduce modulo p, and store
  789.  * the result in r.  r could be a.
  790.  * Uses simple square-and-multiply algorithm A.5.1 from IEEE P1363.
  791.  */
  792. int BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const unsigned int p[], BN_CTX *ctx)
  793. {
  794. int ret = 0, i, n;
  795. BIGNUM *u;
  797. bn_check_top(a);
  798. bn_check_top(b);
  800. if (BN_is_zero(b))
  801. return(BN_one(r));
  803. if (BN_abs_is_word(b, 1))
  804. return (BN_copy(r, a) != NULL);
  806. BN_CTX_start(ctx);
  807. if ((u = BN_CTX_get(ctx)) == NULL) goto err;
  809. if (!BN_GF2m_mod_arr(u, a, p)) goto err;
  811. n = BN_num_bits(b) - 1;
  812. for (i = n - 1; i >= 0; i--)
  813. {
  814. if (!BN_GF2m_mod_sqr_arr(u, u, p, ctx)) goto err;
  815. if (BN_is_bit_set(b, i))
  816. {
  817. if (!BN_GF2m_mod_mul_arr(u, u, a, p, ctx)) goto err;
  818. }
  819. }
  820. if (!BN_copy(r, u)) goto err;
  821. bn_check_top(r);
  822. ret = 1;
  823. err:
  824. BN_CTX_end(ctx);
  825. return ret;
  826. }
  828. /* Compute the bth power of a, reduce modulo p, and store
  829.  * the result in r.  r could be a.
  830.  *
  831.  * This function calls down to the BN_GF2m_mod_exp_arr implementation; this wrapper
  832.  * function is only provided for convenience; for best performance, use the 
  833.  * BN_GF2m_mod_exp_arr function.
  834.  */
  835. int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx)
  836. {
  837. int ret = 0;
  838. const int max = BN_num_bits(p);
  839. unsigned int *arr=NULL;
  840. bn_check_top(a);
  841. bn_check_top(b);
  842. bn_check_top(p);
  843. if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
  844. ret = BN_GF2m_poly2arr(p, arr, max);
  845. if (!ret || ret > max)
  846. {
  847. BNerr(BN_F_BN_GF2M_MOD_EXP,BN_R_INVALID_LENGTH);
  848. goto err;
  849. }
  850. ret = BN_GF2m_mod_exp_arr(r, a, b, arr, ctx);
  851. bn_check_top(r);
  852. err:
  853. if (arr) OPENSSL_free(arr);
  854. return ret;
  855. }
  857. /* Compute the square root of a, reduce modulo p, and store
  858.  * the result in r.  r could be a.
  859.  * Uses exponentiation as in algorithm A.4.1 from IEEE P1363.
  860.  */
  861. int BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[], BN_CTX *ctx)
  862. {
  863. int ret = 0;
  864. BIGNUM *u;
  866. bn_check_top(a);
  868. if (!p[0])
  869. {
  870. /* reduction mod 1 => return 0 */
  871. BN_zero(r);
  872. return 1;
  873. }
  875. BN_CTX_start(ctx);
  876. if ((u = BN_CTX_get(ctx)) == NULL) goto err;
  878. if (!BN_set_bit(u, p[0] - 1)) goto err;
  879. ret = BN_GF2m_mod_exp_arr(r, a, u, p, ctx);
  880. bn_check_top(r);
  882. err:
  883. BN_CTX_end(ctx);
  884. return ret;
  885. }
  887. /* Compute the square root of a, reduce modulo p, and store
  888.  * the result in r.  r could be a.
  889.  *
  890.  * This function calls down to the BN_GF2m_mod_sqrt_arr implementation; this wrapper
  891.  * function is only provided for convenience; for best performance, use the 
  892.  * BN_GF2m_mod_sqrt_arr function.
  893.  */
  894. int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
  895. {
  896. int ret = 0;
  897. const int max = BN_num_bits(p);
  898. unsigned int *arr=NULL;
  899. bn_check_top(a);
  900. bn_check_top(p);
  901. if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) * max)) == NULL) goto err;
  902. ret = BN_GF2m_poly2arr(p, arr, max);
  903. if (!ret || ret > max)
  904. {
  905. BNerr(BN_F_BN_GF2M_MOD_SQRT,BN_R_INVALID_LENGTH);
  906. goto err;
  907. }
  908. ret = BN_GF2m_mod_sqrt_arr(r, a, arr, ctx);
  909. bn_check_top(r);
  910. err:
  911. if (arr) OPENSSL_free(arr);
  912. return ret;
  913. }
  915. /* Find r such that r^2 + r = a mod p.  r could be a. If no r exists returns 0.
  916.  * Uses algorithms A.4.7 and A.4.6 from IEEE P1363.
  917.  */
  918. int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a_, const unsigned int p[], BN_CTX *ctx)
  919. {
  920. int ret = 0, count = 0;
  921. unsigned int j;
  922. BIGNUM *a, *z, *rho, *w, *w2, *tmp;
  924. bn_check_top(a_);
  926. if (!p[0])
  927. {
  928. /* reduction mod 1 => return 0 */
  929. BN_zero(r);
  930. return 1;
  931. }
  933. BN_CTX_start(ctx);
  934. a = BN_CTX_get(ctx);
  935. z = BN_CTX_get(ctx);
  936. w = BN_CTX_get(ctx);
  937. if (w == NULL) goto err;
  939. if (!BN_GF2m_mod_arr(a, a_, p)) goto err;
  941. if (BN_is_zero(a))
  942. {
  943. BN_zero(r);
  944. ret = 1;
  945. goto err;
  946. }
  948. if (p[0] & 0x1) /* m is odd */
  949. {
  950. /* compute half-trace of a */
  951. if (!BN_copy(z, a)) goto err;
  952. for (j = 1; j <= (p[0] - 1) / 2; j++)
  953. {
  954. if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) goto err;
  955. if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) goto err;
  956. if (!BN_GF2m_add(z, z, a)) goto err;
  957. }
  959. }
  960. else /* m is even */
  961. {
  962. rho = BN_CTX_get(ctx);
  963. w2 = BN_CTX_get(ctx);
  964. tmp = BN_CTX_get(ctx);
  965. if (tmp == NULL) goto err;
  966. do
  967. {
  968. if (!BN_rand(rho, p[0], 0, 0)) goto err;
  969. if (!BN_GF2m_mod_arr(rho, rho, p)) goto err;
  970. BN_zero(z);
  971. if (!BN_copy(w, rho)) goto err;
  972. for (j = 1; j <= p[0] - 1; j++)
  973. {
  974. if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) goto err;
  975. if (!BN_GF2m_mod_sqr_arr(w2, w, p, ctx)) goto err;
  976. if (!BN_GF2m_mod_mul_arr(tmp, w2, a, p, ctx)) goto err;
  977. if (!BN_GF2m_add(z, z, tmp)) goto err;
  978. if (!BN_GF2m_add(w, w2, rho)) goto err;
  979. }
  980. count++;
  981. } while (BN_is_zero(w) && (count < MAX_ITERATIONS));
  982. if (BN_is_zero(w))
  983. {
  984. BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR,BN_R_TOO_MANY_ITERATIONS);
  985. goto err;
  986. }
  987. }
  989. if (!BN_GF2m_mod_sqr_arr(w, z, p, ctx)) goto err;
  990. if (!BN_GF2m_add(w, z, w)) goto err;
  991. if (BN_GF2m_cmp(w, a))
  992. {
  993. BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR, BN_R_NO_SOLUTION);
  994. goto err;
  995. }
  997. if (!BN_copy(r, z)) goto err;
  998. bn_check_top(r);
  1000. ret = 1;
  1002. err:
  1003. BN_CTX_end(ctx);
  1004. return ret;
  1005. }
  1007. /* Find r such that r^2 + r = a mod p.  r could be a. If no r exists returns 0.
  1008.  *
  1009.  * This function calls down to the BN_GF2m_mod_solve_quad_arr implementation; this wrapper
  1010.  * function is only provided for convenience; for best performance, use the 
  1011.  * BN_GF2m_mod_solve_quad_arr function.
  1012.  */
  1013. int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
  1014. {
  1015. int ret = 0;
  1016. const int max = BN_num_bits(p);
  1017. unsigned int *arr=NULL;
  1018. bn_check_top(a);
  1019. bn_check_top(p);
  1020. if ((arr = (unsigned int *)OPENSSL_malloc(sizeof(unsigned int) *
  1021. max)) == NULL) goto err;
  1022. ret = BN_GF2m_poly2arr(p, arr, max);
  1023. if (!ret || ret > max)
  1024. {
  1025. BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD,BN_R_INVALID_LENGTH);
  1026. goto err;
  1027. }
  1028. ret = BN_GF2m_mod_solve_quad_arr(r, a, arr, ctx);
  1029. bn_check_top(r);
  1030. err:
  1031. if (arr) OPENSSL_free(arr);
  1032. return ret;
  1033. }
  1035. /* Convert the bit-string representation of a polynomial
  1036.  * ( sum_{i=0}^n a_i * x^i , where a_0 is *not* zero) into an array
  1037.  * of integers corresponding to the bits with non-zero coefficient.
  1038.  * Up to max elements of the array will be filled.  Return value is total
  1039.  * number of coefficients that would be extracted if array was large enough.
  1040.  */
  1041. int BN_GF2m_poly2arr(const BIGNUM *a, unsigned int p[], int max)
  1042. {
  1043. int i, j, k = 0;
  1044. BN_ULONG mask;
  1046. if (BN_is_zero(a) || !BN_is_bit_set(a, 0))
  1047. /* a_0 == 0 => return error (the unsigned int array
  1048.  * must be terminated by 0)
  1049.  */
  1050. return 0;
  1052. for (i = a->top - 1; i >= 0; i--)
  1053. {
  1054. if (!a->d[i])
  1055. /* skip word if a->d[i] == 0 */
  1056. continue;
  1057. mask = BN_TBIT;
  1058. for (j = BN_BITS2 - 1; j >= 0; j--)
  1059. {
  1060. if (a->d[i] & mask) 
  1061. {
  1062. if (k < max) p[k] = BN_BITS2 * i + j;
  1063. k++;
  1064. }
  1065. mask >>= 1;
  1066. }
  1067. }
  1069. return k;
  1070. }
  1072. /* Convert the coefficient array representation of a polynomial to a 
  1073.  * bit-string.  The array must be terminated by 0.
  1074.  */
  1075. int BN_GF2m_arr2poly(const unsigned int p[], BIGNUM *a)
  1076. {
  1077. int i;
  1079. bn_check_top(a);
  1080. BN_zero(a);
  1081. for (i = 0; p[i] != 0; i++)
  1082. {
  1083. if (BN_set_bit(a, p[i]) == 0)
  1084. return 0;
  1085. }
  1086. BN_set_bit(a, 0);
  1087. bn_check_top(a);
  1089. return 1;
  1090. }