10SN/A/* crypto/bn/bn_nist.c */ 2370SN/A/* 30SN/A * Written by Nils Larsch for the OpenSSL project 40SN/A */ 50SN/A/* ==================================================================== 60SN/A * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. 7157SN/A * 80SN/A * Redistribution and use in source and binary forms, with or without 9157SN/A * modification, are permitted provided that the following conditions 100SN/A * are met: 110SN/A * 120SN/A * 1. Redistributions of source code must retain the above copyright 130SN/A * notice, this list of conditions and the following disclaimer. 140SN/A * 150SN/A * 2. Redistributions in binary form must reproduce the above copyright 160SN/A * notice, this list of conditions and the following disclaimer in 170SN/A * the documentation and/or other materials provided with the 180SN/A * distribution. 190SN/A * 200SN/A * 3. All advertising materials mentioning features or use of this 21157SN/A * software must display the following acknowledgment: 22157SN/A * "This product includes software developed by the OpenSSL Project 23157SN/A * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 240SN/A * 250SN/A * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 260SN/A * endorse or promote products derived from this software without 270SN/A * prior written permission. For written permission, please contact 280SN/A * openssl-core@openssl.org. 290SN/A * 300SN/A * 5. Products derived from this software may not be called "OpenSSL" 310SN/A * nor may "OpenSSL" appear in their names without prior written 320SN/A * permission of the OpenSSL Project. 330SN/A * 340SN/A * 6. Redistributions of any form whatsoever must retain the following 350SN/A * acknowledgment: 360SN/A * "This product includes software developed by the OpenSSL Project 370SN/A * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 380SN/A * 390SN/A * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 400SN/A * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 410SN/A * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 420SN/A * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 430SN/A * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 440SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 450SN/A * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 460SN/A * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 470SN/A * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 480SN/A * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 490SN/A * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 500SN/A * OF THE POSSIBILITY OF SUCH DAMAGE. 510SN/A * ==================================================================== 520SN/A * 530SN/A * This product includes cryptographic software written by Eric Young 540SN/A * (eay@cryptsoft.com). This product includes software written by Tim 550SN/A * Hudson (tjh@cryptsoft.com). 560SN/A * 570SN/A */ 580SN/A 590SN/A#include "bn_lcl.h" 60370SN/A#include "cryptlib.h" 610SN/A 620SN/A#define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2 630SN/A#define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2 640SN/A#define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2 650SN/A#define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2 660SN/A#define BN_NIST_521_TOP (521+BN_BITS2-1)/BN_BITS2 670SN/A 680SN/A/* pre-computed tables are "carry-less" values of modulus*(i+1) */ 690SN/A#if BN_BITS2 == 64 700SN/Astatic const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = { 710SN/A {0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFFULL}, 720SN/A {0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL}, 730SN/A {0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFFFULL} 740SN/A}; 750SN/A 760SN/Astatic const BN_ULONG _nist_p_192_sqr[] = { 770SN/A 0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000001ULL, 780SN/A 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL 790SN/A}; 800SN/A 810SN/Astatic const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = { 820SN/A {0x0000000000000001ULL, 0xFFFFFFFF00000000ULL, 830SN/A 0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL}, 840SN/A {0x0000000000000002ULL, 0xFFFFFFFE00000000ULL, 850SN/A 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFFULL} /* this one is 860SN/A * "carry-full" */ 870SN/A}; 880SN/A 890SN/Astatic const BN_ULONG _nist_p_224_sqr[] = { 900SN/A 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL, 910SN/A 0xFFFFFFFFFFFFFFFFULL, 0x0000000200000000ULL, 920SN/A 0x0000000000000000ULL, 0xFFFFFFFFFFFFFFFEULL, 930SN/A 0xFFFFFFFFFFFFFFFFULL 940SN/A}; 950SN/A 960SN/Astatic const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = { 970SN/A {0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL, 98370SN/A 0x0000000000000000ULL, 0xFFFFFFFF00000001ULL}, 990SN/A {0xFFFFFFFFFFFFFFFEULL, 0x00000001FFFFFFFFULL, 1000SN/A 0x0000000000000000ULL, 0xFFFFFFFE00000002ULL}, 1010SN/A {0xFFFFFFFFFFFFFFFDULL, 0x00000002FFFFFFFFULL, 1020SN/A 0x0000000000000000ULL, 0xFFFFFFFD00000003ULL}, 1030SN/A {0xFFFFFFFFFFFFFFFCULL, 0x00000003FFFFFFFFULL, 1040SN/A 0x0000000000000000ULL, 0xFFFFFFFC00000004ULL}, 1050SN/A {0xFFFFFFFFFFFFFFFBULL, 0x00000004FFFFFFFFULL, 1060SN/A 0x0000000000000000ULL, 0xFFFFFFFB00000005ULL}, 1070SN/A}; 1080SN/A 1090SN/Astatic const BN_ULONG _nist_p_256_sqr[] = { 1100SN/A 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL, 1110SN/A 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFEULL, 1120SN/A 0x00000001FFFFFFFEULL, 0x00000001FFFFFFFEULL, 1130SN/A 0xFFFFFFFE00000001ULL, 0xFFFFFFFE00000002ULL 1140SN/A}; 1150SN/A 1160SN/Astatic const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = { 1170SN/A {0x00000000FFFFFFFFULL, 0xFFFFFFFF00000000ULL, 0xFFFFFFFFFFFFFFFEULL, 1180SN/A 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 1190SN/A {0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL, 1200SN/A 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 1210SN/A {0x00000002FFFFFFFDULL, 0xFFFFFFFD00000000ULL, 0xFFFFFFFFFFFFFFFCULL, 1220SN/A 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 1230SN/A {0x00000003FFFFFFFCULL, 0xFFFFFFFC00000000ULL, 0xFFFFFFFFFFFFFFFBULL, 1240SN/A 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 1250SN/A {0x00000004FFFFFFFBULL, 0xFFFFFFFB00000000ULL, 0xFFFFFFFFFFFFFFFAULL, 1260SN/A 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 1270SN/A}; 1280SN/A 1290SN/Astatic const BN_ULONG _nist_p_384_sqr[] = { 1300SN/A 0xFFFFFFFE00000001ULL, 0x0000000200000000ULL, 0xFFFFFFFE00000000ULL, 1310SN/A 0x0000000200000000ULL, 0x0000000000000001ULL, 0x0000000000000000ULL, 1320SN/A 0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL, 1330SN/A 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL 1340SN/A}; 1350SN/A 1360SN/Astatic const BN_ULONG _nist_p_521[] = 1370SN/A { 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 1380SN/A 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 1390SN/A 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 1400SN/A 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 1410SN/A 0x00000000000001FFULL 1420SN/A}; 1430SN/A 1440SN/Astatic const BN_ULONG _nist_p_521_sqr[] = { 1450SN/A 0x0000000000000001ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 1460SN/A 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 1470SN/A 0x0000000000000000ULL, 0x0000000000000000ULL, 0xFFFFFFFFFFFFFC00ULL, 1480SN/A 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 1490SN/A 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 1500SN/A 0xFFFFFFFFFFFFFFFFULL, 0x000000000003FFFFULL 1510SN/A}; 1520SN/A#elif BN_BITS2 == 32 1530SN/Astatic const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = { 1540SN/A {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 1550SN/A {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 1560SN/A {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF} 1570SN/A}; 1580SN/A 1590SN/Astatic const BN_ULONG _nist_p_192_sqr[] = { 1600SN/A 0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, 0x00000000, 1610SN/A 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF 1620SN/A}; 1630SN/A 1640SN/Astatic const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = { 1650SN/A {0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF, 1660SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 1670SN/A {0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE, 1680SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF} 1690SN/A}; 1700SN/A 1710SN/Astatic const BN_ULONG _nist_p_224_sqr[] = { 1720SN/A 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE, 1730SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000002, 1740SN/A 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, 1750SN/A 0xFFFFFFFF, 0xFFFFFFFF 1760SN/A}; 1770SN/A 1780SN/Astatic const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = { 1790SN/A {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 1800SN/A 0x00000000, 0x00000000, 0x00000001, 0xFFFFFFFF}, 1810SN/A {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, 1820SN/A 0x00000000, 0x00000000, 0x00000002, 0xFFFFFFFE}, 1830SN/A {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000002, 1840SN/A 0x00000000, 0x00000000, 0x00000003, 0xFFFFFFFD}, 1850SN/A {0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000003, 1860SN/A 0x00000000, 0x00000000, 0x00000004, 0xFFFFFFFC}, 1870SN/A {0xFFFFFFFB, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000004, 1880SN/A 0x00000000, 0x00000000, 0x00000005, 0xFFFFFFFB}, 1890SN/A}; 1900SN/A 1910SN/Astatic const BN_ULONG _nist_p_256_sqr[] = { 1920SN/A 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE, 1930SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0x00000001, 1940SN/A 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 195370SN/A 0x00000001, 0xFFFFFFFE, 0x00000002, 0xFFFFFFFE 1960SN/A}; 1970SN/A 1980SN/Astatic const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = { 1990SN/A {0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 2000SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 2010SN/A {0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF, 2020SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 2030SN/A {0xFFFFFFFD, 0x00000002, 0x00000000, 0xFFFFFFFD, 0xFFFFFFFC, 0xFFFFFFFF, 204370SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 2050SN/A {0xFFFFFFFC, 0x00000003, 0x00000000, 0xFFFFFFFC, 0xFFFFFFFB, 0xFFFFFFFF, 2060SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 2070SN/A {0xFFFFFFFB, 0x00000004, 0x00000000, 0xFFFFFFFB, 0xFFFFFFFA, 0xFFFFFFFF, 2080SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 2090SN/A}; 2100SN/A 2110SN/Astatic const BN_ULONG _nist_p_384_sqr[] = { 212370SN/A 0x00000001, 0xFFFFFFFE, 0x00000000, 0x00000002, 0x00000000, 0xFFFFFFFE, 2130SN/A 0x00000000, 0x00000002, 0x00000001, 0x00000000, 0x00000000, 0x00000000, 2140SN/A 0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF, 2150SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF 2160SN/A}; 2170SN/A 2180SN/Astatic const BN_ULONG _nist_p_521[] = { 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 2190SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 2200SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 2210SN/A 0xFFFFFFFF, 0x000001FF 2220SN/A}; 2230SN/A 224370SN/Astatic const BN_ULONG _nist_p_521_sqr[] = { 2250SN/A 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 2260SN/A 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 2270SN/A 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFC00, 0xFFFFFFFF, 2280SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 2290SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 2300SN/A 0xFFFFFFFF, 0xFFFFFFFF, 0x0003FFFF 2310SN/A}; 2320SN/A#else 2330SN/A# error "unsupported BN_BITS2" 2340SN/A#endif 235370SN/A 2360SN/Astatic const BIGNUM _bignum_nist_p_192 = { 2370SN/A (BN_ULONG *)_nist_p_192[0], 2380SN/A BN_NIST_192_TOP, 2390SN/A BN_NIST_192_TOP, 2400SN/A 0, 2410SN/A BN_FLG_STATIC_DATA 2420SN/A}; 2430SN/A 2440SN/Astatic const BIGNUM _bignum_nist_p_224 = { 2450SN/A (BN_ULONG *)_nist_p_224[0], 2460SN/A BN_NIST_224_TOP, 247370SN/A BN_NIST_224_TOP, 2480SN/A 0, 2490SN/A BN_FLG_STATIC_DATA 2500SN/A}; 2510SN/A 2520SN/Astatic const BIGNUM _bignum_nist_p_256 = { 2530SN/A (BN_ULONG *)_nist_p_256[0], 2540SN/A BN_NIST_256_TOP, 2550SN/A BN_NIST_256_TOP, 2560SN/A 0, 2570SN/A BN_FLG_STATIC_DATA 258370SN/A}; 2590SN/A 2600SN/Astatic const BIGNUM _bignum_nist_p_384 = { 2610SN/A (BN_ULONG *)_nist_p_384[0], 2620SN/A BN_NIST_384_TOP, 2630SN/A BN_NIST_384_TOP, 2640SN/A 0, 2650SN/A BN_FLG_STATIC_DATA 2660SN/A}; 2670SN/A 2680SN/Astatic const BIGNUM _bignum_nist_p_521 = { 2690SN/A (BN_ULONG *)_nist_p_521, 2700SN/A BN_NIST_521_TOP, 2710SN/A BN_NIST_521_TOP, 2720SN/A 0, 2730SN/A BN_FLG_STATIC_DATA 2740SN/A}; 2750SN/A 2760SN/Aconst BIGNUM *BN_get0_nist_prime_192(void) 2770SN/A{ 2780SN/A return &_bignum_nist_p_192; 2790SN/A} 2800SN/A 2810SN/Aconst BIGNUM *BN_get0_nist_prime_224(void) 2820SN/A{ 2830SN/A return &_bignum_nist_p_224; 2840SN/A} 2850SN/A 2860SN/Aconst BIGNUM *BN_get0_nist_prime_256(void) 2870SN/A{ 2880SN/A return &_bignum_nist_p_256; 2890SN/A} 2900SN/A 2910SN/Aconst BIGNUM *BN_get0_nist_prime_384(void) 2920SN/A{ 2930SN/A return &_bignum_nist_p_384; 2940SN/A} 2950SN/A 2960SN/Aconst BIGNUM *BN_get0_nist_prime_521(void) 2970SN/A{ 2980SN/A return &_bignum_nist_p_521; 2990SN/A} 3000SN/A 3010SN/Astatic void nist_cp_bn_0(BN_ULONG *dst, const BN_ULONG *src, int top, int max) 3020SN/A{ 3030SN/A int i; 3040SN/A 3050SN/A#ifdef BN_DEBUG 3060SN/A OPENSSL_assert(top <= max); 3070SN/A#endif 3080SN/A for (i = 0; i < top; i++) 3090SN/A dst[i] = src[i]; 3100SN/A for (; i < max; i++) 3110SN/A dst[i] = 0; 3120SN/A} 3130SN/A 3140SN/Astatic void nist_cp_bn(BN_ULONG *dst, const BN_ULONG *src, int top) 3150SN/A{ 3160SN/A int i; 3170SN/A 3180SN/A for (i = 0; i < top; i++) 3190SN/A dst[i] = src[i]; 3200SN/A} 3210SN/A 3220SN/A#if BN_BITS2 == 64 3230SN/A# define bn_cp_64(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0; 3240SN/A# define bn_64_set_0(to, n) (to)[n] = (BN_ULONG)0; 3250SN/A/* 3260SN/A * two following macros are implemented under assumption that they 3270SN/A * are called in a sequence with *ascending* n, i.e. as they are... 3280SN/A */ 3290SN/A# 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))\ 3300SN/A :(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l))) 3310SN/A# define bn_32_set_0(to, n) (((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0)); 3320SN/A# define bn_cp_32(to,n,from,m) ((m)>=0)?bn_cp_32_naked(to,n,from,m):bn_32_set_0(to,n) 3330SN/A# if defined(L_ENDIAN) 3340SN/A# if defined(__arch64__) 3350SN/A# define NIST_INT64 long 3360SN/A# else 3370SN/A# define NIST_INT64 long long 3380SN/A# endif 3390SN/A# endif 3400SN/A#else 3410SN/A# define bn_cp_64(to, n, from, m) \ 3420SN/A { \ 3430SN/A bn_cp_32(to, (n)*2, from, (m)*2); \ 3440SN/A bn_cp_32(to, (n)*2+1, from, (m)*2+1); \ 3450SN/A } 3460SN/A# define bn_64_set_0(to, n) \ 3470SN/A { \ 3480SN/A bn_32_set_0(to, (n)*2); \ 3490SN/A bn_32_set_0(to, (n)*2+1); \ 3500SN/A } 3510SN/A# define bn_cp_32(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0; 3520SN/A# define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0; 3530SN/A# if defined(_WIN32) && !defined(__GNUC__) 3540SN/A# define NIST_INT64 __int64 3550SN/A# elif defined(BN_LLONG) 3560SN/A# define NIST_INT64 long long 3570SN/A# endif 3580SN/A#endif /* BN_BITS2 != 64 */ 3590SN/A 3600SN/A#define nist_set_192(to, from, a1, a2, a3) \ 3610SN/A { \ 3620SN/A bn_cp_64(to, 0, from, (a3) - 3) \ 3630SN/A bn_cp_64(to, 1, from, (a2) - 3) \ 3640SN/A bn_cp_64(to, 2, from, (a1) - 3) \ 3650SN/A } 3660SN/A 3670SN/Aint BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 3680SN/A BN_CTX *ctx) 3690SN/A{ 3700SN/A int top = a->top, i; 3710SN/A int carry; 3720SN/A register BN_ULONG *r_d, *a_d = a->d; 3730SN/A union { 3740SN/A BN_ULONG bn[BN_NIST_192_TOP]; 3750SN/A unsigned int ui[BN_NIST_192_TOP * sizeof(BN_ULONG) / 3760SN/A sizeof(unsigned int)]; 3770SN/A } buf; 3780SN/A BN_ULONG c_d[BN_NIST_192_TOP], *res; 3790SN/A PTR_SIZE_INT mask; 3800SN/A static const BIGNUM _bignum_nist_p_192_sqr = { 3810SN/A (BN_ULONG *)_nist_p_192_sqr, 3820SN/A sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]), 3830SN/A sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]), 3840SN/A 0, BN_FLG_STATIC_DATA 3850SN/A }; 3860SN/A 3870SN/A field = &_bignum_nist_p_192; /* just to make sure */ 3880SN/A 3890SN/A if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_192_sqr) >= 0) 3900SN/A return BN_nnmod(r, a, field, ctx); 3910SN/A 3920SN/A i = BN_ucmp(field, a); 3930SN/A if (i == 0) { 3940SN/A BN_zero(r); 3950SN/A return 1; 3960SN/A } else if (i > 0) 3970SN/A return (r == a) ? 1 : (BN_copy(r, a) != NULL); 3980SN/A 3990SN/A if (r != a) { 4000SN/A if (!bn_wexpand(r, BN_NIST_192_TOP)) 4010SN/A return 0; 4020SN/A r_d = r->d; 4030SN/A nist_cp_bn(r_d, a_d, BN_NIST_192_TOP); 4040SN/A } else 4050SN/A r_d = a_d; 4060SN/A 4070SN/A nist_cp_bn_0(buf.bn, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP, 4080SN/A BN_NIST_192_TOP); 4090SN/A 4100SN/A#if defined(NIST_INT64) 4110SN/A { 4120SN/A NIST_INT64 acc; /* accumulator */ 4130SN/A unsigned int *rp = (unsigned int *)r_d; 4140SN/A const unsigned int *bp = (const unsigned int *)buf.ui; 4150SN/A 4160SN/A acc = rp[0]; 4170SN/A acc += bp[3 * 2 - 6]; 4180SN/A acc += bp[5 * 2 - 6]; 4190SN/A rp[0] = (unsigned int)acc; 4200SN/A acc >>= 32; 4210SN/A 4220SN/A acc += rp[1]; 4230SN/A acc += bp[3 * 2 - 5]; 4240SN/A acc += bp[5 * 2 - 5]; 4250SN/A rp[1] = (unsigned int)acc; 4260SN/A acc >>= 32; 4270SN/A 4280SN/A acc += rp[2]; 4290SN/A acc += bp[3 * 2 - 6]; 4300SN/A acc += bp[4 * 2 - 6]; 4310SN/A acc += bp[5 * 2 - 6]; 4320SN/A rp[2] = (unsigned int)acc; 4330SN/A acc >>= 32; 4340SN/A 4350SN/A acc += rp[3]; 4360SN/A acc += bp[3 * 2 - 5]; 4370SN/A acc += bp[4 * 2 - 5]; 4380SN/A acc += bp[5 * 2 - 5]; 4390SN/A rp[3] = (unsigned int)acc; 4400SN/A acc >>= 32; 4410SN/A 4420SN/A acc += rp[4]; 4430SN/A acc += bp[4 * 2 - 6]; 4440SN/A acc += bp[5 * 2 - 6]; 4450SN/A rp[4] = (unsigned int)acc; 4460SN/A acc >>= 32; 4470SN/A 4480SN/A acc += rp[5]; 4490SN/A acc += bp[4 * 2 - 5]; 4500SN/A acc += bp[5 * 2 - 5]; 4510SN/A rp[5] = (unsigned int)acc; 4520SN/A 4530SN/A carry = (int)(acc >> 32); 4540SN/A } 4550SN/A#else 4560SN/A { 4570SN/A BN_ULONG t_d[BN_NIST_192_TOP]; 4580SN/A 4590SN/A nist_set_192(t_d, buf.bn, 0, 3, 3); 4600SN/A carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); 4610SN/A nist_set_192(t_d, buf.bn, 4, 4, 0); 4620SN/A carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); 4630SN/A nist_set_192(t_d, buf.bn, 5, 5, 5) 4640SN/A carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); 4650SN/A } 4660SN/A#endif 4670SN/A if (carry > 0) 4680SN/A carry = 4690SN/A (int)bn_sub_words(r_d, r_d, _nist_p_192[carry - 1], 4700SN/A BN_NIST_192_TOP); 4710SN/A else 4720SN/A carry = 1; 4730SN/A 4740SN/A /* 4750SN/A * we need 'if (carry==0 || result>=modulus) result-=modulus;' 4760SN/A * as comparison implies subtraction, we can write 4770SN/A * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;' 4780SN/A * this is what happens below, but without explicit if:-) a. 4790SN/A */ 4800SN/A mask = 4810SN/A 0 - (PTR_SIZE_INT) bn_sub_words(c_d, r_d, _nist_p_192[0], 4820SN/A BN_NIST_192_TOP); 4830SN/A mask &= 0 - (PTR_SIZE_INT) carry; 4840SN/A res = c_d; 4850SN/A res = (BN_ULONG *) 4860SN/A (((PTR_SIZE_INT) res & ~mask) | ((PTR_SIZE_INT) r_d & mask)); 4870SN/A nist_cp_bn(r_d, res, BN_NIST_192_TOP); 4880SN/A r->top = BN_NIST_192_TOP; 4890SN/A bn_correct_top(r); 4900SN/A 4910SN/A return 1; 4920SN/A} 4930SN/A 4940SN/Atypedef BN_ULONG (*bn_addsub_f) (BN_ULONG *, const BN_ULONG *, 4950SN/A const BN_ULONG *, int); 4960SN/A 4970SN/A#define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \ 4980SN/A { \ 4990SN/A bn_cp_32(to, 0, from, (a7) - 7) \ 5000SN/A bn_cp_32(to, 1, from, (a6) - 7) \ 5010SN/A bn_cp_32(to, 2, from, (a5) - 7) \ 5020SN/A bn_cp_32(to, 3, from, (a4) - 7) \ 5030SN/A bn_cp_32(to, 4, from, (a3) - 7) \ 5040SN/A bn_cp_32(to, 5, from, (a2) - 7) \ 5050SN/A bn_cp_32(to, 6, from, (a1) - 7) \ 5060SN/A } 5070SN/A 5080SN/Aint BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 5090SN/A BN_CTX *ctx) 5100SN/A{ 5110SN/A int top = a->top, i; 5120SN/A int carry; 5130SN/A BN_ULONG *r_d, *a_d = a->d; 5140SN/A union { 5150SN/A BN_ULONG bn[BN_NIST_224_TOP]; 5160SN/A unsigned int ui[BN_NIST_224_TOP * sizeof(BN_ULONG) / 5170SN/A sizeof(unsigned int)]; 5180SN/A } buf; 5190SN/A BN_ULONG c_d[BN_NIST_224_TOP], *res; 5200SN/A PTR_SIZE_INT mask; 5210SN/A union { 5220SN/A bn_addsub_f f; 5230SN/A PTR_SIZE_INT p; 5240SN/A } u; 5250SN/A static const BIGNUM _bignum_nist_p_224_sqr = { 5260SN/A (BN_ULONG *)_nist_p_224_sqr, 5270SN/A sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]), 5280SN/A sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]), 5290SN/A 0, BN_FLG_STATIC_DATA 5300SN/A }; 5310SN/A 5320SN/A field = &_bignum_nist_p_224; /* just to make sure */ 5330SN/A 5340SN/A if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_224_sqr) >= 0) 5350SN/A return BN_nnmod(r, a, field, ctx); 5360SN/A 5370SN/A i = BN_ucmp(field, a); 5380SN/A if (i == 0) { 5390SN/A BN_zero(r); 5400SN/A return 1; 5410SN/A } else if (i > 0) 5420SN/A return (r == a) ? 1 : (BN_copy(r, a) != NULL); 5430SN/A 5440SN/A if (r != a) { 5450SN/A if (!bn_wexpand(r, BN_NIST_224_TOP)) 5460SN/A return 0; 5470SN/A r_d = r->d; 5480SN/A nist_cp_bn(r_d, a_d, BN_NIST_224_TOP); 5490SN/A } else 5500SN/A r_d = a_d; 5510SN/A 5520SN/A#if BN_BITS2==64 5530SN/A /* copy upper 256 bits of 448 bit number ... */ 5540SN/A nist_cp_bn_0(c_d, a_d + (BN_NIST_224_TOP - 1), 5550SN/A top - (BN_NIST_224_TOP - 1), BN_NIST_224_TOP); 5560SN/A /* ... and right shift by 32 to obtain upper 224 bits */ 5570SN/A nist_set_224(buf.bn, c_d, 14, 13, 12, 11, 10, 9, 8); 5580SN/A /* truncate lower part to 224 bits too */ 5590SN/A r_d[BN_NIST_224_TOP - 1] &= BN_MASK2l; 5600SN/A#else 5610SN/A nist_cp_bn_0(buf.bn, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP, 5620SN/A BN_NIST_224_TOP); 5630SN/A#endif 5640SN/A 5650SN/A#if defined(NIST_INT64) && BN_BITS2!=64 5660SN/A { 5670SN/A NIST_INT64 acc; /* accumulator */ 5680SN/A unsigned int *rp = (unsigned int *)r_d; 5690SN/A const unsigned int *bp = (const unsigned int *)buf.ui; 5700SN/A 5710SN/A acc = rp[0]; 5720SN/A acc -= bp[7 - 7]; 5730SN/A acc -= bp[11 - 7]; 5740SN/A rp[0] = (unsigned int)acc; 5750SN/A acc >>= 32; 5760SN/A 5770SN/A acc += rp[1]; 5780SN/A acc -= bp[8 - 7]; 5790SN/A acc -= bp[12 - 7]; 5800SN/A rp[1] = (unsigned int)acc; 5810SN/A acc >>= 32; 5820SN/A 5830SN/A acc += rp[2]; 5840SN/A acc -= bp[9 - 7]; 5850SN/A acc -= bp[13 - 7]; 5860SN/A rp[2] = (unsigned int)acc; 5870SN/A acc >>= 32; 5880SN/A 5890SN/A acc += rp[3]; 5900SN/A acc += bp[7 - 7]; 5910SN/A acc += bp[11 - 7]; 5920SN/A acc -= bp[10 - 7]; 5930SN/A rp[3] = (unsigned int)acc; 5940SN/A acc >>= 32; 5950SN/A 5960SN/A acc += rp[4]; 5970SN/A acc += bp[8 - 7]; 5980SN/A acc += bp[12 - 7]; 5990SN/A acc -= bp[11 - 7]; 6000SN/A rp[4] = (unsigned int)acc; 6010SN/A acc >>= 32; 6020SN/A 6030SN/A acc += rp[5]; 6040SN/A acc += bp[9 - 7]; 6050SN/A acc += bp[13 - 7]; 6060SN/A acc -= bp[12 - 7]; 6070SN/A rp[5] = (unsigned int)acc; 6080SN/A acc >>= 32; 6090SN/A 6100SN/A acc += rp[6]; 6110SN/A acc += bp[10 - 7]; 6120SN/A acc -= bp[13 - 7]; 6130SN/A rp[6] = (unsigned int)acc; 6140SN/A 6150SN/A carry = (int)(acc >> 32); 6160SN/A# if BN_BITS2==64 6170SN/A rp[7] = carry; 6180SN/A# endif 6190SN/A } 6200SN/A#else 6210SN/A { 6220SN/A BN_ULONG t_d[BN_NIST_224_TOP]; 6230SN/A 6240SN/A nist_set_224(t_d, buf.bn, 10, 9, 8, 7, 0, 0, 0); 6250SN/A carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP); 6260SN/A nist_set_224(t_d, buf.bn, 0, 13, 12, 11, 0, 0, 0); 6270SN/A carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP); 6280SN/A nist_set_224(t_d, buf.bn, 13, 12, 11, 10, 9, 8, 7); 6290SN/A carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP); 6300SN/A nist_set_224(t_d, buf.bn, 0, 0, 0, 0, 13, 12, 11); 6310SN/A carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP); 6320SN/A 6330SN/A# if BN_BITS2==64 6340SN/A carry = (int)(r_d[BN_NIST_224_TOP - 1] >> 32); 6350SN/A# endif 6360SN/A } 6370SN/A#endif 6380SN/A u.f = bn_sub_words; 6390SN/A if (carry > 0) { 6400SN/A carry = 6410SN/A (int)bn_sub_words(r_d, r_d, _nist_p_224[carry - 1], 6420SN/A BN_NIST_224_TOP); 6430SN/A#if BN_BITS2==64 6440SN/A carry = (int)(~(r_d[BN_NIST_224_TOP - 1] >> 32)) & 1; 6450SN/A#endif 6460SN/A } else if (carry < 0) { 6470SN/A /* 6480SN/A * it's a bit more comlicated logic in this case. if bn_add_words 6490SN/A * yields no carry, then result has to be adjusted by unconditionally 6500SN/A * *adding* the modulus. but if it does, then result has to be 6510SN/A * compared to the modulus and conditionally adjusted by 6520SN/A * *subtracting* the latter. 6530SN/A */ 6540SN/A carry = 6550SN/A (int)bn_add_words(r_d, r_d, _nist_p_224[-carry - 1], 6560SN/A BN_NIST_224_TOP); 6570SN/A mask = 0 - (PTR_SIZE_INT) carry; 6580SN/A u.p = ((PTR_SIZE_INT) bn_sub_words & mask) | 6590SN/A ((PTR_SIZE_INT) bn_add_words & ~mask); 6600SN/A } else 6610SN/A carry = 1; 6620SN/A 6630SN/A /* otherwise it's effectively same as in BN_nist_mod_192... */ 6640SN/A mask = 6650SN/A 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_224[0], BN_NIST_224_TOP); 6660SN/A mask &= 0 - (PTR_SIZE_INT) carry; 6670SN/A res = c_d; 6680SN/A res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) | 6690SN/A ((PTR_SIZE_INT) r_d & mask)); 6700SN/A nist_cp_bn(r_d, res, BN_NIST_224_TOP); 6710SN/A r->top = BN_NIST_224_TOP; 6720SN/A bn_correct_top(r); 6730SN/A 6740SN/A return 1; 6750SN/A} 6760SN/A 6770SN/A#define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \ 6780SN/A { \ 6790SN/A bn_cp_32(to, 0, from, (a8) - 8) \ 6800SN/A bn_cp_32(to, 1, from, (a7) - 8) \ 6810SN/A bn_cp_32(to, 2, from, (a6) - 8) \ 6820SN/A bn_cp_32(to, 3, from, (a5) - 8) \ 6830SN/A bn_cp_32(to, 4, from, (a4) - 8) \ 6840SN/A bn_cp_32(to, 5, from, (a3) - 8) \ 6850SN/A bn_cp_32(to, 6, from, (a2) - 8) \ 6860SN/A bn_cp_32(to, 7, from, (a1) - 8) \ 6870SN/A } 6880SN/A 6890SN/Aint BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 6900SN/A BN_CTX *ctx) 6910SN/A{ 6920SN/A int i, top = a->top; 6930SN/A int carry = 0; 6940SN/A register BN_ULONG *a_d = a->d, *r_d; 6950SN/A union { 6960SN/A BN_ULONG bn[BN_NIST_256_TOP]; 6970SN/A unsigned int ui[BN_NIST_256_TOP * sizeof(BN_ULONG) / 6980SN/A sizeof(unsigned int)]; 6990SN/A } buf; 7000SN/A BN_ULONG c_d[BN_NIST_256_TOP], *res; 7010SN/A PTR_SIZE_INT mask; 7020SN/A union { 7030SN/A bn_addsub_f f; 7040SN/A PTR_SIZE_INT p; 7050SN/A } u; 7060SN/A static const BIGNUM _bignum_nist_p_256_sqr = { 7070SN/A (BN_ULONG *)_nist_p_256_sqr, 7080SN/A sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]), 7090SN/A sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]), 7100SN/A 0, BN_FLG_STATIC_DATA 7110SN/A }; 7120SN/A 7130SN/A field = &_bignum_nist_p_256; /* just to make sure */ 7140SN/A 7150SN/A if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_256_sqr) >= 0) 7160SN/A return BN_nnmod(r, a, field, ctx); 7170SN/A 7180SN/A i = BN_ucmp(field, a); 7190SN/A if (i == 0) { 7200SN/A BN_zero(r); 7210SN/A return 1; 7220SN/A } else if (i > 0) 7230SN/A return (r == a) ? 1 : (BN_copy(r, a) != NULL); 7240SN/A 7250SN/A if (r != a) { 7260SN/A if (!bn_wexpand(r, BN_NIST_256_TOP)) 7270SN/A return 0; 7280SN/A r_d = r->d; 7290SN/A nist_cp_bn(r_d, a_d, BN_NIST_256_TOP); 7300SN/A } else 7310SN/A r_d = a_d; 7320SN/A 7330SN/A nist_cp_bn_0(buf.bn, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP, 7340SN/A BN_NIST_256_TOP); 7350SN/A 7360SN/A#if defined(NIST_INT64) 7370SN/A { 7380SN/A NIST_INT64 acc; /* accumulator */ 7390SN/A unsigned int *rp = (unsigned int *)r_d; 7400SN/A const unsigned int *bp = (const unsigned int *)buf.ui; 7410SN/A 7420SN/A acc = rp[0]; 7430SN/A acc += bp[8 - 8]; 7440SN/A acc += bp[9 - 8]; 7450SN/A acc -= bp[11 - 8]; 7460SN/A acc -= bp[12 - 8]; 7470SN/A acc -= bp[13 - 8]; 7480SN/A acc -= bp[14 - 8]; 7490SN/A rp[0] = (unsigned int)acc; 7500SN/A acc >>= 32; 7510SN/A 7520SN/A acc += rp[1]; 7530SN/A acc += bp[9 - 8]; 7540SN/A acc += bp[10 - 8]; 7550SN/A acc -= bp[12 - 8]; 7560SN/A acc -= bp[13 - 8]; 7570SN/A acc -= bp[14 - 8]; 7580SN/A acc -= bp[15 - 8]; 7590SN/A rp[1] = (unsigned int)acc; 7600SN/A acc >>= 32; 7610SN/A 7620SN/A acc += rp[2]; 7630SN/A acc += bp[10 - 8]; 7640SN/A acc += bp[11 - 8]; 7650SN/A acc -= bp[13 - 8]; 7660SN/A acc -= bp[14 - 8]; 7670SN/A acc -= bp[15 - 8]; 7680SN/A rp[2] = (unsigned int)acc; 7690SN/A acc >>= 32; 7700SN/A 7710SN/A acc += rp[3]; 7720SN/A acc += bp[11 - 8]; 7730SN/A acc += bp[11 - 8]; 7740SN/A acc += bp[12 - 8]; 7750SN/A acc += bp[12 - 8]; 7760SN/A acc += bp[13 - 8]; 7770SN/A acc -= bp[15 - 8]; 7780SN/A acc -= bp[8 - 8]; 7790SN/A acc -= bp[9 - 8]; 7800SN/A rp[3] = (unsigned int)acc; 7810SN/A acc >>= 32; 7820SN/A 7830SN/A acc += rp[4]; 7840SN/A acc += bp[12 - 8]; 7850SN/A acc += bp[12 - 8]; 7860SN/A acc += bp[13 - 8]; 7870SN/A acc += bp[13 - 8]; 7880SN/A acc += bp[14 - 8]; 7890SN/A acc -= bp[9 - 8]; 7900SN/A acc -= bp[10 - 8]; 7910SN/A rp[4] = (unsigned int)acc; 7920SN/A acc >>= 32; 7930SN/A 7940SN/A acc += rp[5]; 7950SN/A acc += bp[13 - 8]; 7960SN/A acc += bp[13 - 8]; 7970SN/A acc += bp[14 - 8]; 7980SN/A acc += bp[14 - 8]; 7990SN/A acc += bp[15 - 8]; 8000SN/A acc -= bp[10 - 8]; 8010SN/A acc -= bp[11 - 8]; 8020SN/A rp[5] = (unsigned int)acc; 8030SN/A acc >>= 32; 8040SN/A 8050SN/A acc += rp[6]; 8060SN/A acc += bp[14 - 8]; 8070SN/A acc += bp[14 - 8]; 8080SN/A acc += bp[15 - 8]; 8090SN/A acc += bp[15 - 8]; 8100SN/A acc += bp[14 - 8]; 8110SN/A acc += bp[13 - 8]; 8120SN/A acc -= bp[8 - 8]; 8130SN/A acc -= bp[9 - 8]; 8140SN/A rp[6] = (unsigned int)acc; 8150SN/A acc >>= 32; 8160SN/A 8170SN/A acc += rp[7]; 8180SN/A acc += bp[15 - 8]; 8190SN/A acc += bp[15 - 8]; 8200SN/A acc += bp[15 - 8]; 8210SN/A acc += bp[8 - 8]; 8220SN/A acc -= bp[10 - 8]; 8230SN/A acc -= bp[11 - 8]; 8240SN/A acc -= bp[12 - 8]; 8250SN/A acc -= bp[13 - 8]; 8260SN/A rp[7] = (unsigned int)acc; 8270SN/A 8280SN/A carry = (int)(acc >> 32); 8290SN/A } 8300SN/A#else 8310SN/A { 8320SN/A BN_ULONG t_d[BN_NIST_256_TOP]; 8330SN/A 8340SN/A /* 8350SN/A * S1 8360SN/A */ 8370SN/A nist_set_256(t_d, buf.bn, 15, 14, 13, 12, 11, 0, 0, 0); 8380SN/A /* 8390SN/A * S2 8400SN/A */ 8410SN/A nist_set_256(c_d, buf.bn, 0, 15, 14, 13, 12, 0, 0, 0); 8420SN/A carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP); 8430SN/A /* left shift */ 8440SN/A { 8450SN/A register BN_ULONG *ap, t, c; 8460SN/A ap = t_d; 8470SN/A c = 0; 8480SN/A for (i = BN_NIST_256_TOP; i != 0; --i) { 8490SN/A t = *ap; 8500SN/A *(ap++) = ((t << 1) | c) & BN_MASK2; 8510SN/A c = (t & BN_TBIT) ? 1 : 0; 8520SN/A } 8530SN/A carry <<= 1; 8540SN/A carry |= c; 8550SN/A } 8560SN/A carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 8570SN/A /* 8580SN/A * S3 8590SN/A */ 8600SN/A nist_set_256(t_d, buf.bn, 15, 14, 0, 0, 0, 10, 9, 8); 8610SN/A carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 8620SN/A /* 8630SN/A * S4 8640SN/A */ 8650SN/A nist_set_256(t_d, buf.bn, 8, 13, 15, 14, 13, 11, 10, 9); 8660SN/A carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 8670SN/A /* 8680SN/A * D1 8690SN/A */ 8700SN/A nist_set_256(t_d, buf.bn, 10, 8, 0, 0, 0, 13, 12, 11); 8710SN/A carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 8720SN/A /* 8730SN/A * D2 8740SN/A */ 8750SN/A nist_set_256(t_d, buf.bn, 11, 9, 0, 0, 15, 14, 13, 12); 8760SN/A carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 8770SN/A /* 8780SN/A * D3 8790SN/A */ 8800SN/A nist_set_256(t_d, buf.bn, 12, 0, 10, 9, 8, 15, 14, 13); 8810SN/A carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 8820SN/A /* 8830SN/A * D4 8840SN/A */ 8850SN/A nist_set_256(t_d, buf.bn, 13, 0, 11, 10, 9, 0, 15, 14); 8860SN/A carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 8870SN/A 8880SN/A } 8890SN/A#endif 8900SN/A /* see BN_nist_mod_224 for explanation */ 8910SN/A u.f = bn_sub_words; 8920SN/A if (carry > 0) 8930SN/A carry = 8940SN/A (int)bn_sub_words(r_d, r_d, _nist_p_256[carry - 1], 8950SN/A BN_NIST_256_TOP); 8960SN/A else if (carry < 0) { 8970SN/A carry = 8980SN/A (int)bn_add_words(r_d, r_d, _nist_p_256[-carry - 1], 8990SN/A BN_NIST_256_TOP); 9000SN/A mask = 0 - (PTR_SIZE_INT) carry; 9010SN/A u.p = ((PTR_SIZE_INT) bn_sub_words & mask) | 9020SN/A ((PTR_SIZE_INT) bn_add_words & ~mask); 9030SN/A } else 9040SN/A carry = 1; 9050SN/A 9060SN/A mask = 9070SN/A 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_256[0], BN_NIST_256_TOP); 9080SN/A mask &= 0 - (PTR_SIZE_INT) carry; 9090SN/A res = c_d; 9100SN/A res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) | 9110SN/A ((PTR_SIZE_INT) r_d & mask)); 9120SN/A nist_cp_bn(r_d, res, BN_NIST_256_TOP); 9130SN/A r->top = BN_NIST_256_TOP; 9140SN/A bn_correct_top(r); 9150SN/A 9160SN/A return 1; 9170SN/A} 9180SN/A 9190SN/A#define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \ 9200SN/A { \ 9210SN/A bn_cp_32(to, 0, from, (a12) - 12) \ 9220SN/A bn_cp_32(to, 1, from, (a11) - 12) \ 9230SN/A bn_cp_32(to, 2, from, (a10) - 12) \ 9240SN/A bn_cp_32(to, 3, from, (a9) - 12) \ 9250SN/A bn_cp_32(to, 4, from, (a8) - 12) \ 9260SN/A bn_cp_32(to, 5, from, (a7) - 12) \ 9270SN/A bn_cp_32(to, 6, from, (a6) - 12) \ 9280SN/A bn_cp_32(to, 7, from, (a5) - 12) \ 9290SN/A bn_cp_32(to, 8, from, (a4) - 12) \ 9300SN/A bn_cp_32(to, 9, from, (a3) - 12) \ 9310SN/A bn_cp_32(to, 10, from, (a2) - 12) \ 9320SN/A bn_cp_32(to, 11, from, (a1) - 12) \ 9330SN/A } 9340SN/A 9350SN/Aint BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 9360SN/A BN_CTX *ctx) 9370SN/A{ 9380SN/A int i, top = a->top; 9390SN/A int carry = 0; 9400SN/A register BN_ULONG *r_d, *a_d = a->d; 9410SN/A union { 9420SN/A BN_ULONG bn[BN_NIST_384_TOP]; 9430SN/A unsigned int ui[BN_NIST_384_TOP * sizeof(BN_ULONG) / 9440SN/A sizeof(unsigned int)]; 9450SN/A } buf; 9460SN/A BN_ULONG c_d[BN_NIST_384_TOP], *res; 9470SN/A PTR_SIZE_INT mask; 9480SN/A union { 9490SN/A bn_addsub_f f; 9500SN/A PTR_SIZE_INT p; 9510SN/A } u; 9520SN/A static const BIGNUM _bignum_nist_p_384_sqr = { 9530SN/A (BN_ULONG *)_nist_p_384_sqr, 9540SN/A sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]), 9550SN/A sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]), 9560SN/A 0, BN_FLG_STATIC_DATA 9570SN/A }; 9580SN/A 9590SN/A field = &_bignum_nist_p_384; /* just to make sure */ 9600SN/A 9610SN/A if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_384_sqr) >= 0) 9620SN/A return BN_nnmod(r, a, field, ctx); 9630SN/A 9640SN/A i = BN_ucmp(field, a); 9650SN/A if (i == 0) { 9660SN/A BN_zero(r); 9670SN/A return 1; 9680SN/A } else if (i > 0) 9690SN/A return (r == a) ? 1 : (BN_copy(r, a) != NULL); 9700SN/A 9710SN/A if (r != a) { 9720SN/A if (!bn_wexpand(r, BN_NIST_384_TOP)) 9730SN/A return 0; 9740SN/A r_d = r->d; 9750SN/A nist_cp_bn(r_d, a_d, BN_NIST_384_TOP); 9760SN/A } else 9770SN/A r_d = a_d; 9780SN/A 9790SN/A nist_cp_bn_0(buf.bn, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP, 9800SN/A BN_NIST_384_TOP); 9810SN/A 9820SN/A#if defined(NIST_INT64) 9830SN/A { 9840SN/A NIST_INT64 acc; /* accumulator */ 9850SN/A unsigned int *rp = (unsigned int *)r_d; 9860SN/A const unsigned int *bp = (const unsigned int *)buf.ui; 9870SN/A 9880SN/A acc = rp[0]; 9890SN/A acc += bp[12 - 12]; 9900SN/A acc += bp[21 - 12]; 9910SN/A acc += bp[20 - 12]; 9920SN/A acc -= bp[23 - 12]; 9930SN/A rp[0] = (unsigned int)acc; 994 acc >>= 32; 995 996 acc += rp[1]; 997 acc += bp[13 - 12]; 998 acc += bp[22 - 12]; 999 acc += bp[23 - 12]; 1000 acc -= bp[12 - 12]; 1001 acc -= bp[20 - 12]; 1002 rp[1] = (unsigned int)acc; 1003 acc >>= 32; 1004 1005 acc += rp[2]; 1006 acc += bp[14 - 12]; 1007 acc += bp[23 - 12]; 1008 acc -= bp[13 - 12]; 1009 acc -= bp[21 - 12]; 1010 rp[2] = (unsigned int)acc; 1011 acc >>= 32; 1012 1013 acc += rp[3]; 1014 acc += bp[15 - 12]; 1015 acc += bp[12 - 12]; 1016 acc += bp[20 - 12]; 1017 acc += bp[21 - 12]; 1018 acc -= bp[14 - 12]; 1019 acc -= bp[22 - 12]; 1020 acc -= bp[23 - 12]; 1021 rp[3] = (unsigned int)acc; 1022 acc >>= 32; 1023 1024 acc += rp[4]; 1025 acc += bp[21 - 12]; 1026 acc += bp[21 - 12]; 1027 acc += bp[16 - 12]; 1028 acc += bp[13 - 12]; 1029 acc += bp[12 - 12]; 1030 acc += bp[20 - 12]; 1031 acc += bp[22 - 12]; 1032 acc -= bp[15 - 12]; 1033 acc -= bp[23 - 12]; 1034 acc -= bp[23 - 12]; 1035 rp[4] = (unsigned int)acc; 1036 acc >>= 32; 1037 1038 acc += rp[5]; 1039 acc += bp[22 - 12]; 1040 acc += bp[22 - 12]; 1041 acc += bp[17 - 12]; 1042 acc += bp[14 - 12]; 1043 acc += bp[13 - 12]; 1044 acc += bp[21 - 12]; 1045 acc += bp[23 - 12]; 1046 acc -= bp[16 - 12]; 1047 rp[5] = (unsigned int)acc; 1048 acc >>= 32; 1049 1050 acc += rp[6]; 1051 acc += bp[23 - 12]; 1052 acc += bp[23 - 12]; 1053 acc += bp[18 - 12]; 1054 acc += bp[15 - 12]; 1055 acc += bp[14 - 12]; 1056 acc += bp[22 - 12]; 1057 acc -= bp[17 - 12]; 1058 rp[6] = (unsigned int)acc; 1059 acc >>= 32; 1060 1061 acc += rp[7]; 1062 acc += bp[19 - 12]; 1063 acc += bp[16 - 12]; 1064 acc += bp[15 - 12]; 1065 acc += bp[23 - 12]; 1066 acc -= bp[18 - 12]; 1067 rp[7] = (unsigned int)acc; 1068 acc >>= 32; 1069 1070 acc += rp[8]; 1071 acc += bp[20 - 12]; 1072 acc += bp[17 - 12]; 1073 acc += bp[16 - 12]; 1074 acc -= bp[19 - 12]; 1075 rp[8] = (unsigned int)acc; 1076 acc >>= 32; 1077 1078 acc += rp[9]; 1079 acc += bp[21 - 12]; 1080 acc += bp[18 - 12]; 1081 acc += bp[17 - 12]; 1082 acc -= bp[20 - 12]; 1083 rp[9] = (unsigned int)acc; 1084 acc >>= 32; 1085 1086 acc += rp[10]; 1087 acc += bp[22 - 12]; 1088 acc += bp[19 - 12]; 1089 acc += bp[18 - 12]; 1090 acc -= bp[21 - 12]; 1091 rp[10] = (unsigned int)acc; 1092 acc >>= 32; 1093 1094 acc += rp[11]; 1095 acc += bp[23 - 12]; 1096 acc += bp[20 - 12]; 1097 acc += bp[19 - 12]; 1098 acc -= bp[22 - 12]; 1099 rp[11] = (unsigned int)acc; 1100 1101 carry = (int)(acc >> 32); 1102 } 1103#else 1104 { 1105 BN_ULONG t_d[BN_NIST_384_TOP]; 1106 1107 /* 1108 * S1 1109 */ 1110 nist_set_256(t_d, buf.bn, 0, 0, 0, 0, 0, 23 - 4, 22 - 4, 21 - 4); 1111 /* left shift */ 1112 { 1113 register BN_ULONG *ap, t, c; 1114 ap = t_d; 1115 c = 0; 1116 for (i = 3; i != 0; --i) { 1117 t = *ap; 1118 *(ap++) = ((t << 1) | c) & BN_MASK2; 1119 c = (t & BN_TBIT) ? 1 : 0; 1120 } 1121 *ap = c; 1122 } 1123 carry = 1124 (int)bn_add_words(r_d + (128 / BN_BITS2), r_d + (128 / BN_BITS2), 1125 t_d, BN_NIST_256_TOP); 1126 /* 1127 * S2 1128 */ 1129 carry += (int)bn_add_words(r_d, r_d, buf.bn, BN_NIST_384_TOP); 1130 /* 1131 * S3 1132 */ 1133 nist_set_384(t_d, buf.bn, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 22, 1134 21); 1135 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 1136 /* 1137 * S4 1138 */ 1139 nist_set_384(t_d, buf.bn, 19, 18, 17, 16, 15, 14, 13, 12, 20, 0, 23, 1140 0); 1141 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 1142 /* 1143 * S5 1144 */ 1145 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 23, 22, 21, 20, 0, 0, 0, 0); 1146 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 1147 /* 1148 * S6 1149 */ 1150 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 23, 22, 21, 0, 0, 20); 1151 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 1152 /* 1153 * D1 1154 */ 1155 nist_set_384(t_d, buf.bn, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 1156 23); 1157 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 1158 /* 1159 * D2 1160 */ 1161 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 22, 21, 20, 0); 1162 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 1163 /* 1164 * D3 1165 */ 1166 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 23, 0, 0, 0); 1167 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 1168 1169 } 1170#endif 1171 /* see BN_nist_mod_224 for explanation */ 1172 u.f = bn_sub_words; 1173 if (carry > 0) 1174 carry = 1175 (int)bn_sub_words(r_d, r_d, _nist_p_384[carry - 1], 1176 BN_NIST_384_TOP); 1177 else if (carry < 0) { 1178 carry = 1179 (int)bn_add_words(r_d, r_d, _nist_p_384[-carry - 1], 1180 BN_NIST_384_TOP); 1181 mask = 0 - (PTR_SIZE_INT) carry; 1182 u.p = ((PTR_SIZE_INT) bn_sub_words & mask) | 1183 ((PTR_SIZE_INT) bn_add_words & ~mask); 1184 } else 1185 carry = 1; 1186 1187 mask = 1188 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_384[0], BN_NIST_384_TOP); 1189 mask &= 0 - (PTR_SIZE_INT) carry; 1190 res = c_d; 1191 res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) | 1192 ((PTR_SIZE_INT) r_d & mask)); 1193 nist_cp_bn(r_d, res, BN_NIST_384_TOP); 1194 r->top = BN_NIST_384_TOP; 1195 bn_correct_top(r); 1196 1197 return 1; 1198} 1199 1200#define BN_NIST_521_RSHIFT (521%BN_BITS2) 1201#define BN_NIST_521_LSHIFT (BN_BITS2-BN_NIST_521_RSHIFT) 1202#define BN_NIST_521_TOP_MASK ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT) 1203 1204int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 1205 BN_CTX *ctx) 1206{ 1207 int top = a->top, i; 1208 BN_ULONG *r_d, *a_d = a->d, t_d[BN_NIST_521_TOP], val, tmp, *res; 1209 PTR_SIZE_INT mask; 1210 static const BIGNUM _bignum_nist_p_521_sqr = { 1211 (BN_ULONG *)_nist_p_521_sqr, 1212 sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]), 1213 sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]), 1214 0, BN_FLG_STATIC_DATA 1215 }; 1216 1217 field = &_bignum_nist_p_521; /* just to make sure */ 1218 1219 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_521_sqr) >= 0) 1220 return BN_nnmod(r, a, field, ctx); 1221 1222 i = BN_ucmp(field, a); 1223 if (i == 0) { 1224 BN_zero(r); 1225 return 1; 1226 } else if (i > 0) 1227 return (r == a) ? 1 : (BN_copy(r, a) != NULL); 1228 1229 if (r != a) { 1230 if (!bn_wexpand(r, BN_NIST_521_TOP)) 1231 return 0; 1232 r_d = r->d; 1233 nist_cp_bn(r_d, a_d, BN_NIST_521_TOP); 1234 } else 1235 r_d = a_d; 1236 1237 /* upper 521 bits, copy ... */ 1238 nist_cp_bn_0(t_d, a_d + (BN_NIST_521_TOP - 1), 1239 top - (BN_NIST_521_TOP - 1), BN_NIST_521_TOP); 1240 /* ... and right shift */ 1241 for (val = t_d[0], i = 0; i < BN_NIST_521_TOP - 1; i++) { 1242 t_d[i] = (val >> BN_NIST_521_RSHIFT | 1243 (tmp = t_d[i + 1]) << BN_NIST_521_LSHIFT) & BN_MASK2; 1244 val = tmp; 1245 } 1246 t_d[i] = val >> BN_NIST_521_RSHIFT; 1247 /* lower 521 bits */ 1248 r_d[i] &= BN_NIST_521_TOP_MASK; 1249 1250 bn_add_words(r_d, r_d, t_d, BN_NIST_521_TOP); 1251 mask = 1252 0 - (PTR_SIZE_INT) bn_sub_words(t_d, r_d, _nist_p_521, 1253 BN_NIST_521_TOP); 1254 res = t_d; 1255 res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) | 1256 ((PTR_SIZE_INT) r_d & mask)); 1257 nist_cp_bn(r_d, res, BN_NIST_521_TOP); 1258 r->top = BN_NIST_521_TOP; 1259 bn_correct_top(r); 1260 1261 return 1; 1262} 1263