1 /*
2 * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the OpenSSL license (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10 #include "internal/cryptlib.h"
11 #include "bn_local.h"
12
BN_RECP_CTX_init(BN_RECP_CTX * recp)13 void BN_RECP_CTX_init(BN_RECP_CTX *recp)
14 {
15 memset(recp, 0, sizeof(*recp));
16 bn_init(&(recp->N));
17 bn_init(&(recp->Nr));
18 }
19
BN_RECP_CTX_new(void)20 BN_RECP_CTX *BN_RECP_CTX_new(void)
21 {
22 BN_RECP_CTX *ret;
23
24 if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
25 BNerr(BN_F_BN_RECP_CTX_NEW, ERR_R_MALLOC_FAILURE);
26 return NULL;
27 }
28
29 bn_init(&(ret->N));
30 bn_init(&(ret->Nr));
31 ret->flags = BN_FLG_MALLOCED;
32 return ret;
33 }
34
BN_RECP_CTX_free(BN_RECP_CTX * recp)35 void BN_RECP_CTX_free(BN_RECP_CTX *recp)
36 {
37 if (recp == NULL)
38 return;
39 BN_free(&recp->N);
40 BN_free(&recp->Nr);
41 if (recp->flags & BN_FLG_MALLOCED)
42 OPENSSL_free(recp);
43 }
44
BN_RECP_CTX_set(BN_RECP_CTX * recp,const BIGNUM * d,BN_CTX * ctx)45 int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx)
46 {
47 if (!BN_copy(&(recp->N), d))
48 return 0;
49 BN_zero(&(recp->Nr));
50 recp->num_bits = BN_num_bits(d);
51 recp->shift = 0;
52 return 1;
53 }
54
BN_mod_mul_reciprocal(BIGNUM * r,const BIGNUM * x,const BIGNUM * y,BN_RECP_CTX * recp,BN_CTX * ctx)55 int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y,
56 BN_RECP_CTX *recp, BN_CTX *ctx)
57 {
58 int ret = 0;
59 BIGNUM *a;
60 const BIGNUM *ca;
61
62 BN_CTX_start(ctx);
63 if ((a = BN_CTX_get(ctx)) == NULL)
64 goto err;
65 if (y != NULL) {
66 if (x == y) {
67 if (!BN_sqr(a, x, ctx))
68 goto err;
69 } else {
70 if (!BN_mul(a, x, y, ctx))
71 goto err;
72 }
73 ca = a;
74 } else
75 ca = x; /* Just do the mod */
76
77 ret = BN_div_recp(NULL, r, ca, recp, ctx);
78 err:
79 BN_CTX_end(ctx);
80 bn_check_top(r);
81 return ret;
82 }
83
BN_div_recp(BIGNUM * dv,BIGNUM * rem,const BIGNUM * m,BN_RECP_CTX * recp,BN_CTX * ctx)84 int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,
85 BN_RECP_CTX *recp, BN_CTX *ctx)
86 {
87 int i, j, ret = 0;
88 BIGNUM *a, *b, *d, *r;
89
90 BN_CTX_start(ctx);
91 d = (dv != NULL) ? dv : BN_CTX_get(ctx);
92 r = (rem != NULL) ? rem : BN_CTX_get(ctx);
93 a = BN_CTX_get(ctx);
94 b = BN_CTX_get(ctx);
95 if (b == NULL)
96 goto err;
97
98 if (BN_ucmp(m, &(recp->N)) < 0) {
99 BN_zero(d);
100 if (!BN_copy(r, m)) {
101 BN_CTX_end(ctx);
102 return 0;
103 }
104 BN_CTX_end(ctx);
105 return 1;
106 }
107
108 /*
109 * We want the remainder Given input of ABCDEF / ab we need multiply
110 * ABCDEF by 3 digests of the reciprocal of ab
111 */
112
113 /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */
114 i = BN_num_bits(m);
115 j = recp->num_bits << 1;
116 if (j > i)
117 i = j;
118
119 /* Nr := round(2^i / N) */
120 if (i != recp->shift)
121 recp->shift = BN_reciprocal(&(recp->Nr), &(recp->N), i, ctx);
122 /* BN_reciprocal could have returned -1 for an error */
123 if (recp->shift == -1)
124 goto err;
125
126 /*-
127 * d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|
128 * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|
129 * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
130 * = |m/N|
131 */
132 if (!BN_rshift(a, m, recp->num_bits))
133 goto err;
134 if (!BN_mul(b, a, &(recp->Nr), ctx))
135 goto err;
136 if (!BN_rshift(d, b, i - recp->num_bits))
137 goto err;
138 d->neg = 0;
139
140 if (!BN_mul(b, &(recp->N), d, ctx))
141 goto err;
142 if (!BN_usub(r, m, b))
143 goto err;
144 r->neg = 0;
145
146 j = 0;
147 while (BN_ucmp(r, &(recp->N)) >= 0) {
148 if (j++ > 2) {
149 BNerr(BN_F_BN_DIV_RECP, BN_R_BAD_RECIPROCAL);
150 goto err;
151 }
152 if (!BN_usub(r, r, &(recp->N)))
153 goto err;
154 if (!BN_add_word(d, 1))
155 goto err;
156 }
157
158 r->neg = BN_is_zero(r) ? 0 : m->neg;
159 d->neg = m->neg ^ recp->N.neg;
160 ret = 1;
161 err:
162 BN_CTX_end(ctx);
163 bn_check_top(dv);
164 bn_check_top(rem);
165 return ret;
166 }
167
168 /*
169 * len is the expected size of the result We actually calculate with an extra
170 * word of precision, so we can do faster division if the remainder is not
171 * required.
172 */
173 /* r := 2^len / m */
BN_reciprocal(BIGNUM * r,const BIGNUM * m,int len,BN_CTX * ctx)174 int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx)
175 {
176 int ret = -1;
177 BIGNUM *t;
178
179 BN_CTX_start(ctx);
180 if ((t = BN_CTX_get(ctx)) == NULL)
181 goto err;
182
183 if (!BN_set_bit(t, len))
184 goto err;
185
186 if (!BN_div(r, NULL, t, m, ctx))
187 goto err;
188
189 ret = len;
190 err:
191 bn_check_top(r);
192 BN_CTX_end(ctx);
193 return ret;
194 }
195