5090fcf3d8e1188092f77db1bc8b1997359ff663
[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                                           SC_LIMB(0x2378c292ab5844f3),
21                                           SC_LIMB(0x216cc2728dc58f55),
22                                           SC_LIMB(0xc44edb49aed63690),
23                                           SC_LIMB(0xffffffff7cca23e9),
24                                           SC_LIMB(0xffffffffffffffff),
25                                           SC_LIMB(0xffffffffffffffff),
26                                           SC_LIMB(0x3fffffffffffffff)
27                                           }}
28 }, sc_r2 = { { {
29
30             SC_LIMB(0xe3539257049b9b60), SC_LIMB(0x7af32c4bc1b195d9),
31                 SC_LIMB(0x0d66de2388ea1859), SC_LIMB(0xae17cf725ee4d838),
32                 SC_LIMB(0x1a9cc14ba3c47c44), SC_LIMB(0x2052bcb7e4d070af),
33                 SC_LIMB(0x3402a939f823b729)
34 }}};
35
36 /* End of template stuff */
37
38 #define WBITS DECAF_WORD_BITS   /* NB this may be different from ARCH_WORD_BITS */
39
40 const curve448_scalar_t curve448_scalar_one = { {{1}} }, curve448_scalar_zero = { { {
41 0}}};
42
43 /** {extra,accum} - sub +? p
44  * Must have extra <= 1
45  */
46 static void sc_subx(curve448_scalar_t out,
47                     const decaf_word_t accum[DECAF_448_SCALAR_LIMBS],
48                     const curve448_scalar_t sub,
49                     const curve448_scalar_t p, decaf_word_t extra)
50 {
51     decaf_dsword_t chain = 0;
52     unsigned int i;
53     decaf_word_t borrow;
54
55     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
56         chain = (chain + accum[i]) - sub->limb[i];
57         out->limb[i] = chain;
58         chain >>= WBITS;
59     }
60     borrow = chain + extra;     /* = 0 or -1 */
61
62     chain = 0;
63     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
64         chain = (chain + out->limb[i]) + (p->limb[i] & borrow);
65         out->limb[i] = chain;
66         chain >>= WBITS;
67     }
68 }
69
70 static void sc_montmul(curve448_scalar_t out,
71                        const curve448_scalar_t a, const curve448_scalar_t b)
72 {
73     unsigned int i, j;
74     decaf_word_t accum[DECAF_448_SCALAR_LIMBS + 1] = { 0 };
75     decaf_word_t hi_carry = 0;
76
77     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
78         decaf_word_t mand = a->limb[i];
79         const decaf_word_t *mier = b->limb;
80
81         decaf_dword_t chain = 0;
82         for (j = 0; j < DECAF_448_SCALAR_LIMBS; j++) {
83             chain += ((decaf_dword_t) mand) * mier[j] + accum[j];
84             accum[j] = chain;
85             chain >>= WBITS;
86         }
87         accum[j] = chain;
88
89         mand = accum[0] * MONTGOMERY_FACTOR;
90         chain = 0;
91         mier = sc_p->limb;
92         for (j = 0; j < DECAF_448_SCALAR_LIMBS; j++) {
93             chain += (decaf_dword_t) mand *mier[j] + accum[j];
94             if (j)
95                 accum[j - 1] = chain;
96             chain >>= WBITS;
97         }
98         chain += accum[j];
99         chain += hi_carry;
100         accum[j - 1] = chain;
101         hi_carry = chain >> WBITS;
102     }
103
104     sc_subx(out, accum, sc_p, sc_p, hi_carry);
105 }
106
107 void curve448_scalar_mul(curve448_scalar_t out,
108                          const curve448_scalar_t a, const curve448_scalar_t b)
109 {
110     sc_montmul(out, a, b);
111     sc_montmul(out, out, sc_r2);
112 }
113
114 void curve448_scalar_sub(curve448_scalar_t out,
115                          const curve448_scalar_t a, const curve448_scalar_t b)
116 {
117     sc_subx(out, a->limb, b, sc_p, 0);
118 }
119
120 void curve448_scalar_add(curve448_scalar_t out,
121                          const curve448_scalar_t a, const curve448_scalar_t b)
122 {
123     decaf_dword_t chain = 0;
124     unsigned int i;
125     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
126         chain = (chain + a->limb[i]) + b->limb[i];
127         out->limb[i] = chain;
128         chain >>= WBITS;
129     }
130     sc_subx(out, out->limb, sc_p, sc_p, chain);
131 }
132
133 static ossl_inline void scalar_decode_short(curve448_scalar_t s,
134                                             const unsigned char *ser,
135                                             unsigned int nbytes)
136 {
137     unsigned int i, j, k = 0;
138     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
139         decaf_word_t out = 0;
140         for (j = 0; j < sizeof(decaf_word_t) && k < nbytes; j++, k++) {
141             out |= ((decaf_word_t) ser[k]) << (8 * j);
142         }
143         s->limb[i] = out;
144     }
145 }
146
147 decaf_error_t curve448_scalar_decode(curve448_scalar_t s,
148                                      const unsigned char
149                                      ser[DECAF_448_SCALAR_BYTES]
150     )
151 {
152     unsigned int i;
153     decaf_dsword_t accum = 0;
154
155     scalar_decode_short(s, ser, DECAF_448_SCALAR_BYTES);
156     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
157         accum = (accum + s->limb[i] - sc_p->limb[i]) >> WBITS;
158     }
159     /* Here accum == 0 or -1 */
160
161     curve448_scalar_mul(s, s, curve448_scalar_one); /* ham-handed reduce */
162
163     return decaf_succeed_if(~word_is_zero(accum));
164 }
165
166 void curve448_scalar_destroy(curve448_scalar_t scalar)
167 {
168     OPENSSL_cleanse(scalar, sizeof(curve448_scalar_t));
169 }
170
171 void curve448_scalar_decode_long(curve448_scalar_t s,
172                                  const unsigned char *ser, size_t ser_len)
173 {
174     size_t i;
175     curve448_scalar_t t1, t2;
176
177     if (ser_len == 0) {
178         curve448_scalar_copy(s, curve448_scalar_zero);
179         return;
180     }
181
182     i = ser_len - (ser_len % DECAF_448_SCALAR_BYTES);
183     if (i == ser_len)
184         i -= DECAF_448_SCALAR_BYTES;
185
186     scalar_decode_short(t1, &ser[i], ser_len - i);
187
188     if (ser_len == sizeof(curve448_scalar_t)) {
189         assert(i == 0);
190         /* ham-handed reduce */
191         curve448_scalar_mul(s, t1, curve448_scalar_one);
192         curve448_scalar_destroy(t1);
193         return;
194     }
195
196     while (i) {
197         i -= DECAF_448_SCALAR_BYTES;
198         sc_montmul(t1, t1, sc_r2);
199         ignore_result(curve448_scalar_decode(t2, ser + i));
200         curve448_scalar_add(t1, t1, t2);
201     }
202
203     curve448_scalar_copy(s, t1);
204     curve448_scalar_destroy(t1);
205     curve448_scalar_destroy(t2);
206 }
207
208 void curve448_scalar_encode(unsigned char ser[DECAF_448_SCALAR_BYTES],
209                             const curve448_scalar_t s)
210 {
211     unsigned int i, j, k = 0;
212     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
213         for (j = 0; j < sizeof(decaf_word_t); j++, k++) {
214             ser[k] = s->limb[i] >> (8 * j);
215         }
216     }
217 }
218
219 void curve448_scalar_halve(curve448_scalar_t out, const curve448_scalar_t a)
220 {
221     decaf_word_t mask = -(a->limb[0] & 1);
222     decaf_dword_t chain = 0;
223     unsigned int i;
224     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
225         chain = (chain + a->limb[i]) + (sc_p->limb[i] & mask);
226         out->limb[i] = chain;
227         chain >>= DECAF_WORD_BITS;
228     }
229     for (i = 0; i < DECAF_448_SCALAR_LIMBS - 1; i++) {
230         out->limb[i] = out->limb[i] >> 1 | out->limb[i + 1] << (WBITS - 1);
231     }
232     out->limb[i] = out->limb[i] >> 1 | chain << (WBITS - 1);
233 }