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