Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 1 | /* crypto/bn/bn_gf2m.c */ |
| 2 | /* ==================================================================== |
| 3 | * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. |
| 4 | * |
| 5 | * The Elliptic Curve Public-Key Crypto Library (ECC Code) included |
| 6 | * herein is developed by SUN MICROSYSTEMS, INC., and is contributed |
| 7 | * to the OpenSSL project. |
| 8 | * |
| 9 | * The ECC Code is licensed pursuant to the OpenSSL open source |
| 10 | * license provided below. |
| 11 | * |
| 12 | * In addition, Sun covenants to all licensees who provide a reciprocal |
| 13 | * covenant with respect to their own patents if any, not to sue under |
| 14 | * current and future patent claims necessarily infringed by the making, |
| 15 | * using, practicing, selling, offering for sale and/or otherwise |
| 16 | * disposing of the ECC Code as delivered hereunder (or portions thereof), |
| 17 | * provided that such covenant shall not apply: |
| 18 | * 1) for code that a licensee deletes from the ECC Code; |
| 19 | * 2) separates from the ECC Code; or |
| 20 | * 3) for infringements caused by: |
| 21 | * i) the modification of the ECC Code or |
| 22 | * ii) the combination of the ECC Code with other software or |
| 23 | * devices where such combination causes the infringement. |
| 24 | * |
| 25 | * The software is originally written by Sheueling Chang Shantz and |
| 26 | * Douglas Stebila of Sun Microsystems Laboratories. |
| 27 | * |
| 28 | */ |
| 29 | |
| 30 | /* NOTE: This file is licensed pursuant to the OpenSSL license below |
| 31 | * and may be modified; but after modifications, the above covenant |
| 32 | * may no longer apply! In such cases, the corresponding paragraph |
| 33 | * ["In addition, Sun covenants ... causes the infringement."] and |
| 34 | * this note can be edited out; but please keep the Sun copyright |
| 35 | * notice and attribution. */ |
| 36 | |
| 37 | /* ==================================================================== |
| 38 | * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved. |
| 39 | * |
| 40 | * Redistribution and use in source and binary forms, with or without |
| 41 | * modification, are permitted provided that the following conditions |
| 42 | * are met: |
| 43 | * |
| 44 | * 1. Redistributions of source code must retain the above copyright |
| 45 | * notice, this list of conditions and the following disclaimer. |
| 46 | * |
| 47 | * 2. Redistributions in binary form must reproduce the above copyright |
| 48 | * notice, this list of conditions and the following disclaimer in |
| 49 | * the documentation and/or other materials provided with the |
| 50 | * distribution. |
| 51 | * |
| 52 | * 3. All advertising materials mentioning features or use of this |
| 53 | * software must display the following acknowledgment: |
| 54 | * "This product includes software developed by the OpenSSL Project |
| 55 | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" |
| 56 | * |
| 57 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to |
| 58 | * endorse or promote products derived from this software without |
| 59 | * prior written permission. For written permission, please contact |
| 60 | * openssl-core@openssl.org. |
| 61 | * |
| 62 | * 5. Products derived from this software may not be called "OpenSSL" |
| 63 | * nor may "OpenSSL" appear in their names without prior written |
| 64 | * permission of the OpenSSL Project. |
| 65 | * |
| 66 | * 6. Redistributions of any form whatsoever must retain the following |
| 67 | * acknowledgment: |
| 68 | * "This product includes software developed by the OpenSSL Project |
| 69 | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" |
| 70 | * |
| 71 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY |
| 72 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| 73 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| 74 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR |
| 75 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 76 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| 77 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
| 78 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 79 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
| 80 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| 81 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
| 82 | * OF THE POSSIBILITY OF SUCH DAMAGE. |
| 83 | * ==================================================================== |
| 84 | * |
| 85 | * This product includes cryptographic software written by Eric Young |
| 86 | * (eay@cryptsoft.com). This product includes software written by Tim |
| 87 | * Hudson (tjh@cryptsoft.com). |
| 88 | * |
| 89 | */ |
| 90 | |
| 91 | #include <assert.h> |
| 92 | #include <limits.h> |
| 93 | #include <stdio.h> |
| 94 | #include "cryptlib.h" |
| 95 | #include "bn_lcl.h" |
| 96 | |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 97 | /* Maximum number of iterations before BN_GF2m_mod_solve_quad_arr should fail. */ |
| 98 | #define MAX_ITERATIONS 50 |
| 99 | |
| 100 | static const BN_ULONG SQR_tb[16] = |
| 101 | { 0, 1, 4, 5, 16, 17, 20, 21, |
| 102 | 64, 65, 68, 69, 80, 81, 84, 85 }; |
| 103 | /* Platform-specific macros to accelerate squaring. */ |
| 104 | #if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) |
| 105 | #define SQR1(w) \ |
| 106 | SQR_tb[(w) >> 60 & 0xF] << 56 | SQR_tb[(w) >> 56 & 0xF] << 48 | \ |
| 107 | SQR_tb[(w) >> 52 & 0xF] << 40 | SQR_tb[(w) >> 48 & 0xF] << 32 | \ |
| 108 | SQR_tb[(w) >> 44 & 0xF] << 24 | SQR_tb[(w) >> 40 & 0xF] << 16 | \ |
| 109 | SQR_tb[(w) >> 36 & 0xF] << 8 | SQR_tb[(w) >> 32 & 0xF] |
| 110 | #define SQR0(w) \ |
| 111 | SQR_tb[(w) >> 28 & 0xF] << 56 | SQR_tb[(w) >> 24 & 0xF] << 48 | \ |
| 112 | SQR_tb[(w) >> 20 & 0xF] << 40 | SQR_tb[(w) >> 16 & 0xF] << 32 | \ |
| 113 | SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >> 8 & 0xF] << 16 | \ |
| 114 | SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF] |
| 115 | #endif |
| 116 | #ifdef THIRTY_TWO_BIT |
| 117 | #define SQR1(w) \ |
| 118 | SQR_tb[(w) >> 28 & 0xF] << 24 | SQR_tb[(w) >> 24 & 0xF] << 16 | \ |
| 119 | SQR_tb[(w) >> 20 & 0xF] << 8 | SQR_tb[(w) >> 16 & 0xF] |
| 120 | #define SQR0(w) \ |
| 121 | SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >> 8 & 0xF] << 16 | \ |
| 122 | SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF] |
| 123 | #endif |
| 124 | |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 125 | /* Product of two polynomials a, b each with degree < BN_BITS2 - 1, |
| 126 | * result is a polynomial r with degree < 2 * BN_BITS - 1 |
| 127 | * The caller MUST ensure that the variables have the right amount |
| 128 | * of space allocated. |
| 129 | */ |
| 130 | #ifdef THIRTY_TWO_BIT |
| 131 | static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, const BN_ULONG b) |
| 132 | { |
| 133 | register BN_ULONG h, l, s; |
| 134 | BN_ULONG tab[8], top2b = a >> 30; |
| 135 | register BN_ULONG a1, a2, a4; |
| 136 | |
| 137 | a1 = a & (0x3FFFFFFF); a2 = a1 << 1; a4 = a2 << 1; |
| 138 | |
| 139 | tab[0] = 0; tab[1] = a1; tab[2] = a2; tab[3] = a1^a2; |
| 140 | tab[4] = a4; tab[5] = a1^a4; tab[6] = a2^a4; tab[7] = a1^a2^a4; |
| 141 | |
| 142 | s = tab[b & 0x7]; l = s; |
| 143 | s = tab[b >> 3 & 0x7]; l ^= s << 3; h = s >> 29; |
| 144 | s = tab[b >> 6 & 0x7]; l ^= s << 6; h ^= s >> 26; |
| 145 | s = tab[b >> 9 & 0x7]; l ^= s << 9; h ^= s >> 23; |
| 146 | s = tab[b >> 12 & 0x7]; l ^= s << 12; h ^= s >> 20; |
| 147 | s = tab[b >> 15 & 0x7]; l ^= s << 15; h ^= s >> 17; |
| 148 | s = tab[b >> 18 & 0x7]; l ^= s << 18; h ^= s >> 14; |
| 149 | s = tab[b >> 21 & 0x7]; l ^= s << 21; h ^= s >> 11; |
| 150 | s = tab[b >> 24 & 0x7]; l ^= s << 24; h ^= s >> 8; |
| 151 | s = tab[b >> 27 & 0x7]; l ^= s << 27; h ^= s >> 5; |
| 152 | s = tab[b >> 30 ]; l ^= s << 30; h ^= s >> 2; |
| 153 | |
| 154 | /* compensate for the top two bits of a */ |
| 155 | |
| 156 | if (top2b & 01) { l ^= b << 30; h ^= b >> 2; } |
| 157 | if (top2b & 02) { l ^= b << 31; h ^= b >> 1; } |
| 158 | |
| 159 | *r1 = h; *r0 = l; |
| 160 | } |
| 161 | #endif |
| 162 | #if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) |
| 163 | static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, const BN_ULONG b) |
| 164 | { |
| 165 | register BN_ULONG h, l, s; |
| 166 | BN_ULONG tab[16], top3b = a >> 61; |
| 167 | register BN_ULONG a1, a2, a4, a8; |
| 168 | |
| 169 | a1 = a & (0x1FFFFFFFFFFFFFFFULL); a2 = a1 << 1; a4 = a2 << 1; a8 = a4 << 1; |
| 170 | |
| 171 | tab[ 0] = 0; tab[ 1] = a1; tab[ 2] = a2; tab[ 3] = a1^a2; |
| 172 | tab[ 4] = a4; tab[ 5] = a1^a4; tab[ 6] = a2^a4; tab[ 7] = a1^a2^a4; |
| 173 | tab[ 8] = a8; tab[ 9] = a1^a8; tab[10] = a2^a8; tab[11] = a1^a2^a8; |
| 174 | tab[12] = a4^a8; tab[13] = a1^a4^a8; tab[14] = a2^a4^a8; tab[15] = a1^a2^a4^a8; |
| 175 | |
| 176 | s = tab[b & 0xF]; l = s; |
| 177 | s = tab[b >> 4 & 0xF]; l ^= s << 4; h = s >> 60; |
| 178 | s = tab[b >> 8 & 0xF]; l ^= s << 8; h ^= s >> 56; |
| 179 | s = tab[b >> 12 & 0xF]; l ^= s << 12; h ^= s >> 52; |
| 180 | s = tab[b >> 16 & 0xF]; l ^= s << 16; h ^= s >> 48; |
| 181 | s = tab[b >> 20 & 0xF]; l ^= s << 20; h ^= s >> 44; |
| 182 | s = tab[b >> 24 & 0xF]; l ^= s << 24; h ^= s >> 40; |
| 183 | s = tab[b >> 28 & 0xF]; l ^= s << 28; h ^= s >> 36; |
| 184 | s = tab[b >> 32 & 0xF]; l ^= s << 32; h ^= s >> 32; |
| 185 | s = tab[b >> 36 & 0xF]; l ^= s << 36; h ^= s >> 28; |
| 186 | s = tab[b >> 40 & 0xF]; l ^= s << 40; h ^= s >> 24; |
| 187 | s = tab[b >> 44 & 0xF]; l ^= s << 44; h ^= s >> 20; |
| 188 | s = tab[b >> 48 & 0xF]; l ^= s << 48; h ^= s >> 16; |
| 189 | s = tab[b >> 52 & 0xF]; l ^= s << 52; h ^= s >> 12; |
| 190 | s = tab[b >> 56 & 0xF]; l ^= s << 56; h ^= s >> 8; |
| 191 | s = tab[b >> 60 ]; l ^= s << 60; h ^= s >> 4; |
| 192 | |
| 193 | /* compensate for the top three bits of a */ |
| 194 | |
| 195 | if (top3b & 01) { l ^= b << 61; h ^= b >> 3; } |
| 196 | if (top3b & 02) { l ^= b << 62; h ^= b >> 2; } |
| 197 | if (top3b & 04) { l ^= b << 63; h ^= b >> 1; } |
| 198 | |
| 199 | *r1 = h; *r0 = l; |
| 200 | } |
| 201 | #endif |
| 202 | |
| 203 | /* Product of two polynomials a, b each with degree < 2 * BN_BITS2 - 1, |
| 204 | * result is a polynomial r with degree < 4 * BN_BITS2 - 1 |
| 205 | * The caller MUST ensure that the variables have the right amount |
| 206 | * of space allocated. |
| 207 | */ |
| 208 | static void bn_GF2m_mul_2x2(BN_ULONG *r, const BN_ULONG a1, const BN_ULONG a0, const BN_ULONG b1, const BN_ULONG b0) |
| 209 | { |
| 210 | BN_ULONG m1, m0; |
| 211 | /* r[3] = h1, r[2] = h0; r[1] = l1; r[0] = l0 */ |
| 212 | bn_GF2m_mul_1x1(r+3, r+2, a1, b1); |
| 213 | bn_GF2m_mul_1x1(r+1, r, a0, b0); |
| 214 | bn_GF2m_mul_1x1(&m1, &m0, a0 ^ a1, b0 ^ b1); |
| 215 | /* Correction on m1 ^= l1 ^ h1; m0 ^= l0 ^ h0; */ |
| 216 | r[2] ^= m1 ^ r[1] ^ r[3]; /* h0 ^= m1 ^ l1 ^ h1; */ |
| 217 | r[1] = r[3] ^ r[2] ^ r[0] ^ m1 ^ m0; /* l1 ^= l0 ^ h0 ^ m0; */ |
| 218 | } |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 219 | |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 220 | |
| 221 | /* Add polynomials a and b and store result in r; r could be a or b, a and b |
| 222 | * could be equal; r is the bitwise XOR of a and b. |
| 223 | */ |
| 224 | int BN_GF2m_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) |
| 225 | { |
| 226 | int i; |
| 227 | const BIGNUM *at, *bt; |
| 228 | |
| 229 | bn_check_top(a); |
| 230 | bn_check_top(b); |
| 231 | |
| 232 | if (a->top < b->top) { at = b; bt = a; } |
| 233 | else { at = a; bt = b; } |
| 234 | |
| 235 | if(bn_wexpand(r, at->top) == NULL) |
| 236 | return 0; |
| 237 | |
| 238 | for (i = 0; i < bt->top; i++) |
| 239 | { |
| 240 | r->d[i] = at->d[i] ^ bt->d[i]; |
| 241 | } |
| 242 | for (; i < at->top; i++) |
| 243 | { |
| 244 | r->d[i] = at->d[i]; |
| 245 | } |
| 246 | |
| 247 | r->top = at->top; |
| 248 | bn_correct_top(r); |
| 249 | |
| 250 | return 1; |
| 251 | } |
| 252 | |
| 253 | |
| 254 | /* Some functions allow for representation of the irreducible polynomials |
| 255 | * as an int[], say p. The irreducible f(t) is then of the form: |
| 256 | * t^p[0] + t^p[1] + ... + t^p[k] |
| 257 | * where m = p[0] > p[1] > ... > p[k] = 0. |
| 258 | */ |
| 259 | |
| 260 | |
| 261 | /* Performs modular reduction of a and store result in r. r could be a. */ |
| 262 | int BN_GF2m_mod_arr(BIGNUM *r, const BIGNUM *a, const int p[]) |
| 263 | { |
| 264 | int j, k; |
| 265 | int n, dN, d0, d1; |
| 266 | BN_ULONG zz, *z; |
| 267 | |
| 268 | bn_check_top(a); |
| 269 | |
| 270 | if (!p[0]) |
| 271 | { |
| 272 | /* reduction mod 1 => return 0 */ |
| 273 | BN_zero(r); |
| 274 | return 1; |
| 275 | } |
| 276 | |
| 277 | /* Since the algorithm does reduction in the r value, if a != r, copy |
| 278 | * the contents of a into r so we can do reduction in r. |
| 279 | */ |
| 280 | if (a != r) |
| 281 | { |
| 282 | if (!bn_wexpand(r, a->top)) return 0; |
| 283 | for (j = 0; j < a->top; j++) |
| 284 | { |
| 285 | r->d[j] = a->d[j]; |
| 286 | } |
| 287 | r->top = a->top; |
| 288 | } |
| 289 | z = r->d; |
| 290 | |
| 291 | /* start reduction */ |
| 292 | dN = p[0] / BN_BITS2; |
| 293 | for (j = r->top - 1; j > dN;) |
| 294 | { |
| 295 | zz = z[j]; |
| 296 | if (z[j] == 0) { j--; continue; } |
| 297 | z[j] = 0; |
| 298 | |
| 299 | for (k = 1; p[k] != 0; k++) |
| 300 | { |
| 301 | /* reducing component t^p[k] */ |
| 302 | n = p[0] - p[k]; |
| 303 | d0 = n % BN_BITS2; d1 = BN_BITS2 - d0; |
| 304 | n /= BN_BITS2; |
| 305 | z[j-n] ^= (zz>>d0); |
| 306 | if (d0) z[j-n-1] ^= (zz<<d1); |
| 307 | } |
| 308 | |
| 309 | /* reducing component t^0 */ |
| 310 | n = dN; |
| 311 | d0 = p[0] % BN_BITS2; |
| 312 | d1 = BN_BITS2 - d0; |
| 313 | z[j-n] ^= (zz >> d0); |
| 314 | if (d0) z[j-n-1] ^= (zz << d1); |
| 315 | } |
| 316 | |
| 317 | /* final round of reduction */ |
| 318 | while (j == dN) |
| 319 | { |
| 320 | |
| 321 | d0 = p[0] % BN_BITS2; |
| 322 | zz = z[dN] >> d0; |
| 323 | if (zz == 0) break; |
| 324 | d1 = BN_BITS2 - d0; |
| 325 | |
| 326 | /* clear up the top d1 bits */ |
| 327 | if (d0) |
| 328 | z[dN] = (z[dN] << d1) >> d1; |
| 329 | else |
| 330 | z[dN] = 0; |
| 331 | z[0] ^= zz; /* reduction t^0 component */ |
| 332 | |
| 333 | for (k = 1; p[k] != 0; k++) |
| 334 | { |
| 335 | BN_ULONG tmp_ulong; |
| 336 | |
| 337 | /* reducing component t^p[k]*/ |
| 338 | n = p[k] / BN_BITS2; |
| 339 | d0 = p[k] % BN_BITS2; |
| 340 | d1 = BN_BITS2 - d0; |
| 341 | z[n] ^= (zz << d0); |
| 342 | tmp_ulong = zz >> d1; |
| 343 | if (d0 && tmp_ulong) |
| 344 | z[n+1] ^= tmp_ulong; |
| 345 | } |
| 346 | |
| 347 | |
| 348 | } |
| 349 | |
| 350 | bn_correct_top(r); |
| 351 | return 1; |
| 352 | } |
| 353 | |
| 354 | /* Performs modular reduction of a by p and store result in r. r could be a. |
| 355 | * |
| 356 | * This function calls down to the BN_GF2m_mod_arr implementation; this wrapper |
| 357 | * function is only provided for convenience; for best performance, use the |
| 358 | * BN_GF2m_mod_arr function. |
| 359 | */ |
| 360 | int BN_GF2m_mod(BIGNUM *r, const BIGNUM *a, const BIGNUM *p) |
| 361 | { |
| 362 | int ret = 0; |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 363 | const int max = BN_num_bits(p) + 1; |
| 364 | int *arr=NULL; |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 365 | bn_check_top(a); |
| 366 | bn_check_top(p); |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 367 | if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) goto err; |
| 368 | ret = BN_GF2m_poly2arr(p, arr, max); |
| 369 | if (!ret || ret > max) |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 370 | { |
| 371 | BNerr(BN_F_BN_GF2M_MOD,BN_R_INVALID_LENGTH); |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 372 | goto err; |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 373 | } |
| 374 | ret = BN_GF2m_mod_arr(r, a, arr); |
| 375 | bn_check_top(r); |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 376 | err: |
| 377 | if (arr) OPENSSL_free(arr); |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 378 | return ret; |
| 379 | } |
| 380 | |
| 381 | |
| 382 | /* Compute the product of two polynomials a and b, reduce modulo p, and store |
| 383 | * the result in r. r could be a or b; a could be b. |
| 384 | */ |
| 385 | int BN_GF2m_mod_mul_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const int p[], BN_CTX *ctx) |
| 386 | { |
| 387 | int zlen, i, j, k, ret = 0; |
| 388 | BIGNUM *s; |
| 389 | BN_ULONG x1, x0, y1, y0, zz[4]; |
| 390 | |
| 391 | bn_check_top(a); |
| 392 | bn_check_top(b); |
| 393 | |
| 394 | if (a == b) |
| 395 | { |
| 396 | return BN_GF2m_mod_sqr_arr(r, a, p, ctx); |
| 397 | } |
| 398 | |
| 399 | BN_CTX_start(ctx); |
| 400 | if ((s = BN_CTX_get(ctx)) == NULL) goto err; |
| 401 | |
| 402 | zlen = a->top + b->top + 4; |
| 403 | if (!bn_wexpand(s, zlen)) goto err; |
| 404 | s->top = zlen; |
| 405 | |
| 406 | for (i = 0; i < zlen; i++) s->d[i] = 0; |
| 407 | |
| 408 | for (j = 0; j < b->top; j += 2) |
| 409 | { |
| 410 | y0 = b->d[j]; |
| 411 | y1 = ((j+1) == b->top) ? 0 : b->d[j+1]; |
| 412 | for (i = 0; i < a->top; i += 2) |
| 413 | { |
| 414 | x0 = a->d[i]; |
| 415 | x1 = ((i+1) == a->top) ? 0 : a->d[i+1]; |
| 416 | bn_GF2m_mul_2x2(zz, x1, x0, y1, y0); |
| 417 | for (k = 0; k < 4; k++) s->d[i+j+k] ^= zz[k]; |
| 418 | } |
| 419 | } |
| 420 | |
| 421 | bn_correct_top(s); |
| 422 | if (BN_GF2m_mod_arr(r, s, p)) |
| 423 | ret = 1; |
| 424 | bn_check_top(r); |
| 425 | |
| 426 | err: |
| 427 | BN_CTX_end(ctx); |
| 428 | return ret; |
| 429 | } |
| 430 | |
| 431 | /* Compute the product of two polynomials a and b, reduce modulo p, and store |
| 432 | * the result in r. r could be a or b; a could equal b. |
| 433 | * |
| 434 | * This function calls down to the BN_GF2m_mod_mul_arr implementation; this wrapper |
| 435 | * function is only provided for convenience; for best performance, use the |
| 436 | * BN_GF2m_mod_mul_arr function. |
| 437 | */ |
| 438 | int BN_GF2m_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx) |
| 439 | { |
| 440 | int ret = 0; |
| 441 | const int max = BN_num_bits(p) + 1; |
| 442 | int *arr=NULL; |
| 443 | bn_check_top(a); |
| 444 | bn_check_top(b); |
| 445 | bn_check_top(p); |
| 446 | if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) goto err; |
| 447 | ret = BN_GF2m_poly2arr(p, arr, max); |
| 448 | if (!ret || ret > max) |
| 449 | { |
| 450 | BNerr(BN_F_BN_GF2M_MOD_MUL,BN_R_INVALID_LENGTH); |
| 451 | goto err; |
| 452 | } |
| 453 | ret = BN_GF2m_mod_mul_arr(r, a, b, arr, ctx); |
| 454 | bn_check_top(r); |
| 455 | err: |
| 456 | if (arr) OPENSSL_free(arr); |
| 457 | return ret; |
| 458 | } |
| 459 | |
| 460 | |
| 461 | /* Square a, reduce the result mod p, and store it in a. r could be a. */ |
| 462 | int BN_GF2m_mod_sqr_arr(BIGNUM *r, const BIGNUM *a, const int p[], BN_CTX *ctx) |
| 463 | { |
| 464 | int i, ret = 0; |
| 465 | BIGNUM *s; |
| 466 | |
| 467 | bn_check_top(a); |
| 468 | BN_CTX_start(ctx); |
| 469 | if ((s = BN_CTX_get(ctx)) == NULL) return 0; |
| 470 | if (!bn_wexpand(s, 2 * a->top)) goto err; |
| 471 | |
| 472 | for (i = a->top - 1; i >= 0; i--) |
| 473 | { |
| 474 | s->d[2*i+1] = SQR1(a->d[i]); |
| 475 | s->d[2*i ] = SQR0(a->d[i]); |
| 476 | } |
| 477 | |
| 478 | s->top = 2 * a->top; |
| 479 | bn_correct_top(s); |
| 480 | if (!BN_GF2m_mod_arr(r, s, p)) goto err; |
| 481 | bn_check_top(r); |
| 482 | ret = 1; |
| 483 | err: |
| 484 | BN_CTX_end(ctx); |
| 485 | return ret; |
| 486 | } |
| 487 | |
| 488 | /* Square a, reduce the result mod p, and store it in a. r could be a. |
| 489 | * |
| 490 | * This function calls down to the BN_GF2m_mod_sqr_arr implementation; this wrapper |
| 491 | * function is only provided for convenience; for best performance, use the |
| 492 | * BN_GF2m_mod_sqr_arr function. |
| 493 | */ |
| 494 | int BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) |
| 495 | { |
| 496 | int ret = 0; |
| 497 | const int max = BN_num_bits(p) + 1; |
| 498 | int *arr=NULL; |
| 499 | |
| 500 | bn_check_top(a); |
| 501 | bn_check_top(p); |
| 502 | if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) goto err; |
| 503 | ret = BN_GF2m_poly2arr(p, arr, max); |
| 504 | if (!ret || ret > max) |
| 505 | { |
| 506 | BNerr(BN_F_BN_GF2M_MOD_SQR,BN_R_INVALID_LENGTH); |
| 507 | goto err; |
| 508 | } |
| 509 | ret = BN_GF2m_mod_sqr_arr(r, a, arr, ctx); |
| 510 | bn_check_top(r); |
| 511 | err: |
| 512 | if (arr) OPENSSL_free(arr); |
| 513 | return ret; |
| 514 | } |
| 515 | |
| 516 | |
| 517 | /* Invert a, reduce modulo p, and store the result in r. r could be a. |
| 518 | * Uses Modified Almost Inverse Algorithm (Algorithm 10) from |
| 519 | * Hankerson, D., Hernandez, J.L., and Menezes, A. "Software Implementation |
| 520 | * of Elliptic Curve Cryptography Over Binary Fields". |
| 521 | */ |
| 522 | int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) |
| 523 | { |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 524 | BIGNUM *b, *c, *u, *v, *tmp; |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 525 | int ret = 0; |
| 526 | |
| 527 | bn_check_top(a); |
| 528 | bn_check_top(p); |
| 529 | |
| 530 | BN_CTX_start(ctx); |
| 531 | |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 532 | b = BN_CTX_get(ctx); |
| 533 | c = BN_CTX_get(ctx); |
| 534 | u = BN_CTX_get(ctx); |
| 535 | v = BN_CTX_get(ctx); |
| 536 | if (v == NULL) goto err; |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 537 | |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 538 | if (!BN_one(b)) goto err; |
Alexandre Savard | 7541067 | 2012-08-08 09:50:01 -0400 | [diff] [blame] | 539 | if (!BN_GF2m_mod(u, a, p)) goto err; |
| 540 | if (!BN_copy(v, p)) goto err; |
| 541 | |
| 542 | if (BN_is_zero(u)) goto err; |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 543 | |
| 544 | while (1) |
| 545 | { |
| 546 | while (!BN_is_odd(u)) |
| 547 | { |
| 548 | if (BN_is_zero(u)) goto err; |
| 549 | if (!BN_rshift1(u, u)) goto err; |
| 550 | if (BN_is_odd(b)) |
| 551 | { |
| 552 | if (!BN_GF2m_add(b, b, p)) goto err; |
| 553 | } |
| 554 | if (!BN_rshift1(b, b)) goto err; |
| 555 | } |
| 556 | |
| 557 | if (BN_abs_is_word(u, 1)) break; |
| 558 | |
| 559 | if (BN_num_bits(u) < BN_num_bits(v)) |
| 560 | { |
| 561 | tmp = u; u = v; v = tmp; |
| 562 | tmp = b; b = c; c = tmp; |
| 563 | } |
| 564 | |
| 565 | if (!BN_GF2m_add(u, u, v)) goto err; |
| 566 | if (!BN_GF2m_add(b, b, c)) goto err; |
| 567 | } |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 568 | |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 569 | |
| 570 | if (!BN_copy(r, b)) goto err; |
| 571 | bn_check_top(r); |
| 572 | ret = 1; |
| 573 | |
| 574 | err: |
Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 575 | BN_CTX_end(ctx); |
| 576 | return ret; |
| 577 | } |
| 578 | |
| 579 | /* Invert xx, reduce modulo p, and store the result in r. r could be xx. |
| 580 | * |
| 581 | * This function calls down to the BN_GF2m_mod_inv implementation; this wrapper |
| 582 | * function is only provided for convenience; for best performance, use the |
| 583 | * BN_GF2m_mod_inv function. |
| 584 | */ |
| 585 | int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const int p[], BN_CTX *ctx) |
| 586 | { |
| 587 | BIGNUM *field; |
| 588 | int ret = 0; |
| 589 | |
| 590 | bn_check_top(xx); |
| 591 | BN_CTX_start(ctx); |
| 592 | if ((field = BN_CTX_get(ctx)) == NULL) goto err; |
| 593 | if (!BN_GF2m_arr2poly(p, field)) goto err; |
| 594 | |
| 595 | ret = BN_GF2m_mod_inv(r, xx, field, ctx); |
| 596 | bn_check_top(r); |
| 597 | |
| 598 | err: |
| 599 | BN_CTX_end(ctx); |
| 600 | return ret; |
| 601 | } |
| 602 | |
| 603 | |
| 604 | #ifndef OPENSSL_SUN_GF2M_DIV |
| 605 | /* Divide y by x, reduce modulo p, and store the result in r. r could be x |
| 606 | * or y, x could equal y. |
| 607 | */ |
| 608 | int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, const BIGNUM *p, BN_CTX *ctx) |
| 609 | { |
| 610 | BIGNUM *xinv = NULL; |
| 611 | int ret = 0; |
| 612 | |
| 613 | bn_check_top(y); |
| 614 | bn_check_top(x); |
| 615 | bn_check_top(p); |
| 616 | |
| 617 | BN_CTX_start(ctx); |
| 618 | xinv = BN_CTX_get(ctx); |
| 619 | if (xinv == NULL) goto err; |
| 620 | |
| 621 | if (!BN_GF2m_mod_inv(xinv, x, p, ctx)) goto err; |
| 622 | if (!BN_GF2m_mod_mul(r, y, xinv, p, ctx)) goto err; |
| 623 | bn_check_top(r); |
| 624 | ret = 1; |
| 625 | |
| 626 | err: |
| 627 | BN_CTX_end(ctx); |
| 628 | return ret; |
| 629 | } |
| 630 | #else |
| 631 | /* Divide y by x, reduce modulo p, and store the result in r. r could be x |
| 632 | * or y, x could equal y. |
| 633 | * Uses algorithm Modular_Division_GF(2^m) from |
| 634 | * Chang-Shantz, S. "From Euclid's GCD to Montgomery Multiplication to |
| 635 | * the Great Divide". |
| 636 | */ |
| 637 | int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, const BIGNUM *p, BN_CTX *ctx) |
| 638 | { |
| 639 | BIGNUM *a, *b, *u, *v; |
| 640 | int ret = 0; |
| 641 | |
| 642 | bn_check_top(y); |
| 643 | bn_check_top(x); |
| 644 | bn_check_top(p); |
| 645 | |
| 646 | BN_CTX_start(ctx); |
| 647 | |
| 648 | a = BN_CTX_get(ctx); |
| 649 | b = BN_CTX_get(ctx); |
| 650 | u = BN_CTX_get(ctx); |
| 651 | v = BN_CTX_get(ctx); |
| 652 | if (v == NULL) goto err; |
| 653 | |
| 654 | /* reduce x and y mod p */ |
| 655 | if (!BN_GF2m_mod(u, y, p)) goto err; |
| 656 | if (!BN_GF2m_mod(a, x, p)) goto err; |
| 657 | if (!BN_copy(b, p)) goto err; |
| 658 | |
| 659 | while (!BN_is_odd(a)) |
| 660 | { |
| 661 | if (!BN_rshift1(a, a)) goto err; |
| 662 | if (BN_is_odd(u)) if (!BN_GF2m_add(u, u, p)) goto err; |
| 663 | if (!BN_rshift1(u, u)) goto err; |
| 664 | } |
| 665 | |
| 666 | do |
| 667 | { |
| 668 | if (BN_GF2m_cmp(b, a) > 0) |
| 669 | { |
| 670 | if (!BN_GF2m_add(b, b, a)) goto err; |
| 671 | if (!BN_GF2m_add(v, v, u)) goto err; |
| 672 | do |
| 673 | { |
| 674 | if (!BN_rshift1(b, b)) goto err; |
| 675 | if (BN_is_odd(v)) if (!BN_GF2m_add(v, v, p)) goto err; |
| 676 | if (!BN_rshift1(v, v)) goto err; |
| 677 | } while (!BN_is_odd(b)); |
| 678 | } |
| 679 | else if (BN_abs_is_word(a, 1)) |
| 680 | break; |
| 681 | else |
| 682 | { |
| 683 | if (!BN_GF2m_add(a, a, b)) goto err; |
| 684 | if (!BN_GF2m_add(u, u, v)) goto err; |
| 685 | do |
| 686 | { |
| 687 | if (!BN_rshift1(a, a)) goto err; |
| 688 | if (BN_is_odd(u)) if (!BN_GF2m_add(u, u, p)) goto err; |
| 689 | if (!BN_rshift1(u, u)) goto err; |
| 690 | } while (!BN_is_odd(a)); |
| 691 | } |
| 692 | } while (1); |
| 693 | |
| 694 | if (!BN_copy(r, u)) goto err; |
| 695 | bn_check_top(r); |
| 696 | ret = 1; |
| 697 | |
| 698 | err: |
| 699 | BN_CTX_end(ctx); |
| 700 | return ret; |
| 701 | } |
| 702 | #endif |
| 703 | |
| 704 | /* Divide yy by xx, reduce modulo p, and store the result in r. r could be xx |
| 705 | * or yy, xx could equal yy. |
| 706 | * |
| 707 | * This function calls down to the BN_GF2m_mod_div implementation; this wrapper |
| 708 | * function is only provided for convenience; for best performance, use the |
| 709 | * BN_GF2m_mod_div function. |
| 710 | */ |
| 711 | int BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *yy, const BIGNUM *xx, const int p[], BN_CTX *ctx) |
| 712 | { |
| 713 | BIGNUM *field; |
| 714 | int ret = 0; |
| 715 | |
| 716 | bn_check_top(yy); |
| 717 | bn_check_top(xx); |
| 718 | |
| 719 | BN_CTX_start(ctx); |
| 720 | if ((field = BN_CTX_get(ctx)) == NULL) goto err; |
| 721 | if (!BN_GF2m_arr2poly(p, field)) goto err; |
| 722 | |
| 723 | ret = BN_GF2m_mod_div(r, yy, xx, field, ctx); |
| 724 | bn_check_top(r); |
| 725 | |
| 726 | err: |
| 727 | BN_CTX_end(ctx); |
| 728 | return ret; |
| 729 | } |
| 730 | |
| 731 | |
| 732 | /* Compute the bth power of a, reduce modulo p, and store |
| 733 | * the result in r. r could be a. |
| 734 | * Uses simple square-and-multiply algorithm A.5.1 from IEEE P1363. |
| 735 | */ |
| 736 | int BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const int p[], BN_CTX *ctx) |
| 737 | { |
| 738 | int ret = 0, i, n; |
| 739 | BIGNUM *u; |
| 740 | |
| 741 | bn_check_top(a); |
| 742 | bn_check_top(b); |
| 743 | |
| 744 | if (BN_is_zero(b)) |
| 745 | return(BN_one(r)); |
| 746 | |
| 747 | if (BN_abs_is_word(b, 1)) |
| 748 | return (BN_copy(r, a) != NULL); |
| 749 | |
| 750 | BN_CTX_start(ctx); |
| 751 | if ((u = BN_CTX_get(ctx)) == NULL) goto err; |
| 752 | |
| 753 | if (!BN_GF2m_mod_arr(u, a, p)) goto err; |
| 754 | |
| 755 | n = BN_num_bits(b) - 1; |
| 756 | for (i = n - 1; i >= 0; i--) |
| 757 | { |
| 758 | if (!BN_GF2m_mod_sqr_arr(u, u, p, ctx)) goto err; |
| 759 | if (BN_is_bit_set(b, i)) |
| 760 | { |
| 761 | if (!BN_GF2m_mod_mul_arr(u, u, a, p, ctx)) goto err; |
| 762 | } |
| 763 | } |
| 764 | if (!BN_copy(r, u)) goto err; |
| 765 | bn_check_top(r); |
| 766 | ret = 1; |
| 767 | err: |
| 768 | BN_CTX_end(ctx); |
| 769 | return ret; |
| 770 | } |
| 771 | |
| 772 | /* Compute the bth power of a, reduce modulo p, and store |
| 773 | * the result in r. r could be a. |
| 774 | * |
| 775 | * This function calls down to the BN_GF2m_mod_exp_arr implementation; this wrapper |
| 776 | * function is only provided for convenience; for best performance, use the |
| 777 | * BN_GF2m_mod_exp_arr function. |
| 778 | */ |
| 779 | int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *p, BN_CTX *ctx) |
| 780 | { |
| 781 | int ret = 0; |
| 782 | const int max = BN_num_bits(p) + 1; |
| 783 | int *arr=NULL; |
| 784 | bn_check_top(a); |
| 785 | bn_check_top(b); |
| 786 | bn_check_top(p); |
| 787 | if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) goto err; |
| 788 | ret = BN_GF2m_poly2arr(p, arr, max); |
| 789 | if (!ret || ret > max) |
| 790 | { |
| 791 | BNerr(BN_F_BN_GF2M_MOD_EXP,BN_R_INVALID_LENGTH); |
| 792 | goto err; |
| 793 | } |
| 794 | ret = BN_GF2m_mod_exp_arr(r, a, b, arr, ctx); |
| 795 | bn_check_top(r); |
| 796 | err: |
| 797 | if (arr) OPENSSL_free(arr); |
| 798 | return ret; |
| 799 | } |
| 800 | |
| 801 | /* Compute the square root of a, reduce modulo p, and store |
| 802 | * the result in r. r could be a. |
| 803 | * Uses exponentiation as in algorithm A.4.1 from IEEE P1363. |
| 804 | */ |
| 805 | int BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const int p[], BN_CTX *ctx) |
| 806 | { |
| 807 | int ret = 0; |
| 808 | BIGNUM *u; |
| 809 | |
| 810 | bn_check_top(a); |
| 811 | |
| 812 | if (!p[0]) |
| 813 | { |
| 814 | /* reduction mod 1 => return 0 */ |
| 815 | BN_zero(r); |
| 816 | return 1; |
| 817 | } |
| 818 | |
| 819 | BN_CTX_start(ctx); |
| 820 | if ((u = BN_CTX_get(ctx)) == NULL) goto err; |
| 821 | |
| 822 | if (!BN_set_bit(u, p[0] - 1)) goto err; |
| 823 | ret = BN_GF2m_mod_exp_arr(r, a, u, p, ctx); |
| 824 | bn_check_top(r); |
| 825 | |
| 826 | err: |
| 827 | BN_CTX_end(ctx); |
| 828 | return ret; |
| 829 | } |
| 830 | |
| 831 | /* Compute the square root of a, reduce modulo p, and store |
| 832 | * the result in r. r could be a. |
| 833 | * |
| 834 | * This function calls down to the BN_GF2m_mod_sqrt_arr implementation; this wrapper |
| 835 | * function is only provided for convenience; for best performance, use the |
| 836 | * BN_GF2m_mod_sqrt_arr function. |
| 837 | */ |
| 838 | int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) |
| 839 | { |
| 840 | int ret = 0; |
| 841 | const int max = BN_num_bits(p) + 1; |
| 842 | int *arr=NULL; |
| 843 | bn_check_top(a); |
| 844 | bn_check_top(p); |
| 845 | if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) goto err; |
| 846 | ret = BN_GF2m_poly2arr(p, arr, max); |
| 847 | if (!ret || ret > max) |
| 848 | { |
| 849 | BNerr(BN_F_BN_GF2M_MOD_SQRT,BN_R_INVALID_LENGTH); |
| 850 | goto err; |
| 851 | } |
| 852 | ret = BN_GF2m_mod_sqrt_arr(r, a, arr, ctx); |
| 853 | bn_check_top(r); |
| 854 | err: |
| 855 | if (arr) OPENSSL_free(arr); |
| 856 | return ret; |
| 857 | } |
| 858 | |
| 859 | /* Find r such that r^2 + r = a mod p. r could be a. If no r exists returns 0. |
| 860 | * Uses algorithms A.4.7 and A.4.6 from IEEE P1363. |
| 861 | */ |
| 862 | int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a_, const int p[], BN_CTX *ctx) |
| 863 | { |
| 864 | int ret = 0, count = 0, j; |
| 865 | BIGNUM *a, *z, *rho, *w, *w2, *tmp; |
| 866 | |
| 867 | bn_check_top(a_); |
| 868 | |
| 869 | if (!p[0]) |
| 870 | { |
| 871 | /* reduction mod 1 => return 0 */ |
| 872 | BN_zero(r); |
| 873 | return 1; |
| 874 | } |
| 875 | |
| 876 | BN_CTX_start(ctx); |
| 877 | a = BN_CTX_get(ctx); |
| 878 | z = BN_CTX_get(ctx); |
| 879 | w = BN_CTX_get(ctx); |
| 880 | if (w == NULL) goto err; |
| 881 | |
| 882 | if (!BN_GF2m_mod_arr(a, a_, p)) goto err; |
| 883 | |
| 884 | if (BN_is_zero(a)) |
| 885 | { |
| 886 | BN_zero(r); |
| 887 | ret = 1; |
| 888 | goto err; |
| 889 | } |
| 890 | |
| 891 | if (p[0] & 0x1) /* m is odd */ |
| 892 | { |
| 893 | /* compute half-trace of a */ |
| 894 | if (!BN_copy(z, a)) goto err; |
| 895 | for (j = 1; j <= (p[0] - 1) / 2; j++) |
| 896 | { |
| 897 | if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) goto err; |
| 898 | if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) goto err; |
| 899 | if (!BN_GF2m_add(z, z, a)) goto err; |
| 900 | } |
| 901 | |
| 902 | } |
| 903 | else /* m is even */ |
| 904 | { |
| 905 | rho = BN_CTX_get(ctx); |
| 906 | w2 = BN_CTX_get(ctx); |
| 907 | tmp = BN_CTX_get(ctx); |
| 908 | if (tmp == NULL) goto err; |
| 909 | do |
| 910 | { |
| 911 | if (!BN_rand(rho, p[0], 0, 0)) goto err; |
| 912 | if (!BN_GF2m_mod_arr(rho, rho, p)) goto err; |
| 913 | BN_zero(z); |
| 914 | if (!BN_copy(w, rho)) goto err; |
| 915 | for (j = 1; j <= p[0] - 1; j++) |
| 916 | { |
| 917 | if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) goto err; |
| 918 | if (!BN_GF2m_mod_sqr_arr(w2, w, p, ctx)) goto err; |
| 919 | if (!BN_GF2m_mod_mul_arr(tmp, w2, a, p, ctx)) goto err; |
| 920 | if (!BN_GF2m_add(z, z, tmp)) goto err; |
| 921 | if (!BN_GF2m_add(w, w2, rho)) goto err; |
| 922 | } |
| 923 | count++; |
| 924 | } while (BN_is_zero(w) && (count < MAX_ITERATIONS)); |
| 925 | if (BN_is_zero(w)) |
| 926 | { |
| 927 | BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR,BN_R_TOO_MANY_ITERATIONS); |
| 928 | goto err; |
| 929 | } |
| 930 | } |
| 931 | |
| 932 | if (!BN_GF2m_mod_sqr_arr(w, z, p, ctx)) goto err; |
| 933 | if (!BN_GF2m_add(w, z, w)) goto err; |
| 934 | if (BN_GF2m_cmp(w, a)) |
| 935 | { |
| 936 | BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR, BN_R_NO_SOLUTION); |
| 937 | goto err; |
| 938 | } |
| 939 | |
| 940 | if (!BN_copy(r, z)) goto err; |
| 941 | bn_check_top(r); |
| 942 | |
| 943 | ret = 1; |
| 944 | |
| 945 | err: |
| 946 | BN_CTX_end(ctx); |
| 947 | return ret; |
| 948 | } |
| 949 | |
| 950 | /* Find r such that r^2 + r = a mod p. r could be a. If no r exists returns 0. |
| 951 | * |
| 952 | * This function calls down to the BN_GF2m_mod_solve_quad_arr implementation; this wrapper |
| 953 | * function is only provided for convenience; for best performance, use the |
| 954 | * BN_GF2m_mod_solve_quad_arr function. |
| 955 | */ |
| 956 | int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) |
| 957 | { |
| 958 | int ret = 0; |
| 959 | const int max = BN_num_bits(p) + 1; |
| 960 | int *arr=NULL; |
| 961 | bn_check_top(a); |
| 962 | bn_check_top(p); |
| 963 | if ((arr = (int *)OPENSSL_malloc(sizeof(int) * |
| 964 | max)) == NULL) goto err; |
| 965 | ret = BN_GF2m_poly2arr(p, arr, max); |
| 966 | if (!ret || ret > max) |
| 967 | { |
| 968 | BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD,BN_R_INVALID_LENGTH); |
| 969 | goto err; |
| 970 | } |
| 971 | ret = BN_GF2m_mod_solve_quad_arr(r, a, arr, ctx); |
| 972 | bn_check_top(r); |
| 973 | err: |
| 974 | if (arr) OPENSSL_free(arr); |
| 975 | return ret; |
| 976 | } |
| 977 | |
| 978 | /* Convert the bit-string representation of a polynomial |
| 979 | * ( \sum_{i=0}^n a_i * x^i) into an array of integers corresponding |
| 980 | * to the bits with non-zero coefficient. Array is terminated with -1. |
| 981 | * Up to max elements of the array will be filled. Return value is total |
| 982 | * number of array elements that would be filled if array was large enough. |
| 983 | */ |
| 984 | int BN_GF2m_poly2arr(const BIGNUM *a, int p[], int max) |
| 985 | { |
| 986 | int i, j, k = 0; |
| 987 | BN_ULONG mask; |
| 988 | |
| 989 | if (BN_is_zero(a)) |
| 990 | return 0; |
| 991 | |
| 992 | for (i = a->top - 1; i >= 0; i--) |
| 993 | { |
| 994 | if (!a->d[i]) |
| 995 | /* skip word if a->d[i] == 0 */ |
| 996 | continue; |
| 997 | mask = BN_TBIT; |
| 998 | for (j = BN_BITS2 - 1; j >= 0; j--) |
| 999 | { |
| 1000 | if (a->d[i] & mask) |
| 1001 | { |
| 1002 | if (k < max) p[k] = BN_BITS2 * i + j; |
| 1003 | k++; |
| 1004 | } |
| 1005 | mask >>= 1; |
| 1006 | } |
| 1007 | } |
| 1008 | |
| 1009 | if (k < max) { |
| 1010 | p[k] = -1; |
| 1011 | k++; |
| 1012 | } |
| 1013 | |
| 1014 | return k; |
| 1015 | } |
| 1016 | |
| 1017 | /* Convert the coefficient array representation of a polynomial to a |
| 1018 | * bit-string. The array must be terminated by -1. |
| 1019 | */ |
| 1020 | int BN_GF2m_arr2poly(const int p[], BIGNUM *a) |
| 1021 | { |
| 1022 | int i; |
| 1023 | |
| 1024 | bn_check_top(a); |
| 1025 | BN_zero(a); |
| 1026 | for (i = 0; p[i] != -1; i++) |
| 1027 | { |
| 1028 | if (BN_set_bit(a, p[i]) == 0) |
| 1029 | return 0; |
| 1030 | } |
| 1031 | bn_check_top(a); |
| 1032 | |
| 1033 | return 1; |
| 1034 | } |
| 1035 | |