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