Symaptic: os/ossrv/ssl/libcrypto/src/crypto/bn/bn

     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  © Portions copyright (c) 2006 Nokia Corporation.  All rights reserved.

    60  */

    64 #include "bn_lcl.h"

    65 #include "cryptlib.h"

    66 #if (defined(SYMBIAN) && (defined(__WINSCW__) || defined(__WINS__)))

    67 #include "libcrypto_wsd_macros.h"

    68 #include "libcrypto_wsd.h"

    69 #endif

    72 #define BN_NIST_192_TOP	(192+BN_BITS2-1)/BN_BITS2

    73 #define BN_NIST_224_TOP	(224+BN_BITS2-1)/BN_BITS2

    74 #define BN_NIST_256_TOP	(256+BN_BITS2-1)/BN_BITS2

    75 #define BN_NIST_384_TOP	(384+BN_BITS2-1)/BN_BITS2

    76 #define BN_NIST_521_TOP	(521+BN_BITS2-1)/BN_BITS2

    79 #if BN_BITS2 == 64

    80 static const BN_ULONG _nist_p_192[] =

    81 	{0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFEULL,

    82 	0xFFFFFFFFFFFFFFFFULL};

    83 static const BN_ULONG _nist_p_224[] =

    84 	{0x0000000000000001ULL,0xFFFFFFFF00000000ULL,

    85 	0xFFFFFFFFFFFFFFFFULL,0x00000000FFFFFFFFULL};

    86 static const BN_ULONG _nist_p_256[] =

    87 	{0xFFFFFFFFFFFFFFFFULL,0x00000000FFFFFFFFULL,

    88 	0x0000000000000000ULL,0xFFFFFFFF00000001ULL};

    89 static const BN_ULONG _nist_p_384[] =

    90 	{0x00000000FFFFFFFFULL,0xFFFFFFFF00000000ULL,

    91 	0xFFFFFFFFFFFFFFFEULL,0xFFFFFFFFFFFFFFFFULL,

    92 	0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL};

    93 static const BN_ULONG _nist_p_521[] =

    94 	{0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,

    95 	0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,

    96 	0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,

    97 	0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,

    98 	0x00000000000001FFULL};

    99 #elif BN_BITS2 == 32

   100 static const BN_ULONG _nist_p_192[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFE,

   101 	0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};

   102 static const BN_ULONG _nist_p_224[] = {0x00000001,0x00000000,0x00000000,

   103 	0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};

   104 static const BN_ULONG _nist_p_256[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,

   105 	0x00000000,0x00000000,0x00000000,0x00000001,0xFFFFFFFF};

   106 static const BN_ULONG _nist_p_384[] = {0xFFFFFFFF,0x00000000,0x00000000,

   107 	0xFFFFFFFF,0xFFFFFFFE,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,

   108 	0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};

   109 static const BN_ULONG _nist_p_521[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,

   110 	0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,

   111 	0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,

   112 	0xFFFFFFFF,0x000001FF};

   113 #elif BN_BITS2 == 16

   114 static const BN_ULONG _nist_p_192[] = {0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFE,

   115 	0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF};

   116 static const BN_ULONG _nist_p_224[] = {0x0001,0x0000,0x0000,0x0000,0x0000,

   117 	0x0000,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF};

   118 static const BN_ULONG _nist_p_256[] = {0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,

   119 	0xFFFF,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0001,0x0000,0xFFFF,

   120 	0xFFFF};

   121 static const BN_ULONG _nist_p_384[] = {0xFFFF,0xFFFF,0x0000,0x0000,0x0000,

   122 	0x0000,0xFFFF,0xFFFF,0xFFFE,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,

   123 	0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF};

   124 static const BN_ULONG _nist_p_521[] = {0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,

   125 	0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,

   126 	0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,

   127 	0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0x01FF};

   128 #elif BN_BITS2 == 8

   129 static const BN_ULONG _nist_p_192[] = {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,

   130 	0xFE,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,

   131 	0xFF,0xFF};

   132 static const BN_ULONG _nist_p_224[] = {0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,

   133 	0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,

   134 	0xFF,0xFF,0xFF,0xFF,0xFF,0xFF};

   135 static const BN_ULONG _nist_p_256[] = {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,

   136 	0xFF,0xFF,0xFF,0xFF,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,

   137 	0x00,0x00,0x01,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF};

   138 static const BN_ULONG _nist_p_384[] = {0xFF,0xFF,0xFF,0xFF,0x00,0x00,0x00,0x00,

   139 	0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFF,0xFF,

   140 	0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,

   141 	0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF};

   142 static const BN_ULONG _nist_p_521[] = {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,

   143 	0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,

   144 	0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,

   145 	0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,

   146 	0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,

   147 	0xFF,0x01};

   148 #endif

   153 EXPORT_C const BIGNUM *BN_get0_nist_prime_192(void)

   154 	{

   155 #ifndef EMULATOR

   156 	static BIGNUM const_nist_192 = { (BN_ULONG *)_nist_p_192,

   157 		BN_NIST_192_TOP, BN_NIST_192_TOP, 0, BN_FLG_STATIC_DATA };

   158 #else

   159 	static const BIGNUM const_nist_192 = { (BN_ULONG *)_nist_p_192,

   160 		BN_NIST_192_TOP, BN_NIST_192_TOP, 0, BN_FLG_STATIC_DATA };

   162 #endif

   163 	return &const_nist_192;

   164 	}

   166 EXPORT_C const BIGNUM *BN_get0_nist_prime_224(void)

   167 	{

   168 #ifndef EMULATOR

   169 	static BIGNUM const_nist_224 = { (BN_ULONG *)_nist_p_224,

   170 		BN_NIST_224_TOP, BN_NIST_224_TOP, 0, BN_FLG_STATIC_DATA };

   171 #else

   172     static const  BIGNUM const_nist_224 = { (BN_ULONG *)_nist_p_224,

   173 		BN_NIST_224_TOP, BN_NIST_224_TOP, 0, BN_FLG_STATIC_DATA };

   175 #endif

   177 	return &const_nist_224;

   178 	}

   180 EXPORT_C const BIGNUM *BN_get0_nist_prime_256(void)

   181 	{

   182 #ifndef EMULATOR

   183 	static BIGNUM const_nist_256 = { (BN_ULONG *)_nist_p_256,

   184 		BN_NIST_256_TOP, BN_NIST_256_TOP, 0, BN_FLG_STATIC_DATA };

   185 #else

   186     static const BIGNUM const_nist_256 = { (BN_ULONG *)_nist_p_256,

   187 		BN_NIST_256_TOP, BN_NIST_256_TOP, 0, BN_FLG_STATIC_DATA };

   189 #endif

   190 	return &const_nist_256;

   191 	}

   193 EXPORT_C const BIGNUM *BN_get0_nist_prime_384(void)

   194 	{

   195 #ifndef EMULATOR

   196 	static BIGNUM const_nist_384 = { (BN_ULONG *)_nist_p_384,

   197 		BN_NIST_384_TOP, BN_NIST_384_TOP, 0, BN_FLG_STATIC_DATA };

   198 #else

   199     static const BIGNUM const_nist_384 = { (BN_ULONG *)_nist_p_384,

   200 		BN_NIST_384_TOP, BN_NIST_384_TOP, 0, BN_FLG_STATIC_DATA };

   202 #endif

   203 	return &const_nist_384;

   204 	}

   206 EXPORT_C const BIGNUM *BN_get0_nist_prime_521(void)

   207 	{

   208 #ifndef EMULATOR

   209 	static BIGNUM const_nist_521 = { (BN_ULONG *)_nist_p_521,

   210 		BN_NIST_521_TOP, BN_NIST_521_TOP, 0, BN_FLG_STATIC_DATA };

   211 #else

   212 	static const BIGNUM const_nist_521 = { (BN_ULONG *)_nist_p_521,

   213 		BN_NIST_521_TOP, BN_NIST_521_TOP, 0, BN_FLG_STATIC_DATA };

   215 #endif

   216 	return &const_nist_521;

   217 	}

   219 /* some misc internal functions */

   220 #if BN_BITS2 != 64

   221 #ifndef EMULATOR

   222 static BN_ULONG _256_data[BN_NIST_256_TOP*6];

   223 static int _is_set_256_data = 0;

   224 static void _init_256_data(void);

   226 static BN_ULONG _384_data[BN_NIST_384_TOP*8];

   227 static int _is_set_384_data = 0;

   228 static void _init_384_data(void);

   229 #else

   230 GET_STATIC_ARRAY_FROM_TLS(_256_data,bn_nist,BN_ULONG)

   231 #define _256_data (GET_WSD_VAR_NAME(_256_data,bn_nist, s)())

   232 GET_STATIC_VAR_FROM_TLS(_is_set_256_data,bn_nist,int)

   233 #define _is_set_256_data (*GET_WSD_VAR_NAME(_is_set_256_data,bn_nist, s)())

   235 GET_STATIC_ARRAY_FROM_TLS(_384_data,bn_nist,BN_ULONG)

   236 #define _384_data (GET_WSD_VAR_NAME(_384_data,bn_nist, s)())

   237 GET_STATIC_VAR_FROM_TLS(_is_set_384_data,bn_nist,int)

   238 #define _is_set_384_data (*GET_WSD_VAR_NAME(_is_set_384_data,bn_nist, s)())

   239 #endif

   240 #endif

   242 #define BN_NIST_ADD_ONE(a)	while (!(++(*(a)))) ++(a);

   244 static void nist_cp_bn_0(BN_ULONG *buf, BN_ULONG *a, int top, int max)

   245         {

   246 	int i;

   247         BN_ULONG *_tmp1 = (buf), *_tmp2 = (a);

   248         for (i = (top); i != 0; i--)

   249                 *_tmp1++ = *_tmp2++;

   250         for (i = (max) - (top); i != 0; i--)

   251                 *_tmp1++ = (BN_ULONG) 0;

   252         }

   254 static void nist_cp_bn(BN_ULONG *buf, BN_ULONG *a, int top)

   255         {

   256 	int i;

   257         BN_ULONG *_tmp1 = (buf), *_tmp2 = (a);

   258         for (i = (top); i != 0; i--)

   259                 *_tmp1++ = *_tmp2++;

   260         }

   262 #if BN_BITS2 == 64

   263 #define bn_cp_64(to, n, from, m)	(to)[n] = (from)[m];

   264 #define bn_64_set_0(to, n)		(to)[n] = (BN_ULONG)0;

   265 /* TBD */

   266 #define bn_cp_32(to, n, from, m)	(to)[n] = (from)[m];

   267 #define bn_32_set_0(to, n)		(to)[n] = (BN_ULONG)0;

   268 #else

   269 #define bn_cp_64(to, n, from, m) \

   270 	{ \

   271 	bn_cp_32(to, (n)*2, from, (m)*2); \

   272 	bn_cp_32(to, (n)*2+1, from, (m)*2+1); \

   273 	}

   274 #define bn_64_set_0(to, n) \

   275 	{ \

   276 	bn_32_set_0(to, (n)*2); \

   277 	bn_32_set_0(to, (n)*2+1); \

   278 	}

   279 #if BN_BITS2 == 32

   280 #define bn_cp_32(to, n, from, m)	(to)[n] = (from)[m];

   281 #define bn_32_set_0(to, n)		(to)[n] = (BN_ULONG)0;

   282 #elif BN_BITS2 == 16

   283 #define bn_cp_32(to, n, from, m) \

   284 	{ \

   285 	(to)[(n)*2]   = (from)[(m)*2];  \

   286 	(to)[(n)*2+1] = (from)[(m)*2+1];\

   287 	}

   288 #define bn_32_set_0(to, n) { (to)[(n)*2] = 0; (to)[(n)*2+1] = 0; }

   289 #elif BN_BITS2 == 8

   290 #define bn_cp_32(to, n, from, m) \

   291 	{ \

   292 	(to)[(n)*4]   = (from)[(m)*4];  \

   293 	(to)[(n)*4+1] = (from)[(m)*4+1];\

   294 	(to)[(n)*4+2] = (from)[(m)*4+2];\

   295 	(to)[(n)*4+3] = (from)[(m)*4+3];\

   296 	}

   297 #define bn_32_set_0(to, n) \

   298 	{ (to)[(n)*4]   = (BN_ULONG)0; (to)[(n)*4+1] = (BN_ULONG)0; \

   299 	  (to)[(n)*4+2] = (BN_ULONG)0; (to)[(n)*4+3] = (BN_ULONG)0; }

   300 #endif

   301 #endif /* BN_BITS2 != 64 */

   304 #define nist_set_192(to, from, a1, a2, a3) \

   305 	{ \

   306 	if (a3 != 0) bn_cp_64(to, 0, from, (a3) - 3) else bn_64_set_0(to, 0)\

   307 	bn_cp_64(to, 1, from, (a2) - 3) \

   308 	if (a1 != 0) bn_cp_64(to, 2, from, (a1) - 3) else bn_64_set_0(to, 2)\

   309 	}

   311 EXPORT_C int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,

   312 	BN_CTX *ctx)

   313 	{

   314 	int      top = a->top, i;

   315 	BN_ULONG carry = 0;

   316 	register BN_ULONG *r_d, *a_d = a->d;

   317 	BN_ULONG t_d[BN_NIST_192_TOP],

   318 	         buf[BN_NIST_192_TOP];

   320 	i = BN_ucmp(field, a);

   321 	if (i == 0)

   322 		{

   323 		BN_zero(r);

   324 		return 1;

   325 		}

   326 	else if (i > 0)

   327 		return (r == a) ? 1 : (BN_copy(r ,a) != NULL);

   329 	if (top == BN_NIST_192_TOP)

   330 		return BN_usub(r, a, field);

   332 	if (r != a)

   333 		{

   334 		if (!bn_wexpand(r, BN_NIST_192_TOP))

   335 			return 0;

   336 		r_d = r->d;

   337 		nist_cp_bn(r_d, a_d, BN_NIST_192_TOP);

   338 		}

   339 	else

   340 		r_d = a_d;

   342 	nist_cp_bn_0(buf, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP, BN_NIST_192_TOP);

   344 #if defined(OPENSSL_SYS_VMS) && defined(__DECC)

   345 # pragma message save

   346 # pragma message disable BADSUBSCRIPT

   347 #endif

   349 	nist_set_192(t_d, buf, 0, 3, 3);

   350 	if (bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP))

   351 		++carry;

   353 	nist_set_192(t_d, buf, 4, 4, 0);

   354 	if (bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP))

   355 		++carry;

   357 #if defined(OPENSSL_SYS_VMS) && defined(__DECC)

   358 # pragma message restore

   359 #endif

   361 	nist_set_192(t_d, buf, 5, 5, 5)

   362 	if (bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP))

   363 		++carry;

   365 	while (carry)

   366 		{

   367 		if (bn_sub_words(r_d, r_d, _nist_p_192, BN_NIST_192_TOP))

   368 			--carry;

   369 		}

   370 	r->top = BN_NIST_192_TOP;

   371 	bn_correct_top(r);

   372 	if (BN_ucmp(r, field) >= 0)

   373 		{

   374 		bn_sub_words(r_d, r_d, _nist_p_192, BN_NIST_192_TOP);

   375 		bn_correct_top(r);

   376 		}

   378 	bn_check_top(r);

   379 	return 1;

   380 	}

   382 #define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \

   383 	{ \

   384 	if (a7 != 0) bn_cp_32(to, 0, from, (a7) - 7) else bn_32_set_0(to, 0)\

   385 	if (a6 != 0) bn_cp_32(to, 1, from, (a6) - 7) else bn_32_set_0(to, 1)\

   386 	if (a5 != 0) bn_cp_32(to, 2, from, (a5) - 7) else bn_32_set_0(to, 2)\

   387 	if (a4 != 0) bn_cp_32(to, 3, from, (a4) - 7) else bn_32_set_0(to, 3)\

   388 	if (a3 != 0) bn_cp_32(to, 4, from, (a3) - 7) else bn_32_set_0(to, 4)\

   389 	if (a2 != 0) bn_cp_32(to, 5, from, (a2) - 7) else bn_32_set_0(to, 5)\

   390 	if (a1 != 0) bn_cp_32(to, 6, from, (a1) - 7) else bn_32_set_0(to, 6)\

   391 	}

   393 EXPORT_C int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,

   394 	BN_CTX *ctx)

   395 	{

   396 #if BN_BITS2 != 64

   397 	int	top = a->top, i;

   398 	int	carry = 0;

   399 	BN_ULONG *r_d, *a_d = a->d;

   400 	BN_ULONG t_d[BN_NIST_224_TOP],

   401 	         buf[BN_NIST_224_TOP];

   403 	i = BN_ucmp(field, a);

   404 	if (i == 0)

   405 		{

   406 		BN_zero(r);

   407 		return 1;

   408 		}

   409 	else if (i > 0)

   410 		return (r == a)? 1 : (BN_copy(r ,a) != NULL);

   412 	if (top == BN_NIST_224_TOP)

   413 		return BN_usub(r, a, field);

   415 	if (r != a)

   416 		{

   417 		if (!bn_wexpand(r, BN_NIST_224_TOP))

   418 			return 0;

   419 		r_d = r->d;

   420 		nist_cp_bn(r_d, a_d, BN_NIST_224_TOP);

   421 		}

   422 	else

   423 		r_d = a_d;

   425 	nist_cp_bn_0(buf, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP, BN_NIST_224_TOP);

   427 	nist_set_224(t_d, buf, 10, 9, 8, 7, 0, 0, 0);

   428 	if (bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP))

   429 		++carry;

   430 	nist_set_224(t_d, buf, 0, 13, 12, 11, 0, 0, 0);

   431 	if (bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP))

   432 		++carry;

   433 	nist_set_224(t_d, buf, 13, 12, 11, 10, 9, 8, 7);

   434 	if (bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP))

   435 		--carry;

   436 	nist_set_224(t_d, buf, 0, 0, 0, 0, 13, 12, 11);

   437 	if (bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP))

   438 		--carry;

   440 	if (carry > 0)

   441 		while (carry)

   442 			{

   443 			if (bn_sub_words(r_d,r_d,_nist_p_224,BN_NIST_224_TOP))

   444 				--carry;

   445 			}

   446 	else if (carry < 0)

   447 		while (carry)

   448 			{

   449 			if (bn_add_words(r_d,r_d,_nist_p_224,BN_NIST_224_TOP))

   450 				++carry;

   451 			}

   453 	r->top = BN_NIST_224_TOP;

   454 	bn_correct_top(r);

   455 	if (BN_ucmp(r, field) >= 0)

   456 		{

   457 		bn_sub_words(r_d, r_d, _nist_p_224, BN_NIST_224_TOP);

   458 		bn_correct_top(r);

   459 		}

   460 	bn_check_top(r);

   461 	return 1;

   462 #else

   463 	return 0;

   464 #endif

   465 	}

   467 #if BN_BITS2 != 64

   468 static void _init_256_data(void)

   469 	{

   470 	int	i;

   471 	BN_ULONG *tmp1 = _256_data;

   472 	const BN_ULONG *tmp2 = tmp1;

   474 	memcpy(tmp1, _nist_p_256, BN_NIST_256_TOP * sizeof(BN_ULONG));

   475 	tmp1 += BN_NIST_256_TOP;

   477 	for (i=0; i<5; i++)

   478 		{

   479 		bn_add_words(tmp1, _nist_p_256, tmp2, BN_NIST_256_TOP);

   480 		tmp2  = tmp1;

   481 		tmp1 += BN_NIST_256_TOP;

   482 		}

   483 	_is_set_256_data = 1;

   484 	}

   485 #endif

   487 #define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \

   488 	{ \

   489 	if (a8 != 0) bn_cp_32(to, 0, from, (a8) - 8) else bn_32_set_0(to, 0)\

   490 	if (a7 != 0) bn_cp_32(to, 1, from, (a7) - 8) else bn_32_set_0(to, 1)\

   491 	if (a6 != 0) bn_cp_32(to, 2, from, (a6) - 8) else bn_32_set_0(to, 2)\

   492 	if (a5 != 0) bn_cp_32(to, 3, from, (a5) - 8) else bn_32_set_0(to, 3)\

   493 	if (a4 != 0) bn_cp_32(to, 4, from, (a4) - 8) else bn_32_set_0(to, 4)\

   494 	if (a3 != 0) bn_cp_32(to, 5, from, (a3) - 8) else bn_32_set_0(to, 5)\

   495 	if (a2 != 0) bn_cp_32(to, 6, from, (a2) - 8) else bn_32_set_0(to, 6)\

   496 	if (a1 != 0) bn_cp_32(to, 7, from, (a1) - 8) else bn_32_set_0(to, 7)\

   497 	}

   499 EXPORT_C int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,

   500 	BN_CTX *ctx)

   501 	{

   502 #if BN_BITS2 != 64

   503 	int	i, top = a->top;

   504 	int	carry = 0;

   505 	register BN_ULONG *a_d = a->d, *r_d;

   506 	BN_ULONG t_d[BN_NIST_256_TOP],

   507 	         t_d2[BN_NIST_256_TOP],

   508 	         buf[BN_NIST_256_TOP];

   510 	if (!_is_set_256_data)

   511 		{

   512 		CRYPTO_w_lock(CRYPTO_LOCK_BN);

   514 		if (!_is_set_256_data)

   515 			_init_256_data();

   517 		CRYPTO_w_unlock(CRYPTO_LOCK_BN);

   518 		}

   520 	i = BN_ucmp(field, a);

   521 	if (i == 0)

   522 		{

   523 		BN_zero(r);

   524 		return 1;

   525 		}

   526 	else if (i > 0)

   527 		return (r == a)? 1 : (BN_copy(r ,a) != NULL);

   529 	if (top == BN_NIST_256_TOP)

   530 		return BN_usub(r, a, field);

   532 	if (r != a)

   533 		{

   534 		if (!bn_wexpand(r, BN_NIST_256_TOP))

   535 			return 0;

   536 		r_d = r->d;

   537 		nist_cp_bn(r_d, a_d, BN_NIST_256_TOP);

   538 		}

   539 	else

   540 		r_d = a_d;

   542 	nist_cp_bn_0(buf, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP, BN_NIST_256_TOP);

   544 	/*S1*/

   545 	nist_set_256(t_d, buf, 15, 14, 13, 12, 11, 0, 0, 0);

   546 	/*S2*/

   547 	nist_set_256(t_d2,buf, 0, 15, 14, 13, 12, 0, 0, 0);

   548 	if (bn_add_words(t_d, t_d, t_d2, BN_NIST_256_TOP))

   549 		carry = 2;

   550 	/* left shift */

   551 		{

   552 		register BN_ULONG *ap,t,c;

   553 		ap = t_d;

   554 		c=0;

   555 		for (i = BN_NIST_256_TOP; i != 0; --i)

   556 			{

   557 			t= *ap;

   558 			*(ap++)=((t<<1)|c)&BN_MASK2;

   559 			c=(t & BN_TBIT)?1:0;

   560 			}

   561 		if (c)

   562 			++carry;

   563 		}

   565 	if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))

   566 		++carry;

   567 	/*S3*/

   568 	nist_set_256(t_d, buf, 15, 14, 0, 0, 0, 10, 9, 8);

   569 	if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))

   570 		++carry;

   571 	/*S4*/

   572 	nist_set_256(t_d, buf, 8, 13, 15, 14, 13, 11, 10, 9);

   573 	if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))

   574 		++carry;

   575 	/*D1*/

   576 	nist_set_256(t_d, buf, 10, 8, 0, 0, 0, 13, 12, 11);

   577 	if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))

   578 		--carry;

   579 	/*D2*/

   580 	nist_set_256(t_d, buf, 11, 9, 0, 0, 15, 14, 13, 12);

   581 	if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))

   582 		--carry;

   583 	/*D3*/

   584 	nist_set_256(t_d, buf, 12, 0, 10, 9, 8, 15, 14, 13);

   585 	if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))

   586 		--carry;

   587 	/*D4*/

   588 	nist_set_256(t_d, buf, 13, 0, 11, 10, 9, 0, 15, 14);

   589 	if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))

   590 		--carry;

   592 	if (carry)

   593 		{

   594 		if (carry > 0)

   595 			bn_sub_words(r_d, r_d, _256_data + BN_NIST_256_TOP *

   596 				--carry, BN_NIST_256_TOP);

   597 		else

   598 			{

   599 			carry = -carry;

   600 			bn_add_words(r_d, r_d, _256_data + BN_NIST_256_TOP *

   601 				--carry, BN_NIST_256_TOP);

   602 			}

   603 		}

   605 	r->top = BN_NIST_256_TOP;

   606 	bn_correct_top(r);

   607 	if (BN_ucmp(r, field) >= 0)

   608 		{

   609 		bn_sub_words(r_d, r_d, _nist_p_256, BN_NIST_256_TOP);

   610 		bn_correct_top(r);

   611 		}

   612 	bn_check_top(r);

   613 	return 1;

   614 #else

   615 	return 0;

   616 #endif

   617 	}

   619 #if BN_BITS2 != 64

   620 static void _init_384_data(void)

   621 	{

   622 	int	i;

   623 	BN_ULONG *tmp1 = _384_data;

   624 	const BN_ULONG *tmp2 = tmp1;

   626 	memcpy(tmp1, _nist_p_384, BN_NIST_384_TOP * sizeof(BN_ULONG));

   627 	tmp1 += BN_NIST_384_TOP;

   629 	for (i=0; i<7; i++)

   630 		{

   631 		bn_add_words(tmp1, _nist_p_384, tmp2, BN_NIST_384_TOP);

   632 		tmp2  = tmp1;

   633 		tmp1 += BN_NIST_384_TOP;

   634 		}

   635 	_is_set_384_data = 1;

   636 	}

   637 #endif

   639 #define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \

   640 	{ \

   641 	if (a12 != 0) bn_cp_32(to, 0, from,  (a12) - 12) else bn_32_set_0(to, 0)\

   642 	if (a11 != 0) bn_cp_32(to, 1, from,  (a11) - 12) else bn_32_set_0(to, 1)\

   643 	if (a10 != 0) bn_cp_32(to, 2, from,  (a10) - 12) else bn_32_set_0(to, 2)\

   644 	if (a9 != 0)  bn_cp_32(to, 3, from,  (a9) - 12)  else bn_32_set_0(to, 3)\

   645 	if (a8 != 0)  bn_cp_32(to, 4, from,  (a8) - 12)  else bn_32_set_0(to, 4)\

   646 	if (a7 != 0)  bn_cp_32(to, 5, from,  (a7) - 12)  else bn_32_set_0(to, 5)\

   647 	if (a6 != 0)  bn_cp_32(to, 6, from,  (a6) - 12)  else bn_32_set_0(to, 6)\

   648 	if (a5 != 0)  bn_cp_32(to, 7, from,  (a5) - 12)  else bn_32_set_0(to, 7)\

   649 	if (a4 != 0)  bn_cp_32(to, 8, from,  (a4) - 12)  else bn_32_set_0(to, 8)\

   650 	if (a3 != 0)  bn_cp_32(to, 9, from,  (a3) - 12)  else bn_32_set_0(to, 9)\

   651 	if (a2 != 0)  bn_cp_32(to, 10, from, (a2) - 12)  else bn_32_set_0(to, 10)\

   652 	if (a1 != 0)  bn_cp_32(to, 11, from, (a1) - 12)  else bn_32_set_0(to, 11)\

   653 	}

   655 EXPORT_C int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,

   656 	BN_CTX *ctx)

   657 	{

   658 #if BN_BITS2 != 64

   659 	int	i, top = a->top;

   660 	int	carry = 0;

   661 	register BN_ULONG *r_d, *a_d = a->d;

   662 	BN_ULONG t_d[BN_NIST_384_TOP],

   663 	         buf[BN_NIST_384_TOP];

   665 	if (!_is_set_384_data)

   666 		{

   667 		CRYPTO_w_lock(CRYPTO_LOCK_BN);

   669 		if (!_is_set_384_data)

   670 			_init_384_data();

   672 		CRYPTO_w_unlock(CRYPTO_LOCK_BN);

   673 		}

   675 	i = BN_ucmp(field, a);

   676 	if (i == 0)

   677 		{

   678 		BN_zero(r);

   679 		return 1;

   680 		}

   681 	else if (i > 0)

   682 		return (r == a)? 1 : (BN_copy(r ,a) != NULL);

   684 	if (top == BN_NIST_384_TOP)

   685 		return BN_usub(r, a, field);

   687 	if (r != a)

   688 		{

   689 		if (!bn_wexpand(r, BN_NIST_384_TOP))

   690 			return 0;

   691 		r_d = r->d;

   692 		nist_cp_bn(r_d, a_d, BN_NIST_384_TOP);

   693 		}

   694 	else

   695 		r_d = a_d;

   697 	nist_cp_bn_0(buf, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP, BN_NIST_384_TOP);

   699 	/*S1*/

   700 	nist_set_256(t_d, buf, 0, 0, 0, 0, 0, 23-4, 22-4, 21-4);

   701 		/* left shift */

   702 		{

   703 		register BN_ULONG *ap,t,c;

   704 		ap = t_d;

   705 		c=0;

   706 		for (i = BN_NIST_256_TOP; i != 0; --i)

   707 			{

   708 			t= *ap;

   709 			*(ap++)=((t<<1)|c)&BN_MASK2;

   710 			c=(t & BN_TBIT)?1:0;

   711 			}

   712 		}

   713 	if (bn_add_words(r_d+(128/BN_BITS2), r_d+(128/BN_BITS2),

   714 		t_d, BN_NIST_256_TOP))

   715 		++carry;

   716 	/*S2 */

   717 	if (bn_add_words(r_d, r_d, buf, BN_NIST_384_TOP))

   718 		++carry;

   719 	/*S3*/

   720 	nist_set_384(t_d,buf,20,19,18,17,16,15,14,13,12,23,22,21);

   721 	if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))

   722 		++carry;

   723 	/*S4*/

   724 	nist_set_384(t_d,buf,19,18,17,16,15,14,13,12,20,0,23,0);

   725 	if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))

   726 		++carry;

   727 	/*S5*/

   728 	nist_set_256(t_d, buf, 0, 0, 0, 0, 23-4, 22-4, 21-4, 20-4);

   729 	if (bn_add_words(r_d+(128/BN_BITS2), r_d+(128/BN_BITS2),

   730 		t_d, BN_NIST_256_TOP))

   731 		++carry;

   732 	/*S6*/

   733 	nist_set_384(t_d,buf,0,0,0,0,0,0,23,22,21,0,0,20);

   734 	if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))

   735 		++carry;

   736 	/*D1*/

   737 	nist_set_384(t_d,buf,22,21,20,19,18,17,16,15,14,13,12,23);

   738 	if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))

   739 		--carry;

   740 	/*D2*/

   741 	nist_set_384(t_d,buf,0,0,0,0,0,0,0,23,22,21,20,0);

   742 	if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))

   743 		--carry;

   744 	/*D3*/

   745 	nist_set_384(t_d,buf,0,0,0,0,0,0,0,23,23,0,0,0);

   746 	if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))

   747 		--carry;

   749 	if (carry)

   750 		{

   751 		if (carry > 0)

   752 			bn_sub_words(r_d, r_d, _384_data + BN_NIST_384_TOP *

   753 				--carry, BN_NIST_384_TOP);

   754 		else

   755 			{

   756 			carry = -carry;

   757 			bn_add_words(r_d, r_d, _384_data + BN_NIST_384_TOP *

   758 				--carry, BN_NIST_384_TOP);

   759 			}

   760 		}

   762 	r->top = BN_NIST_384_TOP;

   763 	bn_correct_top(r);

   764 	if (BN_ucmp(r, field) >= 0)

   765 		{

   766 		bn_sub_words(r_d, r_d, _nist_p_384, BN_NIST_384_TOP);

   767 		bn_correct_top(r);

   768 		}

   769 	bn_check_top(r);

   770 	return 1;

   771 #else

   772 	return 0;

   773 #endif

   774 	}

   776 EXPORT_C int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,

   777 	BN_CTX *ctx)

   778 	{

   779 #if BN_BITS2 == 64

   780 #define BN_NIST_521_TOP_MASK	(BN_ULONG)0x1FF

   781 #elif BN_BITS2 == 32

   782 #define BN_NIST_521_TOP_MASK	(BN_ULONG)0x1FF

   783 #elif BN_BITS2 == 16

   784 #define BN_NIST_521_TOP_MASK	(BN_ULONG)0x1FF

   785 #elif BN_BITS2 == 8

   786 #define BN_NIST_521_TOP_MASK	(BN_ULONG)0x1

   787 #endif

   788 	int	top, ret = 0;

   789 	BN_ULONG *r_d;

   790 	BIGNUM	*tmp;

   792 	/* check whether a reduction is necessary */

   793 	top = a->top;

   794 	if (top < BN_NIST_521_TOP  || ( top == BN_NIST_521_TOP &&

   795            (!(a->d[BN_NIST_521_TOP-1] & ~(BN_NIST_521_TOP_MASK)))))

   796 		return (r == a)? 1 : (BN_copy(r ,a) != NULL);

   798 	BN_CTX_start(ctx);

   799 	tmp = BN_CTX_get(ctx);

   800 	if (!tmp)

   801 		goto err;

   803 	if (!bn_wexpand(tmp, BN_NIST_521_TOP))

   804 		goto err;

   805 	nist_cp_bn(tmp->d, a->d, BN_NIST_521_TOP);

   807 	tmp->top = BN_NIST_521_TOP;

   808         tmp->d[BN_NIST_521_TOP-1]  &= BN_NIST_521_TOP_MASK;

   809 	bn_correct_top(tmp);

   811 	if (!BN_rshift(r, a, 521))

   812 		goto err;

   814 	if (!BN_uadd(r, tmp, r))

   815 		goto err;

   816 	top = r->top;

   817 	r_d = r->d;

   818 	if (top == BN_NIST_521_TOP  &&

   819            (r_d[BN_NIST_521_TOP-1] & ~(BN_NIST_521_TOP_MASK)))

   820 		{

   821 		BN_NIST_ADD_ONE(r_d)

   822 		r_d[BN_NIST_521_TOP-1] &= BN_NIST_521_TOP_MASK;

   823 		}

   824 	bn_correct_top(r);

   826 	ret = 1;

   827 err:

   828 	BN_CTX_end(ctx);

   830 	bn_check_top(r);

   831 	return ret;

   832 	}

author	sl
	Tue, 10 Jun 2014 14:32:02 +0200
changeset 1	260cb5ec6c19
permissions	-rw-r--r--