From 66ed3801fd63ca8372bb74241e31e39c044b64c5 Mon Sep 17 00:00:00 2001 From: tb Date: Mon, 23 Jul 2018 18:07:21 +0000 Subject: [PATCH] Clean up our disgusting implementations of BN_{,u}{add,sub}(), following changes made in OpenSSL by Davide Galassi and others, so that one can actually follow what is going on. There is no performance impact from this change as the code still does essentially the same thing. There's a ton of work still to be done to make the BN code less terrible. ok jsing, kn --- lib/libcrypto/bn/bn_add.c | 224 ++++++++++++-------------------------- 1 file changed, 67 insertions(+), 157 deletions(-) diff --git a/lib/libcrypto/bn/bn_add.c b/lib/libcrypto/bn/bn_add.c index 2e82d280eca..048a136b95d 100644 --- a/lib/libcrypto/bn/bn_add.c +++ b/lib/libcrypto/bn/bn_add.c @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_add.c,v 1.12 2018/06/10 19:38:19 tb Exp $ */ +/* $OpenBSD: bn_add.c,v 1.13 2018/07/23 18:07:21 tb Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -62,61 +62,51 @@ #include "bn_lcl.h" -/* r can == a or b */ int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { - const BIGNUM *tmp; - int a_neg = a->neg, ret; + int ret, r_neg; bn_check_top(a); bn_check_top(b); - /* a + b a+b - * a + -b a-b - * -a + b b-a - * -a + -b -(a+b) - */ - if (a_neg ^ b->neg) { - /* only one is negative */ - if (a_neg) { - tmp = a; - a = b; - b = tmp; - } - - /* we are now a - b */ - - if (BN_ucmp(a, b) < 0) { - if (!BN_usub(r, b, a)) - return (0); - r->neg = 1; + if (a->neg == b->neg) { + r_neg = a->neg; + ret = BN_uadd(r, a, b); + } else { + int cmp = BN_ucmp(a, b); + + if (cmp > 0) { + r_neg = a->neg; + ret = BN_usub(r, a, b); + } else if (cmp < 0) { + r_neg = b->neg; + ret = BN_usub(r, b, a); } else { - if (!BN_usub(r, a, b)) - return (0); - r->neg = 0; + r_neg = 0; + BN_zero(r); + ret = 1; } - return (1); } - ret = BN_uadd(r, a, b); - r->neg = a_neg; + r->neg = r_neg; bn_check_top(r); return ret; } -/* unsigned add of b to a */ int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { int max, min, dif; - BN_ULONG *ap, *bp, *rp, carry, t1, t2; - const BIGNUM *tmp; + const BN_ULONG *ap, *bp; + BN_ULONG *rp, carry, t1, t2; bn_check_top(a); bn_check_top(b); if (a->top < b->top) { + const BIGNUM *tmp; + tmp = a; a = b; b = tmp; @@ -137,41 +127,28 @@ BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) carry = bn_add_words(rp, ap, bp, min); rp += min; ap += min; - bp += min; - - if (carry) { - while (dif) { - dif--; - t1 = *(ap++); - t2 = (t1 + 1) & BN_MASK2; - *(rp++) = t2; - if (t2) { - carry = 0; - break; - } - } - if (carry) { - /* carry != 0 => dif == 0 */ - *rp = 1; - r->top++; - } + + while (dif) { + dif--; + t1 = *(ap++); + t2 = (t1 + carry) & BN_MASK2; + *(rp++) = t2; + carry &= (t2 == 0); } - if (dif && rp != ap) - while (dif--) - /* copy remaining words if ap != rp */ - *(rp++) = *(ap++); + *rp = carry; + r->top += carry; + r->neg = 0; bn_check_top(r); return 1; } -/* unsigned subtraction of b from a, a must be larger than b. */ int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { int max, min, dif; - BN_ULONG t1, t2, *ap, *bp, *rp; - int i, carry; + const BN_ULONG *ap, *bp; + BN_ULONG t1, t2, borrow, *rp; bn_check_top(a); bn_check_top(b); @@ -180,134 +157,67 @@ BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) min = b->top; dif = max - min; - if (dif < 0) /* hmm... should not be happening */ - { + if (dif < 0) { BNerror(BN_R_ARG2_LT_ARG3); - return (0); + return 0; } if (bn_wexpand(r, max) == NULL) - return (0); + return 0; ap = a->d; bp = b->d; rp = r->d; -#if 1 - carry = 0; - for (i = min; i != 0; i--) { - t1= *(ap++); - t2= *(bp++); - if (carry) { - carry = (t1 <= t2); - t1 = (t1 - t2 - 1)&BN_MASK2; - } else { - carry = (t1 < t2); - t1 = (t1 - t2)&BN_MASK2; - } - *(rp++) = t1&BN_MASK2; - } -#else - carry = bn_sub_words(rp, ap, bp, min); + borrow = bn_sub_words(rp, ap, bp, min); ap += min; - bp += min; rp += min; -#endif - if (carry) /* subtracted */ - { - if (!dif) - /* error: a < b */ - return 0; - while (dif) { - dif--; - t1 = *(ap++); - t2 = (t1 - 1)&BN_MASK2; - *(rp++) = t2; - if (t1) - break; - } - } -#if 0 - memcpy(rp, ap, sizeof(*rp)*(max - i)); -#else - if (rp != ap) { - for (;;) { - if (!dif--) - break; - rp[0] = ap[0]; - if (!dif--) - break; - rp[1] = ap[1]; - if (!dif--) - break; - rp[2] = ap[2]; - if (!dif--) - break; - rp[3] = ap[3]; - rp += 4; - ap += 4; - } + + while (dif) { + dif--; + t1 = *(ap++); + t2 = (t1 - borrow) & BN_MASK2; + *(rp++) = t2; + borrow &= (t1 == 0); } -#endif + + while (max > 0 && *--rp == 0) + max--; r->top = max; r->neg = 0; bn_correct_top(r); - return (1); + return 1; } int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { - int max; - int add = 0, neg = 0; - const BIGNUM *tmp; + int ret, r_neg; bn_check_top(a); bn_check_top(b); - /* a - b a-b - * a - -b a+b - * -a - b -(a+b) - * -a - -b b-a - */ - if (a->neg) { - if (b->neg) { - tmp = a; - a = b; - b = tmp; - } else { - add = 1; - neg = 1; - } + if (a->neg != b->neg) { + r_neg = a->neg; + ret = BN_uadd(r, a, b); } else { - if (b->neg) { - add = 1; - neg = 0; + int cmp = BN_ucmp(a, b); + + if (cmp > 0) { + r_neg = a->neg; + ret = BN_usub(r, a, b); + } else if (cmp < 0) { + r_neg = !b->neg; + ret = BN_usub(r, b, a); + } else { + r_neg = 0; + BN_zero(r); + ret = 1; } } - if (add) { - if (!BN_uadd(r, a, b)) - return (0); - r->neg = neg; - return (1); - } - - /* We are actually doing a - b :-) */ - - max = (a->top > b->top) ? a->top : b->top; - if (bn_wexpand(r, max) == NULL) - return (0); - if (BN_ucmp(a, b) < 0) { - if (!BN_usub(r, b, a)) - return (0); - r->neg = 1; - } else { - if (!BN_usub(r, a, b)) - return (0); - r->neg = 0; - } + r->neg = r_neg; bn_check_top(r); - return (1); + return ret; } -- 2.20.1