summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/lib/libcrypto/bn/bn_exp.c22
-rw-r--r--src/lib/libcrypto/bn/bn_local.h19
-rw-r--r--src/lib/libcrypto/bn/bn_recp.c74
3 files changed, 48 insertions, 67 deletions
diff --git a/src/lib/libcrypto/bn/bn_exp.c b/src/lib/libcrypto/bn/bn_exp.c
index c51296c3c3..8ff518e938 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.53 2024/04/10 14:58:06 beck Exp $ */ 1/* $OpenBSD: bn_exp.c,v 1.54 2025/01/21 15:44:22 tb 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 *
@@ -972,7 +972,7 @@ BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
972 BIGNUM *aa, *q; 972 BIGNUM *aa, *q;
973 /* Table of variables obtained from 'ctx' */ 973 /* Table of variables obtained from 'ctx' */
974 BIGNUM *val[TABLE_SIZE]; 974 BIGNUM *val[TABLE_SIZE];
975 BN_RECP_CTX recp; 975 BN_RECP_CTX *recp = NULL;
976 int ret = 0; 976 int ret = 0;
977 977
978 if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) { 978 if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) {
@@ -992,8 +992,6 @@ BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
992 return ret; 992 return ret;
993 } 993 }
994 994
995 BN_RECP_CTX_init(&recp);
996
997 BN_CTX_start(ctx); 995 BN_CTX_start(ctx);
998 if ((aa = BN_CTX_get(ctx)) == NULL) 996 if ((aa = BN_CTX_get(ctx)) == NULL)
999 goto err; 997 goto err;
@@ -1007,10 +1005,10 @@ BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
1007 if (!bn_copy(aa, m)) 1005 if (!bn_copy(aa, m))
1008 goto err; 1006 goto err;
1009 aa->neg = 0; 1007 aa->neg = 0;
1010 if (BN_RECP_CTX_set(&recp, aa, ctx) <= 0) 1008 if ((recp = BN_RECP_CTX_create(aa)) == 0)
1011 goto err; 1009 goto err;
1012 } else { 1010 } else {
1013 if (BN_RECP_CTX_set(&recp, m, ctx) <= 0) 1011 if ((recp = BN_RECP_CTX_create(m)) == 0)
1014 goto err; 1012 goto err;
1015 } 1013 }
1016 1014
@@ -1025,13 +1023,13 @@ BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
1025 1023
1026 window = BN_window_bits_for_exponent_size(bits); 1024 window = BN_window_bits_for_exponent_size(bits);
1027 if (window > 1) { 1025 if (window > 1) {
1028 if (!BN_mod_mul_reciprocal(aa, val[0], val[0], &recp, ctx)) 1026 if (!BN_mod_mul_reciprocal(aa, val[0], val[0], recp, ctx))
1029 goto err; 1027 goto err;
1030 j = 1 << (window - 1); 1028 j = 1 << (window - 1);
1031 for (i = 1; i < j; i++) { 1029 for (i = 1; i < j; i++) {
1032 if (((val[i] = BN_CTX_get(ctx)) == NULL) || 1030 if (((val[i] = BN_CTX_get(ctx)) == NULL) ||
1033 !BN_mod_mul_reciprocal(val[i], val[i - 1], 1031 !BN_mod_mul_reciprocal(val[i], val[i - 1],
1034 aa, &recp, ctx)) 1032 aa, recp, ctx))
1035 goto err; 1033 goto err;
1036 } 1034 }
1037 } 1035 }
@@ -1049,7 +1047,7 @@ BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
1049 for (;;) { 1047 for (;;) {
1050 if (BN_is_bit_set(q, wstart) == 0) { 1048 if (BN_is_bit_set(q, wstart) == 0) {
1051 if (!start) 1049 if (!start)
1052 if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx)) 1050 if (!BN_mod_mul_reciprocal(r, r, r, recp, ctx))
1053 goto err; 1051 goto err;
1054 if (wstart == 0) 1052 if (wstart == 0)
1055 break; 1053 break;
@@ -1078,12 +1076,12 @@ BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
1078 /* add the 'bytes above' */ 1076 /* add the 'bytes above' */
1079 if (!start) 1077 if (!start)
1080 for (i = 0; i < j; i++) { 1078 for (i = 0; i < j; i++) {
1081 if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx)) 1079 if (!BN_mod_mul_reciprocal(r, r, r, recp, ctx))
1082 goto err; 1080 goto err;
1083 } 1081 }
1084 1082
1085 /* wvalue will be an odd number < 2^window */ 1083 /* wvalue will be an odd number < 2^window */
1086 if (!BN_mod_mul_reciprocal(r, r, val[wvalue >> 1], &recp, ctx)) 1084 if (!BN_mod_mul_reciprocal(r, r, val[wvalue >> 1], recp, ctx))
1087 goto err; 1085 goto err;
1088 1086
1089 /* move the 'window' down further */ 1087 /* move the 'window' down further */
@@ -1099,7 +1097,7 @@ BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
1099 1097
1100 err: 1098 err:
1101 BN_CTX_end(ctx); 1099 BN_CTX_end(ctx);
1102 BN_RECP_CTX_free(&recp); 1100 BN_RECP_CTX_free(recp);
1103 1101
1104 return ret; 1102 return ret;
1105} 1103}
diff --git a/src/lib/libcrypto/bn/bn_local.h b/src/lib/libcrypto/bn/bn_local.h
index 310cce2a0e..2042e0b193 100644
--- a/src/lib/libcrypto/bn/bn_local.h
+++ b/src/lib/libcrypto/bn/bn_local.h
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_local.h,v 1.45 2025/01/06 13:47:37 tb Exp $ */ 1/* $OpenBSD: bn_local.h,v 1.46 2025/01/21 15:44:22 tb 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 *
@@ -138,16 +138,7 @@ struct bn_mont_ctx_st {
138 int flags; 138 int flags;
139}; 139};
140 140
141/* Used for reciprocal division/mod functions 141typedef struct bn_recp_ctx_st BN_RECP_CTX;
142 * It cannot be shared between threads
143 */
144typedef struct bn_recp_ctx_st {
145 BIGNUM N; /* the divisor */
146 BIGNUM Nr; /* the reciprocal */
147 int num_bits;
148 int shift;
149 int flags;
150} BN_RECP_CTX;
151 142
152/* Used for slow "generation" functions. */ 143/* Used for slow "generation" functions. */
153struct bn_gencb_st { 144struct bn_gencb_st {
@@ -280,10 +271,8 @@ int bn_rand_interval(BIGNUM *rnd, BN_ULONG lower_word, const BIGNUM *upper_exc);
280 271
281void BN_init(BIGNUM *); 272void BN_init(BIGNUM *);
282 273
283void BN_RECP_CTX_init(BN_RECP_CTX *recp); 274BN_RECP_CTX *BN_RECP_CTX_create(const BIGNUM *N);
284BN_RECP_CTX *BN_RECP_CTX_new(void); 275void BN_RECP_CTX_free(BN_RECP_CTX *recp);
285void BN_RECP_CTX_free(BN_RECP_CTX *recp);
286int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *rdiv, BN_CTX *ctx);
287int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, BN_RECP_CTX *recp, 276int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, BN_RECP_CTX *recp,
288 BN_CTX *ctx); 277 BN_CTX *ctx);
289int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y, 278int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y,
diff --git a/src/lib/libcrypto/bn/bn_recp.c b/src/lib/libcrypto/bn/bn_recp.c
index 44c5b05e4d..e7484f9f4b 100644
--- a/src/lib/libcrypto/bn/bn_recp.c
+++ b/src/lib/libcrypto/bn/bn_recp.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_recp.c,v 1.25 2025/01/08 20:21:28 tb Exp $ */ 1/* $OpenBSD: bn_recp.c,v 1.26 2025/01/21 15:44:22 tb 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 *
@@ -62,26 +62,34 @@
62 62
63#include "bn_local.h" 63#include "bn_local.h"
64 64
65void 65struct bn_recp_ctx_st {
66BN_RECP_CTX_init(BN_RECP_CTX *recp) 66 BIGNUM *N; /* the divisor */
67{ 67 BIGNUM *Nr; /* the reciprocal 2^shift / N */
68 BN_init(&recp->N); 68 int num_bits; /* number of bits in N */
69 BN_init(&recp->Nr); 69 int shift;
70 recp->num_bits = 0; 70} /* BN_RECP_CTX */;
71 recp->flags = 0;
72}
73 71
74BN_RECP_CTX * 72BN_RECP_CTX *
75BN_RECP_CTX_new(void) 73BN_RECP_CTX_create(const BIGNUM *N)
76{ 74{
77 BN_RECP_CTX *ret; 75 BN_RECP_CTX *recp;
78 76
79 if ((ret = malloc(sizeof(BN_RECP_CTX))) == NULL) 77 if ((recp = calloc(1, sizeof(*recp))) == NULL)
80 return NULL; 78 goto err;
81 79
82 BN_RECP_CTX_init(ret); 80 if ((recp->N = BN_dup(N)) == NULL)
83 ret->flags = BN_FLG_MALLOCED; 81 goto err;
84 return ret; 82 recp->num_bits = BN_num_bits(recp->N);
83
84 if ((recp->Nr = BN_new()) == NULL)
85 goto err;
86
87 return recp;
88
89 err:
90 BN_RECP_CTX_free(recp);
91
92 return NULL;
85} 93}
86 94
87void 95void
@@ -90,23 +98,9 @@ BN_RECP_CTX_free(BN_RECP_CTX *recp)
90 if (recp == NULL) 98 if (recp == NULL)
91 return; 99 return;
92 100
93 BN_free(&recp->N); 101 BN_free(recp->N);
94 BN_free(&recp->Nr); 102 BN_free(recp->Nr);
95 if (recp->flags & BN_FLG_MALLOCED) 103 freezero(recp, sizeof(*recp));
96 free(recp);
97}
98
99int
100BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx)
101{
102 if (!bn_copy(&recp->N, d))
103 return 0;
104 recp->num_bits = BN_num_bits(&recp->N);
105
106 BN_zero(&recp->Nr);
107 recp->shift = 0;
108
109 return 1;
110} 104}
111 105
112/* len is the expected size of the result 106/* len is the expected size of the result
@@ -158,7 +152,7 @@ BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, BN_RECP_CTX *recp,
158 if (a == NULL || b == NULL || d == NULL || r == NULL) 152 if (a == NULL || b == NULL || d == NULL || r == NULL)
159 goto err; 153 goto err;
160 154
161 if (BN_ucmp(m, &recp->N) < 0) { 155 if (BN_ucmp(m, recp->N) < 0) {
162 BN_zero(d); 156 BN_zero(d);
163 if (!bn_copy(r, m)) { 157 if (!bn_copy(r, m)) {
164 BN_CTX_end(ctx); 158 BN_CTX_end(ctx);
@@ -182,7 +176,7 @@ BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, BN_RECP_CTX *recp,
182 176
183 /* Nr := round(2^i / N) */ 177 /* Nr := round(2^i / N) */
184 if (i != recp->shift) 178 if (i != recp->shift)
185 recp->shift = BN_reciprocal(&recp->Nr, &recp->N, i, ctx); 179 recp->shift = BN_reciprocal(recp->Nr, recp->N, i, ctx);
186 180
187 /* BN_reciprocal returns i, or -1 for an error */ 181 /* BN_reciprocal returns i, or -1 for an error */
188 if (recp->shift == -1) 182 if (recp->shift == -1)
@@ -195,13 +189,13 @@ BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, BN_RECP_CTX *recp,
195 */ 189 */
196 if (!BN_rshift(a, m, recp->num_bits)) 190 if (!BN_rshift(a, m, recp->num_bits))
197 goto err; 191 goto err;
198 if (!BN_mul(b, a, &recp->Nr, ctx)) 192 if (!BN_mul(b, a, recp->Nr, ctx))
199 goto err; 193 goto err;
200 if (!BN_rshift(d, b, i - recp->num_bits)) 194 if (!BN_rshift(d, b, i - recp->num_bits))
201 goto err; 195 goto err;
202 d->neg = 0; 196 d->neg = 0;
203 197
204 if (!BN_mul(b, &recp->N, d, ctx)) 198 if (!BN_mul(b, recp->N, d, ctx))
205 goto err; 199 goto err;
206 if (!BN_usub(r, m, b)) 200 if (!BN_usub(r, m, b))
207 goto err; 201 goto err;
@@ -209,12 +203,12 @@ BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, BN_RECP_CTX *recp,
209 203
210#if 1 204#if 1
211 j = 0; 205 j = 0;
212 while (BN_ucmp(r, &recp->N) >= 0) { 206 while (BN_ucmp(r, recp->N) >= 0) {
213 if (j++ > 2) { 207 if (j++ > 2) {
214 BNerror(BN_R_BAD_RECIPROCAL); 208 BNerror(BN_R_BAD_RECIPROCAL);
215 goto err; 209 goto err;
216 } 210 }
217 if (!BN_usub(r, r, &recp->N)) 211 if (!BN_usub(r, r, recp->N))
218 goto err; 212 goto err;
219 if (!BN_add_word(d, 1)) 213 if (!BN_add_word(d, 1))
220 goto err; 214 goto err;
@@ -222,7 +216,7 @@ BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, BN_RECP_CTX *recp,
222#endif 216#endif
223 217
224 BN_set_negative(r, m->neg); 218 BN_set_negative(r, m->neg);
225 BN_set_negative(d, m->neg ^ recp->N.neg); 219 BN_set_negative(d, m->neg ^ recp->N->neg);
226 220
227 ret = 1; 221 ret = 1;
228 222
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-22 22:56:34 +0000