Branch data 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 : : #define OPENSSL_FIPSAPI
60 : :
61 : : #include <stdio.h>
62 : : #include "cryptlib.h"
63 : : #include "bn_lcl.h"
64 : :
65 : 301 : void BN_RECP_CTX_init(BN_RECP_CTX *recp)
66 : : {
67 : 301 : BN_init(&(recp->N));
68 : 301 : BN_init(&(recp->Nr));
69 : 301 : recp->num_bits=0;
70 : 301 : recp->flags=0;
71 : 301 : }
72 : :
73 : 0 : BN_RECP_CTX *BN_RECP_CTX_new(void)
74 : : {
75 : : BN_RECP_CTX *ret;
76 : :
77 [ # # ]: 0 : if ((ret=(BN_RECP_CTX *)OPENSSL_malloc(sizeof(BN_RECP_CTX))) == NULL)
78 : : return(NULL);
79 : :
80 : 0 : BN_RECP_CTX_init(ret);
81 : 0 : ret->flags=BN_FLG_MALLOCED;
82 : 0 : return(ret);
83 : : }
84 : :
85 : 301 : void BN_RECP_CTX_free(BN_RECP_CTX *recp)
86 : : {
87 [ + - ]: 301 : if(recp == NULL)
88 : 301 : return;
89 : :
90 : 301 : BN_free(&(recp->N));
91 : 301 : BN_free(&(recp->Nr));
92 [ - + ]: 301 : if (recp->flags & BN_FLG_MALLOCED)
93 : 0 : OPENSSL_free(recp);
94 : : }
95 : :
96 : 450 : int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx)
97 : : {
98 [ + - ]: 450 : if (!BN_copy(&(recp->N),d)) return 0;
99 : 450 : BN_zero(&(recp->Nr));
100 : 450 : recp->num_bits=BN_num_bits(d);
101 : 450 : recp->shift=0;
102 : 450 : return(1);
103 : : }
104 : :
105 : 137905 : int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y,
106 : : BN_RECP_CTX *recp, BN_CTX *ctx)
107 : : {
108 : 137905 : int ret=0;
109 : : BIGNUM *a;
110 : : const BIGNUM *ca;
111 : :
112 : 137905 : BN_CTX_start(ctx);
113 [ + - ]: 137905 : if ((a = BN_CTX_get(ctx)) == NULL) goto err;
114 [ + - ]: 137905 : if (y != NULL)
115 : : {
116 [ + + ]: 137905 : if (x == y)
117 [ + - ]: 114198 : { if (!BN_sqr(a,x,ctx)) goto err; }
118 : : else
119 [ + - ]: 23707 : { if (!BN_mul(a,x,y,ctx)) goto err; }
120 : 137905 : ca = a;
121 : : }
122 : : else
123 : : ca=x; /* Just do the mod */
124 : :
125 : 137905 : ret = BN_div_recp(NULL,r,ca,recp,ctx);
126 : : err:
127 : 137905 : BN_CTX_end(ctx);
128 : : bn_check_top(r);
129 : 137905 : return(ret);
130 : : }
131 : :
132 : 138055 : int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,
133 : : BN_RECP_CTX *recp, BN_CTX *ctx)
134 : : {
135 : 138055 : int i,j,ret=0;
136 : : BIGNUM *a,*b,*d,*r;
137 : :
138 : 138055 : BN_CTX_start(ctx);
139 : 138055 : a=BN_CTX_get(ctx);
140 : 138055 : b=BN_CTX_get(ctx);
141 [ + + ]: 138055 : if (dv != NULL)
142 : : d=dv;
143 : : else
144 : 137905 : d=BN_CTX_get(ctx);
145 [ - + ]: 138055 : if (rem != NULL)
146 : : r=rem;
147 : : else
148 : 0 : r=BN_CTX_get(ctx);
149 [ + - ][ + - ]: 138055 : if (a == NULL || b == NULL || d == NULL || r == NULL) goto err;
150 : :
151 [ + + ]: 138055 : if (BN_ucmp(m,&(recp->N)) < 0)
152 : : {
153 : 321 : BN_zero(d);
154 [ + - ]: 321 : if (!BN_copy(r,m)) return 0;
155 : 321 : BN_CTX_end(ctx);
156 : 321 : return(1);
157 : : }
158 : :
159 : : /* We want the remainder
160 : : * Given input of ABCDEF / ab
161 : : * we need multiply ABCDEF by 3 digests of the reciprocal of ab
162 : : *
163 : : */
164 : :
165 : : /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */
166 : 137734 : i=BN_num_bits(m);
167 : 137734 : j=recp->num_bits<<1;
168 [ + + ]: 137734 : if (j>i) i=j;
169 : :
170 : : /* Nr := round(2^i / N) */
171 [ + + ]: 137734 : if (i != recp->shift)
172 : 450 : recp->shift=BN_reciprocal(&(recp->Nr),&(recp->N),
173 : : i,ctx); /* BN_reciprocal returns i, or -1 for an error */
174 [ + - ]: 137734 : if (recp->shift == -1) goto err;
175 : :
176 : : /* d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|
177 : : * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|
178 : : * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
179 : : * = |m/N|
180 : : */
181 [ + - ]: 137734 : if (!BN_rshift(a,m,recp->num_bits)) goto err;
182 [ + - ]: 137734 : if (!BN_mul(b,a,&(recp->Nr),ctx)) goto err;
183 [ + - ]: 137734 : if (!BN_rshift(d,b,i-recp->num_bits)) goto err;
184 : 137734 : d->neg=0;
185 : :
186 [ + - ]: 137734 : if (!BN_mul(b,&(recp->N),d,ctx)) goto err;
187 [ + - ]: 137734 : if (!BN_usub(r,m,b)) goto err;
188 : 137734 : r->neg=0;
189 : :
190 : : #if 1
191 : 137734 : j=0;
192 [ + + ]: 237863 : while (BN_ucmp(r,&(recp->N)) >= 0)
193 : : {
194 [ - + ]: 100129 : if (j++ > 2)
195 : : {
196 : 0 : BNerr(BN_F_BN_DIV_RECP,BN_R_BAD_RECIPROCAL);
197 : 0 : goto err;
198 : : }
199 [ + - ]: 100129 : if (!BN_usub(r,r,&(recp->N))) goto err;
200 [ + - ]: 100129 : if (!BN_add_word(d,1)) goto err;
201 : : }
202 : : #endif
203 : :
204 [ + + ]: 137734 : r->neg=BN_is_zero(r)?0:m->neg;
205 : 137734 : d->neg=m->neg^recp->N.neg;
206 : 137734 : ret=1;
207 : : err:
208 : 137734 : BN_CTX_end(ctx);
209 : : bn_check_top(dv);
210 : : bn_check_top(rem);
211 : 137734 : return(ret);
212 : : }
213 : :
214 : : /* len is the expected size of the result
215 : : * We actually calculate with an extra word of precision, so
216 : : * we can do faster division if the remainder is not required.
217 : : */
218 : : /* r := 2^len / m */
219 : 450 : int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx)
220 : : {
221 : 450 : int ret= -1;
222 : : BIGNUM *t;
223 : :
224 : 450 : BN_CTX_start(ctx);
225 [ + - ]: 450 : if((t = BN_CTX_get(ctx)) == NULL) goto err;
226 : :
227 [ + - ]: 450 : if (!BN_set_bit(t,len)) goto err;
228 : :
229 [ + - ]: 450 : if (!BN_div(r,NULL,t,m,ctx)) goto err;
230 : :
231 : 450 : ret=len;
232 : : err:
233 : : bn_check_top(r);
234 : 450 : BN_CTX_end(ctx);
235 : 450 : return(ret);
236 : : }
|
