Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 1 | /* crypto/bn/bn_nist.c */ |
| 2 | /* |
| 3 | * Written by Nils Larsch for the OpenSSL project |
| 4 | */ |
| 5 | /* ==================================================================== |
| 6 | * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. |
| 7 | * |
| 8 | * Redistribution and use in source and binary forms, with or without |
| 9 | * modification, are permitted provided that the following conditions |
| 10 | * are met: |
| 11 | * |
| 12 | * 1. Redistributions of source code must retain the above copyright |
| 13 | * notice, this list of conditions and the following disclaimer. |
| 14 | * |
| 15 | * 2. Redistributions in binary form must reproduce the above copyright |
| 16 | * notice, this list of conditions and the following disclaimer in |
| 17 | * the documentation and/or other materials provided with the |
| 18 | * distribution. |
| 19 | * |
| 20 | * 3. All advertising materials mentioning features or use of this |
| 21 | * software must display the following acknowledgment: |
| 22 | * "This product includes software developed by the OpenSSL Project |
| 23 | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" |
| 24 | * |
| 25 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to |
| 26 | * endorse or promote products derived from this software without |
| 27 | * prior written permission. For written permission, please contact |
| 28 | * openssl-core@openssl.org. |
| 29 | * |
| 30 | * 5. Products derived from this software may not be called "OpenSSL" |
| 31 | * nor may "OpenSSL" appear in their names without prior written |
| 32 | * permission of the OpenSSL Project. |
| 33 | * |
| 34 | * 6. Redistributions of any form whatsoever must retain the following |
| 35 | * acknowledgment: |
| 36 | * "This product includes software developed by the OpenSSL Project |
| 37 | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" |
| 38 | * |
| 39 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY |
| 40 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| 41 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| 42 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR |
| 43 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 44 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| 45 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
| 46 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 47 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
| 48 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| 49 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
| 50 | * OF THE POSSIBILITY OF SUCH DAMAGE. |
| 51 | * ==================================================================== |
| 52 | * |
| 53 | * This product includes cryptographic software written by Eric Young |
| 54 | * (eay@cryptsoft.com). This product includes software written by Tim |
| 55 | * Hudson (tjh@cryptsoft.com). |
| 56 | * |
| 57 | */ |
| 58 | |
| 59 | #include "bn_lcl.h" |
| 60 | #include "cryptlib.h" |
| 61 | |
| 62 | |
| 63 | #define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2 |
| 64 | #define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2 |
| 65 | #define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2 |
| 66 | #define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2 |
| 67 | #define BN_NIST_521_TOP (521+BN_BITS2-1)/BN_BITS2 |
| 68 | |
| 69 | /* pre-computed tables are "carry-less" values of modulus*(i+1) */ |
| 70 | #if BN_BITS2 == 64 |
| 71 | static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = { |
| 72 | {0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFEULL,0xFFFFFFFFFFFFFFFFULL}, |
| 73 | {0xFFFFFFFFFFFFFFFEULL,0xFFFFFFFFFFFFFFFDULL,0xFFFFFFFFFFFFFFFFULL}, |
| 74 | {0xFFFFFFFFFFFFFFFDULL,0xFFFFFFFFFFFFFFFCULL,0xFFFFFFFFFFFFFFFFULL} |
| 75 | }; |
| 76 | static const BN_ULONG _nist_p_192_sqr[] = { |
| 77 | 0x0000000000000001ULL,0x0000000000000002ULL,0x0000000000000001ULL, |
| 78 | 0xFFFFFFFFFFFFFFFEULL,0xFFFFFFFFFFFFFFFDULL,0xFFFFFFFFFFFFFFFFULL |
| 79 | }; |
| 80 | static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = { |
| 81 | {0x0000000000000001ULL,0xFFFFFFFF00000000ULL, |
| 82 | 0xFFFFFFFFFFFFFFFFULL,0x00000000FFFFFFFFULL}, |
| 83 | {0x0000000000000002ULL,0xFFFFFFFE00000000ULL, |
| 84 | 0xFFFFFFFFFFFFFFFFULL,0x00000001FFFFFFFFULL} /* this one is "carry-full" */ |
| 85 | }; |
| 86 | static const BN_ULONG _nist_p_224_sqr[] = { |
| 87 | 0x0000000000000001ULL,0xFFFFFFFE00000000ULL, |
| 88 | 0xFFFFFFFFFFFFFFFFULL,0x0000000200000000ULL, |
| 89 | 0x0000000000000000ULL,0xFFFFFFFFFFFFFFFEULL, |
| 90 | 0xFFFFFFFFFFFFFFFFULL |
| 91 | }; |
| 92 | static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = { |
| 93 | {0xFFFFFFFFFFFFFFFFULL,0x00000000FFFFFFFFULL, |
| 94 | 0x0000000000000000ULL,0xFFFFFFFF00000001ULL}, |
| 95 | {0xFFFFFFFFFFFFFFFEULL,0x00000001FFFFFFFFULL, |
| 96 | 0x0000000000000000ULL,0xFFFFFFFE00000002ULL}, |
| 97 | {0xFFFFFFFFFFFFFFFDULL,0x00000002FFFFFFFFULL, |
| 98 | 0x0000000000000000ULL,0xFFFFFFFD00000003ULL}, |
| 99 | {0xFFFFFFFFFFFFFFFCULL,0x00000003FFFFFFFFULL, |
| 100 | 0x0000000000000000ULL,0xFFFFFFFC00000004ULL}, |
| 101 | {0xFFFFFFFFFFFFFFFBULL,0x00000004FFFFFFFFULL, |
| 102 | 0x0000000000000000ULL,0xFFFFFFFB00000005ULL}, |
| 103 | }; |
| 104 | static const BN_ULONG _nist_p_256_sqr[] = { |
| 105 | 0x0000000000000001ULL,0xFFFFFFFE00000000ULL, |
| 106 | 0xFFFFFFFFFFFFFFFFULL,0x00000001FFFFFFFEULL, |
| 107 | 0x00000001FFFFFFFEULL,0x00000001FFFFFFFEULL, |
| 108 | 0xFFFFFFFE00000001ULL,0xFFFFFFFE00000002ULL |
| 109 | }; |
| 110 | static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = { |
| 111 | {0x00000000FFFFFFFFULL,0xFFFFFFFF00000000ULL,0xFFFFFFFFFFFFFFFEULL, |
| 112 | 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL}, |
| 113 | {0x00000001FFFFFFFEULL,0xFFFFFFFE00000000ULL,0xFFFFFFFFFFFFFFFDULL, |
| 114 | 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL}, |
| 115 | {0x00000002FFFFFFFDULL,0xFFFFFFFD00000000ULL,0xFFFFFFFFFFFFFFFCULL, |
| 116 | 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL}, |
| 117 | {0x00000003FFFFFFFCULL,0xFFFFFFFC00000000ULL,0xFFFFFFFFFFFFFFFBULL, |
| 118 | 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL}, |
| 119 | {0x00000004FFFFFFFBULL,0xFFFFFFFB00000000ULL,0xFFFFFFFFFFFFFFFAULL, |
| 120 | 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL}, |
| 121 | }; |
| 122 | static const BN_ULONG _nist_p_384_sqr[] = { |
| 123 | 0xFFFFFFFE00000001ULL,0x0000000200000000ULL,0xFFFFFFFE00000000ULL, |
| 124 | 0x0000000200000000ULL,0x0000000000000001ULL,0x0000000000000000ULL, |
| 125 | 0x00000001FFFFFFFEULL,0xFFFFFFFE00000000ULL,0xFFFFFFFFFFFFFFFDULL, |
| 126 | 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL |
| 127 | }; |
| 128 | static const BN_ULONG _nist_p_521[] = |
| 129 | {0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, |
| 130 | 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, |
| 131 | 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, |
| 132 | 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, |
| 133 | 0x00000000000001FFULL}; |
| 134 | static const BN_ULONG _nist_p_521_sqr[] = { |
| 135 | 0x0000000000000001ULL,0x0000000000000000ULL,0x0000000000000000ULL, |
| 136 | 0x0000000000000000ULL,0x0000000000000000ULL,0x0000000000000000ULL, |
| 137 | 0x0000000000000000ULL,0x0000000000000000ULL,0xFFFFFFFFFFFFFC00ULL, |
| 138 | 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, |
| 139 | 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, |
| 140 | 0xFFFFFFFFFFFFFFFFULL,0x000000000003FFFFULL |
| 141 | }; |
| 142 | #elif BN_BITS2 == 32 |
| 143 | static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = { |
| 144 | {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFE,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, |
| 145 | {0xFFFFFFFE,0xFFFFFFFF,0xFFFFFFFD,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, |
| 146 | {0xFFFFFFFD,0xFFFFFFFF,0xFFFFFFFC,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF} |
| 147 | }; |
| 148 | static const BN_ULONG _nist_p_192_sqr[] = { |
| 149 | 0x00000001,0x00000000,0x00000002,0x00000000,0x00000001,0x00000000, |
| 150 | 0xFFFFFFFE,0xFFFFFFFF,0xFFFFFFFD,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF |
| 151 | }; |
| 152 | static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = { |
| 153 | {0x00000001,0x00000000,0x00000000,0xFFFFFFFF, |
| 154 | 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, |
| 155 | {0x00000002,0x00000000,0x00000000,0xFFFFFFFE, |
| 156 | 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF} |
| 157 | }; |
| 158 | static const BN_ULONG _nist_p_224_sqr[] = { |
| 159 | 0x00000001,0x00000000,0x00000000,0xFFFFFFFE, |
| 160 | 0xFFFFFFFF,0xFFFFFFFF,0x00000000,0x00000002, |
| 161 | 0x00000000,0x00000000,0xFFFFFFFE,0xFFFFFFFF, |
| 162 | 0xFFFFFFFF,0xFFFFFFFF |
| 163 | }; |
| 164 | static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = { |
| 165 | {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0x00000000, |
| 166 | 0x00000000,0x00000000,0x00000001,0xFFFFFFFF}, |
| 167 | {0xFFFFFFFE,0xFFFFFFFF,0xFFFFFFFF,0x00000001, |
| 168 | 0x00000000,0x00000000,0x00000002,0xFFFFFFFE}, |
| 169 | {0xFFFFFFFD,0xFFFFFFFF,0xFFFFFFFF,0x00000002, |
| 170 | 0x00000000,0x00000000,0x00000003,0xFFFFFFFD}, |
| 171 | {0xFFFFFFFC,0xFFFFFFFF,0xFFFFFFFF,0x00000003, |
| 172 | 0x00000000,0x00000000,0x00000004,0xFFFFFFFC}, |
| 173 | {0xFFFFFFFB,0xFFFFFFFF,0xFFFFFFFF,0x00000004, |
| 174 | 0x00000000,0x00000000,0x00000005,0xFFFFFFFB}, |
| 175 | }; |
| 176 | static const BN_ULONG _nist_p_256_sqr[] = { |
| 177 | 0x00000001,0x00000000,0x00000000,0xFFFFFFFE, |
| 178 | 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFE,0x00000001, |
| 179 | 0xFFFFFFFE,0x00000001,0xFFFFFFFE,0x00000001, |
| 180 | 0x00000001,0xFFFFFFFE,0x00000002,0xFFFFFFFE |
| 181 | }; |
| 182 | static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = { |
| 183 | {0xFFFFFFFF,0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFE,0xFFFFFFFF, |
| 184 | 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, |
| 185 | {0xFFFFFFFE,0x00000001,0x00000000,0xFFFFFFFE,0xFFFFFFFD,0xFFFFFFFF, |
| 186 | 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, |
| 187 | {0xFFFFFFFD,0x00000002,0x00000000,0xFFFFFFFD,0xFFFFFFFC,0xFFFFFFFF, |
| 188 | 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, |
| 189 | {0xFFFFFFFC,0x00000003,0x00000000,0xFFFFFFFC,0xFFFFFFFB,0xFFFFFFFF, |
| 190 | 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, |
| 191 | {0xFFFFFFFB,0x00000004,0x00000000,0xFFFFFFFB,0xFFFFFFFA,0xFFFFFFFF, |
| 192 | 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, |
| 193 | }; |
| 194 | static const BN_ULONG _nist_p_384_sqr[] = { |
| 195 | 0x00000001,0xFFFFFFFE,0x00000000,0x00000002,0x00000000,0xFFFFFFFE, |
| 196 | 0x00000000,0x00000002,0x00000001,0x00000000,0x00000000,0x00000000, |
| 197 | 0xFFFFFFFE,0x00000001,0x00000000,0xFFFFFFFE,0xFFFFFFFD,0xFFFFFFFF, |
| 198 | 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF |
| 199 | }; |
| 200 | static const BN_ULONG _nist_p_521[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, |
| 201 | 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, |
| 202 | 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, |
| 203 | 0xFFFFFFFF,0x000001FF}; |
| 204 | static const BN_ULONG _nist_p_521_sqr[] = { |
| 205 | 0x00000001,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000, |
| 206 | 0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000, |
| 207 | 0x00000000,0x00000000,0x00000000,0x00000000,0xFFFFFC00,0xFFFFFFFF, |
| 208 | 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, |
| 209 | 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, |
| 210 | 0xFFFFFFFF,0xFFFFFFFF,0x0003FFFF |
| 211 | }; |
| 212 | #else |
| 213 | #error "unsupported BN_BITS2" |
| 214 | #endif |
| 215 | |
| 216 | |
| 217 | static const BIGNUM _bignum_nist_p_192 = |
| 218 | { |
| 219 | (BN_ULONG *)_nist_p_192[0], |
| 220 | BN_NIST_192_TOP, |
| 221 | BN_NIST_192_TOP, |
| 222 | 0, |
| 223 | BN_FLG_STATIC_DATA |
| 224 | }; |
| 225 | |
| 226 | static const BIGNUM _bignum_nist_p_224 = |
| 227 | { |
| 228 | (BN_ULONG *)_nist_p_224[0], |
| 229 | BN_NIST_224_TOP, |
| 230 | BN_NIST_224_TOP, |
| 231 | 0, |
| 232 | BN_FLG_STATIC_DATA |
| 233 | }; |
| 234 | |
| 235 | static const BIGNUM _bignum_nist_p_256 = |
| 236 | { |
| 237 | (BN_ULONG *)_nist_p_256[0], |
| 238 | BN_NIST_256_TOP, |
| 239 | BN_NIST_256_TOP, |
| 240 | 0, |
| 241 | BN_FLG_STATIC_DATA |
| 242 | }; |
| 243 | |
| 244 | static const BIGNUM _bignum_nist_p_384 = |
| 245 | { |
| 246 | (BN_ULONG *)_nist_p_384[0], |
| 247 | BN_NIST_384_TOP, |
| 248 | BN_NIST_384_TOP, |
| 249 | 0, |
| 250 | BN_FLG_STATIC_DATA |
| 251 | }; |
| 252 | |
| 253 | static const BIGNUM _bignum_nist_p_521 = |
| 254 | { |
| 255 | (BN_ULONG *)_nist_p_521, |
| 256 | BN_NIST_521_TOP, |
| 257 | BN_NIST_521_TOP, |
| 258 | 0, |
| 259 | BN_FLG_STATIC_DATA |
| 260 | }; |
| 261 | |
| 262 | |
| 263 | const BIGNUM *BN_get0_nist_prime_192(void) |
| 264 | { |
| 265 | return &_bignum_nist_p_192; |
| 266 | } |
| 267 | |
| 268 | const BIGNUM *BN_get0_nist_prime_224(void) |
| 269 | { |
| 270 | return &_bignum_nist_p_224; |
| 271 | } |
| 272 | |
| 273 | const BIGNUM *BN_get0_nist_prime_256(void) |
| 274 | { |
| 275 | return &_bignum_nist_p_256; |
| 276 | } |
| 277 | |
| 278 | const BIGNUM *BN_get0_nist_prime_384(void) |
| 279 | { |
| 280 | return &_bignum_nist_p_384; |
| 281 | } |
| 282 | |
| 283 | const BIGNUM *BN_get0_nist_prime_521(void) |
| 284 | { |
| 285 | return &_bignum_nist_p_521; |
| 286 | } |
| 287 | |
| 288 | |
| 289 | static void nist_cp_bn_0(BN_ULONG *buf, BN_ULONG *a, int top, int max) |
| 290 | { |
| 291 | int i; |
| 292 | BN_ULONG *_tmp1 = (buf), *_tmp2 = (a); |
| 293 | |
| 294 | #ifdef BN_DEBUG |
| 295 | OPENSSL_assert(top <= max); |
| 296 | #endif |
| 297 | for (i = (top); i != 0; i--) |
| 298 | *_tmp1++ = *_tmp2++; |
| 299 | for (i = (max) - (top); i != 0; i--) |
| 300 | *_tmp1++ = (BN_ULONG) 0; |
| 301 | } |
| 302 | |
| 303 | static void nist_cp_bn(BN_ULONG *buf, BN_ULONG *a, int top) |
| 304 | { |
| 305 | int i; |
| 306 | BN_ULONG *_tmp1 = (buf), *_tmp2 = (a); |
| 307 | for (i = (top); i != 0; i--) |
| 308 | *_tmp1++ = *_tmp2++; |
| 309 | } |
| 310 | |
| 311 | #if BN_BITS2 == 64 |
| 312 | #define bn_cp_64(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0; |
| 313 | #define bn_64_set_0(to, n) (to)[n] = (BN_ULONG)0; |
| 314 | /* |
| 315 | * two following macros are implemented under assumption that they |
| 316 | * are called in a sequence with *ascending* n, i.e. as they are... |
| 317 | */ |
| 318 | #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))\ |
| 319 | :(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l))) |
| 320 | #define bn_32_set_0(to, n) (((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0)); |
| 321 | #define bn_cp_32(to,n,from,m) ((m)>=0)?bn_cp_32_naked(to,n,from,m):bn_32_set_0(to,n) |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 322 | #else |
| 323 | #define bn_cp_64(to, n, from, m) \ |
| 324 | { \ |
| 325 | bn_cp_32(to, (n)*2, from, (m)*2); \ |
| 326 | bn_cp_32(to, (n)*2+1, from, (m)*2+1); \ |
| 327 | } |
| 328 | #define bn_64_set_0(to, n) \ |
| 329 | { \ |
| 330 | bn_32_set_0(to, (n)*2); \ |
| 331 | bn_32_set_0(to, (n)*2+1); \ |
| 332 | } |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 333 | #if BN_BITS2 == 32 |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 334 | #define bn_cp_32(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0; |
| 335 | #define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0; |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 336 | #endif |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 337 | #endif /* BN_BITS2 != 64 */ |
| 338 | |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 339 | |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 340 | #define nist_set_192(to, from, a1, a2, a3) \ |
| 341 | { \ |
| 342 | bn_cp_64(to, 0, from, (a3) - 3) \ |
| 343 | bn_cp_64(to, 1, from, (a2) - 3) \ |
| 344 | bn_cp_64(to, 2, from, (a1) - 3) \ |
| 345 | } |
| 346 | |
| 347 | int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, |
| 348 | BN_CTX *ctx) |
| 349 | { |
| 350 | int top = a->top, i; |
| 351 | int carry; |
| 352 | register BN_ULONG *r_d, *a_d = a->d; |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 353 | BN_ULONG t_d[BN_NIST_192_TOP], |
| 354 | buf[BN_NIST_192_TOP], |
| 355 | c_d[BN_NIST_192_TOP], |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 356 | *res; |
| 357 | PTR_SIZE_INT mask; |
| 358 | static const BIGNUM _bignum_nist_p_192_sqr = { |
| 359 | (BN_ULONG *)_nist_p_192_sqr, |
| 360 | sizeof(_nist_p_192_sqr)/sizeof(_nist_p_192_sqr[0]), |
| 361 | sizeof(_nist_p_192_sqr)/sizeof(_nist_p_192_sqr[0]), |
| 362 | 0,BN_FLG_STATIC_DATA }; |
| 363 | |
| 364 | field = &_bignum_nist_p_192; /* just to make sure */ |
| 365 | |
| 366 | if (BN_is_negative(a) || BN_ucmp(a,&_bignum_nist_p_192_sqr)>=0) |
| 367 | return BN_nnmod(r, a, field, ctx); |
| 368 | |
| 369 | i = BN_ucmp(field, a); |
| 370 | if (i == 0) |
| 371 | { |
| 372 | BN_zero(r); |
| 373 | return 1; |
| 374 | } |
| 375 | else if (i > 0) |
| 376 | return (r == a) ? 1 : (BN_copy(r ,a) != NULL); |
| 377 | |
| 378 | if (r != a) |
| 379 | { |
| 380 | if (!bn_wexpand(r, BN_NIST_192_TOP)) |
| 381 | return 0; |
| 382 | r_d = r->d; |
| 383 | nist_cp_bn(r_d, a_d, BN_NIST_192_TOP); |
| 384 | } |
| 385 | else |
| 386 | r_d = a_d; |
| 387 | |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 388 | nist_cp_bn_0(buf, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP, BN_NIST_192_TOP); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 389 | |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 390 | nist_set_192(t_d, buf, 0, 3, 3); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 391 | carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 392 | nist_set_192(t_d, buf, 4, 4, 0); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 393 | carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 394 | nist_set_192(t_d, buf, 5, 5, 5) |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 395 | carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 396 | |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 397 | if (carry > 0) |
| 398 | carry = (int)bn_sub_words(r_d,r_d,_nist_p_192[carry-1],BN_NIST_192_TOP); |
| 399 | else |
| 400 | carry = 1; |
| 401 | |
| 402 | /* |
| 403 | * we need 'if (carry==0 || result>=modulus) result-=modulus;' |
| 404 | * as comparison implies subtraction, we can write |
| 405 | * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;' |
| 406 | * this is what happens below, but without explicit if:-) a. |
| 407 | */ |
| 408 | mask = 0-(PTR_SIZE_INT)bn_sub_words(c_d,r_d,_nist_p_192[0],BN_NIST_192_TOP); |
| 409 | mask &= 0-(PTR_SIZE_INT)carry; |
| 410 | res = (BN_ULONG *) |
| 411 | (((PTR_SIZE_INT)c_d&~mask) | ((PTR_SIZE_INT)r_d&mask)); |
| 412 | nist_cp_bn(r_d, res, BN_NIST_192_TOP); |
| 413 | r->top = BN_NIST_192_TOP; |
| 414 | bn_correct_top(r); |
| 415 | |
| 416 | return 1; |
| 417 | } |
| 418 | |
| 419 | typedef BN_ULONG (*bn_addsub_f)(BN_ULONG *,const BN_ULONG *,const BN_ULONG *,int); |
| 420 | |
| 421 | #define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \ |
| 422 | { \ |
| 423 | bn_cp_32(to, 0, from, (a7) - 7) \ |
| 424 | bn_cp_32(to, 1, from, (a6) - 7) \ |
| 425 | bn_cp_32(to, 2, from, (a5) - 7) \ |
| 426 | bn_cp_32(to, 3, from, (a4) - 7) \ |
| 427 | bn_cp_32(to, 4, from, (a3) - 7) \ |
| 428 | bn_cp_32(to, 5, from, (a2) - 7) \ |
| 429 | bn_cp_32(to, 6, from, (a1) - 7) \ |
| 430 | } |
| 431 | |
| 432 | int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, |
| 433 | BN_CTX *ctx) |
| 434 | { |
| 435 | int top = a->top, i; |
| 436 | int carry; |
| 437 | BN_ULONG *r_d, *a_d = a->d; |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 438 | BN_ULONG t_d[BN_NIST_224_TOP], |
| 439 | buf[BN_NIST_224_TOP], |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 440 | c_d[BN_NIST_224_TOP], |
| 441 | *res; |
| 442 | PTR_SIZE_INT mask; |
| 443 | union { bn_addsub_f f; PTR_SIZE_INT p; } u; |
| 444 | static const BIGNUM _bignum_nist_p_224_sqr = { |
| 445 | (BN_ULONG *)_nist_p_224_sqr, |
| 446 | sizeof(_nist_p_224_sqr)/sizeof(_nist_p_224_sqr[0]), |
| 447 | sizeof(_nist_p_224_sqr)/sizeof(_nist_p_224_sqr[0]), |
| 448 | 0,BN_FLG_STATIC_DATA }; |
| 449 | |
| 450 | |
| 451 | field = &_bignum_nist_p_224; /* just to make sure */ |
| 452 | |
| 453 | if (BN_is_negative(a) || BN_ucmp(a,&_bignum_nist_p_224_sqr)>=0) |
| 454 | return BN_nnmod(r, a, field, ctx); |
| 455 | |
| 456 | i = BN_ucmp(field, a); |
| 457 | if (i == 0) |
| 458 | { |
| 459 | BN_zero(r); |
| 460 | return 1; |
| 461 | } |
| 462 | else if (i > 0) |
| 463 | return (r == a)? 1 : (BN_copy(r ,a) != NULL); |
| 464 | |
| 465 | if (r != a) |
| 466 | { |
| 467 | if (!bn_wexpand(r, BN_NIST_224_TOP)) |
| 468 | return 0; |
| 469 | r_d = r->d; |
| 470 | nist_cp_bn(r_d, a_d, BN_NIST_224_TOP); |
| 471 | } |
| 472 | else |
| 473 | r_d = a_d; |
| 474 | |
| 475 | #if BN_BITS2==64 |
| 476 | /* copy upper 256 bits of 448 bit number ... */ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 477 | nist_cp_bn_0(t_d, a_d + (BN_NIST_224_TOP-1), top - (BN_NIST_224_TOP-1), BN_NIST_224_TOP); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 478 | /* ... and right shift by 32 to obtain upper 224 bits */ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 479 | nist_set_224(buf, t_d, 14, 13, 12, 11, 10, 9, 8); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 480 | /* truncate lower part to 224 bits too */ |
| 481 | r_d[BN_NIST_224_TOP-1] &= BN_MASK2l; |
| 482 | #else |
| 483 | nist_cp_bn_0(buf, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP, BN_NIST_224_TOP); |
| 484 | #endif |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 485 | nist_set_224(t_d, buf, 10, 9, 8, 7, 0, 0, 0); |
| 486 | carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP); |
| 487 | nist_set_224(t_d, buf, 0, 13, 12, 11, 0, 0, 0); |
| 488 | carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP); |
| 489 | nist_set_224(t_d, buf, 13, 12, 11, 10, 9, 8, 7); |
| 490 | carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP); |
| 491 | nist_set_224(t_d, buf, 0, 0, 0, 0, 13, 12, 11); |
| 492 | carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP); |
| 493 | |
| 494 | #if BN_BITS2==64 |
| 495 | carry = (int)(r_d[BN_NIST_224_TOP-1]>>32); |
| 496 | #endif |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 497 | u.f = bn_sub_words; |
| 498 | if (carry > 0) |
| 499 | { |
| 500 | carry = (int)bn_sub_words(r_d,r_d,_nist_p_224[carry-1],BN_NIST_224_TOP); |
| 501 | #if BN_BITS2==64 |
| 502 | carry=(int)(~(r_d[BN_NIST_224_TOP-1]>>32))&1; |
| 503 | #endif |
| 504 | } |
| 505 | else if (carry < 0) |
| 506 | { |
| 507 | /* it's a bit more comlicated logic in this case. |
| 508 | * if bn_add_words yields no carry, then result |
| 509 | * has to be adjusted by unconditionally *adding* |
| 510 | * the modulus. but if it does, then result has |
| 511 | * to be compared to the modulus and conditionally |
| 512 | * adjusted by *subtracting* the latter. */ |
| 513 | carry = (int)bn_add_words(r_d,r_d,_nist_p_224[-carry-1],BN_NIST_224_TOP); |
| 514 | mask = 0-(PTR_SIZE_INT)carry; |
| 515 | u.p = ((PTR_SIZE_INT)bn_sub_words&mask) | |
| 516 | ((PTR_SIZE_INT)bn_add_words&~mask); |
| 517 | } |
| 518 | else |
| 519 | carry = 1; |
| 520 | |
| 521 | /* otherwise it's effectively same as in BN_nist_mod_192... */ |
| 522 | mask = 0-(PTR_SIZE_INT)(*u.f)(c_d,r_d,_nist_p_224[0],BN_NIST_224_TOP); |
| 523 | mask &= 0-(PTR_SIZE_INT)carry; |
| 524 | res = (BN_ULONG *)(((PTR_SIZE_INT)c_d&~mask) | |
| 525 | ((PTR_SIZE_INT)r_d&mask)); |
| 526 | nist_cp_bn(r_d, res, BN_NIST_224_TOP); |
| 527 | r->top = BN_NIST_224_TOP; |
| 528 | bn_correct_top(r); |
| 529 | |
| 530 | return 1; |
| 531 | } |
| 532 | |
| 533 | #define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \ |
| 534 | { \ |
| 535 | bn_cp_32(to, 0, from, (a8) - 8) \ |
| 536 | bn_cp_32(to, 1, from, (a7) - 8) \ |
| 537 | bn_cp_32(to, 2, from, (a6) - 8) \ |
| 538 | bn_cp_32(to, 3, from, (a5) - 8) \ |
| 539 | bn_cp_32(to, 4, from, (a4) - 8) \ |
| 540 | bn_cp_32(to, 5, from, (a3) - 8) \ |
| 541 | bn_cp_32(to, 6, from, (a2) - 8) \ |
| 542 | bn_cp_32(to, 7, from, (a1) - 8) \ |
| 543 | } |
| 544 | |
| 545 | int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, |
| 546 | BN_CTX *ctx) |
| 547 | { |
| 548 | int i, top = a->top; |
| 549 | int carry = 0; |
| 550 | register BN_ULONG *a_d = a->d, *r_d; |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 551 | BN_ULONG t_d[BN_NIST_256_TOP], |
| 552 | buf[BN_NIST_256_TOP], |
| 553 | c_d[BN_NIST_256_TOP], |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 554 | *res; |
| 555 | PTR_SIZE_INT mask; |
| 556 | union { bn_addsub_f f; PTR_SIZE_INT p; } u; |
| 557 | static const BIGNUM _bignum_nist_p_256_sqr = { |
| 558 | (BN_ULONG *)_nist_p_256_sqr, |
| 559 | sizeof(_nist_p_256_sqr)/sizeof(_nist_p_256_sqr[0]), |
| 560 | sizeof(_nist_p_256_sqr)/sizeof(_nist_p_256_sqr[0]), |
| 561 | 0,BN_FLG_STATIC_DATA }; |
| 562 | |
| 563 | field = &_bignum_nist_p_256; /* just to make sure */ |
| 564 | |
| 565 | if (BN_is_negative(a) || BN_ucmp(a,&_bignum_nist_p_256_sqr)>=0) |
| 566 | return BN_nnmod(r, a, field, ctx); |
| 567 | |
| 568 | i = BN_ucmp(field, a); |
| 569 | if (i == 0) |
| 570 | { |
| 571 | BN_zero(r); |
| 572 | return 1; |
| 573 | } |
| 574 | else if (i > 0) |
| 575 | return (r == a)? 1 : (BN_copy(r ,a) != NULL); |
| 576 | |
| 577 | if (r != a) |
| 578 | { |
| 579 | if (!bn_wexpand(r, BN_NIST_256_TOP)) |
| 580 | return 0; |
| 581 | r_d = r->d; |
| 582 | nist_cp_bn(r_d, a_d, BN_NIST_256_TOP); |
| 583 | } |
| 584 | else |
| 585 | r_d = a_d; |
| 586 | |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 587 | nist_cp_bn_0(buf, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP, BN_NIST_256_TOP); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 588 | |
| 589 | /*S1*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 590 | nist_set_256(t_d, buf, 15, 14, 13, 12, 11, 0, 0, 0); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 591 | /*S2*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 592 | nist_set_256(c_d, buf, 0, 15, 14, 13, 12, 0, 0, 0); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 593 | carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP); |
| 594 | /* left shift */ |
| 595 | { |
| 596 | register BN_ULONG *ap,t,c; |
| 597 | ap = t_d; |
| 598 | c=0; |
| 599 | for (i = BN_NIST_256_TOP; i != 0; --i) |
| 600 | { |
| 601 | t= *ap; |
| 602 | *(ap++)=((t<<1)|c)&BN_MASK2; |
| 603 | c=(t & BN_TBIT)?1:0; |
| 604 | } |
| 605 | carry <<= 1; |
| 606 | carry |= c; |
| 607 | } |
| 608 | carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); |
| 609 | /*S3*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 610 | nist_set_256(t_d, buf, 15, 14, 0, 0, 0, 10, 9, 8); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 611 | carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); |
| 612 | /*S4*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 613 | nist_set_256(t_d, buf, 8, 13, 15, 14, 13, 11, 10, 9); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 614 | carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); |
| 615 | /*D1*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 616 | nist_set_256(t_d, buf, 10, 8, 0, 0, 0, 13, 12, 11); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 617 | carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); |
| 618 | /*D2*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 619 | nist_set_256(t_d, buf, 11, 9, 0, 0, 15, 14, 13, 12); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 620 | carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); |
| 621 | /*D3*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 622 | nist_set_256(t_d, buf, 12, 0, 10, 9, 8, 15, 14, 13); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 623 | carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); |
| 624 | /*D4*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 625 | nist_set_256(t_d, buf, 13, 0, 11, 10, 9, 0, 15, 14); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 626 | carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); |
| 627 | |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 628 | /* see BN_nist_mod_224 for explanation */ |
| 629 | u.f = bn_sub_words; |
| 630 | if (carry > 0) |
| 631 | carry = (int)bn_sub_words(r_d,r_d,_nist_p_256[carry-1],BN_NIST_256_TOP); |
| 632 | else if (carry < 0) |
| 633 | { |
| 634 | carry = (int)bn_add_words(r_d,r_d,_nist_p_256[-carry-1],BN_NIST_256_TOP); |
| 635 | mask = 0-(PTR_SIZE_INT)carry; |
| 636 | u.p = ((PTR_SIZE_INT)bn_sub_words&mask) | |
| 637 | ((PTR_SIZE_INT)bn_add_words&~mask); |
| 638 | } |
| 639 | else |
| 640 | carry = 1; |
| 641 | |
| 642 | mask = 0-(PTR_SIZE_INT)(*u.f)(c_d,r_d,_nist_p_256[0],BN_NIST_256_TOP); |
| 643 | mask &= 0-(PTR_SIZE_INT)carry; |
| 644 | res = (BN_ULONG *)(((PTR_SIZE_INT)c_d&~mask) | |
| 645 | ((PTR_SIZE_INT)r_d&mask)); |
| 646 | nist_cp_bn(r_d, res, BN_NIST_256_TOP); |
| 647 | r->top = BN_NIST_256_TOP; |
| 648 | bn_correct_top(r); |
| 649 | |
| 650 | return 1; |
| 651 | } |
| 652 | |
| 653 | #define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \ |
| 654 | { \ |
| 655 | bn_cp_32(to, 0, from, (a12) - 12) \ |
| 656 | bn_cp_32(to, 1, from, (a11) - 12) \ |
| 657 | bn_cp_32(to, 2, from, (a10) - 12) \ |
| 658 | bn_cp_32(to, 3, from, (a9) - 12) \ |
| 659 | bn_cp_32(to, 4, from, (a8) - 12) \ |
| 660 | bn_cp_32(to, 5, from, (a7) - 12) \ |
| 661 | bn_cp_32(to, 6, from, (a6) - 12) \ |
| 662 | bn_cp_32(to, 7, from, (a5) - 12) \ |
| 663 | bn_cp_32(to, 8, from, (a4) - 12) \ |
| 664 | bn_cp_32(to, 9, from, (a3) - 12) \ |
| 665 | bn_cp_32(to, 10, from, (a2) - 12) \ |
| 666 | bn_cp_32(to, 11, from, (a1) - 12) \ |
| 667 | } |
| 668 | |
| 669 | int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, |
| 670 | BN_CTX *ctx) |
| 671 | { |
| 672 | int i, top = a->top; |
| 673 | int carry = 0; |
| 674 | register BN_ULONG *r_d, *a_d = a->d; |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 675 | BN_ULONG t_d[BN_NIST_384_TOP], |
| 676 | buf[BN_NIST_384_TOP], |
| 677 | c_d[BN_NIST_384_TOP], |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 678 | *res; |
| 679 | PTR_SIZE_INT mask; |
| 680 | union { bn_addsub_f f; PTR_SIZE_INT p; } u; |
| 681 | static const BIGNUM _bignum_nist_p_384_sqr = { |
| 682 | (BN_ULONG *)_nist_p_384_sqr, |
| 683 | sizeof(_nist_p_384_sqr)/sizeof(_nist_p_384_sqr[0]), |
| 684 | sizeof(_nist_p_384_sqr)/sizeof(_nist_p_384_sqr[0]), |
| 685 | 0,BN_FLG_STATIC_DATA }; |
| 686 | |
| 687 | |
| 688 | field = &_bignum_nist_p_384; /* just to make sure */ |
| 689 | |
| 690 | if (BN_is_negative(a) || BN_ucmp(a,&_bignum_nist_p_384_sqr)>=0) |
| 691 | return BN_nnmod(r, a, field, ctx); |
| 692 | |
| 693 | i = BN_ucmp(field, a); |
| 694 | if (i == 0) |
| 695 | { |
| 696 | BN_zero(r); |
| 697 | return 1; |
| 698 | } |
| 699 | else if (i > 0) |
| 700 | return (r == a)? 1 : (BN_copy(r ,a) != NULL); |
| 701 | |
| 702 | if (r != a) |
| 703 | { |
| 704 | if (!bn_wexpand(r, BN_NIST_384_TOP)) |
| 705 | return 0; |
| 706 | r_d = r->d; |
| 707 | nist_cp_bn(r_d, a_d, BN_NIST_384_TOP); |
| 708 | } |
| 709 | else |
| 710 | r_d = a_d; |
| 711 | |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 712 | nist_cp_bn_0(buf, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP, BN_NIST_384_TOP); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 713 | |
| 714 | /*S1*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 715 | nist_set_256(t_d, buf, 0, 0, 0, 0, 0, 23-4, 22-4, 21-4); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 716 | /* left shift */ |
| 717 | { |
| 718 | register BN_ULONG *ap,t,c; |
| 719 | ap = t_d; |
| 720 | c=0; |
| 721 | for (i = 3; i != 0; --i) |
| 722 | { |
| 723 | t= *ap; |
| 724 | *(ap++)=((t<<1)|c)&BN_MASK2; |
| 725 | c=(t & BN_TBIT)?1:0; |
| 726 | } |
| 727 | *ap=c; |
| 728 | } |
| 729 | carry = (int)bn_add_words(r_d+(128/BN_BITS2), r_d+(128/BN_BITS2), |
| 730 | t_d, BN_NIST_256_TOP); |
| 731 | /*S2 */ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 732 | carry += (int)bn_add_words(r_d, r_d, buf, BN_NIST_384_TOP); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 733 | /*S3*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 734 | nist_set_384(t_d,buf,20,19,18,17,16,15,14,13,12,23,22,21); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 735 | carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); |
| 736 | /*S4*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 737 | nist_set_384(t_d,buf,19,18,17,16,15,14,13,12,20,0,23,0); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 738 | carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); |
| 739 | /*S5*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 740 | nist_set_384(t_d, buf,0,0,0,0,23,22,21,20,0,0,0,0); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 741 | carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); |
| 742 | /*S6*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 743 | nist_set_384(t_d,buf,0,0,0,0,0,0,23,22,21,0,0,20); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 744 | carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); |
| 745 | /*D1*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 746 | nist_set_384(t_d,buf,22,21,20,19,18,17,16,15,14,13,12,23); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 747 | carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); |
| 748 | /*D2*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 749 | nist_set_384(t_d,buf,0,0,0,0,0,0,0,23,22,21,20,0); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 750 | carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); |
| 751 | /*D3*/ |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 752 | nist_set_384(t_d,buf,0,0,0,0,0,0,0,23,23,0,0,0); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 753 | carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); |
| 754 | |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 755 | /* see BN_nist_mod_224 for explanation */ |
| 756 | u.f = bn_sub_words; |
| 757 | if (carry > 0) |
| 758 | carry = (int)bn_sub_words(r_d,r_d,_nist_p_384[carry-1],BN_NIST_384_TOP); |
| 759 | else if (carry < 0) |
| 760 | { |
| 761 | carry = (int)bn_add_words(r_d,r_d,_nist_p_384[-carry-1],BN_NIST_384_TOP); |
| 762 | mask = 0-(PTR_SIZE_INT)carry; |
| 763 | u.p = ((PTR_SIZE_INT)bn_sub_words&mask) | |
| 764 | ((PTR_SIZE_INT)bn_add_words&~mask); |
| 765 | } |
| 766 | else |
| 767 | carry = 1; |
| 768 | |
| 769 | mask = 0-(PTR_SIZE_INT)(*u.f)(c_d,r_d,_nist_p_384[0],BN_NIST_384_TOP); |
| 770 | mask &= 0-(PTR_SIZE_INT)carry; |
| 771 | res = (BN_ULONG *)(((PTR_SIZE_INT)c_d&~mask) | |
| 772 | ((PTR_SIZE_INT)r_d&mask)); |
| 773 | nist_cp_bn(r_d, res, BN_NIST_384_TOP); |
| 774 | r->top = BN_NIST_384_TOP; |
| 775 | bn_correct_top(r); |
| 776 | |
| 777 | return 1; |
| 778 | } |
| 779 | |
| 780 | #define BN_NIST_521_RSHIFT (521%BN_BITS2) |
| 781 | #define BN_NIST_521_LSHIFT (BN_BITS2-BN_NIST_521_RSHIFT) |
| 782 | #define BN_NIST_521_TOP_MASK ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT) |
| 783 | |
| 784 | int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, |
| 785 | BN_CTX *ctx) |
| 786 | { |
| 787 | int top = a->top, i; |
| 788 | BN_ULONG *r_d, *a_d = a->d, |
| 789 | t_d[BN_NIST_521_TOP], |
| 790 | val,tmp,*res; |
| 791 | PTR_SIZE_INT mask; |
| 792 | static const BIGNUM _bignum_nist_p_521_sqr = { |
| 793 | (BN_ULONG *)_nist_p_521_sqr, |
| 794 | sizeof(_nist_p_521_sqr)/sizeof(_nist_p_521_sqr[0]), |
| 795 | sizeof(_nist_p_521_sqr)/sizeof(_nist_p_521_sqr[0]), |
| 796 | 0,BN_FLG_STATIC_DATA }; |
| 797 | |
| 798 | field = &_bignum_nist_p_521; /* just to make sure */ |
| 799 | |
| 800 | if (BN_is_negative(a) || BN_ucmp(a,&_bignum_nist_p_521_sqr)>=0) |
| 801 | return BN_nnmod(r, a, field, ctx); |
| 802 | |
| 803 | i = BN_ucmp(field, a); |
| 804 | if (i == 0) |
| 805 | { |
| 806 | BN_zero(r); |
| 807 | return 1; |
| 808 | } |
| 809 | else if (i > 0) |
| 810 | return (r == a)? 1 : (BN_copy(r ,a) != NULL); |
| 811 | |
| 812 | if (r != a) |
| 813 | { |
| 814 | if (!bn_wexpand(r,BN_NIST_521_TOP)) |
| 815 | return 0; |
| 816 | r_d = r->d; |
| 817 | nist_cp_bn(r_d,a_d, BN_NIST_521_TOP); |
| 818 | } |
| 819 | else |
| 820 | r_d = a_d; |
| 821 | |
| 822 | /* upper 521 bits, copy ... */ |
| 823 | nist_cp_bn_0(t_d,a_d + (BN_NIST_521_TOP-1), top - (BN_NIST_521_TOP-1),BN_NIST_521_TOP); |
| 824 | /* ... and right shift */ |
| 825 | for (val=t_d[0],i=0; i<BN_NIST_521_TOP-1; i++) |
| 826 | { |
| 827 | tmp = val>>BN_NIST_521_RSHIFT; |
| 828 | val = t_d[i+1]; |
| 829 | t_d[i] = (tmp | val<<BN_NIST_521_LSHIFT) & BN_MASK2; |
| 830 | } |
| 831 | t_d[i] = val>>BN_NIST_521_RSHIFT; |
| 832 | /* lower 521 bits */ |
| 833 | r_d[i] &= BN_NIST_521_TOP_MASK; |
| 834 | |
| 835 | bn_add_words(r_d,r_d,t_d,BN_NIST_521_TOP); |
| 836 | mask = 0-(PTR_SIZE_INT)bn_sub_words(t_d,r_d,_nist_p_521,BN_NIST_521_TOP); |
| 837 | res = (BN_ULONG *)(((PTR_SIZE_INT)t_d&~mask) | |
| 838 | ((PTR_SIZE_INT)r_d&mask)); |
| 839 | nist_cp_bn(r_d,res,BN_NIST_521_TOP); |
| 840 | r->top = BN_NIST_521_TOP; |
| 841 | bn_correct_top(r); |
| 842 | |
| 843 | return 1; |
| 844 | } |