crypto/bn/bn_nist.c

   1 /*
   2  * Copyright 2002-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include "bn_lcl.h"
  11 #include "internal/cryptlib.h"
  12
  13 #define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2
  14 #define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2
  15 #define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2
  16 #define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2
  17 #define BN_NIST_521_TOP (521+BN_BITS2-1)/BN_BITS2
  18
  19 /* pre-computed tables are "carry-less" values of modulus*(i+1) */
  20 #if BN_BITS2 == 64
  21 static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
  22     {0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFFULL},
  23     {0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL},
  24     {0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFFFULL}
  25 };
  26
  27 static const BN_ULONG _nist_p_192_sqr[] = {
  28     0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000001ULL,
  29     0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL
  30 };
  31
  32 static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = {
  33     {0x0000000000000001ULL, 0xFFFFFFFF00000000ULL,
  34      0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL},
  35     {0x0000000000000002ULL, 0xFFFFFFFE00000000ULL,
  36      0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFFULL} /* this one is
  37                                                     * "carry-full" */
  38 };
  39
  40 static const BN_ULONG _nist_p_224_sqr[] = {
  41     0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
  42     0xFFFFFFFFFFFFFFFFULL, 0x0000000200000000ULL,
  43     0x0000000000000000ULL, 0xFFFFFFFFFFFFFFFEULL,
  44     0xFFFFFFFFFFFFFFFFULL
  45 };
  46
  47 static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = {
  48     {0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL,
  49      0x0000000000000000ULL, 0xFFFFFFFF00000001ULL},
  50     {0xFFFFFFFFFFFFFFFEULL, 0x00000001FFFFFFFFULL,
  51      0x0000000000000000ULL, 0xFFFFFFFE00000002ULL},
  52     {0xFFFFFFFFFFFFFFFDULL, 0x00000002FFFFFFFFULL,
  53      0x0000000000000000ULL, 0xFFFFFFFD00000003ULL},
  54     {0xFFFFFFFFFFFFFFFCULL, 0x00000003FFFFFFFFULL,
  55      0x0000000000000000ULL, 0xFFFFFFFC00000004ULL},
  56     {0xFFFFFFFFFFFFFFFBULL, 0x00000004FFFFFFFFULL,
  57      0x0000000000000000ULL, 0xFFFFFFFB00000005ULL},
  58 };
  59
  60 static const BN_ULONG _nist_p_256_sqr[] = {
  61     0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
  62     0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFEULL,
  63     0x00000001FFFFFFFEULL, 0x00000001FFFFFFFEULL,
  64     0xFFFFFFFE00000001ULL, 0xFFFFFFFE00000002ULL
  65 };
  66
  67 static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = {
  68     {0x00000000FFFFFFFFULL, 0xFFFFFFFF00000000ULL, 0xFFFFFFFFFFFFFFFEULL,
  69      0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
  70     {0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL,
  71      0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
  72     {0x00000002FFFFFFFDULL, 0xFFFFFFFD00000000ULL, 0xFFFFFFFFFFFFFFFCULL,
  73      0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
  74     {0x00000003FFFFFFFCULL, 0xFFFFFFFC00000000ULL, 0xFFFFFFFFFFFFFFFBULL,
  75      0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
  76     {0x00000004FFFFFFFBULL, 0xFFFFFFFB00000000ULL, 0xFFFFFFFFFFFFFFFAULL,
  77      0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
  78 };
  79
  80 static const BN_ULONG _nist_p_384_sqr[] = {
  81     0xFFFFFFFE00000001ULL, 0x0000000200000000ULL, 0xFFFFFFFE00000000ULL,
  82     0x0000000200000000ULL, 0x0000000000000001ULL, 0x0000000000000000ULL,
  83     0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL,
  84     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL
  85 };
  86
  87 static const BN_ULONG _nist_p_521[] =
  88     { 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
  89     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
  90     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
  91     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
  92     0x00000000000001FFULL
  93 };
  94
  95 static const BN_ULONG _nist_p_521_sqr[] = {
  96     0x0000000000000001ULL, 0x0000000000000000ULL, 0x0000000000000000ULL,
  97     0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL,
  98     0x0000000000000000ULL, 0x0000000000000000ULL, 0xFFFFFFFFFFFFFC00ULL,
  99     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
 100     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
 101     0xFFFFFFFFFFFFFFFFULL, 0x000000000003FFFFULL
 102 };
 103 #elif BN_BITS2 == 32
 104 static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
 105     {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 106     {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 107     {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
 108 };
 109
 110 static const BN_ULONG _nist_p_192_sqr[] = {
 111     0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, 0x00000000,
 112     0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
 113 };
 114
 115 static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = {
 116     {0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF,
 117      0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 118     {0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE,
 119      0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
 120 };
 121
 122 static const BN_ULONG _nist_p_224_sqr[] = {
 123     0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE,
 124     0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000002,
 125     0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF,
 126     0xFFFFFFFF, 0xFFFFFFFF
 127 };
 128
 129 static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = {
 130     {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000,
 131      0x00000000, 0x00000000, 0x00000001, 0xFFFFFFFF},
 132     {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001,
 133      0x00000000, 0x00000000, 0x00000002, 0xFFFFFFFE},
 134     {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000002,
 135      0x00000000, 0x00000000, 0x00000003, 0xFFFFFFFD},
 136     {0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000003,
 137      0x00000000, 0x00000000, 0x00000004, 0xFFFFFFFC},
 138     {0xFFFFFFFB, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000004,
 139      0x00000000, 0x00000000, 0x00000005, 0xFFFFFFFB},
 140 };
 141
 142 static const BN_ULONG _nist_p_256_sqr[] = {
 143     0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE,
 144     0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0x00000001,
 145     0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001,
 146     0x00000001, 0xFFFFFFFE, 0x00000002, 0xFFFFFFFE
 147 };
 148
 149 static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = {
 150     {0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF,
 151      0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 152     {0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF,
 153      0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 154     {0xFFFFFFFD, 0x00000002, 0x00000000, 0xFFFFFFFD, 0xFFFFFFFC, 0xFFFFFFFF,
 155      0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 156     {0xFFFFFFFC, 0x00000003, 0x00000000, 0xFFFFFFFC, 0xFFFFFFFB, 0xFFFFFFFF,
 157      0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 158     {0xFFFFFFFB, 0x00000004, 0x00000000, 0xFFFFFFFB, 0xFFFFFFFA, 0xFFFFFFFF,
 159      0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 160 };
 161
 162 static const BN_ULONG _nist_p_384_sqr[] = {
 163     0x00000001, 0xFFFFFFFE, 0x00000000, 0x00000002, 0x00000000, 0xFFFFFFFE,
 164     0x00000000, 0x00000002, 0x00000001, 0x00000000, 0x00000000, 0x00000000,
 165     0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF,
 166     0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
 167 };
 168
 169 static const BN_ULONG _nist_p_521[] = { 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
 170     0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
 171     0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
 172     0xFFFFFFFF, 0x000001FF
 173 };
 174
 175 static const BN_ULONG _nist_p_521_sqr[] = {
 176     0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
 177     0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
 178     0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFC00, 0xFFFFFFFF,
 179     0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
 180     0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
 181     0xFFFFFFFF, 0xFFFFFFFF, 0x0003FFFF
 182 };
 183 #else
 184 # error "unsupported BN_BITS2"
 185 #endif
 186
 187 static const BIGNUM _bignum_nist_p_192 = {
 188     (BN_ULONG *)_nist_p_192[0],
 189     BN_NIST_192_TOP,
 190     BN_NIST_192_TOP,
 191     0,
 192     BN_FLG_STATIC_DATA
 193 };
 194
 195 static const BIGNUM _bignum_nist_p_224 = {
 196     (BN_ULONG *)_nist_p_224[0],
 197     BN_NIST_224_TOP,
 198     BN_NIST_224_TOP,
 199     0,
 200     BN_FLG_STATIC_DATA
 201 };
 202
 203 static const BIGNUM _bignum_nist_p_256 = {
 204     (BN_ULONG *)_nist_p_256[0],
 205     BN_NIST_256_TOP,
 206     BN_NIST_256_TOP,
 207     0,
 208     BN_FLG_STATIC_DATA
 209 };
 210
 211 static const BIGNUM _bignum_nist_p_384 = {
 212     (BN_ULONG *)_nist_p_384[0],
 213     BN_NIST_384_TOP,
 214     BN_NIST_384_TOP,
 215     0,
 216     BN_FLG_STATIC_DATA
 217 };
 218
 219 static const BIGNUM _bignum_nist_p_521 = {
 220     (BN_ULONG *)_nist_p_521,
 221     BN_NIST_521_TOP,
 222     BN_NIST_521_TOP,
 223     0,
 224     BN_FLG_STATIC_DATA
 225 };
 226
 227 const BIGNUM *BN_get0_nist_prime_192(void)
 228 {
 229     return &_bignum_nist_p_192;
 230 }
 231
 232 const BIGNUM *BN_get0_nist_prime_224(void)
 233 {
 234     return &_bignum_nist_p_224;
 235 }
 236
 237 const BIGNUM *BN_get0_nist_prime_256(void)
 238 {
 239     return &_bignum_nist_p_256;
 240 }
 241
 242 const BIGNUM *BN_get0_nist_prime_384(void)
 243 {
 244     return &_bignum_nist_p_384;
 245 }
 246
 247 const BIGNUM *BN_get0_nist_prime_521(void)
 248 {
 249     return &_bignum_nist_p_521;
 250 }
 251
 252 static void nist_cp_bn_0(BN_ULONG *dst, const BN_ULONG *src, int top, int max)
 253 {
 254     int i;
 255
 256 #ifdef BN_DEBUG
 257     (void)ossl_assert(top <= max);
 258 #endif
 259     for (i = 0; i < top; i++)
 260         dst[i] = src[i];
 261     for (; i < max; i++)
 262         dst[i] = 0;
 263 }
 264
 265 static void nist_cp_bn(BN_ULONG *dst, const BN_ULONG *src, int top)
 266 {
 267     int i;
 268
 269     for (i = 0; i < top; i++)
 270         dst[i] = src[i];
 271 }
 272
 273 #if BN_BITS2 == 64
 274 # define bn_cp_64(to, n, from, m)        (to)[n] = (m>=0)?((from)[m]):0;
 275 # define bn_64_set_0(to, n)              (to)[n] = (BN_ULONG)0;
 276 /*
 277  * two following macros are implemented under assumption that they
 278  * are called in a sequence with *ascending* n, i.e. as they are...
 279  */
 280 # define bn_cp_32_naked(to, n, from, m)  (((n)&1)?(to[(n)/2]|=((m)&1)?(from[(m)/2]&BN_MASK2h):(from[(m)/2]<<32))\
 281                                                 :(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l)))
 282 # define bn_32_set_0(to, n)              (((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0));
 283 # define bn_cp_32(to,n,from,m)           ((m)>=0)?bn_cp_32_naked(to,n,from,m):bn_32_set_0(to,n)
 284 # if defined(L_ENDIAN)
 285 #  if defined(__arch64__)
 286 #   define NIST_INT64 long
 287 #  else
 288 #   define NIST_INT64 long long
 289 #  endif
 290 # endif
 291 #else
 292 # define bn_cp_64(to, n, from, m) \
 293         { \
 294         bn_cp_32(to, (n)*2, from, (m)*2); \
 295         bn_cp_32(to, (n)*2+1, from, (m)*2+1); \
 296         }
 297 # define bn_64_set_0(to, n) \
 298         { \
 299         bn_32_set_0(to, (n)*2); \
 300         bn_32_set_0(to, (n)*2+1); \
 301         }
 302 # define bn_cp_32(to, n, from, m)        (to)[n] = (m>=0)?((from)[m]):0;
 303 # define bn_32_set_0(to, n)              (to)[n] = (BN_ULONG)0;
 304 # if defined(_WIN32) && !defined(__GNUC__)
 305 #  define NIST_INT64 __int64
 306 # elif defined(BN_LLONG)
 307 #  define NIST_INT64 long long
 308 # endif
 309 #endif                          /* BN_BITS2 != 64 */
 310
 311 #define nist_set_192(to, from, a1, a2, a3) \
 312         { \
 313         bn_cp_64(to, 0, from, (a3) - 3) \
 314         bn_cp_64(to, 1, from, (a2) - 3) \
 315         bn_cp_64(to, 2, from, (a1) - 3) \
 316         }
 317
 318 int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
 319                     BN_CTX *ctx)
 320 {
 321     int top = a->top, i;
 322     int carry;
 323     register BN_ULONG *r_d, *a_d = a->d;
 324     union {
 325         BN_ULONG bn[BN_NIST_192_TOP];
 326         unsigned int ui[BN_NIST_192_TOP * sizeof(BN_ULONG) /
 327                         sizeof(unsigned int)];
 328     } buf;
 329     BN_ULONG c_d[BN_NIST_192_TOP], *res;
 330     PTR_SIZE_INT mask;
 331     static const BIGNUM _bignum_nist_p_192_sqr = {
 332         (BN_ULONG *)_nist_p_192_sqr,
 333         OSSL_NELEM(_nist_p_192_sqr),
 334         OSSL_NELEM(_nist_p_192_sqr),
 335         0, BN_FLG_STATIC_DATA
 336     };
 337
 338     field = &_bignum_nist_p_192; /* just to make sure */
 339
 340     if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_192_sqr) >= 0)
 341         return BN_nnmod(r, a, field, ctx);
 342
 343     i = BN_ucmp(field, a);
 344     if (i == 0) {
 345         BN_zero(r);
 346         return 1;
 347     } else if (i > 0)
 348         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
 349
 350     if (r != a) {
 351         if (!bn_wexpand(r, BN_NIST_192_TOP))
 352             return 0;
 353         r_d = r->d;
 354         nist_cp_bn(r_d, a_d, BN_NIST_192_TOP);
 355     } else
 356         r_d = a_d;
 357
 358     nist_cp_bn_0(buf.bn, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP,
 359                  BN_NIST_192_TOP);
 360
 361 #if defined(NIST_INT64)
 362     {
 363         NIST_INT64 acc;         /* accumulator */
 364         unsigned int *rp = (unsigned int *)r_d;
 365         const unsigned int *bp = (const unsigned int *)buf.ui;
 366
 367         acc = rp[0];
 368         acc += bp[3 * 2 - 6];
 369         acc += bp[5 * 2 - 6];
 370         rp[0] = (unsigned int)acc;
 371         acc >>= 32;
 372
 373         acc += rp[1];
 374         acc += bp[3 * 2 - 5];
 375         acc += bp[5 * 2 - 5];
 376         rp[1] = (unsigned int)acc;
 377         acc >>= 32;
 378
 379         acc += rp[2];
 380         acc += bp[3 * 2 - 6];
 381         acc += bp[4 * 2 - 6];
 382         acc += bp[5 * 2 - 6];
 383         rp[2] = (unsigned int)acc;
 384         acc >>= 32;
 385
 386         acc += rp[3];
 387         acc += bp[3 * 2 - 5];
 388         acc += bp[4 * 2 - 5];
 389         acc += bp[5 * 2 - 5];
 390         rp[3] = (unsigned int)acc;
 391         acc >>= 32;
 392
 393         acc += rp[4];
 394         acc += bp[4 * 2 - 6];
 395         acc += bp[5 * 2 - 6];
 396         rp[4] = (unsigned int)acc;
 397         acc >>= 32;
 398
 399         acc += rp[5];
 400         acc += bp[4 * 2 - 5];
 401         acc += bp[5 * 2 - 5];
 402         rp[5] = (unsigned int)acc;
 403
 404         carry = (int)(acc >> 32);
 405     }
 406 #else
 407     {
 408         BN_ULONG t_d[BN_NIST_192_TOP];
 409
 410         nist_set_192(t_d, buf.bn, 0, 3, 3);
 411         carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
 412         nist_set_192(t_d, buf.bn, 4, 4, 0);
 413         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
 414         nist_set_192(t_d, buf.bn, 5, 5, 5)
 415             carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
 416     }
 417 #endif
 418     if (carry > 0)
 419         carry =
 420             (int)bn_sub_words(r_d, r_d, _nist_p_192[carry - 1],
 421                               BN_NIST_192_TOP);
 422     else
 423         carry = 1;
 424
 425     /*
 426      * we need 'if (carry==0 || result>=modulus) result-=modulus;'
 427      * as comparison implies subtraction, we can write
 428      * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;'
 429      * this is what happens below, but without explicit if:-) a.
 430      */
 431     mask =
 432         0 - (PTR_SIZE_INT) bn_sub_words(c_d, r_d, _nist_p_192[0],
 433                                         BN_NIST_192_TOP);
 434     mask &= 0 - (PTR_SIZE_INT) carry;
 435     res = c_d;
 436     res = (BN_ULONG *)
 437         (((PTR_SIZE_INT) res & ~mask) | ((PTR_SIZE_INT) r_d & mask));
 438     nist_cp_bn(r_d, res, BN_NIST_192_TOP);
 439     r->top = BN_NIST_192_TOP;
 440     bn_correct_top(r);
 441
 442     return 1;
 443 }
 444
 445 typedef BN_ULONG (*bn_addsub_f) (BN_ULONG *, const BN_ULONG *,
 446                                  const BN_ULONG *, int);
 447
 448 #define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \
 449         { \
 450         bn_cp_32(to, 0, from, (a7) - 7) \
 451         bn_cp_32(to, 1, from, (a6) - 7) \
 452         bn_cp_32(to, 2, from, (a5) - 7) \
 453         bn_cp_32(to, 3, from, (a4) - 7) \
 454         bn_cp_32(to, 4, from, (a3) - 7) \
 455         bn_cp_32(to, 5, from, (a2) - 7) \
 456         bn_cp_32(to, 6, from, (a1) - 7) \
 457         }
 458
 459 int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
 460                     BN_CTX *ctx)
 461 {
 462     int top = a->top, i;
 463     int carry;
 464     BN_ULONG *r_d, *a_d = a->d;
 465     union {
 466         BN_ULONG bn[BN_NIST_224_TOP];
 467         unsigned int ui[BN_NIST_224_TOP * sizeof(BN_ULONG) /
 468                         sizeof(unsigned int)];
 469     } buf;
 470     BN_ULONG c_d[BN_NIST_224_TOP], *res;
 471     PTR_SIZE_INT mask;
 472     union {
 473         bn_addsub_f f;
 474         PTR_SIZE_INT p;
 475     } u;
 476     static const BIGNUM _bignum_nist_p_224_sqr = {
 477         (BN_ULONG *)_nist_p_224_sqr,
 478         OSSL_NELEM(_nist_p_224_sqr),
 479         OSSL_NELEM(_nist_p_224_sqr),
 480         0, BN_FLG_STATIC_DATA
 481     };
 482
 483     field = &_bignum_nist_p_224; /* just to make sure */
 484
 485     if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_224_sqr) >= 0)
 486         return BN_nnmod(r, a, field, ctx);
 487
 488     i = BN_ucmp(field, a);
 489     if (i == 0) {
 490         BN_zero(r);
 491         return 1;
 492     } else if (i > 0)
 493         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
 494
 495     if (r != a) {
 496         if (!bn_wexpand(r, BN_NIST_224_TOP))
 497             return 0;
 498         r_d = r->d;
 499         nist_cp_bn(r_d, a_d, BN_NIST_224_TOP);
 500     } else
 501         r_d = a_d;
 502
 503 #if BN_BITS2==64
 504     /* copy upper 256 bits of 448 bit number ... */
 505     nist_cp_bn_0(c_d, a_d + (BN_NIST_224_TOP - 1),
 506                  top - (BN_NIST_224_TOP - 1), BN_NIST_224_TOP);
 507     /* ... and right shift by 32 to obtain upper 224 bits */
 508     nist_set_224(buf.bn, c_d, 14, 13, 12, 11, 10, 9, 8);
 509     /* truncate lower part to 224 bits too */
 510     r_d[BN_NIST_224_TOP - 1] &= BN_MASK2l;
 511 #else
 512     nist_cp_bn_0(buf.bn, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP,
 513                  BN_NIST_224_TOP);
 514 #endif
 515
 516 #if defined(NIST_INT64) && BN_BITS2!=64
 517     {
 518         NIST_INT64 acc;         /* accumulator */
 519         unsigned int *rp = (unsigned int *)r_d;
 520         const unsigned int *bp = (const unsigned int *)buf.ui;
 521
 522         acc = rp[0];
 523         acc -= bp[7 - 7];
 524         acc -= bp[11 - 7];
 525         rp[0] = (unsigned int)acc;
 526         acc >>= 32;
 527
 528         acc += rp[1];
 529         acc -= bp[8 - 7];
 530         acc -= bp[12 - 7];
 531         rp[1] = (unsigned int)acc;
 532         acc >>= 32;
 533
 534         acc += rp[2];
 535         acc -= bp[9 - 7];
 536         acc -= bp[13 - 7];
 537         rp[2] = (unsigned int)acc;
 538         acc >>= 32;
 539
 540         acc += rp[3];
 541         acc += bp[7 - 7];
 542         acc += bp[11 - 7];
 543         acc -= bp[10 - 7];
 544         rp[3] = (unsigned int)acc;
 545         acc >>= 32;
 546
 547         acc += rp[4];
 548         acc += bp[8 - 7];
 549         acc += bp[12 - 7];
 550         acc -= bp[11 - 7];
 551         rp[4] = (unsigned int)acc;
 552         acc >>= 32;
 553
 554         acc += rp[5];
 555         acc += bp[9 - 7];
 556         acc += bp[13 - 7];
 557         acc -= bp[12 - 7];
 558         rp[5] = (unsigned int)acc;
 559         acc >>= 32;
 560
 561         acc += rp[6];
 562         acc += bp[10 - 7];
 563         acc -= bp[13 - 7];
 564         rp[6] = (unsigned int)acc;
 565
 566         carry = (int)(acc >> 32);
 567 # if BN_BITS2==64
 568         rp[7] = carry;
 569 # endif
 570     }
 571 #else
 572     {
 573         BN_ULONG t_d[BN_NIST_224_TOP];
 574
 575         nist_set_224(t_d, buf.bn, 10, 9, 8, 7, 0, 0, 0);
 576         carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
 577         nist_set_224(t_d, buf.bn, 0, 13, 12, 11, 0, 0, 0);
 578         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
 579         nist_set_224(t_d, buf.bn, 13, 12, 11, 10, 9, 8, 7);
 580         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
 581         nist_set_224(t_d, buf.bn, 0, 0, 0, 0, 13, 12, 11);
 582         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
 583
 584 # if BN_BITS2==64
 585         carry = (int)(r_d[BN_NIST_224_TOP - 1] >> 32);
 586 # endif
 587     }
 588 #endif
 589     u.f = bn_sub_words;
 590     if (carry > 0) {
 591         carry =
 592             (int)bn_sub_words(r_d, r_d, _nist_p_224[carry - 1],
 593                               BN_NIST_224_TOP);
 594 #if BN_BITS2==64
 595         carry = (int)(~(r_d[BN_NIST_224_TOP - 1] >> 32)) & 1;
 596 #endif
 597     } else if (carry < 0) {
 598         /*
 599          * it's a bit more complicated logic in this case. if bn_add_words
 600          * yields no carry, then result has to be adjusted by unconditionally
 601          * *adding* the modulus. but if it does, then result has to be
 602          * compared to the modulus and conditionally adjusted by
 603          * *subtracting* the latter.
 604          */
 605         carry =
 606             (int)bn_add_words(r_d, r_d, _nist_p_224[-carry - 1],
 607                               BN_NIST_224_TOP);
 608         mask = 0 - (PTR_SIZE_INT) carry;
 609         u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
 610             ((PTR_SIZE_INT) bn_add_words & ~mask);
 611     } else
 612         carry = 1;
 613
 614     /* otherwise it's effectively same as in BN_nist_mod_192... */
 615     mask =
 616         0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_224[0], BN_NIST_224_TOP);
 617     mask &= 0 - (PTR_SIZE_INT) carry;
 618     res = c_d;
 619     res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
 620                        ((PTR_SIZE_INT) r_d & mask));
 621     nist_cp_bn(r_d, res, BN_NIST_224_TOP);
 622     r->top = BN_NIST_224_TOP;
 623     bn_correct_top(r);
 624
 625     return 1;
 626 }
 627
 628 #define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \
 629         { \
 630         bn_cp_32(to, 0, from, (a8) - 8) \
 631         bn_cp_32(to, 1, from, (a7) - 8) \
 632         bn_cp_32(to, 2, from, (a6) - 8) \
 633         bn_cp_32(to, 3, from, (a5) - 8) \
 634         bn_cp_32(to, 4, from, (a4) - 8) \
 635         bn_cp_32(to, 5, from, (a3) - 8) \
 636         bn_cp_32(to, 6, from, (a2) - 8) \
 637         bn_cp_32(to, 7, from, (a1) - 8) \
 638         }
 639
 640 int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
 641                     BN_CTX *ctx)
 642 {
 643     int i, top = a->top;
 644     int carry = 0;
 645     register BN_ULONG *a_d = a->d, *r_d;
 646     union {
 647         BN_ULONG bn[BN_NIST_256_TOP];
 648         unsigned int ui[BN_NIST_256_TOP * sizeof(BN_ULONG) /
 649                         sizeof(unsigned int)];
 650     } buf;
 651     BN_ULONG c_d[BN_NIST_256_TOP], *res;
 652     PTR_SIZE_INT mask;
 653     union {
 654         bn_addsub_f f;
 655         PTR_SIZE_INT p;
 656     } u;
 657     static const BIGNUM _bignum_nist_p_256_sqr = {
 658         (BN_ULONG *)_nist_p_256_sqr,
 659         OSSL_NELEM(_nist_p_256_sqr),
 660         OSSL_NELEM(_nist_p_256_sqr),
 661         0, BN_FLG_STATIC_DATA
 662     };
 663
 664     field = &_bignum_nist_p_256; /* just to make sure */
 665
 666     if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_256_sqr) >= 0)
 667         return BN_nnmod(r, a, field, ctx);
 668
 669     i = BN_ucmp(field, a);
 670     if (i == 0) {
 671         BN_zero(r);
 672         return 1;
 673     } else if (i > 0)
 674         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
 675
 676     if (r != a) {
 677         if (!bn_wexpand(r, BN_NIST_256_TOP))
 678             return 0;
 679         r_d = r->d;
 680         nist_cp_bn(r_d, a_d, BN_NIST_256_TOP);
 681     } else
 682         r_d = a_d;
 683
 684     nist_cp_bn_0(buf.bn, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP,
 685                  BN_NIST_256_TOP);
 686
 687 #if defined(NIST_INT64)
 688     {
 689         NIST_INT64 acc;         /* accumulator */
 690         unsigned int *rp = (unsigned int *)r_d;
 691         const unsigned int *bp = (const unsigned int *)buf.ui;
 692
 693         acc = rp[0];
 694         acc += bp[8 - 8];
 695         acc += bp[9 - 8];
 696         acc -= bp[11 - 8];
 697         acc -= bp[12 - 8];
 698         acc -= bp[13 - 8];
 699         acc -= bp[14 - 8];
 700         rp[0] = (unsigned int)acc;
 701         acc >>= 32;
 702
 703         acc += rp[1];
 704         acc += bp[9 - 8];
 705         acc += bp[10 - 8];
 706         acc -= bp[12 - 8];
 707         acc -= bp[13 - 8];
 708         acc -= bp[14 - 8];
 709         acc -= bp[15 - 8];
 710         rp[1] = (unsigned int)acc;
 711         acc >>= 32;
 712
 713         acc += rp[2];
 714         acc += bp[10 - 8];
 715         acc += bp[11 - 8];
 716         acc -= bp[13 - 8];
 717         acc -= bp[14 - 8];
 718         acc -= bp[15 - 8];
 719         rp[2] = (unsigned int)acc;
 720         acc >>= 32;
 721
 722         acc += rp[3];
 723         acc += bp[11 - 8];
 724         acc += bp[11 - 8];
 725         acc += bp[12 - 8];
 726         acc += bp[12 - 8];
 727         acc += bp[13 - 8];
 728         acc -= bp[15 - 8];
 729         acc -= bp[8 - 8];
 730         acc -= bp[9 - 8];
 731         rp[3] = (unsigned int)acc;
 732         acc >>= 32;
 733
 734         acc += rp[4];
 735         acc += bp[12 - 8];
 736         acc += bp[12 - 8];
 737         acc += bp[13 - 8];
 738         acc += bp[13 - 8];
 739         acc += bp[14 - 8];
 740         acc -= bp[9 - 8];
 741         acc -= bp[10 - 8];
 742         rp[4] = (unsigned int)acc;
 743         acc >>= 32;
 744
 745         acc += rp[5];
 746         acc += bp[13 - 8];
 747         acc += bp[13 - 8];
 748         acc += bp[14 - 8];
 749         acc += bp[14 - 8];
 750         acc += bp[15 - 8];
 751         acc -= bp[10 - 8];
 752         acc -= bp[11 - 8];
 753         rp[5] = (unsigned int)acc;
 754         acc >>= 32;
 755
 756         acc += rp[6];
 757         acc += bp[14 - 8];
 758         acc += bp[14 - 8];
 759         acc += bp[15 - 8];
 760         acc += bp[15 - 8];
 761         acc += bp[14 - 8];
 762         acc += bp[13 - 8];
 763         acc -= bp[8 - 8];
 764         acc -= bp[9 - 8];
 765         rp[6] = (unsigned int)acc;
 766         acc >>= 32;
 767
 768         acc += rp[7];
 769         acc += bp[15 - 8];
 770         acc += bp[15 - 8];
 771         acc += bp[15 - 8];
 772         acc += bp[8 - 8];
 773         acc -= bp[10 - 8];
 774         acc -= bp[11 - 8];
 775         acc -= bp[12 - 8];
 776         acc -= bp[13 - 8];
 777         rp[7] = (unsigned int)acc;
 778
 779         carry = (int)(acc >> 32);
 780     }
 781 #else
 782     {
 783         BN_ULONG t_d[BN_NIST_256_TOP];
 784
 785         /*
 786          * S1
 787          */
 788         nist_set_256(t_d, buf.bn, 15, 14, 13, 12, 11, 0, 0, 0);
 789         /*
 790          * S2
 791          */
 792         nist_set_256(c_d, buf.bn, 0, 15, 14, 13, 12, 0, 0, 0);
 793         carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP);
 794         /* left shift */
 795         {
 796             register BN_ULONG *ap, t, c;
 797             ap = t_d;
 798             c = 0;
 799             for (i = BN_NIST_256_TOP; i != 0; --i) {
 800                 t = *ap;
 801                 *(ap++) = ((t << 1) | c) & BN_MASK2;
 802                 c = (t & BN_TBIT) ? 1 : 0;
 803             }
 804             carry <<= 1;
 805             carry |= c;
 806         }
 807         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
 808         /*
 809          * S3
 810          */
 811         nist_set_256(t_d, buf.bn, 15, 14, 0, 0, 0, 10, 9, 8);
 812         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
 813         /*
 814          * S4
 815          */
 816         nist_set_256(t_d, buf.bn, 8, 13, 15, 14, 13, 11, 10, 9);
 817         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
 818         /*
 819          * D1
 820          */
 821         nist_set_256(t_d, buf.bn, 10, 8, 0, 0, 0, 13, 12, 11);
 822         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
 823         /*
 824          * D2
 825          */
 826         nist_set_256(t_d, buf.bn, 11, 9, 0, 0, 15, 14, 13, 12);
 827         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
 828         /*
 829          * D3
 830          */
 831         nist_set_256(t_d, buf.bn, 12, 0, 10, 9, 8, 15, 14, 13);
 832         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
 833         /*
 834          * D4
 835          */
 836         nist_set_256(t_d, buf.bn, 13, 0, 11, 10, 9, 0, 15, 14);
 837         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
 838
 839     }
 840 #endif
 841     /* see BN_nist_mod_224 for explanation */
 842     u.f = bn_sub_words;
 843     if (carry > 0)
 844         carry =
 845             (int)bn_sub_words(r_d, r_d, _nist_p_256[carry - 1],
 846                               BN_NIST_256_TOP);
 847     else if (carry < 0) {
 848         carry =
 849             (int)bn_add_words(r_d, r_d, _nist_p_256[-carry - 1],
 850                               BN_NIST_256_TOP);
 851         mask = 0 - (PTR_SIZE_INT) carry;
 852         u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
 853             ((PTR_SIZE_INT) bn_add_words & ~mask);
 854     } else
 855         carry = 1;
 856
 857     mask =
 858         0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_256[0], BN_NIST_256_TOP);
 859     mask &= 0 - (PTR_SIZE_INT) carry;
 860     res = c_d;
 861     res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
 862                        ((PTR_SIZE_INT) r_d & mask));
 863     nist_cp_bn(r_d, res, BN_NIST_256_TOP);
 864     r->top = BN_NIST_256_TOP;
 865     bn_correct_top(r);
 866
 867     return 1;
 868 }
 869
 870 #define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \
 871         { \
 872         bn_cp_32(to, 0, from,  (a12) - 12) \
 873         bn_cp_32(to, 1, from,  (a11) - 12) \
 874         bn_cp_32(to, 2, from,  (a10) - 12) \
 875         bn_cp_32(to, 3, from,  (a9) - 12)  \
 876         bn_cp_32(to, 4, from,  (a8) - 12)  \
 877         bn_cp_32(to, 5, from,  (a7) - 12)  \
 878         bn_cp_32(to, 6, from,  (a6) - 12)  \
 879         bn_cp_32(to, 7, from,  (a5) - 12)  \
 880         bn_cp_32(to, 8, from,  (a4) - 12)  \
 881         bn_cp_32(to, 9, from,  (a3) - 12)  \
 882         bn_cp_32(to, 10, from, (a2) - 12)  \
 883         bn_cp_32(to, 11, from, (a1) - 12)  \
 884         }
 885
 886 int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
 887                     BN_CTX *ctx)
 888 {
 889     int i, top = a->top;
 890     int carry = 0;
 891     register BN_ULONG *r_d, *a_d = a->d;
 892     union {
 893         BN_ULONG bn[BN_NIST_384_TOP];
 894         unsigned int ui[BN_NIST_384_TOP * sizeof(BN_ULONG) /
 895                         sizeof(unsigned int)];
 896     } buf;
 897     BN_ULONG c_d[BN_NIST_384_TOP], *res;
 898     PTR_SIZE_INT mask;
 899     union {
 900         bn_addsub_f f;
 901         PTR_SIZE_INT p;
 902     } u;
 903     static const BIGNUM _bignum_nist_p_384_sqr = {
 904         (BN_ULONG *)_nist_p_384_sqr,
 905         OSSL_NELEM(_nist_p_384_sqr),
 906         OSSL_NELEM(_nist_p_384_sqr),
 907         0, BN_FLG_STATIC_DATA
 908     };
 909
 910     field = &_bignum_nist_p_384; /* just to make sure */
 911
 912     if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_384_sqr) >= 0)
 913         return BN_nnmod(r, a, field, ctx);
 914
 915     i = BN_ucmp(field, a);
 916     if (i == 0) {
 917         BN_zero(r);
 918         return 1;
 919     } else if (i > 0)
 920         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
 921
 922     if (r != a) {
 923         if (!bn_wexpand(r, BN_NIST_384_TOP))
 924             return 0;
 925         r_d = r->d;
 926         nist_cp_bn(r_d, a_d, BN_NIST_384_TOP);
 927     } else
 928         r_d = a_d;
 929
 930     nist_cp_bn_0(buf.bn, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP,
 931                  BN_NIST_384_TOP);
 932
 933 #if defined(NIST_INT64)
 934     {
 935         NIST_INT64 acc;         /* accumulator */
 936         unsigned int *rp = (unsigned int *)r_d;
 937         const unsigned int *bp = (const unsigned int *)buf.ui;
 938
 939         acc = rp[0];
 940         acc += bp[12 - 12];
 941         acc += bp[21 - 12];
 942         acc += bp[20 - 12];
 943         acc -= bp[23 - 12];
 944         rp[0] = (unsigned int)acc;
 945         acc >>= 32;
 946
 947         acc += rp[1];
 948         acc += bp[13 - 12];
 949         acc += bp[22 - 12];
 950         acc += bp[23 - 12];
 951         acc -= bp[12 - 12];
 952         acc -= bp[20 - 12];
 953         rp[1] = (unsigned int)acc;
 954         acc >>= 32;
 955
 956         acc += rp[2];
 957         acc += bp[14 - 12];
 958         acc += bp[23 - 12];
 959         acc -= bp[13 - 12];
 960         acc -= bp[21 - 12];
 961         rp[2] = (unsigned int)acc;
 962         acc >>= 32;
 963
 964         acc += rp[3];
 965         acc += bp[15 - 12];
 966         acc += bp[12 - 12];
 967         acc += bp[20 - 12];
 968         acc += bp[21 - 12];
 969         acc -= bp[14 - 12];
 970         acc -= bp[22 - 12];
 971         acc -= bp[23 - 12];
 972         rp[3] = (unsigned int)acc;
 973         acc >>= 32;
 974
 975         acc += rp[4];
 976         acc += bp[21 - 12];
 977         acc += bp[21 - 12];
 978         acc += bp[16 - 12];
 979         acc += bp[13 - 12];
 980         acc += bp[12 - 12];
 981         acc += bp[20 - 12];
 982         acc += bp[22 - 12];
 983         acc -= bp[15 - 12];
 984         acc -= bp[23 - 12];
 985         acc -= bp[23 - 12];
 986         rp[4] = (unsigned int)acc;
 987         acc >>= 32;
 988
 989         acc += rp[5];
 990         acc += bp[22 - 12];
 991         acc += bp[22 - 12];
 992         acc += bp[17 - 12];
 993         acc += bp[14 - 12];
 994         acc += bp[13 - 12];
 995         acc += bp[21 - 12];
 996         acc += bp[23 - 12];
 997         acc -= bp[16 - 12];
 998         rp[5] = (unsigned int)acc;
 999         acc >>= 32;
1000
1001         acc += rp[6];
1002         acc += bp[23 - 12];
1003         acc += bp[23 - 12];
1004         acc += bp[18 - 12];
1005         acc += bp[15 - 12];
1006         acc += bp[14 - 12];
1007         acc += bp[22 - 12];
1008         acc -= bp[17 - 12];
1009         rp[6] = (unsigned int)acc;
1010         acc >>= 32;
1011
1012         acc += rp[7];
1013         acc += bp[19 - 12];
1014         acc += bp[16 - 12];
1015         acc += bp[15 - 12];
1016         acc += bp[23 - 12];
1017         acc -= bp[18 - 12];
1018         rp[7] = (unsigned int)acc;
1019         acc >>= 32;
1020
1021         acc += rp[8];
1022         acc += bp[20 - 12];
1023         acc += bp[17 - 12];
1024         acc += bp[16 - 12];
1025         acc -= bp[19 - 12];
1026         rp[8] = (unsigned int)acc;
1027         acc >>= 32;
1028
1029         acc += rp[9];
1030         acc += bp[21 - 12];
1031         acc += bp[18 - 12];
1032         acc += bp[17 - 12];
1033         acc -= bp[20 - 12];
1034         rp[9] = (unsigned int)acc;
1035         acc >>= 32;
1036
1037         acc += rp[10];
1038         acc += bp[22 - 12];
1039         acc += bp[19 - 12];
1040         acc += bp[18 - 12];
1041         acc -= bp[21 - 12];
1042         rp[10] = (unsigned int)acc;
1043         acc >>= 32;
1044
1045         acc += rp[11];
1046         acc += bp[23 - 12];
1047         acc += bp[20 - 12];
1048         acc += bp[19 - 12];
1049         acc -= bp[22 - 12];
1050         rp[11] = (unsigned int)acc;
1051
1052         carry = (int)(acc >> 32);
1053     }
1054 #else
1055     {
1056         BN_ULONG t_d[BN_NIST_384_TOP];
1057
1058         /*
1059          * S1
1060          */
1061         nist_set_256(t_d, buf.bn, 0, 0, 0, 0, 0, 23 - 4, 22 - 4, 21 - 4);
1062         /* left shift */
1063         {
1064             register BN_ULONG *ap, t, c;
1065             ap = t_d;
1066             c = 0;
1067             for (i = 3; i != 0; --i) {
1068                 t = *ap;
1069                 *(ap++) = ((t << 1) | c) & BN_MASK2;
1070                 c = (t & BN_TBIT) ? 1 : 0;
1071             }
1072             *ap = c;
1073         }
1074         carry =
1075             (int)bn_add_words(r_d + (128 / BN_BITS2), r_d + (128 / BN_BITS2),
1076                               t_d, BN_NIST_256_TOP);
1077         /*
1078          * S2
1079          */
1080         carry += (int)bn_add_words(r_d, r_d, buf.bn, BN_NIST_384_TOP);
1081         /*
1082          * S3
1083          */
1084         nist_set_384(t_d, buf.bn, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 22,
1085                      21);
1086         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1087         /*
1088          * S4
1089          */
1090         nist_set_384(t_d, buf.bn, 19, 18, 17, 16, 15, 14, 13, 12, 20, 0, 23,
1091                      0);
1092         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1093         /*
1094          * S5
1095          */
1096         nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 23, 22, 21, 20, 0, 0, 0, 0);
1097         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1098         /*
1099          * S6
1100          */
1101         nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 23, 22, 21, 0, 0, 20);
1102         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1103         /*
1104          * D1
1105          */
1106         nist_set_384(t_d, buf.bn, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12,
1107                      23);
1108         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1109         /*
1110          * D2
1111          */
1112         nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 22, 21, 20, 0);
1113         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1114         /*
1115          * D3
1116          */
1117         nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 23, 0, 0, 0);
1118         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1119
1120     }
1121 #endif
1122     /* see BN_nist_mod_224 for explanation */
1123     u.f = bn_sub_words;
1124     if (carry > 0)
1125         carry =
1126             (int)bn_sub_words(r_d, r_d, _nist_p_384[carry - 1],
1127                               BN_NIST_384_TOP);
1128     else if (carry < 0) {
1129         carry =
1130             (int)bn_add_words(r_d, r_d, _nist_p_384[-carry - 1],
1131                               BN_NIST_384_TOP);
1132         mask = 0 - (PTR_SIZE_INT) carry;
1133         u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
1134             ((PTR_SIZE_INT) bn_add_words & ~mask);
1135     } else
1136         carry = 1;
1137
1138     mask =
1139         0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_384[0], BN_NIST_384_TOP);
1140     mask &= 0 - (PTR_SIZE_INT) carry;
1141     res = c_d;
1142     res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
1143                        ((PTR_SIZE_INT) r_d & mask));
1144     nist_cp_bn(r_d, res, BN_NIST_384_TOP);
1145     r->top = BN_NIST_384_TOP;
1146     bn_correct_top(r);
1147
1148     return 1;
1149 }
1150
1151 #define BN_NIST_521_RSHIFT      (521%BN_BITS2)
1152 #define BN_NIST_521_LSHIFT      (BN_BITS2-BN_NIST_521_RSHIFT)
1153 #define BN_NIST_521_TOP_MASK    ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT)
1154
1155 int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
1156                     BN_CTX *ctx)
1157 {
1158     int top = a->top, i;
1159     BN_ULONG *r_d, *a_d = a->d, t_d[BN_NIST_521_TOP], val, tmp, *res;
1160     PTR_SIZE_INT mask;
1161     static const BIGNUM _bignum_nist_p_521_sqr = {
1162         (BN_ULONG *)_nist_p_521_sqr,
1163         OSSL_NELEM(_nist_p_521_sqr),
1164         OSSL_NELEM(_nist_p_521_sqr),
1165         0, BN_FLG_STATIC_DATA
1166     };
1167
1168     field = &_bignum_nist_p_521; /* just to make sure */
1169
1170     if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_521_sqr) >= 0)
1171         return BN_nnmod(r, a, field, ctx);
1172
1173     i = BN_ucmp(field, a);
1174     if (i == 0) {
1175         BN_zero(r);
1176         return 1;
1177     } else if (i > 0)
1178         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
1179
1180     if (r != a) {
1181         if (!bn_wexpand(r, BN_NIST_521_TOP))
1182             return 0;
1183         r_d = r->d;
1184         nist_cp_bn(r_d, a_d, BN_NIST_521_TOP);
1185     } else
1186         r_d = a_d;
1187
1188     /* upper 521 bits, copy ... */
1189     nist_cp_bn_0(t_d, a_d + (BN_NIST_521_TOP - 1),
1190                  top - (BN_NIST_521_TOP - 1), BN_NIST_521_TOP);
1191     /* ... and right shift */
1192     for (val = t_d[0], i = 0; i < BN_NIST_521_TOP - 1; i++) {
1193 #if 0
1194         /*
1195          * MSC ARM compiler [version 2013, presumably even earlier,
1196          * much earlier] miscompiles this code, but not one in
1197          * #else section. See RT#3541.
1198          */
1199         tmp = val >> BN_NIST_521_RSHIFT;
1200         val = t_d[i + 1];
1201         t_d[i] = (tmp | val << BN_NIST_521_LSHIFT) & BN_MASK2;
1202 #else
1203         t_d[i] = (val >> BN_NIST_521_RSHIFT |
1204                   (tmp = t_d[i + 1]) << BN_NIST_521_LSHIFT) & BN_MASK2;
1205         val = tmp;
1206 #endif
1207     }
1208     t_d[i] = val >> BN_NIST_521_RSHIFT;
1209     /* lower 521 bits */
1210     r_d[i] &= BN_NIST_521_TOP_MASK;
1211
1212     bn_add_words(r_d, r_d, t_d, BN_NIST_521_TOP);
1213     mask =
1214         0 - (PTR_SIZE_INT) bn_sub_words(t_d, r_d, _nist_p_521,
1215                                         BN_NIST_521_TOP);
1216     res = t_d;
1217     res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
1218                        ((PTR_SIZE_INT) r_d & mask));
1219     nist_cp_bn(r_d, res, BN_NIST_521_TOP);
1220     r->top = BN_NIST_521_TOP;
1221     bn_correct_top(r);
1222
1223     return 1;
1224 }
1225
1226 int (*BN_nist_mod_func(const BIGNUM *p)) (BIGNUM *r, const BIGNUM *a,
1227                                           const BIGNUM *field, BN_CTX *ctx) {
1228     if (BN_ucmp(&_bignum_nist_p_192, p) == 0)
1229         return BN_nist_mod_192;
1230     if (BN_ucmp(&_bignum_nist_p_224, p) == 0)
1231         return BN_nist_mod_224;
1232     if (BN_ucmp(&_bignum_nist_p_256, p) == 0)
1233         return BN_nist_mod_256;
1234     if (BN_ucmp(&_bignum_nist_p_384, p) == 0)
1235         return BN_nist_mod_384;
1236     if (BN_ucmp(&_bignum_nist_p_521, p) == 0)
1237         return BN_nist_mod_521;
1238     return 0;
1239 }