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)(cc_ws_t ws, cczp_const_t zp, cc_unit *r, const cc_unit *s);
  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 int 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(cc_ws_t ws, cczp_const_t zp, cc_unit *r, const cc_unit *s2n);
 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 int cczp_modn(cczp_const_t zp, cc_unit *r, cc_size ns, const cc_unit *s);
 188
 189 /* Compute r = x * y mod cczp_prime(zp). Will write cczp_n(zp) units to r
 190    and reads cczp_n(zp) units units from both x and y. If r and x are not
 191    identical they must not overlap, The same holds for r and y.  Before
 192    calling this function either cczp_init(zp) must have been called or both
 193    CCZP_MOD_PRIME((cc_unit *)zp) and CCZP_RECIP((cc_unit *)zp) must be
 194    initialized some other way. */
 195 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4))
 196 void cczp_mul(cczp_const_t zp, cc_unit *t, const cc_unit *x, const cc_unit *y);
 197
 198 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4, 5))
 199 void cczp_mul_ws(cc_ws_t ws, cczp_const_t zp, cc_unit *t, const cc_unit *x, const cc_unit *y);
 200
 201 /* Compute r = x * x mod cczp_prime(zp). Will write cczp_n(zp) units to r
 202    and reads cczp_n(zp) units from x. If r and x are not identical they must
 203    not overlap. Before calling this function either cczp_init(zp) must have
 204    been called or both CCZP_MOD_PRIME((cc_unit *)zp) and
 205    CCZP_RECIP((cc_unit *)zp) must be initialized some other way. */
 206 CC_NONNULL_TU((1)) CC_NONNULL((2, 3))
 207 void cczp_sqr(cczp_const_t zp, cc_unit *r, const cc_unit *x);
 208
 209 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4))
 210 void cczp_sqr_ws(cc_ws_t ws, cczp_const_t zp, cc_unit *r, const cc_unit *x);
 211
 212 /* Compute r = x^(1/2) mod cczp_prime(zp). Will write cczp_n(zp) units to r
 213  and reads cczp_n(zp) units from x. If r and x are not identical they must
 214  not overlap. Before calling this function either cczp_init(zp) must have
 215  been called or both CCZP_MOD_PRIME((cc_unit *)zp) and
 216  CCZP_RECIP((cc_unit *)zp) must be initialized some other way.
 217  Only support prime = 3 mod 4 */
 218 CC_NONNULL_TU((1)) CC_NONNULL((2, 3))
 219 int cczp_sqrt(cczp_const_t zp, cc_unit *r, const cc_unit *x);
 220
 221 /* Compute r = m ^ e mod cczp_prime(zp), using Montgomery ladder.
 222    - writes cczp_n(zp) units to r
 223    - reads  cczp_n(zp) units units from m and e
 224    - if r and m are not identical they must not overlap.
 225    - r and e must not overlap nor be identical.
 226    - before calling this function either cczp_init(zp) must have been called
 227    or both CCZP_MOD_PRIME((cc_unit *)zp) and CCZP_RECIP((cc_unit *)zp) must
 228    be initialized some other way.
 229  */
 230 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4))
 231 int cczp_power(cczp_const_t zp, cc_unit *r, const cc_unit *m,
 232                const cc_unit *e);
 233
 234 /* Compute r = m ^ e mod cczp_prime(zp), using Square Square Multiply Always.
 235  - writes cczp_n(zp) units to r
 236  - reads  cczp_n(zp) units units from m and e
 237  - if r and m are not identical they must not overlap.
 238  - r and e must not overlap nor be identical.
 239  - before calling this function either cczp_init(zp) must have been called
 240  or both CCZP_MOD_PRIME((cc_unit *)zp) and CCZP_RECIP((cc_unit *)zp) must
 241  be initialized some other way.
 242
 243  Important: This function is intented to be constant time but is more likely
 244     to leak information due to memory cache. Only used with randomized input
 245  */
 246 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4))
 247 int cczp_power_ssma(cczp_const_t zp, cc_unit *r, const cc_unit *m,
 248                 const cc_unit *e);
 249
 250 int cczp_power_ssma_ws(cc_ws_t ws, cczp_const_t zp, cc_unit *r, const cc_unit *s, const cc_unit *e);
 251
 252 /* Compute r = m ^ e mod cczp_prime(zp). Will write cczp_n(zp) units to r and
 253  reads cczp_n(zp) units units from m.  Reads ebitlen bits from e.
 254  m must be <= to cczp_prime(zp).  If r and m are not identical they must not
 255  overlap. r and e must not overlap nor be identical.
 256  Before calling this function either cczp_init(zp) must have been called
 257  or both CCZP_MOD_PRIME((cc_unit *)zp) and CCZP_RECIP((cc_unit *)zp) must
 258  be initialized some other way. */
 259 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 5))
 260 int cczp_powern(cczp_const_t zp, cc_unit *r, const cc_unit *s,
 261                 size_t ebitlen, const cc_unit *e);
 262
 263 /* Compute r = x + y mod cczp_prime(zp). Will write cczp_n(zp) units to r and
 264    reads cczp_n(zp) units units from x and y. If r and x are not identical
 265    they must not overlap. Only cczp_n(zp) and cczp_prime(zp) need to be valid.
 266    Can be used with cczp_short_nof_n sized cc_unit array zp. */
 267 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4))
 268 void cczp_add(cczp_const_t zp, cc_unit *r, const cc_unit *x,
 269               const cc_unit *y);
 270
 271 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4, 5))
 272 void cczp_add_ws(cc_ws_t ws, cczp_const_t zp, cc_unit *r, const cc_unit *x,
 273                  const cc_unit *y);
 274
 275 /* Compute r = x - y mod cczp_prime(zp). Will write cczp_n(zp) units to r and
 276    reads cczp_n(zp) units units from x and y. If r and x are not identical
 277    they must not overlap. Only cczp_n(zp) and cczp_prime(zp) need to be valid.
 278    Can be used with cczp_short_nof_n sized cc_unit array zp. */
 279 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4))
 280 void cczp_sub(cczp_const_t zp, cc_unit *r, const cc_unit *x, const cc_unit *y);
 281
 282 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4, 5))
 283 void cczp_sub_ws(cc_ws_t ws, cczp_const_t zp, cc_unit *r, const cc_unit *x,
 284                  const cc_unit *y);
 285
 286 /* Compute r = x / 2 mod cczp_prime(zp). Will write cczp_n(zp) units to r and
 287    reads cczp_n(zp) units units from x. If r and x are not identical
 288    they must not overlap. Only cczp_n(zp) and cczp_prime(zp) need to be valid.
 289    Can be used with cczp_short_nof_n sized cc_unit array zp. */
 290 CC_NONNULL_TU((1)) CC_NONNULL((2, 3))
 291 void cczp_div2(cczp_const_t zp, cc_unit *r, const cc_unit *x);
 292
 293 /* Compute q = a_2n / cczp_prime(zd) (mod cczp_prime(zd)) . Will write cczp_n(zd)
 294    units to q and r. Will read 2 * cczp_n(zd) units units from a. If r and a
 295    are not identical they must not overlap. Before calling this function
 296    either cczp_init(zp) must have been called or both
 297    CCZP_MOD_PRIME((cc_unit *)zp) and CCZP_RECIP((cc_unit *)zp) must be
 298    initialized some other way. */
 299 CC_NONNULL_TU((1)) CC_NONNULL((2, 3, 4))
 300 void cczp_div(cczp_const_t zd, cc_unit *q, cc_unit *r, const cc_unit *a_2n);
 301
 302
 303 /*!
 304  @brief cczp_inv(zp, r, x) computes r = x^-1 (mod p) , where p=cczp_prime(zp).
 305  @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.
 306  @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().
 307  @param x input big integer
 308  @param r output big integer
 309  @return  0 if inverse exists and correctly computed.
 310  */
 311 CC_NONNULL_TU((1)) CC_NONNULL((2, 3))
 312
 313 int cczp_inv(cczp_const_t zp, cc_unit *r, const cc_unit *x);
 314
 315 /*!
 316  @brief cczp_inv_odd(zp, r, x) computes r = x^-1 (mod p) , where p=cczp_prime(zp) is an odd number.
 317  @discussion  r and x can overlap.
 318  @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.
 319  @param x input big integer
 320  @param r output big integer
 321  @return  0 if successful
 322  */
 323 CC_NONNULL_TU((1)) CC_NONNULL((2, 3))
 324 int cczp_inv_odd(cczp_const_t zp, cc_unit *r, const cc_unit *x);
 325
 326 /*!
 327  @brief cczp_inv_field(zp, r, x) computes r = x^-1 (mod p) , where p=cczp_prime(zp) is a prime number number.
 328  @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)
 329
 330  @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().
 331  @param x input big unteger
 332  @param r output big integer
 333  @return  0 if inverse exists and correctly computed.
 334  */
 335 CC_NONNULL_TU((1)) CC_NONNULL((2, 3))
 336 int cczp_inv_field(cczp_const_t zp, cc_unit *r, const cc_unit *x);
 337
 338 #endif /* _CORECRYPTO_CCZP_H_ */