crypto/bn/bn_nist.c

   1 /* crypto/bn/bn_nist.c */
   2 /*
   3  * Written by Nils Larsch for the OpenSSL project
   4  */
   5 /* ====================================================================
   6  * Copyright (c) 1998-2005 The OpenSSL Project.  All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  *
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in
  17  *    the documentation and/or other materials provided with the
  18  *    distribution.
  19  *
  20  * 3. All advertising materials mentioning features or use of this
  21  *    software must display the following acknowledgment:
  22  *    "This product includes software developed by the OpenSSL Project
  23  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  24  *
  25  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  26  *    endorse or promote products derived from this software without
  27  *    prior written permission. For written permission, please contact
  28  *    openssl-core@openssl.org.
  29  *
  30  * 5. Products derived from this software may not be called "OpenSSL"
  31  *    nor may "OpenSSL" appear in their names without prior written
  32  *    permission of the OpenSSL Project.
  33  *
  34  * 6. Redistributions of any form whatsoever must retain the following
  35  *    acknowledgment:
  36  *    "This product includes software developed by the OpenSSL Project
  37  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  38  *
  39  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  40  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  41  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  42  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  43  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  44  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  45  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  46  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  48  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  49  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  50  * OF THE POSSIBILITY OF SUCH DAMAGE.
  51  * ====================================================================
  52  *
  53  * This product includes cryptographic software written by Eric Young
  54  * (eay@cryptsoft.com).  This product includes software written by Tim
  55  * Hudson (tjh@cryptsoft.com).
  56  *
  57  */
  58
  59 #include "bn_lcl.h"
  60 #include "cryptlib.h"
  61
  62 #define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2
  63 #define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2
  64 #define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2
  65 #define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2
  66 #define BN_NIST_521_TOP (521+BN_BITS2-1)/BN_BITS2
  67
  68 /* pre-computed tables are "carry-less" values of modulus*(i+1) */
  69 #if BN_BITS2 == 64
  70 static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
  71     {0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFFULL},
  72     {0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL},
  73     {0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFFFULL}
  74 };
  75
  76 static const BN_ULONG _nist_p_192_sqr[] = {
  77     0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000001ULL,
  78     0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL
  79 };
  80
  81 static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = {
  82     {0x0000000000000001ULL, 0xFFFFFFFF00000000ULL,
  83      0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL},
  84     {0x0000000000000002ULL, 0xFFFFFFFE00000000ULL,
  85      0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFFULL} /* this one is
  86                                                     * "carry-full" */
  87 };
  88
  89 static const BN_ULONG _nist_p_224_sqr[] = {
  90     0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
  91     0xFFFFFFFFFFFFFFFFULL, 0x0000000200000000ULL,
  92     0x0000000000000000ULL, 0xFFFFFFFFFFFFFFFEULL,
  93     0xFFFFFFFFFFFFFFFFULL
  94 };
  95
  96 static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = {
  97     {0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL,
  98      0x0000000000000000ULL, 0xFFFFFFFF00000001ULL},
  99     {0xFFFFFFFFFFFFFFFEULL, 0x00000001FFFFFFFFULL,
 100      0x0000000000000000ULL, 0xFFFFFFFE00000002ULL},
 101     {0xFFFFFFFFFFFFFFFDULL, 0x00000002FFFFFFFFULL,
 102      0x0000000000000000ULL, 0xFFFFFFFD00000003ULL},
 103     {0xFFFFFFFFFFFFFFFCULL, 0x00000003FFFFFFFFULL,
 104      0x0000000000000000ULL, 0xFFFFFFFC00000004ULL},
 105     {0xFFFFFFFFFFFFFFFBULL, 0x00000004FFFFFFFFULL,
 106      0x0000000000000000ULL, 0xFFFFFFFB00000005ULL},
 107 };
 108
 109 static const BN_ULONG _nist_p_256_sqr[] = {
 110     0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
 111     0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFEULL,
 112     0x00000001FFFFFFFEULL, 0x00000001FFFFFFFEULL,
 113     0xFFFFFFFE00000001ULL, 0xFFFFFFFE00000002ULL
 114 };
 115
 116 static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = {
 117     {0x00000000FFFFFFFFULL, 0xFFFFFFFF00000000ULL, 0xFFFFFFFFFFFFFFFEULL,
 118      0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
 119     {0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL,
 120      0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
 121     {0x00000002FFFFFFFDULL, 0xFFFFFFFD00000000ULL, 0xFFFFFFFFFFFFFFFCULL,
 122      0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
 123     {0x00000003FFFFFFFCULL, 0xFFFFFFFC00000000ULL, 0xFFFFFFFFFFFFFFFBULL,
 124      0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
 125     {0x00000004FFFFFFFBULL, 0xFFFFFFFB00000000ULL, 0xFFFFFFFFFFFFFFFAULL,
 126      0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
 127 };
 128
 129 static const BN_ULONG _nist_p_384_sqr[] = {
 130     0xFFFFFFFE00000001ULL, 0x0000000200000000ULL, 0xFFFFFFFE00000000ULL,
 131     0x0000000200000000ULL, 0x0000000000000001ULL, 0x0000000000000000ULL,
 132     0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL,
 133     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL
 134 };
 135
 136 static const BN_ULONG _nist_p_521[] =
 137     { 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
 138     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
 139     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
 140     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
 141     0x00000000000001FFULL
 142 };
 143
 144 static const BN_ULONG _nist_p_521_sqr[] = {
 145     0x0000000000000001ULL, 0x0000000000000000ULL, 0x0000000000000000ULL,
 146     0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL,
 147     0x0000000000000000ULL, 0x0000000000000000ULL, 0xFFFFFFFFFFFFFC00ULL,
 148     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
 149     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
 150     0xFFFFFFFFFFFFFFFFULL, 0x000000000003FFFFULL
 151 };
 152 #elif BN_BITS2 == 32
 153 static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
 154     {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 155     {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 156     {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
 157 };
 158
 159 static const BN_ULONG _nist_p_192_sqr[] = {
 160     0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, 0x00000000,
 161     0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
 162 };
 163
 164 static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = {
 165     {0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF,
 166      0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 167     {0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE,
 168      0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
 169 };
 170
 171 static const BN_ULONG _nist_p_224_sqr[] = {
 172     0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE,
 173     0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000002,
 174     0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF,
 175     0xFFFFFFFF, 0xFFFFFFFF
 176 };
 177
 178 static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = {
 179     {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000,
 180      0x00000000, 0x00000000, 0x00000001, 0xFFFFFFFF},
 181     {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001,
 182      0x00000000, 0x00000000, 0x00000002, 0xFFFFFFFE},
 183     {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000002,
 184      0x00000000, 0x00000000, 0x00000003, 0xFFFFFFFD},
 185     {0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000003,
 186      0x00000000, 0x00000000, 0x00000004, 0xFFFFFFFC},
 187     {0xFFFFFFFB, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000004,
 188      0x00000000, 0x00000000, 0x00000005, 0xFFFFFFFB},
 189 };
 190
 191 static const BN_ULONG _nist_p_256_sqr[] = {
 192     0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE,
 193     0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0x00000001,
 194     0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001,
 195     0x00000001, 0xFFFFFFFE, 0x00000002, 0xFFFFFFFE
 196 };
 197
 198 static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = {
 199     {0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF,
 200      0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 201     {0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF,
 202      0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 203     {0xFFFFFFFD, 0x00000002, 0x00000000, 0xFFFFFFFD, 0xFFFFFFFC, 0xFFFFFFFF,
 204      0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 205     {0xFFFFFFFC, 0x00000003, 0x00000000, 0xFFFFFFFC, 0xFFFFFFFB, 0xFFFFFFFF,
 206      0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 207     {0xFFFFFFFB, 0x00000004, 0x00000000, 0xFFFFFFFB, 0xFFFFFFFA, 0xFFFFFFFF,
 208      0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
 209 };
 210
 211 static const BN_ULONG _nist_p_384_sqr[] = {
 212     0x00000001, 0xFFFFFFFE, 0x00000000, 0x00000002, 0x00000000, 0xFFFFFFFE,
 213     0x00000000, 0x00000002, 0x00000001, 0x00000000, 0x00000000, 0x00000000,
 214     0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF,
 215     0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
 216 };
 217
 218 static const BN_ULONG _nist_p_521[] = { 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
 219     0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
 220     0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
 221     0xFFFFFFFF, 0x000001FF
 222 };
 223
 224 static const BN_ULONG _nist_p_521_sqr[] = {
 225     0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
 226     0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
 227     0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFC00, 0xFFFFFFFF,
 228     0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
 229     0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
 230     0xFFFFFFFF, 0xFFFFFFFF, 0x0003FFFF
 231 };
 232 #else
 233 # error "unsupported BN_BITS2"
 234 #endif
 235
 236 static const BIGNUM _bignum_nist_p_192 = {
 237     (BN_ULONG *)_nist_p_192[0],
 238     BN_NIST_192_TOP,
 239     BN_NIST_192_TOP,
 240     0,
 241     BN_FLG_STATIC_DATA
 242 };
 243
 244 static const BIGNUM _bignum_nist_p_224 = {
 245     (BN_ULONG *)_nist_p_224[0],
 246     BN_NIST_224_TOP,
 247     BN_NIST_224_TOP,
 248     0,
 249     BN_FLG_STATIC_DATA
 250 };
 251
 252 static const BIGNUM _bignum_nist_p_256 = {
 253     (BN_ULONG *)_nist_p_256[0],
 254     BN_NIST_256_TOP,
 255     BN_NIST_256_TOP,
 256     0,
 257     BN_FLG_STATIC_DATA
 258 };
 259
 260 static const BIGNUM _bignum_nist_p_384 = {
 261     (BN_ULONG *)_nist_p_384[0],
 262     BN_NIST_384_TOP,
 263     BN_NIST_384_TOP,
 264     0,
 265     BN_FLG_STATIC_DATA
 266 };
 267
 268 static const BIGNUM _bignum_nist_p_521 = {
 269     (BN_ULONG *)_nist_p_521,
 270     BN_NIST_521_TOP,
 271     BN_NIST_521_TOP,
 272     0,
 273     BN_FLG_STATIC_DATA
 274 };
 275
 276 const BIGNUM *BN_get0_nist_prime_192(void)
 277 {
 278     return &_bignum_nist_p_192;
 279 }
 280
 281 const BIGNUM *BN_get0_nist_prime_224(void)
 282 {
 283     return &_bignum_nist_p_224;
 284 }
 285
 286 const BIGNUM *BN_get0_nist_prime_256(void)
 287 {
 288     return &_bignum_nist_p_256;
 289 }
 290
 291 const BIGNUM *BN_get0_nist_prime_384(void)
 292 {
 293     return &_bignum_nist_p_384;
 294 }
 295
 296 const BIGNUM *BN_get0_nist_prime_521(void)
 297 {
 298     return &_bignum_nist_p_521;
 299 }
 300
 301 static void nist_cp_bn_0(BN_ULONG *buf, BN_ULONG *a, int top, int max)
 302 {
 303     int i;
 304     BN_ULONG *_tmp1 = (buf), *_tmp2 = (a);
 305
 306 #ifdef BN_DEBUG
 307     OPENSSL_assert(top <= max);
 308 #endif
 309     for (i = (top); i != 0; i--)
 310         *_tmp1++ = *_tmp2++;
 311     for (i = (max) - (top); i != 0; i--)
 312         *_tmp1++ = (BN_ULONG)0;
 313 }
 314
 315 static void nist_cp_bn(BN_ULONG *buf, BN_ULONG *a, int top)
 316 {
 317     int i;
 318     BN_ULONG *_tmp1 = (buf), *_tmp2 = (a);
 319     for (i = (top); i != 0; i--)
 320         *_tmp1++ = *_tmp2++;
 321 }
 322
 323 #if BN_BITS2 == 64
 324 # define bn_cp_64(to, n, from, m)        (to)[n] = (m>=0)?((from)[m]):0;
 325 # define bn_64_set_0(to, n)              (to)[n] = (BN_ULONG)0;
 326 /*
 327  * two following macros are implemented under assumption that they
 328  * are called in a sequence with *ascending* n, i.e. as they are...
 329  */
 330 # 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))\
 331                                                 :(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l)))
 332 # define bn_32_set_0(to, n)              (((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0));
 333 # define bn_cp_32(to,n,from,m)           ((m)>=0)?bn_cp_32_naked(to,n,from,m):bn_32_set_0(to,n)
 334 #else
 335 # define bn_cp_64(to, n, from, m) \
 336         { \
 337         bn_cp_32(to, (n)*2, from, (m)*2); \
 338         bn_cp_32(to, (n)*2+1, from, (m)*2+1); \
 339         }
 340 # define bn_64_set_0(to, n) \
 341         { \
 342         bn_32_set_0(to, (n)*2); \
 343         bn_32_set_0(to, (n)*2+1); \
 344         }
 345 # if BN_BITS2 == 32
 346 #  define bn_cp_32(to, n, from, m)        (to)[n] = (m>=0)?((from)[m]):0;
 347 #  define bn_32_set_0(to, n)              (to)[n] = (BN_ULONG)0;
 348 # endif
 349 #endif                          /* BN_BITS2 != 64 */
 350
 351 #define nist_set_192(to, from, a1, a2, a3) \
 352         { \
 353         bn_cp_64(to, 0, from, (a3) - 3) \
 354         bn_cp_64(to, 1, from, (a2) - 3) \
 355         bn_cp_64(to, 2, from, (a1) - 3) \
 356         }
 357
 358 int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
 359                     BN_CTX *ctx)
 360 {
 361     int top = a->top, i;
 362     int carry;
 363     register BN_ULONG *r_d, *a_d = a->d;
 364     BN_ULONG t_d[BN_NIST_192_TOP],
 365         buf[BN_NIST_192_TOP], c_d[BN_NIST_192_TOP], *res;
 366     size_t mask;
 367     static const BIGNUM _bignum_nist_p_192_sqr = {
 368         (BN_ULONG *)_nist_p_192_sqr,
 369         sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]),
 370         sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]),
 371         0, BN_FLG_STATIC_DATA
 372     };
 373
 374     field = &_bignum_nist_p_192; /* just to make sure */
 375
 376     if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_192_sqr) >= 0)
 377         return BN_nnmod(r, a, field, ctx);
 378
 379     i = BN_ucmp(field, a);
 380     if (i == 0) {
 381         BN_zero(r);
 382         return 1;
 383     } else if (i > 0)
 384         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
 385
 386     if (r != a) {
 387         if (!bn_wexpand(r, BN_NIST_192_TOP))
 388             return 0;
 389         r_d = r->d;
 390         nist_cp_bn(r_d, a_d, BN_NIST_192_TOP);
 391     } else
 392         r_d = a_d;
 393
 394     nist_cp_bn_0(buf, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP,
 395                  BN_NIST_192_TOP);
 396
 397     nist_set_192(t_d, buf, 0, 3, 3);
 398     carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
 399     nist_set_192(t_d, buf, 4, 4, 0);
 400     carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
 401     nist_set_192(t_d, buf, 5, 5, 5)
 402         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
 403
 404     if (carry > 0)
 405         carry =
 406             (int)bn_sub_words(r_d, r_d, _nist_p_192[carry - 1],
 407                               BN_NIST_192_TOP);
 408     else
 409         carry = 1;
 410
 411     /*
 412      * we need 'if (carry==0 || result>=modulus) result-=modulus;'
 413      * as comparison implies subtraction, we can write
 414      * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;'
 415      * this is what happens below, but without explicit if:-) a.
 416      */
 417     mask =
 418         0 - (size_t)bn_sub_words(c_d, r_d, _nist_p_192[0], BN_NIST_192_TOP);
 419     mask &= 0 - (size_t)carry;
 420     res = (BN_ULONG *)(((size_t)c_d & ~mask) | ((size_t)r_d & mask));
 421     nist_cp_bn(r_d, res, BN_NIST_192_TOP);
 422     r->top = BN_NIST_192_TOP;
 423     bn_correct_top(r);
 424
 425     return 1;
 426 }
 427
 428 typedef BN_ULONG (*bn_addsub_f) (BN_ULONG *, const BN_ULONG *,
 429                                  const BN_ULONG *, int);
 430
 431 #define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \
 432         { \
 433         bn_cp_32(to, 0, from, (a7) - 7) \
 434         bn_cp_32(to, 1, from, (a6) - 7) \
 435         bn_cp_32(to, 2, from, (a5) - 7) \
 436         bn_cp_32(to, 3, from, (a4) - 7) \
 437         bn_cp_32(to, 4, from, (a3) - 7) \
 438         bn_cp_32(to, 5, from, (a2) - 7) \
 439         bn_cp_32(to, 6, from, (a1) - 7) \
 440         }
 441
 442 int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
 443                     BN_CTX *ctx)
 444 {
 445     int top = a->top, i;
 446     int carry;
 447     BN_ULONG *r_d, *a_d = a->d;
 448     BN_ULONG t_d[BN_NIST_224_TOP],
 449         buf[BN_NIST_224_TOP], c_d[BN_NIST_224_TOP], *res;
 450     size_t mask;
 451     union {
 452         bn_addsub_f f;
 453         size_t p;
 454     } u;
 455     static const BIGNUM _bignum_nist_p_224_sqr = {
 456         (BN_ULONG *)_nist_p_224_sqr,
 457         sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]),
 458         sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]),
 459         0, BN_FLG_STATIC_DATA
 460     };
 461
 462     field = &_bignum_nist_p_224; /* just to make sure */
 463
 464     if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_224_sqr) >= 0)
 465         return BN_nnmod(r, a, field, ctx);
 466
 467     i = BN_ucmp(field, a);
 468     if (i == 0) {
 469         BN_zero(r);
 470         return 1;
 471     } else if (i > 0)
 472         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
 473
 474     if (r != a) {
 475         if (!bn_wexpand(r, BN_NIST_224_TOP))
 476             return 0;
 477         r_d = r->d;
 478         nist_cp_bn(r_d, a_d, BN_NIST_224_TOP);
 479     } else
 480         r_d = a_d;
 481
 482 #if BN_BITS2==64
 483     /* copy upper 256 bits of 448 bit number ... */
 484     nist_cp_bn_0(t_d, a_d + (BN_NIST_224_TOP - 1),
 485                  top - (BN_NIST_224_TOP - 1), BN_NIST_224_TOP);
 486     /* ... and right shift by 32 to obtain upper 224 bits */
 487     nist_set_224(buf, t_d, 14, 13, 12, 11, 10, 9, 8);
 488     /* truncate lower part to 224 bits too */
 489     r_d[BN_NIST_224_TOP - 1] &= BN_MASK2l;
 490 #else
 491     nist_cp_bn_0(buf, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP,
 492                  BN_NIST_224_TOP);
 493 #endif
 494     nist_set_224(t_d, buf, 10, 9, 8, 7, 0, 0, 0);
 495     carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
 496     nist_set_224(t_d, buf, 0, 13, 12, 11, 0, 0, 0);
 497     carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
 498     nist_set_224(t_d, buf, 13, 12, 11, 10, 9, 8, 7);
 499     carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
 500     nist_set_224(t_d, buf, 0, 0, 0, 0, 13, 12, 11);
 501     carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
 502
 503 #if BN_BITS2==64
 504     carry = (int)(r_d[BN_NIST_224_TOP - 1] >> 32);
 505 #endif
 506     u.f = bn_sub_words;
 507     if (carry > 0) {
 508         carry =
 509             (int)bn_sub_words(r_d, r_d, _nist_p_224[carry - 1],
 510                               BN_NIST_224_TOP);
 511 #if BN_BITS2==64
 512         carry = (int)(~(r_d[BN_NIST_224_TOP - 1] >> 32)) & 1;
 513 #endif
 514     } else if (carry < 0) {
 515         /*
 516          * it's a bit more comlicated logic in this case. if bn_add_words
 517          * yields no carry, then result has to be adjusted by unconditionally
 518          * *adding* the modulus. but if it does, then result has to be
 519          * compared to the modulus and conditionally adjusted by
 520          * *subtracting* the latter.
 521          */
 522         carry =
 523             (int)bn_add_words(r_d, r_d, _nist_p_224[-carry - 1],
 524                               BN_NIST_224_TOP);
 525         mask = 0 - (size_t)carry;
 526         u.p = ((size_t)bn_sub_words & mask) | ((size_t)bn_add_words & ~mask);
 527     } else
 528         carry = 1;
 529
 530     /* otherwise it's effectively same as in BN_nist_mod_192... */
 531     mask = 0 - (size_t)(*u.f) (c_d, r_d, _nist_p_224[0], BN_NIST_224_TOP);
 532     mask &= 0 - (size_t)carry;
 533     res = (BN_ULONG *)(((size_t)c_d & ~mask) | ((size_t)r_d & mask));
 534     nist_cp_bn(r_d, res, BN_NIST_224_TOP);
 535     r->top = BN_NIST_224_TOP;
 536     bn_correct_top(r);
 537
 538     return 1;
 539 }
 540
 541 #define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \
 542         { \
 543         bn_cp_32(to, 0, from, (a8) - 8) \
 544         bn_cp_32(to, 1, from, (a7) - 8) \
 545         bn_cp_32(to, 2, from, (a6) - 8) \
 546         bn_cp_32(to, 3, from, (a5) - 8) \
 547         bn_cp_32(to, 4, from, (a4) - 8) \
 548         bn_cp_32(to, 5, from, (a3) - 8) \
 549         bn_cp_32(to, 6, from, (a2) - 8) \
 550         bn_cp_32(to, 7, from, (a1) - 8) \
 551         }
 552
 553 int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
 554                     BN_CTX *ctx)
 555 {
 556     int i, top = a->top;
 557     int carry = 0;
 558     register BN_ULONG *a_d = a->d, *r_d;
 559     BN_ULONG t_d[BN_NIST_256_TOP],
 560         buf[BN_NIST_256_TOP], c_d[BN_NIST_256_TOP], *res;
 561     size_t mask;
 562     union {
 563         bn_addsub_f f;
 564         size_t p;
 565     } u;
 566     static const BIGNUM _bignum_nist_p_256_sqr = {
 567         (BN_ULONG *)_nist_p_256_sqr,
 568         sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]),
 569         sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]),
 570         0, BN_FLG_STATIC_DATA
 571     };
 572
 573     field = &_bignum_nist_p_256; /* just to make sure */
 574
 575     if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_256_sqr) >= 0)
 576         return BN_nnmod(r, a, field, ctx);
 577
 578     i = BN_ucmp(field, a);
 579     if (i == 0) {
 580         BN_zero(r);
 581         return 1;
 582     } else if (i > 0)
 583         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
 584
 585     if (r != a) {
 586         if (!bn_wexpand(r, BN_NIST_256_TOP))
 587             return 0;
 588         r_d = r->d;
 589         nist_cp_bn(r_d, a_d, BN_NIST_256_TOP);
 590     } else
 591         r_d = a_d;
 592
 593     nist_cp_bn_0(buf, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP,
 594                  BN_NIST_256_TOP);
 595
 596     /*
 597      * S1
 598      */
 599     nist_set_256(t_d, buf, 15, 14, 13, 12, 11, 0, 0, 0);
 600     /*
 601      * S2
 602      */
 603     nist_set_256(c_d, buf, 0, 15, 14, 13, 12, 0, 0, 0);
 604     carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP);
 605     /* left shift */
 606     {
 607         register BN_ULONG *ap, t, c;
 608         ap = t_d;
 609         c = 0;
 610         for (i = BN_NIST_256_TOP; i != 0; --i) {
 611             t = *ap;
 612             *(ap++) = ((t << 1) | c) & BN_MASK2;
 613             c = (t & BN_TBIT) ? 1 : 0;
 614         }
 615         carry <<= 1;
 616         carry |= c;
 617     }
 618     carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
 619     /*
 620      * S3
 621      */
 622     nist_set_256(t_d, buf, 15, 14, 0, 0, 0, 10, 9, 8);
 623     carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
 624     /*
 625      * S4
 626      */
 627     nist_set_256(t_d, buf, 8, 13, 15, 14, 13, 11, 10, 9);
 628     carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
 629     /*
 630      * D1
 631      */
 632     nist_set_256(t_d, buf, 10, 8, 0, 0, 0, 13, 12, 11);
 633     carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
 634     /*
 635      * D2
 636      */
 637     nist_set_256(t_d, buf, 11, 9, 0, 0, 15, 14, 13, 12);
 638     carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
 639     /*
 640      * D3
 641      */
 642     nist_set_256(t_d, buf, 12, 0, 10, 9, 8, 15, 14, 13);
 643     carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
 644     /*
 645      * D4
 646      */
 647     nist_set_256(t_d, buf, 13, 0, 11, 10, 9, 0, 15, 14);
 648     carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
 649
 650     /* see BN_nist_mod_224 for explanation */
 651     u.f = bn_sub_words;
 652     if (carry > 0)
 653         carry =
 654             (int)bn_sub_words(r_d, r_d, _nist_p_256[carry - 1],
 655                               BN_NIST_256_TOP);
 656     else if (carry < 0) {
 657         carry =
 658             (int)bn_add_words(r_d, r_d, _nist_p_256[-carry - 1],
 659                               BN_NIST_256_TOP);
 660         mask = 0 - (size_t)carry;
 661         u.p = ((size_t)bn_sub_words & mask) | ((size_t)bn_add_words & ~mask);
 662     } else
 663         carry = 1;
 664
 665     mask = 0 - (size_t)(*u.f) (c_d, r_d, _nist_p_256[0], BN_NIST_256_TOP);
 666     mask &= 0 - (size_t)carry;
 667     res = (BN_ULONG *)(((size_t)c_d & ~mask) | ((size_t)r_d & mask));
 668     nist_cp_bn(r_d, res, BN_NIST_256_TOP);
 669     r->top = BN_NIST_256_TOP;
 670     bn_correct_top(r);
 671
 672     return 1;
 673 }
 674
 675 #define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \
 676         { \
 677         bn_cp_32(to, 0, from,  (a12) - 12) \
 678         bn_cp_32(to, 1, from,  (a11) - 12) \
 679         bn_cp_32(to, 2, from,  (a10) - 12) \
 680         bn_cp_32(to, 3, from,  (a9) - 12)  \
 681         bn_cp_32(to, 4, from,  (a8) - 12)  \
 682         bn_cp_32(to, 5, from,  (a7) - 12)  \
 683         bn_cp_32(to, 6, from,  (a6) - 12)  \
 684         bn_cp_32(to, 7, from,  (a5) - 12)  \
 685         bn_cp_32(to, 8, from,  (a4) - 12)  \
 686         bn_cp_32(to, 9, from,  (a3) - 12)  \
 687         bn_cp_32(to, 10, from, (a2) - 12)  \
 688         bn_cp_32(to, 11, from, (a1) - 12)  \
 689         }
 690
 691 int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
 692                     BN_CTX *ctx)
 693 {
 694     int i, top = a->top;
 695     int carry = 0;
 696     register BN_ULONG *r_d, *a_d = a->d;
 697     BN_ULONG t_d[BN_NIST_384_TOP],
 698         buf[BN_NIST_384_TOP], c_d[BN_NIST_384_TOP], *res;
 699     size_t mask;
 700     union {
 701         bn_addsub_f f;
 702         size_t p;
 703     } u;
 704     static const BIGNUM _bignum_nist_p_384_sqr = {
 705         (BN_ULONG *)_nist_p_384_sqr,
 706         sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]),
 707         sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]),
 708         0, BN_FLG_STATIC_DATA
 709     };
 710
 711     field = &_bignum_nist_p_384; /* just to make sure */
 712
 713     if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_384_sqr) >= 0)
 714         return BN_nnmod(r, a, field, ctx);
 715
 716     i = BN_ucmp(field, a);
 717     if (i == 0) {
 718         BN_zero(r);
 719         return 1;
 720     } else if (i > 0)
 721         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
 722
 723     if (r != a) {
 724         if (!bn_wexpand(r, BN_NIST_384_TOP))
 725             return 0;
 726         r_d = r->d;
 727         nist_cp_bn(r_d, a_d, BN_NIST_384_TOP);
 728     } else
 729         r_d = a_d;
 730
 731     nist_cp_bn_0(buf, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP,
 732                  BN_NIST_384_TOP);
 733
 734     /*
 735      * S1
 736      */
 737     nist_set_256(t_d, buf, 0, 0, 0, 0, 0, 23 - 4, 22 - 4, 21 - 4);
 738     /* left shift */
 739     {
 740         register BN_ULONG *ap, t, c;
 741         ap = t_d;
 742         c = 0;
 743         for (i = 3; i != 0; --i) {
 744             t = *ap;
 745             *(ap++) = ((t << 1) | c) & BN_MASK2;
 746             c = (t & BN_TBIT) ? 1 : 0;
 747         }
 748         *ap = c;
 749     }
 750     carry = (int)bn_add_words(r_d + (128 / BN_BITS2), r_d + (128 / BN_BITS2),
 751                               t_d, BN_NIST_256_TOP);
 752     /*
 753      * S2
 754      */
 755     carry += (int)bn_add_words(r_d, r_d, buf, BN_NIST_384_TOP);
 756     /*
 757      * S3
 758      */
 759     nist_set_384(t_d, buf, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 22, 21);
 760     carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
 761     /*
 762      * S4
 763      */
 764     nist_set_384(t_d, buf, 19, 18, 17, 16, 15, 14, 13, 12, 20, 0, 23, 0);
 765     carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
 766     /*
 767      * S5
 768      */
 769     nist_set_384(t_d, buf, 0, 0, 0, 0, 23, 22, 21, 20, 0, 0, 0, 0);
 770     carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
 771     /*
 772      * S6
 773      */
 774     nist_set_384(t_d, buf, 0, 0, 0, 0, 0, 0, 23, 22, 21, 0, 0, 20);
 775     carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
 776     /*
 777      * D1
 778      */
 779     nist_set_384(t_d, buf, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23);
 780     carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
 781     /*
 782      * D2
 783      */
 784     nist_set_384(t_d, buf, 0, 0, 0, 0, 0, 0, 0, 23, 22, 21, 20, 0);
 785     carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
 786     /*
 787      * D3
 788      */
 789     nist_set_384(t_d, buf, 0, 0, 0, 0, 0, 0, 0, 23, 23, 0, 0, 0);
 790     carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
 791
 792     /* see BN_nist_mod_224 for explanation */
 793     u.f = bn_sub_words;
 794     if (carry > 0)
 795         carry =
 796             (int)bn_sub_words(r_d, r_d, _nist_p_384[carry - 1],
 797                               BN_NIST_384_TOP);
 798     else if (carry < 0) {
 799         carry =
 800             (int)bn_add_words(r_d, r_d, _nist_p_384[-carry - 1],
 801                               BN_NIST_384_TOP);
 802         mask = 0 - (size_t)carry;
 803         u.p = ((size_t)bn_sub_words & mask) | ((size_t)bn_add_words & ~mask);
 804     } else
 805         carry = 1;
 806
 807     mask = 0 - (size_t)(*u.f) (c_d, r_d, _nist_p_384[0], BN_NIST_384_TOP);
 808     mask &= 0 - (size_t)carry;
 809     res = (BN_ULONG *)(((size_t)c_d & ~mask) | ((size_t)r_d & mask));
 810     nist_cp_bn(r_d, res, BN_NIST_384_TOP);
 811     r->top = BN_NIST_384_TOP;
 812     bn_correct_top(r);
 813
 814     return 1;
 815 }
 816
 817 #define BN_NIST_521_RSHIFT      (521%BN_BITS2)
 818 #define BN_NIST_521_LSHIFT      (BN_BITS2-BN_NIST_521_RSHIFT)
 819 #define BN_NIST_521_TOP_MASK    ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT)
 820
 821 int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
 822                     BN_CTX *ctx)
 823 {
 824     int top = a->top, i;
 825     BN_ULONG *r_d, *a_d = a->d, t_d[BN_NIST_521_TOP], val, tmp, *res;
 826     size_t mask;
 827     static const BIGNUM _bignum_nist_p_521_sqr = {
 828         (BN_ULONG *)_nist_p_521_sqr,
 829         sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]),
 830         sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]),
 831         0, BN_FLG_STATIC_DATA
 832     };
 833
 834     field = &_bignum_nist_p_521; /* just to make sure */
 835
 836     if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_521_sqr) >= 0)
 837         return BN_nnmod(r, a, field, ctx);
 838
 839     i = BN_ucmp(field, a);
 840     if (i == 0) {
 841         BN_zero(r);
 842         return 1;
 843     } else if (i > 0)
 844         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
 845
 846     if (r != a) {
 847         if (!bn_wexpand(r, BN_NIST_521_TOP))
 848             return 0;
 849         r_d = r->d;
 850         nist_cp_bn(r_d, a_d, BN_NIST_521_TOP);
 851     } else
 852         r_d = a_d;
 853
 854     /* upper 521 bits, copy ... */
 855     nist_cp_bn_0(t_d, a_d + (BN_NIST_521_TOP - 1),
 856                  top - (BN_NIST_521_TOP - 1), BN_NIST_521_TOP);
 857     /* ... and right shift */
 858     for (val = t_d[0], i = 0; i < BN_NIST_521_TOP - 1; i++) {
 859         tmp = val >> BN_NIST_521_RSHIFT;
 860         val = t_d[i + 1];
 861         t_d[i] = (tmp | val << BN_NIST_521_LSHIFT) & BN_MASK2;
 862     }
 863     t_d[i] = val >> BN_NIST_521_RSHIFT;
 864     /* lower 521 bits */
 865     r_d[i] &= BN_NIST_521_TOP_MASK;
 866
 867     bn_add_words(r_d, r_d, t_d, BN_NIST_521_TOP);
 868     mask = 0 - (size_t)bn_sub_words(t_d, r_d, _nist_p_521, BN_NIST_521_TOP);
 869     res = (BN_ULONG *)(((size_t)t_d & ~mask) | ((size_t)r_d & mask));
 870     nist_cp_bn(r_d, res, BN_NIST_521_TOP);
 871     r->top = BN_NIST_521_TOP;
 872     bn_correct_top(r);
 873
 874     return 1;
 875 }