crypto/bn/bn_nist.c

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