Manual formatting tweaks to Curve448 code
[openssl.git] / crypto / ec / curve448 / scalar.c
1 /*
2  * Copyright 2017 The OpenSSL Project Authors. All Rights Reserved.
3  * Copyright 2015-2016 Cryptography Research, Inc.
4  *
5  * Licensed under the OpenSSL license (the "License").  You may not use
6  * this file except in compliance with the License.  You can obtain a copy
7  * in the file LICENSE in the source distribution or at
8  * https://www.openssl.org/source/license.html
9  *
10  * Originally written by Mike Hamburg
11  */
12 #include <openssl/crypto.h>
13
14 #include "word.h"
15 #include "constant_time.h"
16 #include "point_448.h"
17
18 static const decaf_word_t MONTGOMERY_FACTOR = (decaf_word_t) 0x3bd440fae918bc5;
19 static const curve448_scalar_t sc_p = {
20     {
21         {
22             SC_LIMB(0x2378c292ab5844f3), SC_LIMB(0x216cc2728dc58f55),
23             SC_LIMB(0xc44edb49aed63690), SC_LIMB(0xffffffff7cca23e9),
24             SC_LIMB(0xffffffffffffffff), SC_LIMB(0xffffffffffffffff),
25             SC_LIMB(0x3fffffffffffffff)
26         }
27     }
28 }, sc_r2 = {
29     {
30         {
31
32             SC_LIMB(0xe3539257049b9b60), SC_LIMB(0x7af32c4bc1b195d9),
33             SC_LIMB(0x0d66de2388ea1859), SC_LIMB(0xae17cf725ee4d838),
34             SC_LIMB(0x1a9cc14ba3c47c44), SC_LIMB(0x2052bcb7e4d070af),
35             SC_LIMB(0x3402a939f823b729)
36         }
37     }
38 };
39
40 /* End of template stuff */
41
42 #define WBITS DECAF_WORD_BITS   /* NB this may be different from ARCH_WORD_BITS */
43
44 const curve448_scalar_t curve448_scalar_one = {{{1}}};
45 const curve448_scalar_t  curve448_scalar_zero = {{{0}}};
46
47 /*
48  * {extra,accum} - sub +? p
49  * Must have extra <= 1
50  */
51 static void sc_subx(curve448_scalar_t out,
52                     const decaf_word_t accum[DECAF_448_SCALAR_LIMBS],
53                     const curve448_scalar_t sub,
54                     const curve448_scalar_t p, decaf_word_t extra)
55 {
56     decaf_dsword_t chain = 0;
57     unsigned int i;
58     decaf_word_t borrow;
59
60     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
61         chain = (chain + accum[i]) - sub->limb[i];
62         out->limb[i] = chain;
63         chain >>= WBITS;
64     }
65     borrow = chain + extra;     /* = 0 or -1 */
66
67     chain = 0;
68     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
69         chain = (chain + out->limb[i]) + (p->limb[i] & borrow);
70         out->limb[i] = chain;
71         chain >>= WBITS;
72     }
73 }
74
75 static void sc_montmul(curve448_scalar_t out, const curve448_scalar_t a,
76                        const curve448_scalar_t b)
77 {
78     unsigned int i, j;
79     decaf_word_t accum[DECAF_448_SCALAR_LIMBS + 1] = { 0 };
80     decaf_word_t hi_carry = 0;
81
82     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
83         decaf_word_t mand = a->limb[i];
84         const decaf_word_t *mier = b->limb;
85
86         decaf_dword_t chain = 0;
87         for (j = 0; j < DECAF_448_SCALAR_LIMBS; j++) {
88             chain += ((decaf_dword_t) mand) * mier[j] + accum[j];
89             accum[j] = chain;
90             chain >>= WBITS;
91         }
92         accum[j] = chain;
93
94         mand = accum[0] * MONTGOMERY_FACTOR;
95         chain = 0;
96         mier = sc_p->limb;
97         for (j = 0; j < DECAF_448_SCALAR_LIMBS; j++) {
98             chain += (decaf_dword_t) mand *mier[j] + accum[j];
99             if (j)
100                 accum[j - 1] = chain;
101             chain >>= WBITS;
102         }
103         chain += accum[j];
104         chain += hi_carry;
105         accum[j - 1] = chain;
106         hi_carry = chain >> WBITS;
107     }
108
109     sc_subx(out, accum, sc_p, sc_p, hi_carry);
110 }
111
112 void curve448_scalar_mul(curve448_scalar_t out, const curve448_scalar_t a,
113                          const curve448_scalar_t b)
114 {
115     sc_montmul(out, a, b);
116     sc_montmul(out, out, sc_r2);
117 }
118
119 void curve448_scalar_sub(curve448_scalar_t out, const curve448_scalar_t a,
120                          const curve448_scalar_t b)
121 {
122     sc_subx(out, a->limb, b, sc_p, 0);
123 }
124
125 void curve448_scalar_add(curve448_scalar_t out, const curve448_scalar_t a,
126                          const curve448_scalar_t b)
127 {
128     decaf_dword_t chain = 0;
129     unsigned int i;
130
131     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
132         chain = (chain + a->limb[i]) + b->limb[i];
133         out->limb[i] = chain;
134         chain >>= WBITS;
135     }
136     sc_subx(out, out->limb, sc_p, sc_p, chain);
137 }
138
139 static ossl_inline void scalar_decode_short(curve448_scalar_t s,
140                                             const unsigned char *ser,
141                                             unsigned int nbytes)
142 {
143     unsigned int i, j, k = 0;
144
145     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
146         decaf_word_t out = 0;
147
148         for (j = 0; j < sizeof(decaf_word_t) && k < nbytes; j++, k++)
149             out |= ((decaf_word_t) ser[k]) << (8 * j);
150         s->limb[i] = out;
151     }
152 }
153
154 decaf_error_t curve448_scalar_decode(
155                                 curve448_scalar_t s,
156                                 const unsigned char ser[DECAF_448_SCALAR_BYTES])
157 {
158     unsigned int i;
159     decaf_dsword_t accum = 0;
160
161     scalar_decode_short(s, ser, DECAF_448_SCALAR_BYTES);
162     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++)
163         accum = (accum + s->limb[i] - sc_p->limb[i]) >> WBITS;
164     /* Here accum == 0 or -1 */
165
166     curve448_scalar_mul(s, s, curve448_scalar_one); /* ham-handed reduce */
167
168     return decaf_succeed_if(~word_is_zero(accum));
169 }
170
171 void curve448_scalar_destroy(curve448_scalar_t scalar)
172 {
173     OPENSSL_cleanse(scalar, sizeof(curve448_scalar_t));
174 }
175
176 void curve448_scalar_decode_long(curve448_scalar_t s,
177                                  const unsigned char *ser, size_t ser_len)
178 {
179     size_t i;
180     curve448_scalar_t t1, t2;
181
182     if (ser_len == 0) {
183         curve448_scalar_copy(s, curve448_scalar_zero);
184         return;
185     }
186
187     i = ser_len - (ser_len % DECAF_448_SCALAR_BYTES);
188     if (i == ser_len)
189         i -= DECAF_448_SCALAR_BYTES;
190
191     scalar_decode_short(t1, &ser[i], ser_len - i);
192
193     if (ser_len == sizeof(curve448_scalar_t)) {
194         assert(i == 0);
195         /* ham-handed reduce */
196         curve448_scalar_mul(s, t1, curve448_scalar_one);
197         curve448_scalar_destroy(t1);
198         return;
199     }
200
201     while (i) {
202         i -= DECAF_448_SCALAR_BYTES;
203         sc_montmul(t1, t1, sc_r2);
204         ignore_result(curve448_scalar_decode(t2, ser + i));
205         curve448_scalar_add(t1, t1, t2);
206     }
207
208     curve448_scalar_copy(s, t1);
209     curve448_scalar_destroy(t1);
210     curve448_scalar_destroy(t2);
211 }
212
213 void curve448_scalar_encode(unsigned char ser[DECAF_448_SCALAR_BYTES],
214                             const curve448_scalar_t s)
215 {
216     unsigned int i, j, k = 0;
217
218     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
219         for (j = 0; j < sizeof(decaf_word_t); j++, k++)
220             ser[k] = s->limb[i] >> (8 * j);
221     }
222 }
223
224 void curve448_scalar_halve(curve448_scalar_t out, const curve448_scalar_t a)
225 {
226     decaf_word_t mask = -(a->limb[0] & 1);
227     decaf_dword_t chain = 0;
228     unsigned int i;
229     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
230         chain = (chain + a->limb[i]) + (sc_p->limb[i] & mask);
231         out->limb[i] = chain;
232         chain >>= DECAF_WORD_BITS;
233     }
234     for (i = 0; i < DECAF_448_SCALAR_LIMBS - 1; i++)
235         out->limb[i] = out->limb[i] >> 1 | out->limb[i + 1] << (WBITS - 1);
236     out->limb[i] = out->limb[i] >> 1 | chain << (WBITS - 1);
237 }