bn_nist.c 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775
  1. /* crypto/bn/bn_nist.c */
  2. /*
  3. * Written by Nils Larsch for the OpenSSL project
  4. */
  5. /* ====================================================================
  6. * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved.
  7. *
  8. * Redistribution and use in source and binary forms, with or without
  9. * modification, are permitted provided that the following conditions
  10. * are met:
  11. *
  12. * 1. Redistributions of source code must retain the above copyright
  13. * notice, this list of conditions and the following disclaimer.
  14. *
  15. * 2. Redistributions in binary form must reproduce the above copyright
  16. * notice, this list of conditions and the following disclaimer in
  17. * the documentation and/or other materials provided with the
  18. * distribution.
  19. *
  20. * 3. All advertising materials mentioning features or use of this
  21. * software must display the following acknowledgment:
  22. * "This product includes software developed by the OpenSSL Project
  23. * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  24. *
  25. * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  26. * endorse or promote products derived from this software without
  27. * prior written permission. For written permission, please contact
  28. * openssl-core@openssl.org.
  29. *
  30. * 5. Products derived from this software may not be called "OpenSSL"
  31. * nor may "OpenSSL" appear in their names without prior written
  32. * permission of the OpenSSL Project.
  33. *
  34. * 6. Redistributions of any form whatsoever must retain the following
  35. * acknowledgment:
  36. * "This product includes software developed by the OpenSSL Project
  37. * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  38. *
  39. * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  40. * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  41. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  42. * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
  43. * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  44. * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  45. * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  46. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  48. * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  49. * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  50. * OF THE POSSIBILITY OF SUCH DAMAGE.
  51. * ====================================================================
  52. *
  53. * This product includes cryptographic software written by Eric Young
  54. * (eay@cryptsoft.com). This product includes software written by Tim
  55. * Hudson (tjh@cryptsoft.com).
  56. *
  57. */
  58. #include "bn_lcl.h"
  59. #include "cryptlib.h"
  60. #define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2
  61. #define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2
  62. #define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2
  63. #define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2
  64. #define BN_NIST_521_TOP (521+BN_BITS2-1)/BN_BITS2
  65. #if BN_BITS2 == 64
  66. static const BN_ULONG _nist_p_192[] =
  67. {0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFEULL,
  68. 0xFFFFFFFFFFFFFFFFULL};
  69. static const BN_ULONG _nist_p_224[] =
  70. {0x0000000000000001ULL,0xFFFFFFFF00000000ULL,
  71. 0xFFFFFFFFFFFFFFFFULL,0x00000000FFFFFFFFULL};
  72. static const BN_ULONG _nist_p_256[] =
  73. {0xFFFFFFFFFFFFFFFFULL,0x00000000FFFFFFFFULL,
  74. 0x0000000000000000ULL,0xFFFFFFFF00000001ULL};
  75. static const BN_ULONG _nist_p_384[] =
  76. {0x00000000FFFFFFFFULL,0xFFFFFFFF00000000ULL,
  77. 0xFFFFFFFFFFFFFFFEULL,0xFFFFFFFFFFFFFFFFULL,
  78. 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL};
  79. static const BN_ULONG _nist_p_521[] =
  80. {0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,
  81. 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,
  82. 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,
  83. 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,
  84. 0x00000000000001FFULL};
  85. #elif BN_BITS2 == 32
  86. static const BN_ULONG _nist_p_192[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFE,
  87. 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};
  88. static const BN_ULONG _nist_p_224[] = {0x00000001,0x00000000,0x00000000,
  89. 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};
  90. static const BN_ULONG _nist_p_256[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
  91. 0x00000000,0x00000000,0x00000000,0x00000001,0xFFFFFFFF};
  92. static const BN_ULONG _nist_p_384[] = {0xFFFFFFFF,0x00000000,0x00000000,
  93. 0xFFFFFFFF,0xFFFFFFFE,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
  94. 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};
  95. static const BN_ULONG _nist_p_521[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
  96. 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
  97. 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
  98. 0xFFFFFFFF,0x000001FF};
  99. #elif BN_BITS2 == 16
  100. static const BN_ULONG _nist_p_192[] = {0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFE,
  101. 0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF};
  102. static const BN_ULONG _nist_p_224[] = {0x0001,0x0000,0x0000,0x0000,0x0000,
  103. 0x0000,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF};
  104. static const BN_ULONG _nist_p_256[] = {0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
  105. 0xFFFF,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0001,0x0000,0xFFFF,
  106. 0xFFFF};
  107. static const BN_ULONG _nist_p_384[] = {0xFFFF,0xFFFF,0x0000,0x0000,0x0000,
  108. 0x0000,0xFFFF,0xFFFF,0xFFFE,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
  109. 0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF};
  110. static const BN_ULONG _nist_p_521[] = {0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
  111. 0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
  112. 0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
  113. 0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0x01FF};
  114. #elif BN_BITS2 == 8
  115. static const BN_ULONG _nist_p_192[] = {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
  116. 0xFE,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
  117. 0xFF,0xFF};
  118. static const BN_ULONG _nist_p_224[] = {0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
  119. 0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
  120. 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF};
  121. static const BN_ULONG _nist_p_256[] = {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
  122. 0xFF,0xFF,0xFF,0xFF,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
  123. 0x00,0x00,0x01,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF};
  124. static const BN_ULONG _nist_p_384[] = {0xFF,0xFF,0xFF,0xFF,0x00,0x00,0x00,0x00,
  125. 0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFF,0xFF,
  126. 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
  127. 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF};
  128. static const BN_ULONG _nist_p_521[] = {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
  129. 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
  130. 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
  131. 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
  132. 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
  133. 0xFF,0x01};
  134. #endif
  135. const BIGNUM *BN_get0_nist_prime_192(void)
  136. {
  137. static BIGNUM const_nist_192 = { (BN_ULONG *)_nist_p_192,
  138. BN_NIST_192_TOP, BN_NIST_192_TOP, 0, BN_FLG_STATIC_DATA };
  139. return &const_nist_192;
  140. }
  141. const BIGNUM *BN_get0_nist_prime_224(void)
  142. {
  143. static BIGNUM const_nist_224 = { (BN_ULONG *)_nist_p_224,
  144. BN_NIST_224_TOP, BN_NIST_224_TOP, 0, BN_FLG_STATIC_DATA };
  145. return &const_nist_224;
  146. }
  147. const BIGNUM *BN_get0_nist_prime_256(void)
  148. {
  149. static BIGNUM const_nist_256 = { (BN_ULONG *)_nist_p_256,
  150. BN_NIST_256_TOP, BN_NIST_256_TOP, 0, BN_FLG_STATIC_DATA };
  151. return &const_nist_256;
  152. }
  153. const BIGNUM *BN_get0_nist_prime_384(void)
  154. {
  155. static BIGNUM const_nist_384 = { (BN_ULONG *)_nist_p_384,
  156. BN_NIST_384_TOP, BN_NIST_384_TOP, 0, BN_FLG_STATIC_DATA };
  157. return &const_nist_384;
  158. }
  159. const BIGNUM *BN_get0_nist_prime_521(void)
  160. {
  161. static BIGNUM const_nist_521 = { (BN_ULONG *)_nist_p_521,
  162. BN_NIST_521_TOP, BN_NIST_521_TOP, 0, BN_FLG_STATIC_DATA };
  163. return &const_nist_521;
  164. }
  165. /* some misc internal functions */
  166. #if BN_BITS2 != 64
  167. static BN_ULONG _256_data[BN_NIST_256_TOP*6];
  168. static int _is_set_256_data = 0;
  169. static void _init_256_data(void);
  170. static BN_ULONG _384_data[BN_NIST_384_TOP*8];
  171. static int _is_set_384_data = 0;
  172. static void _init_384_data(void);
  173. #endif
  174. #define BN_NIST_ADD_ONE(a) while (!(++(*(a)))) ++(a);
  175. static void nist_cp_bn_0(BN_ULONG *buf, BN_ULONG *a, int top, int max)
  176. {
  177. int i;
  178. BN_ULONG *_tmp1 = (buf), *_tmp2 = (a);
  179. for (i = (top); i != 0; i--)
  180. *_tmp1++ = *_tmp2++;
  181. for (i = (max) - (top); i != 0; i--)
  182. *_tmp1++ = (BN_ULONG) 0;
  183. }
  184. static void nist_cp_bn(BN_ULONG *buf, BN_ULONG *a, int top)
  185. {
  186. int i;
  187. BN_ULONG *_tmp1 = (buf), *_tmp2 = (a);
  188. for (i = (top); i != 0; i--)
  189. *_tmp1++ = *_tmp2++;
  190. }
  191. #if BN_BITS2 == 64
  192. #define bn_cp_64(to, n, from, m) (to)[n] = (from)[m];
  193. #define bn_64_set_0(to, n) (to)[n] = (BN_ULONG)0;
  194. /* TBD */
  195. #define bn_cp_32(to, n, from, m) (to)[n] = (from)[m];
  196. #define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0;
  197. #else
  198. #define bn_cp_64(to, n, from, m) \
  199. { \
  200. bn_cp_32(to, (n)*2, from, (m)*2); \
  201. bn_cp_32(to, (n)*2+1, from, (m)*2+1); \
  202. }
  203. #define bn_64_set_0(to, n) \
  204. { \
  205. bn_32_set_0(to, (n)*2); \
  206. bn_32_set_0(to, (n)*2+1); \
  207. }
  208. #if BN_BITS2 == 32
  209. #define bn_cp_32(to, n, from, m) (to)[n] = (from)[m];
  210. #define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0;
  211. #elif BN_BITS2 == 16
  212. #define bn_cp_32(to, n, from, m) \
  213. { \
  214. (to)[(n)*2] = (from)[(m)*2]; \
  215. (to)[(n)*2+1] = (from)[(m)*2+1];\
  216. }
  217. #define bn_32_set_0(to, n) { (to)[(n)*2] = 0; (to)[(n)*2+1] = 0; }
  218. #elif BN_BITS2 == 8
  219. #define bn_cp_32(to, n, from, m) \
  220. { \
  221. (to)[(n)*4] = (from)[(m)*4]; \
  222. (to)[(n)*4+1] = (from)[(m)*4+1];\
  223. (to)[(n)*4+2] = (from)[(m)*4+2];\
  224. (to)[(n)*4+3] = (from)[(m)*4+3];\
  225. }
  226. #define bn_32_set_0(to, n) \
  227. { (to)[(n)*4] = (BN_ULONG)0; (to)[(n)*4+1] = (BN_ULONG)0; \
  228. (to)[(n)*4+2] = (BN_ULONG)0; (to)[(n)*4+3] = (BN_ULONG)0; }
  229. #endif
  230. #endif /* BN_BITS2 != 64 */
  231. #define nist_set_192(to, from, a1, a2, a3) \
  232. { \
  233. if (a3 != 0) bn_cp_64(to, 0, from, (a3) - 3) else bn_64_set_0(to, 0)\
  234. bn_cp_64(to, 1, from, (a2) - 3) \
  235. if (a1 != 0) bn_cp_64(to, 2, from, (a1) - 3) else bn_64_set_0(to, 2)\
  236. }
  237. int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
  238. BN_CTX *ctx)
  239. {
  240. int top = a->top, i;
  241. BN_ULONG carry = 0;
  242. register BN_ULONG *r_d, *a_d = a->d;
  243. BN_ULONG t_d[BN_NIST_192_TOP],
  244. buf[BN_NIST_192_TOP];
  245. i = BN_ucmp(field, a);
  246. if (i == 0)
  247. {
  248. BN_zero(r);
  249. return 1;
  250. }
  251. else if (i > 0)
  252. return (r == a) ? 1 : (BN_copy(r ,a) != NULL);
  253. if (top == BN_NIST_192_TOP)
  254. return BN_usub(r, a, field);
  255. if (r != a)
  256. {
  257. if (!bn_wexpand(r, BN_NIST_192_TOP))
  258. return 0;
  259. r_d = r->d;
  260. nist_cp_bn(r_d, a_d, BN_NIST_192_TOP);
  261. }
  262. else
  263. r_d = a_d;
  264. nist_cp_bn_0(buf, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP, BN_NIST_192_TOP);
  265. #if defined(OPENSSL_SYS_VMS) && defined(__DECC)
  266. # pragma message save
  267. # pragma message disable BADSUBSCRIPT
  268. #endif
  269. nist_set_192(t_d, buf, 0, 3, 3);
  270. if (bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP))
  271. ++carry;
  272. nist_set_192(t_d, buf, 4, 4, 0);
  273. if (bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP))
  274. ++carry;
  275. #if defined(OPENSSL_SYS_VMS) && defined(__DECC)
  276. # pragma message restore
  277. #endif
  278. nist_set_192(t_d, buf, 5, 5, 5)
  279. if (bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP))
  280. ++carry;
  281. while (carry)
  282. {
  283. if (bn_sub_words(r_d, r_d, _nist_p_192, BN_NIST_192_TOP))
  284. --carry;
  285. }
  286. r->top = BN_NIST_192_TOP;
  287. bn_correct_top(r);
  288. if (BN_ucmp(r, field) >= 0)
  289. {
  290. bn_sub_words(r_d, r_d, _nist_p_192, BN_NIST_192_TOP);
  291. bn_correct_top(r);
  292. }
  293. bn_check_top(r);
  294. return 1;
  295. }
  296. #define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \
  297. { \
  298. if (a7 != 0) bn_cp_32(to, 0, from, (a7) - 7) else bn_32_set_0(to, 0)\
  299. if (a6 != 0) bn_cp_32(to, 1, from, (a6) - 7) else bn_32_set_0(to, 1)\
  300. if (a5 != 0) bn_cp_32(to, 2, from, (a5) - 7) else bn_32_set_0(to, 2)\
  301. if (a4 != 0) bn_cp_32(to, 3, from, (a4) - 7) else bn_32_set_0(to, 3)\
  302. if (a3 != 0) bn_cp_32(to, 4, from, (a3) - 7) else bn_32_set_0(to, 4)\
  303. if (a2 != 0) bn_cp_32(to, 5, from, (a2) - 7) else bn_32_set_0(to, 5)\
  304. if (a1 != 0) bn_cp_32(to, 6, from, (a1) - 7) else bn_32_set_0(to, 6)\
  305. }
  306. int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
  307. BN_CTX *ctx)
  308. {
  309. #if BN_BITS2 != 64
  310. int top = a->top, i;
  311. int carry = 0;
  312. BN_ULONG *r_d, *a_d = a->d;
  313. BN_ULONG t_d[BN_NIST_224_TOP],
  314. buf[BN_NIST_224_TOP];
  315. i = BN_ucmp(field, a);
  316. if (i == 0)
  317. {
  318. BN_zero(r);
  319. return 1;
  320. }
  321. else if (i > 0)
  322. return (r == a)? 1 : (BN_copy(r ,a) != NULL);
  323. if (top == BN_NIST_224_TOP)
  324. return BN_usub(r, a, field);
  325. if (r != a)
  326. {
  327. if (!bn_wexpand(r, BN_NIST_224_TOP))
  328. return 0;
  329. r_d = r->d;
  330. nist_cp_bn(r_d, a_d, BN_NIST_224_TOP);
  331. }
  332. else
  333. r_d = a_d;
  334. nist_cp_bn_0(buf, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP, BN_NIST_224_TOP);
  335. nist_set_224(t_d, buf, 10, 9, 8, 7, 0, 0, 0);
  336. if (bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP))
  337. ++carry;
  338. nist_set_224(t_d, buf, 0, 13, 12, 11, 0, 0, 0);
  339. if (bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP))
  340. ++carry;
  341. nist_set_224(t_d, buf, 13, 12, 11, 10, 9, 8, 7);
  342. if (bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP))
  343. --carry;
  344. nist_set_224(t_d, buf, 0, 0, 0, 0, 13, 12, 11);
  345. if (bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP))
  346. --carry;
  347. if (carry > 0)
  348. while (carry)
  349. {
  350. if (bn_sub_words(r_d,r_d,_nist_p_224,BN_NIST_224_TOP))
  351. --carry;
  352. }
  353. else if (carry < 0)
  354. while (carry)
  355. {
  356. if (bn_add_words(r_d,r_d,_nist_p_224,BN_NIST_224_TOP))
  357. ++carry;
  358. }
  359. r->top = BN_NIST_224_TOP;
  360. bn_correct_top(r);
  361. if (BN_ucmp(r, field) >= 0)
  362. {
  363. bn_sub_words(r_d, r_d, _nist_p_224, BN_NIST_224_TOP);
  364. bn_correct_top(r);
  365. }
  366. bn_check_top(r);
  367. return 1;
  368. #else
  369. return 0;
  370. #endif
  371. }
  372. #if BN_BITS2 != 64
  373. static void _init_256_data(void)
  374. {
  375. int i;
  376. BN_ULONG *tmp1 = _256_data;
  377. const BN_ULONG *tmp2 = tmp1;
  378. memcpy(tmp1, _nist_p_256, BN_NIST_256_TOP * sizeof(BN_ULONG));
  379. tmp1 += BN_NIST_256_TOP;
  380. for (i=0; i<5; i++)
  381. {
  382. bn_add_words(tmp1, _nist_p_256, tmp2, BN_NIST_256_TOP);
  383. tmp2 = tmp1;
  384. tmp1 += BN_NIST_256_TOP;
  385. }
  386. _is_set_256_data = 1;
  387. }
  388. #endif
  389. #define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \
  390. { \
  391. if (a8 != 0) bn_cp_32(to, 0, from, (a8) - 8) else bn_32_set_0(to, 0)\
  392. if (a7 != 0) bn_cp_32(to, 1, from, (a7) - 8) else bn_32_set_0(to, 1)\
  393. if (a6 != 0) bn_cp_32(to, 2, from, (a6) - 8) else bn_32_set_0(to, 2)\
  394. if (a5 != 0) bn_cp_32(to, 3, from, (a5) - 8) else bn_32_set_0(to, 3)\
  395. if (a4 != 0) bn_cp_32(to, 4, from, (a4) - 8) else bn_32_set_0(to, 4)\
  396. if (a3 != 0) bn_cp_32(to, 5, from, (a3) - 8) else bn_32_set_0(to, 5)\
  397. if (a2 != 0) bn_cp_32(to, 6, from, (a2) - 8) else bn_32_set_0(to, 6)\
  398. if (a1 != 0) bn_cp_32(to, 7, from, (a1) - 8) else bn_32_set_0(to, 7)\
  399. }
  400. int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
  401. BN_CTX *ctx)
  402. {
  403. #if BN_BITS2 != 64
  404. int i, top = a->top;
  405. int carry = 0;
  406. register BN_ULONG *a_d = a->d, *r_d;
  407. BN_ULONG t_d[BN_NIST_256_TOP],
  408. t_d2[BN_NIST_256_TOP],
  409. buf[BN_NIST_256_TOP];
  410. if (!_is_set_256_data)
  411. {
  412. CRYPTO_w_lock(CRYPTO_LOCK_BN);
  413. if (!_is_set_256_data)
  414. _init_256_data();
  415. CRYPTO_w_unlock(CRYPTO_LOCK_BN);
  416. }
  417. i = BN_ucmp(field, a);
  418. if (i == 0)
  419. {
  420. BN_zero(r);
  421. return 1;
  422. }
  423. else if (i > 0)
  424. return (r == a)? 1 : (BN_copy(r ,a) != NULL);
  425. if (top == BN_NIST_256_TOP)
  426. return BN_usub(r, a, field);
  427. if (r != a)
  428. {
  429. if (!bn_wexpand(r, BN_NIST_256_TOP))
  430. return 0;
  431. r_d = r->d;
  432. nist_cp_bn(r_d, a_d, BN_NIST_256_TOP);
  433. }
  434. else
  435. r_d = a_d;
  436. nist_cp_bn_0(buf, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP, BN_NIST_256_TOP);
  437. /*S1*/
  438. nist_set_256(t_d, buf, 15, 14, 13, 12, 11, 0, 0, 0);
  439. /*S2*/
  440. nist_set_256(t_d2,buf, 0, 15, 14, 13, 12, 0, 0, 0);
  441. if (bn_add_words(t_d, t_d, t_d2, BN_NIST_256_TOP))
  442. carry = 2;
  443. /* left shift */
  444. {
  445. register BN_ULONG *ap,t,c;
  446. ap = t_d;
  447. c=0;
  448. for (i = BN_NIST_256_TOP; i != 0; --i)
  449. {
  450. t= *ap;
  451. *(ap++)=((t<<1)|c)&BN_MASK2;
  452. c=(t & BN_TBIT)?1:0;
  453. }
  454. if (c)
  455. ++carry;
  456. }
  457. if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))
  458. ++carry;
  459. /*S3*/
  460. nist_set_256(t_d, buf, 15, 14, 0, 0, 0, 10, 9, 8);
  461. if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))
  462. ++carry;
  463. /*S4*/
  464. nist_set_256(t_d, buf, 8, 13, 15, 14, 13, 11, 10, 9);
  465. if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))
  466. ++carry;
  467. /*D1*/
  468. nist_set_256(t_d, buf, 10, 8, 0, 0, 0, 13, 12, 11);
  469. if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
  470. --carry;
  471. /*D2*/
  472. nist_set_256(t_d, buf, 11, 9, 0, 0, 15, 14, 13, 12);
  473. if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
  474. --carry;
  475. /*D3*/
  476. nist_set_256(t_d, buf, 12, 0, 10, 9, 8, 15, 14, 13);
  477. if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
  478. --carry;
  479. /*D4*/
  480. nist_set_256(t_d, buf, 13, 0, 11, 10, 9, 0, 15, 14);
  481. if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
  482. --carry;
  483. if (carry)
  484. {
  485. if (carry > 0)
  486. bn_sub_words(r_d, r_d, _256_data + BN_NIST_256_TOP *
  487. --carry, BN_NIST_256_TOP);
  488. else
  489. {
  490. carry = -carry;
  491. bn_add_words(r_d, r_d, _256_data + BN_NIST_256_TOP *
  492. --carry, BN_NIST_256_TOP);
  493. }
  494. }
  495. r->top = BN_NIST_256_TOP;
  496. bn_correct_top(r);
  497. if (BN_ucmp(r, field) >= 0)
  498. {
  499. bn_sub_words(r_d, r_d, _nist_p_256, BN_NIST_256_TOP);
  500. bn_correct_top(r);
  501. }
  502. bn_check_top(r);
  503. return 1;
  504. #else
  505. return 0;
  506. #endif
  507. }
  508. #if BN_BITS2 != 64
  509. static void _init_384_data(void)
  510. {
  511. int i;
  512. BN_ULONG *tmp1 = _384_data;
  513. const BN_ULONG *tmp2 = tmp1;
  514. memcpy(tmp1, _nist_p_384, BN_NIST_384_TOP * sizeof(BN_ULONG));
  515. tmp1 += BN_NIST_384_TOP;
  516. for (i=0; i<7; i++)
  517. {
  518. bn_add_words(tmp1, _nist_p_384, tmp2, BN_NIST_384_TOP);
  519. tmp2 = tmp1;
  520. tmp1 += BN_NIST_384_TOP;
  521. }
  522. _is_set_384_data = 1;
  523. }
  524. #endif
  525. #define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \
  526. { \
  527. if (a12 != 0) bn_cp_32(to, 0, from, (a12) - 12) else bn_32_set_0(to, 0)\
  528. if (a11 != 0) bn_cp_32(to, 1, from, (a11) - 12) else bn_32_set_0(to, 1)\
  529. if (a10 != 0) bn_cp_32(to, 2, from, (a10) - 12) else bn_32_set_0(to, 2)\
  530. if (a9 != 0) bn_cp_32(to, 3, from, (a9) - 12) else bn_32_set_0(to, 3)\
  531. if (a8 != 0) bn_cp_32(to, 4, from, (a8) - 12) else bn_32_set_0(to, 4)\
  532. if (a7 != 0) bn_cp_32(to, 5, from, (a7) - 12) else bn_32_set_0(to, 5)\
  533. if (a6 != 0) bn_cp_32(to, 6, from, (a6) - 12) else bn_32_set_0(to, 6)\
  534. if (a5 != 0) bn_cp_32(to, 7, from, (a5) - 12) else bn_32_set_0(to, 7)\
  535. if (a4 != 0) bn_cp_32(to, 8, from, (a4) - 12) else bn_32_set_0(to, 8)\
  536. if (a3 != 0) bn_cp_32(to, 9, from, (a3) - 12) else bn_32_set_0(to, 9)\
  537. if (a2 != 0) bn_cp_32(to, 10, from, (a2) - 12) else bn_32_set_0(to, 10)\
  538. if (a1 != 0) bn_cp_32(to, 11, from, (a1) - 12) else bn_32_set_0(to, 11)\
  539. }
  540. int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
  541. BN_CTX *ctx)
  542. {
  543. #if BN_BITS2 != 64
  544. int i, top = a->top;
  545. int carry = 0;
  546. register BN_ULONG *r_d, *a_d = a->d;
  547. BN_ULONG t_d[BN_NIST_384_TOP],
  548. buf[BN_NIST_384_TOP];
  549. if (!_is_set_384_data)
  550. {
  551. CRYPTO_w_lock(CRYPTO_LOCK_BN);
  552. if (!_is_set_384_data)
  553. _init_384_data();
  554. CRYPTO_w_unlock(CRYPTO_LOCK_BN);
  555. }
  556. i = BN_ucmp(field, a);
  557. if (i == 0)
  558. {
  559. BN_zero(r);
  560. return 1;
  561. }
  562. else if (i > 0)
  563. return (r == a)? 1 : (BN_copy(r ,a) != NULL);
  564. if (top == BN_NIST_384_TOP)
  565. return BN_usub(r, a, field);
  566. if (r != a)
  567. {
  568. if (!bn_wexpand(r, BN_NIST_384_TOP))
  569. return 0;
  570. r_d = r->d;
  571. nist_cp_bn(r_d, a_d, BN_NIST_384_TOP);
  572. }
  573. else
  574. r_d = a_d;
  575. nist_cp_bn_0(buf, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP, BN_NIST_384_TOP);
  576. /*S1*/
  577. nist_set_256(t_d, buf, 0, 0, 0, 0, 0, 23-4, 22-4, 21-4);
  578. /* left shift */
  579. {
  580. register BN_ULONG *ap,t,c;
  581. ap = t_d;
  582. c=0;
  583. for (i = BN_NIST_256_TOP; i != 0; --i)
  584. {
  585. t= *ap;
  586. *(ap++)=((t<<1)|c)&BN_MASK2;
  587. c=(t & BN_TBIT)?1:0;
  588. }
  589. }
  590. if (bn_add_words(r_d+(128/BN_BITS2), r_d+(128/BN_BITS2),
  591. t_d, BN_NIST_256_TOP))
  592. ++carry;
  593. /*S2 */
  594. if (bn_add_words(r_d, r_d, buf, BN_NIST_384_TOP))
  595. ++carry;
  596. /*S3*/
  597. nist_set_384(t_d,buf,20,19,18,17,16,15,14,13,12,23,22,21);
  598. if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))
  599. ++carry;
  600. /*S4*/
  601. nist_set_384(t_d,buf,19,18,17,16,15,14,13,12,20,0,23,0);
  602. if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))
  603. ++carry;
  604. /*S5*/
  605. nist_set_256(t_d, buf, 0, 0, 0, 0, 23-4, 22-4, 21-4, 20-4);
  606. if (bn_add_words(r_d+(128/BN_BITS2), r_d+(128/BN_BITS2),
  607. t_d, BN_NIST_256_TOP))
  608. ++carry;
  609. /*S6*/
  610. nist_set_384(t_d,buf,0,0,0,0,0,0,23,22,21,0,0,20);
  611. if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))
  612. ++carry;
  613. /*D1*/
  614. nist_set_384(t_d,buf,22,21,20,19,18,17,16,15,14,13,12,23);
  615. if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))
  616. --carry;
  617. /*D2*/
  618. nist_set_384(t_d,buf,0,0,0,0,0,0,0,23,22,21,20,0);
  619. if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))
  620. --carry;
  621. /*D3*/
  622. nist_set_384(t_d,buf,0,0,0,0,0,0,0,23,23,0,0,0);
  623. if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))
  624. --carry;
  625. if (carry)
  626. {
  627. if (carry > 0)
  628. bn_sub_words(r_d, r_d, _384_data + BN_NIST_384_TOP *
  629. --carry, BN_NIST_384_TOP);
  630. else
  631. {
  632. carry = -carry;
  633. bn_add_words(r_d, r_d, _384_data + BN_NIST_384_TOP *
  634. --carry, BN_NIST_384_TOP);
  635. }
  636. }
  637. r->top = BN_NIST_384_TOP;
  638. bn_correct_top(r);
  639. if (BN_ucmp(r, field) >= 0)
  640. {
  641. bn_sub_words(r_d, r_d, _nist_p_384, BN_NIST_384_TOP);
  642. bn_correct_top(r);
  643. }
  644. bn_check_top(r);
  645. return 1;
  646. #else
  647. return 0;
  648. #endif
  649. }
  650. int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
  651. BN_CTX *ctx)
  652. {
  653. #if BN_BITS2 == 64
  654. #define BN_NIST_521_TOP_MASK (BN_ULONG)0x1FF
  655. #elif BN_BITS2 == 32
  656. #define BN_NIST_521_TOP_MASK (BN_ULONG)0x1FF
  657. #elif BN_BITS2 == 16
  658. #define BN_NIST_521_TOP_MASK (BN_ULONG)0x1FF
  659. #elif BN_BITS2 == 8
  660. #define BN_NIST_521_TOP_MASK (BN_ULONG)0x1
  661. #endif
  662. int top, ret = 0;
  663. BN_ULONG *r_d;
  664. BIGNUM *tmp;
  665. /* check whether a reduction is necessary */
  666. top = a->top;
  667. if (top < BN_NIST_521_TOP || ( top == BN_NIST_521_TOP &&
  668. (!(a->d[BN_NIST_521_TOP-1] & ~(BN_NIST_521_TOP_MASK)))))
  669. return (r == a)? 1 : (BN_copy(r ,a) != NULL);
  670. BN_CTX_start(ctx);
  671. tmp = BN_CTX_get(ctx);
  672. if (!tmp)
  673. goto err;
  674. if (!bn_wexpand(tmp, BN_NIST_521_TOP))
  675. goto err;
  676. nist_cp_bn(tmp->d, a->d, BN_NIST_521_TOP);
  677. tmp->top = BN_NIST_521_TOP;
  678. tmp->d[BN_NIST_521_TOP-1] &= BN_NIST_521_TOP_MASK;
  679. bn_correct_top(tmp);
  680. if (!BN_rshift(r, a, 521))
  681. goto err;
  682. if (!BN_uadd(r, tmp, r))
  683. goto err;
  684. top = r->top;
  685. r_d = r->d;
  686. if (top == BN_NIST_521_TOP &&
  687. (r_d[BN_NIST_521_TOP-1] & ~(BN_NIST_521_TOP_MASK)))
  688. {
  689. BN_NIST_ADD_ONE(r_d)
  690. r_d[BN_NIST_521_TOP-1] &= BN_NIST_521_TOP_MASK;
  691. }
  692. bn_correct_top(r);
  693. ret = 1;
  694. err:
  695. BN_CTX_end(ctx);
  696. bn_check_top(r);
  697. return ret;
  698. }