1465ae836SThomas Gleixner /* SPDX-License-Identifier: GPL-2.0-or-later */
25ce3e312SDmitry Kasatkin /* mpi.h - Multi Precision Integers
35ce3e312SDmitry Kasatkin * Copyright (C) 1994, 1996, 1998, 1999,
45ce3e312SDmitry Kasatkin * 2000, 2001 Free Software Foundation, Inc.
55ce3e312SDmitry Kasatkin *
65ce3e312SDmitry Kasatkin * This file is part of GNUPG.
75ce3e312SDmitry Kasatkin *
85ce3e312SDmitry Kasatkin * Note: This code is heavily based on the GNU MP Library.
95ce3e312SDmitry Kasatkin * Actually it's the same code with only minor changes in the
105ce3e312SDmitry Kasatkin * way the data is stored; this is to support the abstraction
115ce3e312SDmitry Kasatkin * of an optional secure memory allocation which may be used
125ce3e312SDmitry Kasatkin * to avoid revealing of sensitive data due to paging etc.
135ce3e312SDmitry Kasatkin * The GNU MP Library itself is published under the LGPL;
145ce3e312SDmitry Kasatkin * however I decided to publish this code under the plain GPL.
155ce3e312SDmitry Kasatkin */
165ce3e312SDmitry Kasatkin
175ce3e312SDmitry Kasatkin #ifndef G10_MPI_H
185ce3e312SDmitry Kasatkin #define G10_MPI_H
195ce3e312SDmitry Kasatkin
205ce3e312SDmitry Kasatkin #include <linux/types.h>
212d4d1eeaSTadeusz Struk #include <linux/scatterlist.h>
225ce3e312SDmitry Kasatkin
235ce3e312SDmitry Kasatkin #define BYTES_PER_MPI_LIMB (BITS_PER_LONG / 8)
245ce3e312SDmitry Kasatkin #define BITS_PER_MPI_LIMB BITS_PER_LONG
255ce3e312SDmitry Kasatkin
265ce3e312SDmitry Kasatkin typedef unsigned long int mpi_limb_t;
275ce3e312SDmitry Kasatkin typedef signed long int mpi_limb_signed_t;
285ce3e312SDmitry Kasatkin
295ce3e312SDmitry Kasatkin struct gcry_mpi {
305ce3e312SDmitry Kasatkin int alloced; /* array size (# of allocated limbs) */
315ce3e312SDmitry Kasatkin int nlimbs; /* number of valid limbs */
325ce3e312SDmitry Kasatkin int nbits; /* the real number of valid bits (info only) */
335ce3e312SDmitry Kasatkin int sign; /* indicates a negative number */
345ce3e312SDmitry Kasatkin unsigned flags; /* bit 0: array must be allocated in secure memory space */
355ce3e312SDmitry Kasatkin /* bit 1: not used */
365ce3e312SDmitry Kasatkin /* bit 2: the limb is a pointer to some m_alloced data */
375ce3e312SDmitry Kasatkin mpi_limb_t *d; /* array with the limbs */
385ce3e312SDmitry Kasatkin };
395ce3e312SDmitry Kasatkin
405ce3e312SDmitry Kasatkin typedef struct gcry_mpi *MPI;
415ce3e312SDmitry Kasatkin
425ce3e312SDmitry Kasatkin #define mpi_get_nlimbs(a) ((a)->nlimbs)
43a8ea8bddSTianjia Zhang #define mpi_has_sign(a) ((a)->sign)
445ce3e312SDmitry Kasatkin
455ce3e312SDmitry Kasatkin /*-- mpiutil.c --*/
465ce3e312SDmitry Kasatkin MPI mpi_alloc(unsigned nlimbs);
47a8ea8bddSTianjia Zhang void mpi_clear(MPI a);
485ce3e312SDmitry Kasatkin void mpi_free(MPI a);
495ce3e312SDmitry Kasatkin int mpi_resize(MPI a, unsigned nlimbs);
505ce3e312SDmitry Kasatkin
mpi_new(unsigned int nbits)51a8ea8bddSTianjia Zhang static inline MPI mpi_new(unsigned int nbits)
52a8ea8bddSTianjia Zhang {
53a8ea8bddSTianjia Zhang return mpi_alloc((nbits + BITS_PER_MPI_LIMB - 1) / BITS_PER_MPI_LIMB);
54a8ea8bddSTianjia Zhang }
55a8ea8bddSTianjia Zhang
56a8ea8bddSTianjia Zhang MPI mpi_copy(MPI a);
57a8ea8bddSTianjia Zhang MPI mpi_alloc_like(MPI a);
58a8ea8bddSTianjia Zhang void mpi_snatch(MPI w, MPI u);
59a8ea8bddSTianjia Zhang MPI mpi_set(MPI w, MPI u);
60a8ea8bddSTianjia Zhang MPI mpi_set_ui(MPI w, unsigned long u);
61a8ea8bddSTianjia Zhang MPI mpi_alloc_set_ui(unsigned long u);
62a8ea8bddSTianjia Zhang void mpi_swap_cond(MPI a, MPI b, unsigned long swap);
63a8ea8bddSTianjia Zhang
64a8ea8bddSTianjia Zhang /* Constants used to return constant MPIs. See mpi_init if you
65a8ea8bddSTianjia Zhang * want to add more constants.
66a8ea8bddSTianjia Zhang */
67a8ea8bddSTianjia Zhang #define MPI_NUMBER_OF_CONSTANTS 6
68a8ea8bddSTianjia Zhang enum gcry_mpi_constants {
69a8ea8bddSTianjia Zhang MPI_C_ZERO,
70a8ea8bddSTianjia Zhang MPI_C_ONE,
71a8ea8bddSTianjia Zhang MPI_C_TWO,
72a8ea8bddSTianjia Zhang MPI_C_THREE,
73a8ea8bddSTianjia Zhang MPI_C_FOUR,
74a8ea8bddSTianjia Zhang MPI_C_EIGHT
75a8ea8bddSTianjia Zhang };
76a8ea8bddSTianjia Zhang
77a8ea8bddSTianjia Zhang MPI mpi_const(enum gcry_mpi_constants no);
78a8ea8bddSTianjia Zhang
795ce3e312SDmitry Kasatkin /*-- mpicoder.c --*/
80a8ea8bddSTianjia Zhang
81a8ea8bddSTianjia Zhang /* Different formats of external big integer representation. */
82a8ea8bddSTianjia Zhang enum gcry_mpi_format {
83a8ea8bddSTianjia Zhang GCRYMPI_FMT_NONE = 0,
84a8ea8bddSTianjia Zhang GCRYMPI_FMT_STD = 1, /* Twos complement stored without length. */
85a8ea8bddSTianjia Zhang GCRYMPI_FMT_PGP = 2, /* As used by OpenPGP (unsigned only). */
86a8ea8bddSTianjia Zhang GCRYMPI_FMT_SSH = 3, /* As used by SSH (like STD but with length). */
87a8ea8bddSTianjia Zhang GCRYMPI_FMT_HEX = 4, /* Hex format. */
88a8ea8bddSTianjia Zhang GCRYMPI_FMT_USG = 5, /* Like STD but unsigned. */
89a8ea8bddSTianjia Zhang GCRYMPI_FMT_OPAQUE = 8 /* Opaque format (some functions only). */
90a8ea8bddSTianjia Zhang };
91a8ea8bddSTianjia Zhang
92e1045992SDavid Howells MPI mpi_read_raw_data(const void *xbuffer, size_t nbytes);
935ce3e312SDmitry Kasatkin MPI mpi_read_from_buffer(const void *buffer, unsigned *ret_nread);
94a8ea8bddSTianjia Zhang int mpi_fromstr(MPI val, const char *str);
95a8ea8bddSTianjia Zhang MPI mpi_scanval(const char *string);
962d4d1eeaSTadeusz Struk MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int len);
975ce3e312SDmitry Kasatkin void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign);
98d37e2969STadeusz Struk int mpi_read_buffer(MPI a, uint8_t *buf, unsigned buf_len, unsigned *nbytes,
99d37e2969STadeusz Struk int *sign);
1009b45b7bbSHerbert Xu int mpi_write_to_sgl(MPI a, struct scatterlist *sg, unsigned nbytes,
1012d4d1eeaSTadeusz Struk int *sign);
102a8ea8bddSTianjia Zhang int mpi_print(enum gcry_mpi_format format, unsigned char *buffer,
103a8ea8bddSTianjia Zhang size_t buflen, size_t *nwritten, MPI a);
104a8ea8bddSTianjia Zhang
105a8ea8bddSTianjia Zhang /*-- mpi-mod.c --*/
106a8ea8bddSTianjia Zhang void mpi_mod(MPI rem, MPI dividend, MPI divisor);
107a8ea8bddSTianjia Zhang
108a8ea8bddSTianjia Zhang /* Context used with Barrett reduction. */
109a8ea8bddSTianjia Zhang struct barrett_ctx_s;
110a8ea8bddSTianjia Zhang typedef struct barrett_ctx_s *mpi_barrett_t;
111a8ea8bddSTianjia Zhang
112a8ea8bddSTianjia Zhang mpi_barrett_t mpi_barrett_init(MPI m, int copy);
113a8ea8bddSTianjia Zhang void mpi_barrett_free(mpi_barrett_t ctx);
114a8ea8bddSTianjia Zhang void mpi_mod_barrett(MPI r, MPI x, mpi_barrett_t ctx);
115a8ea8bddSTianjia Zhang void mpi_mul_barrett(MPI w, MPI u, MPI v, mpi_barrett_t ctx);
1165ce3e312SDmitry Kasatkin
1175ce3e312SDmitry Kasatkin /*-- mpi-pow.c --*/
1185ce3e312SDmitry Kasatkin int mpi_powm(MPI res, MPI base, MPI exp, MPI mod);
1195ce3e312SDmitry Kasatkin
1205ce3e312SDmitry Kasatkin /*-- mpi-cmp.c --*/
1215ce3e312SDmitry Kasatkin int mpi_cmp_ui(MPI u, ulong v);
1225ce3e312SDmitry Kasatkin int mpi_cmp(MPI u, MPI v);
123a8ea8bddSTianjia Zhang int mpi_cmpabs(MPI u, MPI v);
1245ce3e312SDmitry Kasatkin
1254278e9d9SMarcelo Henrique Cerri /*-- mpi-sub-ui.c --*/
1264278e9d9SMarcelo Henrique Cerri int mpi_sub_ui(MPI w, MPI u, unsigned long vval);
1274278e9d9SMarcelo Henrique Cerri
1285ce3e312SDmitry Kasatkin /*-- mpi-bit.c --*/
1295ce3e312SDmitry Kasatkin void mpi_normalize(MPI a);
1305ce3e312SDmitry Kasatkin unsigned mpi_get_nbits(MPI a);
131a8ea8bddSTianjia Zhang int mpi_test_bit(MPI a, unsigned int n);
132a8ea8bddSTianjia Zhang void mpi_set_bit(MPI a, unsigned int n);
133a8ea8bddSTianjia Zhang void mpi_set_highbit(MPI a, unsigned int n);
134a8ea8bddSTianjia Zhang void mpi_clear_highbit(MPI a, unsigned int n);
135a8ea8bddSTianjia Zhang void mpi_clear_bit(MPI a, unsigned int n);
136a8ea8bddSTianjia Zhang void mpi_rshift_limbs(MPI a, unsigned int count);
137a8ea8bddSTianjia Zhang void mpi_rshift(MPI x, MPI a, unsigned int n);
138a8ea8bddSTianjia Zhang void mpi_lshift_limbs(MPI a, unsigned int count);
139a8ea8bddSTianjia Zhang void mpi_lshift(MPI x, MPI a, unsigned int n);
140a8ea8bddSTianjia Zhang
141a8ea8bddSTianjia Zhang /*-- mpi-add.c --*/
142a8ea8bddSTianjia Zhang void mpi_add_ui(MPI w, MPI u, unsigned long v);
143a8ea8bddSTianjia Zhang void mpi_add(MPI w, MPI u, MPI v);
144a8ea8bddSTianjia Zhang void mpi_sub(MPI w, MPI u, MPI v);
145a8ea8bddSTianjia Zhang void mpi_addm(MPI w, MPI u, MPI v, MPI m);
146a8ea8bddSTianjia Zhang void mpi_subm(MPI w, MPI u, MPI v, MPI m);
147a8ea8bddSTianjia Zhang
148a8ea8bddSTianjia Zhang /*-- mpi-mul.c --*/
149a8ea8bddSTianjia Zhang void mpi_mul(MPI w, MPI u, MPI v);
150a8ea8bddSTianjia Zhang void mpi_mulm(MPI w, MPI u, MPI v, MPI m);
151a8ea8bddSTianjia Zhang
152a8ea8bddSTianjia Zhang /*-- mpi-div.c --*/
153a8ea8bddSTianjia Zhang void mpi_tdiv_r(MPI rem, MPI num, MPI den);
154a8ea8bddSTianjia Zhang void mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor);
155a8ea8bddSTianjia Zhang void mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor);
156a8ea8bddSTianjia Zhang
157a8ea8bddSTianjia Zhang /*-- mpi-inv.c --*/
158a8ea8bddSTianjia Zhang int mpi_invm(MPI x, MPI a, MPI n);
1595ce3e312SDmitry Kasatkin
160d58bb7e5STianjia Zhang /*-- ec.c --*/
161d58bb7e5STianjia Zhang
162d58bb7e5STianjia Zhang /* Object to represent a point in projective coordinates */
163d58bb7e5STianjia Zhang struct gcry_mpi_point {
164d58bb7e5STianjia Zhang MPI x;
165d58bb7e5STianjia Zhang MPI y;
166d58bb7e5STianjia Zhang MPI z;
167d58bb7e5STianjia Zhang };
168d58bb7e5STianjia Zhang
169d58bb7e5STianjia Zhang typedef struct gcry_mpi_point *MPI_POINT;
170d58bb7e5STianjia Zhang
171d58bb7e5STianjia Zhang /* Models describing an elliptic curve */
172d58bb7e5STianjia Zhang enum gcry_mpi_ec_models {
173d58bb7e5STianjia Zhang /* The Short Weierstrass equation is
174d58bb7e5STianjia Zhang * y^2 = x^3 + ax + b
175d58bb7e5STianjia Zhang */
176d58bb7e5STianjia Zhang MPI_EC_WEIERSTRASS = 0,
177d58bb7e5STianjia Zhang /* The Montgomery equation is
178d58bb7e5STianjia Zhang * by^2 = x^3 + ax^2 + x
179d58bb7e5STianjia Zhang */
180d58bb7e5STianjia Zhang MPI_EC_MONTGOMERY,
181d58bb7e5STianjia Zhang /* The Twisted Edwards equation is
182d58bb7e5STianjia Zhang * ax^2 + y^2 = 1 + bx^2y^2
183d58bb7e5STianjia Zhang * Note that we use 'b' instead of the commonly used 'd'.
184d58bb7e5STianjia Zhang */
185d58bb7e5STianjia Zhang MPI_EC_EDWARDS
186d58bb7e5STianjia Zhang };
187d58bb7e5STianjia Zhang
188d58bb7e5STianjia Zhang /* Dialects used with elliptic curves */
189d58bb7e5STianjia Zhang enum ecc_dialects {
190d58bb7e5STianjia Zhang ECC_DIALECT_STANDARD = 0,
191d58bb7e5STianjia Zhang ECC_DIALECT_ED25519,
192d58bb7e5STianjia Zhang ECC_DIALECT_SAFECURVE
193d58bb7e5STianjia Zhang };
194d58bb7e5STianjia Zhang
195d58bb7e5STianjia Zhang /* This context is used with all our EC functions. */
196d58bb7e5STianjia Zhang struct mpi_ec_ctx {
197d58bb7e5STianjia Zhang enum gcry_mpi_ec_models model; /* The model describing this curve. */
198d58bb7e5STianjia Zhang enum ecc_dialects dialect; /* The ECC dialect used with the curve. */
199d58bb7e5STianjia Zhang int flags; /* Public key flags (not always used). */
200d58bb7e5STianjia Zhang unsigned int nbits; /* Number of bits. */
201d58bb7e5STianjia Zhang
202d58bb7e5STianjia Zhang /* Domain parameters. Note that they may not all be set and if set
203*478485f6SZhen Lei * the MPIs may be flagged as constant.
204d58bb7e5STianjia Zhang */
205d58bb7e5STianjia Zhang MPI p; /* Prime specifying the field GF(p). */
206d58bb7e5STianjia Zhang MPI a; /* First coefficient of the Weierstrass equation. */
207d58bb7e5STianjia Zhang MPI b; /* Second coefficient of the Weierstrass equation. */
208d58bb7e5STianjia Zhang MPI_POINT G; /* Base point (generator). */
209d58bb7e5STianjia Zhang MPI n; /* Order of G. */
210d58bb7e5STianjia Zhang unsigned int h; /* Cofactor. */
211d58bb7e5STianjia Zhang
212d58bb7e5STianjia Zhang /* The actual key. May not be set. */
213d58bb7e5STianjia Zhang MPI_POINT Q; /* Public key. */
214d58bb7e5STianjia Zhang MPI d; /* Private key. */
215d58bb7e5STianjia Zhang
216d58bb7e5STianjia Zhang const char *name; /* Name of the curve. */
217d58bb7e5STianjia Zhang
218d58bb7e5STianjia Zhang /* This structure is private to mpi/ec.c! */
219d58bb7e5STianjia Zhang struct {
220d58bb7e5STianjia Zhang struct {
221d58bb7e5STianjia Zhang unsigned int a_is_pminus3:1;
222d58bb7e5STianjia Zhang unsigned int two_inv_p:1;
223d58bb7e5STianjia Zhang } valid; /* Flags to help setting the helper vars below. */
224d58bb7e5STianjia Zhang
225d58bb7e5STianjia Zhang int a_is_pminus3; /* True if A = P - 3. */
226d58bb7e5STianjia Zhang
227d58bb7e5STianjia Zhang MPI two_inv_p;
228d58bb7e5STianjia Zhang
229d58bb7e5STianjia Zhang mpi_barrett_t p_barrett;
230d58bb7e5STianjia Zhang
231d58bb7e5STianjia Zhang /* Scratch variables. */
232d58bb7e5STianjia Zhang MPI scratch[11];
233d58bb7e5STianjia Zhang
234d58bb7e5STianjia Zhang /* Helper for fast reduction. */
235d58bb7e5STianjia Zhang /* int nist_nbits; /\* If this is a NIST curve, the # of bits. *\/ */
236d58bb7e5STianjia Zhang /* MPI s[10]; */
237d58bb7e5STianjia Zhang /* MPI c; */
238d58bb7e5STianjia Zhang } t;
239d58bb7e5STianjia Zhang
240d58bb7e5STianjia Zhang /* Curve specific computation routines for the field. */
241d58bb7e5STianjia Zhang void (*addm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx);
242d58bb7e5STianjia Zhang void (*subm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec);
243d58bb7e5STianjia Zhang void (*mulm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx);
244d58bb7e5STianjia Zhang void (*pow2)(MPI w, const MPI b, struct mpi_ec_ctx *ctx);
245d58bb7e5STianjia Zhang void (*mul2)(MPI w, MPI u, struct mpi_ec_ctx *ctx);
246d58bb7e5STianjia Zhang };
247d58bb7e5STianjia Zhang
248d58bb7e5STianjia Zhang void mpi_ec_init(struct mpi_ec_ctx *ctx, enum gcry_mpi_ec_models model,
249d58bb7e5STianjia Zhang enum ecc_dialects dialect,
250d58bb7e5STianjia Zhang int flags, MPI p, MPI a, MPI b);
251d58bb7e5STianjia Zhang void mpi_ec_deinit(struct mpi_ec_ctx *ctx);
252d58bb7e5STianjia Zhang MPI_POINT mpi_point_new(unsigned int nbits);
253d58bb7e5STianjia Zhang void mpi_point_release(MPI_POINT p);
254d58bb7e5STianjia Zhang void mpi_point_init(MPI_POINT p);
255d58bb7e5STianjia Zhang void mpi_point_free_parts(MPI_POINT p);
256d58bb7e5STianjia Zhang int mpi_ec_get_affine(MPI x, MPI y, MPI_POINT point, struct mpi_ec_ctx *ctx);
257d58bb7e5STianjia Zhang void mpi_ec_add_points(MPI_POINT result,
258d58bb7e5STianjia Zhang MPI_POINT p1, MPI_POINT p2,
259d58bb7e5STianjia Zhang struct mpi_ec_ctx *ctx);
260d58bb7e5STianjia Zhang void mpi_ec_mul_point(MPI_POINT result,
261d58bb7e5STianjia Zhang MPI scalar, MPI_POINT point,
262d58bb7e5STianjia Zhang struct mpi_ec_ctx *ctx);
263d58bb7e5STianjia Zhang int mpi_ec_curve_point(MPI_POINT point, struct mpi_ec_ctx *ctx);
264d58bb7e5STianjia Zhang
265d37e2969STadeusz Struk /* inline functions */
266d37e2969STadeusz Struk
267d37e2969STadeusz Struk /**
268d37e2969STadeusz Struk * mpi_get_size() - returns max size required to store the number
269d37e2969STadeusz Struk *
270*478485f6SZhen Lei * @a: A multi precision integer for which we want to allocate a buffer
271d37e2969STadeusz Struk *
272d37e2969STadeusz Struk * Return: size required to store the number
273d37e2969STadeusz Struk */
mpi_get_size(MPI a)274d37e2969STadeusz Struk static inline unsigned int mpi_get_size(MPI a)
275d37e2969STadeusz Struk {
276d37e2969STadeusz Struk return a->nlimbs * BYTES_PER_MPI_LIMB;
277d37e2969STadeusz Struk }
2785ce3e312SDmitry Kasatkin #endif /*G10_MPI_H */
279