]>
Commit | Line | Data |
---|---|---|
1308e022 MC |
1 | /* |
2 | * Copyright 2017 The OpenSSL Project Authors. All Rights Reserved. | |
3 | * Copyright 2015-2016 Cryptography Research, Inc. | |
7324473f | 4 | * |
1308e022 MC |
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 | |
7324473f | 9 | * |
1308e022 | 10 | * Originally written by Mike Hamburg |
7324473f | 11 | */ |
b6e388ba MC |
12 | #include <openssl/crypto.h> |
13 | ||
7324473f MC |
14 | #include "word.h" |
15 | #include "constant_time.h" | |
a2039c87 | 16 | #include "point_448.h" |
7324473f | 17 | |
aeeef83c | 18 | static const c448_word_t MONTGOMERY_FACTOR = (c448_word_t) 0x3bd440fae918bc5; |
8d55f844 MC |
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 | { | |
205fd638 MC |
31 | |
32 | SC_LIMB(0xe3539257049b9b60), SC_LIMB(0x7af32c4bc1b195d9), | |
8d55f844 MC |
33 | SC_LIMB(0x0d66de2388ea1859), SC_LIMB(0xae17cf725ee4d838), |
34 | SC_LIMB(0x1a9cc14ba3c47c44), SC_LIMB(0x2052bcb7e4d070af), | |
35 | SC_LIMB(0x3402a939f823b729) | |
36 | } | |
37 | } | |
38 | }; | |
205fd638 | 39 | |
aeeef83c | 40 | #define WBITS C448_WORD_BITS /* NB this may be different from ARCH_WORD_BITS */ |
7324473f | 41 | |
8d55f844 MC |
42 | const curve448_scalar_t curve448_scalar_one = {{{1}}}; |
43 | const curve448_scalar_t curve448_scalar_zero = {{{0}}}; | |
7324473f | 44 | |
8d55f844 MC |
45 | /* |
46 | * {extra,accum} - sub +? p | |
7324473f MC |
47 | * Must have extra <= 1 |
48 | */ | |
205fd638 | 49 | static void sc_subx(curve448_scalar_t out, |
db90b274 | 50 | const c448_word_t accum[C448_SCALAR_LIMBS], |
205fd638 | 51 | const curve448_scalar_t sub, |
aeeef83c | 52 | const curve448_scalar_t p, c448_word_t extra) |
205fd638 | 53 | { |
aeeef83c | 54 | c448_dsword_t chain = 0; |
7324473f | 55 | unsigned int i; |
aeeef83c | 56 | c448_word_t borrow; |
094c071c | 57 | |
db90b274 | 58 | for (i = 0; i < C448_SCALAR_LIMBS; i++) { |
7324473f MC |
59 | chain = (chain + accum[i]) - sub->limb[i]; |
60 | out->limb[i] = chain; | |
61 | chain >>= WBITS; | |
62 | } | |
205fd638 MC |
63 | borrow = chain + extra; /* = 0 or -1 */ |
64 | ||
7324473f | 65 | chain = 0; |
db90b274 | 66 | for (i = 0; i < C448_SCALAR_LIMBS; i++) { |
7324473f MC |
67 | chain = (chain + out->limb[i]) + (p->limb[i] & borrow); |
68 | out->limb[i] = chain; | |
69 | chain >>= WBITS; | |
70 | } | |
71 | } | |
72 | ||
8d55f844 MC |
73 | static void sc_montmul(curve448_scalar_t out, const curve448_scalar_t a, |
74 | const curve448_scalar_t b) | |
205fd638 MC |
75 | { |
76 | unsigned int i, j; | |
db90b274 | 77 | c448_word_t accum[C448_SCALAR_LIMBS + 1] = { 0 }; |
aeeef83c | 78 | c448_word_t hi_carry = 0; |
205fd638 | 79 | |
db90b274 | 80 | for (i = 0; i < C448_SCALAR_LIMBS; i++) { |
aeeef83c MC |
81 | c448_word_t mand = a->limb[i]; |
82 | const c448_word_t *mier = b->limb; | |
205fd638 | 83 | |
aeeef83c | 84 | c448_dword_t chain = 0; |
db90b274 | 85 | for (j = 0; j < C448_SCALAR_LIMBS; j++) { |
aeeef83c | 86 | chain += ((c448_dword_t) mand) * mier[j] + accum[j]; |
7324473f MC |
87 | accum[j] = chain; |
88 | chain >>= WBITS; | |
89 | } | |
90 | accum[j] = chain; | |
205fd638 | 91 | |
7324473f MC |
92 | mand = accum[0] * MONTGOMERY_FACTOR; |
93 | chain = 0; | |
94 | mier = sc_p->limb; | |
db90b274 | 95 | for (j = 0; j < C448_SCALAR_LIMBS; j++) { |
aeeef83c | 96 | chain += (c448_dword_t) mand *mier[j] + accum[j]; |
205fd638 MC |
97 | if (j) |
98 | accum[j - 1] = chain; | |
7324473f MC |
99 | chain >>= WBITS; |
100 | } | |
101 | chain += accum[j]; | |
102 | chain += hi_carry; | |
205fd638 | 103 | accum[j - 1] = chain; |
7324473f MC |
104 | hi_carry = chain >> WBITS; |
105 | } | |
205fd638 | 106 | |
7324473f MC |
107 | sc_subx(out, accum, sc_p, sc_p, hi_carry); |
108 | } | |
109 | ||
8d55f844 MC |
110 | void curve448_scalar_mul(curve448_scalar_t out, const curve448_scalar_t a, |
111 | const curve448_scalar_t b) | |
205fd638 MC |
112 | { |
113 | sc_montmul(out, a, b); | |
114 | sc_montmul(out, out, sc_r2); | |
7324473f MC |
115 | } |
116 | ||
8d55f844 MC |
117 | void curve448_scalar_sub(curve448_scalar_t out, const curve448_scalar_t a, |
118 | const curve448_scalar_t b) | |
205fd638 | 119 | { |
7324473f MC |
120 | sc_subx(out, a->limb, b, sc_p, 0); |
121 | } | |
122 | ||
8d55f844 MC |
123 | void curve448_scalar_add(curve448_scalar_t out, const curve448_scalar_t a, |
124 | const curve448_scalar_t b) | |
205fd638 | 125 | { |
aeeef83c | 126 | c448_dword_t chain = 0; |
7324473f | 127 | unsigned int i; |
8d55f844 | 128 | |
db90b274 | 129 | for (i = 0; i < C448_SCALAR_LIMBS; i++) { |
7324473f MC |
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 | ||
205fd638 MC |
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; | |
8d55f844 | 142 | |
db90b274 | 143 | for (i = 0; i < C448_SCALAR_LIMBS; i++) { |
aeeef83c | 144 | c448_word_t out = 0; |
8d55f844 | 145 | |
aeeef83c MC |
146 | for (j = 0; j < sizeof(c448_word_t) && k < nbytes; j++, k++) |
147 | out |= ((c448_word_t) ser[k]) << (8 * j); | |
7324473f MC |
148 | s->limb[i] = out; |
149 | } | |
150 | } | |
151 | ||
aeeef83c | 152 | c448_error_t curve448_scalar_decode( |
8d55f844 | 153 | curve448_scalar_t s, |
db90b274 | 154 | const unsigned char ser[C448_SCALAR_BYTES]) |
205fd638 | 155 | { |
7324473f | 156 | unsigned int i; |
aeeef83c | 157 | c448_dsword_t accum = 0; |
094c071c | 158 | |
db90b274 MC |
159 | scalar_decode_short(s, ser, C448_SCALAR_BYTES); |
160 | for (i = 0; i < C448_SCALAR_LIMBS; i++) | |
7324473f | 161 | accum = (accum + s->limb[i] - sc_p->limb[i]) >> WBITS; |
7324473f | 162 | /* Here accum == 0 or -1 */ |
205fd638 MC |
163 | |
164 | curve448_scalar_mul(s, s, curve448_scalar_one); /* ham-handed reduce */ | |
165 | ||
aeeef83c | 166 | return c448_succeed_if(~word_is_zero(accum)); |
7324473f MC |
167 | } |
168 | ||
205fd638 MC |
169 | void curve448_scalar_destroy(curve448_scalar_t scalar) |
170 | { | |
88ba7e71 | 171 | OPENSSL_cleanse(scalar, sizeof(curve448_scalar_t)); |
7324473f MC |
172 | } |
173 | ||
205fd638 MC |
174 | void curve448_scalar_decode_long(curve448_scalar_t s, |
175 | const unsigned char *ser, size_t ser_len) | |
176 | { | |
094c071c MC |
177 | size_t i; |
178 | curve448_scalar_t t1, t2; | |
179 | ||
7324473f | 180 | if (ser_len == 0) { |
e7772577 | 181 | curve448_scalar_copy(s, curve448_scalar_zero); |
7324473f MC |
182 | return; |
183 | } | |
7324473f | 184 | |
db90b274 | 185 | i = ser_len - (ser_len % C448_SCALAR_BYTES); |
205fd638 | 186 | if (i == ser_len) |
db90b274 | 187 | i -= C448_SCALAR_BYTES; |
205fd638 MC |
188 | |
189 | scalar_decode_short(t1, &ser[i], ser_len - i); | |
7324473f | 190 | |
88ba7e71 | 191 | if (ser_len == sizeof(curve448_scalar_t)) { |
205fd638 | 192 | assert(i == 0); |
7324473f | 193 | /* ham-handed reduce */ |
205fd638 | 194 | curve448_scalar_mul(s, t1, curve448_scalar_one); |
e7772577 | 195 | curve448_scalar_destroy(t1); |
7324473f MC |
196 | return; |
197 | } | |
198 | ||
199 | while (i) { | |
db90b274 | 200 | i -= C448_SCALAR_BYTES; |
205fd638 MC |
201 | sc_montmul(t1, t1, sc_r2); |
202 | ignore_result(curve448_scalar_decode(t2, ser + i)); | |
e7772577 | 203 | curve448_scalar_add(t1, t1, t2); |
7324473f MC |
204 | } |
205 | ||
e7772577 MC |
206 | curve448_scalar_copy(s, t1); |
207 | curve448_scalar_destroy(t1); | |
208 | curve448_scalar_destroy(t2); | |
7324473f MC |
209 | } |
210 | ||
db90b274 | 211 | void curve448_scalar_encode(unsigned char ser[C448_SCALAR_BYTES], |
205fd638 MC |
212 | const curve448_scalar_t s) |
213 | { | |
214 | unsigned int i, j, k = 0; | |
8d55f844 | 215 | |
db90b274 | 216 | for (i = 0; i < C448_SCALAR_LIMBS; i++) { |
aeeef83c | 217 | for (j = 0; j < sizeof(c448_word_t); j++, k++) |
205fd638 | 218 | ser[k] = s->limb[i] >> (8 * j); |
7324473f MC |
219 | } |
220 | } | |
221 | ||
205fd638 MC |
222 | void curve448_scalar_halve(curve448_scalar_t out, const curve448_scalar_t a) |
223 | { | |
aeeef83c MC |
224 | c448_word_t mask = -(a->limb[0] & 1); |
225 | c448_dword_t chain = 0; | |
7324473f | 226 | unsigned int i; |
db90b274 | 227 | for (i = 0; i < C448_SCALAR_LIMBS; i++) { |
7324473f MC |
228 | chain = (chain + a->limb[i]) + (sc_p->limb[i] & mask); |
229 | out->limb[i] = chain; | |
aeeef83c | 230 | chain >>= C448_WORD_BITS; |
7324473f | 231 | } |
db90b274 | 232 | for (i = 0; i < C448_SCALAR_LIMBS - 1; i++) |
205fd638 | 233 | out->limb[i] = out->limb[i] >> 1 | out->limb[i + 1] << (WBITS - 1); |
205fd638 | 234 | out->limb[i] = out->limb[i] >> 1 | chain << (WBITS - 1); |
7324473f | 235 | } |