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