summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/lib/libcrypto/bn/bn_exp.c186
-rw-r--r--src/lib/libcrypto/bn/bn_exp2.c188
2 files changed, 186 insertions, 188 deletions
diff --git a/src/lib/libcrypto/bn/bn_exp.c b/src/lib/libcrypto/bn/bn_exp.c
index b72b535962..4011bb4890 100644
--- a/src/lib/libcrypto/bn/bn_exp.c
+++ b/src/lib/libcrypto/bn/bn_exp.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_exp.c,v 1.36 2023/02/03 05:27:50 jsing Exp $ */ 1/* $OpenBSD: bn_exp.c,v 1.37 2023/02/03 05:30:49 jsing Exp $ */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -1155,3 +1155,187 @@ BN_mod_exp_nonct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
1155{ 1155{
1156 return BN_mod_exp_internal(r, a, p, m, ctx, 0); 1156 return BN_mod_exp_internal(r, a, p, m, ctx, 0);
1157} 1157}
1158
1159int
1160BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1,
1161 const BIGNUM *a2, const BIGNUM *p2, const BIGNUM *m, BN_CTX *ctx,
1162 BN_MONT_CTX *in_mont)
1163{
1164 int i, j, bits, b, bits1, bits2, ret = 0, wpos1, wpos2, window1, window2, wvalue1, wvalue2;
1165 int r_is_one = 1;
1166 BIGNUM *d, *r;
1167 const BIGNUM *a_mod_m;
1168 /* Tables of variables obtained from 'ctx' */
1169 BIGNUM *val1[TABLE_SIZE], *val2[TABLE_SIZE];
1170 BN_MONT_CTX *mont = NULL;
1171
1172
1173 if (!BN_is_odd(m)) {
1174 BNerror(BN_R_CALLED_WITH_EVEN_MODULUS);
1175 return (0);
1176 }
1177 bits1 = BN_num_bits(p1);
1178 bits2 = BN_num_bits(p2);
1179 if ((bits1 == 0) && (bits2 == 0)) {
1180 ret = BN_one(rr);
1181 return ret;
1182 }
1183
1184 bits = (bits1 > bits2) ? bits1 : bits2;
1185
1186 BN_CTX_start(ctx);
1187 if ((d = BN_CTX_get(ctx)) == NULL)
1188 goto err;
1189 if ((r = BN_CTX_get(ctx)) == NULL)
1190 goto err;
1191 if ((val1[0] = BN_CTX_get(ctx)) == NULL)
1192 goto err;
1193 if ((val2[0] = BN_CTX_get(ctx)) == NULL)
1194 goto err;
1195
1196 if (in_mont != NULL)
1197 mont = in_mont;
1198 else {
1199 if ((mont = BN_MONT_CTX_new()) == NULL)
1200 goto err;
1201 if (!BN_MONT_CTX_set(mont, m, ctx))
1202 goto err;
1203 }
1204
1205 window1 = BN_window_bits_for_exponent_size(bits1);
1206 window2 = BN_window_bits_for_exponent_size(bits2);
1207
1208 /*
1209 * Build table for a1: val1[i] := a1^(2*i + 1) mod m for i = 0 .. 2^(window1-1)
1210 */
1211 if (a1->neg || BN_ucmp(a1, m) >= 0) {
1212 if (!BN_mod_ct(val1[0], a1, m, ctx))
1213 goto err;
1214 a_mod_m = val1[0];
1215 } else
1216 a_mod_m = a1;
1217 if (BN_is_zero(a_mod_m)) {
1218 BN_zero(rr);
1219 ret = 1;
1220 goto err;
1221 }
1222
1223 if (!BN_to_montgomery(val1[0], a_mod_m, mont, ctx))
1224 goto err;
1225 if (window1 > 1) {
1226 if (!BN_mod_mul_montgomery(d, val1[0], val1[0], mont, ctx))
1227 goto err;
1228
1229 j = 1 << (window1 - 1);
1230 for (i = 1; i < j; i++) {
1231 if (((val1[i] = BN_CTX_get(ctx)) == NULL) ||
1232 !BN_mod_mul_montgomery(val1[i], val1[i - 1],
1233 d, mont, ctx))
1234 goto err;
1235 }
1236 }
1237
1238
1239 /*
1240 * Build table for a2: val2[i] := a2^(2*i + 1) mod m for i = 0 .. 2^(window2-1)
1241 */
1242 if (a2->neg || BN_ucmp(a2, m) >= 0) {
1243 if (!BN_mod_ct(val2[0], a2, m, ctx))
1244 goto err;
1245 a_mod_m = val2[0];
1246 } else
1247 a_mod_m = a2;
1248 if (BN_is_zero(a_mod_m)) {
1249 BN_zero(rr);
1250 ret = 1;
1251 goto err;
1252 }
1253 if (!BN_to_montgomery(val2[0], a_mod_m, mont, ctx))
1254 goto err;
1255 if (window2 > 1) {
1256 if (!BN_mod_mul_montgomery(d, val2[0], val2[0], mont, ctx))
1257 goto err;
1258
1259 j = 1 << (window2 - 1);
1260 for (i = 1; i < j; i++) {
1261 if (((val2[i] = BN_CTX_get(ctx)) == NULL) ||
1262 !BN_mod_mul_montgomery(val2[i], val2[i - 1],
1263 d, mont, ctx))
1264 goto err;
1265 }
1266 }
1267
1268
1269 /* Now compute the power product, using independent windows. */
1270 r_is_one = 1;
1271 wvalue1 = 0; /* The 'value' of the first window */
1272 wvalue2 = 0; /* The 'value' of the second window */
1273 wpos1 = 0; /* If wvalue1 > 0, the bottom bit of the first window */
1274 wpos2 = 0; /* If wvalue2 > 0, the bottom bit of the second window */
1275
1276 if (!BN_to_montgomery(r, BN_value_one(), mont, ctx))
1277 goto err;
1278 for (b = bits - 1; b >= 0; b--) {
1279 if (!r_is_one) {
1280 if (!BN_mod_mul_montgomery(r, r,r, mont, ctx))
1281 goto err;
1282 }
1283
1284 if (!wvalue1)
1285 if (BN_is_bit_set(p1, b)) {
1286 /* consider bits b-window1+1 .. b for this window */
1287 i = b - window1 + 1;
1288 while (!BN_is_bit_set(p1, i)) /* works for i<0 */
1289 i++;
1290 wpos1 = i;
1291 wvalue1 = 1;
1292 for (i = b - 1; i >= wpos1; i--) {
1293 wvalue1 <<= 1;
1294 if (BN_is_bit_set(p1, i))
1295 wvalue1++;
1296 }
1297 }
1298
1299 if (!wvalue2)
1300 if (BN_is_bit_set(p2, b)) {
1301 /* consider bits b-window2+1 .. b for this window */
1302 i = b - window2 + 1;
1303 while (!BN_is_bit_set(p2, i))
1304 i++;
1305 wpos2 = i;
1306 wvalue2 = 1;
1307 for (i = b - 1; i >= wpos2; i--) {
1308 wvalue2 <<= 1;
1309 if (BN_is_bit_set(p2, i))
1310 wvalue2++;
1311 }
1312 }
1313
1314 if (wvalue1 && b == wpos1) {
1315 /* wvalue1 is odd and < 2^window1 */
1316 if (!BN_mod_mul_montgomery(r, r, val1[wvalue1 >> 1],
1317 mont, ctx))
1318 goto err;
1319 wvalue1 = 0;
1320 r_is_one = 0;
1321 }
1322
1323 if (wvalue2 && b == wpos2) {
1324 /* wvalue2 is odd and < 2^window2 */
1325 if (!BN_mod_mul_montgomery(r, r, val2[wvalue2 >> 1],
1326 mont, ctx))
1327 goto err;
1328 wvalue2 = 0;
1329 r_is_one = 0;
1330 }
1331 }
1332 if (!BN_from_montgomery(rr, r,mont, ctx))
1333 goto err;
1334 ret = 1;
1335
1336err:
1337 if ((in_mont == NULL) && (mont != NULL))
1338 BN_MONT_CTX_free(mont);
1339 BN_CTX_end(ctx);
1340 return (ret);
1341}
diff --git a/src/lib/libcrypto/bn/bn_exp2.c b/src/lib/libcrypto/bn/bn_exp2.c
index 03f99414cd..fb688c5922 100644
--- a/src/lib/libcrypto/bn/bn_exp2.c
+++ b/src/lib/libcrypto/bn/bn_exp2.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_exp2.c,v 1.15 2022/11/26 16:08:51 tb Exp $ */ 1/* $OpenBSD: bn_exp2.c,v 1.16 2023/02/03 05:30:49 jsing Exp $ */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -114,189 +114,3 @@
114#include <openssl/err.h> 114#include <openssl/err.h>
115 115
116#include "bn_local.h" 116#include "bn_local.h"
117
118#define TABLE_SIZE 32
119
120int
121BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1,
122 const BIGNUM *a2, const BIGNUM *p2, const BIGNUM *m, BN_CTX *ctx,
123 BN_MONT_CTX *in_mont)
124{
125 int i, j, bits, b, bits1, bits2, ret = 0, wpos1, wpos2, window1, window2, wvalue1, wvalue2;
126 int r_is_one = 1;
127 BIGNUM *d, *r;
128 const BIGNUM *a_mod_m;
129 /* Tables of variables obtained from 'ctx' */
130 BIGNUM *val1[TABLE_SIZE], *val2[TABLE_SIZE];
131 BN_MONT_CTX *mont = NULL;
132
133
134 if (!BN_is_odd(m)) {
135 BNerror(BN_R_CALLED_WITH_EVEN_MODULUS);
136 return (0);
137 }
138 bits1 = BN_num_bits(p1);
139 bits2 = BN_num_bits(p2);
140 if ((bits1 == 0) && (bits2 == 0)) {
141 ret = BN_one(rr);
142 return ret;
143 }
144
145 bits = (bits1 > bits2) ? bits1 : bits2;
146
147 BN_CTX_start(ctx);
148 if ((d = BN_CTX_get(ctx)) == NULL)
149 goto err;
150 if ((r = BN_CTX_get(ctx)) == NULL)
151 goto err;
152 if ((val1[0] = BN_CTX_get(ctx)) == NULL)
153 goto err;
154 if ((val2[0] = BN_CTX_get(ctx)) == NULL)
155 goto err;
156
157 if (in_mont != NULL)
158 mont = in_mont;
159 else {
160 if ((mont = BN_MONT_CTX_new()) == NULL)
161 goto err;
162 if (!BN_MONT_CTX_set(mont, m, ctx))
163 goto err;
164 }
165
166 window1 = BN_window_bits_for_exponent_size(bits1);
167 window2 = BN_window_bits_for_exponent_size(bits2);
168
169 /*
170 * Build table for a1: val1[i] := a1^(2*i + 1) mod m for i = 0 .. 2^(window1-1)
171 */
172 if (a1->neg || BN_ucmp(a1, m) >= 0) {
173 if (!BN_mod_ct(val1[0], a1, m, ctx))
174 goto err;
175 a_mod_m = val1[0];
176 } else
177 a_mod_m = a1;
178 if (BN_is_zero(a_mod_m)) {
179 BN_zero(rr);
180 ret = 1;
181 goto err;
182 }
183
184 if (!BN_to_montgomery(val1[0], a_mod_m, mont, ctx))
185 goto err;
186 if (window1 > 1) {
187 if (!BN_mod_mul_montgomery(d, val1[0], val1[0], mont, ctx))
188 goto err;
189
190 j = 1 << (window1 - 1);
191 for (i = 1; i < j; i++) {
192 if (((val1[i] = BN_CTX_get(ctx)) == NULL) ||
193 !BN_mod_mul_montgomery(val1[i], val1[i - 1],
194 d, mont, ctx))
195 goto err;
196 }
197 }
198
199
200 /*
201 * Build table for a2: val2[i] := a2^(2*i + 1) mod m for i = 0 .. 2^(window2-1)
202 */
203 if (a2->neg || BN_ucmp(a2, m) >= 0) {
204 if (!BN_mod_ct(val2[0], a2, m, ctx))
205 goto err;
206 a_mod_m = val2[0];
207 } else
208 a_mod_m = a2;
209 if (BN_is_zero(a_mod_m)) {
210 BN_zero(rr);
211 ret = 1;
212 goto err;
213 }
214 if (!BN_to_montgomery(val2[0], a_mod_m, mont, ctx))
215 goto err;
216 if (window2 > 1) {
217 if (!BN_mod_mul_montgomery(d, val2[0], val2[0], mont, ctx))
218 goto err;
219
220 j = 1 << (window2 - 1);
221 for (i = 1; i < j; i++) {
222 if (((val2[i] = BN_CTX_get(ctx)) == NULL) ||
223 !BN_mod_mul_montgomery(val2[i], val2[i - 1],
224 d, mont, ctx))
225 goto err;
226 }
227 }
228
229
230 /* Now compute the power product, using independent windows. */
231 r_is_one = 1;
232 wvalue1 = 0; /* The 'value' of the first window */
233 wvalue2 = 0; /* The 'value' of the second window */
234 wpos1 = 0; /* If wvalue1 > 0, the bottom bit of the first window */
235 wpos2 = 0; /* If wvalue2 > 0, the bottom bit of the second window */
236
237 if (!BN_to_montgomery(r, BN_value_one(), mont, ctx))
238 goto err;
239 for (b = bits - 1; b >= 0; b--) {
240 if (!r_is_one) {
241 if (!BN_mod_mul_montgomery(r, r,r, mont, ctx))
242 goto err;
243 }
244
245 if (!wvalue1)
246 if (BN_is_bit_set(p1, b)) {
247 /* consider bits b-window1+1 .. b for this window */
248 i = b - window1 + 1;
249 while (!BN_is_bit_set(p1, i)) /* works for i<0 */
250 i++;
251 wpos1 = i;
252 wvalue1 = 1;
253 for (i = b - 1; i >= wpos1; i--) {
254 wvalue1 <<= 1;
255 if (BN_is_bit_set(p1, i))
256 wvalue1++;
257 }
258 }
259
260 if (!wvalue2)
261 if (BN_is_bit_set(p2, b)) {
262 /* consider bits b-window2+1 .. b for this window */
263 i = b - window2 + 1;
264 while (!BN_is_bit_set(p2, i))
265 i++;
266 wpos2 = i;
267 wvalue2 = 1;
268 for (i = b - 1; i >= wpos2; i--) {
269 wvalue2 <<= 1;
270 if (BN_is_bit_set(p2, i))
271 wvalue2++;
272 }
273 }
274
275 if (wvalue1 && b == wpos1) {
276 /* wvalue1 is odd and < 2^window1 */
277 if (!BN_mod_mul_montgomery(r, r, val1[wvalue1 >> 1],
278 mont, ctx))
279 goto err;
280 wvalue1 = 0;
281 r_is_one = 0;
282 }
283
284 if (wvalue2 && b == wpos2) {
285 /* wvalue2 is odd and < 2^window2 */
286 if (!BN_mod_mul_montgomery(r, r, val2[wvalue2 >> 1],
287 mont, ctx))
288 goto err;
289 wvalue2 = 0;
290 r_is_one = 0;
291 }
292 }
293 if (!BN_from_montgomery(rr, r,mont, ctx))
294 goto err;
295 ret = 1;
296
297err:
298 if ((in_mont == NULL) && (mont != NULL))
299 BN_MONT_CTX_free(mont);
300 BN_CTX_end(ctx);
301 return (ret);
302}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-11-20 21:56:56 +0000