1 /*
2 * Copyright 2017-2023 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright 2014 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
13 #ifndef OSSL_CRYPTO_EC_CURVE448_FIELD_H
14 #define OSSL_CRYPTO_EC_CURVE448_FIELD_H
15
16 #include "internal/constant_time.h"
17 #include <string.h>
18 #include <assert.h>
19 #include "word.h"
20
21 #define NLIMBS (64 / sizeof(word_t))
22 #define X_SER_BYTES 56
23 #define SER_BYTES 56
24
25 #if defined(__GNUC__) || defined(__clang__)
26 #define INLINE_UNUSED __inline__ __attribute__((__unused__, __always_inline__))
27 #define RESTRICT __restrict__
28 #define ALIGNED __attribute__((__aligned__(16)))
29 #else
30 #define INLINE_UNUSED ossl_inline
31 #define RESTRICT
32 #define ALIGNED
33 #endif
34
35 typedef struct gf_s {
36 word_t limb[NLIMBS];
37 } ALIGNED gf_s, gf[1];
38
39 /* RFC 7748 support */
40 #define X_PUBLIC_BYTES X_SER_BYTES
41 #define X_PRIVATE_BYTES X_PUBLIC_BYTES
42 #define X_PRIVATE_BITS 448
43
gf_copy(gf out,const gf a)44 static INLINE_UNUSED void gf_copy(gf out, const gf a)
45 {
46 *out = *a;
47 }
48
49 static INLINE_UNUSED void gf_add_RAW(gf out, const gf a, const gf b);
50 static INLINE_UNUSED void gf_sub_RAW(gf out, const gf a, const gf b);
51 static INLINE_UNUSED void gf_bias(gf inout, int amount);
52 static INLINE_UNUSED void gf_weak_reduce(gf inout);
53
54 void gf_strong_reduce(gf inout);
55 void gf_add(gf out, const gf a, const gf b);
56 void gf_sub(gf out, const gf a, const gf b);
57 void ossl_gf_mul(gf_s *RESTRICT out, const gf a, const gf b);
58 void ossl_gf_mulw_unsigned(gf_s *RESTRICT out, const gf a, uint32_t b);
59 void ossl_gf_sqr(gf_s *RESTRICT out, const gf a);
60 mask_t gf_isr(gf a, const gf x); /** a^2 x = 1, QNR, or 0 if x=0. Return true if successful */
61 mask_t gf_eq(const gf x, const gf y);
62 mask_t gf_lobit(const gf x);
63 mask_t gf_hibit(const gf x);
64
65 void gf_serialize(uint8_t serial[SER_BYTES], const gf x, int with_highbit);
66 mask_t gf_deserialize(gf x, const uint8_t serial[SER_BYTES], int with_hibit,
67 uint8_t hi_nmask);
68
69 #define LIMBPERM(i) (i)
70 #if (ARCH_WORD_BITS == 32)
71 #include "arch_32/f_impl.h" /* Bring in the inline implementations */
72 #define LIMB_MASK(i) (((1) << LIMB_PLACE_VALUE(i)) - 1)
73 #elif (ARCH_WORD_BITS == 64)
74 #include "arch_64/f_impl.h" /* Bring in the inline implementations */
75 #define LIMB_MASK(i) (((1ULL) << LIMB_PLACE_VALUE(i)) - 1)
76 #endif
77
78 static const gf ZERO = { { { 0 } } }, ONE = { { { 1 } } };
79
80 /* Square x, n times. */
gf_sqrn(gf_s * RESTRICT y,const gf x,int n)81 static ossl_inline void gf_sqrn(gf_s *RESTRICT y, const gf x, int n)
82 {
83 gf tmp;
84
85 assert(n > 0);
86 if (n & 1) {
87 ossl_gf_sqr(y, x);
88 n--;
89 } else {
90 ossl_gf_sqr(tmp, x);
91 ossl_gf_sqr(y, tmp);
92 n -= 2;
93 }
94 for (; n; n -= 2) {
95 ossl_gf_sqr(tmp, y);
96 ossl_gf_sqr(y, tmp);
97 }
98 }
99
100 #define gf_add_nr gf_add_RAW
101
102 /* Subtract mod p. Bias by 2 and don't reduce */
gf_sub_nr(gf c,const gf a,const gf b)103 static ossl_inline void gf_sub_nr(gf c, const gf a, const gf b)
104 {
105 gf_sub_RAW(c, a, b);
106 gf_bias(c, 2);
107 if (GF_HEADROOM < 3)
108 gf_weak_reduce(c);
109 }
110
111 /* Subtract mod p. Bias by amt but don't reduce. */
gf_subx_nr(gf c,const gf a,const gf b,int amt)112 static ossl_inline void gf_subx_nr(gf c, const gf a, const gf b, int amt)
113 {
114 gf_sub_RAW(c, a, b);
115 gf_bias(c, amt);
116 if (GF_HEADROOM < amt + 1)
117 gf_weak_reduce(c);
118 }
119
120 /* Mul by signed int. Not constant-time WRT the sign of that int. */
gf_mulw(gf c,const gf a,int32_t w)121 static ossl_inline void gf_mulw(gf c, const gf a, int32_t w)
122 {
123 if (w > 0) {
124 ossl_gf_mulw_unsigned(c, a, w);
125 } else {
126 ossl_gf_mulw_unsigned(c, a, -w);
127 gf_sub(c, ZERO, c);
128 }
129 }
130
131 /* Constant time, x = is_z ? z : y */
gf_cond_sel(gf x,const gf y,const gf z,mask_t is_z)132 static ossl_inline void gf_cond_sel(gf x, const gf y, const gf z, mask_t is_z)
133 {
134 size_t i;
135
136 for (i = 0; i < NLIMBS; i++) {
137 #if ARCH_WORD_BITS == 32
138 x[0].limb[i] = constant_time_select_32(is_z, z[0].limb[i],
139 y[0].limb[i]);
140 #else
141 /* Must be 64 bit */
142 x[0].limb[i] = constant_time_select_64(is_z, z[0].limb[i],
143 y[0].limb[i]);
144 #endif
145 }
146 }
147
148 /* Constant time, if (neg) x=-x; */
gf_cond_neg(gf x,mask_t neg)149 static ossl_inline void gf_cond_neg(gf x, mask_t neg)
150 {
151 gf y;
152
153 gf_sub(y, ZERO, x);
154 gf_cond_sel(x, x, y, neg);
155 }
156
157 /* Constant time, if (swap) (x,y) = (y,x); */
gf_cond_swap(gf x,gf_s * RESTRICT y,mask_t swap)158 static ossl_inline void gf_cond_swap(gf x, gf_s *RESTRICT y, mask_t swap)
159 {
160 size_t i;
161
162 for (i = 0; i < NLIMBS; i++) {
163 #if ARCH_WORD_BITS == 32
164 constant_time_cond_swap_32(swap, &(x[0].limb[i]), &(y->limb[i]));
165 #else
166 /* Must be 64 bit */
167 constant_time_cond_swap_64(swap, &(x[0].limb[i]), &(y->limb[i]));
168 #endif
169 }
170 }
171
172 #endif /* OSSL_CRYPTO_EC_CURVE448_FIELD_H */
173