/src/openssl/crypto/ec/curve448/field.h

Source
/*
 * Copyright 2017-2023 The OpenSSL Project Authors. All Rights Reserved.
 * Copyright 2014 Cryptography Research, Inc.
 *
 * Licensed under the Apache License 2.0 (the "License").  You may not use
 * this file except in compliance with the License.  You can obtain a copy
 * in the file LICENSE in the source distribution or at
 * https://www.openssl.org/source/license.html
 *
 * Originally written by Mike Hamburg
 */

#ifndef OSSL_CRYPTO_EC_CURVE448_FIELD_H
#define OSSL_CRYPTO_EC_CURVE448_FIELD_H

#include "internal/constant_time.h"
#include <string.h>
#include <assert.h>
#include "word.h"

#define NLIMBS (64 / sizeof(word_t))
#define X_SER_BYTES 56
#define SER_BYTES 56

#if defined(__GNUC__) || defined(__clang__)
#define INLINE_UNUSED __inline__ __attribute__((__unused__, __always_inline__))
#define RESTRICT __restrict__
#define ALIGNED __attribute__((__aligned__(16)))
#else
#define INLINE_UNUSED ossl_inline
#define RESTRICT
#define ALIGNED
#endif

typedef struct gf_s {
    word_t limb[NLIMBS];
} ALIGNED gf_s, gf[1];

/* RFC 7748 support */
#define X_PUBLIC_BYTES X_SER_BYTES
#define X_PRIVATE_BYTES X_PUBLIC_BYTES
#define X_PRIVATE_BITS 448

static INLINE_UNUSED void gf_copy(gf out, const gf a)
{
    *out = *a;
}

static INLINE_UNUSED void gf_add_RAW(gf out, const gf a, const gf b);
static INLINE_UNUSED void gf_sub_RAW(gf out, const gf a, const gf b);
static INLINE_UNUSED void gf_bias(gf inout, int amount);
static INLINE_UNUSED void gf_weak_reduce(gf inout);

void gf_strong_reduce(gf inout);
void gf_add(gf out, const gf a, const gf b);
void gf_sub(gf out, const gf a, const gf b);
void ossl_gf_mul(gf_s *RESTRICT out, const gf a, const gf b);
void ossl_gf_mulw_unsigned(gf_s *RESTRICT out, const gf a, uint32_t b);
void ossl_gf_sqr(gf_s *RESTRICT out, const gf a);
mask_t gf_isr(gf a, const gf x); /** a^2 x = 1, QNR, or 0 if x=0.  Return true if successful */
mask_t gf_eq(const gf x, const gf y);
mask_t gf_lobit(const gf x);
mask_t gf_hibit(const gf x);

void gf_serialize(uint8_t serial[SER_BYTES], const gf x, int with_highbit);
mask_t gf_deserialize(gf x, const uint8_t serial[SER_BYTES], int with_hibit,
    uint8_t hi_nmask);

/* clang-format off */
#define LIMBPERM(i) (i)
#if (ARCH_WORD_BITS == 32)
#define GF_HEADROOM 2
#define LIMB(x) ((x) & ((1 << 28) - 1)), ((x) >> 28)
#define FIELD_LITERAL(a, b, c, d, e, f, g, h)                                      \
    {                                                                              \
        {                                                                          \
            LIMB(a), LIMB(b), LIMB(c), LIMB(d), LIMB(e), LIMB(f), LIMB(g), LIMB(h) \
        }                                                                          \
    }

#define LIMB_PLACE_VALUE(i) 28

void gf_add_RAW(gf out, const gf a, const gf b)
{
    unsigned int i;

    for (i = 0; i < NLIMBS; i++)
        out->limb[i] = a->limb[i] + b->limb[i];
}

void gf_sub_RAW(gf out, const gf a, const gf b)
{
    unsigned int i;

    for (i = 0; i < NLIMBS; i++)
        out->limb[i] = a->limb[i] - b->limb[i];
}

void gf_bias(gf a, int amt)
{
    unsigned int i;
    uint32_t co1 = ((1 << 28) - 1) * amt, co2 = co1 - amt;

    for (i = 0; i < NLIMBS; i++)
        a->limb[i] += (i == NLIMBS / 2) ? co2 : co1;
}

