1 /* 2 * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the OpenSSL license (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10 #include "internal/cryptlib.h" 11 #include "bn_lcl.h" 12 13 void BN_RECP_CTX_init(BN_RECP_CTX *recp) 14 { 15 memset(recp, 0, sizeof(*recp)); 16 bn_init(&(recp->N)); 17 bn_init(&(recp->Nr)); 18 } 19 20 BN_RECP_CTX *BN_RECP_CTX_new(void) 21 { 22 BN_RECP_CTX *ret; 23 24 if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) { 25 BNerr(BN_F_BN_RECP_CTX_NEW, ERR_R_MALLOC_FAILURE); 26 return NULL; 27 } 28 29 bn_init(&(ret->N)); 30 bn_init(&(ret->Nr)); 31 ret->flags = BN_FLG_MALLOCED; 32 return ret; 33 } 34 35 void BN_RECP_CTX_free(BN_RECP_CTX *recp) 36 { 37 if (recp == NULL) 38 return; 39 BN_free(&recp->N); 40 BN_free(&recp->Nr); 41 if (recp->flags & BN_FLG_MALLOCED) 42 OPENSSL_free(recp); 43 } 44 45 int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx) 46 { 47 if (!BN_copy(&(recp->N), d)) 48 return 0; 49 BN_zero(&(recp->Nr)); 50 recp->num_bits = BN_num_bits(d); 51 recp->shift = 0; 52 return 1; 53 } 54 55 int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y, 56 BN_RECP_CTX *recp, BN_CTX *ctx) 57 { 58 int ret = 0; 59 BIGNUM *a; 60 const BIGNUM *ca; 61 62 BN_CTX_start(ctx); 63 if ((a = BN_CTX_get(ctx)) == NULL) 64 goto err; 65 if (y != NULL) { 66 if (x == y) { 67 if (!BN_sqr(a, x, ctx)) 68 goto err; 69 } else { 70 if (!BN_mul(a, x, y, ctx)) 71 goto err; 72 } 73 ca = a; 74 } else 75 ca = x; /* Just do the mod */ 76 77 ret = BN_div_recp(NULL, r, ca, recp, ctx); 78 err: 79 BN_CTX_end(ctx); 80 bn_check_top(r); 81 return ret; 82 } 83 84 int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, 85 BN_RECP_CTX *recp, BN_CTX *ctx) 86 { 87 int i, j, ret = 0; 88 BIGNUM *a, *b, *d, *r; 89 90 BN_CTX_start(ctx); 91 d = (dv != NULL) ? dv : BN_CTX_get(ctx); 92 r = (rem != NULL) ? rem : BN_CTX_get(ctx); 93 a = BN_CTX_get(ctx); 94 b = BN_CTX_get(ctx); 95 if (b == NULL) 96 goto err; 97 98 if (BN_ucmp(m, &(recp->N)) < 0) { 99 BN_zero(d); 100 if (!BN_copy(r, m)) { 101 BN_CTX_end(ctx); 102 return 0; 103 } 104 BN_CTX_end(ctx); 105 return 1; 106 } 107 108 /* 109 * We want the remainder Given input of ABCDEF / ab we need multiply 110 * ABCDEF by 3 digests of the reciprocal of ab 111 */ 112 113 /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */ 114 i = BN_num_bits(m); 115 j = recp->num_bits << 1; 116 if (j > i) 117 i = j; 118 119 /* Nr := round(2^i / N) */ 120 if (i != recp->shift) 121 recp->shift = BN_reciprocal(&(recp->Nr), &(recp->N), i, ctx); 122 /* BN_reciprocal could have returned -1 for an error */ 123 if (recp->shift == -1) 124 goto err; 125 126 /*- 127 * d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))| 128 * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))| 129 * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)| 130 * = |m/N| 131 */ 132 if (!BN_rshift(a, m, recp->num_bits)) 133 goto err; 134 if (!BN_mul(b, a, &(recp->Nr), ctx)) 135 goto err; 136 if (!BN_rshift(d, b, i - recp->num_bits)) 137 goto err; 138 d->neg = 0; 139 140 if (!BN_mul(b, &(recp->N), d, ctx)) 141 goto err; 142 if (!BN_usub(r, m, b)) 143 goto err; 144 r->neg = 0; 145 146 j = 0; 147 while (BN_ucmp(r, &(recp->N)) >= 0) { 148 if (j++ > 2) { 149 BNerr(BN_F_BN_DIV_RECP, BN_R_BAD_RECIPROCAL); 150 goto err; 151 } 152 if (!BN_usub(r, r, &(recp->N))) 153 goto err; 154 if (!BN_add_word(d, 1)) 155 goto err; 156 } 157 158 r->neg = BN_is_zero(r) ? 0 : m->neg; 159 d->neg = m->neg ^ recp->N.neg; 160 ret = 1; 161 err: 162 BN_CTX_end(ctx); 163 bn_check_top(dv); 164 bn_check_top(rem); 165 return ret; 166 } 167 168 /* 169 * len is the expected size of the result We actually calculate with an extra 170 * word of precision, so we can do faster division if the remainder is not 171 * required. 172 */ 173 /* r := 2^len / m */ 174 int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx) 175 { 176 int ret = -1; 177 BIGNUM *t; 178 179 BN_CTX_start(ctx); 180 if ((t = BN_CTX_get(ctx)) == NULL) 181 goto err; 182 183 if (!BN_set_bit(t, len)) 184 goto err; 185 186 if (!BN_div(r, NULL, t, m, ctx)) 187 goto err; 188 189 ret = len; 190 err: 191 bn_check_top(r); 192 BN_CTX_end(ctx); 193 return ret; 194 } 195