1160814Ssimon/* crypto/bn/bn_nist.c */ 2160814Ssimon/* 3160814Ssimon * Written by Nils Larsch for the OpenSSL project 4160814Ssimon */ 5160814Ssimon/* ==================================================================== 6160814Ssimon * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. 7160814Ssimon * 8160814Ssimon * Redistribution and use in source and binary forms, with or without 9160814Ssimon * modification, are permitted provided that the following conditions 10160814Ssimon * are met: 11160814Ssimon * 12160814Ssimon * 1. Redistributions of source code must retain the above copyright 13280304Sjkim * notice, this list of conditions and the following disclaimer. 14160814Ssimon * 15160814Ssimon * 2. Redistributions in binary form must reproduce the above copyright 16160814Ssimon * notice, this list of conditions and the following disclaimer in 17160814Ssimon * the documentation and/or other materials provided with the 18160814Ssimon * distribution. 19160814Ssimon * 20160814Ssimon * 3. All advertising materials mentioning features or use of this 21160814Ssimon * software must display the following acknowledgment: 22160814Ssimon * "This product includes software developed by the OpenSSL Project 23160814Ssimon * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 24160814Ssimon * 25160814Ssimon * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 26160814Ssimon * endorse or promote products derived from this software without 27160814Ssimon * prior written permission. For written permission, please contact 28160814Ssimon * openssl-core@openssl.org. 29160814Ssimon * 30160814Ssimon * 5. Products derived from this software may not be called "OpenSSL" 31160814Ssimon * nor may "OpenSSL" appear in their names without prior written 32160814Ssimon * permission of the OpenSSL Project. 33160814Ssimon * 34160814Ssimon * 6. Redistributions of any form whatsoever must retain the following 35160814Ssimon * acknowledgment: 36160814Ssimon * "This product includes software developed by the OpenSSL Project 37160814Ssimon * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 38160814Ssimon * 39160814Ssimon * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 40160814Ssimon * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 41160814Ssimon * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 42160814Ssimon * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 43160814Ssimon * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 44160814Ssimon * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 45160814Ssimon * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 46160814Ssimon * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47160814Ssimon * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 48160814Ssimon * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 49160814Ssimon * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 50160814Ssimon * OF THE POSSIBILITY OF SUCH DAMAGE. 51160814Ssimon * ==================================================================== 52160814Ssimon * 53160814Ssimon * This product includes cryptographic software written by Eric Young 54160814Ssimon * (eay@cryptsoft.com). This product includes software written by Tim 55160814Ssimon * Hudson (tjh@cryptsoft.com). 56160814Ssimon * 57160814Ssimon */ 58160814Ssimon 59160814Ssimon#include "bn_lcl.h" 60160814Ssimon#include "cryptlib.h" 61160814Ssimon 62280304Sjkim#define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2 63280304Sjkim#define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2 64280304Sjkim#define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2 65280304Sjkim#define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2 66280304Sjkim#define BN_NIST_521_TOP (521+BN_BITS2-1)/BN_BITS2 67194206Ssimon 68194206Ssimon/* pre-computed tables are "carry-less" values of modulus*(i+1) */ 69160814Ssimon#if BN_BITS2 == 64 70194206Ssimonstatic const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = { 71280304Sjkim {0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFFULL}, 72280304Sjkim {0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL}, 73280304Sjkim {0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFFFULL} 74280304Sjkim}; 75280304Sjkim 76194206Ssimonstatic const BN_ULONG _nist_p_192_sqr[] = { 77280304Sjkim 0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000001ULL, 78280304Sjkim 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL 79280304Sjkim}; 80280304Sjkim 81194206Ssimonstatic const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = { 82280304Sjkim {0x0000000000000001ULL, 0xFFFFFFFF00000000ULL, 83280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL}, 84280304Sjkim {0x0000000000000002ULL, 0xFFFFFFFE00000000ULL, 85280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFFULL} /* this one is 86280304Sjkim * "carry-full" */ 87280304Sjkim}; 88280304Sjkim 89194206Ssimonstatic const BN_ULONG _nist_p_224_sqr[] = { 90280304Sjkim 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL, 91280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0x0000000200000000ULL, 92280304Sjkim 0x0000000000000000ULL, 0xFFFFFFFFFFFFFFFEULL, 93280304Sjkim 0xFFFFFFFFFFFFFFFFULL 94280304Sjkim}; 95280304Sjkim 96194206Ssimonstatic const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = { 97280304Sjkim {0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL, 98280304Sjkim 0x0000000000000000ULL, 0xFFFFFFFF00000001ULL}, 99280304Sjkim {0xFFFFFFFFFFFFFFFEULL, 0x00000001FFFFFFFFULL, 100280304Sjkim 0x0000000000000000ULL, 0xFFFFFFFE00000002ULL}, 101280304Sjkim {0xFFFFFFFFFFFFFFFDULL, 0x00000002FFFFFFFFULL, 102280304Sjkim 0x0000000000000000ULL, 0xFFFFFFFD00000003ULL}, 103280304Sjkim {0xFFFFFFFFFFFFFFFCULL, 0x00000003FFFFFFFFULL, 104280304Sjkim 0x0000000000000000ULL, 0xFFFFFFFC00000004ULL}, 105280304Sjkim {0xFFFFFFFFFFFFFFFBULL, 0x00000004FFFFFFFFULL, 106280304Sjkim 0x0000000000000000ULL, 0xFFFFFFFB00000005ULL}, 107280304Sjkim}; 108280304Sjkim 109194206Ssimonstatic const BN_ULONG _nist_p_256_sqr[] = { 110280304Sjkim 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL, 111280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFEULL, 112280304Sjkim 0x00000001FFFFFFFEULL, 0x00000001FFFFFFFEULL, 113280304Sjkim 0xFFFFFFFE00000001ULL, 0xFFFFFFFE00000002ULL 114280304Sjkim}; 115280304Sjkim 116194206Ssimonstatic const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = { 117280304Sjkim {0x00000000FFFFFFFFULL, 0xFFFFFFFF00000000ULL, 0xFFFFFFFFFFFFFFFEULL, 118280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 119280304Sjkim {0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL, 120280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 121280304Sjkim {0x00000002FFFFFFFDULL, 0xFFFFFFFD00000000ULL, 0xFFFFFFFFFFFFFFFCULL, 122280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 123280304Sjkim {0x00000003FFFFFFFCULL, 0xFFFFFFFC00000000ULL, 0xFFFFFFFFFFFFFFFBULL, 124280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 125280304Sjkim {0x00000004FFFFFFFBULL, 0xFFFFFFFB00000000ULL, 0xFFFFFFFFFFFFFFFAULL, 126280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 127280304Sjkim}; 128280304Sjkim 129194206Ssimonstatic const BN_ULONG _nist_p_384_sqr[] = { 130280304Sjkim 0xFFFFFFFE00000001ULL, 0x0000000200000000ULL, 0xFFFFFFFE00000000ULL, 131280304Sjkim 0x0000000200000000ULL, 0x0000000000000001ULL, 0x0000000000000000ULL, 132280304Sjkim 0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL, 133280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL 134280304Sjkim}; 135280304Sjkim 136160814Ssimonstatic const BN_ULONG _nist_p_521[] = 137280304Sjkim { 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 138280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 139280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 140280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 141280304Sjkim 0x00000000000001FFULL 142280304Sjkim}; 143280304Sjkim 144194206Ssimonstatic const BN_ULONG _nist_p_521_sqr[] = { 145280304Sjkim 0x0000000000000001ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 146280304Sjkim 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 147280304Sjkim 0x0000000000000000ULL, 0x0000000000000000ULL, 0xFFFFFFFFFFFFFC00ULL, 148280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 149280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 150280304Sjkim 0xFFFFFFFFFFFFFFFFULL, 0x000000000003FFFFULL 151280304Sjkim}; 152160814Ssimon#elif BN_BITS2 == 32 153194206Ssimonstatic const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = { 154280304Sjkim {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 155280304Sjkim {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 156280304Sjkim {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF} 157280304Sjkim}; 158280304Sjkim 159194206Ssimonstatic const BN_ULONG _nist_p_192_sqr[] = { 160280304Sjkim 0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, 0x00000000, 161280304Sjkim 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF 162280304Sjkim}; 163280304Sjkim 164194206Ssimonstatic const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = { 165280304Sjkim {0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF, 166280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 167280304Sjkim {0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE, 168280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF} 169280304Sjkim}; 170280304Sjkim 171194206Ssimonstatic const BN_ULONG _nist_p_224_sqr[] = { 172280304Sjkim 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE, 173280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000002, 174280304Sjkim 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, 175280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF 176280304Sjkim}; 177280304Sjkim 178194206Ssimonstatic const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = { 179280304Sjkim {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 180280304Sjkim 0x00000000, 0x00000000, 0x00000001, 0xFFFFFFFF}, 181280304Sjkim {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, 182280304Sjkim 0x00000000, 0x00000000, 0x00000002, 0xFFFFFFFE}, 183280304Sjkim {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000002, 184280304Sjkim 0x00000000, 0x00000000, 0x00000003, 0xFFFFFFFD}, 185280304Sjkim {0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000003, 186280304Sjkim 0x00000000, 0x00000000, 0x00000004, 0xFFFFFFFC}, 187280304Sjkim {0xFFFFFFFB, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000004, 188280304Sjkim 0x00000000, 0x00000000, 0x00000005, 0xFFFFFFFB}, 189280304Sjkim}; 190280304Sjkim 191194206Ssimonstatic const BN_ULONG _nist_p_256_sqr[] = { 192280304Sjkim 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE, 193280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0x00000001, 194280304Sjkim 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 195280304Sjkim 0x00000001, 0xFFFFFFFE, 0x00000002, 0xFFFFFFFE 196280304Sjkim}; 197280304Sjkim 198194206Ssimonstatic const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = { 199280304Sjkim {0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 200280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 201280304Sjkim {0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF, 202280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 203280304Sjkim {0xFFFFFFFD, 0x00000002, 0x00000000, 0xFFFFFFFD, 0xFFFFFFFC, 0xFFFFFFFF, 204280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 205280304Sjkim {0xFFFFFFFC, 0x00000003, 0x00000000, 0xFFFFFFFC, 0xFFFFFFFB, 0xFFFFFFFF, 206280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 207280304Sjkim {0xFFFFFFFB, 0x00000004, 0x00000000, 0xFFFFFFFB, 0xFFFFFFFA, 0xFFFFFFFF, 208280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 209280304Sjkim}; 210280304Sjkim 211194206Ssimonstatic const BN_ULONG _nist_p_384_sqr[] = { 212280304Sjkim 0x00000001, 0xFFFFFFFE, 0x00000000, 0x00000002, 0x00000000, 0xFFFFFFFE, 213280304Sjkim 0x00000000, 0x00000002, 0x00000001, 0x00000000, 0x00000000, 0x00000000, 214280304Sjkim 0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF, 215280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF 216280304Sjkim}; 217280304Sjkim 218280304Sjkimstatic const BN_ULONG _nist_p_521[] = { 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 219280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 220280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 221280304Sjkim 0xFFFFFFFF, 0x000001FF 222280304Sjkim}; 223280304Sjkim 224194206Ssimonstatic const BN_ULONG _nist_p_521_sqr[] = { 225280304Sjkim 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 226280304Sjkim 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 227280304Sjkim 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFC00, 0xFFFFFFFF, 228280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 229280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 230280304Sjkim 0xFFFFFFFF, 0xFFFFFFFF, 0x0003FFFF 231280304Sjkim}; 232194206Ssimon#else 233280304Sjkim# error "unsupported BN_BITS2" 234160814Ssimon#endif 235160814Ssimon 236280304Sjkimstatic const BIGNUM _bignum_nist_p_192 = { 237280304Sjkim (BN_ULONG *)_nist_p_192[0], 238280304Sjkim BN_NIST_192_TOP, 239280304Sjkim BN_NIST_192_TOP, 240280304Sjkim 0, 241280304Sjkim BN_FLG_STATIC_DATA 242280304Sjkim}; 243194206Ssimon 244280304Sjkimstatic const BIGNUM _bignum_nist_p_224 = { 245280304Sjkim (BN_ULONG *)_nist_p_224[0], 246280304Sjkim BN_NIST_224_TOP, 247280304Sjkim BN_NIST_224_TOP, 248280304Sjkim 0, 249280304Sjkim BN_FLG_STATIC_DATA 250280304Sjkim}; 251194206Ssimon 252280304Sjkimstatic const BIGNUM _bignum_nist_p_256 = { 253280304Sjkim (BN_ULONG *)_nist_p_256[0], 254280304Sjkim BN_NIST_256_TOP, 255280304Sjkim BN_NIST_256_TOP, 256280304Sjkim 0, 257280304Sjkim BN_FLG_STATIC_DATA 258280304Sjkim}; 259194206Ssimon 260280304Sjkimstatic const BIGNUM _bignum_nist_p_384 = { 261280304Sjkim (BN_ULONG *)_nist_p_384[0], 262280304Sjkim BN_NIST_384_TOP, 263280304Sjkim BN_NIST_384_TOP, 264280304Sjkim 0, 265280304Sjkim BN_FLG_STATIC_DATA 266280304Sjkim}; 267194206Ssimon 268280304Sjkimstatic const BIGNUM _bignum_nist_p_521 = { 269280304Sjkim (BN_ULONG *)_nist_p_521, 270280304Sjkim BN_NIST_521_TOP, 271280304Sjkim BN_NIST_521_TOP, 272280304Sjkim 0, 273280304Sjkim BN_FLG_STATIC_DATA 274280304Sjkim}; 275194206Ssimon 276160814Ssimonconst BIGNUM *BN_get0_nist_prime_192(void) 277280304Sjkim{ 278280304Sjkim return &_bignum_nist_p_192; 279280304Sjkim} 280160814Ssimon 281160814Ssimonconst BIGNUM *BN_get0_nist_prime_224(void) 282280304Sjkim{ 283280304Sjkim return &_bignum_nist_p_224; 284280304Sjkim} 285160814Ssimon 286160814Ssimonconst BIGNUM *BN_get0_nist_prime_256(void) 287280304Sjkim{ 288280304Sjkim return &_bignum_nist_p_256; 289280304Sjkim} 290160814Ssimon 291160814Ssimonconst BIGNUM *BN_get0_nist_prime_384(void) 292280304Sjkim{ 293280304Sjkim return &_bignum_nist_p_384; 294280304Sjkim} 295160814Ssimon 296160814Ssimonconst BIGNUM *BN_get0_nist_prime_521(void) 297280304Sjkim{ 298280304Sjkim return &_bignum_nist_p_521; 299280304Sjkim} 300160814Ssimon 301264331Sjkimstatic void nist_cp_bn_0(BN_ULONG *dst, const BN_ULONG *src, int top, int max) 302280304Sjkim{ 303280304Sjkim int i; 304160814Ssimon 305194206Ssimon#ifdef BN_DEBUG 306280304Sjkim OPENSSL_assert(top <= max); 307194206Ssimon#endif 308280304Sjkim for (i = 0; i < top; i++) 309280304Sjkim dst[i] = src[i]; 310280304Sjkim for (; i < max; i++) 311280304Sjkim dst[i] = 0; 312280304Sjkim} 313194206Ssimon 314264331Sjkimstatic void nist_cp_bn(BN_ULONG *dst, const BN_ULONG *src, int top) 315280304Sjkim{ 316280304Sjkim int i; 317264331Sjkim 318280304Sjkim for (i = 0; i < top; i++) 319280304Sjkim dst[i] = src[i]; 320280304Sjkim} 321160814Ssimon 322160814Ssimon#if BN_BITS2 == 64 323280304Sjkim# define bn_cp_64(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0; 324280304Sjkim# define bn_64_set_0(to, n) (to)[n] = (BN_ULONG)0; 325194206Ssimon/* 326194206Ssimon * two following macros are implemented under assumption that they 327194206Ssimon * are called in a sequence with *ascending* n, i.e. as they are... 328194206Ssimon */ 329280304Sjkim# 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))\ 330280304Sjkim :(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l))) 331280304Sjkim# define bn_32_set_0(to, n) (((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0)); 332280304Sjkim# define bn_cp_32(to,n,from,m) ((m)>=0)?bn_cp_32_naked(to,n,from,m):bn_32_set_0(to,n) 333238405Sjkim# if defined(L_ENDIAN) 334238405Sjkim# if defined(__arch64__) 335238405Sjkim# define NIST_INT64 long 336238405Sjkim# else 337238405Sjkim# define NIST_INT64 long long 338238405Sjkim# endif 339238405Sjkim# endif 340160814Ssimon#else 341280304Sjkim# define bn_cp_64(to, n, from, m) \ 342280304Sjkim { \ 343280304Sjkim bn_cp_32(to, (n)*2, from, (m)*2); \ 344280304Sjkim bn_cp_32(to, (n)*2+1, from, (m)*2+1); \ 345280304Sjkim } 346280304Sjkim# define bn_64_set_0(to, n) \ 347280304Sjkim { \ 348280304Sjkim bn_32_set_0(to, (n)*2); \ 349280304Sjkim bn_32_set_0(to, (n)*2+1); \ 350280304Sjkim } 351280304Sjkim# define bn_cp_32(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0; 352280304Sjkim# define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0; 353238405Sjkim# if defined(_WIN32) && !defined(__GNUC__) 354238405Sjkim# define NIST_INT64 __int64 355238405Sjkim# elif defined(BN_LLONG) 356238405Sjkim# define NIST_INT64 long long 357238405Sjkim# endif 358280304Sjkim#endif /* BN_BITS2 != 64 */ 359160814Ssimon 360160814Ssimon#define nist_set_192(to, from, a1, a2, a3) \ 361280304Sjkim { \ 362280304Sjkim bn_cp_64(to, 0, from, (a3) - 3) \ 363280304Sjkim bn_cp_64(to, 1, from, (a2) - 3) \ 364280304Sjkim bn_cp_64(to, 2, from, (a1) - 3) \ 365280304Sjkim } 366160814Ssimon 367160814Ssimonint BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 368280304Sjkim BN_CTX *ctx) 369280304Sjkim{ 370280304Sjkim int top = a->top, i; 371280304Sjkim int carry; 372280304Sjkim register BN_ULONG *r_d, *a_d = a->d; 373280304Sjkim union { 374280304Sjkim BN_ULONG bn[BN_NIST_192_TOP]; 375280304Sjkim unsigned int ui[BN_NIST_192_TOP * sizeof(BN_ULONG) / 376280304Sjkim sizeof(unsigned int)]; 377280304Sjkim } buf; 378280304Sjkim BN_ULONG c_d[BN_NIST_192_TOP], *res; 379280304Sjkim PTR_SIZE_INT mask; 380280304Sjkim static const BIGNUM _bignum_nist_p_192_sqr = { 381280304Sjkim (BN_ULONG *)_nist_p_192_sqr, 382280304Sjkim sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]), 383280304Sjkim sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]), 384280304Sjkim 0, BN_FLG_STATIC_DATA 385280304Sjkim }; 386160814Ssimon 387280304Sjkim field = &_bignum_nist_p_192; /* just to make sure */ 388194206Ssimon 389280304Sjkim if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_192_sqr) >= 0) 390280304Sjkim return BN_nnmod(r, a, field, ctx); 391194206Ssimon 392280304Sjkim i = BN_ucmp(field, a); 393280304Sjkim if (i == 0) { 394280304Sjkim BN_zero(r); 395280304Sjkim return 1; 396280304Sjkim } else if (i > 0) 397280304Sjkim return (r == a) ? 1 : (BN_copy(r, a) != NULL); 398160814Ssimon 399280304Sjkim if (r != a) { 400280304Sjkim if (!bn_wexpand(r, BN_NIST_192_TOP)) 401280304Sjkim return 0; 402280304Sjkim r_d = r->d; 403280304Sjkim nist_cp_bn(r_d, a_d, BN_NIST_192_TOP); 404280304Sjkim } else 405280304Sjkim r_d = a_d; 406160814Ssimon 407280304Sjkim nist_cp_bn_0(buf.bn, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP, 408280304Sjkim BN_NIST_192_TOP); 409160814Ssimon 410238405Sjkim#if defined(NIST_INT64) 411280304Sjkim { 412280304Sjkim NIST_INT64 acc; /* accumulator */ 413280304Sjkim unsigned int *rp = (unsigned int *)r_d; 414280304Sjkim const unsigned int *bp = (const unsigned int *)buf.ui; 415238405Sjkim 416280304Sjkim acc = rp[0]; 417280304Sjkim acc += bp[3 * 2 - 6]; 418280304Sjkim acc += bp[5 * 2 - 6]; 419280304Sjkim rp[0] = (unsigned int)acc; 420280304Sjkim acc >>= 32; 421238405Sjkim 422280304Sjkim acc += rp[1]; 423280304Sjkim acc += bp[3 * 2 - 5]; 424280304Sjkim acc += bp[5 * 2 - 5]; 425280304Sjkim rp[1] = (unsigned int)acc; 426280304Sjkim acc >>= 32; 427238405Sjkim 428280304Sjkim acc += rp[2]; 429280304Sjkim acc += bp[3 * 2 - 6]; 430280304Sjkim acc += bp[4 * 2 - 6]; 431280304Sjkim acc += bp[5 * 2 - 6]; 432280304Sjkim rp[2] = (unsigned int)acc; 433280304Sjkim acc >>= 32; 434238405Sjkim 435280304Sjkim acc += rp[3]; 436280304Sjkim acc += bp[3 * 2 - 5]; 437280304Sjkim acc += bp[4 * 2 - 5]; 438280304Sjkim acc += bp[5 * 2 - 5]; 439280304Sjkim rp[3] = (unsigned int)acc; 440280304Sjkim acc >>= 32; 441238405Sjkim 442280304Sjkim acc += rp[4]; 443280304Sjkim acc += bp[4 * 2 - 6]; 444280304Sjkim acc += bp[5 * 2 - 6]; 445280304Sjkim rp[4] = (unsigned int)acc; 446280304Sjkim acc >>= 32; 447238405Sjkim 448280304Sjkim acc += rp[5]; 449280304Sjkim acc += bp[4 * 2 - 5]; 450280304Sjkim acc += bp[5 * 2 - 5]; 451280304Sjkim rp[5] = (unsigned int)acc; 452238405Sjkim 453280304Sjkim carry = (int)(acc >> 32); 454280304Sjkim } 455238405Sjkim#else 456280304Sjkim { 457280304Sjkim BN_ULONG t_d[BN_NIST_192_TOP]; 458238405Sjkim 459280304Sjkim nist_set_192(t_d, buf.bn, 0, 3, 3); 460280304Sjkim carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); 461280304Sjkim nist_set_192(t_d, buf.bn, 4, 4, 0); 462280304Sjkim carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); 463280304Sjkim nist_set_192(t_d, buf.bn, 5, 5, 5) 464280304Sjkim carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); 465280304Sjkim } 466238405Sjkim#endif 467280304Sjkim if (carry > 0) 468280304Sjkim carry = 469280304Sjkim (int)bn_sub_words(r_d, r_d, _nist_p_192[carry - 1], 470280304Sjkim BN_NIST_192_TOP); 471280304Sjkim else 472280304Sjkim carry = 1; 473160814Ssimon 474280304Sjkim /* 475280304Sjkim * we need 'if (carry==0 || result>=modulus) result-=modulus;' 476280304Sjkim * as comparison implies subtraction, we can write 477280304Sjkim * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;' 478280304Sjkim * this is what happens below, but without explicit if:-) a. 479280304Sjkim */ 480280304Sjkim mask = 481280304Sjkim 0 - (PTR_SIZE_INT) bn_sub_words(c_d, r_d, _nist_p_192[0], 482280304Sjkim BN_NIST_192_TOP); 483280304Sjkim mask &= 0 - (PTR_SIZE_INT) carry; 484280304Sjkim res = c_d; 485280304Sjkim res = (BN_ULONG *) 486280304Sjkim (((PTR_SIZE_INT) res & ~mask) | ((PTR_SIZE_INT) r_d & mask)); 487280304Sjkim nist_cp_bn(r_d, res, BN_NIST_192_TOP); 488280304Sjkim r->top = BN_NIST_192_TOP; 489280304Sjkim bn_correct_top(r); 490160814Ssimon 491280304Sjkim return 1; 492280304Sjkim} 493160814Ssimon 494280304Sjkimtypedef BN_ULONG (*bn_addsub_f) (BN_ULONG *, const BN_ULONG *, 495280304Sjkim const BN_ULONG *, int); 496194206Ssimon 497160814Ssimon#define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \ 498280304Sjkim { \ 499280304Sjkim bn_cp_32(to, 0, from, (a7) - 7) \ 500280304Sjkim bn_cp_32(to, 1, from, (a6) - 7) \ 501280304Sjkim bn_cp_32(to, 2, from, (a5) - 7) \ 502280304Sjkim bn_cp_32(to, 3, from, (a4) - 7) \ 503280304Sjkim bn_cp_32(to, 4, from, (a3) - 7) \ 504280304Sjkim bn_cp_32(to, 5, from, (a2) - 7) \ 505280304Sjkim bn_cp_32(to, 6, from, (a1) - 7) \ 506280304Sjkim } 507160814Ssimon 508160814Ssimonint BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 509280304Sjkim BN_CTX *ctx) 510280304Sjkim{ 511280304Sjkim int top = a->top, i; 512280304Sjkim int carry; 513280304Sjkim BN_ULONG *r_d, *a_d = a->d; 514280304Sjkim union { 515280304Sjkim BN_ULONG bn[BN_NIST_224_TOP]; 516280304Sjkim unsigned int ui[BN_NIST_224_TOP * sizeof(BN_ULONG) / 517280304Sjkim sizeof(unsigned int)]; 518280304Sjkim } buf; 519280304Sjkim BN_ULONG c_d[BN_NIST_224_TOP], *res; 520280304Sjkim PTR_SIZE_INT mask; 521280304Sjkim union { 522280304Sjkim bn_addsub_f f; 523280304Sjkim PTR_SIZE_INT p; 524280304Sjkim } u; 525280304Sjkim static const BIGNUM _bignum_nist_p_224_sqr = { 526280304Sjkim (BN_ULONG *)_nist_p_224_sqr, 527280304Sjkim sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]), 528280304Sjkim sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]), 529280304Sjkim 0, BN_FLG_STATIC_DATA 530280304Sjkim }; 531160814Ssimon 532280304Sjkim field = &_bignum_nist_p_224; /* just to make sure */ 533194206Ssimon 534280304Sjkim if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_224_sqr) >= 0) 535280304Sjkim return BN_nnmod(r, a, field, ctx); 536194206Ssimon 537280304Sjkim i = BN_ucmp(field, a); 538280304Sjkim if (i == 0) { 539280304Sjkim BN_zero(r); 540280304Sjkim return 1; 541280304Sjkim } else if (i > 0) 542280304Sjkim return (r == a) ? 1 : (BN_copy(r, a) != NULL); 543194206Ssimon 544280304Sjkim if (r != a) { 545280304Sjkim if (!bn_wexpand(r, BN_NIST_224_TOP)) 546280304Sjkim return 0; 547280304Sjkim r_d = r->d; 548280304Sjkim nist_cp_bn(r_d, a_d, BN_NIST_224_TOP); 549280304Sjkim } else 550280304Sjkim r_d = a_d; 551160814Ssimon 552194206Ssimon#if BN_BITS2==64 553280304Sjkim /* copy upper 256 bits of 448 bit number ... */ 554280304Sjkim nist_cp_bn_0(c_d, a_d + (BN_NIST_224_TOP - 1), 555280304Sjkim top - (BN_NIST_224_TOP - 1), BN_NIST_224_TOP); 556280304Sjkim /* ... and right shift by 32 to obtain upper 224 bits */ 557280304Sjkim nist_set_224(buf.bn, c_d, 14, 13, 12, 11, 10, 9, 8); 558280304Sjkim /* truncate lower part to 224 bits too */ 559280304Sjkim r_d[BN_NIST_224_TOP - 1] &= BN_MASK2l; 560194206Ssimon#else 561280304Sjkim nist_cp_bn_0(buf.bn, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP, 562280304Sjkim BN_NIST_224_TOP); 563194206Ssimon#endif 564238405Sjkim 565238405Sjkim#if defined(NIST_INT64) && BN_BITS2!=64 566280304Sjkim { 567280304Sjkim NIST_INT64 acc; /* accumulator */ 568280304Sjkim unsigned int *rp = (unsigned int *)r_d; 569280304Sjkim const unsigned int *bp = (const unsigned int *)buf.ui; 570238405Sjkim 571280304Sjkim acc = rp[0]; 572280304Sjkim acc -= bp[7 - 7]; 573280304Sjkim acc -= bp[11 - 7]; 574280304Sjkim rp[0] = (unsigned int)acc; 575280304Sjkim acc >>= 32; 576238405Sjkim 577280304Sjkim acc += rp[1]; 578280304Sjkim acc -= bp[8 - 7]; 579280304Sjkim acc -= bp[12 - 7]; 580280304Sjkim rp[1] = (unsigned int)acc; 581280304Sjkim acc >>= 32; 582238405Sjkim 583280304Sjkim acc += rp[2]; 584280304Sjkim acc -= bp[9 - 7]; 585280304Sjkim acc -= bp[13 - 7]; 586280304Sjkim rp[2] = (unsigned int)acc; 587280304Sjkim acc >>= 32; 588238405Sjkim 589280304Sjkim acc += rp[3]; 590280304Sjkim acc += bp[7 - 7]; 591280304Sjkim acc += bp[11 - 7]; 592280304Sjkim acc -= bp[10 - 7]; 593280304Sjkim rp[3] = (unsigned int)acc; 594280304Sjkim acc >>= 32; 595238405Sjkim 596280304Sjkim acc += rp[4]; 597280304Sjkim acc += bp[8 - 7]; 598280304Sjkim acc += bp[12 - 7]; 599280304Sjkim acc -= bp[11 - 7]; 600280304Sjkim rp[4] = (unsigned int)acc; 601280304Sjkim acc >>= 32; 602238405Sjkim 603280304Sjkim acc += rp[5]; 604280304Sjkim acc += bp[9 - 7]; 605280304Sjkim acc += bp[13 - 7]; 606280304Sjkim acc -= bp[12 - 7]; 607280304Sjkim rp[5] = (unsigned int)acc; 608280304Sjkim acc >>= 32; 609238405Sjkim 610280304Sjkim acc += rp[6]; 611280304Sjkim acc += bp[10 - 7]; 612280304Sjkim acc -= bp[13 - 7]; 613280304Sjkim rp[6] = (unsigned int)acc; 614238405Sjkim 615280304Sjkim carry = (int)(acc >> 32); 616238405Sjkim# if BN_BITS2==64 617280304Sjkim rp[7] = carry; 618238405Sjkim# endif 619280304Sjkim } 620238405Sjkim#else 621280304Sjkim { 622280304Sjkim BN_ULONG t_d[BN_NIST_224_TOP]; 623238405Sjkim 624280304Sjkim nist_set_224(t_d, buf.bn, 10, 9, 8, 7, 0, 0, 0); 625280304Sjkim carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP); 626280304Sjkim nist_set_224(t_d, buf.bn, 0, 13, 12, 11, 0, 0, 0); 627280304Sjkim carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP); 628280304Sjkim nist_set_224(t_d, buf.bn, 13, 12, 11, 10, 9, 8, 7); 629280304Sjkim carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP); 630280304Sjkim nist_set_224(t_d, buf.bn, 0, 0, 0, 0, 13, 12, 11); 631280304Sjkim carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP); 632160814Ssimon 633280304Sjkim# if BN_BITS2==64 634280304Sjkim carry = (int)(r_d[BN_NIST_224_TOP - 1] >> 32); 635280304Sjkim# endif 636280304Sjkim } 637194206Ssimon#endif 638280304Sjkim u.f = bn_sub_words; 639280304Sjkim if (carry > 0) { 640280304Sjkim carry = 641280304Sjkim (int)bn_sub_words(r_d, r_d, _nist_p_224[carry - 1], 642280304Sjkim BN_NIST_224_TOP); 643194206Ssimon#if BN_BITS2==64 644280304Sjkim carry = (int)(~(r_d[BN_NIST_224_TOP - 1] >> 32)) & 1; 645194206Ssimon#endif 646280304Sjkim } else if (carry < 0) { 647280304Sjkim /* 648280304Sjkim * it's a bit more comlicated logic in this case. if bn_add_words 649280304Sjkim * yields no carry, then result has to be adjusted by unconditionally 650280304Sjkim * *adding* the modulus. but if it does, then result has to be 651280304Sjkim * compared to the modulus and conditionally adjusted by 652280304Sjkim * *subtracting* the latter. 653280304Sjkim */ 654280304Sjkim carry = 655280304Sjkim (int)bn_add_words(r_d, r_d, _nist_p_224[-carry - 1], 656280304Sjkim BN_NIST_224_TOP); 657280304Sjkim mask = 0 - (PTR_SIZE_INT) carry; 658280304Sjkim u.p = ((PTR_SIZE_INT) bn_sub_words & mask) | 659280304Sjkim ((PTR_SIZE_INT) bn_add_words & ~mask); 660280304Sjkim } else 661280304Sjkim carry = 1; 662160814Ssimon 663280304Sjkim /* otherwise it's effectively same as in BN_nist_mod_192... */ 664280304Sjkim mask = 665280304Sjkim 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_224[0], BN_NIST_224_TOP); 666280304Sjkim mask &= 0 - (PTR_SIZE_INT) carry; 667280304Sjkim res = c_d; 668280304Sjkim res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) | 669280304Sjkim ((PTR_SIZE_INT) r_d & mask)); 670280304Sjkim nist_cp_bn(r_d, res, BN_NIST_224_TOP); 671280304Sjkim r->top = BN_NIST_224_TOP; 672280304Sjkim bn_correct_top(r); 673194206Ssimon 674280304Sjkim return 1; 675280304Sjkim} 676160814Ssimon 677160814Ssimon#define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \ 678280304Sjkim { \ 679280304Sjkim bn_cp_32(to, 0, from, (a8) - 8) \ 680280304Sjkim bn_cp_32(to, 1, from, (a7) - 8) \ 681280304Sjkim bn_cp_32(to, 2, from, (a6) - 8) \ 682280304Sjkim bn_cp_32(to, 3, from, (a5) - 8) \ 683280304Sjkim bn_cp_32(to, 4, from, (a4) - 8) \ 684280304Sjkim bn_cp_32(to, 5, from, (a3) - 8) \ 685280304Sjkim bn_cp_32(to, 6, from, (a2) - 8) \ 686280304Sjkim bn_cp_32(to, 7, from, (a1) - 8) \ 687280304Sjkim } 688160814Ssimon 689160814Ssimonint BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 690280304Sjkim BN_CTX *ctx) 691280304Sjkim{ 692280304Sjkim int i, top = a->top; 693280304Sjkim int carry = 0; 694280304Sjkim register BN_ULONG *a_d = a->d, *r_d; 695280304Sjkim union { 696280304Sjkim BN_ULONG bn[BN_NIST_256_TOP]; 697280304Sjkim unsigned int ui[BN_NIST_256_TOP * sizeof(BN_ULONG) / 698280304Sjkim sizeof(unsigned int)]; 699280304Sjkim } buf; 700280304Sjkim BN_ULONG c_d[BN_NIST_256_TOP], *res; 701280304Sjkim PTR_SIZE_INT mask; 702280304Sjkim union { 703280304Sjkim bn_addsub_f f; 704280304Sjkim PTR_SIZE_INT p; 705280304Sjkim } u; 706280304Sjkim static const BIGNUM _bignum_nist_p_256_sqr = { 707280304Sjkim (BN_ULONG *)_nist_p_256_sqr, 708280304Sjkim sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]), 709280304Sjkim sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]), 710280304Sjkim 0, BN_FLG_STATIC_DATA 711280304Sjkim }; 712160814Ssimon 713280304Sjkim field = &_bignum_nist_p_256; /* just to make sure */ 714194206Ssimon 715280304Sjkim if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_256_sqr) >= 0) 716280304Sjkim return BN_nnmod(r, a, field, ctx); 717194206Ssimon 718280304Sjkim i = BN_ucmp(field, a); 719280304Sjkim if (i == 0) { 720280304Sjkim BN_zero(r); 721280304Sjkim return 1; 722280304Sjkim } else if (i > 0) 723280304Sjkim return (r == a) ? 1 : (BN_copy(r, a) != NULL); 724160814Ssimon 725280304Sjkim if (r != a) { 726280304Sjkim if (!bn_wexpand(r, BN_NIST_256_TOP)) 727280304Sjkim return 0; 728280304Sjkim r_d = r->d; 729280304Sjkim nist_cp_bn(r_d, a_d, BN_NIST_256_TOP); 730280304Sjkim } else 731280304Sjkim r_d = a_d; 732160814Ssimon 733280304Sjkim nist_cp_bn_0(buf.bn, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP, 734280304Sjkim BN_NIST_256_TOP); 735160814Ssimon 736238405Sjkim#if defined(NIST_INT64) 737280304Sjkim { 738280304Sjkim NIST_INT64 acc; /* accumulator */ 739280304Sjkim unsigned int *rp = (unsigned int *)r_d; 740280304Sjkim const unsigned int *bp = (const unsigned int *)buf.ui; 741238405Sjkim 742280304Sjkim acc = rp[0]; 743280304Sjkim acc += bp[8 - 8]; 744280304Sjkim acc += bp[9 - 8]; 745280304Sjkim acc -= bp[11 - 8]; 746280304Sjkim acc -= bp[12 - 8]; 747280304Sjkim acc -= bp[13 - 8]; 748280304Sjkim acc -= bp[14 - 8]; 749280304Sjkim rp[0] = (unsigned int)acc; 750280304Sjkim acc >>= 32; 751238405Sjkim 752280304Sjkim acc += rp[1]; 753280304Sjkim acc += bp[9 - 8]; 754280304Sjkim acc += bp[10 - 8]; 755280304Sjkim acc -= bp[12 - 8]; 756280304Sjkim acc -= bp[13 - 8]; 757280304Sjkim acc -= bp[14 - 8]; 758280304Sjkim acc -= bp[15 - 8]; 759280304Sjkim rp[1] = (unsigned int)acc; 760280304Sjkim acc >>= 32; 761238405Sjkim 762280304Sjkim acc += rp[2]; 763280304Sjkim acc += bp[10 - 8]; 764280304Sjkim acc += bp[11 - 8]; 765280304Sjkim acc -= bp[13 - 8]; 766280304Sjkim acc -= bp[14 - 8]; 767280304Sjkim acc -= bp[15 - 8]; 768280304Sjkim rp[2] = (unsigned int)acc; 769280304Sjkim acc >>= 32; 770238405Sjkim 771280304Sjkim acc += rp[3]; 772280304Sjkim acc += bp[11 - 8]; 773280304Sjkim acc += bp[11 - 8]; 774280304Sjkim acc += bp[12 - 8]; 775280304Sjkim acc += bp[12 - 8]; 776280304Sjkim acc += bp[13 - 8]; 777280304Sjkim acc -= bp[15 - 8]; 778280304Sjkim acc -= bp[8 - 8]; 779280304Sjkim acc -= bp[9 - 8]; 780280304Sjkim rp[3] = (unsigned int)acc; 781280304Sjkim acc >>= 32; 782238405Sjkim 783280304Sjkim acc += rp[4]; 784280304Sjkim acc += bp[12 - 8]; 785280304Sjkim acc += bp[12 - 8]; 786280304Sjkim acc += bp[13 - 8]; 787280304Sjkim acc += bp[13 - 8]; 788280304Sjkim acc += bp[14 - 8]; 789280304Sjkim acc -= bp[9 - 8]; 790280304Sjkim acc -= bp[10 - 8]; 791280304Sjkim rp[4] = (unsigned int)acc; 792280304Sjkim acc >>= 32; 793238405Sjkim 794280304Sjkim acc += rp[5]; 795280304Sjkim acc += bp[13 - 8]; 796280304Sjkim acc += bp[13 - 8]; 797280304Sjkim acc += bp[14 - 8]; 798280304Sjkim acc += bp[14 - 8]; 799280304Sjkim acc += bp[15 - 8]; 800280304Sjkim acc -= bp[10 - 8]; 801280304Sjkim acc -= bp[11 - 8]; 802280304Sjkim rp[5] = (unsigned int)acc; 803280304Sjkim acc >>= 32; 804238405Sjkim 805280304Sjkim acc += rp[6]; 806280304Sjkim acc += bp[14 - 8]; 807280304Sjkim acc += bp[14 - 8]; 808280304Sjkim acc += bp[15 - 8]; 809280304Sjkim acc += bp[15 - 8]; 810280304Sjkim acc += bp[14 - 8]; 811280304Sjkim acc += bp[13 - 8]; 812280304Sjkim acc -= bp[8 - 8]; 813280304Sjkim acc -= bp[9 - 8]; 814280304Sjkim rp[6] = (unsigned int)acc; 815280304Sjkim acc >>= 32; 816238405Sjkim 817280304Sjkim acc += rp[7]; 818280304Sjkim acc += bp[15 - 8]; 819280304Sjkim acc += bp[15 - 8]; 820280304Sjkim acc += bp[15 - 8]; 821280304Sjkim acc += bp[8 - 8]; 822280304Sjkim acc -= bp[10 - 8]; 823280304Sjkim acc -= bp[11 - 8]; 824280304Sjkim acc -= bp[12 - 8]; 825280304Sjkim acc -= bp[13 - 8]; 826280304Sjkim rp[7] = (unsigned int)acc; 827238405Sjkim 828280304Sjkim carry = (int)(acc >> 32); 829280304Sjkim } 830238405Sjkim#else 831280304Sjkim { 832280304Sjkim BN_ULONG t_d[BN_NIST_256_TOP]; 833238405Sjkim 834280304Sjkim /* 835280304Sjkim * S1 836280304Sjkim */ 837280304Sjkim nist_set_256(t_d, buf.bn, 15, 14, 13, 12, 11, 0, 0, 0); 838280304Sjkim /* 839280304Sjkim * S2 840280304Sjkim */ 841280304Sjkim nist_set_256(c_d, buf.bn, 0, 15, 14, 13, 12, 0, 0, 0); 842280304Sjkim carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP); 843280304Sjkim /* left shift */ 844280304Sjkim { 845280304Sjkim register BN_ULONG *ap, t, c; 846280304Sjkim ap = t_d; 847280304Sjkim c = 0; 848280304Sjkim for (i = BN_NIST_256_TOP; i != 0; --i) { 849280304Sjkim t = *ap; 850280304Sjkim *(ap++) = ((t << 1) | c) & BN_MASK2; 851280304Sjkim c = (t & BN_TBIT) ? 1 : 0; 852280304Sjkim } 853280304Sjkim carry <<= 1; 854280304Sjkim carry |= c; 855280304Sjkim } 856280304Sjkim carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 857280304Sjkim /* 858280304Sjkim * S3 859280304Sjkim */ 860280304Sjkim nist_set_256(t_d, buf.bn, 15, 14, 0, 0, 0, 10, 9, 8); 861280304Sjkim carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 862280304Sjkim /* 863280304Sjkim * S4 864280304Sjkim */ 865280304Sjkim nist_set_256(t_d, buf.bn, 8, 13, 15, 14, 13, 11, 10, 9); 866280304Sjkim carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 867280304Sjkim /* 868280304Sjkim * D1 869280304Sjkim */ 870280304Sjkim nist_set_256(t_d, buf.bn, 10, 8, 0, 0, 0, 13, 12, 11); 871280304Sjkim carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 872280304Sjkim /* 873280304Sjkim * D2 874280304Sjkim */ 875280304Sjkim nist_set_256(t_d, buf.bn, 11, 9, 0, 0, 15, 14, 13, 12); 876280304Sjkim carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 877280304Sjkim /* 878280304Sjkim * D3 879280304Sjkim */ 880280304Sjkim nist_set_256(t_d, buf.bn, 12, 0, 10, 9, 8, 15, 14, 13); 881280304Sjkim carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 882280304Sjkim /* 883280304Sjkim * D4 884280304Sjkim */ 885280304Sjkim nist_set_256(t_d, buf.bn, 13, 0, 11, 10, 9, 0, 15, 14); 886280304Sjkim carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 887194206Ssimon 888280304Sjkim } 889238405Sjkim#endif 890280304Sjkim /* see BN_nist_mod_224 for explanation */ 891280304Sjkim u.f = bn_sub_words; 892280304Sjkim if (carry > 0) 893280304Sjkim carry = 894280304Sjkim (int)bn_sub_words(r_d, r_d, _nist_p_256[carry - 1], 895280304Sjkim BN_NIST_256_TOP); 896280304Sjkim else if (carry < 0) { 897280304Sjkim carry = 898280304Sjkim (int)bn_add_words(r_d, r_d, _nist_p_256[-carry - 1], 899280304Sjkim BN_NIST_256_TOP); 900280304Sjkim mask = 0 - (PTR_SIZE_INT) carry; 901280304Sjkim u.p = ((PTR_SIZE_INT) bn_sub_words & mask) | 902280304Sjkim ((PTR_SIZE_INT) bn_add_words & ~mask); 903280304Sjkim } else 904280304Sjkim carry = 1; 905160814Ssimon 906280304Sjkim mask = 907280304Sjkim 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_256[0], BN_NIST_256_TOP); 908280304Sjkim mask &= 0 - (PTR_SIZE_INT) carry; 909280304Sjkim res = c_d; 910280304Sjkim res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) | 911280304Sjkim ((PTR_SIZE_INT) r_d & mask)); 912280304Sjkim nist_cp_bn(r_d, res, BN_NIST_256_TOP); 913280304Sjkim r->top = BN_NIST_256_TOP; 914280304Sjkim bn_correct_top(r); 915194206Ssimon 916280304Sjkim return 1; 917280304Sjkim} 918160814Ssimon 919160814Ssimon#define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \ 920280304Sjkim { \ 921280304Sjkim bn_cp_32(to, 0, from, (a12) - 12) \ 922280304Sjkim bn_cp_32(to, 1, from, (a11) - 12) \ 923280304Sjkim bn_cp_32(to, 2, from, (a10) - 12) \ 924280304Sjkim bn_cp_32(to, 3, from, (a9) - 12) \ 925280304Sjkim bn_cp_32(to, 4, from, (a8) - 12) \ 926280304Sjkim bn_cp_32(to, 5, from, (a7) - 12) \ 927280304Sjkim bn_cp_32(to, 6, from, (a6) - 12) \ 928280304Sjkim bn_cp_32(to, 7, from, (a5) - 12) \ 929280304Sjkim bn_cp_32(to, 8, from, (a4) - 12) \ 930280304Sjkim bn_cp_32(to, 9, from, (a3) - 12) \ 931280304Sjkim bn_cp_32(to, 10, from, (a2) - 12) \ 932280304Sjkim bn_cp_32(to, 11, from, (a1) - 12) \ 933280304Sjkim } 934160814Ssimon 935160814Ssimonint BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 936280304Sjkim BN_CTX *ctx) 937280304Sjkim{ 938280304Sjkim int i, top = a->top; 939280304Sjkim int carry = 0; 940280304Sjkim register BN_ULONG *r_d, *a_d = a->d; 941280304Sjkim union { 942280304Sjkim BN_ULONG bn[BN_NIST_384_TOP]; 943280304Sjkim unsigned int ui[BN_NIST_384_TOP * sizeof(BN_ULONG) / 944280304Sjkim sizeof(unsigned int)]; 945280304Sjkim } buf; 946280304Sjkim BN_ULONG c_d[BN_NIST_384_TOP], *res; 947280304Sjkim PTR_SIZE_INT mask; 948280304Sjkim union { 949280304Sjkim bn_addsub_f f; 950280304Sjkim PTR_SIZE_INT p; 951280304Sjkim } u; 952280304Sjkim static const BIGNUM _bignum_nist_p_384_sqr = { 953280304Sjkim (BN_ULONG *)_nist_p_384_sqr, 954280304Sjkim sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]), 955280304Sjkim sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]), 956280304Sjkim 0, BN_FLG_STATIC_DATA 957280304Sjkim }; 958160814Ssimon 959280304Sjkim field = &_bignum_nist_p_384; /* just to make sure */ 960160814Ssimon 961280304Sjkim if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_384_sqr) >= 0) 962280304Sjkim return BN_nnmod(r, a, field, ctx); 963160814Ssimon 964280304Sjkim i = BN_ucmp(field, a); 965280304Sjkim if (i == 0) { 966280304Sjkim BN_zero(r); 967280304Sjkim return 1; 968280304Sjkim } else if (i > 0) 969280304Sjkim return (r == a) ? 1 : (BN_copy(r, a) != NULL); 970194206Ssimon 971280304Sjkim if (r != a) { 972280304Sjkim if (!bn_wexpand(r, BN_NIST_384_TOP)) 973280304Sjkim return 0; 974280304Sjkim r_d = r->d; 975280304Sjkim nist_cp_bn(r_d, a_d, BN_NIST_384_TOP); 976280304Sjkim } else 977280304Sjkim r_d = a_d; 978160814Ssimon 979280304Sjkim nist_cp_bn_0(buf.bn, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP, 980280304Sjkim BN_NIST_384_TOP); 981160814Ssimon 982238405Sjkim#if defined(NIST_INT64) 983280304Sjkim { 984280304Sjkim NIST_INT64 acc; /* accumulator */ 985280304Sjkim unsigned int *rp = (unsigned int *)r_d; 986280304Sjkim const unsigned int *bp = (const unsigned int *)buf.ui; 987238405Sjkim 988280304Sjkim acc = rp[0]; 989280304Sjkim acc += bp[12 - 12]; 990280304Sjkim acc += bp[21 - 12]; 991280304Sjkim acc += bp[20 - 12]; 992280304Sjkim acc -= bp[23 - 12]; 993280304Sjkim rp[0] = (unsigned int)acc; 994280304Sjkim acc >>= 32; 995238405Sjkim 996280304Sjkim acc += rp[1]; 997280304Sjkim acc += bp[13 - 12]; 998280304Sjkim acc += bp[22 - 12]; 999280304Sjkim acc += bp[23 - 12]; 1000280304Sjkim acc -= bp[12 - 12]; 1001280304Sjkim acc -= bp[20 - 12]; 1002280304Sjkim rp[1] = (unsigned int)acc; 1003280304Sjkim acc >>= 32; 1004238405Sjkim 1005280304Sjkim acc += rp[2]; 1006280304Sjkim acc += bp[14 - 12]; 1007280304Sjkim acc += bp[23 - 12]; 1008280304Sjkim acc -= bp[13 - 12]; 1009280304Sjkim acc -= bp[21 - 12]; 1010280304Sjkim rp[2] = (unsigned int)acc; 1011280304Sjkim acc >>= 32; 1012238405Sjkim 1013280304Sjkim acc += rp[3]; 1014280304Sjkim acc += bp[15 - 12]; 1015280304Sjkim acc += bp[12 - 12]; 1016280304Sjkim acc += bp[20 - 12]; 1017280304Sjkim acc += bp[21 - 12]; 1018280304Sjkim acc -= bp[14 - 12]; 1019280304Sjkim acc -= bp[22 - 12]; 1020280304Sjkim acc -= bp[23 - 12]; 1021280304Sjkim rp[3] = (unsigned int)acc; 1022280304Sjkim acc >>= 32; 1023238405Sjkim 1024280304Sjkim acc += rp[4]; 1025280304Sjkim acc += bp[21 - 12]; 1026280304Sjkim acc += bp[21 - 12]; 1027280304Sjkim acc += bp[16 - 12]; 1028280304Sjkim acc += bp[13 - 12]; 1029280304Sjkim acc += bp[12 - 12]; 1030280304Sjkim acc += bp[20 - 12]; 1031280304Sjkim acc += bp[22 - 12]; 1032280304Sjkim acc -= bp[15 - 12]; 1033280304Sjkim acc -= bp[23 - 12]; 1034280304Sjkim acc -= bp[23 - 12]; 1035280304Sjkim rp[4] = (unsigned int)acc; 1036280304Sjkim acc >>= 32; 1037238405Sjkim 1038280304Sjkim acc += rp[5]; 1039280304Sjkim acc += bp[22 - 12]; 1040280304Sjkim acc += bp[22 - 12]; 1041280304Sjkim acc += bp[17 - 12]; 1042280304Sjkim acc += bp[14 - 12]; 1043280304Sjkim acc += bp[13 - 12]; 1044280304Sjkim acc += bp[21 - 12]; 1045280304Sjkim acc += bp[23 - 12]; 1046280304Sjkim acc -= bp[16 - 12]; 1047280304Sjkim rp[5] = (unsigned int)acc; 1048280304Sjkim acc >>= 32; 1049238405Sjkim 1050280304Sjkim acc += rp[6]; 1051280304Sjkim acc += bp[23 - 12]; 1052280304Sjkim acc += bp[23 - 12]; 1053280304Sjkim acc += bp[18 - 12]; 1054280304Sjkim acc += bp[15 - 12]; 1055280304Sjkim acc += bp[14 - 12]; 1056280304Sjkim acc += bp[22 - 12]; 1057280304Sjkim acc -= bp[17 - 12]; 1058280304Sjkim rp[6] = (unsigned int)acc; 1059280304Sjkim acc >>= 32; 1060280304Sjkim 1061280304Sjkim acc += rp[7]; 1062280304Sjkim acc += bp[19 - 12]; 1063280304Sjkim acc += bp[16 - 12]; 1064280304Sjkim acc += bp[15 - 12]; 1065280304Sjkim acc += bp[23 - 12]; 1066280304Sjkim acc -= bp[18 - 12]; 1067280304Sjkim rp[7] = (unsigned int)acc; 1068280304Sjkim acc >>= 32; 1069280304Sjkim 1070280304Sjkim acc += rp[8]; 1071280304Sjkim acc += bp[20 - 12]; 1072280304Sjkim acc += bp[17 - 12]; 1073280304Sjkim acc += bp[16 - 12]; 1074280304Sjkim acc -= bp[19 - 12]; 1075280304Sjkim rp[8] = (unsigned int)acc; 1076280304Sjkim acc >>= 32; 1077280304Sjkim 1078280304Sjkim acc += rp[9]; 1079280304Sjkim acc += bp[21 - 12]; 1080280304Sjkim acc += bp[18 - 12]; 1081280304Sjkim acc += bp[17 - 12]; 1082280304Sjkim acc -= bp[20 - 12]; 1083280304Sjkim rp[9] = (unsigned int)acc; 1084280304Sjkim acc >>= 32; 1085280304Sjkim 1086280304Sjkim acc += rp[10]; 1087280304Sjkim acc += bp[22 - 12]; 1088280304Sjkim acc += bp[19 - 12]; 1089280304Sjkim acc += bp[18 - 12]; 1090280304Sjkim acc -= bp[21 - 12]; 1091280304Sjkim rp[10] = (unsigned int)acc; 1092280304Sjkim acc >>= 32; 1093280304Sjkim 1094280304Sjkim acc += rp[11]; 1095280304Sjkim acc += bp[23 - 12]; 1096280304Sjkim acc += bp[20 - 12]; 1097280304Sjkim acc += bp[19 - 12]; 1098280304Sjkim acc -= bp[22 - 12]; 1099280304Sjkim rp[11] = (unsigned int)acc; 1100280304Sjkim 1101280304Sjkim carry = (int)(acc >> 32); 1102280304Sjkim } 1103238405Sjkim#else 1104280304Sjkim { 1105280304Sjkim BN_ULONG t_d[BN_NIST_384_TOP]; 1106238405Sjkim 1107280304Sjkim /* 1108280304Sjkim * S1 1109280304Sjkim */ 1110280304Sjkim nist_set_256(t_d, buf.bn, 0, 0, 0, 0, 0, 23 - 4, 22 - 4, 21 - 4); 1111280304Sjkim /* left shift */ 1112280304Sjkim { 1113280304Sjkim register BN_ULONG *ap, t, c; 1114280304Sjkim ap = t_d; 1115280304Sjkim c = 0; 1116280304Sjkim for (i = 3; i != 0; --i) { 1117280304Sjkim t = *ap; 1118280304Sjkim *(ap++) = ((t << 1) | c) & BN_MASK2; 1119280304Sjkim c = (t & BN_TBIT) ? 1 : 0; 1120280304Sjkim } 1121280304Sjkim *ap = c; 1122280304Sjkim } 1123280304Sjkim carry = 1124280304Sjkim (int)bn_add_words(r_d + (128 / BN_BITS2), r_d + (128 / BN_BITS2), 1125280304Sjkim t_d, BN_NIST_256_TOP); 1126280304Sjkim /* 1127280304Sjkim * S2 1128280304Sjkim */ 1129280304Sjkim carry += (int)bn_add_words(r_d, r_d, buf.bn, BN_NIST_384_TOP); 1130280304Sjkim /* 1131280304Sjkim * S3 1132280304Sjkim */ 1133280304Sjkim nist_set_384(t_d, buf.bn, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 22, 1134280304Sjkim 21); 1135280304Sjkim carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 1136280304Sjkim /* 1137280304Sjkim * S4 1138280304Sjkim */ 1139280304Sjkim nist_set_384(t_d, buf.bn, 19, 18, 17, 16, 15, 14, 13, 12, 20, 0, 23, 1140280304Sjkim 0); 1141280304Sjkim carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 1142280304Sjkim /* 1143280304Sjkim * S5 1144280304Sjkim */ 1145280304Sjkim nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 23, 22, 21, 20, 0, 0, 0, 0); 1146280304Sjkim carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 1147280304Sjkim /* 1148280304Sjkim * S6 1149280304Sjkim */ 1150280304Sjkim nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 23, 22, 21, 0, 0, 20); 1151280304Sjkim carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 1152280304Sjkim /* 1153280304Sjkim * D1 1154280304Sjkim */ 1155280304Sjkim nist_set_384(t_d, buf.bn, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 1156280304Sjkim 23); 1157280304Sjkim carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 1158280304Sjkim /* 1159280304Sjkim * D2 1160280304Sjkim */ 1161280304Sjkim nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 22, 21, 20, 0); 1162280304Sjkim carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 1163280304Sjkim /* 1164280304Sjkim * D3 1165280304Sjkim */ 1166280304Sjkim nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 23, 0, 0, 0); 1167280304Sjkim carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 1168194206Ssimon 1169280304Sjkim } 1170238405Sjkim#endif 1171280304Sjkim /* see BN_nist_mod_224 for explanation */ 1172280304Sjkim u.f = bn_sub_words; 1173280304Sjkim if (carry > 0) 1174280304Sjkim carry = 1175280304Sjkim (int)bn_sub_words(r_d, r_d, _nist_p_384[carry - 1], 1176280304Sjkim BN_NIST_384_TOP); 1177280304Sjkim else if (carry < 0) { 1178280304Sjkim carry = 1179280304Sjkim (int)bn_add_words(r_d, r_d, _nist_p_384[-carry - 1], 1180280304Sjkim BN_NIST_384_TOP); 1181280304Sjkim mask = 0 - (PTR_SIZE_INT) carry; 1182280304Sjkim u.p = ((PTR_SIZE_INT) bn_sub_words & mask) | 1183280304Sjkim ((PTR_SIZE_INT) bn_add_words & ~mask); 1184280304Sjkim } else 1185280304Sjkim carry = 1; 1186160814Ssimon 1187280304Sjkim mask = 1188280304Sjkim 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_384[0], BN_NIST_384_TOP); 1189280304Sjkim mask &= 0 - (PTR_SIZE_INT) carry; 1190280304Sjkim res = c_d; 1191280304Sjkim res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) | 1192280304Sjkim ((PTR_SIZE_INT) r_d & mask)); 1193280304Sjkim nist_cp_bn(r_d, res, BN_NIST_384_TOP); 1194280304Sjkim r->top = BN_NIST_384_TOP; 1195280304Sjkim bn_correct_top(r); 1196194206Ssimon 1197280304Sjkim return 1; 1198280304Sjkim} 1199160814Ssimon 1200280304Sjkim#define BN_NIST_521_RSHIFT (521%BN_BITS2) 1201280304Sjkim#define BN_NIST_521_LSHIFT (BN_BITS2-BN_NIST_521_RSHIFT) 1202280304Sjkim#define BN_NIST_521_TOP_MASK ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT) 1203194206Ssimon 1204160814Ssimonint BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 1205280304Sjkim BN_CTX *ctx) 1206280304Sjkim{ 1207280304Sjkim int top = a->top, i; 1208280304Sjkim BN_ULONG *r_d, *a_d = a->d, t_d[BN_NIST_521_TOP], val, tmp, *res; 1209280304Sjkim PTR_SIZE_INT mask; 1210280304Sjkim static const BIGNUM _bignum_nist_p_521_sqr = { 1211280304Sjkim (BN_ULONG *)_nist_p_521_sqr, 1212280304Sjkim sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]), 1213280304Sjkim sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]), 1214280304Sjkim 0, BN_FLG_STATIC_DATA 1215280304Sjkim }; 1216160814Ssimon 1217280304Sjkim field = &_bignum_nist_p_521; /* just to make sure */ 1218160814Ssimon 1219280304Sjkim if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_521_sqr) >= 0) 1220280304Sjkim return BN_nnmod(r, a, field, ctx); 1221160814Ssimon 1222280304Sjkim i = BN_ucmp(field, a); 1223280304Sjkim if (i == 0) { 1224280304Sjkim BN_zero(r); 1225280304Sjkim return 1; 1226280304Sjkim } else if (i > 0) 1227280304Sjkim return (r == a) ? 1 : (BN_copy(r, a) != NULL); 1228160814Ssimon 1229280304Sjkim if (r != a) { 1230280304Sjkim if (!bn_wexpand(r, BN_NIST_521_TOP)) 1231280304Sjkim return 0; 1232280304Sjkim r_d = r->d; 1233280304Sjkim nist_cp_bn(r_d, a_d, BN_NIST_521_TOP); 1234280304Sjkim } else 1235280304Sjkim r_d = a_d; 1236160814Ssimon 1237280304Sjkim /* upper 521 bits, copy ... */ 1238280304Sjkim nist_cp_bn_0(t_d, a_d + (BN_NIST_521_TOP - 1), 1239280304Sjkim top - (BN_NIST_521_TOP - 1), BN_NIST_521_TOP); 1240280304Sjkim /* ... and right shift */ 1241280304Sjkim for (val = t_d[0], i = 0; i < BN_NIST_521_TOP - 1; i++) { 1242280304Sjkim t_d[i] = (val >> BN_NIST_521_RSHIFT | 1243280304Sjkim (tmp = t_d[i + 1]) << BN_NIST_521_LSHIFT) & BN_MASK2; 1244280304Sjkim val = tmp; 1245280304Sjkim } 1246280304Sjkim t_d[i] = val >> BN_NIST_521_RSHIFT; 1247280304Sjkim /* lower 521 bits */ 1248280304Sjkim r_d[i] &= BN_NIST_521_TOP_MASK; 1249194206Ssimon 1250280304Sjkim bn_add_words(r_d, r_d, t_d, BN_NIST_521_TOP); 1251280304Sjkim mask = 1252280304Sjkim 0 - (PTR_SIZE_INT) bn_sub_words(t_d, r_d, _nist_p_521, 1253280304Sjkim BN_NIST_521_TOP); 1254280304Sjkim res = t_d; 1255280304Sjkim res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) | 1256280304Sjkim ((PTR_SIZE_INT) r_d & mask)); 1257280304Sjkim nist_cp_bn(r_d, res, BN_NIST_521_TOP); 1258280304Sjkim r->top = BN_NIST_521_TOP; 1259280304Sjkim bn_correct_top(r); 1260160814Ssimon 1261280304Sjkim return 1; 1262280304Sjkim} 1263