void gf_weak_reduce(gf a)
{
    uint32_t mask = (1 << 28) - 1;
    uint32_t tmp = a->limb[NLIMBS - 1] >> 28;
    unsigned int i;

    a->limb[NLIMBS / 2] += tmp;
    for (i = NLIMBS - 1; i > 0; i--)
        a->limb[i] = (a->limb[i] & mask) + (a->limb[i - 1] >> 28);
    a->limb[0] = (a->limb[0] & mask) + tmp;
}
#define LIMB_MASK(i) (((1) << LIMB_PLACE_VALUE(i)) - 1)
#elif (ARCH_WORD_BITS == 64)
#define GF_HEADROOM 9999 /* Everything is reduced anyway */
#define FIELD_LITERAL(a, b, c, d, e, f, g, h) \
    {                                         \
        {                                     \
            a, b, c, d, e, f, g, h            \
        }                                     \
    }

#define LIMB_PLACE_VALUE(i) 56

void gf_add_RAW(gf out, const gf a, const gf b)
{
    unsigned int i;

    for (i = 0; i < NLIMBS; i++)
        out->limb[i] = a->limb[i] + b->limb[i];

    gf_weak_reduce(out);
}

void gf_sub_RAW(gf out, const gf a, const gf b)
{
    uint64_t co1 = ((1ULL << 56) - 1) * 2, co2 = co1 - 2;
    unsigned int i;

    for (i = 0; i < NLIMBS; i++)
        out->limb[i] = a->limb[i] - b->limb[i] + ((i == NLIMBS / 2) ? co2 : co1);

    gf_weak_reduce(out);
}

void gf_bias(gf a, int amt)
{
}

void gf_weak_reduce(gf a)
{
    uint64_t mask = (1ULL << 56) - 1;
    uint64_t tmp = a->limb[NLIMBS - 1] >> 56;
    unsigned int i;

    a->limb[NLIMBS / 2] += tmp;
    for (i = NLIMBS - 1; i > 0; i--)
        a->limb[i] = (a->limb[i] & mask) + (a->limb[i - 1] >> 56);
    a->limb[0] = (a->limb[0] & mask) + tmp;
}
#define LIMB_MASK(i) (((1ULL) << LIMB_PLACE_VALUE(i)) - 1)
#endif
/* clang-format on */

static const gf ZERO = { { { 0 } } }, ONE = { { { 1 } } };

/* Square x, n times. */
static ossl_inline void gf_sqrn(gf_s *RESTRICT y, const gf x, int n)
{
    gf tmp;

    assert(n > 0);
    if (n & 1) {
        ossl_gf_sqr(y, x);
        n--;
    } else {
        ossl_gf_sqr(tmp, x);
        ossl_gf_sqr(y, tmp);
        n -= 2;
    }
    for (; n; n -= 2) {
        ossl_gf_sqr(tmp, y);
        ossl_gf_sqr(y, tmp);
    }
}

#define gf_add_nr gf_add_RAW

/* Subtract mod p.  Bias by 2 and don't reduce  */
static ossl_inline void gf_sub_nr(gf c, const gf a, const gf b)
{
    gf_sub_RAW(c, a, b);
    gf_bias(c, 2);
    if (GF_HEADROOM < 3)
        gf_weak_reduce(c);
}

/* Subtract mod p. Bias by amt but don't reduce.  */
static ossl_inline void gf_subx_nr(gf c, const gf a, const gf b, int amt)
{
    gf_sub_RAW(c, a, b);
    gf_bias(c, amt);
    if (GF_HEADROOM < amt + 1)
        gf_weak_reduce(c);
}

/* Mul by signed int.  Not constant-time WRT the sign of that int. */
static ossl_inline void gf_mulw(gf c, const gf a, int32_t w)
{
    if (w > 0) {
        ossl_gf_mulw_unsigned(c, a, w);
    } else {
        ossl_gf_mulw_unsigned(c, a, -w);
        gf_sub(c, ZERO, c);
    }
}

/* Constant time, x = is_z ? z : y */
static ossl_inline void gf_cond_sel(gf x, const gf y, const gf z, mask_t is_z)
{
    size_t i;

    for (i = 0; i < NLIMBS; i++) {
#if ARCH_WORD_BITS == 32
        x[0].limb[i] = constant_time_select_32(is_z, z[0].limb[i],
            y[0].limb[i]);
#else
        /* Must be 64 bit */
        x[0].limb[i] = constant_time_select_64(is_z, z[0].limb[i],
            y[0].limb[i]);
#endif
    }
}

/* Constant time, if (neg) x=-x; */
static ossl_inline void gf_cond_neg(gf x, mask_t neg)
{
    gf y;

    gf_sub(y, ZERO, x);
    gf_cond_sel(x, x, y, neg);
}

