Remove the decaf_bzero function and replace with OPENSSL_cleanse()
[openssl.git] / crypto / ec / curve448 / scalar.c
1 /**
2  * @file ed448goldilocks/scalar.c
3  * @author Mike Hamburg
4  *
5  * @copyright
6  *   Copyright (c) 2015-2016 Cryptography Research, Inc.  \n
7  *   Released under the MIT License.  See LICENSE.txt for license information.
8  *
9  * @brief Decaf high-level functions.
10  *
11  * @warning This file was automatically generated in Python.
12  * Please do not edit it.
13  */
14 #include <openssl/crypto.h>
15
16 #include "word.h"
17 #include "constant_time.h"
18 #include "point_448.h"
19
20 /* Template stuff */
21 #define API_NS(_id) decaf_448_##_id
22 #define SCALAR_BITS DECAF_448_SCALAR_BITS
23 #define SCALAR_SER_BYTES DECAF_448_SCALAR_BYTES
24 #define SCALAR_LIMBS DECAF_448_SCALAR_LIMBS
25 #define scalar_t API_NS(scalar_t)
26
27 static const decaf_word_t MONTGOMERY_FACTOR = (decaf_word_t)0x3bd440fae918bc5ull;
28 static const scalar_t sc_p = {{{
29     SC_LIMB(0x2378c292ab5844f3), SC_LIMB(0x216cc2728dc58f55), SC_LIMB(0xc44edb49aed63690), SC_LIMB(0xffffffff7cca23e9), SC_LIMB(0xffffffffffffffff), SC_LIMB(0xffffffffffffffff), SC_LIMB(0x3fffffffffffffff)
30 }}}, sc_r2 = {{{
31     SC_LIMB(0xe3539257049b9b60), SC_LIMB(0x7af32c4bc1b195d9), SC_LIMB(0x0d66de2388ea1859), SC_LIMB(0xae17cf725ee4d838), SC_LIMB(0x1a9cc14ba3c47c44), SC_LIMB(0x2052bcb7e4d070af), SC_LIMB(0x3402a939f823b729)
32 }}};
33 /* End of template stuff */
34
35 #define WBITS DECAF_WORD_BITS /* NB this may be different from ARCH_WORD_BITS */
36
37 const scalar_t API_NS(scalar_one) = {{{1}}}, API_NS(scalar_zero) = {{{0}}};
38
39 /** {extra,accum} - sub +? p
40  * Must have extra <= 1
41  */
42 static DECAF_NOINLINE void sc_subx(
43     scalar_t out,
44     const decaf_word_t accum[SCALAR_LIMBS],
45     const scalar_t sub,
46     const scalar_t p,
47     decaf_word_t extra
48 ) {
49     decaf_dsword_t chain = 0;
50     unsigned int i;
51     for (i=0; i<SCALAR_LIMBS; i++) {
52         chain = (chain + accum[i]) - sub->limb[i];
53         out->limb[i] = chain;
54         chain >>= WBITS;
55     }
56     decaf_word_t borrow = chain+extra; /* = 0 or -1 */
57     
58     chain = 0;
59     for (i=0; i<SCALAR_LIMBS; i++) {
60         chain = (chain + out->limb[i]) + (p->limb[i] & borrow);
61         out->limb[i] = chain;
62         chain >>= WBITS;
63     }
64 }
65
66 static DECAF_NOINLINE void sc_montmul (
67     scalar_t out,
68     const scalar_t a,
69     const scalar_t b
70 ) {
71     unsigned int i,j;
72     decaf_word_t accum[SCALAR_LIMBS+1] = {0};
73     decaf_word_t hi_carry = 0;
74     
75     for (i=0; i<SCALAR_LIMBS; i++) {
76         decaf_word_t mand = a->limb[i];
77         const decaf_word_t *mier = b->limb;
78         
79         decaf_dword_t chain = 0;
80         for (j=0; j<SCALAR_LIMBS; j++) {
81             chain += ((decaf_dword_t)mand)*mier[j] + accum[j];
82             accum[j] = chain;
83             chain >>= WBITS;
84         }
85         accum[j] = chain;
86         
87         mand = accum[0] * MONTGOMERY_FACTOR;
88         chain = 0;
89         mier = sc_p->limb;
90         for (j=0; j<SCALAR_LIMBS; j++) {
91             chain += (decaf_dword_t)mand*mier[j] + accum[j];
92             if (j) accum[j-1] = chain;
93             chain >>= WBITS;
94         }
95         chain += accum[j];
96         chain += hi_carry;
97         accum[j-1] = chain;
98         hi_carry = chain >> WBITS;
99     }
100     
101     sc_subx(out, accum, sc_p, sc_p, hi_carry);
102 }
103
104 void API_NS(scalar_mul) (
105     scalar_t out,
106     const scalar_t a,
107     const scalar_t b
108 ) {
109     sc_montmul(out,a,b);
110     sc_montmul(out,out,sc_r2);
111 }
112
113 /* PERF: could implement this */
114 static DECAF_INLINE void sc_montsqr (scalar_t out, const scalar_t a) {
115     sc_montmul(out,a,a);
116 }
117
118 decaf_error_t API_NS(scalar_invert) (
119     scalar_t out,
120     const scalar_t a
121 ) {
122     /* Fermat's little theorem, sliding window.
123      * Sliding window is fine here because the modulus isn't secret.
124      */
125     const int SCALAR_WINDOW_BITS = 3;
126     scalar_t precmp[1<<SCALAR_WINDOW_BITS];
127     const int LAST = (1<<SCALAR_WINDOW_BITS)-1;
128
129     /* Precompute precmp = [a^1,a^3,...] */
130     sc_montmul(precmp[0],a,sc_r2);
131     if (LAST > 0) sc_montmul(precmp[LAST],precmp[0],precmp[0]);
132
133     int i;
134     for (i=1; i<=LAST; i++) {
135         sc_montmul(precmp[i],precmp[i-1],precmp[LAST]);
136     }
137     
138     /* Sliding window */
139     unsigned residue = 0, trailing = 0, started = 0;
140     for (i=SCALAR_BITS-1; i>=-SCALAR_WINDOW_BITS; i--) {
141         
142         if (started) sc_montsqr(out,out);
143         
144         decaf_word_t w = (i>=0) ? sc_p->limb[i/WBITS] : 0;
145         if (i >= 0 && i<WBITS) {
146             assert(w >= 2);
147             w-=2;
148         }
149         
150         residue = (residue<<1) | ((w>>(i%WBITS))&1);
151         if (residue>>SCALAR_WINDOW_BITS != 0) {
152             assert(trailing == 0);
153             trailing = residue;
154             residue = 0;
155         }
156         
157         if (trailing > 0 && (trailing & ((1<<SCALAR_WINDOW_BITS)-1)) == 0) {
158             if (started) {
159                 sc_montmul(out,out,precmp[trailing>>(SCALAR_WINDOW_BITS+1)]);
160             } else {
161                 API_NS(scalar_copy)(out,precmp[trailing>>(SCALAR_WINDOW_BITS+1)]);
162                 started = 1;
163             }
164             trailing = 0;
165         }
166         trailing <<= 1;
167         
168     }
169     assert(residue==0);
170     assert(trailing==0);
171     
172     /* Demontgomerize */
173     sc_montmul(out,out,API_NS(scalar_one));
174     OPENSSL_cleanse(precmp, sizeof(precmp));
175     return decaf_succeed_if(~API_NS(scalar_eq)(out,API_NS(scalar_zero)));
176 }
177
178 void API_NS(scalar_sub) (
179     scalar_t out,
180     const scalar_t a,
181     const scalar_t b
182 ) {
183     sc_subx(out, a->limb, b, sc_p, 0);
184 }
185
186 void API_NS(scalar_add) (
187     scalar_t out,
188     const scalar_t a,
189     const scalar_t b
190 ) {
191     decaf_dword_t chain = 0;
192     unsigned int i;
193     for (i=0; i<SCALAR_LIMBS; i++) {
194         chain = (chain + a->limb[i]) + b->limb[i];
195         out->limb[i] = chain;
196         chain >>= WBITS;
197     }
198     sc_subx(out, out->limb, sc_p, sc_p, chain);
199 }
200
201 void
202 API_NS(scalar_set_unsigned) (
203     scalar_t out,
204     uint64_t w
205 ) {
206     memset(out,0,sizeof(scalar_t));
207     unsigned int i = 0;
208     for (; i<sizeof(uint64_t)/sizeof(decaf_word_t); i++) {
209         out->limb[i] = w;
210 #if DECAF_WORD_BITS < 64
211         w >>= 8*sizeof(decaf_word_t);
212 #endif
213     }
214 }
215
216 decaf_bool_t
217 API_NS(scalar_eq) (
218     const scalar_t a,
219     const scalar_t b
220 ) {
221     decaf_word_t diff = 0;
222     unsigned int i;
223     for (i=0; i<SCALAR_LIMBS; i++) {
224         diff |= a->limb[i] ^ b->limb[i];
225     }
226     return mask_to_bool(word_is_zero(diff));
227 }
228
229 static DECAF_INLINE void scalar_decode_short (
230     scalar_t s,
231     const unsigned char *ser,
232     unsigned int nbytes
233 ) {
234     unsigned int i,j,k=0;
235     for (i=0; i<SCALAR_LIMBS; i++) {
236         decaf_word_t out = 0;
237         for (j=0; j<sizeof(decaf_word_t) && k<nbytes; j++,k++) {
238             out |= ((decaf_word_t)ser[k])<<(8*j);
239         }
240         s->limb[i] = out;
241     }
242 }
243
244 decaf_error_t API_NS(scalar_decode)(
245     scalar_t s,
246     const unsigned char ser[SCALAR_SER_BYTES]
247 ) {
248     unsigned int i;
249     scalar_decode_short(s, ser, SCALAR_SER_BYTES);
250     decaf_dsword_t accum = 0;
251     for (i=0; i<SCALAR_LIMBS; i++) {
252         accum = (accum + s->limb[i] - sc_p->limb[i]) >> WBITS;
253     }
254     /* Here accum == 0 or -1 */
255     
256     API_NS(scalar_mul)(s,s,API_NS(scalar_one)); /* ham-handed reduce */
257     
258     return decaf_succeed_if(~word_is_zero(accum));
259 }
260
261 void API_NS(scalar_destroy) (
262     scalar_t scalar
263 ) {
264     OPENSSL_cleanse(scalar, sizeof(scalar_t));
265 }
266
267 void API_NS(scalar_decode_long)(
268     scalar_t s,
269     const unsigned char *ser,
270     size_t ser_len
271 ) {
272     if (ser_len == 0) {
273         API_NS(scalar_copy)(s, API_NS(scalar_zero));
274         return;
275     }
276     
277     size_t i;
278     scalar_t t1, t2;
279
280     i = ser_len - (ser_len%SCALAR_SER_BYTES);
281     if (i==ser_len) i -= SCALAR_SER_BYTES;
282     
283     scalar_decode_short(t1, &ser[i], ser_len-i);
284
285     if (ser_len == sizeof(scalar_t)) {
286         assert(i==0);
287         /* ham-handed reduce */
288         API_NS(scalar_mul)(s,t1,API_NS(scalar_one));
289         API_NS(scalar_destroy)(t1);
290         return;
291     }
292
293     while (i) {
294         i -= SCALAR_SER_BYTES;
295         sc_montmul(t1,t1,sc_r2);
296         ignore_result( API_NS(scalar_decode)(t2, ser+i) );
297         API_NS(scalar_add)(t1, t1, t2);
298     }
299
300     API_NS(scalar_copy)(s, t1);
301     API_NS(scalar_destroy)(t1);
302     API_NS(scalar_destroy)(t2);
303 }
304
305 void API_NS(scalar_encode)(
306     unsigned char ser[SCALAR_SER_BYTES],
307     const scalar_t s
308 ) {
309     unsigned int i,j,k=0;
310     for (i=0; i<SCALAR_LIMBS; i++) {
311         for (j=0; j<sizeof(decaf_word_t); j++,k++) {
312             ser[k] = s->limb[i] >> (8*j);
313         }
314     }
315 }
316
317 void API_NS(scalar_cond_sel) (
318     scalar_t out,
319     const scalar_t a,
320     const scalar_t b,
321     decaf_bool_t pick_b
322 ) {
323     constant_time_select(out,a,b,sizeof(scalar_t),bool_to_mask(pick_b),sizeof(out->limb[0]));
324 }
325
326 void API_NS(scalar_halve) (
327     scalar_t out,
328     const scalar_t a
329 ) {
330     decaf_word_t mask = -(a->limb[0] & 1);
331     decaf_dword_t chain = 0;
332     unsigned int i;
333     for (i=0; i<SCALAR_LIMBS; i++) {
334         chain = (chain + a->limb[i]) + (sc_p->limb[i] & mask);
335         out->limb[i] = chain;
336         chain >>= DECAF_WORD_BITS;
337     }
338     for (i=0; i<SCALAR_LIMBS-1; i++) {
339         out->limb[i] = out->limb[i]>>1 | out->limb[i+1]<<(WBITS-1);
340     }
341     out->limb[i] = out->limb[i]>>1 | chain<<(WBITS-1);
342 }
343