2 * Copyright 2017 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright 2015-2016 Cryptography Research, Inc.
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
10 * Originally written by Mike Hamburg
12 #include <openssl/crypto.h>
15 #include "constant_time.h"
16 #include "point_448.h"
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)
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)
36 /* End of template stuff */
38 #define WBITS DECAF_WORD_BITS /* NB this may be different from ARCH_WORD_BITS */
40 const curve448_scalar_t curve448_scalar_one = { {{1}} }, curve448_scalar_zero = { { {
43 /** {extra,accum} - sub +? p
44 * Must have extra <= 1
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)
51 decaf_dsword_t chain = 0;
55 for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
56 chain = (chain + accum[i]) - sub->limb[i];
60 borrow = chain + extra; /* = 0 or -1 */
63 for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
64 chain = (chain + out->limb[i]) + (p->limb[i] & borrow);
70 static void sc_montmul(curve448_scalar_t out,
71 const curve448_scalar_t a, const curve448_scalar_t b)
74 decaf_word_t accum[DECAF_448_SCALAR_LIMBS + 1] = { 0 };
75 decaf_word_t hi_carry = 0;
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;
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];
89 mand = accum[0] * MONTGOMERY_FACTOR;
92 for (j = 0; j < DECAF_448_SCALAR_LIMBS; j++) {
93 chain += (decaf_dword_t) mand *mier[j] + accum[j];
100 accum[j - 1] = chain;
101 hi_carry = chain >> WBITS;
104 sc_subx(out, accum, sc_p, sc_p, hi_carry);
107 void curve448_scalar_mul(curve448_scalar_t out,
108 const curve448_scalar_t a, const curve448_scalar_t b)
110 sc_montmul(out, a, b);
111 sc_montmul(out, out, sc_r2);
114 void curve448_scalar_sub(curve448_scalar_t out,
115 const curve448_scalar_t a, const curve448_scalar_t b)
117 sc_subx(out, a->limb, b, sc_p, 0);
120 void curve448_scalar_add(curve448_scalar_t out,
121 const curve448_scalar_t a, const curve448_scalar_t b)
123 decaf_dword_t chain = 0;
125 for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
126 chain = (chain + a->limb[i]) + b->limb[i];
127 out->limb[i] = chain;
130 sc_subx(out, out->limb, sc_p, sc_p, chain);
133 static ossl_inline void scalar_decode_short(curve448_scalar_t s,
134 const unsigned char *ser,
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);
147 decaf_error_t curve448_scalar_decode(curve448_scalar_t s,
149 ser[DECAF_448_SCALAR_BYTES]
153 decaf_dsword_t accum = 0;
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;
159 /* Here accum == 0 or -1 */
161 curve448_scalar_mul(s, s, curve448_scalar_one); /* ham-handed reduce */
163 return decaf_succeed_if(~word_is_zero(accum));
166 void curve448_scalar_destroy(curve448_scalar_t scalar)
168 OPENSSL_cleanse(scalar, sizeof(curve448_scalar_t));
171 void curve448_scalar_decode_long(curve448_scalar_t s,
172 const unsigned char *ser, size_t ser_len)
175 curve448_scalar_t t1, t2;
178 curve448_scalar_copy(s, curve448_scalar_zero);
182 i = ser_len - (ser_len % DECAF_448_SCALAR_BYTES);
184 i -= DECAF_448_SCALAR_BYTES;
186 scalar_decode_short(t1, &ser[i], ser_len - i);
188 if (ser_len == sizeof(curve448_scalar_t)) {
190 /* ham-handed reduce */
191 curve448_scalar_mul(s, t1, curve448_scalar_one);
192 curve448_scalar_destroy(t1);
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);
203 curve448_scalar_copy(s, t1);
204 curve448_scalar_destroy(t1);
205 curve448_scalar_destroy(t2);
208 void curve448_scalar_encode(unsigned char ser[DECAF_448_SCALAR_BYTES],
209 const curve448_scalar_t s)
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);
219 void curve448_scalar_halve(curve448_scalar_t out, const curve448_scalar_t a)
221 decaf_word_t mask = -(a->limb[0] & 1);
222 decaf_dword_t chain = 0;
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;
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);
232 out->limb[i] = out->limb[i] >> 1 | chain << (WBITS - 1);