/src/spdm-rs/external/ring/crypto/fipsmodule/bn/montgomery.c
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. |
2 | | // |
3 | | // Licensed under the Apache License, Version 2.0 (the "License"); |
4 | | // you may not use this file except in compliance with the License. |
5 | | // You may obtain a copy of the License at |
6 | | // |
7 | | // https://www.apache.org/licenses/LICENSE-2.0 |
8 | | // |
9 | | // Unless required by applicable law or agreed to in writing, software |
10 | | // distributed under the License is distributed on an "AS IS" BASIS, |
11 | | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
12 | | // See the License for the specific language governing permissions and |
13 | | // limitations under the License. |
14 | | |
15 | | #include "internal.h" |
16 | | #include "../../internal.h" |
17 | | |
18 | | #include "../../limbs/limbs.h" |
19 | | #include "../../limbs/limbs.inl" |
20 | | |
21 | | OPENSSL_STATIC_ASSERT(BN_MONT_CTX_N0_LIMBS == 1 || BN_MONT_CTX_N0_LIMBS == 2, |
22 | | "BN_MONT_CTX_N0_LIMBS value is invalid"); |
23 | | OPENSSL_STATIC_ASSERT( |
24 | | sizeof(BN_ULONG) * BN_MONT_CTX_N0_LIMBS == sizeof(uint64_t), |
25 | | "uint64_t is insufficient precision for n0"); |
26 | | |
27 | | int bn_from_montgomery_in_place(BN_ULONG r[], size_t num_r, BN_ULONG a[], |
28 | | size_t num_a, const BN_ULONG n[], |
29 | | size_t num_n, |
30 | 0 | const BN_ULONG n0_[BN_MONT_CTX_N0_LIMBS]) { |
31 | 0 | if (num_n == 0 || num_r != num_n || num_a != 2 * num_n) { |
32 | 0 | return 0; |
33 | 0 | } |
34 | | |
35 | | // Add multiples of |n| to |r| until R = 2^(nl * BN_BITS2) divides it. On |
36 | | // input, we had |r| < |n| * R, so now |r| < 2 * |n| * R. Note that |r| |
37 | | // includes |carry| which is stored separately. |
38 | 0 | BN_ULONG n0 = n0_[0]; |
39 | 0 | BN_ULONG carry = 0; |
40 | 0 | for (size_t i = 0; i < num_n; i++) { |
41 | 0 | BN_ULONG v = limbs_mul_add_limb(a + i, n, a[i] * n0, num_n); |
42 | 0 | v += carry + a[i + num_n]; |
43 | 0 | carry |= (v != a[i + num_n]); |
44 | 0 | carry &= (v <= a[i + num_n]); |
45 | 0 | a[i + num_n] = v; |
46 | 0 | } |
47 | | |
48 | | // Shift |num_n| words to divide by R. We have |a| < 2 * |n|. Note that |a| |
49 | | // includes |carry| which is stored separately. |
50 | 0 | a += num_n; |
51 | | |
52 | | // |a| thus requires at most one additional subtraction |n| to be reduced. |
53 | | // Subtract |n| and select the answer in constant time. |
54 | 0 | BN_ULONG v = limbs_sub(r, a, n, num_n) - carry; |
55 | | // |v| is one if |a| - |n| underflowed or zero if it did not. Note |v| cannot |
56 | | // be -1. That would imply the subtraction did not fit in |num_n| words, and |
57 | | // we know at most one subtraction is needed. |
58 | 0 | v = 0u - v; |
59 | 0 | for (size_t i = 0; i < num_n; i++) { |
60 | 0 | r[i] = constant_time_select_w(v, a[i], r[i]); |
61 | 0 | a[i] = 0; |
62 | 0 | } |
63 | 0 | return 1; |
64 | 0 | } |