Botan 3.0.0-alpha0
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#include <botan/internal/ct_utils.h>
12#include <botan/mem_ops.h>
13#include <botan/exceptn.h>
14
15namespace Botan {
16
17/*
18* Montgomery reduction - product scanning form
19*
20* https://www.iacr.org/archive/ches2005/006.pdf
21* https://eprint.iacr.org/2013/882.pdf
22* https://www.microsoft.com/en-us/research/wp-content/uploads/1996/01/j37acmon.pdf
23*/
24void bigint_monty_redc_generic(word z[], size_t z_size,
25 const word p[], size_t p_size, word p_dash,
26 word ws[])
27 {
28 word w2 = 0, w1 = 0, w0 = 0;
29
30 w0 = z[0];
31
32 ws[0] = w0 * p_dash;
33
34 word3_muladd(&w2, &w1, &w0, ws[0], p[0]);
35
36 w0 = w1;
37 w1 = w2;
38 w2 = 0;
39
40 for(size_t i = 1; i != p_size; ++i)
41 {
42 for(size_t j = 0; j < i; ++j)
43 {
44 word3_muladd(&w2, &w1, &w0, ws[j], p[i-j]);
45 }
46
47 word3_add(&w2, &w1, &w0, z[i]);
48
49 ws[i] = w0 * p_dash;
50
51 word3_muladd(&w2, &w1, &w0, ws[i], p[0]);
52
53 w0 = w1;
54 w1 = w2;
55 w2 = 0;
56 }
57
58 for(size_t i = 0; i != p_size; ++i)
59 {
60 for(size_t j = i + 1; j != p_size; ++j)
61 {
62 word3_muladd(&w2, &w1, &w0, ws[j], p[p_size + i-j]);
63 }
64
65 word3_add(&w2, &w1, &w0, z[p_size+i]);
66
67 ws[i] = w0;
68 w0 = w1;
69 w1 = w2;
70 w2 = 0;
71 }
72
73 word3_add(&w2, &w1, &w0, z[z_size-1]);
74
75 ws[p_size] = w0;
76 ws[p_size+1] = w1;
77
78 /*
79 * The result might need to be reduced mod p. To avoid a timing
80 * channel, always perform the subtraction. If in the compution
81 * of x - p a borrow is required then x was already < p.
82 *
83 * x starts at ws[0] and is p_size+1 bytes long.
84 * x - p starts at ws[p_size+1] and is also p_size+1 bytes log
85 *
86 * Select which address to copy from indexing off of the final
87 * borrow.
88 */
89
90 word borrow = bigint_sub3(ws + p_size + 1, ws, p_size + 1, p, p_size);
91
92 BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1);
93
94 CT::conditional_copy_mem(borrow, z, ws, ws + (p_size + 1), (p_size + 1));
95 clear_mem(z + p_size, z_size - p_size - 2);
96 }
97
98}
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:122
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:360
Definition: alg_id.cpp:13
void word3_muladd(word *w2, word *w1, word *w0, word x, word y)
Definition: mp_asmi.h:566
void word3_add(word *w2, word *w1, word *w0, word x)
Definition: mp_asmi.h:614
void bigint_monty_redc_generic(word z[], size_t z_size, const word p[], size_t p_size, word p_dash, word ws[])
Definition: mp_monty.cpp:24
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:342
constexpr void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115