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