/src/libressl/crypto/bn/bn_recp.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* $OpenBSD: bn_recp.c,v 1.33 2025/02/04 20:22:20 tb Exp $ */ |
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 | | |
61 | | #include <openssl/err.h> |
62 | | |
63 | | #include "bn_local.h" |
64 | | |
65 | | struct bn_recp_ctx_st { |
66 | | BIGNUM *N; /* the divisor */ |
67 | | BIGNUM *Nr; /* the reciprocal 2^shift / N */ |
68 | | int num_bits; /* number of bits in N */ |
69 | | int shift; |
70 | | } /* BN_RECP_CTX */; |
71 | | |
72 | | BN_RECP_CTX * |
73 | | BN_RECP_CTX_create(const BIGNUM *N) |
74 | 922 | { |
75 | 922 | BN_RECP_CTX *recp; |
76 | | |
77 | 922 | if ((recp = calloc(1, sizeof(*recp))) == NULL) |
78 | 0 | goto err; |
79 | | |
80 | 922 | if ((recp->N = BN_dup(N)) == NULL) |
81 | 0 | goto err; |
82 | 922 | BN_set_negative(recp->N, 0); |
83 | 922 | recp->num_bits = BN_num_bits(recp->N); |
84 | | |
85 | 922 | if ((recp->Nr = BN_new()) == NULL) |
86 | 0 | goto err; |
87 | | |
88 | 922 | return recp; |
89 | | |
90 | 0 | err: |
91 | 0 | BN_RECP_CTX_free(recp); |
92 | |
|
93 | 0 | return NULL; |
94 | 922 | } |
95 | | |
96 | | void |
97 | | BN_RECP_CTX_free(BN_RECP_CTX *recp) |
98 | 922 | { |
99 | 922 | if (recp == NULL) |
100 | 0 | return; |
101 | | |
102 | 922 | BN_free(recp->N); |
103 | 922 | BN_free(recp->Nr); |
104 | 922 | freezero(recp, sizeof(*recp)); |
105 | 922 | } |
106 | | |
107 | | int |
108 | | BN_div_reciprocal(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, BN_RECP_CTX *recp, |
109 | | BN_CTX *ctx) |
110 | 197k | { |
111 | 197k | int i, j, ret = 0; |
112 | 197k | BIGNUM *a, *b, *d, *r; |
113 | | |
114 | 197k | if (BN_ucmp(m, recp->N) < 0) { |
115 | 12.7k | if (dv != NULL) |
116 | 0 | BN_zero(dv); |
117 | 12.7k | if (rem != NULL) |
118 | 12.7k | return bn_copy(rem, m); |
119 | 0 | return 1; |
120 | 12.7k | } |
121 | | |
122 | 184k | BN_CTX_start(ctx); |
123 | 184k | if ((a = BN_CTX_get(ctx)) == NULL) |
124 | 0 | goto err; |
125 | 184k | if ((b = BN_CTX_get(ctx)) == NULL) |
126 | 0 | goto err; |
127 | | |
128 | 184k | if ((d = dv) == NULL) |
129 | 184k | d = BN_CTX_get(ctx); |
130 | 184k | if (d == NULL) |
131 | 0 | goto err; |
132 | | |
133 | 184k | if ((r = rem) == NULL) |
134 | 0 | r = BN_CTX_get(ctx); |
135 | 184k | if (r == NULL) |
136 | 0 | goto err; |
137 | | |
138 | | /* |
139 | | * We want the remainder. Given input of ABCDEF / ab we need to |
140 | | * multiply ABCDEF by 3 digits of the reciprocal of ab. |
141 | | */ |
142 | | |
143 | | /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */ |
144 | 184k | i = BN_num_bits(m); |
145 | 184k | j = recp->num_bits << 1; |
146 | 184k | if (j > i) |
147 | 169k | i = j; |
148 | | |
149 | | /* Compute Nr := (1 << i) / N if necessary. */ |
150 | 184k | if (i != recp->shift) { |
151 | 851 | BN_zero(recp->Nr); |
152 | 851 | if (!BN_set_bit(recp->Nr, i)) |
153 | 0 | goto err; |
154 | 851 | if (!BN_div_ct(recp->Nr, NULL, recp->Nr, recp->N, ctx)) |
155 | 0 | goto err; |
156 | 851 | recp->shift = i; |
157 | 851 | } |
158 | | |
159 | | /* |
160 | | * d := |((m >> BN_num_bits(N)) * recp->Nr) >> (i - BN_num_bits(N))| |
161 | | * = |((m >> BN_num_bits(N)) * (1 << i) / N) >> (i - BN_num_bits(N))| |
162 | | * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * 2^BN_num_bits(N) / 2^i | |
163 | | * = |m / N| |
164 | | */ |
165 | 184k | if (!BN_rshift(a, m, recp->num_bits)) |
166 | 0 | goto err; |
167 | 184k | if (!BN_mul(b, a, recp->Nr, ctx)) |
168 | 0 | goto err; |
169 | 184k | if (!BN_rshift(d, b, i - recp->num_bits)) |
170 | 0 | goto err; |
171 | 184k | d->neg = 0; |
172 | | |
173 | 184k | if (!BN_mul(b, recp->N, d, ctx)) |
174 | 0 | goto err; |
175 | 184k | if (!BN_usub(r, m, b)) |
176 | 0 | goto err; |
177 | 184k | r->neg = 0; |
178 | | |
179 | 184k | #if 1 |
180 | 184k | j = 0; |
181 | 340k | while (BN_ucmp(r, recp->N) >= 0) { |
182 | 156k | if (j++ > 2) { |
183 | 0 | BNerror(BN_R_BAD_RECIPROCAL); |
184 | 0 | goto err; |
185 | 0 | } |
186 | 156k | if (!BN_usub(r, r, recp->N)) |
187 | 0 | goto err; |
188 | 156k | if (!BN_add_word(d, 1)) |
189 | 0 | goto err; |
190 | 156k | } |
191 | 184k | #endif |
192 | | |
193 | 184k | BN_set_negative(r, m->neg); |
194 | 184k | BN_set_negative(d, m->neg ^ recp->N->neg); |
195 | | |
196 | 184k | ret = 1; |
197 | | |
198 | 184k | err: |
199 | 184k | BN_CTX_end(ctx); |
200 | 184k | return ret; |
201 | 184k | } |
202 | | |
203 | | /* Compute r = (x * y) % m. */ |
204 | | int |
205 | | BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y, |
206 | | BN_RECP_CTX *recp, BN_CTX *ctx) |
207 | 28.5k | { |
208 | 28.5k | if (!BN_mul(r, x, y, ctx)) |
209 | 0 | return 0; |
210 | | |
211 | 28.5k | return BN_div_reciprocal(NULL, r, r, recp, ctx); |
212 | 28.5k | } |
213 | | |
214 | | /* Compute r = x^2 % m. */ |
215 | | int |
216 | | BN_mod_sqr_reciprocal(BIGNUM *r, const BIGNUM *x, BN_RECP_CTX *recp, BN_CTX *ctx) |
217 | 168k | { |
218 | 168k | if (!BN_sqr(r, x, ctx)) |
219 | 0 | return 0; |
220 | | |
221 | 168k | return BN_div_reciprocal(NULL, r, r, recp, ctx); |
222 | 168k | } |