]>
git.ipfire.org Git - thirdparty/openssl.git/blob - crypto/bn/bn_recp.c
2 * Copyright 1995-2020 The OpenSSL Project Authors. All Rights Reserved.
4 * Licensed under the Apache License 2.0 (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
)
39 if (recp
->flags
& BN_FLG_MALLOCED
)
43 int BN_RECP_CTX_set(BN_RECP_CTX
*recp
, const BIGNUM
*d
, BN_CTX
*ctx
)
45 if (!BN_copy(&(recp
->N
), d
))
48 recp
->num_bits
= BN_num_bits(d
);
53 int BN_mod_mul_reciprocal(BIGNUM
*r
, const BIGNUM
*x
, const BIGNUM
*y
,
54 BN_RECP_CTX
*recp
, BN_CTX
*ctx
)
61 if ((a
= BN_CTX_get(ctx
)) == NULL
)
65 if (!BN_sqr(a
, x
, ctx
))
68 if (!BN_mul(a
, x
, y
, ctx
))
73 ca
= x
; /* Just do the mod */
75 ret
= BN_div_recp(NULL
, r
, ca
, recp
, ctx
);
82 int BN_div_recp(BIGNUM
*dv
, BIGNUM
*rem
, const BIGNUM
*m
,
83 BN_RECP_CTX
*recp
, BN_CTX
*ctx
)
86 BIGNUM
*a
, *b
, *d
, *r
;
89 d
= (dv
!= NULL
) ? dv
: BN_CTX_get(ctx
);
90 r
= (rem
!= NULL
) ? rem
: BN_CTX_get(ctx
);
96 if (BN_ucmp(m
, &(recp
->N
)) < 0) {
107 * We want the remainder Given input of ABCDEF / ab we need multiply
108 * ABCDEF by 3 digests of the reciprocal of ab
111 /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */
113 j
= recp
->num_bits
<< 1;
117 /* Nr := round(2^i / N) */
118 if (i
!= recp
->shift
)
119 recp
->shift
= BN_reciprocal(&(recp
->Nr
), &(recp
->N
), i
, ctx
);
120 /* BN_reciprocal could have returned -1 for an error */
121 if (recp
->shift
== -1)
125 * d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|
126 * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|
127 * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
130 if (!BN_rshift(a
, m
, recp
->num_bits
))
132 if (!BN_mul(b
, a
, &(recp
->Nr
), ctx
))
134 if (!BN_rshift(d
, b
, i
- recp
->num_bits
))
138 if (!BN_mul(b
, &(recp
->N
), d
, ctx
))
140 if (!BN_usub(r
, m
, b
))
145 while (BN_ucmp(r
, &(recp
->N
)) >= 0) {
147 ERR_raise(ERR_LIB_BN
, BN_R_BAD_RECIPROCAL
);
150 if (!BN_usub(r
, r
, &(recp
->N
)))
152 if (!BN_add_word(d
, 1))
156 r
->neg
= BN_is_zero(r
) ? 0 : m
->neg
;
157 d
->neg
= m
->neg
^ recp
->N
.neg
;
167 * len is the expected size of the result We actually calculate with an extra
168 * word of precision, so we can do faster division if the remainder is not
172 int BN_reciprocal(BIGNUM
*r
, const BIGNUM
*m
, int len
, BN_CTX
*ctx
)
178 if ((t
= BN_CTX_get(ctx
)) == NULL
)
181 if (!BN_set_bit(t
, len
))
184 if (!BN_div(r
, NULL
, t
, m
, ctx
))