bn_mod.c
上传用户:yisoukefu
上传日期:2020-08-09
资源大小:39506k
文件大小:9k
源码类别:

其他游戏

开发平台:

Visual C++

  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. #include "cryptlib.h"
  114. #include "bn_lcl.h"
  115. #if 0 /* now just a #define */
  116. int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
  117. {
  118. return(BN_div(NULL,rem,m,d,ctx));
  119. /* note that  rem->neg == m->neg  (unless the remainder is zero) */
  120. }
  121. #endif
  122. int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
  123. {
  124. /* like BN_mod, but returns non-negative remainder
  125.  * (i.e.,  0 <= r < |d|  always holds) */
  126. if (!(BN_mod(r,m,d,ctx)))
  127. return 0;
  128. if (!r->neg)
  129. return 1;
  130. /* now   -|d| < r < 0,  so we have to set  r := r + |d| */
  131. return (d->neg ? BN_sub : BN_add)(r, r, d);
  132. }
  133. int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
  134. {
  135. if (!BN_add(r, a, b)) return 0;
  136. return BN_nnmod(r, r, m, ctx);
  137. }
  138. /* BN_mod_add variant that may be used if both  a  and  b  are non-negative
  139.  * and less than  m */
  140. int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)
  141. {
  142. if (!BN_uadd(r, a, b)) return 0;
  143. if (BN_ucmp(r, m) >= 0)
  144. return BN_usub(r, r, m);
  145. return 1;
  146. }
  147. int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
  148. {
  149. if (!BN_sub(r, a, b)) return 0;
  150. return BN_nnmod(r, r, m, ctx);
  151. }
  152. /* BN_mod_sub variant that may be used if both  a  and  b  are non-negative
  153.  * and less than  m */
  154. int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)
  155. {
  156. if (!BN_sub(r, a, b)) return 0;
  157. if (r->neg)
  158. return BN_add(r, r, m);
  159. return 1;
  160. }
  161. /* slow but works */
  162. int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
  163. BN_CTX *ctx)
  164. {
  165. BIGNUM *t;
  166. int ret=0;
  167. bn_check_top(a);
  168. bn_check_top(b);
  169. bn_check_top(m);
  170. BN_CTX_start(ctx);
  171. if ((t = BN_CTX_get(ctx)) == NULL) goto err;
  172. if (a == b)
  173. { if (!BN_sqr(t,a,ctx)) goto err; }
  174. else
  175. { if (!BN_mul(t,a,b,ctx)) goto err; }
  176. if (!BN_nnmod(r,t,m,ctx)) goto err;
  177. bn_check_top(r);
  178. ret=1;
  179. err:
  180. BN_CTX_end(ctx);
  181. return(ret);
  182. }
  183. int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
  184. {
  185. if (!BN_sqr(r, a, ctx)) return 0;
  186. /* r->neg == 0,  thus we don't need BN_nnmod */
  187. return BN_mod(r, r, m, ctx);
  188. }
  189. int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
  190. {
  191. if (!BN_lshift1(r, a)) return 0;
  192. bn_check_top(r);
  193. return BN_nnmod(r, r, m, ctx);
  194. }
  195. /* BN_mod_lshift1 variant that may be used if  a  is non-negative
  196.  * and less than  m */
  197. int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
  198. {
  199. if (!BN_lshift1(r, a)) return 0;
  200. bn_check_top(r);
  201. if (BN_cmp(r, m) >= 0)
  202. return BN_sub(r, r, m);
  203. return 1;
  204. }
  205. int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx)
  206. {
  207. BIGNUM *abs_m = NULL;
  208. int ret;
  209. if (!BN_nnmod(r, a, m, ctx)) return 0;
  210. if (m->neg)
  211. {
  212. abs_m = BN_dup(m);
  213. if (abs_m == NULL) return 0;
  214. abs_m->neg = 0;
  215. }
  216. ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
  217. bn_check_top(r);
  218. if (abs_m)
  219. BN_free(abs_m);
  220. return ret;
  221. }
  222. /* BN_mod_lshift variant that may be used if  a  is non-negative
  223.  * and less than  m */
  224. int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
  225. {
  226. if (r != a)
  227. {
  228. if (BN_copy(r, a) == NULL) return 0;
  229. }
  230. while (n > 0)
  231. {
  232. int max_shift;
  233. /* 0 < r < m */
  234. max_shift = BN_num_bits(m) - BN_num_bits(r);
  235. /* max_shift >= 0 */
  236. if (max_shift < 0)
  237. {
  238. BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
  239. return 0;
  240. }
  241. if (max_shift > n)
  242. max_shift = n;
  243. if (max_shift)
  244. {
  245. if (!BN_lshift(r, r, max_shift)) return 0;
  246. n -= max_shift;
  247. }
  248. else
  249. {
  250. if (!BN_lshift1(r, r)) return 0;
  251. --n;
  252. }
  253. /* BN_num_bits(r) <= BN_num_bits(m) */
  254. if (BN_cmp(r, m) >= 0) 
  255. {
  256. if (!BN_sub(r, r, m)) return 0;
  257. }
  258. }
  259. bn_check_top(r);
  260. return 1;
  261. }