Some style fixes
[openssl.git] / crypto / ec / curve448 / f_generic.c
1 /*
2  * Copyright 2017-2018 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 "field.h"
13
14 static const gf MODULUS = {
15     FIELD_LITERAL(0xffffffffffffff, 0xffffffffffffff, 0xffffffffffffff,
16                   0xffffffffffffff, 0xfffffffffffffe, 0xffffffffffffff,
17                   0xffffffffffffff, 0xffffffffffffff)
18 };
19
20 /* Serialize to wire format. */
21 void gf_serialize(uint8_t serial[SER_BYTES], const gf x, int with_hibit)
22 {
23     unsigned int j = 0, fill = 0;
24     dword_t buffer = 0;
25     int i;
26     gf red;
27
28     gf_copy(red, x);
29     gf_strong_reduce(red);
30     if (!with_hibit)
31         assert(gf_hibit(red) == 0);
32
33     UNROLL for (i = 0; i < (with_hibit ? X_SER_BYTES : SER_BYTES); i++) {
34         if (fill < 8 && j < NLIMBS) {
35             buffer |= ((dword_t) red->limb[LIMBPERM(j)]) << fill;
36             fill += LIMB_PLACE_VALUE(LIMBPERM(j));
37             j++;
38         }
39         serial[i] = (uint8_t)buffer;
40         fill -= 8;
41         buffer >>= 8;
42     }
43 }
44
45 /* Return high bit of x = low bit of 2x mod p */
46 mask_t gf_hibit(const gf x)
47 {
48     gf y;
49     gf_add(y, x, x);
50     gf_strong_reduce(y);
51     return 0 - (y->limb[0] & 1);
52 }
53
54 /* Return high bit of x = low bit of 2x mod p */
55 mask_t gf_lobit(const gf x)
56 {
57     gf y;
58     gf_copy(y, x);
59     gf_strong_reduce(y);
60     return 0 - (y->limb[0] & 1);
61 }
62
63 /* Deserialize from wire format; return -1 on success and 0 on failure. */
64 mask_t gf_deserialize(gf x, const uint8_t serial[SER_BYTES], int with_hibit,
65                       uint8_t hi_nmask)
66 {
67     unsigned int j = 0, fill = 0;
68     dword_t buffer = 0;
69     dsword_t scarry = 0;
70     const unsigned nbytes = with_hibit ? X_SER_BYTES : SER_BYTES;
71     unsigned int i;
72     mask_t succ;
73
74     UNROLL for (i = 0; i < NLIMBS; i++) {
75         UNROLL while (fill < LIMB_PLACE_VALUE(LIMBPERM(i)) && j < nbytes) {
76             uint8_t sj = serial[j];
77             if (j == nbytes - 1)
78                 sj &= ~hi_nmask;
79             buffer |= ((dword_t) sj) << fill;
80             fill += 8;
81             j++;
82         }
83         x->limb[LIMBPERM(i)] = (word_t)
84             ((i < NLIMBS - 1) ? buffer & LIMB_MASK(LIMBPERM(i)) : buffer);
85         fill -= LIMB_PLACE_VALUE(LIMBPERM(i));
86         buffer >>= LIMB_PLACE_VALUE(LIMBPERM(i));
87         scarry =
88             (scarry + x->limb[LIMBPERM(i)] -
89              MODULUS->limb[LIMBPERM(i)]) >> (8 * sizeof(word_t));
90     }
91     succ = with_hibit ? 0 - (mask_t) 1 : ~gf_hibit(x);
92     return succ & word_is_zero((word_t)buffer) & ~word_is_zero((word_t)scarry);
93 }
94
95 /* Reduce to canonical form. */
96 void gf_strong_reduce(gf a)
97 {
98     dsword_t scarry;
99     word_t scarry_0;
100     dword_t carry = 0;
101     unsigned int i;
102
103     /* first, clear high */
104     gf_weak_reduce(a);          /* Determined to have negligible perf impact. */
105
106     /* now the total is less than 2p */
107
108     /* compute total_value - p.  No need to reduce mod p. */
109     scarry = 0;
110     for (i = 0; i < NLIMBS; i++) {
111         scarry = scarry + a->limb[LIMBPERM(i)] - MODULUS->limb[LIMBPERM(i)];
112         a->limb[LIMBPERM(i)] = scarry & LIMB_MASK(LIMBPERM(i));
113         scarry >>= LIMB_PLACE_VALUE(LIMBPERM(i));
114     }
115
116     /*
117      * uncommon case: it was >= p, so now scarry = 0 and this = x common case:
118      * it was < p, so now scarry = -1 and this = x - p + 2^255 so let's add
119      * back in p.  will carry back off the top for 2^255.
120      */
121     assert(word_is_zero(scarry) | word_is_zero(scarry + 1));
122
123     scarry_0 = (word_t)scarry;
124
125     /* add it back */
126     for (i = 0; i < NLIMBS; i++) {
127         carry =
128             carry + a->limb[LIMBPERM(i)] +
129             (scarry_0 & MODULUS->limb[LIMBPERM(i)]);
130         a->limb[LIMBPERM(i)] = carry & LIMB_MASK(LIMBPERM(i));
131         carry >>= LIMB_PLACE_VALUE(LIMBPERM(i));
132     }
133
134     assert(word_is_zero(carry + scarry_0));
135 }
136
137 /* Subtract two gf elements d=a-b */
138 void gf_sub(gf d, const gf a, const gf b)
139 {
140     gf_sub_RAW(d, a, b);
141     gf_bias(d, 2);
142     gf_weak_reduce(d);
143 }
144
145 /* Add two field elements d = a+b */
146 void gf_add(gf d, const gf a, const gf b)
147 {
148     gf_add_RAW(d, a, b);
149     gf_weak_reduce(d);
150 }
151
152 /* Compare a==b */
153 mask_t gf_eq(const gf a, const gf b)
154 {
155     gf c;
156     mask_t ret = 0;
157     unsigned int i;
158
159     gf_sub(c, a, b);
160     gf_strong_reduce(c);
161
162     for (i = 0; i < NLIMBS; i++)
163         ret |= c->limb[LIMBPERM(i)];
164
165     return word_is_zero(ret);
166 }
167
168 mask_t gf_isr(gf a, const gf x)
169 {
170     gf L0, L1, L2;
171     gf_sqr(L1, x);
172     gf_mul(L2, x, L1);
173     gf_sqr(L1, L2);
174     gf_mul(L2, x, L1);
175     gf_sqrn(L1, L2, 3);
176     gf_mul(L0, L2, L1);
177     gf_sqrn(L1, L0, 3);
178     gf_mul(L0, L2, L1);
179     gf_sqrn(L2, L0, 9);
180     gf_mul(L1, L0, L2);
181     gf_sqr(L0, L1);
182     gf_mul(L2, x, L0);
183     gf_sqrn(L0, L2, 18);
184     gf_mul(L2, L1, L0);
185     gf_sqrn(L0, L2, 37);
186     gf_mul(L1, L2, L0);
187     gf_sqrn(L0, L1, 37);
188     gf_mul(L1, L2, L0);
189     gf_sqrn(L0, L1, 111);
190     gf_mul(L2, L1, L0);
191     gf_sqr(L0, L2);
192     gf_mul(L1, x, L0);
193     gf_sqrn(L0, L1, 223);
194     gf_mul(L1, L2, L0);
195     gf_sqr(L2, L1);
196     gf_mul(L0, L2, x);
197     gf_copy(a, L1);
198     return gf_eq(L0, ONE);
199 }