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 13296465Sdelphij * 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 62296465Sdelphij#define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2 63296465Sdelphij#define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2 64296465Sdelphij#define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2 65296465Sdelphij#define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2 66296465Sdelphij#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] = { 71296465Sdelphij {0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFFULL}, 72296465Sdelphij {0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL}, 73296465Sdelphij {0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFFFULL} 74296465Sdelphij}; 75296465Sdelphij 76194206Ssimonstatic const BN_ULONG _nist_p_192_sqr[] = { 77296465Sdelphij 0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000001ULL, 78296465Sdelphij 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL 79296465Sdelphij}; 80296465Sdelphij 81194206Ssimonstatic const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = { 82296465Sdelphij {0x0000000000000001ULL, 0xFFFFFFFF00000000ULL, 83296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL}, 84296465Sdelphij {0x0000000000000002ULL, 0xFFFFFFFE00000000ULL, 85296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFFULL} /* this one is 86296465Sdelphij * "carry-full" */ 87296465Sdelphij}; 88296465Sdelphij 89194206Ssimonstatic const BN_ULONG _nist_p_224_sqr[] = { 90296465Sdelphij 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL, 91296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0x0000000200000000ULL, 92296465Sdelphij 0x0000000000000000ULL, 0xFFFFFFFFFFFFFFFEULL, 93296465Sdelphij 0xFFFFFFFFFFFFFFFFULL 94296465Sdelphij}; 95296465Sdelphij 96194206Ssimonstatic const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = { 97296465Sdelphij {0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL, 98296465Sdelphij 0x0000000000000000ULL, 0xFFFFFFFF00000001ULL}, 99296465Sdelphij {0xFFFFFFFFFFFFFFFEULL, 0x00000001FFFFFFFFULL, 100296465Sdelphij 0x0000000000000000ULL, 0xFFFFFFFE00000002ULL}, 101296465Sdelphij {0xFFFFFFFFFFFFFFFDULL, 0x00000002FFFFFFFFULL, 102296465Sdelphij 0x0000000000000000ULL, 0xFFFFFFFD00000003ULL}, 103296465Sdelphij {0xFFFFFFFFFFFFFFFCULL, 0x00000003FFFFFFFFULL, 104296465Sdelphij 0x0000000000000000ULL, 0xFFFFFFFC00000004ULL}, 105296465Sdelphij {0xFFFFFFFFFFFFFFFBULL, 0x00000004FFFFFFFFULL, 106296465Sdelphij 0x0000000000000000ULL, 0xFFFFFFFB00000005ULL}, 107296465Sdelphij}; 108296465Sdelphij 109194206Ssimonstatic const BN_ULONG _nist_p_256_sqr[] = { 110296465Sdelphij 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL, 111296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFEULL, 112296465Sdelphij 0x00000001FFFFFFFEULL, 0x00000001FFFFFFFEULL, 113296465Sdelphij 0xFFFFFFFE00000001ULL, 0xFFFFFFFE00000002ULL 114296465Sdelphij}; 115296465Sdelphij 116194206Ssimonstatic const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = { 117296465Sdelphij {0x00000000FFFFFFFFULL, 0xFFFFFFFF00000000ULL, 0xFFFFFFFFFFFFFFFEULL, 118296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 119296465Sdelphij {0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL, 120296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 121296465Sdelphij {0x00000002FFFFFFFDULL, 0xFFFFFFFD00000000ULL, 0xFFFFFFFFFFFFFFFCULL, 122296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 123296465Sdelphij {0x00000003FFFFFFFCULL, 0xFFFFFFFC00000000ULL, 0xFFFFFFFFFFFFFFFBULL, 124296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 125296465Sdelphij {0x00000004FFFFFFFBULL, 0xFFFFFFFB00000000ULL, 0xFFFFFFFFFFFFFFFAULL, 126296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL}, 127296465Sdelphij}; 128296465Sdelphij 129194206Ssimonstatic const BN_ULONG _nist_p_384_sqr[] = { 130296465Sdelphij 0xFFFFFFFE00000001ULL, 0x0000000200000000ULL, 0xFFFFFFFE00000000ULL, 131296465Sdelphij 0x0000000200000000ULL, 0x0000000000000001ULL, 0x0000000000000000ULL, 132296465Sdelphij 0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL, 133296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL 134296465Sdelphij}; 135296465Sdelphij 136160814Ssimonstatic const BN_ULONG _nist_p_521[] = 137296465Sdelphij { 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 138296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 139296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 140296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 141296465Sdelphij 0x00000000000001FFULL 142296465Sdelphij}; 143296465Sdelphij 144194206Ssimonstatic const BN_ULONG _nist_p_521_sqr[] = { 145296465Sdelphij 0x0000000000000001ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 146296465Sdelphij 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 147296465Sdelphij 0x0000000000000000ULL, 0x0000000000000000ULL, 0xFFFFFFFFFFFFFC00ULL, 148296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 149296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 150296465Sdelphij 0xFFFFFFFFFFFFFFFFULL, 0x000000000003FFFFULL 151296465Sdelphij}; 152160814Ssimon#elif BN_BITS2 == 32 153194206Ssimonstatic const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = { 154296465Sdelphij {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 155296465Sdelphij {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 156296465Sdelphij {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF} 157296465Sdelphij}; 158296465Sdelphij 159194206Ssimonstatic const BN_ULONG _nist_p_192_sqr[] = { 160296465Sdelphij 0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, 0x00000000, 161296465Sdelphij 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF 162296465Sdelphij}; 163296465Sdelphij 164194206Ssimonstatic const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = { 165296465Sdelphij {0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF, 166296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 167296465Sdelphij {0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE, 168296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF} 169296465Sdelphij}; 170296465Sdelphij 171194206Ssimonstatic const BN_ULONG _nist_p_224_sqr[] = { 172296465Sdelphij 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE, 173296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000002, 174296465Sdelphij 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, 175296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF 176296465Sdelphij}; 177296465Sdelphij 178194206Ssimonstatic const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = { 179296465Sdelphij {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 180296465Sdelphij 0x00000000, 0x00000000, 0x00000001, 0xFFFFFFFF}, 181296465Sdelphij {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, 182296465Sdelphij 0x00000000, 0x00000000, 0x00000002, 0xFFFFFFFE}, 183296465Sdelphij {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000002, 184296465Sdelphij 0x00000000, 0x00000000, 0x00000003, 0xFFFFFFFD}, 185296465Sdelphij {0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000003, 186296465Sdelphij 0x00000000, 0x00000000, 0x00000004, 0xFFFFFFFC}, 187296465Sdelphij {0xFFFFFFFB, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000004, 188296465Sdelphij 0x00000000, 0x00000000, 0x00000005, 0xFFFFFFFB}, 189296465Sdelphij}; 190296465Sdelphij 191194206Ssimonstatic const BN_ULONG _nist_p_256_sqr[] = { 192296465Sdelphij 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE, 193296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0x00000001, 194296465Sdelphij 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 195296465Sdelphij 0x00000001, 0xFFFFFFFE, 0x00000002, 0xFFFFFFFE 196296465Sdelphij}; 197296465Sdelphij 198194206Ssimonstatic const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = { 199296465Sdelphij {0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 200296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 201296465Sdelphij {0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF, 202296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 203296465Sdelphij {0xFFFFFFFD, 0x00000002, 0x00000000, 0xFFFFFFFD, 0xFFFFFFFC, 0xFFFFFFFF, 204296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 205296465Sdelphij {0xFFFFFFFC, 0x00000003, 0x00000000, 0xFFFFFFFC, 0xFFFFFFFB, 0xFFFFFFFF, 206296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 207296465Sdelphij {0xFFFFFFFB, 0x00000004, 0x00000000, 0xFFFFFFFB, 0xFFFFFFFA, 0xFFFFFFFF, 208296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}, 209296465Sdelphij}; 210296465Sdelphij 211194206Ssimonstatic const BN_ULONG _nist_p_384_sqr[] = { 212296465Sdelphij 0x00000001, 0xFFFFFFFE, 0x00000000, 0x00000002, 0x00000000, 0xFFFFFFFE, 213296465Sdelphij 0x00000000, 0x00000002, 0x00000001, 0x00000000, 0x00000000, 0x00000000, 214296465Sdelphij 0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF, 215296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF 216296465Sdelphij}; 217296465Sdelphij 218296465Sdelphijstatic const BN_ULONG _nist_p_521[] = { 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 219296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 220296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 221296465Sdelphij 0xFFFFFFFF, 0x000001FF 222296465Sdelphij}; 223296465Sdelphij 224194206Ssimonstatic const BN_ULONG _nist_p_521_sqr[] = { 225296465Sdelphij 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 226296465Sdelphij 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 227296465Sdelphij 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFC00, 0xFFFFFFFF, 228296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 229296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 230296465Sdelphij 0xFFFFFFFF, 0xFFFFFFFF, 0x0003FFFF 231296465Sdelphij}; 232194206Ssimon#else 233296465Sdelphij# error "unsupported BN_BITS2" 234160814Ssimon#endif 235160814Ssimon 236296465Sdelphijstatic const BIGNUM _bignum_nist_p_192 = { 237296465Sdelphij (BN_ULONG *)_nist_p_192[0], 238296465Sdelphij BN_NIST_192_TOP, 239296465Sdelphij BN_NIST_192_TOP, 240296465Sdelphij 0, 241296465Sdelphij BN_FLG_STATIC_DATA 242296465Sdelphij}; 243194206Ssimon 244296465Sdelphijstatic const BIGNUM _bignum_nist_p_224 = { 245296465Sdelphij (BN_ULONG *)_nist_p_224[0], 246296465Sdelphij BN_NIST_224_TOP, 247296465Sdelphij BN_NIST_224_TOP, 248296465Sdelphij 0, 249296465Sdelphij BN_FLG_STATIC_DATA 250296465Sdelphij}; 251194206Ssimon 252296465Sdelphijstatic const BIGNUM _bignum_nist_p_256 = { 253296465Sdelphij (BN_ULONG *)_nist_p_256[0], 254296465Sdelphij BN_NIST_256_TOP, 255296465Sdelphij BN_NIST_256_TOP, 256296465Sdelphij 0, 257296465Sdelphij BN_FLG_STATIC_DATA 258296465Sdelphij}; 259194206Ssimon 260296465Sdelphijstatic const BIGNUM _bignum_nist_p_384 = { 261296465Sdelphij (BN_ULONG *)_nist_p_384[0], 262296465Sdelphij BN_NIST_384_TOP, 263296465Sdelphij BN_NIST_384_TOP, 264296465Sdelphij 0, 265296465Sdelphij BN_FLG_STATIC_DATA 266296465Sdelphij}; 267194206Ssimon 268296465Sdelphijstatic const BIGNUM _bignum_nist_p_521 = { 269296465Sdelphij (BN_ULONG *)_nist_p_521, 270296465Sdelphij BN_NIST_521_TOP, 271296465Sdelphij BN_NIST_521_TOP, 272296465Sdelphij 0, 273296465Sdelphij BN_FLG_STATIC_DATA 274296465Sdelphij}; 275194206Ssimon 276160814Ssimonconst BIGNUM *BN_get0_nist_prime_192(void) 277296465Sdelphij{ 278296465Sdelphij return &_bignum_nist_p_192; 279296465Sdelphij} 280160814Ssimon 281160814Ssimonconst BIGNUM *BN_get0_nist_prime_224(void) 282296465Sdelphij{ 283296465Sdelphij return &_bignum_nist_p_224; 284296465Sdelphij} 285160814Ssimon 286160814Ssimonconst BIGNUM *BN_get0_nist_prime_256(void) 287296465Sdelphij{ 288296465Sdelphij return &_bignum_nist_p_256; 289296465Sdelphij} 290160814Ssimon 291160814Ssimonconst BIGNUM *BN_get0_nist_prime_384(void) 292296465Sdelphij{ 293296465Sdelphij return &_bignum_nist_p_384; 294296465Sdelphij} 295160814Ssimon 296160814Ssimonconst BIGNUM *BN_get0_nist_prime_521(void) 297296465Sdelphij{ 298296465Sdelphij return &_bignum_nist_p_521; 299296465Sdelphij} 300160814Ssimon 301160814Ssimonstatic void nist_cp_bn_0(BN_ULONG *buf, BN_ULONG *a, int top, int max) 302296465Sdelphij{ 303296465Sdelphij int i; 304296465Sdelphij BN_ULONG *_tmp1 = (buf), *_tmp2 = (a); 305160814Ssimon 306194206Ssimon#ifdef BN_DEBUG 307296465Sdelphij OPENSSL_assert(top <= max); 308194206Ssimon#endif 309296465Sdelphij for (i = (top); i != 0; i--) 310296465Sdelphij *_tmp1++ = *_tmp2++; 311296465Sdelphij for (i = (max) - (top); i != 0; i--) 312296465Sdelphij *_tmp1++ = (BN_ULONG)0; 313296465Sdelphij} 314194206Ssimon 315160814Ssimonstatic void nist_cp_bn(BN_ULONG *buf, BN_ULONG *a, int top) 316296465Sdelphij{ 317296465Sdelphij int i; 318296465Sdelphij BN_ULONG *_tmp1 = (buf), *_tmp2 = (a); 319296465Sdelphij for (i = (top); i != 0; i--) 320296465Sdelphij *_tmp1++ = *_tmp2++; 321296465Sdelphij} 322160814Ssimon 323160814Ssimon#if BN_BITS2 == 64 324296465Sdelphij# define bn_cp_64(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0; 325296465Sdelphij# define bn_64_set_0(to, n) (to)[n] = (BN_ULONG)0; 326194206Ssimon/* 327194206Ssimon * two following macros are implemented under assumption that they 328194206Ssimon * are called in a sequence with *ascending* n, i.e. as they are... 329194206Ssimon */ 330296465Sdelphij# 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))\ 331296465Sdelphij :(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l))) 332296465Sdelphij# define bn_32_set_0(to, n) (((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0)); 333296465Sdelphij# define bn_cp_32(to,n,from,m) ((m)>=0)?bn_cp_32_naked(to,n,from,m):bn_32_set_0(to,n) 334160814Ssimon#else 335296465Sdelphij# define bn_cp_64(to, n, from, m) \ 336296465Sdelphij { \ 337296465Sdelphij bn_cp_32(to, (n)*2, from, (m)*2); \ 338296465Sdelphij bn_cp_32(to, (n)*2+1, from, (m)*2+1); \ 339296465Sdelphij } 340296465Sdelphij# define bn_64_set_0(to, n) \ 341296465Sdelphij { \ 342296465Sdelphij bn_32_set_0(to, (n)*2); \ 343296465Sdelphij bn_32_set_0(to, (n)*2+1); \ 344296465Sdelphij } 345296465Sdelphij# if BN_BITS2 == 32 346296465Sdelphij# define bn_cp_32(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0; 347296465Sdelphij# define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0; 348296465Sdelphij# endif 349296465Sdelphij#endif /* BN_BITS2 != 64 */ 350160814Ssimon 351160814Ssimon#define nist_set_192(to, from, a1, a2, a3) \ 352296465Sdelphij { \ 353296465Sdelphij bn_cp_64(to, 0, from, (a3) - 3) \ 354296465Sdelphij bn_cp_64(to, 1, from, (a2) - 3) \ 355296465Sdelphij bn_cp_64(to, 2, from, (a1) - 3) \ 356296465Sdelphij } 357160814Ssimon 358160814Ssimonint BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 359296465Sdelphij BN_CTX *ctx) 360296465Sdelphij{ 361296465Sdelphij int top = a->top, i; 362296465Sdelphij int carry; 363296465Sdelphij register BN_ULONG *r_d, *a_d = a->d; 364296465Sdelphij BN_ULONG t_d[BN_NIST_192_TOP], 365296465Sdelphij buf[BN_NIST_192_TOP], c_d[BN_NIST_192_TOP], *res; 366296465Sdelphij size_t mask; 367296465Sdelphij static const BIGNUM _bignum_nist_p_192_sqr = { 368296465Sdelphij (BN_ULONG *)_nist_p_192_sqr, 369296465Sdelphij sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]), 370296465Sdelphij sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]), 371296465Sdelphij 0, BN_FLG_STATIC_DATA 372296465Sdelphij }; 373160814Ssimon 374296465Sdelphij field = &_bignum_nist_p_192; /* just to make sure */ 375194206Ssimon 376296465Sdelphij if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_192_sqr) >= 0) 377296465Sdelphij return BN_nnmod(r, a, field, ctx); 378194206Ssimon 379296465Sdelphij i = BN_ucmp(field, a); 380296465Sdelphij if (i == 0) { 381296465Sdelphij BN_zero(r); 382296465Sdelphij return 1; 383296465Sdelphij } else if (i > 0) 384296465Sdelphij return (r == a) ? 1 : (BN_copy(r, a) != NULL); 385160814Ssimon 386296465Sdelphij if (r != a) { 387296465Sdelphij if (!bn_wexpand(r, BN_NIST_192_TOP)) 388296465Sdelphij return 0; 389296465Sdelphij r_d = r->d; 390296465Sdelphij nist_cp_bn(r_d, a_d, BN_NIST_192_TOP); 391296465Sdelphij } else 392296465Sdelphij r_d = a_d; 393160814Ssimon 394296465Sdelphij nist_cp_bn_0(buf, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP, 395296465Sdelphij BN_NIST_192_TOP); 396160814Ssimon 397296465Sdelphij nist_set_192(t_d, buf, 0, 3, 3); 398296465Sdelphij carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); 399296465Sdelphij nist_set_192(t_d, buf, 4, 4, 0); 400296465Sdelphij carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); 401296465Sdelphij nist_set_192(t_d, buf, 5, 5, 5) 402296465Sdelphij carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); 403160814Ssimon 404296465Sdelphij if (carry > 0) 405296465Sdelphij carry = 406296465Sdelphij (int)bn_sub_words(r_d, r_d, _nist_p_192[carry - 1], 407296465Sdelphij BN_NIST_192_TOP); 408296465Sdelphij else 409296465Sdelphij carry = 1; 410160814Ssimon 411296465Sdelphij /* 412296465Sdelphij * we need 'if (carry==0 || result>=modulus) result-=modulus;' 413296465Sdelphij * as comparison implies subtraction, we can write 414296465Sdelphij * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;' 415296465Sdelphij * this is what happens below, but without explicit if:-) a. 416296465Sdelphij */ 417296465Sdelphij mask = 418296465Sdelphij 0 - (size_t)bn_sub_words(c_d, r_d, _nist_p_192[0], BN_NIST_192_TOP); 419296465Sdelphij mask &= 0 - (size_t)carry; 420296465Sdelphij res = (BN_ULONG *)(((size_t)c_d & ~mask) | ((size_t)r_d & mask)); 421296465Sdelphij nist_cp_bn(r_d, res, BN_NIST_192_TOP); 422296465Sdelphij r->top = BN_NIST_192_TOP; 423296465Sdelphij bn_correct_top(r); 424160814Ssimon 425296465Sdelphij return 1; 426296465Sdelphij} 427160814Ssimon 428296465Sdelphijtypedef BN_ULONG (*bn_addsub_f) (BN_ULONG *, const BN_ULONG *, 429296465Sdelphij const BN_ULONG *, int); 430194206Ssimon 431160814Ssimon#define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \ 432296465Sdelphij { \ 433296465Sdelphij bn_cp_32(to, 0, from, (a7) - 7) \ 434296465Sdelphij bn_cp_32(to, 1, from, (a6) - 7) \ 435296465Sdelphij bn_cp_32(to, 2, from, (a5) - 7) \ 436296465Sdelphij bn_cp_32(to, 3, from, (a4) - 7) \ 437296465Sdelphij bn_cp_32(to, 4, from, (a3) - 7) \ 438296465Sdelphij bn_cp_32(to, 5, from, (a2) - 7) \ 439296465Sdelphij bn_cp_32(to, 6, from, (a1) - 7) \ 440296465Sdelphij } 441160814Ssimon 442160814Ssimonint BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 443296465Sdelphij BN_CTX *ctx) 444296465Sdelphij{ 445296465Sdelphij int top = a->top, i; 446296465Sdelphij int carry; 447296465Sdelphij BN_ULONG *r_d, *a_d = a->d; 448296465Sdelphij BN_ULONG t_d[BN_NIST_224_TOP], 449296465Sdelphij buf[BN_NIST_224_TOP], c_d[BN_NIST_224_TOP], *res; 450296465Sdelphij size_t mask; 451296465Sdelphij union { 452296465Sdelphij bn_addsub_f f; 453296465Sdelphij size_t p; 454296465Sdelphij } u; 455296465Sdelphij static const BIGNUM _bignum_nist_p_224_sqr = { 456296465Sdelphij (BN_ULONG *)_nist_p_224_sqr, 457296465Sdelphij sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]), 458296465Sdelphij sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]), 459296465Sdelphij 0, BN_FLG_STATIC_DATA 460296465Sdelphij }; 461160814Ssimon 462296465Sdelphij field = &_bignum_nist_p_224; /* just to make sure */ 463194206Ssimon 464296465Sdelphij if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_224_sqr) >= 0) 465296465Sdelphij return BN_nnmod(r, a, field, ctx); 466194206Ssimon 467296465Sdelphij i = BN_ucmp(field, a); 468296465Sdelphij if (i == 0) { 469296465Sdelphij BN_zero(r); 470296465Sdelphij return 1; 471296465Sdelphij } else if (i > 0) 472296465Sdelphij return (r == a) ? 1 : (BN_copy(r, a) != NULL); 473194206Ssimon 474296465Sdelphij if (r != a) { 475296465Sdelphij if (!bn_wexpand(r, BN_NIST_224_TOP)) 476296465Sdelphij return 0; 477296465Sdelphij r_d = r->d; 478296465Sdelphij nist_cp_bn(r_d, a_d, BN_NIST_224_TOP); 479296465Sdelphij } else 480296465Sdelphij r_d = a_d; 481160814Ssimon 482194206Ssimon#if BN_BITS2==64 483296465Sdelphij /* copy upper 256 bits of 448 bit number ... */ 484296465Sdelphij nist_cp_bn_0(t_d, a_d + (BN_NIST_224_TOP - 1), 485296465Sdelphij top - (BN_NIST_224_TOP - 1), BN_NIST_224_TOP); 486296465Sdelphij /* ... and right shift by 32 to obtain upper 224 bits */ 487296465Sdelphij nist_set_224(buf, t_d, 14, 13, 12, 11, 10, 9, 8); 488296465Sdelphij /* truncate lower part to 224 bits too */ 489296465Sdelphij r_d[BN_NIST_224_TOP - 1] &= BN_MASK2l; 490194206Ssimon#else 491296465Sdelphij nist_cp_bn_0(buf, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP, 492296465Sdelphij BN_NIST_224_TOP); 493194206Ssimon#endif 494296465Sdelphij nist_set_224(t_d, buf, 10, 9, 8, 7, 0, 0, 0); 495296465Sdelphij carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP); 496296465Sdelphij nist_set_224(t_d, buf, 0, 13, 12, 11, 0, 0, 0); 497296465Sdelphij carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP); 498296465Sdelphij nist_set_224(t_d, buf, 13, 12, 11, 10, 9, 8, 7); 499296465Sdelphij carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP); 500296465Sdelphij nist_set_224(t_d, buf, 0, 0, 0, 0, 13, 12, 11); 501296465Sdelphij carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP); 502160814Ssimon 503194206Ssimon#if BN_BITS2==64 504296465Sdelphij carry = (int)(r_d[BN_NIST_224_TOP - 1] >> 32); 505194206Ssimon#endif 506296465Sdelphij u.f = bn_sub_words; 507296465Sdelphij if (carry > 0) { 508296465Sdelphij carry = 509296465Sdelphij (int)bn_sub_words(r_d, r_d, _nist_p_224[carry - 1], 510296465Sdelphij BN_NIST_224_TOP); 511194206Ssimon#if BN_BITS2==64 512296465Sdelphij carry = (int)(~(r_d[BN_NIST_224_TOP - 1] >> 32)) & 1; 513194206Ssimon#endif 514296465Sdelphij } else if (carry < 0) { 515296465Sdelphij /* 516296465Sdelphij * it's a bit more comlicated logic in this case. if bn_add_words 517296465Sdelphij * yields no carry, then result has to be adjusted by unconditionally 518296465Sdelphij * *adding* the modulus. but if it does, then result has to be 519296465Sdelphij * compared to the modulus and conditionally adjusted by 520296465Sdelphij * *subtracting* the latter. 521296465Sdelphij */ 522296465Sdelphij carry = 523296465Sdelphij (int)bn_add_words(r_d, r_d, _nist_p_224[-carry - 1], 524296465Sdelphij BN_NIST_224_TOP); 525296465Sdelphij mask = 0 - (size_t)carry; 526296465Sdelphij u.p = ((size_t)bn_sub_words & mask) | ((size_t)bn_add_words & ~mask); 527296465Sdelphij } else 528296465Sdelphij carry = 1; 529160814Ssimon 530296465Sdelphij /* otherwise it's effectively same as in BN_nist_mod_192... */ 531296465Sdelphij mask = 0 - (size_t)(*u.f) (c_d, r_d, _nist_p_224[0], BN_NIST_224_TOP); 532296465Sdelphij mask &= 0 - (size_t)carry; 533296465Sdelphij res = (BN_ULONG *)(((size_t)c_d & ~mask) | ((size_t)r_d & mask)); 534296465Sdelphij nist_cp_bn(r_d, res, BN_NIST_224_TOP); 535296465Sdelphij r->top = BN_NIST_224_TOP; 536296465Sdelphij bn_correct_top(r); 537194206Ssimon 538296465Sdelphij return 1; 539296465Sdelphij} 540160814Ssimon 541160814Ssimon#define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \ 542296465Sdelphij { \ 543296465Sdelphij bn_cp_32(to, 0, from, (a8) - 8) \ 544296465Sdelphij bn_cp_32(to, 1, from, (a7) - 8) \ 545296465Sdelphij bn_cp_32(to, 2, from, (a6) - 8) \ 546296465Sdelphij bn_cp_32(to, 3, from, (a5) - 8) \ 547296465Sdelphij bn_cp_32(to, 4, from, (a4) - 8) \ 548296465Sdelphij bn_cp_32(to, 5, from, (a3) - 8) \ 549296465Sdelphij bn_cp_32(to, 6, from, (a2) - 8) \ 550296465Sdelphij bn_cp_32(to, 7, from, (a1) - 8) \ 551296465Sdelphij } 552160814Ssimon 553160814Ssimonint BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 554296465Sdelphij BN_CTX *ctx) 555296465Sdelphij{ 556296465Sdelphij int i, top = a->top; 557296465Sdelphij int carry = 0; 558296465Sdelphij register BN_ULONG *a_d = a->d, *r_d; 559296465Sdelphij BN_ULONG t_d[BN_NIST_256_TOP], 560296465Sdelphij buf[BN_NIST_256_TOP], c_d[BN_NIST_256_TOP], *res; 561296465Sdelphij size_t mask; 562296465Sdelphij union { 563296465Sdelphij bn_addsub_f f; 564296465Sdelphij size_t p; 565296465Sdelphij } u; 566296465Sdelphij static const BIGNUM _bignum_nist_p_256_sqr = { 567296465Sdelphij (BN_ULONG *)_nist_p_256_sqr, 568296465Sdelphij sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]), 569296465Sdelphij sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]), 570296465Sdelphij 0, BN_FLG_STATIC_DATA 571296465Sdelphij }; 572160814Ssimon 573296465Sdelphij field = &_bignum_nist_p_256; /* just to make sure */ 574194206Ssimon 575296465Sdelphij if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_256_sqr) >= 0) 576296465Sdelphij return BN_nnmod(r, a, field, ctx); 577194206Ssimon 578296465Sdelphij i = BN_ucmp(field, a); 579296465Sdelphij if (i == 0) { 580296465Sdelphij BN_zero(r); 581296465Sdelphij return 1; 582296465Sdelphij } else if (i > 0) 583296465Sdelphij return (r == a) ? 1 : (BN_copy(r, a) != NULL); 584160814Ssimon 585296465Sdelphij if (r != a) { 586296465Sdelphij if (!bn_wexpand(r, BN_NIST_256_TOP)) 587296465Sdelphij return 0; 588296465Sdelphij r_d = r->d; 589296465Sdelphij nist_cp_bn(r_d, a_d, BN_NIST_256_TOP); 590296465Sdelphij } else 591296465Sdelphij r_d = a_d; 592160814Ssimon 593296465Sdelphij nist_cp_bn_0(buf, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP, 594296465Sdelphij BN_NIST_256_TOP); 595160814Ssimon 596296465Sdelphij /* 597296465Sdelphij * S1 598296465Sdelphij */ 599296465Sdelphij nist_set_256(t_d, buf, 15, 14, 13, 12, 11, 0, 0, 0); 600296465Sdelphij /* 601296465Sdelphij * S2 602296465Sdelphij */ 603296465Sdelphij nist_set_256(c_d, buf, 0, 15, 14, 13, 12, 0, 0, 0); 604296465Sdelphij carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP); 605296465Sdelphij /* left shift */ 606296465Sdelphij { 607296465Sdelphij register BN_ULONG *ap, t, c; 608296465Sdelphij ap = t_d; 609296465Sdelphij c = 0; 610296465Sdelphij for (i = BN_NIST_256_TOP; i != 0; --i) { 611296465Sdelphij t = *ap; 612296465Sdelphij *(ap++) = ((t << 1) | c) & BN_MASK2; 613296465Sdelphij c = (t & BN_TBIT) ? 1 : 0; 614296465Sdelphij } 615296465Sdelphij carry <<= 1; 616296465Sdelphij carry |= c; 617296465Sdelphij } 618296465Sdelphij carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 619296465Sdelphij /* 620296465Sdelphij * S3 621296465Sdelphij */ 622296465Sdelphij nist_set_256(t_d, buf, 15, 14, 0, 0, 0, 10, 9, 8); 623296465Sdelphij carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 624296465Sdelphij /* 625296465Sdelphij * S4 626296465Sdelphij */ 627296465Sdelphij nist_set_256(t_d, buf, 8, 13, 15, 14, 13, 11, 10, 9); 628296465Sdelphij carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 629296465Sdelphij /* 630296465Sdelphij * D1 631296465Sdelphij */ 632296465Sdelphij nist_set_256(t_d, buf, 10, 8, 0, 0, 0, 13, 12, 11); 633296465Sdelphij carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 634296465Sdelphij /* 635296465Sdelphij * D2 636296465Sdelphij */ 637296465Sdelphij nist_set_256(t_d, buf, 11, 9, 0, 0, 15, 14, 13, 12); 638296465Sdelphij carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 639296465Sdelphij /* 640296465Sdelphij * D3 641296465Sdelphij */ 642296465Sdelphij nist_set_256(t_d, buf, 12, 0, 10, 9, 8, 15, 14, 13); 643296465Sdelphij carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 644296465Sdelphij /* 645296465Sdelphij * D4 646296465Sdelphij */ 647296465Sdelphij nist_set_256(t_d, buf, 13, 0, 11, 10, 9, 0, 15, 14); 648296465Sdelphij carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 649194206Ssimon 650296465Sdelphij /* see BN_nist_mod_224 for explanation */ 651296465Sdelphij u.f = bn_sub_words; 652296465Sdelphij if (carry > 0) 653296465Sdelphij carry = 654296465Sdelphij (int)bn_sub_words(r_d, r_d, _nist_p_256[carry - 1], 655296465Sdelphij BN_NIST_256_TOP); 656296465Sdelphij else if (carry < 0) { 657296465Sdelphij carry = 658296465Sdelphij (int)bn_add_words(r_d, r_d, _nist_p_256[-carry - 1], 659296465Sdelphij BN_NIST_256_TOP); 660296465Sdelphij mask = 0 - (size_t)carry; 661296465Sdelphij u.p = ((size_t)bn_sub_words & mask) | ((size_t)bn_add_words & ~mask); 662296465Sdelphij } else 663296465Sdelphij carry = 1; 664160814Ssimon 665296465Sdelphij mask = 0 - (size_t)(*u.f) (c_d, r_d, _nist_p_256[0], BN_NIST_256_TOP); 666296465Sdelphij mask &= 0 - (size_t)carry; 667296465Sdelphij res = (BN_ULONG *)(((size_t)c_d & ~mask) | ((size_t)r_d & mask)); 668296465Sdelphij nist_cp_bn(r_d, res, BN_NIST_256_TOP); 669296465Sdelphij r->top = BN_NIST_256_TOP; 670296465Sdelphij bn_correct_top(r); 671194206Ssimon 672296465Sdelphij return 1; 673296465Sdelphij} 674160814Ssimon 675160814Ssimon#define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \ 676296465Sdelphij { \ 677296465Sdelphij bn_cp_32(to, 0, from, (a12) - 12) \ 678296465Sdelphij bn_cp_32(to, 1, from, (a11) - 12) \ 679296465Sdelphij bn_cp_32(to, 2, from, (a10) - 12) \ 680296465Sdelphij bn_cp_32(to, 3, from, (a9) - 12) \ 681296465Sdelphij bn_cp_32(to, 4, from, (a8) - 12) \ 682296465Sdelphij bn_cp_32(to, 5, from, (a7) - 12) \ 683296465Sdelphij bn_cp_32(to, 6, from, (a6) - 12) \ 684296465Sdelphij bn_cp_32(to, 7, from, (a5) - 12) \ 685296465Sdelphij bn_cp_32(to, 8, from, (a4) - 12) \ 686296465Sdelphij bn_cp_32(to, 9, from, (a3) - 12) \ 687296465Sdelphij bn_cp_32(to, 10, from, (a2) - 12) \ 688296465Sdelphij bn_cp_32(to, 11, from, (a1) - 12) \ 689296465Sdelphij } 690160814Ssimon 691160814Ssimonint BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 692296465Sdelphij BN_CTX *ctx) 693296465Sdelphij{ 694296465Sdelphij int i, top = a->top; 695296465Sdelphij int carry = 0; 696296465Sdelphij register BN_ULONG *r_d, *a_d = a->d; 697296465Sdelphij BN_ULONG t_d[BN_NIST_384_TOP], 698296465Sdelphij buf[BN_NIST_384_TOP], c_d[BN_NIST_384_TOP], *res; 699296465Sdelphij size_t mask; 700296465Sdelphij union { 701296465Sdelphij bn_addsub_f f; 702296465Sdelphij size_t p; 703296465Sdelphij } u; 704296465Sdelphij static const BIGNUM _bignum_nist_p_384_sqr = { 705296465Sdelphij (BN_ULONG *)_nist_p_384_sqr, 706296465Sdelphij sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]), 707296465Sdelphij sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]), 708296465Sdelphij 0, BN_FLG_STATIC_DATA 709296465Sdelphij }; 710160814Ssimon 711296465Sdelphij field = &_bignum_nist_p_384; /* just to make sure */ 712160814Ssimon 713296465Sdelphij if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_384_sqr) >= 0) 714296465Sdelphij return BN_nnmod(r, a, field, ctx); 715160814Ssimon 716296465Sdelphij i = BN_ucmp(field, a); 717296465Sdelphij if (i == 0) { 718296465Sdelphij BN_zero(r); 719296465Sdelphij return 1; 720296465Sdelphij } else if (i > 0) 721296465Sdelphij return (r == a) ? 1 : (BN_copy(r, a) != NULL); 722194206Ssimon 723296465Sdelphij if (r != a) { 724296465Sdelphij if (!bn_wexpand(r, BN_NIST_384_TOP)) 725296465Sdelphij return 0; 726296465Sdelphij r_d = r->d; 727296465Sdelphij nist_cp_bn(r_d, a_d, BN_NIST_384_TOP); 728296465Sdelphij } else 729296465Sdelphij r_d = a_d; 730160814Ssimon 731296465Sdelphij nist_cp_bn_0(buf, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP, 732296465Sdelphij BN_NIST_384_TOP); 733160814Ssimon 734296465Sdelphij /* 735296465Sdelphij * S1 736296465Sdelphij */ 737296465Sdelphij nist_set_256(t_d, buf, 0, 0, 0, 0, 0, 23 - 4, 22 - 4, 21 - 4); 738296465Sdelphij /* left shift */ 739296465Sdelphij { 740296465Sdelphij register BN_ULONG *ap, t, c; 741296465Sdelphij ap = t_d; 742296465Sdelphij c = 0; 743296465Sdelphij for (i = 3; i != 0; --i) { 744296465Sdelphij t = *ap; 745296465Sdelphij *(ap++) = ((t << 1) | c) & BN_MASK2; 746296465Sdelphij c = (t & BN_TBIT) ? 1 : 0; 747296465Sdelphij } 748296465Sdelphij *ap = c; 749296465Sdelphij } 750296465Sdelphij carry = (int)bn_add_words(r_d + (128 / BN_BITS2), r_d + (128 / BN_BITS2), 751296465Sdelphij t_d, BN_NIST_256_TOP); 752296465Sdelphij /* 753296465Sdelphij * S2 754296465Sdelphij */ 755296465Sdelphij carry += (int)bn_add_words(r_d, r_d, buf, BN_NIST_384_TOP); 756296465Sdelphij /* 757296465Sdelphij * S3 758296465Sdelphij */ 759296465Sdelphij nist_set_384(t_d, buf, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 22, 21); 760296465Sdelphij carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 761296465Sdelphij /* 762296465Sdelphij * S4 763296465Sdelphij */ 764296465Sdelphij nist_set_384(t_d, buf, 19, 18, 17, 16, 15, 14, 13, 12, 20, 0, 23, 0); 765296465Sdelphij carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 766296465Sdelphij /* 767296465Sdelphij * S5 768296465Sdelphij */ 769296465Sdelphij nist_set_384(t_d, buf, 0, 0, 0, 0, 23, 22, 21, 20, 0, 0, 0, 0); 770296465Sdelphij carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 771296465Sdelphij /* 772296465Sdelphij * S6 773296465Sdelphij */ 774296465Sdelphij nist_set_384(t_d, buf, 0, 0, 0, 0, 0, 0, 23, 22, 21, 0, 0, 20); 775296465Sdelphij carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 776296465Sdelphij /* 777296465Sdelphij * D1 778296465Sdelphij */ 779296465Sdelphij nist_set_384(t_d, buf, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23); 780296465Sdelphij carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 781296465Sdelphij /* 782296465Sdelphij * D2 783296465Sdelphij */ 784296465Sdelphij nist_set_384(t_d, buf, 0, 0, 0, 0, 0, 0, 0, 23, 22, 21, 20, 0); 785296465Sdelphij carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 786296465Sdelphij /* 787296465Sdelphij * D3 788296465Sdelphij */ 789296465Sdelphij nist_set_384(t_d, buf, 0, 0, 0, 0, 0, 0, 0, 23, 23, 0, 0, 0); 790296465Sdelphij carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 791160814Ssimon 792296465Sdelphij /* see BN_nist_mod_224 for explanation */ 793296465Sdelphij u.f = bn_sub_words; 794296465Sdelphij if (carry > 0) 795296465Sdelphij carry = 796296465Sdelphij (int)bn_sub_words(r_d, r_d, _nist_p_384[carry - 1], 797296465Sdelphij BN_NIST_384_TOP); 798296465Sdelphij else if (carry < 0) { 799296465Sdelphij carry = 800296465Sdelphij (int)bn_add_words(r_d, r_d, _nist_p_384[-carry - 1], 801296465Sdelphij BN_NIST_384_TOP); 802296465Sdelphij mask = 0 - (size_t)carry; 803296465Sdelphij u.p = ((size_t)bn_sub_words & mask) | ((size_t)bn_add_words & ~mask); 804296465Sdelphij } else 805296465Sdelphij carry = 1; 806194206Ssimon 807296465Sdelphij mask = 0 - (size_t)(*u.f) (c_d, r_d, _nist_p_384[0], BN_NIST_384_TOP); 808296465Sdelphij mask &= 0 - (size_t)carry; 809296465Sdelphij res = (BN_ULONG *)(((size_t)c_d & ~mask) | ((size_t)r_d & mask)); 810296465Sdelphij nist_cp_bn(r_d, res, BN_NIST_384_TOP); 811296465Sdelphij r->top = BN_NIST_384_TOP; 812296465Sdelphij bn_correct_top(r); 813160814Ssimon 814296465Sdelphij return 1; 815296465Sdelphij} 816194206Ssimon 817296465Sdelphij#define BN_NIST_521_RSHIFT (521%BN_BITS2) 818296465Sdelphij#define BN_NIST_521_LSHIFT (BN_BITS2-BN_NIST_521_RSHIFT) 819296465Sdelphij#define BN_NIST_521_TOP_MASK ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT) 820160814Ssimon 821160814Ssimonint BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 822296465Sdelphij BN_CTX *ctx) 823296465Sdelphij{ 824296465Sdelphij int top = a->top, i; 825296465Sdelphij BN_ULONG *r_d, *a_d = a->d, t_d[BN_NIST_521_TOP], val, tmp, *res; 826296465Sdelphij size_t mask; 827296465Sdelphij static const BIGNUM _bignum_nist_p_521_sqr = { 828296465Sdelphij (BN_ULONG *)_nist_p_521_sqr, 829296465Sdelphij sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]), 830296465Sdelphij sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]), 831296465Sdelphij 0, BN_FLG_STATIC_DATA 832296465Sdelphij }; 833160814Ssimon 834296465Sdelphij field = &_bignum_nist_p_521; /* just to make sure */ 835160814Ssimon 836296465Sdelphij if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_521_sqr) >= 0) 837296465Sdelphij return BN_nnmod(r, a, field, ctx); 838160814Ssimon 839296465Sdelphij i = BN_ucmp(field, a); 840296465Sdelphij if (i == 0) { 841296465Sdelphij BN_zero(r); 842296465Sdelphij return 1; 843296465Sdelphij } else if (i > 0) 844296465Sdelphij return (r == a) ? 1 : (BN_copy(r, a) != NULL); 845160814Ssimon 846296465Sdelphij if (r != a) { 847296465Sdelphij if (!bn_wexpand(r, BN_NIST_521_TOP)) 848296465Sdelphij return 0; 849296465Sdelphij r_d = r->d; 850296465Sdelphij nist_cp_bn(r_d, a_d, BN_NIST_521_TOP); 851296465Sdelphij } else 852296465Sdelphij r_d = a_d; 853160814Ssimon 854296465Sdelphij /* upper 521 bits, copy ... */ 855296465Sdelphij nist_cp_bn_0(t_d, a_d + (BN_NIST_521_TOP - 1), 856296465Sdelphij top - (BN_NIST_521_TOP - 1), BN_NIST_521_TOP); 857296465Sdelphij /* ... and right shift */ 858296465Sdelphij for (val = t_d[0], i = 0; i < BN_NIST_521_TOP - 1; i++) { 859296465Sdelphij tmp = val >> BN_NIST_521_RSHIFT; 860296465Sdelphij val = t_d[i + 1]; 861296465Sdelphij t_d[i] = (tmp | val << BN_NIST_521_LSHIFT) & BN_MASK2; 862296465Sdelphij } 863296465Sdelphij t_d[i] = val >> BN_NIST_521_RSHIFT; 864296465Sdelphij /* lower 521 bits */ 865296465Sdelphij r_d[i] &= BN_NIST_521_TOP_MASK; 866194206Ssimon 867296465Sdelphij bn_add_words(r_d, r_d, t_d, BN_NIST_521_TOP); 868296465Sdelphij mask = 0 - (size_t)bn_sub_words(t_d, r_d, _nist_p_521, BN_NIST_521_TOP); 869296465Sdelphij res = (BN_ULONG *)(((size_t)t_d & ~mask) | ((size_t)r_d & mask)); 870296465Sdelphij nist_cp_bn(r_d, res, BN_NIST_521_TOP); 871296465Sdelphij r->top = BN_NIST_521_TOP; 872296465Sdelphij bn_correct_top(r); 873160814Ssimon 874296465Sdelphij return 1; 875296465Sdelphij} 876