summaryrefslogtreecommitdiff
path: root/src/crypto/fipsmodule/bn/exponentiation.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/crypto/fipsmodule/bn/exponentiation.c')
-rw-r--r--src/crypto/fipsmodule/bn/exponentiation.c333
1 files changed, 164 insertions, 169 deletions
diff --git a/src/crypto/fipsmodule/bn/exponentiation.c b/src/crypto/fipsmodule/bn/exponentiation.c
index 187b845c..ae78ff99 100644
--- a/src/crypto/fipsmodule/bn/exponentiation.c
+++ b/src/crypto/fipsmodule/bn/exponentiation.c
@@ -188,12 +188,12 @@ err:
return ret;
}
-/* maximum precomputation table size for *variable* sliding windows */
+// maximum precomputation table size for *variable* sliding windows
#define TABLE_SIZE 32
typedef struct bn_recp_ctx_st {
- BIGNUM N; /* the divisor */
- BIGNUM Nr; /* the reciprocal */
+ BIGNUM N; // the divisor
+ BIGNUM Nr; // the reciprocal
int num_bits;
int shift;
int flags;
@@ -227,10 +227,10 @@ static int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx) {
return 1;
}
-/* len is the expected size of the result We actually calculate with an extra
- * word of precision, so we can do faster division if the remainder is not
- * required.
- * r := 2^len / m */
+// len is the expected size of the result We actually calculate with an extra
+// word of precision, so we can do faster division if the remainder is not
+// required.
+// r := 2^len / m
static int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx) {
int ret = -1;
BIGNUM *t;
@@ -289,34 +289,34 @@ static int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,
return 1;
}
- /* We want the remainder
- * Given input of ABCDEF / ab
- * we need multiply ABCDEF by 3 digests of the reciprocal of ab */
+ // We want the remainder
+ // Given input of ABCDEF / ab
+ // we need multiply ABCDEF by 3 digests of the reciprocal of ab
- /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */
+ // i := max(BN_num_bits(m), 2*BN_num_bits(N))
i = BN_num_bits(m);
j = recp->num_bits << 1;
if (j > i) {
i = j;
}
- /* Nr := round(2^i / N) */
+ // Nr := round(2^i / N)
if (i != recp->shift) {
recp->shift =
BN_reciprocal(&(recp->Nr), &(recp->N), i,
- ctx); /* BN_reciprocal returns i, or -1 for an error */
+ ctx); // BN_reciprocal returns i, or -1 for an error
}
if (recp->shift == -1) {
goto err;
}
- /* d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i -
- * BN_num_bits(N)))|
- * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i -
- * BN_num_bits(N)))|
- * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
- * = |m/N| */
+ // d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i -
+ // BN_num_bits(N)))|
+ // = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i -
+ // BN_num_bits(N)))|
+ // <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
+ // = |m/N|
if (!BN_rshift(a, m, recp->num_bits)) {
goto err;
}
@@ -383,7 +383,7 @@ static int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y,
}
ca = a;
} else {
- ca = x; /* Just do the mod */
+ ca = x; // Just do the mod
}
ret = BN_div_recp(NULL, r, ca, recp, ctx);
@@ -393,29 +393,29 @@ err:
return ret;
}
-/* BN_window_bits_for_exponent_size -- macro for sliding window mod_exp
- * functions
- *
- * For window size 'w' (w >= 2) and a random 'b' bits exponent, the number of
- * multiplications is a constant plus on average
- *
- * 2^(w-1) + (b-w)/(w+1);
- *
- * here 2^(w-1) is for precomputing the table (we actually need entries only
- * for windows that have the lowest bit set), and (b-w)/(w+1) is an
- * approximation for the expected number of w-bit windows, not counting the
- * first one.
- *
- * Thus we should use
- *
- * w >= 6 if b > 671
- * w = 5 if 671 > b > 239
- * w = 4 if 239 > b > 79
- * w = 3 if 79 > b > 23
- * w <= 2 if 23 > b
- *
- * (with draws in between). Very small exponents are often selected
- * with low Hamming weight, so we use w = 1 for b <= 23. */
+// BN_window_bits_for_exponent_size -- macro for sliding window mod_exp
+// functions
+//
+// For window size 'w' (w >= 2) and a random 'b' bits exponent, the number of
+// multiplications is a constant plus on average
+//
+// 2^(w-1) + (b-w)/(w+1);
+//
+// here 2^(w-1) is for precomputing the table (we actually need entries only
+// for windows that have the lowest bit set), and (b-w)/(w+1) is an
+// approximation for the expected number of w-bit windows, not counting the
+// first one.
+//
+// Thus we should use
+//
+// w >= 6 if b > 671
+// w = 5 if 671 > b > 239
+// w = 4 if 239 > b > 79
+// w = 3 if 79 > b > 23
+// w <= 2 if 23 > b
+//
+// (with draws in between). Very small exponents are often selected
+// with low Hamming weight, so we use w = 1 for b <= 23.
#define BN_window_bits_for_exponent_size(b) \
((b) > 671 ? 6 : \
(b) > 239 ? 5 : \
@@ -427,14 +427,14 @@ static int mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
int i, j, bits, ret = 0, wstart, window;
int start = 1;
BIGNUM *aa;
- /* Table of variables obtained from 'ctx' */
+ // Table of variables obtained from 'ctx'
BIGNUM *val[TABLE_SIZE];
BN_RECP_CTX recp;
bits = BN_num_bits(p);
if (bits == 0) {
- /* x**0 mod 1 is still zero. */
+ // x**0 mod 1 is still zero.
if (BN_is_one(m)) {
BN_zero(r);
return 1;
@@ -451,7 +451,7 @@ static int mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
BN_RECP_CTX_init(&recp);
if (m->neg) {
- /* ignore sign of 'm' */
+ // ignore sign of 'm'
if (!BN_copy(aa, m)) {
goto err;
}
@@ -466,7 +466,7 @@ static int mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
}
if (!BN_nnmod(val[0], a, m, ctx)) {
- goto err; /* 1 */
+ goto err; // 1
}
if (BN_is_zero(val[0])) {
BN_zero(r);
@@ -477,7 +477,7 @@ static int mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
window = BN_window_bits_for_exponent_size(bits);
if (window > 1) {
if (!BN_mod_mul_reciprocal(aa, val[0], val[0], &recp, ctx)) {
- goto err; /* 2 */
+ goto err; // 2
}
j = 1 << (window - 1);
for (i = 1; i < j; i++) {
@@ -488,18 +488,18 @@ static int mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
}
}
- start = 1; /* This is used to avoid multiplication etc
- * when there is only the value '1' in the
- * buffer. */
- wstart = bits - 1; /* The top bit of the window */
+ start = 1; // This is used to avoid multiplication etc
+ // when there is only the value '1' in the
+ // buffer.
+ wstart = bits - 1; // The top bit of the window
if (!BN_one(r)) {
goto err;
}
for (;;) {
- int wvalue; /* The 'value' of the window */
- int wend; /* The bottom bit of the window */
+ int wvalue; // The 'value' of the window
+ int wend; // The bottom bit of the window
if (BN_is_bit_set(p, wstart) == 0) {
if (!start) {
@@ -514,10 +514,10 @@ static int mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
continue;
}
- /* We now have wstart on a 'set' bit, we now need to work out
- * how bit a window to do. To do this we need to scan
- * forward until the last set bit before the end of the
- * window */
+ // We now have wstart on a 'set' bit, we now need to work out
+ // how bit a window to do. To do this we need to scan
+ // forward until the last set bit before the end of the
+ // window
wvalue = 1;
wend = 0;
for (i = 1; i < window; i++) {
@@ -531,9 +531,9 @@ static int mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
}
}
- /* wend is the size of the current window */
+ // wend is the size of the current window
j = wend + 1;
- /* add the 'bytes above' */
+ // add the 'bytes above'
if (!start) {
for (i = 0; i < j; i++) {
if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx)) {
@@ -542,12 +542,12 @@ static int mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
}
}
- /* wvalue will be an odd number < 2^window */
+ // wvalue will be an odd number < 2^window
if (!BN_mod_mul_reciprocal(r, r, val[wvalue >> 1], &recp, ctx)) {
goto err;
}
- /* move the 'window' down further */
+ // move the 'window' down further
wstart -= wend + 1;
start = 0;
if (wstart < 0) {
@@ -577,7 +577,7 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
int start = 1;
BIGNUM *d, *r;
const BIGNUM *aa;
- /* Table of variables obtained from 'ctx' */
+ // Table of variables obtained from 'ctx'
BIGNUM *val[TABLE_SIZE];
BN_MONT_CTX *new_mont = NULL;
@@ -587,7 +587,7 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
}
bits = BN_num_bits(p);
if (bits == 0) {
- /* x**0 mod 1 is still zero. */
+ // x**0 mod 1 is still zero.
if (BN_is_one(m)) {
BN_zero(rr);
return 1;
@@ -603,7 +603,7 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
goto err;
}
- /* Allocate a montgomery context if it was not supplied by the caller. */
+ // Allocate a montgomery context if it was not supplied by the caller.
if (mont == NULL) {
new_mont = BN_MONT_CTX_new();
if (new_mont == NULL || !BN_MONT_CTX_set(new_mont, m, ctx)) {
@@ -627,13 +627,13 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
goto err;
}
if (!BN_to_montgomery(val[0], aa, mont, ctx)) {
- goto err; /* 1 */
+ goto err; // 1
}
window = BN_window_bits_for_exponent_size(bits);
if (window > 1) {
if (!BN_mod_mul_montgomery(d, val[0], val[0], mont, ctx)) {
- goto err; /* 2 */
+ goto err; // 2
}
j = 1 << (window - 1);
for (i = 1; i < j; i++) {
@@ -644,32 +644,32 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
}
}
- start = 1; /* This is used to avoid multiplication etc
- * when there is only the value '1' in the
- * buffer. */
- wstart = bits - 1; /* The top bit of the window */
+ start = 1; // This is used to avoid multiplication etc
+ // when there is only the value '1' in the
+ // buffer.
+ wstart = bits - 1; // The top bit of the window
- j = m->top; /* borrow j */
+ j = m->top; // borrow j
if (m->d[j - 1] & (((BN_ULONG)1) << (BN_BITS2 - 1))) {
if (!bn_wexpand(r, j)) {
goto err;
}
- /* 2^(top*BN_BITS2) - m */
+ // 2^(top*BN_BITS2) - m
r->d[0] = (0 - m->d[0]) & BN_MASK2;
for (i = 1; i < j; i++) {
r->d[i] = (~m->d[i]) & BN_MASK2;
}
r->top = j;
- /* Upper words will be zero if the corresponding words of 'm'
- * were 0xfff[...], so decrement r->top accordingly. */
+ // Upper words will be zero if the corresponding words of 'm'
+ // were 0xfff[...], so decrement r->top accordingly.
bn_correct_top(r);
} else if (!BN_to_montgomery(r, BN_value_one(), mont, ctx)) {
goto err;
}
for (;;) {
- int wvalue; /* The 'value' of the window */
- int wend; /* The bottom bit of the window */
+ int wvalue; // The 'value' of the window
+ int wend; // The bottom bit of the window
if (BN_is_bit_set(p, wstart) == 0) {
if (!start && !BN_mod_mul_montgomery(r, r, r, mont, ctx)) {
@@ -682,9 +682,9 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
continue;
}
- /* We now have wstart on a 'set' bit, we now need to work out how bit a
- * window to do. To do this we need to scan forward until the last set bit
- * before the end of the window */
+ // We now have wstart on a 'set' bit, we now need to work out how bit a
+ // window to do. To do this we need to scan forward until the last set bit
+ // before the end of the window
wvalue = 1;
wend = 0;
for (i = 1; i < window; i++) {
@@ -698,9 +698,9 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
}
}
- /* wend is the size of the current window */
+ // wend is the size of the current window
j = wend + 1;
- /* add the 'bytes above' */
+ // add the 'bytes above'
if (!start) {
for (i = 0; i < j; i++) {
if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) {
@@ -709,12 +709,12 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
}
}
- /* wvalue will be an odd number < 2^window */
+ // wvalue will be an odd number < 2^window
if (!BN_mod_mul_montgomery(r, r, val[wvalue >> 1], mont, ctx)) {
goto err;
}
- /* move the 'window' down further */
+ // move the 'window' down further
wstart -= wend + 1;
start = 0;
if (wstart < 0) {
@@ -733,10 +733,10 @@ err:
return ret;
}
-/* BN_mod_exp_mont_consttime() stores the precomputed powers in a specific
- * layout so that accessing any of these table values shows the same access
- * pattern as far as cache lines are concerned. The following functions are
- * used to transfer a BIGNUM from/to that table. */
+// BN_mod_exp_mont_consttime() stores the precomputed powers in a specific
+// layout so that accessing any of these table values shows the same access
+// pattern as far as cache lines are concerned. The following functions are
+// used to transfer a BIGNUM from/to that table.
static int copy_to_prebuf(const BIGNUM *b, int top, unsigned char *buf, int idx,
int window) {
int i, j;
@@ -744,7 +744,7 @@ static int copy_to_prebuf(const BIGNUM *b, int top, unsigned char *buf, int idx,
BN_ULONG *table = (BN_ULONG *) buf;
if (top > b->top) {
- top = b->top; /* this works because 'buf' is explicitly zeroed */
+ top = b->top; // this works because 'buf' is explicitly zeroed
}
for (i = 0, j = idx; i < top; i++, j += width) {
@@ -778,8 +778,8 @@ static int copy_from_prebuf(BIGNUM *b, int top, unsigned char *buf, int idx,
int xstride = 1 << (window - 2);
BN_ULONG y0, y1, y2, y3;
- i = idx >> (window - 2); /* equivalent of idx / xstride */
- idx &= xstride - 1; /* equivalent of idx % xstride */
+ i = idx >> (window - 2); // equivalent of idx / xstride
+ idx &= xstride - 1; // equivalent of idx % xstride
y0 = (BN_ULONG)0 - (constant_time_eq_int(i, 0) & 1);
y1 = (BN_ULONG)0 - (constant_time_eq_int(i, 1) & 1);
@@ -804,23 +804,23 @@ static int copy_from_prebuf(BIGNUM *b, int top, unsigned char *buf, int idx,
return 1;
}
-/* BN_mod_exp_mont_conttime is based on the assumption that the L1 data cache
- * line width of the target processor is at least the following value. */
+// BN_mod_exp_mont_conttime is based on the assumption that the L1 data cache
+// line width of the target processor is at least the following value.
#define MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH (64)
#define MOD_EXP_CTIME_MIN_CACHE_LINE_MASK \
(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - 1)
-/* Window sizes optimized for fixed window size modular exponentiation
- * algorithm (BN_mod_exp_mont_consttime).
- *
- * To achieve the security goals of BN_mode_exp_mont_consttime, the maximum
- * size of the window must not exceed
- * log_2(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH).
- *
- * Window size thresholds are defined for cache line sizes of 32 and 64, cache
- * line sizes where log_2(32)=5 and log_2(64)=6 respectively. A window size of
- * 7 should only be used on processors that have a 128 byte or greater cache
- * line size. */
+// Window sizes optimized for fixed window size modular exponentiation
+// algorithm (BN_mod_exp_mont_consttime).
+//
+// To achieve the security goals of BN_mode_exp_mont_consttime, the maximum
+// size of the window must not exceed
+// log_2(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH).
+//
+// Window size thresholds are defined for cache line sizes of 32 and 64, cache
+// line sizes where log_2(32)=5 and log_2(64)=6 respectively. A window size of
+// 7 should only be used on processors that have a 128 byte or greater cache
+// line size.
#if MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 64
#define BN_window_bits_for_ctime_exponent_size(b) \
@@ -835,19 +835,18 @@ static int copy_from_prebuf(BIGNUM *b, int top, unsigned char *buf, int idx,
#endif
-/* Given a pointer value, compute the next address that is a cache line
- * multiple. */
+// Given a pointer value, compute the next address that is a cache line
+// multiple.
#define MOD_EXP_CTIME_ALIGN(x_) \
((unsigned char *)(x_) + \
(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - \
(((size_t)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK))))
-/* This variant of BN_mod_exp_mont() uses fixed windows and the special
- * precomputation memory layout to limit data-dependency to a minimum
- * to protect secret exponents (cf. the hyper-threading timing attacks
- * pointed out by Colin Percival,
- * http://www.daemonology.net/hyperthreading-considered-harmful/)
- */
+// This variant of BN_mod_exp_mont() uses fixed windows and the special
+// precomputation memory layout to limit data-dependency to a minimum
+// to protect secret exponents (cf. the hyper-threading timing attacks
+// pointed out by Colin Percival,
+// http://www.daemonology.net/hyperthreading-considered-harmful/)
int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
const BIGNUM *m, BN_CTX *ctx,
const BN_MONT_CTX *mont) {
@@ -871,7 +870,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
bits = BN_num_bits(p);
if (bits == 0) {
- /* x**0 mod 1 is still zero. */
+ // x**0 mod 1 is still zero.
if (BN_is_one(m)) {
BN_zero(rr);
return 1;
@@ -879,7 +878,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
return BN_one(rr);
}
- /* Allocate a montgomery context if it was not supplied by the caller. */
+ // Allocate a montgomery context if it was not supplied by the caller.
if (mont == NULL) {
new_mont = BN_MONT_CTX_new();
if (new_mont == NULL || !BN_MONT_CTX_set(new_mont, m, ctx)) {
@@ -898,9 +897,9 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
}
#ifdef RSAZ_ENABLED
- /* If the size of the operands allow it, perform the optimized
- * RSAZ exponentiation. For further information see
- * crypto/bn/rsaz_exp.c and accompanying assembly modules. */
+ // If the size of the operands allow it, perform the optimized
+ // RSAZ exponentiation. For further information see
+ // crypto/bn/rsaz_exp.c and accompanying assembly modules.
if ((16 == a->top) && (16 == p->top) && (BN_num_bits(m) == 1024) &&
rsaz_avx2_eligible()) {
if (!bn_wexpand(rr, 16)) {
@@ -915,19 +914,18 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
}
#endif
- /* Get the window size to use with size of p. */
+ // Get the window size to use with size of p.
window = BN_window_bits_for_ctime_exponent_size(bits);
#if defined(OPENSSL_BN_ASM_MONT5)
if (window >= 5) {
- window = 5; /* ~5% improvement for RSA2048 sign, and even for RSA4096 */
- /* reserve space for mont->N.d[] copy */
+ window = 5; // ~5% improvement for RSA2048 sign, and even for RSA4096
+ // reserve space for mont->N.d[] copy
powerbufLen += top * sizeof(mont->N.d[0]);
}
#endif
- /* Allocate a buffer large enough to hold all of the pre-computed
- * powers of am, am itself and tmp.
- */
+ // Allocate a buffer large enough to hold all of the pre-computed
+ // powers of am, am itself and tmp.
numPowers = 1 << window;
powerbufLen +=
sizeof(m->d[0]) *
@@ -953,7 +951,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
}
#endif
- /* lay down tmp and am right after powers table */
+ // lay down tmp and am right after powers table
tmp.d = (BN_ULONG *)(powerbuf + sizeof(m->d[0]) * top * numPowers);
am.d = tmp.d + top;
tmp.top = am.top = 0;
@@ -961,10 +959,10 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
tmp.neg = am.neg = 0;
tmp.flags = am.flags = BN_FLG_STATIC_DATA;
-/* prepare a^0 in Montgomery domain */
-/* by Shay Gueron's suggestion */
+// prepare a^0 in Montgomery domain
+// by Shay Gueron's suggestion
if (m->d[top - 1] & (((BN_ULONG)1) << (BN_BITS2 - 1))) {
- /* 2^(top*BN_BITS2) - m */
+ // 2^(top*BN_BITS2) - m
tmp.d[0] = (0 - m->d[0]) & BN_MASK2;
for (i = 1; i < top; i++) {
tmp.d[i] = (~m->d[i]) & BN_MASK2;
@@ -974,7 +972,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
goto err;
}
- /* prepare a^1 in Montgomery domain */
+ // prepare a^1 in Montgomery domain
assert(!a->neg);
assert(BN_ucmp(a, m) < 0);
if (!BN_to_montgomery(&am, a, mont, ctx)) {
@@ -982,18 +980,18 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
}
#if defined(OPENSSL_BN_ASM_MONT5)
- /* This optimization uses ideas from http://eprint.iacr.org/2011/239,
- * specifically optimization of cache-timing attack countermeasures
- * and pre-computation optimization. */
+ // This optimization uses ideas from http://eprint.iacr.org/2011/239,
+ // specifically optimization of cache-timing attack countermeasures
+ // and pre-computation optimization.
- /* Dedicated window==4 case improves 512-bit RSA sign by ~15%, but as
- * 512-bit RSA is hardly relevant, we omit it to spare size... */
+ // Dedicated window==4 case improves 512-bit RSA sign by ~15%, but as
+ // 512-bit RSA is hardly relevant, we omit it to spare size...
if (window == 5 && top > 1) {
const BN_ULONG *n0 = mont->n0;
BN_ULONG *np;
- /* BN_to_montgomery can contaminate words above .top
- * [in BN_DEBUG[_DEBUG] build]... */
+ // BN_to_montgomery can contaminate words above .top
+ // [in BN_DEBUG[_DEBUG] build]...
for (i = am.top; i < top; i++) {
am.d[i] = 0;
}
@@ -1001,7 +999,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
tmp.d[i] = 0;
}
- /* copy mont->N.d[] to improve cache locality */
+ // copy mont->N.d[] to improve cache locality
for (np = am.d + top, i = 0; i < top; i++) {
np[i] = mont->N.d[i];
}
@@ -1011,7 +1009,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
bn_mul_mont(tmp.d, am.d, am.d, np, n0, top);
bn_scatter5(tmp.d, top, powerbuf, 2);
- /* same as above, but uses squaring for 1/2 of operations */
+ // same as above, but uses squaring for 1/2 of operations
for (i = 4; i < 32; i *= 2) {
bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
bn_scatter5(tmp.d, top, powerbuf, i);
@@ -1042,13 +1040,12 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
}
bn_gather5(tmp.d, top, powerbuf, wvalue);
- /* At this point |bits| is 4 mod 5 and at least -1. (|bits| is the first bit
- * that has not been read yet.) */
+ // At this point |bits| is 4 mod 5 and at least -1. (|bits| is the first bit
+ // that has not been read yet.)
assert(bits >= -1 && (bits == -1 || bits % 5 == 4));
- /* Scan the exponent one window at a time starting from the most
- * significant bits.
- */
+ // Scan the exponent one window at a time starting from the most
+ // significant bits.
if (top & 7) {
while (bits >= 0) {
for (wvalue = 0, i = 0; i < 5; i++, bits--) {
@@ -1066,16 +1063,16 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
const uint8_t *p_bytes = (const uint8_t *)p->d;
int max_bits = p->top * BN_BITS2;
assert(bits < max_bits);
- /* |p = 0| has been handled as a special case, so |max_bits| is at least
- * one word. */
+ // |p = 0| has been handled as a special case, so |max_bits| is at least
+ // one word.
assert(max_bits >= 64);
- /* If the first bit to be read lands in the last byte, unroll the first
- * iteration to avoid reading past the bounds of |p->d|. (After the first
- * iteration, we are guaranteed to be past the last byte.) Note |bits|
- * here is the top bit, inclusive. */
+ // If the first bit to be read lands in the last byte, unroll the first
+ // iteration to avoid reading past the bounds of |p->d|. (After the first
+ // iteration, we are guaranteed to be past the last byte.) Note |bits|
+ // here is the top bit, inclusive.
if (bits - 4 >= max_bits - 8) {
- /* Read five bits from |bits-4| through |bits|, inclusive. */
+ // Read five bits from |bits-4| through |bits|, inclusive.
wvalue = p_bytes[p->top * BN_BYTES - 1];
wvalue >>= (bits - 4) & 7;
wvalue &= 0x1f;
@@ -1083,7 +1080,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
bn_power5(tmp.d, tmp.d, powerbuf, np, n0, top, wvalue);
}
while (bits >= 0) {
- /* Read five bits from |bits-4| through |bits|, inclusive. */
+ // Read five bits from |bits-4| through |bits|, inclusive.
int first_bit = bits - 4;
uint16_t val;
OPENSSL_memcpy(&val, p_bytes + (first_bit >> 3), sizeof(val));
@@ -1101,7 +1098,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
if (!BN_copy(rr, &tmp)) {
ret = 0;
}
- goto err; /* non-zero ret means it's not error */
+ goto err; // non-zero ret means it's not error
}
} else
#endif
@@ -1111,18 +1108,17 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
goto err;
}
- /* If the window size is greater than 1, then calculate
- * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1)
- * (even powers could instead be computed as (a^(i/2))^2
- * to use the slight performance advantage of sqr over mul).
- */
+ // If the window size is greater than 1, then calculate
+ // val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1)
+ // (even powers could instead be computed as (a^(i/2))^2
+ // to use the slight performance advantage of sqr over mul).
if (window > 1) {
if (!BN_mod_mul_montgomery(&tmp, &am, &am, mont, ctx) ||
!copy_to_prebuf(&tmp, top, powerbuf, 2, window)) {
goto err;
}
for (i = 3; i < numPowers; i++) {
- /* Calculate a^i = a^(i-1) * a */
+ // Calculate a^i = a^(i-1) * a
if (!BN_mod_mul_montgomery(&tmp, &am, &tmp, mont, ctx) ||
!copy_to_prebuf(&tmp, top, powerbuf, i, window)) {
goto err;
@@ -1138,13 +1134,12 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
goto err;
}
- /* Scan the exponent one window at a time starting from the most
- * significant bits.
- */
+ // Scan the exponent one window at a time starting from the most
+ // significant bits.
while (bits >= 0) {
- wvalue = 0; /* The 'value' of the window */
+ wvalue = 0; // The 'value' of the window
- /* Scan the window, squaring the result as we go */
+ // Scan the window, squaring the result as we go
for (i = 0; i < window; i++, bits--) {
if (!BN_mod_mul_montgomery(&tmp, &tmp, &tmp, mont, ctx)) {
goto err;
@@ -1152,19 +1147,19 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
wvalue = (wvalue << 1) + BN_is_bit_set(p, bits);
}
- /* Fetch the appropriate pre-computed value from the pre-buf */
+ // Fetch the appropriate pre-computed value from the pre-buf
if (!copy_from_prebuf(&am, top, powerbuf, wvalue, window)) {
goto err;
}
- /* Multiply the result into the intermediate result */
+ // Multiply the result into the intermediate result
if (!BN_mod_mul_montgomery(&tmp, &tmp, &am, mont, ctx)) {
goto err;
}
}
}
- /* Convert the final result from montgomery to standard format */
+ // Convert the final result from montgomery to standard format
if (!BN_from_montgomery(rr, &tmp, mont, ctx)) {
goto err;
}
@@ -1212,7 +1207,7 @@ int BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1,
int ret = 0;
BN_MONT_CTX *new_mont = NULL;
- /* Allocate a montgomery context if it was not supplied by the caller. */
+ // Allocate a montgomery context if it was not supplied by the caller.
if (mont == NULL) {
new_mont = BN_MONT_CTX_new();
if (new_mont == NULL || !BN_MONT_CTX_set(new_mont, m, ctx)) {
@@ -1221,9 +1216,9 @@ int BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1,
mont = new_mont;
}
- /* BN_mod_mul_montgomery removes one Montgomery factor, so passing one
- * Montgomery-encoded and one non-Montgomery-encoded value gives a
- * non-Montgomery-encoded result. */
+ // BN_mod_mul_montgomery removes one Montgomery factor, so passing one
+ // Montgomery-encoded and one non-Montgomery-encoded value gives a
+ // non-Montgomery-encoded result.
if (!BN_mod_exp_mont(rr, a1, p1, m, ctx, mont) ||
!BN_mod_exp_mont(&tmp, a2, p2, m, ctx, mont) ||
!BN_to_montgomery(rr, rr, mont, ctx) ||
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-25 08:21:56 +0000