Botan 2.19.1
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/mp_monty.h>
12#include <botan/internal/mp_madd.h>
13#include <botan/internal/mp_asmi.h>
14#include <botan/internal/ct_utils.h>
15#include <botan/mem_ops.h>
16#include <botan/exceptn.h>
17
18namespace Botan {
19
20namespace {
21
22/*
23* Montgomery reduction - product scanning form
24*
25* https://www.iacr.org/archive/ches2005/006.pdf
26* https://eprint.iacr.org/2013/882.pdf
27* https://www.microsoft.com/en-us/research/wp-content/uploads/1996/01/j37acmon.pdf
28*/
29void bigint_monty_redc_generic(word z[], size_t z_size,
30 const word p[], size_t p_size, word p_dash,
31 word ws[])
32 {
33 word w2 = 0, w1 = 0, w0 = 0;
34
35 w0 = z[0];
36
37 ws[0] = w0 * p_dash;
38
39 word3_muladd(&w2, &w1, &w0, ws[0], p[0]);
40
41 w0 = w1;
42 w1 = w2;
43 w2 = 0;
44
45 for(size_t i = 1; i != p_size; ++i)
46 {
47 for(size_t j = 0; j < i; ++j)
48 {
49 word3_muladd(&w2, &w1, &w0, ws[j], p[i-j]);
50 }
51
52 word3_add(&w2, &w1, &w0, z[i]);
53
54 ws[i] = w0 * p_dash;
55
56 word3_muladd(&w2, &w1, &w0, ws[i], p[0]);
57
58 w0 = w1;
59 w1 = w2;
60 w2 = 0;
61 }
62
63 for(size_t i = 0; i != p_size; ++i)
64 {
65 for(size_t j = i + 1; j != p_size; ++j)
66 {
67 word3_muladd(&w2, &w1, &w0, ws[j], p[p_size + i-j]);
68 }
69
70 word3_add(&w2, &w1, &w0, z[p_size+i]);
71
72 ws[i] = w0;
73 w0 = w1;
74 w1 = w2;
75 w2 = 0;
76 }
77
78 word3_add(&w2, &w1, &w0, z[z_size-1]);
79
80 ws[p_size] = w0;
81 ws[p_size+1] = w1;
82
83 /*
84 * The result might need to be reduced mod p. To avoid a timing
85 * channel, always perform the subtraction. If in the compution
86 * of x - p a borrow is required then x was already < p.
87 *
88 * x starts at ws[0] and is p_size+1 bytes long.
89 * x - p starts at ws[p_size+1] and is also p_size+1 bytes log
90 *
91 * Select which address to copy from indexing off of the final
92 * borrow.
93 */
94
95 // word borrow = bigint_sub3(ws + p_size + 1, ws, p_size + 1, p, p_size);
96 word borrow = 0;
97 for(size_t i = 0; i != p_size; ++i)
98 ws[p_size + 1 + i] = word_sub(ws[i], p[i], &borrow);
99 ws[2*p_size+1] = word_sub(ws[p_size], 0, &borrow);
100
101 BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1);
102
103 CT::conditional_copy_mem(borrow, z, ws, ws + (p_size + 1), (p_size + 1));
104 clear_mem(z + p_size, z_size - p_size - 2);
105 }
106
107}
108
109void bigint_monty_redc(word z[],
110 const word p[], size_t p_size, word p_dash,
111 word ws[], size_t ws_size)
112 {
113 const size_t z_size = 2*(p_size+1);
114
115 BOTAN_ARG_CHECK(ws_size >= z_size, "workspace too small");
116
117 if(p_size == 4)
118 bigint_monty_redc_4(z, p, p_dash, ws);
119 else if(p_size == 6)
120 bigint_monty_redc_6(z, p, p_dash, ws);
121 else if(p_size == 8)
122 bigint_monty_redc_8(z, p, p_dash, ws);
123 else if(p_size == 16)
124 bigint_monty_redc_16(z, p, p_dash, ws);
125 else if(p_size == 24)
126 bigint_monty_redc_24(z, p, p_dash, ws);
127 else if(p_size == 32)
128 bigint_monty_redc_32(z, p, p_dash, ws);
129 else
130 bigint_monty_redc_generic(z, z_size, p, p_size, p_dash, ws);
131 }
132
133}
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
#define BOTAN_ARG_CHECK(expr, msg)
Definition: assert.h:37
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:363
Definition: alg_id.cpp:13
word word_sub(word x, word y, word *carry)
Definition: mp_asmi.h:209
void word3_muladd(word *w2, word *w1, word *w0, word x, word y)
Definition: mp_asmi.h:451
void bigint_monty_redc_24(word z[], const word p[], word p_dash, word ws[])
void bigint_monty_redc_8(word z[], const word p[], word p_dash, word ws[])
void bigint_monty_redc_16(word z[], const word p[], word p_dash, word ws[])
void bigint_monty_redc_4(word z[], const word p[], word p_dash, word ws[])
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
Definition: mp_monty.cpp:109
void word3_add(word *w2, word *w1, word *w0, word x)
Definition: mp_asmi.h:500
void bigint_monty_redc_32(word z[], const word p[], word p_dash, word ws[])
void bigint_monty_redc_6(word z[], const word p[], word p_dash, word ws[])
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115