include/linux/mpi.h

0001 /* SPDX-License-Identifier: GPL-2.0-or-later */
0002 /* mpi.h  -  Multi Precision Integers
0003  *  Copyright (C) 1994, 1996, 1998, 1999,
0004  *                    2000, 2001 Free Software Foundation, Inc.
0005  *
0006  * This file is part of GNUPG.
0007  *
0008  * Note: This code is heavily based on the GNU MP Library.
0009  *   Actually it's the same code with only minor changes in the
0010  *   way the data is stored; this is to support the abstraction
0011  *   of an optional secure memory allocation which may be used
0012  *   to avoid revealing of sensitive data due to paging etc.
0013  *   The GNU MP Library itself is published under the LGPL;
0014  *   however I decided to publish this code under the plain GPL.
0015  */
0016
0017 #ifndef G10_MPI_H
0018 #define G10_MPI_H
0019
0020 #include <linux/types.h>
0021 #include <linux/scatterlist.h>
0022
0023 #define BYTES_PER_MPI_LIMB  (BITS_PER_LONG / 8)
0024 #define BITS_PER_MPI_LIMB   BITS_PER_LONG
0025
0026 typedef unsigned long int mpi_limb_t;
0027 typedef signed long int mpi_limb_signed_t;
0028
0029 struct gcry_mpi {
0030     int alloced;        /* array size (# of allocated limbs) */
0031     int nlimbs;     /* number of valid limbs */
0032     int nbits;      /* the real number of valid bits (info only) */
0033     int sign;       /* indicates a negative number */
0034     unsigned flags;     /* bit 0: array must be allocated in secure memory space */
0035     /* bit 1: not used */
0036     /* bit 2: the limb is a pointer to some m_alloced data */
0037     mpi_limb_t *d;      /* array with the limbs */
0038 };
0039
0040 typedef struct gcry_mpi *MPI;
0041
0042 #define mpi_get_nlimbs(a)     ((a)->nlimbs)
0043 #define mpi_has_sign(a)       ((a)->sign)
0044
0045 /*-- mpiutil.c --*/
0046 MPI mpi_alloc(unsigned nlimbs);
0047 void mpi_clear(MPI a);
0048 void mpi_free(MPI a);
0049 int mpi_resize(MPI a, unsigned nlimbs);
0050
0051 static inline MPI mpi_new(unsigned int nbits)
0052 {
0053     return mpi_alloc((nbits + BITS_PER_MPI_LIMB - 1) / BITS_PER_MPI_LIMB);
0054 }
0055
0056 MPI mpi_copy(MPI a);
0057 MPI mpi_alloc_like(MPI a);
0058 void mpi_snatch(MPI w, MPI u);
0059 MPI mpi_set(MPI w, MPI u);
0060 MPI mpi_set_ui(MPI w, unsigned long u);
0061 MPI mpi_alloc_set_ui(unsigned long u);
0062 void mpi_swap_cond(MPI a, MPI b, unsigned long swap);
0063
0064 /* Constants used to return constant MPIs.  See mpi_init if you
0065  * want to add more constants.
0066  */
0067 #define MPI_NUMBER_OF_CONSTANTS 6
0068 enum gcry_mpi_constants {
0069     MPI_C_ZERO,
0070     MPI_C_ONE,
0071     MPI_C_TWO,
0072     MPI_C_THREE,
0073     MPI_C_FOUR,
0074     MPI_C_EIGHT
0075 };
0076
0077 MPI mpi_const(enum gcry_mpi_constants no);
0078
0079 /*-- mpicoder.c --*/
0080
0081 /* Different formats of external big integer representation. */
0082 enum gcry_mpi_format {
0083     GCRYMPI_FMT_NONE = 0,
0084     GCRYMPI_FMT_STD = 1,    /* Twos complement stored without length. */
0085     GCRYMPI_FMT_PGP = 2,    /* As used by OpenPGP (unsigned only). */
0086     GCRYMPI_FMT_SSH = 3,    /* As used by SSH (like STD but with length). */
0087     GCRYMPI_FMT_HEX = 4,    /* Hex format. */
0088     GCRYMPI_FMT_USG = 5,    /* Like STD but unsigned. */
0089     GCRYMPI_FMT_OPAQUE = 8  /* Opaque format (some functions only). */
0090 };
0091
0092 MPI mpi_read_raw_data(const void *xbuffer, size_t nbytes);
0093 MPI mpi_read_from_buffer(const void *buffer, unsigned *ret_nread);
0094 int mpi_fromstr(MPI val, const char *str);
0095 MPI mpi_scanval(const char *string);
0096 MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int len);
0097 void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign);
0098 int mpi_read_buffer(MPI a, uint8_t *buf, unsigned buf_len, unsigned *nbytes,
0099             int *sign);
0100 int mpi_write_to_sgl(MPI a, struct scatterlist *sg, unsigned nbytes,
0101              int *sign);
0102 int mpi_print(enum gcry_mpi_format format, unsigned char *buffer,
0103             size_t buflen, size_t *nwritten, MPI a);
0104
0105 /*-- mpi-mod.c --*/
0106 void mpi_mod(MPI rem, MPI dividend, MPI divisor);
0107
0108 /* Context used with Barrett reduction.  */
0109 struct barrett_ctx_s;
0110 typedef struct barrett_ctx_s *mpi_barrett_t;
0111
0112 mpi_barrett_t mpi_barrett_init(MPI m, int copy);
0113 void mpi_barrett_free(mpi_barrett_t ctx);
0114 void mpi_mod_barrett(MPI r, MPI x, mpi_barrett_t ctx);
0115 void mpi_mul_barrett(MPI w, MPI u, MPI v, mpi_barrett_t ctx);
0116
0117 /*-- mpi-pow.c --*/
0118 int mpi_powm(MPI res, MPI base, MPI exp, MPI mod);
0119
0120 /*-- mpi-cmp.c --*/
0121 int mpi_cmp_ui(MPI u, ulong v);
0122 int mpi_cmp(MPI u, MPI v);
0123 int mpi_cmpabs(MPI u, MPI v);
0124
0125 /*-- mpi-sub-ui.c --*/
0126 int mpi_sub_ui(MPI w, MPI u, unsigned long vval);
0127
0128 /*-- mpi-bit.c --*/
0129 void mpi_normalize(MPI a);
0130 unsigned mpi_get_nbits(MPI a);
0131 int mpi_test_bit(MPI a, unsigned int n);
0132 void mpi_set_bit(MPI a, unsigned int n);
0133 void mpi_set_highbit(MPI a, unsigned int n);
0134 void mpi_clear_highbit(MPI a, unsigned int n);
0135 void mpi_clear_bit(MPI a, unsigned int n);
0136 void mpi_rshift_limbs(MPI a, unsigned int count);
0137 void mpi_rshift(MPI x, MPI a, unsigned int n);
0138 void mpi_lshift_limbs(MPI a, unsigned int count);
0139 void mpi_lshift(MPI x, MPI a, unsigned int n);
0140
0141 /*-- mpi-add.c --*/
0142 void mpi_add_ui(MPI w, MPI u, unsigned long v);
0143 void mpi_add(MPI w, MPI u, MPI v);
0144 void mpi_sub(MPI w, MPI u, MPI v);
0145 void mpi_addm(MPI w, MPI u, MPI v, MPI m);
0146 void mpi_subm(MPI w, MPI u, MPI v, MPI m);
0147
0148 /*-- mpi-mul.c --*/
0149 void mpi_mul(MPI w, MPI u, MPI v);
0150 void mpi_mulm(MPI w, MPI u, MPI v, MPI m);
0151
0152 /*-- mpi-div.c --*/
0153 void mpi_tdiv_r(MPI rem, MPI num, MPI den);
0154 void mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor);
0155 void mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor);
0156
0157 /*-- mpi-inv.c --*/
0158 int mpi_invm(MPI x, MPI a, MPI n);
0159
0160 /*-- ec.c --*/
0161
0162 /* Object to represent a point in projective coordinates */
0163 struct gcry_mpi_point {
0164     MPI x;
0165     MPI y;
0166     MPI z;
0167 };
0168
0169 typedef struct gcry_mpi_point *MPI_POINT;
0170
0171 /* Models describing an elliptic curve */
0172 enum gcry_mpi_ec_models {
0173     /* The Short Weierstrass equation is
0174      *      y^2 = x^3 + ax + b
0175      */
0176     MPI_EC_WEIERSTRASS = 0,
0177     /* The Montgomery equation is
0178      *      by^2 = x^3 + ax^2 + x
0179      */
0180     MPI_EC_MONTGOMERY,
0181     /* The Twisted Edwards equation is
0182      *      ax^2 + y^2 = 1 + bx^2y^2
0183      * Note that we use 'b' instead of the commonly used 'd'.
0184      */
0185     MPI_EC_EDWARDS
0186 };
0187
0188 /* Dialects used with elliptic curves */
0189 enum ecc_dialects {
0190     ECC_DIALECT_STANDARD = 0,
0191     ECC_DIALECT_ED25519,
0192     ECC_DIALECT_SAFECURVE
0193 };
0194
0195 /* This context is used with all our EC functions. */
0196 struct mpi_ec_ctx {
0197     enum gcry_mpi_ec_models model; /* The model describing this curve. */
0198     enum ecc_dialects dialect;     /* The ECC dialect used with the curve. */
0199     int flags;                     /* Public key flags (not always used). */
0200     unsigned int nbits;            /* Number of bits.  */
0201
0202     /* Domain parameters.  Note that they may not all be set and if set
0203      * the MPIs may be flagged as constant.
0204      */
0205     MPI p;         /* Prime specifying the field GF(p).  */
0206     MPI a;         /* First coefficient of the Weierstrass equation.  */
0207     MPI b;         /* Second coefficient of the Weierstrass equation.  */
0208     MPI_POINT G;   /* Base point (generator).  */
0209     MPI n;         /* Order of G.  */
0210     unsigned int h;       /* Cofactor.  */
0211
0212     /* The actual key.  May not be set.  */
0213     MPI_POINT Q;   /* Public key.   */
0214     MPI d;         /* Private key.  */
0215
0216     const char *name;      /* Name of the curve.  */
0217
0218     /* This structure is private to mpi/ec.c! */
0219     struct {
0220         struct {
0221             unsigned int a_is_pminus3:1;
0222             unsigned int two_inv_p:1;
0223         } valid; /* Flags to help setting the helper vars below.  */
0224
0225         int a_is_pminus3;  /* True if A = P - 3. */
0226
0227         MPI two_inv_p;
0228
0229         mpi_barrett_t p_barrett;
0230
0231         /* Scratch variables.  */
0232         MPI scratch[11];
0233
0234         /* Helper for fast reduction.  */
0235         /*   int nist_nbits; /\* If this is a NIST curve, the # of bits. *\/ */
0236         /*   MPI s[10]; */
0237         /*   MPI c; */
0238     } t;
0239
0240     /* Curve specific computation routines for the field.  */
0241     void (*addm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx);
0242     void (*subm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec);
0243     void (*mulm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx);
0244     void (*pow2)(MPI w, const MPI b, struct mpi_ec_ctx *ctx);
0245     void (*mul2)(MPI w, MPI u, struct mpi_ec_ctx *ctx);
0246 };
0247
0248 void mpi_ec_init(struct mpi_ec_ctx *ctx, enum gcry_mpi_ec_models model,
0249             enum ecc_dialects dialect,
0250             int flags, MPI p, MPI a, MPI b);
0251 void mpi_ec_deinit(struct mpi_ec_ctx *ctx);
0252 MPI_POINT mpi_point_new(unsigned int nbits);
0253 void mpi_point_release(MPI_POINT p);
0254 void mpi_point_init(MPI_POINT p);
0255 void mpi_point_free_parts(MPI_POINT p);
0256 int mpi_ec_get_affine(MPI x, MPI y, MPI_POINT point, struct mpi_ec_ctx *ctx);
0257 void mpi_ec_add_points(MPI_POINT result,
0258             MPI_POINT p1, MPI_POINT p2,
0259             struct mpi_ec_ctx *ctx);
0260 void mpi_ec_mul_point(MPI_POINT result,
0261             MPI scalar, MPI_POINT point,
0262             struct mpi_ec_ctx *ctx);
0263 int mpi_ec_curve_point(MPI_POINT point, struct mpi_ec_ctx *ctx);
0264
0265 /* inline functions */
0266
0267 /**
0268  * mpi_get_size() - returns max size required to store the number
0269  *
0270  * @a:  A multi precision integer for which we want to allocate a buffer
0271  *
0272  * Return: size required to store the number
0273  */
0274 static inline unsigned int mpi_get_size(MPI a)
0275 {
0276     return a->nlimbs * BYTES_PER_MPI_LIMB;
0277 }
0278 #endif /*G10_MPI_H */