Line data Source code
1 : /* crypto/bn/bn_recp.c */
2 : /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 : * All rights reserved.
4 : *
5 : * This package is an SSL implementation written
6 : * by Eric Young (eay@cryptsoft.com).
7 : * The implementation was written so as to conform with Netscapes SSL.
8 : *
9 : * This library is free for commercial and non-commercial use as long as
10 : * the following conditions are aheared to. The following conditions
11 : * apply to all code found in this distribution, be it the RC4, RSA,
12 : * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13 : * included with this distribution is covered by the same copyright terms
14 : * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 : *
16 : * Copyright remains Eric Young's, and as such any Copyright notices in
17 : * the code are not to be removed.
18 : * If this package is used in a product, Eric Young should be given attribution
19 : * as the author of the parts of the library used.
20 : * This can be in the form of a textual message at program startup or
21 : * in documentation (online or textual) provided with the package.
22 : *
23 : * Redistribution and use in source and binary forms, with or without
24 : * modification, are permitted provided that the following conditions
25 : * are met:
26 : * 1. Redistributions of source code must retain the copyright
27 : * notice, this list of conditions and the following disclaimer.
28 : * 2. Redistributions in binary form must reproduce the above copyright
29 : * notice, this list of conditions and the following disclaimer in the
30 : * documentation and/or other materials provided with the distribution.
31 : * 3. All advertising materials mentioning features or use of this software
32 : * must display the following acknowledgement:
33 : * "This product includes cryptographic software written by
34 : * Eric Young (eay@cryptsoft.com)"
35 : * The word 'cryptographic' can be left out if the rouines from the library
36 : * being used are not cryptographic related :-).
37 : * 4. If you include any Windows specific code (or a derivative thereof) from
38 : * the apps directory (application code) you must include an acknowledgement:
39 : * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 : *
41 : * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 : * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44 : * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45 : * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46 : * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47 : * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49 : * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50 : * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 : * SUCH DAMAGE.
52 : *
53 : * The licence and distribution terms for any publically available version or
54 : * derivative of this code cannot be changed. i.e. this code cannot simply be
55 : * copied and put under another distribution licence
56 : * [including the GNU Public Licence.]
57 : */
58 :
59 : #include <stdio.h>
60 : #include "cryptlib.h"
61 : #include "bn_lcl.h"
62 :
63 0 : void BN_RECP_CTX_init(BN_RECP_CTX *recp)
64 : {
65 0 : BN_init(&(recp->N));
66 0 : BN_init(&(recp->Nr));
67 0 : recp->num_bits = 0;
68 0 : recp->flags = 0;
69 0 : }
70 :
71 0 : BN_RECP_CTX *BN_RECP_CTX_new(void)
72 : {
73 : BN_RECP_CTX *ret;
74 :
75 0 : if ((ret = (BN_RECP_CTX *)OPENSSL_malloc(sizeof(BN_RECP_CTX))) == NULL)
76 : return (NULL);
77 :
78 : BN_RECP_CTX_init(ret);
79 0 : ret->flags = BN_FLG_MALLOCED;
80 0 : return (ret);
81 : }
82 :
83 0 : void BN_RECP_CTX_free(BN_RECP_CTX *recp)
84 : {
85 0 : if (recp == NULL)
86 0 : return;
87 :
88 0 : BN_free(&(recp->N));
89 0 : BN_free(&(recp->Nr));
90 0 : if (recp->flags & BN_FLG_MALLOCED)
91 0 : OPENSSL_free(recp);
92 : }
93 :
94 0 : int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx)
95 : {
96 0 : if (!BN_copy(&(recp->N), d))
97 : return 0;
98 0 : BN_zero(&(recp->Nr));
99 0 : recp->num_bits = BN_num_bits(d);
100 0 : recp->shift = 0;
101 0 : return (1);
102 : }
103 :
104 0 : int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y,
105 : BN_RECP_CTX *recp, BN_CTX *ctx)
106 : {
107 : int ret = 0;
108 : BIGNUM *a;
109 : const BIGNUM *ca;
110 :
111 0 : BN_CTX_start(ctx);
112 0 : if ((a = BN_CTX_get(ctx)) == NULL)
113 : goto err;
114 0 : if (y != NULL) {
115 0 : if (x == y) {
116 0 : if (!BN_sqr(a, x, ctx))
117 : goto err;
118 : } else {
119 0 : if (!BN_mul(a, x, y, ctx))
120 : goto err;
121 : }
122 : ca = a;
123 : } else
124 : ca = x; /* Just do the mod */
125 :
126 0 : ret = BN_div_recp(NULL, r, ca, recp, ctx);
127 : err:
128 0 : BN_CTX_end(ctx);
129 : bn_check_top(r);
130 0 : return (ret);
131 : }
132 :
133 0 : int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,
134 : BN_RECP_CTX *recp, BN_CTX *ctx)
135 : {
136 : int i, j, ret = 0;
137 : BIGNUM *a, *b, *d, *r;
138 :
139 0 : BN_CTX_start(ctx);
140 0 : a = BN_CTX_get(ctx);
141 0 : b = BN_CTX_get(ctx);
142 0 : if (dv != NULL)
143 : d = dv;
144 : else
145 0 : d = BN_CTX_get(ctx);
146 0 : if (rem != NULL)
147 : r = rem;
148 : else
149 0 : r = BN_CTX_get(ctx);
150 0 : if (a == NULL || b == NULL || d == NULL || r == NULL)
151 : goto err;
152 :
153 0 : if (BN_ucmp(m, &(recp->N)) < 0) {
154 0 : BN_zero(d);
155 0 : if (!BN_copy(r, m))
156 : return 0;
157 0 : BN_CTX_end(ctx);
158 0 : return (1);
159 : }
160 :
161 : /*
162 : * We want the remainder Given input of ABCDEF / ab we need multiply
163 : * ABCDEF by 3 digests of the reciprocal of ab
164 : */
165 :
166 : /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */
167 0 : i = BN_num_bits(m);
168 0 : j = recp->num_bits << 1;
169 0 : if (j > i)
170 : i = j;
171 :
172 : /* Nr := round(2^i / N) */
173 0 : if (i != recp->shift)
174 0 : recp->shift = BN_reciprocal(&(recp->Nr), &(recp->N), i, ctx);
175 : /* BN_reciprocal could have returned -1 for an error */
176 0 : if (recp->shift == -1)
177 : goto err;
178 :
179 : /*-
180 : * d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|
181 : * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|
182 : * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
183 : * = |m/N|
184 : */
185 0 : if (!BN_rshift(a, m, recp->num_bits))
186 : goto err;
187 0 : if (!BN_mul(b, a, &(recp->Nr), ctx))
188 : goto err;
189 0 : if (!BN_rshift(d, b, i - recp->num_bits))
190 : goto err;
191 0 : d->neg = 0;
192 :
193 0 : if (!BN_mul(b, &(recp->N), d, ctx))
194 : goto err;
195 0 : if (!BN_usub(r, m, b))
196 : goto err;
197 0 : r->neg = 0;
198 :
199 : #if 1
200 : j = 0;
201 0 : while (BN_ucmp(r, &(recp->N)) >= 0) {
202 0 : if (j++ > 2) {
203 0 : BNerr(BN_F_BN_DIV_RECP, BN_R_BAD_RECIPROCAL);
204 0 : goto err;
205 : }
206 0 : if (!BN_usub(r, r, &(recp->N)))
207 : goto err;
208 0 : if (!BN_add_word(d, 1))
209 : goto err;
210 : }
211 : #endif
212 :
213 0 : r->neg = BN_is_zero(r) ? 0 : m->neg;
214 0 : d->neg = m->neg ^ recp->N.neg;
215 : ret = 1;
216 : err:
217 0 : BN_CTX_end(ctx);
218 : bn_check_top(dv);
219 : bn_check_top(rem);
220 0 : return (ret);
221 : }
222 :
223 : /*
224 : * len is the expected size of the result We actually calculate with an extra
225 : * word of precision, so we can do faster division if the remainder is not
226 : * required.
227 : */
228 : /* r := 2^len / m */
229 0 : int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx)
230 : {
231 : int ret = -1;
232 : BIGNUM *t;
233 :
234 0 : BN_CTX_start(ctx);
235 0 : if ((t = BN_CTX_get(ctx)) == NULL)
236 : goto err;
237 :
238 0 : if (!BN_set_bit(t, len))
239 : goto err;
240 :
241 0 : if (!BN_div(r, NULL, t, m, ctx))
242 : goto err;
243 :
244 : ret = len;
245 : err:
246 : bn_check_top(r);
247 0 : BN_CTX_end(ctx);
248 0 : return (ret);
249 : }
|
