2 * Copyright 2017-2018 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright 2015-2016 Cryptography Research, Inc.
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
10 * Originally written by Mike Hamburg
12 #include <openssl/crypto.h>
15 #include "point_448.h"
17 static const c448_word_t MONTGOMERY_FACTOR = (c448_word_t) 0x3bd440fae918bc5;
18 static const curve448_scalar_t sc_p = {
21 SC_LIMB(0x2378c292ab5844f3), SC_LIMB(0x216cc2728dc58f55),
22 SC_LIMB(0xc44edb49aed63690), SC_LIMB(0xffffffff7cca23e9),
23 SC_LIMB(0xffffffffffffffff), SC_LIMB(0xffffffffffffffff),
24 SC_LIMB(0x3fffffffffffffff)
31 SC_LIMB(0xe3539257049b9b60), SC_LIMB(0x7af32c4bc1b195d9),
32 SC_LIMB(0x0d66de2388ea1859), SC_LIMB(0xae17cf725ee4d838),
33 SC_LIMB(0x1a9cc14ba3c47c44), SC_LIMB(0x2052bcb7e4d070af),
34 SC_LIMB(0x3402a939f823b729)
39 #define WBITS C448_WORD_BITS /* NB this may be different from ARCH_WORD_BITS */
41 const curve448_scalar_t curve448_scalar_one = {{{1}}};
42 const curve448_scalar_t curve448_scalar_zero = {{{0}}};
45 * {extra,accum} - sub +? p
46 * Must have extra <= 1
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)
53 c448_dsword_t chain = 0;
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;
62 borrow = (c448_word_t)chain + extra; /* = 0 or -1 */
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;
72 static void sc_montmul(curve448_scalar_t out, const curve448_scalar_t a,
73 const curve448_scalar_t b)
76 c448_word_t accum[C448_SCALAR_LIMBS + 1] = { 0 };
77 c448_word_t hi_carry = 0;
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;
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;
89 accum[j] = (c448_word_t)chain;
91 mand = accum[0] * MONTGOMERY_FACTOR;
94 for (j = 0; j < C448_SCALAR_LIMBS; j++) {
95 chain += (c448_dword_t) mand *mier[j] + accum[j];
97 accum[j - 1] = (c448_word_t)chain;
102 accum[j - 1] = (c448_word_t)chain;
103 hi_carry = chain >> WBITS;
106 sc_subx(out, accum, sc_p, sc_p, hi_carry);
109 void curve448_scalar_mul(curve448_scalar_t out, const curve448_scalar_t a,
110 const curve448_scalar_t b)
112 sc_montmul(out, a, b);
113 sc_montmul(out, out, sc_r2);
116 void curve448_scalar_sub(curve448_scalar_t out, const curve448_scalar_t a,
117 const curve448_scalar_t b)
119 sc_subx(out, a->limb, b, sc_p, 0);
122 void curve448_scalar_add(curve448_scalar_t out, const curve448_scalar_t a,
123 const curve448_scalar_t b)
125 c448_dword_t chain = 0;
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;
133 sc_subx(out, out->limb, sc_p, sc_p, (c448_word_t)chain);
136 static ossl_inline void scalar_decode_short(curve448_scalar_t s,
137 const unsigned char *ser,
142 for (i = 0; i < C448_SCALAR_LIMBS; i++) {
145 for (j = 0; j < sizeof(c448_word_t) && k < nbytes; j++, k++)
146 out |= ((c448_word_t) ser[k]) << (8 * j);
151 c448_error_t curve448_scalar_decode(
153 const unsigned char ser[C448_SCALAR_BYTES])
156 c448_dsword_t accum = 0;
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 */
163 curve448_scalar_mul(s, s, curve448_scalar_one); /* ham-handed reduce */
165 return c448_succeed_if(~word_is_zero((uint32_t)accum));
168 void curve448_scalar_destroy(curve448_scalar_t scalar)
170 OPENSSL_cleanse(scalar, sizeof(curve448_scalar_t));
173 void curve448_scalar_decode_long(curve448_scalar_t s,
174 const unsigned char *ser, size_t ser_len)
177 curve448_scalar_t t1, t2;
180 curve448_scalar_copy(s, curve448_scalar_zero);
184 i = ser_len - (ser_len % C448_SCALAR_BYTES);
186 i -= C448_SCALAR_BYTES;
188 scalar_decode_short(t1, &ser[i], ser_len - i);
190 if (ser_len == sizeof(curve448_scalar_t)) {
192 /* ham-handed reduce */
193 curve448_scalar_mul(s, t1, curve448_scalar_one);
194 curve448_scalar_destroy(t1);
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);
205 curve448_scalar_copy(s, t1);
206 curve448_scalar_destroy(t1);
207 curve448_scalar_destroy(t2);
210 void curve448_scalar_encode(unsigned char ser[C448_SCALAR_BYTES],
211 const curve448_scalar_t s)
213 unsigned int i, j, k = 0;
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);
221 void curve448_scalar_halve(curve448_scalar_t out, const curve448_scalar_t a)
223 c448_word_t mask = 0 - (a->limb[0] & 1);
224 c448_dword_t chain = 0;
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;
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));