]>
git.ipfire.org Git - thirdparty/openssl.git/blob - crypto/bn/bn_recp.c
80bfa2d38bfbabf2363a11eeb07da470c8fd7044
2 * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved.
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
10 #include "internal/cryptlib.h"
13 void BN_RECP_CTX_init(BN_RECP_CTX
*recp
)
15 memset(recp
, 0, sizeof(*recp
));
20 BN_RECP_CTX
*BN_RECP_CTX_new(void)
24 if ((ret
= OPENSSL_zalloc(sizeof(*ret
))) == NULL
)
29 ret
->flags
= BN_FLG_MALLOCED
;
33 void BN_RECP_CTX_free(BN_RECP_CTX
*recp
)
40 if (recp
->flags
& BN_FLG_MALLOCED
)
44 int BN_RECP_CTX_set(BN_RECP_CTX
*recp
, const BIGNUM
*d
, BN_CTX
*ctx
)
46 if (!BN_copy(&(recp
->N
), d
))
49 recp
->num_bits
= BN_num_bits(d
);
54 int BN_mod_mul_reciprocal(BIGNUM
*r
, const BIGNUM
*x
, const BIGNUM
*y
,
55 BN_RECP_CTX
*recp
, BN_CTX
*ctx
)
62 if ((a
= BN_CTX_get(ctx
)) == NULL
)
66 if (!BN_sqr(a
, x
, ctx
))
69 if (!BN_mul(a
, x
, y
, ctx
))
74 ca
= x
; /* Just do the mod */
76 ret
= BN_div_recp(NULL
, r
, ca
, recp
, ctx
);
83 int BN_div_recp(BIGNUM
*dv
, BIGNUM
*rem
, const BIGNUM
*m
,
84 BN_RECP_CTX
*recp
, BN_CTX
*ctx
)
87 BIGNUM
*a
, *b
, *d
, *r
;
90 d
= (dv
!= NULL
) ? dv
: BN_CTX_get(ctx
);
91 r
= (rem
!= NULL
) ? rem
: BN_CTX_get(ctx
);
97 if (BN_ucmp(m
, &(recp
->N
)) < 0) {
108 * We want the remainder Given input of ABCDEF / ab we need multiply
109 * ABCDEF by 3 digests of the reciprocal of ab
112 /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */
114 j
= recp
->num_bits
<< 1;
118 /* Nr := round(2^i / N) */
119 if (i
!= recp
->shift
)
120 recp
->shift
= BN_reciprocal(&(recp
->Nr
), &(recp
->N
), i
, ctx
);
121 /* BN_reciprocal could have returned -1 for an error */
122 if (recp
->shift
== -1)
126 * d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|
127 * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|
128 * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
131 if (!BN_rshift(a
, m
, recp
->num_bits
))
133 if (!BN_mul(b
, a
, &(recp
->Nr
), ctx
))
135 if (!BN_rshift(d
, b
, i
- recp
->num_bits
))
139 if (!BN_mul(b
, &(recp
->N
), d
, ctx
))
141 if (!BN_usub(r
, m
, b
))
146 while (BN_ucmp(r
, &(recp
->N
)) >= 0) {
148 BNerr(BN_F_BN_DIV_RECP
, BN_R_BAD_RECIPROCAL
);
151 if (!BN_usub(r
, r
, &(recp
->N
)))
153 if (!BN_add_word(d
, 1))
157 r
->neg
= BN_is_zero(r
) ? 0 : m
->neg
;
158 d
->neg
= m
->neg
^ recp
->N
.neg
;
168 * len is the expected size of the result We actually calculate with an extra
169 * word of precision, so we can do faster division if the remainder is not
173 int BN_reciprocal(BIGNUM
*r
, const BIGNUM
*m
, int len
, BN_CTX
*ctx
)
179 if ((t
= BN_CTX_get(ctx
)) == NULL
)
182 if (!BN_set_bit(t
, len
))
185 if (!BN_div(r
, NULL
, t
, m
, ctx
))