1 /* mpih-const-time.c - Constant-time MPI helper functions
2 * Copyright (C) 2020 g10 Code GmbH
3 *
4 * This file is part of Libgcrypt.
5 *
6 * Libgcrypt is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 2.1 of
9 * the License, or (at your option) any later version.
10 *
11 * Libgcrypt is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this program; if not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include <config.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include "mpi-internal.h"
24 #include "g10lib.h"
25
26 #define A_LIMB_1 ((mpi_limb_t)1)
27
28 /* These variables are used to generate masks from conditional operation
29 * flag parameters. Use of volatile prevents compiler optimizations from
30 * converting AND-masking to conditional branches. */
31 static volatile mpi_limb_t vzero = 0;
32 static volatile mpi_limb_t vone = 1;
33
34 /*
35 * W = U when OP_ENABLED=1
36 * otherwise, W keeps old value
37 */
38 void
_gcry_mpih_set_cond(mpi_ptr_t wp,mpi_ptr_t up,mpi_size_t usize,unsigned long op_enable)39 _gcry_mpih_set_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
40 unsigned long op_enable)
41 {
42 mpi_size_t i;
43 mpi_limb_t mask1 = vzero - op_enable;
44 mpi_limb_t mask2 = op_enable - vone;
45
46 for (i = 0; i < usize; i++)
47 {
48 wp[i] = (wp[i] & mask2) | (up[i] & mask1);
49 }
50 }
51
52
53 /*
54 * W = U + V when OP_ENABLED=1
55 * otherwise, W = U
56 */
57 mpi_limb_t
_gcry_mpih_add_n_cond(mpi_ptr_t wp,mpi_ptr_t up,mpi_ptr_t vp,mpi_size_t usize,unsigned long op_enable)58 _gcry_mpih_add_n_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_ptr_t vp,
59 mpi_size_t usize, unsigned long op_enable)
60 {
61 mpi_size_t i;
62 mpi_limb_t cy;
63 mpi_limb_t mask1 = vzero - op_enable;
64 mpi_limb_t mask2 = op_enable - vone;
65
66 cy = 0;
67 for (i = 0; i < usize; i++)
68 {
69 mpi_limb_t u = up[i];
70 mpi_limb_t x = u + vp[i];
71 mpi_limb_t cy1 = x < u;
72 mpi_limb_t cy2;
73
74 x = x + cy;
75 cy2 = x < cy;
76 cy = cy1 | cy2;
77 wp[i] = (u & mask2) | (x & mask1);
78 }
79
80 return cy & mask1;
81 }
82
83
84 /*
85 * W = U - V when OP_ENABLED=1
86 * otherwise, W = U
87 */
88 mpi_limb_t
_gcry_mpih_sub_n_cond(mpi_ptr_t wp,mpi_ptr_t up,mpi_ptr_t vp,mpi_size_t usize,unsigned long op_enable)89 _gcry_mpih_sub_n_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_ptr_t vp,
90 mpi_size_t usize, unsigned long op_enable)
91 {
92 mpi_size_t i;
93 mpi_limb_t cy;
94 mpi_limb_t mask1 = vzero - op_enable;
95 mpi_limb_t mask2 = op_enable - vone;
96
97 cy = 0;
98 for (i = 0; i < usize; i++)
99 {
100 mpi_limb_t u = up[i];
101 mpi_limb_t x = u - vp[i];
102 mpi_limb_t cy1 = x > u;
103 mpi_limb_t cy2;
104
105 cy2 = x < cy;
106 x = x - cy;
107 cy = cy1 | cy2;
108 wp[i] = (u & mask2) | (x & mask1);
109 }
110
111 return cy & mask1;
112 }
113
114
115 /*
116 * Swap value of U and V when OP_ENABLED=1
117 * otherwise, no change
118 */
119 void
_gcry_mpih_swap_cond(mpi_ptr_t up,mpi_ptr_t vp,mpi_size_t usize,unsigned long op_enable)120 _gcry_mpih_swap_cond (mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t usize,
121 unsigned long op_enable)
122 {
123 mpi_size_t i;
124 mpi_limb_t mask1 = vzero - op_enable;
125 mpi_limb_t mask2 = op_enable - vone;
126
127 for (i = 0; i < usize; i++)
128 {
129 mpi_limb_t u = up[i];
130 mpi_limb_t v = vp[i];
131 up[i] = (u & mask2) | (v & mask1);
132 vp[i] = (u & mask1) | (v & mask2);
133 }
134 }
135
136
137 /*
138 * W = -U when OP_ENABLED=1
139 * otherwise, W = U
140 */
141 void
_gcry_mpih_abs_cond(mpi_ptr_t wp,mpi_ptr_t up,mpi_size_t usize,unsigned long op_enable)142 _gcry_mpih_abs_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
143 unsigned long op_enable)
144 {
145 mpi_size_t i;
146 mpi_limb_t mask1 = vzero - op_enable;
147 mpi_limb_t mask2 = op_enable - vone;
148 mpi_limb_t cy = op_enable;
149
150 for (i = 0; i < usize; i++)
151 {
152 mpi_limb_t u = up[i];
153 mpi_limb_t x = ~u + cy;
154
155 cy = (x < ~u);
156 wp[i] = (u & mask2) | (x & mask1);
157 }
158 }
159
160
161 /*
162 * Allocating memory for W,
163 * compute W = V % U, then return W
164 */
165 mpi_ptr_t
_gcry_mpih_mod(mpi_ptr_t vp,mpi_size_t vsize,mpi_ptr_t up,mpi_size_t usize)166 _gcry_mpih_mod (mpi_ptr_t vp, mpi_size_t vsize,
167 mpi_ptr_t up, mpi_size_t usize)
168 {
169 int secure;
170 mpi_ptr_t rp;
171 mpi_size_t i;
172
173 secure = _gcry_is_secure (vp);
174 rp = mpi_alloc_limb_space (usize, secure);
175 MPN_ZERO (rp, usize);
176
177 for (i = 0; i < vsize * BITS_PER_MPI_LIMB; i++)
178 {
179 unsigned int j = vsize * BITS_PER_MPI_LIMB - 1 - i;
180 unsigned int limbno = j / BITS_PER_MPI_LIMB;
181 unsigned int bitno = j % BITS_PER_MPI_LIMB;
182 mpi_limb_t limb = vp[limbno];
183 unsigned int the_bit = ((limb & (A_LIMB_1 << bitno)) ? 1 : 0);
184 mpi_limb_t underflow;
185 mpi_limb_t overflow;
186
187 overflow = _gcry_mpih_lshift (rp, rp, usize, 1);
188 rp[0] |= the_bit;
189
190 underflow = _gcry_mpih_sub_n (rp, rp, up, usize);
191 mpih_add_n_cond (rp, rp, up, usize, overflow ^ underflow);
192 }
193
194 return rp;
195 }
196
197 int
_gcry_mpih_cmp_ui(mpi_ptr_t up,mpi_size_t usize,unsigned long v)198 _gcry_mpih_cmp_ui (mpi_ptr_t up, mpi_size_t usize, unsigned long v)
199 {
200 int is_all_zero = 1;
201 mpi_size_t i;
202
203 for (i = 1; i < usize; i++)
204 is_all_zero &= (up[i] == 0);
205
206 if (is_all_zero)
207 return up[0] - v;
208 return 1;
209 }
210