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