/* Constant time, if (swap) (x,y) = (y,x); */
static ossl_inline void gf_cond_swap(gf x, gf_s *RESTRICT y, mask_t swap)
{
    size_t i;

    for (i = 0; i < NLIMBS; i++) {
#if ARCH_WORD_BITS == 32
        constant_time_cond_swap_32(swap, &(x[0].limb[i]), &(y->limb[i]));
#else
        /* Must be 64 bit */
        constant_time_cond_swap_64(swap, &(x[0].limb[i]), &(y->limb[i]));
#endif
    }
}

#endif /* OSSL_CRYPTO_EC_CURVE448_FIELD_H */

Coverage Report

Created: 2026-05-20 07:05

Line	Count	Source
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	0	#define NLIMBS (64 / sizeof(word_t))
22	0	#define X_SER_BYTES 56
23	0	#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	0	#define X_PUBLIC_BYTES X_SER_BYTES
41	0	#define X_PRIVATE_BYTES X_PUBLIC_BYTES
42	0	#define X_PRIVATE_BITS 448
43
44		static INLINE_UNUSED void gf_copy(gf out, const gf a)
45	0	{
46	0	out = a;
47	0	} Unexecuted instantiation: curve448.c:gf_copy Unexecuted instantiation: curve448_tables.c:gf_copy Unexecuted instantiation: eddsa.c:gf_copy Unexecuted instantiation: f_generic.c:gf_copy Unexecuted instantiation: scalar.c:gf_copy Unexecuted instantiation: f_impl64.c:gf_copy
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		/* clang-format off */
70	0	#define LIMBPERM(i) (i)
71		#if (ARCH_WORD_BITS == 32)
72		#define GF_HEADROOM 2
73		#define LIMB(x) ((x) & ((1 << 28) - 1)), ((x) >> 28)
74		#define FIELD_LITERAL(a, b, c, d, e, f, g, h) \
75		{ \
76		{ \
77		LIMB(a), LIMB(b), LIMB(c), LIMB(d), LIMB(e), LIMB(f), LIMB(g), LIMB(h) \
78		} \
79		}
80
81		#define LIMB_PLACE_VALUE(i) 28
82
83		void gf_add_RAW(gf out, const gf a, const gf b)
84		{
85		unsigned int i;
86
87		for (i = 0; i < NLIMBS; i++)
88		out->limb[i] = a->limb[i] + b->limb[i];
89		}
90
91		void gf_sub_RAW(gf out, const gf a, const gf b)
92		{
93		unsigned int i;
94
95		for (i = 0; i < NLIMBS; i++)
96		out->limb[i] = a->limb[i] - b->limb[i];
97		}
98
99		void gf_bias(gf a, int amt)
100		{
101		unsigned int i;
102		uint32_t co1 = ((1 << 28) - 1) * amt, co2 = co1 - amt;
103
104		for (i = 0; i < NLIMBS; i++)
105		a->limb[i] += (i == NLIMBS / 2) ? co2 : co1;
106		}
107
108		void gf_weak_reduce(gf a)
109		{
110		uint32_t mask = (1 << 28) - 1;
111		uint32_t tmp = a->limb[NLIMBS - 1] >> 28;
112		unsigned int i;
113
114		a->limb[NLIMBS / 2] += tmp;
115		for (i = NLIMBS - 1; i > 0; i--)
116		a->limb[i] = (a->limb[i] & mask) + (a->limb[i - 1] >> 28);
117		a->limb[0] = (a->limb[0] & mask) + tmp;
118		}
119		#define LIMB_MASK(i) (((1) << LIMB_PLACE_VALUE(i)) - 1)
120		#elif (ARCH_WORD_BITS == 64)
121	0	#define GF_HEADROOM 9999 /* Everything is reduced anyway */
122		#define FIELD_LITERAL(a, b, c, d, e, f, g, h) \
123		{ \
124		{ \
125		a, b, c, d, e, f, g, h \
126		} \
127		}
128
129	0	#define LIMB_PLACE_VALUE(i) 56
130
131		void gf_add_RAW(gf out, const gf a, const gf b)
132	0	{
133	0	unsigned int i;
134
135	0	for (i = 0; i < NLIMBS; i++)
136	0	out->limb[i] = a->limb[i] + b->limb[i];
137
138	0	gf_weak_reduce(out);
139	0	} Unexecuted instantiation: curve448.c:gf_add_RAW Unexecuted instantiation: curve448_tables.c:gf_add_RAW Unexecuted instantiation: eddsa.c:gf_add_RAW Unexecuted instantiation: f_generic.c:gf_add_RAW Unexecuted instantiation: scalar.c:gf_add_RAW Unexecuted instantiation: f_impl64.c:gf_add_RAW
140
141		void gf_sub_RAW(gf out, const gf a, const gf b)
142	0	{
143	0	uint64_t co1 = ((1ULL << 56) - 1) * 2, co2 = co1 - 2;
144	0	unsigned int i;
145
146	0	for (i = 0; i < NLIMBS; i++)
147	0	out->limb[i] = a->limb[i] - b->limb[i] + ((i == NLIMBS / 2) ? co2 : co1);
148
149	0	gf_weak_reduce(out);
150	0	} Unexecuted instantiation: curve448.c:gf_sub_RAW Unexecuted instantiation: curve448_tables.c:gf_sub_RAW Unexecuted instantiation: eddsa.c:gf_sub_RAW Unexecuted instantiation: f_generic.c:gf_sub_RAW Unexecuted instantiation: scalar.c:gf_sub_RAW Unexecuted instantiation: f_impl64.c:gf_sub_RAW
151
152		void gf_bias(gf a, int amt)
153	0	{
154	0	} Unexecuted instantiation: curve448.c:gf_bias Unexecuted instantiation: curve448_tables.c:gf_bias Unexecuted instantiation: eddsa.c:gf_bias Unexecuted instantiation: f_generic.c:gf_bias Unexecuted instantiation: scalar.c:gf_bias Unexecuted instantiation: f_impl64.c:gf_bias
155
156		void gf_weak_reduce(gf a)
157	0	{
158	0	uint64_t mask = (1ULL << 56) - 1;
159	0	uint64_t tmp = a->limb[NLIMBS - 1] >> 56;
160	0	unsigned int i;
161
162	0	a->limb[NLIMBS / 2] += tmp;
163	0	for (i = NLIMBS - 1; i > 0; i--)
164	0	a->limb[i] = (a->limb[i] & mask) + (a->limb[i - 1] >> 56);
165	0	a->limb[0] = (a->limb[0] & mask) + tmp;
166	0	} Unexecuted instantiation: curve448.c:gf_weak_reduce Unexecuted instantiation: curve448_tables.c:gf_weak_reduce Unexecuted instantiation: eddsa.c:gf_weak_reduce Unexecuted instantiation: f_generic.c:gf_weak_reduce Unexecuted instantiation: scalar.c:gf_weak_reduce Unexecuted instantiation: f_impl64.c:gf_weak_reduce
167	0	#define LIMB_MASK(i) (((1ULL) << LIMB_PLACE_VALUE(i)) - 1)
168		#endif
169		/* clang-format on */
170
171		static const gf ZERO = { { { 0 } } }, ONE = { { { 1 } } };
172
173		/* Square x, n times. */
174		static ossl_inline void gf_sqrn(gf_s *RESTRICT y, const gf x, int n)
175	0	{
176	0	gf tmp;
177
178	0	assert(n > 0);
179	0	if (n & 1) {
180	0	ossl_gf_sqr(y, x);
181	0	n--;
182	0	} else {
183	0	ossl_gf_sqr(tmp, x);
184	0	ossl_gf_sqr(y, tmp);
185	0	n -= 2;
186	0	}
187	0	for (; n; n -= 2) {
188	0	ossl_gf_sqr(tmp, y);
189	0	ossl_gf_sqr(y, tmp);
190	0	}
191	0	} Unexecuted instantiation: curve448.c:gf_sqrn Unexecuted instantiation: curve448_tables.c:gf_sqrn Unexecuted instantiation: eddsa.c:gf_sqrn Unexecuted instantiation: f_generic.c:gf_sqrn Unexecuted instantiation: scalar.c:gf_sqrn Unexecuted instantiation: f_impl64.c:gf_sqrn
192
193	0	#define gf_add_nr gf_add_RAW
194
195		/* Subtract mod p. Bias by 2 and don't reduce */
196		static ossl_inline void gf_sub_nr(gf c, const gf a, const gf b)
197	0	{
198	0	gf_sub_RAW(c, a, b);
199	0	gf_bias(c, 2);
200	0	if (GF_HEADROOM < 3)
201	0	gf_weak_reduce(c);
202	0	} Unexecuted instantiation: curve448.c:gf_sub_nr Unexecuted instantiation: curve448_tables.c:gf_sub_nr Unexecuted instantiation: eddsa.c:gf_sub_nr Unexecuted instantiation: f_generic.c:gf_sub_nr Unexecuted instantiation: scalar.c:gf_sub_nr Unexecuted instantiation: f_impl64.c:gf_sub_nr
203
204		/* Subtract mod p. Bias by amt but don't reduce. */
205		static ossl_inline void gf_subx_nr(gf c, const gf a, const gf b, int amt)
206	0	{
207	0	gf_sub_RAW(c, a, b);
208	0	gf_bias(c, amt);
209	0	if (GF_HEADROOM < amt + 1)
210	0	gf_weak_reduce(c);
211	0	} Unexecuted instantiation: curve448.c:gf_subx_nr Unexecuted instantiation: curve448_tables.c:gf_subx_nr Unexecuted instantiation: eddsa.c:gf_subx_nr Unexecuted instantiation: f_generic.c:gf_subx_nr Unexecuted instantiation: scalar.c:gf_subx_nr Unexecuted instantiation: f_impl64.c:gf_subx_nr
212
213		/* Mul by signed int. Not constant-time WRT the sign of that int. */
214		static ossl_inline void gf_mulw(gf c, const gf a, int32_t w)
215	0	{
216	0	if (w > 0) {
217	0	ossl_gf_mulw_unsigned(c, a, w);
218	0	} else {
219	0	ossl_gf_mulw_unsigned(c, a, -w);
220	0	gf_sub(c, ZERO, c);
221	0	}
222	0	} Unexecuted instantiation: curve448.c:gf_mulw Unexecuted instantiation: curve448_tables.c:gf_mulw Unexecuted instantiation: eddsa.c:gf_mulw Unexecuted instantiation: f_generic.c:gf_mulw Unexecuted instantiation: scalar.c:gf_mulw Unexecuted instantiation: f_impl64.c:gf_mulw
223
224		/* Constant time, x = is_z ? z : y */
225		static ossl_inline void gf_cond_sel(gf x, const gf y, const gf z, mask_t is_z)
226	0	{
227	0	size_t i;
228
229	0	for (i = 0; i < NLIMBS; i++) {
230		#if ARCH_WORD_BITS == 32
231		x[0].limb[i] = constant_time_select_32(is_z, z[0].limb[i],
232		y[0].limb[i]);
233		#else
234		/* Must be 64 bit */
235	0	x[0].limb[i] = constant_time_select_64(is_z, z[0].limb[i],
236	0	y[0].limb[i]);
237	0	#endif
238	0	}
239	0	} Unexecuted instantiation: curve448.c:gf_cond_sel Unexecuted instantiation: curve448_tables.c:gf_cond_sel Unexecuted instantiation: eddsa.c:gf_cond_sel Unexecuted instantiation: f_generic.c:gf_cond_sel Unexecuted instantiation: scalar.c:gf_cond_sel Unexecuted instantiation: f_impl64.c:gf_cond_sel
240
241		/* Constant time, if (neg) x=-x; */
242		static ossl_inline void gf_cond_neg(gf x, mask_t neg)
243	0	{
244	0	gf y;
245
246	0	gf_sub(y, ZERO, x);
247	0	gf_cond_sel(x, x, y, neg);
248	0	} Unexecuted instantiation: curve448.c:gf_cond_neg Unexecuted instantiation: curve448_tables.c:gf_cond_neg Unexecuted instantiation: eddsa.c:gf_cond_neg Unexecuted instantiation: f_generic.c:gf_cond_neg Unexecuted instantiation: scalar.c:gf_cond_neg Unexecuted instantiation: f_impl64.c:gf_cond_neg
249
250		/* Constant time, if (swap) (x,y) = (y,x); */
251		static ossl_inline void gf_cond_swap(gf x, gf_s *RESTRICT y, mask_t swap)
252	0	{
253	0	size_t i;
254
255	0	for (i = 0; i < NLIMBS; i++) {
256		#if ARCH_WORD_BITS == 32
257		constant_time_cond_swap_32(swap, &(x[0].limb[i]), &(y->limb[i]));
258		#else
259		/* Must be 64 bit */
260	0	constant_time_cond_swap_64(swap, &(x[0].limb[i]), &(y->limb[i]));
261	0	#endif
262	0	}
263	0	} Unexecuted instantiation: curve448.c:gf_cond_swap Unexecuted instantiation: curve448_tables.c:gf_cond_swap Unexecuted instantiation: eddsa.c:gf_cond_swap Unexecuted instantiation: f_generic.c:gf_cond_swap Unexecuted instantiation: scalar.c:gf_cond_swap Unexecuted instantiation: f_impl64.c:gf_cond_swap
264
265		#endif /* OSSL_CRYPTO_EC_CURVE448_FIELD_H */