EXTERNAL_HEADERS/corecrypto/cczp.h

   1 /*
   2  *  cczp.h
   3  *  corecrypto
   4  *
   5  *  Created on 11/16/2010
   6  *
   7  *  Copyright (c) 2010,2011,2012,2013,2014,2015 Apple Inc. All rights reserved.
   8  *
   9  */
  10
  11 #ifndef _CORECRYPTO_CCZP_H_
  12 #define _CORECRYPTO_CCZP_H_
  13
  14 #include <corecrypto/ccn.h>
  15 #include <corecrypto/ccrng.h>
  16
  17 /*
  18  Don't use cczp_hd struct directly, except in static tables such as eliptic curve parameter definitions.
  19
  20  Declare cczp objects using cczp_decl_n(). It allocates cc_unit arrays of the length returned by either cczp_nof_n() or cczp_short_nof_n().
  21 */
  22
  23 struct cczp;
  24 #if CORECRYPTO_USE_TRANSPARENT_UNION
  25
  26 typedef union {
  27     cc_unit *u;
  28     struct cczp *zp;
  29     //cczp_const_t czp; //for automatic type cast
  30     //struct cczp_prime *prime;
  31 } cczp_t __attribute__((transparent_union));
  32
  33 typedef union {
  34     const cc_unit *u;
  35     const struct cczp *zp;
  36     //const struct cczp_prime *prime;
  37     cczp_t _nczp;
  38 } cczp_const_t __attribute__((transparent_union));
  39
  40 #else
  41     typedef struct cczp* cczp_t;
  42     typedef const struct cczp* cczp_const_t;
  43 #endif
  44 typedef void (*ccmod_func_t)(cczp_const_t zp, cc_unit *r, const cc_unit *s, cc_ws_t ws);
  45
  46 // keep cczp_hd and cczp structures consistent
  47 // cczp_hd is typecasted to cczp to read EC curve params
  48 // options field is to specify Montgomery arithmetic, bit field, etc
  49 // make sure n is the first element see ccrsa_ctx_n macro
  50 #define __CCZP_HEADER_ELEMENTS_DEFINITIONS(pre) \
  51 cc_size pre ## n;\
  52 cc_unit pre ## options;\
  53 ccmod_func_t pre ## mod_prime;
  54
  55 #define __CCZP_ELEMENTS_DEFINITIONS(pre) \
  56 __CCZP_HEADER_ELEMENTS_DEFINITIONS(pre) \
  57 cc_unit pre ## ccn[];
  58
  59 //cczp_hd must be defined separetly without variable length array ccn[], because it is used in sructures such as ccdh_gp_decl_n
  60 struct cczp_hd{
  61     __CCZP_HEADER_ELEMENTS_DEFINITIONS()
  62 }  CC_ALIGNED(CCN_UNIT_SIZE);
  63
  64 struct cczp {
  65     __CCZP_ELEMENTS_DEFINITIONS()
  66 } CC_ALIGNED(CCN_UNIT_SIZE);
  67
  68
  69 /* Return the size of an cczp where each ccn is _size_ bytes. */
  70 #define cczp_size(_size_) (sizeof(struct cczp) + ccn_sizeof_n(1) + 2 * (_size_))
  71
  72 /* Return number of units that a struct cczp needs to be in units for a prime
  73    size of N units.  This is large enough for all operations.  */
  74 #define cczp_nof_n(_n_) (ccn_nof_size(sizeof(struct cczp)) + 1 + 2 * (_n_))
  75
  76 /* Return number of units that a struct cczp needs to be in units for a prime
  77    size of _n_ units.  The _short variant does not have room for CCZP_RECIP,
  78    so it can not be used with cczp_mod, cczp_mul, cczp_sqr. It can be used
  79    with cczp_add, cczp_sub, cczp_div2, cczp_mod_inv. */
  80 #define cczp_short_nof_n(_n_) (ccn_nof_size(sizeof(struct cczp)) + (_n_))
  81
  82 #define cczp_decl_n(_n_, _name_)  cc_ctx_decl(struct cczp, ccn_sizeof_n(cczp_nof_n(_n_)), _name_)
  83 #define cczp_short_decl_n(_n_, _name_) cc_ctx_decl(struct cczp_short, ccn_sizeof_n(cczp_short_nof_n(_n_)), _name_)
  84
  85 #define cczp_clear_n(_n_, _name_)  cc_clear(ccn_sizeof_n(cczp_nof_n(_n_)), _name_)
  86 #define cczp_short_clear_n(_n_, _name_)  cc_clear(ccn_sizeof_n(cczp_short_nof_n(_n_)), _name_)
  87
  88 #if CORECRYPTO_USE_TRANSPARENT_UNION
  89   #define CCZP_N(ZP) (((cczp_t)(ZP)).zp->n)
  90   #define CCZP_MOD(ZP) (((cczp_t)(ZP)).zp->mod_prime)
  91   #define CCZP_PRIME(ZP) (((cczp_t)(ZP)).zp->ccn)
  92   #define CCZP_RECIP(ZP) (((cczp_t)(ZP)).zp->ccn + cczp_n(ZP))
  93   #define CCZP_OPS(ZP) ((ZP).zp->options)
  94   #define CCZP_MOD_PRIME(ZP) CCZP_MOD(ZP)
  95
  96 CC_CONST CC_NONNULL_TU((1))
  97 static inline cc_size cczp_n(cczp_const_t zp) {
  98     return zp.zp->n;
  99 }
 100
 101 CC_CONST CC_NONNULL_TU((1))
 102 static inline cc_unit cczp_options(cczp_const_t zp) {
 103     return zp.zp->options;
 104 }
 105
 106 CC_CONST CC_NONNULL_TU((1))
 107 static inline ccmod_func_t cczp_mod_prime(cczp_const_t zp) {
 108     return zp.zp->mod_prime;
 109 }
 110
 111 CC_CONST CC_NONNULL_TU((1))
 112 static inline const cc_unit *cczp_prime(cczp_const_t zp) {
 113     return zp.zp->ccn;
 114 }
 115
 116 /* Return a pointer to the Reciprocal or Montgomery constant of zp, which is
 117  allocated cczp_n(zp) + 1 units long. */
 118 CC_CONST CC_NONNULL_TU((1))
 119
 120 static inline const cc_unit *cczp_recip(cczp_const_t zp) {
 121     return zp.zp->ccn + zp.zp->n;
 122 }
 123
 124 #else
 125   #define CCZP_N(ZP)     ((ZP)->n)
 126   #define CCZP_MOD(ZP)   ((ZP)->mod_prime)
 127   #define CCZP_MOD_PRIME(ZP) CCZP_MOD(ZP)
 128   #define CCZP_PRIME(ZP) ((ZP)->ccn)
 129   #define CCZP_RECIP(ZP) ((ZP)->ccn + CCZP_N(ZP))
 130   #define CCZP_OPS(ZP)   ((ZP)->options)
 131 CC_CONST CC_NONNULL_TU((1))
 132 static inline cc_size cczp_n(cczp_const_t zp) {
 133     return zp->n;
 134 }
 135
 136 CC_CONST CC_NONNULL_TU((1))
 137 static inline cc_unit cczp_options(cczp_const_t zp) {
 138     return zp->options;
 139 }
 140
 141 CC_CONST CC_NONNULL_TU((1))
 142 static inline ccmod_func_t cczp_mod_prime(cczp_const_t zp) {
 143     return zp->mod_prime;
 144 }
 145
 146 CC_CONST CC_NONNULL_TU((1))
 147 static inline const cc_unit *cczp_prime(cczp_const_t zp) {
 148     return zp->ccn;
 149 }
 150
 151 /* Return a pointer to the Reciprocal or Montgomery constant of zp, which is
 152  allocated cczp_n(zp) + 1 units long. */
 153 CC_CONST CC_NONNULL_TU((1))
 154
 155 static inline const cc_unit *cczp_recip(cczp_const_t zp) {
 156     return zp->ccn + zp->n;
 157 }
 158
 159 #endif
 160
 161
 162 CC_CONST CC_NONNULL_TU((1))
 163 CC_INLINE size_t cczp_bitlen(cczp_const_t zp) {
 164     return ccn_bitlen(cczp_n(zp), cczp_prime(zp));
 165 }
 166
 167
 168 /* Ensure both cczp_mod_prime(zp) and cczp_recip(zp) are valid. cczp_n and
 169    cczp_prime must have been previously initialized. */
 170 CC_NONNULL_TU((1))
 171 void cczp_init(cczp_t zp);
 172
 173 /* Compute r = s2n mod cczp_prime(zp). Will write cczp_n(zp)
 174  units to r and reads 2 * cczp_n(zp) units units from s2n. If r and s2n are not
 175  identical they must not overlap.  Before calling this function either
 176  cczp_init(zp) must have been called or both CCZP_MOD_PRIME((cc_unit *)zp)
 177  and CCZP_RECIP((cc_unit *)zp) must be initialized some other way. */
 178 CC_NONNULL_TU((1)) CC_NONNULL((2, 3))
 179 void cczp_mod(cczp_const_t zp, cc_unit *r, const cc_unit *s2n, cc_ws_t ws);
 180
 181 /* Compute r = sn mod cczp_prime(zp), Will write cczp_n(zp)
 182  units to r and reads sn units units from s. If r and s are not
 183  identical they must not overlap.  Before calling this function either
 184  cczp_init(zp) must have been called or both CCZP_MOD_PRIME((cc_unit *)zp)
 185  and CCZP_RECIP((cc_unit *)zp) must be initialized some other way. */
 186 CC_NONNULL_TU((1)) CC_NONNULL((2, 4))
 187
 188 int cczp_modn(cczp_const_t zp, cc_unit *r, cc_size ns, const cc_unit *s);
 189
 190 /* Compute r = x * y mod cczp_prime(zp). Will write cczp_n(zp) units to r
 191    and reads cczp_n(zp) units units from both x and y. If r and x are not
 192    identical they must not overlap, The same holds for r and y.  Before
 193    calling this function either cczp_init(zp) must have been called or both
 194    CCZP_MOD_PRIME((cc_unit *)zp) and CCZP_RECIP((cc_unit *)zp) must be
 195    initialized some other way. */
 196 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4))
 197 void cczp_mul(cczp_const_t zp, cc_unit *t, const cc_unit *x, const cc_unit *y);
 198
 199 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4, 5))
 200 void cczp_mul_ws(cczp_const_t zp, cc_unit *t, const cc_unit *x, const cc_unit *y, cc_ws_t ws);
 201
 202 /* Compute r = x * x mod cczp_prime(zp). Will write cczp_n(zp) units to r
 203    and reads cczp_n(zp) units from x. If r and x are not identical they must
 204    not overlap. Before calling this function either cczp_init(zp) must have
 205    been called or both CCZP_MOD_PRIME((cc_unit *)zp) and
 206    CCZP_RECIP((cc_unit *)zp) must be initialized some other way. */
 207 CC_NONNULL_TU((1)) CC_NONNULL((2, 3))
 208 void cczp_sqr(cczp_const_t zp, cc_unit *r, const cc_unit *x);
 209
 210 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4))
 211 void cczp_sqr_ws(cczp_const_t zp, cc_unit *r, const cc_unit *x, cc_ws_t ws);
 212
 213 /* Compute r = x^(1/2) mod cczp_prime(zp). Will write cczp_n(zp) units to r
 214  and reads cczp_n(zp) units from x. If r and x are not identical they must
 215  not overlap. Before calling this function either cczp_init(zp) must have
 216  been called or both CCZP_MOD_PRIME((cc_unit *)zp) and
 217  CCZP_RECIP((cc_unit *)zp) must be initialized some other way.
 218  Only support prime = 3 mod 4 */
 219 CC_NONNULL_TU((1)) CC_NONNULL((2, 3))
 220 int cczp_sqrt(cczp_const_t zp, cc_unit *r, const cc_unit *x);
 221
 222 /* Compute r = m ^ e mod cczp_prime(zp), using Montgomery ladder.
 223    - writes cczp_n(zp) units to r
 224    - reads  cczp_n(zp) units units from m and e
 225    - if r and m are not identical they must not overlap.
 226    - r and e must not overlap nor be identical.
 227    - before calling this function either cczp_init(zp) must have been called
 228    or both CCZP_MOD_PRIME((cc_unit *)zp) and CCZP_RECIP((cc_unit *)zp) must
 229    be initialized some other way.
 230  */
 231 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4))
 232 void cczp_power(cczp_const_t zp, cc_unit *r, const cc_unit *m,
 233                 const cc_unit *e);
 234
 235 /* Compute r = m ^ e mod cczp_prime(zp), using Square Square Multiply Always.
 236  - writes cczp_n(zp) units to r
 237  - reads  cczp_n(zp) units units from m and e
 238  - if r and m are not identical they must not overlap.
 239  - r and e must not overlap nor be identical.
 240  - before calling this function either cczp_init(zp) must have been called
 241  or both CCZP_MOD_PRIME((cc_unit *)zp) and CCZP_RECIP((cc_unit *)zp) must
 242  be initialized some other way.
 243
 244  Important: This function is intented to be constant time but is more likely
 245     to leak information due to memory cache. Only used with randomized input
 246  */
 247 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4))
 248 int cczp_power_ssma(cczp_const_t zp, cc_unit *r, const cc_unit *m,
 249                 const cc_unit *e);
 250
 251 int cczp_power_ssma_ws(cc_ws_t ws, cczp_const_t zp, cc_unit *r, const cc_unit *s, const cc_unit *e);
 252
 253 /* Compute r = m ^ e mod cczp_prime(zp). Will write cczp_n(zp) units to r and
 254  reads cczp_n(zp) units units from m.  Reads ebitlen bits from e.
 255  m must be <= to cczp_prime(zp).  If r and m are not identical they must not
 256  overlap. r and e must not overlap nor be identical.
 257  Before calling this function either cczp_init(zp) must have been called
 258  or both CCZP_MOD_PRIME((cc_unit *)zp) and CCZP_RECIP((cc_unit *)zp) must
 259  be initialized some other way. */
 260 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 5))
 261 void cczp_powern(cczp_const_t zp, cc_unit *r, const cc_unit *s,
 262                  size_t ebitlen, const cc_unit *e);
 263
 264 /* Compute r = x + y mod cczp_prime(zp). Will write cczp_n(zp) units to r and
 265    reads cczp_n(zp) units units from x and y. If r and x are not identical
 266    they must not overlap. Only cczp_n(zp) and cczp_prime(zp) need to be valid.
 267    Can be used with cczp_short_nof_n sized cc_unit array zp. */
 268 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4))
 269 void cczp_add(cczp_const_t zp, cc_unit *r, const cc_unit *x,
 270               const cc_unit *y);
 271
 272 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4, 5))
 273 void cczp_add_ws(cczp_const_t zp, cc_unit *r, const cc_unit *x,
 274                  const cc_unit *y, cc_ws_t ws);
 275
 276 /* Compute r = x - y mod cczp_prime(zp). Will write cczp_n(zp) units to r and
 277    reads cczp_n(zp) units units from x and y. If r and x are not identical
 278    they must not overlap. Only cczp_n(zp) and cczp_prime(zp) need to be valid.
 279    Can be used with cczp_short_nof_n sized cc_unit array zp. */
 280 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4))
 281 void cczp_sub(cczp_const_t zp, cc_unit *r, const cc_unit *x, const cc_unit *y);
 282
 283 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4, 5))
 284 void cczp_sub_ws(cczp_const_t zp, cc_unit *r, const cc_unit *x,
 285                  const cc_unit *y, cc_ws_t ws);
 286
 287 /* Compute r = x / 2 mod cczp_prime(zp). Will write cczp_n(zp) units to r and
 288    reads cczp_n(zp) units units from x. If r and x are not identical
 289    they must not overlap. Only cczp_n(zp) and cczp_prime(zp) need to be valid.
 290    Can be used with cczp_short_nof_n sized cc_unit array zp. */
 291 CC_NONNULL_TU((1)) CC_NONNULL((2, 3))
 292 void cczp_div2(cczp_const_t zp, cc_unit *r, const cc_unit *x);
 293
 294 /* Compute q = a_2n / cczp_prime(zd) (mod cczp_prime(zd)) . Will write cczp_n(zd)
 295    units to q and r. Will read 2 * cczp_n(zd) units units from a. If r and a
 296    are not identical they must not overlap. Before calling this function
 297    either cczp_init(zp) must have been called or both
 298    CCZP_MOD_PRIME((cc_unit *)zp) and CCZP_RECIP((cc_unit *)zp) must be
 299    initialized some other way. */
 300 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4))
 301 void cczp_div(cczp_const_t zd, cc_unit *q, cc_unit *r, const cc_unit *a_2n);
 302
 303
 304 /*!
 305  @brief cczp_inv(zp, r, x) computes r = x^-1 (mod p) , where p=cczp_prime(zp).
 306  @discussion It is a general function and works for any p. It validates the inputs. r and x can overlap. It writes n =cczp_n(zp) units to r, and read n units units from x and p. The output r is overwriten only if the inverse is correctly computed. This function is not constant time in absolute sense, but it does not have data dependent 'if' statements in the code.
 307  @param zp  The input zp. cczp_n(zp) and cczp_prime(zp) need to be valid. cczp_init(zp) need not to be called before invoking cczp_inv().
 308  @param x input big integer
 309  @param r output big integer
 310  @return  0 if inverse exists and correctly computed.
 311  */
 312 CC_NONNULL_TU((1)) CC_NONNULL((2, 3))
 313
 314 int cczp_inv(cczp_const_t zp, cc_unit *r, const cc_unit *x);
 315
 316 /*!
 317  @brief cczp_inv_odd(zp, r, x) computes r = x^-1 (mod p) , where p=cczp_prime(zp) is an odd number.
 318  @discussion  r and x can overlap.
 319  @param zp  The input zp. cczp_n(zp) and cczp_prime(zp) need to be valid. cczp_init(zp) need not to be called before invoking.
 320  @param x input big integer
 321  @param r output big integer
 322  @return  0 if successful
 323  */
 324 CC_NONNULL_TU((1)) CC_NONNULL((2, 3))
 325 int cczp_inv_odd(cczp_const_t zp, cc_unit *r, const cc_unit *x);
 326
 327 /*!
 328  @brief cczp_inv_field(zp, r, x) computes r = x^-1 (mod p) , where p=cczp_prime(zp) is a prime number number.
 329  @discussion r and x must NOT overlap. The excution time of the function is independent to the value of the input x. It works only if p is a field. That is, when p is a prime. It supports Montgomery and non-Montgomery form of zp. It leaks the value of the prime and should only be used be used for public (not secret) primes (ex. Elliptic Curves)
 330
 331  @param zp  The input zp. cczp_n(zp) and cczp_prime(zp) need to be valid. cczp_init(zp) need not to be called before invoking cczp_inv_field().
 332  @param x input big unteger
 333  @param r output big integer
 334  @return  0 if inverse exists and correctly computed.
 335  */
 336 CC_NONNULL_TU((1)) CC_NONNULL((2, 3))
 337 int cczp_inv_field(cczp_const_t zp, cc_unit *r, const cc_unit *x);
 338
 339 #endif /* _CORECRYPTO_CCZP_H_ */