bn_mod.c 9.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303
  1. /* crypto/bn/bn_mod.c */
  2. /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
  3. * for the OpenSSL project. */
  4. /* ====================================================================
  5. * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved.
  6. *
  7. * Redistribution and use in source and binary forms, with or without
  8. * modification, are permitted provided that the following conditions
  9. * are met:
  10. *
  11. * 1. Redistributions of source code must retain the above copyright
  12. * notice, this list of conditions and the following disclaimer.
  13. *
  14. * 2. Redistributions in binary form must reproduce the above copyright
  15. * notice, this list of conditions and the following disclaimer in
  16. * the documentation and/or other materials provided with the
  17. * distribution.
  18. *
  19. * 3. All advertising materials mentioning features or use of this
  20. * software must display the following acknowledgment:
  21. * "This product includes software developed by the OpenSSL Project
  22. * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  23. *
  24. * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  25. * endorse or promote products derived from this software without
  26. * prior written permission. For written permission, please contact
  27. * openssl-core@openssl.org.
  28. *
  29. * 5. Products derived from this software may not be called "OpenSSL"
  30. * nor may "OpenSSL" appear in their names without prior written
  31. * permission of the OpenSSL Project.
  32. *
  33. * 6. Redistributions of any form whatsoever must retain the following
  34. * acknowledgment:
  35. * "This product includes software developed by the OpenSSL Project
  36. * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  37. *
  38. * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  39. * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  40. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  41. * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
  42. * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  43. * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  44. * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  45. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  46. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  47. * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  48. * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  49. * OF THE POSSIBILITY OF SUCH DAMAGE.
  50. * ====================================================================
  51. *
  52. * This product includes cryptographic software written by Eric Young
  53. * (eay@cryptsoft.com). This product includes software written by Tim
  54. * Hudson (tjh@cryptsoft.com).
  55. *
  56. */
  57. /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  58. * All rights reserved.
  59. *
  60. * This package is an SSL implementation written
  61. * by Eric Young (eay@cryptsoft.com).
  62. * The implementation was written so as to conform with Netscapes SSL.
  63. *
  64. * This library is free for commercial and non-commercial use as long as
  65. * the following conditions are aheared to. The following conditions
  66. * apply to all code found in this distribution, be it the RC4, RSA,
  67. * lhash, DES, etc., code; not just the SSL code. The SSL documentation
  68. * included with this distribution is covered by the same copyright terms
  69. * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  70. *
  71. * Copyright remains Eric Young's, and as such any Copyright notices in
  72. * the code are not to be removed.
  73. * If this package is used in a product, Eric Young should be given attribution
  74. * as the author of the parts of the library used.
  75. * This can be in the form of a textual message at program startup or
  76. * in documentation (online or textual) provided with the package.
  77. *
  78. * Redistribution and use in source and binary forms, with or without
  79. * modification, are permitted provided that the following conditions
  80. * are met:
  81. * 1. Redistributions of source code must retain the copyright
  82. * notice, this list of conditions and the following disclaimer.
  83. * 2. Redistributions in binary form must reproduce the above copyright
  84. * notice, this list of conditions and the following disclaimer in the
  85. * documentation and/or other materials provided with the distribution.
  86. * 3. All advertising materials mentioning features or use of this software
  87. * must display the following acknowledgement:
  88. * "This product includes cryptographic software written by
  89. * Eric Young (eay@cryptsoft.com)"
  90. * The word 'cryptographic' can be left out if the rouines from the library
  91. * being used are not cryptographic related :-).
  92. * 4. If you include any Windows specific code (or a derivative thereof) from
  93. * the apps directory (application code) you must include an acknowledgement:
  94. * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  95. *
  96. * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  97. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  98. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  99. * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  100. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  101. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  102. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  103. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  104. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  105. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  106. * SUCH DAMAGE.
  107. *
  108. * The licence and distribution terms for any publically available version or
  109. * derivative of this code cannot be changed. i.e. this code cannot simply be
  110. * copied and put under another distribution licence
  111. * [including the GNU Public Licence.]
  112. */
  113. #define OPENSSL_FIPSAPI
  114. #include "cryptlib.h"
  115. #include "bn_lcl.h"
  116. #if 0 /* now just a #define */
  117. int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
  118. {
  119. return(BN_div(NULL,rem,m,d,ctx));
  120. /* note that rem->neg == m->neg (unless the remainder is zero) */
  121. }
  122. #endif
  123. int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
  124. {
  125. /* like BN_mod, but returns non-negative remainder
  126. * (i.e., 0 <= r < |d| always holds) */
  127. if (!(BN_mod(r,m,d,ctx)))
  128. return 0;
  129. if (!r->neg)
  130. return 1;
  131. /* now -|d| < r < 0, so we have to set r := r + |d| */
  132. return (d->neg ? BN_sub : BN_add)(r, r, d);
  133. }
  134. int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
  135. {
  136. if (!BN_add(r, a, b)) return 0;
  137. return BN_nnmod(r, r, m, ctx);
  138. }
  139. /* BN_mod_add variant that may be used if both a and b are non-negative
  140. * and less than m */
  141. int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)
  142. {
  143. if (!BN_uadd(r, a, b)) return 0;
  144. if (BN_ucmp(r, m) >= 0)
  145. return BN_usub(r, r, m);
  146. return 1;
  147. }
  148. int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
  149. {
  150. if (!BN_sub(r, a, b)) return 0;
  151. return BN_nnmod(r, r, m, ctx);
  152. }
  153. /* BN_mod_sub variant that may be used if both a and b are non-negative
  154. * and less than m */
  155. int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)
  156. {
  157. if (!BN_sub(r, a, b)) return 0;
  158. if (r->neg)
  159. return BN_add(r, r, m);
  160. return 1;
  161. }
  162. /* slow but works */
  163. int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
  164. BN_CTX *ctx)
  165. {
  166. BIGNUM *t;
  167. int ret=0;
  168. bn_check_top(a);
  169. bn_check_top(b);
  170. bn_check_top(m);
  171. BN_CTX_start(ctx);
  172. if ((t = BN_CTX_get(ctx)) == NULL) goto err;
  173. if (a == b)
  174. { if (!BN_sqr(t,a,ctx)) goto err; }
  175. else
  176. { if (!BN_mul(t,a,b,ctx)) goto err; }
  177. if (!BN_nnmod(r,t,m,ctx)) goto err;
  178. bn_check_top(r);
  179. ret=1;
  180. err:
  181. BN_CTX_end(ctx);
  182. return(ret);
  183. }
  184. int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
  185. {
  186. if (!BN_sqr(r, a, ctx)) return 0;
  187. /* r->neg == 0, thus we don't need BN_nnmod */
  188. return BN_mod(r, r, m, ctx);
  189. }
  190. int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
  191. {
  192. if (!BN_lshift1(r, a)) return 0;
  193. bn_check_top(r);
  194. return BN_nnmod(r, r, m, ctx);
  195. }
  196. /* BN_mod_lshift1 variant that may be used if a is non-negative
  197. * and less than m */
  198. int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
  199. {
  200. if (!BN_lshift1(r, a)) return 0;
  201. bn_check_top(r);
  202. if (BN_cmp(r, m) >= 0)
  203. return BN_sub(r, r, m);
  204. return 1;
  205. }
  206. int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx)
  207. {
  208. BIGNUM *abs_m = NULL;
  209. int ret;
  210. if (!BN_nnmod(r, a, m, ctx)) return 0;
  211. if (m->neg)
  212. {
  213. abs_m = BN_dup(m);
  214. if (abs_m == NULL) return 0;
  215. abs_m->neg = 0;
  216. }
  217. ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
  218. bn_check_top(r);
  219. if (abs_m)
  220. BN_free(abs_m);
  221. return ret;
  222. }
  223. /* BN_mod_lshift variant that may be used if a is non-negative
  224. * and less than m */
  225. int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
  226. {
  227. if (r != a)
  228. {
  229. if (BN_copy(r, a) == NULL) return 0;
  230. }
  231. while (n > 0)
  232. {
  233. int max_shift;
  234. /* 0 < r < m */
  235. max_shift = BN_num_bits(m) - BN_num_bits(r);
  236. /* max_shift >= 0 */
  237. if (max_shift < 0)
  238. {
  239. BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
  240. return 0;
  241. }
  242. if (max_shift > n)
  243. max_shift = n;
  244. if (max_shift)
  245. {
  246. if (!BN_lshift(r, r, max_shift)) return 0;
  247. n -= max_shift;
  248. }
  249. else
  250. {
  251. if (!BN_lshift1(r, r)) return 0;
  252. --n;
  253. }
  254. /* BN_num_bits(r) <= BN_num_bits(m) */
  255. if (BN_cmp(r, m) >= 0)
  256. {
  257. if (!BN_sub(r, r, m)) return 0;
  258. }
  259. }
  260. bn_check_top(r);
  261. return 1;
  262. }