1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/ssl/libcrypto/src/crypto/bn/bn_nist.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,832 @@
1.4 +/* crypto/bn/bn_nist.c */
1.5 +/*
1.6 + * Written by Nils Larsch for the OpenSSL project
1.7 + */
1.8 +/* ====================================================================
1.9 + * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved.
1.10 + *
1.11 + * Redistribution and use in source and binary forms, with or without
1.12 + * modification, are permitted provided that the following conditions
1.13 + * are met:
1.14 + *
1.15 + * 1. Redistributions of source code must retain the above copyright
1.16 + * notice, this list of conditions and the following disclaimer.
1.17 + *
1.18 + * 2. Redistributions in binary form must reproduce the above copyright
1.19 + * notice, this list of conditions and the following disclaimer in
1.20 + * the documentation and/or other materials provided with the
1.21 + * distribution.
1.22 + *
1.23 + * 3. All advertising materials mentioning features or use of this
1.24 + * software must display the following acknowledgment:
1.25 + * "This product includes software developed by the OpenSSL Project
1.26 + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
1.27 + *
1.28 + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
1.29 + * endorse or promote products derived from this software without
1.30 + * prior written permission. For written permission, please contact
1.31 + * openssl-core@openssl.org.
1.32 + *
1.33 + * 5. Products derived from this software may not be called "OpenSSL"
1.34 + * nor may "OpenSSL" appear in their names without prior written
1.35 + * permission of the OpenSSL Project.
1.36 + *
1.37 + * 6. Redistributions of any form whatsoever must retain the following
1.38 + * acknowledgment:
1.39 + * "This product includes software developed by the OpenSSL Project
1.40 + * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
1.41 + *
1.42 + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
1.43 + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.44 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
1.45 + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
1.46 + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.47 + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
1.48 + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
1.49 + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
1.50 + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
1.51 + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.52 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
1.53 + * OF THE POSSIBILITY OF SUCH DAMAGE.
1.54 + * ====================================================================
1.55 + *
1.56 + * This product includes cryptographic software written by Eric Young
1.57 + * (eay@cryptsoft.com). This product includes software written by Tim
1.58 + * Hudson (tjh@cryptsoft.com).
1.59 + *
1.60 + */
1.61 + /*
1.62 + © Portions copyright (c) 2006 Nokia Corporation. All rights reserved.
1.63 + */
1.64 +
1.65 +
1.66 +
1.67 +#include "bn_lcl.h"
1.68 +#include "cryptlib.h"
1.69 +#if (defined(SYMBIAN) && (defined(__WINSCW__) || defined(__WINS__)))
1.70 +#include "libcrypto_wsd_macros.h"
1.71 +#include "libcrypto_wsd.h"
1.72 +#endif
1.73 +
1.74 +
1.75 +#define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2
1.76 +#define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2
1.77 +#define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2
1.78 +#define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2
1.79 +#define BN_NIST_521_TOP (521+BN_BITS2-1)/BN_BITS2
1.80 +
1.81 +
1.82 +#if BN_BITS2 == 64
1.83 +static const BN_ULONG _nist_p_192[] =
1.84 + {0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFEULL,
1.85 + 0xFFFFFFFFFFFFFFFFULL};
1.86 +static const BN_ULONG _nist_p_224[] =
1.87 + {0x0000000000000001ULL,0xFFFFFFFF00000000ULL,
1.88 + 0xFFFFFFFFFFFFFFFFULL,0x00000000FFFFFFFFULL};
1.89 +static const BN_ULONG _nist_p_256[] =
1.90 + {0xFFFFFFFFFFFFFFFFULL,0x00000000FFFFFFFFULL,
1.91 + 0x0000000000000000ULL,0xFFFFFFFF00000001ULL};
1.92 +static const BN_ULONG _nist_p_384[] =
1.93 + {0x00000000FFFFFFFFULL,0xFFFFFFFF00000000ULL,
1.94 + 0xFFFFFFFFFFFFFFFEULL,0xFFFFFFFFFFFFFFFFULL,
1.95 + 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL};
1.96 +static const BN_ULONG _nist_p_521[] =
1.97 + {0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,
1.98 + 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,
1.99 + 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,
1.100 + 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,
1.101 + 0x00000000000001FFULL};
1.102 +#elif BN_BITS2 == 32
1.103 +static const BN_ULONG _nist_p_192[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFE,
1.104 + 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};
1.105 +static const BN_ULONG _nist_p_224[] = {0x00000001,0x00000000,0x00000000,
1.106 + 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};
1.107 +static const BN_ULONG _nist_p_256[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
1.108 + 0x00000000,0x00000000,0x00000000,0x00000001,0xFFFFFFFF};
1.109 +static const BN_ULONG _nist_p_384[] = {0xFFFFFFFF,0x00000000,0x00000000,
1.110 + 0xFFFFFFFF,0xFFFFFFFE,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
1.111 + 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};
1.112 +static const BN_ULONG _nist_p_521[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
1.113 + 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
1.114 + 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
1.115 + 0xFFFFFFFF,0x000001FF};
1.116 +#elif BN_BITS2 == 16
1.117 +static const BN_ULONG _nist_p_192[] = {0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFE,
1.118 + 0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF};
1.119 +static const BN_ULONG _nist_p_224[] = {0x0001,0x0000,0x0000,0x0000,0x0000,
1.120 + 0x0000,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF};
1.121 +static const BN_ULONG _nist_p_256[] = {0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
1.122 + 0xFFFF,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0001,0x0000,0xFFFF,
1.123 + 0xFFFF};
1.124 +static const BN_ULONG _nist_p_384[] = {0xFFFF,0xFFFF,0x0000,0x0000,0x0000,
1.125 + 0x0000,0xFFFF,0xFFFF,0xFFFE,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
1.126 + 0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF};
1.127 +static const BN_ULONG _nist_p_521[] = {0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
1.128 + 0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
1.129 + 0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
1.130 + 0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0x01FF};
1.131 +#elif BN_BITS2 == 8
1.132 +static const BN_ULONG _nist_p_192[] = {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
1.133 + 0xFE,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
1.134 + 0xFF,0xFF};
1.135 +static const BN_ULONG _nist_p_224[] = {0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
1.136 + 0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
1.137 + 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF};
1.138 +static const BN_ULONG _nist_p_256[] = {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
1.139 + 0xFF,0xFF,0xFF,0xFF,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
1.140 + 0x00,0x00,0x01,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF};
1.141 +static const BN_ULONG _nist_p_384[] = {0xFF,0xFF,0xFF,0xFF,0x00,0x00,0x00,0x00,
1.142 + 0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFF,0xFF,
1.143 + 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
1.144 + 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF};
1.145 +static const BN_ULONG _nist_p_521[] = {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
1.146 + 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
1.147 + 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
1.148 + 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
1.149 + 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
1.150 + 0xFF,0x01};
1.151 +#endif
1.152 +
1.153 +
1.154 +
1.155 +
1.156 +EXPORT_C const BIGNUM *BN_get0_nist_prime_192(void)
1.157 + {
1.158 +#ifndef EMULATOR
1.159 + static BIGNUM const_nist_192 = { (BN_ULONG *)_nist_p_192,
1.160 + BN_NIST_192_TOP, BN_NIST_192_TOP, 0, BN_FLG_STATIC_DATA };
1.161 +#else
1.162 + static const BIGNUM const_nist_192 = { (BN_ULONG *)_nist_p_192,
1.163 + BN_NIST_192_TOP, BN_NIST_192_TOP, 0, BN_FLG_STATIC_DATA };
1.164 +
1.165 +#endif
1.166 + return &const_nist_192;
1.167 + }
1.168 +
1.169 +EXPORT_C const BIGNUM *BN_get0_nist_prime_224(void)
1.170 + {
1.171 +#ifndef EMULATOR
1.172 + static BIGNUM const_nist_224 = { (BN_ULONG *)_nist_p_224,
1.173 + BN_NIST_224_TOP, BN_NIST_224_TOP, 0, BN_FLG_STATIC_DATA };
1.174 +#else
1.175 + static const BIGNUM const_nist_224 = { (BN_ULONG *)_nist_p_224,
1.176 + BN_NIST_224_TOP, BN_NIST_224_TOP, 0, BN_FLG_STATIC_DATA };
1.177 +
1.178 +#endif
1.179 +
1.180 + return &const_nist_224;
1.181 + }
1.182 +
1.183 +EXPORT_C const BIGNUM *BN_get0_nist_prime_256(void)
1.184 + {
1.185 +#ifndef EMULATOR
1.186 + static BIGNUM const_nist_256 = { (BN_ULONG *)_nist_p_256,
1.187 + BN_NIST_256_TOP, BN_NIST_256_TOP, 0, BN_FLG_STATIC_DATA };
1.188 +#else
1.189 + static const BIGNUM const_nist_256 = { (BN_ULONG *)_nist_p_256,
1.190 + BN_NIST_256_TOP, BN_NIST_256_TOP, 0, BN_FLG_STATIC_DATA };
1.191 +
1.192 +#endif
1.193 + return &const_nist_256;
1.194 + }
1.195 +
1.196 +EXPORT_C const BIGNUM *BN_get0_nist_prime_384(void)
1.197 + {
1.198 +#ifndef EMULATOR
1.199 + static BIGNUM const_nist_384 = { (BN_ULONG *)_nist_p_384,
1.200 + BN_NIST_384_TOP, BN_NIST_384_TOP, 0, BN_FLG_STATIC_DATA };
1.201 +#else
1.202 + static const BIGNUM const_nist_384 = { (BN_ULONG *)_nist_p_384,
1.203 + BN_NIST_384_TOP, BN_NIST_384_TOP, 0, BN_FLG_STATIC_DATA };
1.204 +
1.205 +#endif
1.206 + return &const_nist_384;
1.207 + }
1.208 +
1.209 +EXPORT_C const BIGNUM *BN_get0_nist_prime_521(void)
1.210 + {
1.211 +#ifndef EMULATOR
1.212 + static BIGNUM const_nist_521 = { (BN_ULONG *)_nist_p_521,
1.213 + BN_NIST_521_TOP, BN_NIST_521_TOP, 0, BN_FLG_STATIC_DATA };
1.214 +#else
1.215 + static const BIGNUM const_nist_521 = { (BN_ULONG *)_nist_p_521,
1.216 + BN_NIST_521_TOP, BN_NIST_521_TOP, 0, BN_FLG_STATIC_DATA };
1.217 +
1.218 +#endif
1.219 + return &const_nist_521;
1.220 + }
1.221 +
1.222 +/* some misc internal functions */
1.223 +#if BN_BITS2 != 64
1.224 +#ifndef EMULATOR
1.225 +static BN_ULONG _256_data[BN_NIST_256_TOP*6];
1.226 +static int _is_set_256_data = 0;
1.227 +static void _init_256_data(void);
1.228 +
1.229 +static BN_ULONG _384_data[BN_NIST_384_TOP*8];
1.230 +static int _is_set_384_data = 0;
1.231 +static void _init_384_data(void);
1.232 +#else
1.233 +GET_STATIC_ARRAY_FROM_TLS(_256_data,bn_nist,BN_ULONG)
1.234 +#define _256_data (GET_WSD_VAR_NAME(_256_data,bn_nist, s)())
1.235 +GET_STATIC_VAR_FROM_TLS(_is_set_256_data,bn_nist,int)
1.236 +#define _is_set_256_data (*GET_WSD_VAR_NAME(_is_set_256_data,bn_nist, s)())
1.237 +
1.238 +GET_STATIC_ARRAY_FROM_TLS(_384_data,bn_nist,BN_ULONG)
1.239 +#define _384_data (GET_WSD_VAR_NAME(_384_data,bn_nist, s)())
1.240 +GET_STATIC_VAR_FROM_TLS(_is_set_384_data,bn_nist,int)
1.241 +#define _is_set_384_data (*GET_WSD_VAR_NAME(_is_set_384_data,bn_nist, s)())
1.242 +#endif
1.243 +#endif
1.244 +
1.245 +#define BN_NIST_ADD_ONE(a) while (!(++(*(a)))) ++(a);
1.246 +
1.247 +static void nist_cp_bn_0(BN_ULONG *buf, BN_ULONG *a, int top, int max)
1.248 + {
1.249 + int i;
1.250 + BN_ULONG *_tmp1 = (buf), *_tmp2 = (a);
1.251 + for (i = (top); i != 0; i--)
1.252 + *_tmp1++ = *_tmp2++;
1.253 + for (i = (max) - (top); i != 0; i--)
1.254 + *_tmp1++ = (BN_ULONG) 0;
1.255 + }
1.256 +
1.257 +static void nist_cp_bn(BN_ULONG *buf, BN_ULONG *a, int top)
1.258 + {
1.259 + int i;
1.260 + BN_ULONG *_tmp1 = (buf), *_tmp2 = (a);
1.261 + for (i = (top); i != 0; i--)
1.262 + *_tmp1++ = *_tmp2++;
1.263 + }
1.264 +
1.265 +#if BN_BITS2 == 64
1.266 +#define bn_cp_64(to, n, from, m) (to)[n] = (from)[m];
1.267 +#define bn_64_set_0(to, n) (to)[n] = (BN_ULONG)0;
1.268 +/* TBD */
1.269 +#define bn_cp_32(to, n, from, m) (to)[n] = (from)[m];
1.270 +#define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0;
1.271 +#else
1.272 +#define bn_cp_64(to, n, from, m) \
1.273 + { \
1.274 + bn_cp_32(to, (n)*2, from, (m)*2); \
1.275 + bn_cp_32(to, (n)*2+1, from, (m)*2+1); \
1.276 + }
1.277 +#define bn_64_set_0(to, n) \
1.278 + { \
1.279 + bn_32_set_0(to, (n)*2); \
1.280 + bn_32_set_0(to, (n)*2+1); \
1.281 + }
1.282 +#if BN_BITS2 == 32
1.283 +#define bn_cp_32(to, n, from, m) (to)[n] = (from)[m];
1.284 +#define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0;
1.285 +#elif BN_BITS2 == 16
1.286 +#define bn_cp_32(to, n, from, m) \
1.287 + { \
1.288 + (to)[(n)*2] = (from)[(m)*2]; \
1.289 + (to)[(n)*2+1] = (from)[(m)*2+1];\
1.290 + }
1.291 +#define bn_32_set_0(to, n) { (to)[(n)*2] = 0; (to)[(n)*2+1] = 0; }
1.292 +#elif BN_BITS2 == 8
1.293 +#define bn_cp_32(to, n, from, m) \
1.294 + { \
1.295 + (to)[(n)*4] = (from)[(m)*4]; \
1.296 + (to)[(n)*4+1] = (from)[(m)*4+1];\
1.297 + (to)[(n)*4+2] = (from)[(m)*4+2];\
1.298 + (to)[(n)*4+3] = (from)[(m)*4+3];\
1.299 + }
1.300 +#define bn_32_set_0(to, n) \
1.301 + { (to)[(n)*4] = (BN_ULONG)0; (to)[(n)*4+1] = (BN_ULONG)0; \
1.302 + (to)[(n)*4+2] = (BN_ULONG)0; (to)[(n)*4+3] = (BN_ULONG)0; }
1.303 +#endif
1.304 +#endif /* BN_BITS2 != 64 */
1.305 +
1.306 +
1.307 +#define nist_set_192(to, from, a1, a2, a3) \
1.308 + { \
1.309 + if (a3 != 0) bn_cp_64(to, 0, from, (a3) - 3) else bn_64_set_0(to, 0)\
1.310 + bn_cp_64(to, 1, from, (a2) - 3) \
1.311 + if (a1 != 0) bn_cp_64(to, 2, from, (a1) - 3) else bn_64_set_0(to, 2)\
1.312 + }
1.313 +
1.314 +EXPORT_C int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
1.315 + BN_CTX *ctx)
1.316 + {
1.317 + int top = a->top, i;
1.318 + BN_ULONG carry = 0;
1.319 + register BN_ULONG *r_d, *a_d = a->d;
1.320 + BN_ULONG t_d[BN_NIST_192_TOP],
1.321 + buf[BN_NIST_192_TOP];
1.322 +
1.323 + i = BN_ucmp(field, a);
1.324 + if (i == 0)
1.325 + {
1.326 + BN_zero(r);
1.327 + return 1;
1.328 + }
1.329 + else if (i > 0)
1.330 + return (r == a) ? 1 : (BN_copy(r ,a) != NULL);
1.331 +
1.332 + if (top == BN_NIST_192_TOP)
1.333 + return BN_usub(r, a, field);
1.334 +
1.335 + if (r != a)
1.336 + {
1.337 + if (!bn_wexpand(r, BN_NIST_192_TOP))
1.338 + return 0;
1.339 + r_d = r->d;
1.340 + nist_cp_bn(r_d, a_d, BN_NIST_192_TOP);
1.341 + }
1.342 + else
1.343 + r_d = a_d;
1.344 +
1.345 + nist_cp_bn_0(buf, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP, BN_NIST_192_TOP);
1.346 +
1.347 +#if defined(OPENSSL_SYS_VMS) && defined(__DECC)
1.348 +# pragma message save
1.349 +# pragma message disable BADSUBSCRIPT
1.350 +#endif
1.351 +
1.352 + nist_set_192(t_d, buf, 0, 3, 3);
1.353 + if (bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP))
1.354 + ++carry;
1.355 +
1.356 + nist_set_192(t_d, buf, 4, 4, 0);
1.357 + if (bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP))
1.358 + ++carry;
1.359 +
1.360 +#if defined(OPENSSL_SYS_VMS) && defined(__DECC)
1.361 +# pragma message restore
1.362 +#endif
1.363 +
1.364 + nist_set_192(t_d, buf, 5, 5, 5)
1.365 + if (bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP))
1.366 + ++carry;
1.367 +
1.368 + while (carry)
1.369 + {
1.370 + if (bn_sub_words(r_d, r_d, _nist_p_192, BN_NIST_192_TOP))
1.371 + --carry;
1.372 + }
1.373 + r->top = BN_NIST_192_TOP;
1.374 + bn_correct_top(r);
1.375 + if (BN_ucmp(r, field) >= 0)
1.376 + {
1.377 + bn_sub_words(r_d, r_d, _nist_p_192, BN_NIST_192_TOP);
1.378 + bn_correct_top(r);
1.379 + }
1.380 +
1.381 + bn_check_top(r);
1.382 + return 1;
1.383 + }
1.384 +
1.385 +#define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \
1.386 + { \
1.387 + if (a7 != 0) bn_cp_32(to, 0, from, (a7) - 7) else bn_32_set_0(to, 0)\
1.388 + if (a6 != 0) bn_cp_32(to, 1, from, (a6) - 7) else bn_32_set_0(to, 1)\
1.389 + if (a5 != 0) bn_cp_32(to, 2, from, (a5) - 7) else bn_32_set_0(to, 2)\
1.390 + if (a4 != 0) bn_cp_32(to, 3, from, (a4) - 7) else bn_32_set_0(to, 3)\
1.391 + if (a3 != 0) bn_cp_32(to, 4, from, (a3) - 7) else bn_32_set_0(to, 4)\
1.392 + if (a2 != 0) bn_cp_32(to, 5, from, (a2) - 7) else bn_32_set_0(to, 5)\
1.393 + if (a1 != 0) bn_cp_32(to, 6, from, (a1) - 7) else bn_32_set_0(to, 6)\
1.394 + }
1.395 +
1.396 +EXPORT_C int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
1.397 + BN_CTX *ctx)
1.398 + {
1.399 +#if BN_BITS2 != 64
1.400 + int top = a->top, i;
1.401 + int carry = 0;
1.402 + BN_ULONG *r_d, *a_d = a->d;
1.403 + BN_ULONG t_d[BN_NIST_224_TOP],
1.404 + buf[BN_NIST_224_TOP];
1.405 +
1.406 + i = BN_ucmp(field, a);
1.407 + if (i == 0)
1.408 + {
1.409 + BN_zero(r);
1.410 + return 1;
1.411 + }
1.412 + else if (i > 0)
1.413 + return (r == a)? 1 : (BN_copy(r ,a) != NULL);
1.414 +
1.415 + if (top == BN_NIST_224_TOP)
1.416 + return BN_usub(r, a, field);
1.417 +
1.418 + if (r != a)
1.419 + {
1.420 + if (!bn_wexpand(r, BN_NIST_224_TOP))
1.421 + return 0;
1.422 + r_d = r->d;
1.423 + nist_cp_bn(r_d, a_d, BN_NIST_224_TOP);
1.424 + }
1.425 + else
1.426 + r_d = a_d;
1.427 +
1.428 + nist_cp_bn_0(buf, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP, BN_NIST_224_TOP);
1.429 +
1.430 + nist_set_224(t_d, buf, 10, 9, 8, 7, 0, 0, 0);
1.431 + if (bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP))
1.432 + ++carry;
1.433 + nist_set_224(t_d, buf, 0, 13, 12, 11, 0, 0, 0);
1.434 + if (bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP))
1.435 + ++carry;
1.436 + nist_set_224(t_d, buf, 13, 12, 11, 10, 9, 8, 7);
1.437 + if (bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP))
1.438 + --carry;
1.439 + nist_set_224(t_d, buf, 0, 0, 0, 0, 13, 12, 11);
1.440 + if (bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP))
1.441 + --carry;
1.442 +
1.443 + if (carry > 0)
1.444 + while (carry)
1.445 + {
1.446 + if (bn_sub_words(r_d,r_d,_nist_p_224,BN_NIST_224_TOP))
1.447 + --carry;
1.448 + }
1.449 + else if (carry < 0)
1.450 + while (carry)
1.451 + {
1.452 + if (bn_add_words(r_d,r_d,_nist_p_224,BN_NIST_224_TOP))
1.453 + ++carry;
1.454 + }
1.455 +
1.456 + r->top = BN_NIST_224_TOP;
1.457 + bn_correct_top(r);
1.458 + if (BN_ucmp(r, field) >= 0)
1.459 + {
1.460 + bn_sub_words(r_d, r_d, _nist_p_224, BN_NIST_224_TOP);
1.461 + bn_correct_top(r);
1.462 + }
1.463 + bn_check_top(r);
1.464 + return 1;
1.465 +#else
1.466 + return 0;
1.467 +#endif
1.468 + }
1.469 +
1.470 +#if BN_BITS2 != 64
1.471 +static void _init_256_data(void)
1.472 + {
1.473 + int i;
1.474 + BN_ULONG *tmp1 = _256_data;
1.475 + const BN_ULONG *tmp2 = tmp1;
1.476 +
1.477 + memcpy(tmp1, _nist_p_256, BN_NIST_256_TOP * sizeof(BN_ULONG));
1.478 + tmp1 += BN_NIST_256_TOP;
1.479 +
1.480 + for (i=0; i<5; i++)
1.481 + {
1.482 + bn_add_words(tmp1, _nist_p_256, tmp2, BN_NIST_256_TOP);
1.483 + tmp2 = tmp1;
1.484 + tmp1 += BN_NIST_256_TOP;
1.485 + }
1.486 + _is_set_256_data = 1;
1.487 + }
1.488 +#endif
1.489 +
1.490 +#define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \
1.491 + { \
1.492 + if (a8 != 0) bn_cp_32(to, 0, from, (a8) - 8) else bn_32_set_0(to, 0)\
1.493 + if (a7 != 0) bn_cp_32(to, 1, from, (a7) - 8) else bn_32_set_0(to, 1)\
1.494 + if (a6 != 0) bn_cp_32(to, 2, from, (a6) - 8) else bn_32_set_0(to, 2)\
1.495 + if (a5 != 0) bn_cp_32(to, 3, from, (a5) - 8) else bn_32_set_0(to, 3)\
1.496 + if (a4 != 0) bn_cp_32(to, 4, from, (a4) - 8) else bn_32_set_0(to, 4)\
1.497 + if (a3 != 0) bn_cp_32(to, 5, from, (a3) - 8) else bn_32_set_0(to, 5)\
1.498 + if (a2 != 0) bn_cp_32(to, 6, from, (a2) - 8) else bn_32_set_0(to, 6)\
1.499 + if (a1 != 0) bn_cp_32(to, 7, from, (a1) - 8) else bn_32_set_0(to, 7)\
1.500 + }
1.501 +
1.502 +EXPORT_C int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
1.503 + BN_CTX *ctx)
1.504 + {
1.505 +#if BN_BITS2 != 64
1.506 + int i, top = a->top;
1.507 + int carry = 0;
1.508 + register BN_ULONG *a_d = a->d, *r_d;
1.509 + BN_ULONG t_d[BN_NIST_256_TOP],
1.510 + t_d2[BN_NIST_256_TOP],
1.511 + buf[BN_NIST_256_TOP];
1.512 +
1.513 + if (!_is_set_256_data)
1.514 + {
1.515 + CRYPTO_w_lock(CRYPTO_LOCK_BN);
1.516 +
1.517 + if (!_is_set_256_data)
1.518 + _init_256_data();
1.519 +
1.520 + CRYPTO_w_unlock(CRYPTO_LOCK_BN);
1.521 + }
1.522 +
1.523 + i = BN_ucmp(field, a);
1.524 + if (i == 0)
1.525 + {
1.526 + BN_zero(r);
1.527 + return 1;
1.528 + }
1.529 + else if (i > 0)
1.530 + return (r == a)? 1 : (BN_copy(r ,a) != NULL);
1.531 +
1.532 + if (top == BN_NIST_256_TOP)
1.533 + return BN_usub(r, a, field);
1.534 +
1.535 + if (r != a)
1.536 + {
1.537 + if (!bn_wexpand(r, BN_NIST_256_TOP))
1.538 + return 0;
1.539 + r_d = r->d;
1.540 + nist_cp_bn(r_d, a_d, BN_NIST_256_TOP);
1.541 + }
1.542 + else
1.543 + r_d = a_d;
1.544 +
1.545 + nist_cp_bn_0(buf, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP, BN_NIST_256_TOP);
1.546 +
1.547 + /*S1*/
1.548 + nist_set_256(t_d, buf, 15, 14, 13, 12, 11, 0, 0, 0);
1.549 + /*S2*/
1.550 + nist_set_256(t_d2,buf, 0, 15, 14, 13, 12, 0, 0, 0);
1.551 + if (bn_add_words(t_d, t_d, t_d2, BN_NIST_256_TOP))
1.552 + carry = 2;
1.553 + /* left shift */
1.554 + {
1.555 + register BN_ULONG *ap,t,c;
1.556 + ap = t_d;
1.557 + c=0;
1.558 + for (i = BN_NIST_256_TOP; i != 0; --i)
1.559 + {
1.560 + t= *ap;
1.561 + *(ap++)=((t<<1)|c)&BN_MASK2;
1.562 + c=(t & BN_TBIT)?1:0;
1.563 + }
1.564 + if (c)
1.565 + ++carry;
1.566 + }
1.567 +
1.568 + if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))
1.569 + ++carry;
1.570 + /*S3*/
1.571 + nist_set_256(t_d, buf, 15, 14, 0, 0, 0, 10, 9, 8);
1.572 + if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))
1.573 + ++carry;
1.574 + /*S4*/
1.575 + nist_set_256(t_d, buf, 8, 13, 15, 14, 13, 11, 10, 9);
1.576 + if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))
1.577 + ++carry;
1.578 + /*D1*/
1.579 + nist_set_256(t_d, buf, 10, 8, 0, 0, 0, 13, 12, 11);
1.580 + if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
1.581 + --carry;
1.582 + /*D2*/
1.583 + nist_set_256(t_d, buf, 11, 9, 0, 0, 15, 14, 13, 12);
1.584 + if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
1.585 + --carry;
1.586 + /*D3*/
1.587 + nist_set_256(t_d, buf, 12, 0, 10, 9, 8, 15, 14, 13);
1.588 + if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
1.589 + --carry;
1.590 + /*D4*/
1.591 + nist_set_256(t_d, buf, 13, 0, 11, 10, 9, 0, 15, 14);
1.592 + if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
1.593 + --carry;
1.594 +
1.595 + if (carry)
1.596 + {
1.597 + if (carry > 0)
1.598 + bn_sub_words(r_d, r_d, _256_data + BN_NIST_256_TOP *
1.599 + --carry, BN_NIST_256_TOP);
1.600 + else
1.601 + {
1.602 + carry = -carry;
1.603 + bn_add_words(r_d, r_d, _256_data + BN_NIST_256_TOP *
1.604 + --carry, BN_NIST_256_TOP);
1.605 + }
1.606 + }
1.607 +
1.608 + r->top = BN_NIST_256_TOP;
1.609 + bn_correct_top(r);
1.610 + if (BN_ucmp(r, field) >= 0)
1.611 + {
1.612 + bn_sub_words(r_d, r_d, _nist_p_256, BN_NIST_256_TOP);
1.613 + bn_correct_top(r);
1.614 + }
1.615 + bn_check_top(r);
1.616 + return 1;
1.617 +#else
1.618 + return 0;
1.619 +#endif
1.620 + }
1.621 +
1.622 +#if BN_BITS2 != 64
1.623 +static void _init_384_data(void)
1.624 + {
1.625 + int i;
1.626 + BN_ULONG *tmp1 = _384_data;
1.627 + const BN_ULONG *tmp2 = tmp1;
1.628 +
1.629 + memcpy(tmp1, _nist_p_384, BN_NIST_384_TOP * sizeof(BN_ULONG));
1.630 + tmp1 += BN_NIST_384_TOP;
1.631 +
1.632 + for (i=0; i<7; i++)
1.633 + {
1.634 + bn_add_words(tmp1, _nist_p_384, tmp2, BN_NIST_384_TOP);
1.635 + tmp2 = tmp1;
1.636 + tmp1 += BN_NIST_384_TOP;
1.637 + }
1.638 + _is_set_384_data = 1;
1.639 + }
1.640 +#endif
1.641 +
1.642 +#define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \
1.643 + { \
1.644 + if (a12 != 0) bn_cp_32(to, 0, from, (a12) - 12) else bn_32_set_0(to, 0)\
1.645 + if (a11 != 0) bn_cp_32(to, 1, from, (a11) - 12) else bn_32_set_0(to, 1)\
1.646 + if (a10 != 0) bn_cp_32(to, 2, from, (a10) - 12) else bn_32_set_0(to, 2)\
1.647 + if (a9 != 0) bn_cp_32(to, 3, from, (a9) - 12) else bn_32_set_0(to, 3)\
1.648 + if (a8 != 0) bn_cp_32(to, 4, from, (a8) - 12) else bn_32_set_0(to, 4)\
1.649 + if (a7 != 0) bn_cp_32(to, 5, from, (a7) - 12) else bn_32_set_0(to, 5)\
1.650 + if (a6 != 0) bn_cp_32(to, 6, from, (a6) - 12) else bn_32_set_0(to, 6)\
1.651 + if (a5 != 0) bn_cp_32(to, 7, from, (a5) - 12) else bn_32_set_0(to, 7)\
1.652 + if (a4 != 0) bn_cp_32(to, 8, from, (a4) - 12) else bn_32_set_0(to, 8)\
1.653 + if (a3 != 0) bn_cp_32(to, 9, from, (a3) - 12) else bn_32_set_0(to, 9)\
1.654 + if (a2 != 0) bn_cp_32(to, 10, from, (a2) - 12) else bn_32_set_0(to, 10)\
1.655 + if (a1 != 0) bn_cp_32(to, 11, from, (a1) - 12) else bn_32_set_0(to, 11)\
1.656 + }
1.657 +
1.658 +EXPORT_C int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
1.659 + BN_CTX *ctx)
1.660 + {
1.661 +#if BN_BITS2 != 64
1.662 + int i, top = a->top;
1.663 + int carry = 0;
1.664 + register BN_ULONG *r_d, *a_d = a->d;
1.665 + BN_ULONG t_d[BN_NIST_384_TOP],
1.666 + buf[BN_NIST_384_TOP];
1.667 +
1.668 + if (!_is_set_384_data)
1.669 + {
1.670 + CRYPTO_w_lock(CRYPTO_LOCK_BN);
1.671 +
1.672 + if (!_is_set_384_data)
1.673 + _init_384_data();
1.674 +
1.675 + CRYPTO_w_unlock(CRYPTO_LOCK_BN);
1.676 + }
1.677 +
1.678 + i = BN_ucmp(field, a);
1.679 + if (i == 0)
1.680 + {
1.681 + BN_zero(r);
1.682 + return 1;
1.683 + }
1.684 + else if (i > 0)
1.685 + return (r == a)? 1 : (BN_copy(r ,a) != NULL);
1.686 +
1.687 + if (top == BN_NIST_384_TOP)
1.688 + return BN_usub(r, a, field);
1.689 +
1.690 + if (r != a)
1.691 + {
1.692 + if (!bn_wexpand(r, BN_NIST_384_TOP))
1.693 + return 0;
1.694 + r_d = r->d;
1.695 + nist_cp_bn(r_d, a_d, BN_NIST_384_TOP);
1.696 + }
1.697 + else
1.698 + r_d = a_d;
1.699 +
1.700 + nist_cp_bn_0(buf, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP, BN_NIST_384_TOP);
1.701 +
1.702 + /*S1*/
1.703 + nist_set_256(t_d, buf, 0, 0, 0, 0, 0, 23-4, 22-4, 21-4);
1.704 + /* left shift */
1.705 + {
1.706 + register BN_ULONG *ap,t,c;
1.707 + ap = t_d;
1.708 + c=0;
1.709 + for (i = BN_NIST_256_TOP; i != 0; --i)
1.710 + {
1.711 + t= *ap;
1.712 + *(ap++)=((t<<1)|c)&BN_MASK2;
1.713 + c=(t & BN_TBIT)?1:0;
1.714 + }
1.715 + }
1.716 + if (bn_add_words(r_d+(128/BN_BITS2), r_d+(128/BN_BITS2),
1.717 + t_d, BN_NIST_256_TOP))
1.718 + ++carry;
1.719 + /*S2 */
1.720 + if (bn_add_words(r_d, r_d, buf, BN_NIST_384_TOP))
1.721 + ++carry;
1.722 + /*S3*/
1.723 + nist_set_384(t_d,buf,20,19,18,17,16,15,14,13,12,23,22,21);
1.724 + if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))
1.725 + ++carry;
1.726 + /*S4*/
1.727 + nist_set_384(t_d,buf,19,18,17,16,15,14,13,12,20,0,23,0);
1.728 + if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))
1.729 + ++carry;
1.730 + /*S5*/
1.731 + nist_set_256(t_d, buf, 0, 0, 0, 0, 23-4, 22-4, 21-4, 20-4);
1.732 + if (bn_add_words(r_d+(128/BN_BITS2), r_d+(128/BN_BITS2),
1.733 + t_d, BN_NIST_256_TOP))
1.734 + ++carry;
1.735 + /*S6*/
1.736 + nist_set_384(t_d,buf,0,0,0,0,0,0,23,22,21,0,0,20);
1.737 + if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))
1.738 + ++carry;
1.739 + /*D1*/
1.740 + nist_set_384(t_d,buf,22,21,20,19,18,17,16,15,14,13,12,23);
1.741 + if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))
1.742 + --carry;
1.743 + /*D2*/
1.744 + nist_set_384(t_d,buf,0,0,0,0,0,0,0,23,22,21,20,0);
1.745 + if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))
1.746 + --carry;
1.747 + /*D3*/
1.748 + nist_set_384(t_d,buf,0,0,0,0,0,0,0,23,23,0,0,0);
1.749 + if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))
1.750 + --carry;
1.751 +
1.752 + if (carry)
1.753 + {
1.754 + if (carry > 0)
1.755 + bn_sub_words(r_d, r_d, _384_data + BN_NIST_384_TOP *
1.756 + --carry, BN_NIST_384_TOP);
1.757 + else
1.758 + {
1.759 + carry = -carry;
1.760 + bn_add_words(r_d, r_d, _384_data + BN_NIST_384_TOP *
1.761 + --carry, BN_NIST_384_TOP);
1.762 + }
1.763 + }
1.764 +
1.765 + r->top = BN_NIST_384_TOP;
1.766 + bn_correct_top(r);
1.767 + if (BN_ucmp(r, field) >= 0)
1.768 + {
1.769 + bn_sub_words(r_d, r_d, _nist_p_384, BN_NIST_384_TOP);
1.770 + bn_correct_top(r);
1.771 + }
1.772 + bn_check_top(r);
1.773 + return 1;
1.774 +#else
1.775 + return 0;
1.776 +#endif
1.777 + }
1.778 +
1.779 +EXPORT_C int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
1.780 + BN_CTX *ctx)
1.781 + {
1.782 +#if BN_BITS2 == 64
1.783 +#define BN_NIST_521_TOP_MASK (BN_ULONG)0x1FF
1.784 +#elif BN_BITS2 == 32
1.785 +#define BN_NIST_521_TOP_MASK (BN_ULONG)0x1FF
1.786 +#elif BN_BITS2 == 16
1.787 +#define BN_NIST_521_TOP_MASK (BN_ULONG)0x1FF
1.788 +#elif BN_BITS2 == 8
1.789 +#define BN_NIST_521_TOP_MASK (BN_ULONG)0x1
1.790 +#endif
1.791 + int top, ret = 0;
1.792 + BN_ULONG *r_d;
1.793 + BIGNUM *tmp;
1.794 +
1.795 + /* check whether a reduction is necessary */
1.796 + top = a->top;
1.797 + if (top < BN_NIST_521_TOP || ( top == BN_NIST_521_TOP &&
1.798 + (!(a->d[BN_NIST_521_TOP-1] & ~(BN_NIST_521_TOP_MASK)))))
1.799 + return (r == a)? 1 : (BN_copy(r ,a) != NULL);
1.800 +
1.801 + BN_CTX_start(ctx);
1.802 + tmp = BN_CTX_get(ctx);
1.803 + if (!tmp)
1.804 + goto err;
1.805 +
1.806 + if (!bn_wexpand(tmp, BN_NIST_521_TOP))
1.807 + goto err;
1.808 + nist_cp_bn(tmp->d, a->d, BN_NIST_521_TOP);
1.809 +
1.810 + tmp->top = BN_NIST_521_TOP;
1.811 + tmp->d[BN_NIST_521_TOP-1] &= BN_NIST_521_TOP_MASK;
1.812 + bn_correct_top(tmp);
1.813 +
1.814 + if (!BN_rshift(r, a, 521))
1.815 + goto err;
1.816 +
1.817 + if (!BN_uadd(r, tmp, r))
1.818 + goto err;
1.819 + top = r->top;
1.820 + r_d = r->d;
1.821 + if (top == BN_NIST_521_TOP &&
1.822 + (r_d[BN_NIST_521_TOP-1] & ~(BN_NIST_521_TOP_MASK)))
1.823 + {
1.824 + BN_NIST_ADD_ONE(r_d)
1.825 + r_d[BN_NIST_521_TOP-1] &= BN_NIST_521_TOP_MASK;
1.826 + }
1.827 + bn_correct_top(r);
1.828 +
1.829 + ret = 1;
1.830 +err:
1.831 + BN_CTX_end(ctx);
1.832 +
1.833 + bn_check_top(r);
1.834 + return ret;
1.835 + }