1/*
2 * Copyright 2017-2021 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright 2015-2016 Cryptography Research, Inc.
4 *
5 * Licensed under the Apache License 2.0 (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
17static const c448_word_t MONTGOMERY_FACTOR = (c448_word_t) 0x3bd440fae918bc5ULL;
18static 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
41const curve448_scalar_t ossl_curve448_scalar_one = {{{1}}};
42const curve448_scalar_t ossl_curve448_scalar_zero = {{{0}}};
43
44/*
45 * {extra,accum} - sub +? p
46 * Must have extra <= 1
47 */
48static 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
72static 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
109void ossl_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
116void
117ossl_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
123void
124ossl_curve448_scalar_add(curve448_scalar_t out, const curve448_scalar_t a,
125                         const curve448_scalar_t b)
126{
127    c448_dword_t chain = 0;
128    unsigned int i;
129
130    for (i = 0; i < C448_SCALAR_LIMBS; i++) {
131        chain = (chain + a->limb[i]) + b->limb[i];
132        out->limb[i] = (c448_word_t)chain;
133        chain >>= WBITS;
134    }
135    sc_subx(out, out->limb, sc_p, sc_p, (c448_word_t)chain);
136}
137
138static ossl_inline void scalar_decode_short(curve448_scalar_t s,
139                                            const unsigned char *ser,
140                                            size_t nbytes)
141{
142    size_t i, j, k = 0;
143
144    for (i = 0; i < C448_SCALAR_LIMBS; i++) {
145        c448_word_t out = 0;
146
147        for (j = 0; j < sizeof(c448_word_t) && k < nbytes; j++, k++)
148            out |= ((c448_word_t) ser[k]) << (8 * j);
149        s->limb[i] = out;
150    }
151}
152
153c448_error_t
154ossl_curve448_scalar_decode(curve448_scalar_t s,
155                            const unsigned char ser[C448_SCALAR_BYTES])
156{
157    unsigned int i;
158    c448_dsword_t accum = 0;
159
160    scalar_decode_short(s, ser, C448_SCALAR_BYTES);
161    for (i = 0; i < C448_SCALAR_LIMBS; i++)
162        accum = (accum + s->limb[i] - sc_p->limb[i]) >> WBITS;
163    /* Here accum == 0 or -1 */
164
165    ossl_curve448_scalar_mul(s, s, ossl_curve448_scalar_one); /* ham-handed reduce */
166
167    return c448_succeed_if(~word_is_zero((uint32_t)accum));
168}
169
170void ossl_curve448_scalar_destroy(curve448_scalar_t scalar)
171{
172    OPENSSL_cleanse(scalar, sizeof(curve448_scalar_t));
173}
174
175void
176ossl_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, ossl_curve448_scalar_zero);
184        return;
185    }
186
187    i = ser_len - (ser_len % C448_SCALAR_BYTES);
188    if (i == ser_len)
189        i -= C448_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        ossl_curve448_scalar_mul(s, t1, ossl_curve448_scalar_one);
197        ossl_curve448_scalar_destroy(t1);
198        return;
199    }
200
201    while (i) {
202        i -= C448_SCALAR_BYTES;
203        sc_montmul(t1, t1, sc_r2);
204        (void)ossl_curve448_scalar_decode(t2, ser + i);
205        ossl_curve448_scalar_add(t1, t1, t2);
206    }
207
208    curve448_scalar_copy(s, t1);
209    ossl_curve448_scalar_destroy(t1);
210    ossl_curve448_scalar_destroy(t2);
211}
212
213void
214ossl_curve448_scalar_encode(unsigned char ser[C448_SCALAR_BYTES],
215                            const curve448_scalar_t s)
216{
217    unsigned int i, j, k = 0;
218
219    for (i = 0; i < C448_SCALAR_LIMBS; i++) {
220        for (j = 0; j < sizeof(c448_word_t); j++, k++)
221            ser[k] = s->limb[i] >> (8 * j);
222    }
223}
224
225void
226ossl_curve448_scalar_halve(curve448_scalar_t out, const curve448_scalar_t a)
227{
228    c448_word_t mask = 0 - (a->limb[0] & 1);
229    c448_dword_t chain = 0;
230    unsigned int i;
231
232    for (i = 0; i < C448_SCALAR_LIMBS; i++) {
233        chain = (chain + a->limb[i]) + (sc_p->limb[i] & mask);
234        out->limb[i] = (c448_word_t)chain;
235        chain >>= C448_WORD_BITS;
236    }
237    for (i = 0; i < C448_SCALAR_LIMBS - 1; i++)
238        out->limb[i] = out->limb[i] >> 1 | out->limb[i + 1] << (WBITS - 1);
239    out->limb[i] = out->limb[i] >> 1 | (c448_word_t)(chain << (WBITS - 1));
240}
241