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