Botan 3.8.0
Crypto and TLS for C&
mp_monty.cpp
Go to the documentation of this file.
1/*
2* Montgomery Reduction
3* (C) 1999-2011 Jack Lloyd
4* 2006 Luca Piccarreta
5* 2016 Matthias Gierlings
6*
7* Botan is released under the Simplified BSD License (see license.txt)
8*/
9
10#include <botan/internal/mp_core.h>
11
12#include <botan/assert.h>
13#include <botan/exceptn.h>
14#include <botan/mem_ops.h>
15#include <botan/internal/ct_utils.h>
16
17namespace Botan {
18
19/*
20* Montgomery reduction - product scanning form
21*
22* Algorithm 5 from "Energy-Efficient Software Implementation of Long
23* Integer Modular Arithmetic"
24* (https://www.iacr.org/archive/ches2005/006.pdf)
25*
26* See also
27*
28* https://eprint.iacr.org/2013/882.pdf
29* https://www.microsoft.com/en-us/research/wp-content/uploads/1996/01/j37acmon.pdf
30*/
32 word r[], const word z[], size_t z_size, const word p[], size_t p_size, word p_dash, word ws[]) {
33 BOTAN_ARG_CHECK(z_size >= 2 * p_size && p_size > 0, "Invalid sizes for bigint_monty_redc_generic");
34
35 word3<word> accum;
36
37 accum.add(z[0]);
38
39 ws[0] = accum.monty_step(p[0], p_dash);
40
41 for(size_t i = 1; i != p_size; ++i) {
42 for(size_t j = 0; j < i; ++j) {
43 accum.mul(ws[j], p[i - j]);
44 }
45
46 accum.add(z[i]);
47 ws[i] = accum.monty_step(p[0], p_dash);
48 }
49
50 for(size_t i = 0; i != p_size - 1; ++i) {
51 for(size_t j = i + 1; j != p_size; ++j) {
52 accum.mul(ws[j], p[p_size + i - j]);
53 }
54
55 accum.add(z[p_size + i]);
56 ws[i] = accum.extract();
57 }
58
59 accum.add(z[2 * p_size - 1]);
60
61 ws[p_size - 1] = accum.extract();
62 // w1 is the final part, which is not stored in the workspace
63 const word w1 = accum.extract();
64
65 /*
66 * The result might need to be reduced mod p. To avoid a timing
67 * channel, always perform the subtraction. If in the compution
68 * of x - p a borrow is required then x was already < p.
69 *
70 * x starts at ws[0] and is p_size bytes long plus a possible high
71 * digit left over in w1.
72 *
73 * x - p starts at z[0] and is also p_size bytes long
74 *
75 * If borrow was set after the subtraction, then x was already less
76 * than p and the subtraction was not needed. In that case overwrite
77 * z[0:p_size] with the original x in ws[0:p_size].
78 *
79 * We only copy out p_size in the final step because we know
80 * the Montgomery result is < P
81 */
82
83 bigint_monty_maybe_sub(p_size, r, w1, ws, p);
84}
85
86} // namespace Botan
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:31
constexpr void add(W x)
Definition mp_asmi.h:574
constexpr W monty_step(W p0, W p_dash)
Definition mp_asmi.h:591
constexpr W extract()
Definition mp_asmi.h:583
constexpr void mul(W x, W y)
Definition mp_asmi.h:509
BOTAN_FUZZER_API void bigint_monty_redc_generic(word r[], const word z[], size_t z_size, const word p[], size_t p_size, word p_dash, word ws[])
Definition mp_monty.cpp:31
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
Definition mp_core.h:344
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
Definition types.h:119