13b4e3dcbSSimon L. B. Nielsen /* crypto/bn/bn_gf2m.c */ 23b4e3dcbSSimon L. B. Nielsen /* ==================================================================== 33b4e3dcbSSimon L. B. Nielsen * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 43b4e3dcbSSimon L. B. Nielsen * 53b4e3dcbSSimon L. B. Nielsen * The Elliptic Curve Public-Key Crypto Library (ECC Code) included 63b4e3dcbSSimon L. B. Nielsen * herein is developed by SUN MICROSYSTEMS, INC., and is contributed 73b4e3dcbSSimon L. B. Nielsen * to the OpenSSL project. 83b4e3dcbSSimon L. B. Nielsen * 93b4e3dcbSSimon L. B. Nielsen * The ECC Code is licensed pursuant to the OpenSSL open source 103b4e3dcbSSimon L. B. Nielsen * license provided below. 113b4e3dcbSSimon L. B. Nielsen * 123b4e3dcbSSimon L. B. Nielsen * In addition, Sun covenants to all licensees who provide a reciprocal 133b4e3dcbSSimon L. B. Nielsen * covenant with respect to their own patents if any, not to sue under 143b4e3dcbSSimon L. B. Nielsen * current and future patent claims necessarily infringed by the making, 153b4e3dcbSSimon L. B. Nielsen * using, practicing, selling, offering for sale and/or otherwise 163b4e3dcbSSimon L. B. Nielsen * disposing of the ECC Code as delivered hereunder (or portions thereof), 173b4e3dcbSSimon L. B. Nielsen * provided that such covenant shall not apply: 183b4e3dcbSSimon L. B. Nielsen * 1) for code that a licensee deletes from the ECC Code; 193b4e3dcbSSimon L. B. Nielsen * 2) separates from the ECC Code; or 203b4e3dcbSSimon L. B. Nielsen * 3) for infringements caused by: 213b4e3dcbSSimon L. B. Nielsen * i) the modification of the ECC Code or 223b4e3dcbSSimon L. B. Nielsen * ii) the combination of the ECC Code with other software or 233b4e3dcbSSimon L. B. Nielsen * devices where such combination causes the infringement. 243b4e3dcbSSimon L. B. Nielsen * 253b4e3dcbSSimon L. B. Nielsen * The software is originally written by Sheueling Chang Shantz and 263b4e3dcbSSimon L. B. Nielsen * Douglas Stebila of Sun Microsystems Laboratories. 273b4e3dcbSSimon L. B. Nielsen * 283b4e3dcbSSimon L. B. Nielsen */ 293b4e3dcbSSimon L. B. Nielsen 306f9291ceSJung-uk Kim /* 316f9291ceSJung-uk Kim * NOTE: This file is licensed pursuant to the OpenSSL license below and may 326f9291ceSJung-uk Kim * be modified; but after modifications, the above covenant may no longer 336f9291ceSJung-uk Kim * apply! In such cases, the corresponding paragraph ["In addition, Sun 346f9291ceSJung-uk Kim * covenants ... causes the infringement."] and this note can be edited out; 356f9291ceSJung-uk Kim * but please keep the Sun copyright notice and attribution. 366f9291ceSJung-uk Kim */ 373b4e3dcbSSimon L. B. Nielsen 383b4e3dcbSSimon L. B. Nielsen /* ==================================================================== 393b4e3dcbSSimon L. B. Nielsen * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved. 403b4e3dcbSSimon L. B. Nielsen * 413b4e3dcbSSimon L. B. Nielsen * Redistribution and use in source and binary forms, with or without 423b4e3dcbSSimon L. B. Nielsen * modification, are permitted provided that the following conditions 433b4e3dcbSSimon L. B. Nielsen * are met: 443b4e3dcbSSimon L. B. Nielsen * 453b4e3dcbSSimon L. B. Nielsen * 1. Redistributions of source code must retain the above copyright 463b4e3dcbSSimon L. B. Nielsen * notice, this list of conditions and the following disclaimer. 473b4e3dcbSSimon L. B. Nielsen * 483b4e3dcbSSimon L. B. Nielsen * 2. Redistributions in binary form must reproduce the above copyright 493b4e3dcbSSimon L. B. Nielsen * notice, this list of conditions and the following disclaimer in 503b4e3dcbSSimon L. B. Nielsen * the documentation and/or other materials provided with the 513b4e3dcbSSimon L. B. Nielsen * distribution. 523b4e3dcbSSimon L. B. Nielsen * 533b4e3dcbSSimon L. B. Nielsen * 3. All advertising materials mentioning features or use of this 543b4e3dcbSSimon L. B. Nielsen * software must display the following acknowledgment: 553b4e3dcbSSimon L. B. Nielsen * "This product includes software developed by the OpenSSL Project 563b4e3dcbSSimon L. B. Nielsen * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 573b4e3dcbSSimon L. B. Nielsen * 583b4e3dcbSSimon L. B. Nielsen * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 593b4e3dcbSSimon L. B. Nielsen * endorse or promote products derived from this software without 603b4e3dcbSSimon L. B. Nielsen * prior written permission. For written permission, please contact 613b4e3dcbSSimon L. B. Nielsen * openssl-core@openssl.org. 623b4e3dcbSSimon L. B. Nielsen * 633b4e3dcbSSimon L. B. Nielsen * 5. Products derived from this software may not be called "OpenSSL" 643b4e3dcbSSimon L. B. Nielsen * nor may "OpenSSL" appear in their names without prior written 653b4e3dcbSSimon L. B. Nielsen * permission of the OpenSSL Project. 663b4e3dcbSSimon L. B. Nielsen * 673b4e3dcbSSimon L. B. Nielsen * 6. Redistributions of any form whatsoever must retain the following 683b4e3dcbSSimon L. B. Nielsen * acknowledgment: 693b4e3dcbSSimon L. B. Nielsen * "This product includes software developed by the OpenSSL Project 703b4e3dcbSSimon L. B. Nielsen * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 713b4e3dcbSSimon L. B. Nielsen * 723b4e3dcbSSimon L. B. Nielsen * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 733b4e3dcbSSimon L. B. Nielsen * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 743b4e3dcbSSimon L. B. Nielsen * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 753b4e3dcbSSimon L. B. Nielsen * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 763b4e3dcbSSimon L. B. Nielsen * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 773b4e3dcbSSimon L. B. Nielsen * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 783b4e3dcbSSimon L. B. Nielsen * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 793b4e3dcbSSimon L. B. Nielsen * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 803b4e3dcbSSimon L. B. Nielsen * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 813b4e3dcbSSimon L. B. Nielsen * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 823b4e3dcbSSimon L. B. Nielsen * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 833b4e3dcbSSimon L. B. Nielsen * OF THE POSSIBILITY OF SUCH DAMAGE. 843b4e3dcbSSimon L. B. Nielsen * ==================================================================== 853b4e3dcbSSimon L. B. Nielsen * 863b4e3dcbSSimon L. B. Nielsen * This product includes cryptographic software written by Eric Young 873b4e3dcbSSimon L. B. Nielsen * (eay@cryptsoft.com). This product includes software written by Tim 883b4e3dcbSSimon L. B. Nielsen * Hudson (tjh@cryptsoft.com). 893b4e3dcbSSimon L. B. Nielsen * 903b4e3dcbSSimon L. B. Nielsen */ 913b4e3dcbSSimon L. B. Nielsen 923b4e3dcbSSimon L. B. Nielsen #include <assert.h> 933b4e3dcbSSimon L. B. Nielsen #include <limits.h> 943b4e3dcbSSimon L. B. Nielsen #include <stdio.h> 953b4e3dcbSSimon L. B. Nielsen #include "cryptlib.h" 963b4e3dcbSSimon L. B. Nielsen #include "bn_lcl.h" 973b4e3dcbSSimon L. B. Nielsen 981f13597dSJung-uk Kim #ifndef OPENSSL_NO_EC2M 991f13597dSJung-uk Kim 1006f9291ceSJung-uk Kim /* 1016f9291ceSJung-uk Kim * Maximum number of iterations before BN_GF2m_mod_solve_quad_arr should 1026f9291ceSJung-uk Kim * fail. 1036f9291ceSJung-uk Kim */ 1043b4e3dcbSSimon L. B. Nielsen # define MAX_ITERATIONS 50 1053b4e3dcbSSimon L. B. Nielsen 1066f9291ceSJung-uk Kim static const BN_ULONG SQR_tb[16] = { 0, 1, 4, 5, 16, 17, 20, 21, 1076f9291ceSJung-uk Kim 64, 65, 68, 69, 80, 81, 84, 85 1086f9291ceSJung-uk Kim }; 1096f9291ceSJung-uk Kim 1103b4e3dcbSSimon L. B. Nielsen /* Platform-specific macros to accelerate squaring. */ 1113b4e3dcbSSimon L. B. Nielsen # if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) 1123b4e3dcbSSimon L. B. Nielsen # define SQR1(w) \ 1133b4e3dcbSSimon L. B. Nielsen SQR_tb[(w) >> 60 & 0xF] << 56 | SQR_tb[(w) >> 56 & 0xF] << 48 | \ 1143b4e3dcbSSimon L. B. Nielsen SQR_tb[(w) >> 52 & 0xF] << 40 | SQR_tb[(w) >> 48 & 0xF] << 32 | \ 1153b4e3dcbSSimon L. B. Nielsen SQR_tb[(w) >> 44 & 0xF] << 24 | SQR_tb[(w) >> 40 & 0xF] << 16 | \ 1163b4e3dcbSSimon L. B. Nielsen SQR_tb[(w) >> 36 & 0xF] << 8 | SQR_tb[(w) >> 32 & 0xF] 1173b4e3dcbSSimon L. B. Nielsen # define SQR0(w) \ 1183b4e3dcbSSimon L. B. Nielsen SQR_tb[(w) >> 28 & 0xF] << 56 | SQR_tb[(w) >> 24 & 0xF] << 48 | \ 1193b4e3dcbSSimon L. B. Nielsen SQR_tb[(w) >> 20 & 0xF] << 40 | SQR_tb[(w) >> 16 & 0xF] << 32 | \ 1203b4e3dcbSSimon L. B. Nielsen SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >> 8 & 0xF] << 16 | \ 1213b4e3dcbSSimon L. B. Nielsen SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF] 1223b4e3dcbSSimon L. B. Nielsen # endif 1233b4e3dcbSSimon L. B. Nielsen # ifdef THIRTY_TWO_BIT 1243b4e3dcbSSimon L. B. Nielsen # define SQR1(w) \ 1253b4e3dcbSSimon L. B. Nielsen SQR_tb[(w) >> 28 & 0xF] << 24 | SQR_tb[(w) >> 24 & 0xF] << 16 | \ 1263b4e3dcbSSimon L. B. Nielsen SQR_tb[(w) >> 20 & 0xF] << 8 | SQR_tb[(w) >> 16 & 0xF] 1273b4e3dcbSSimon L. B. Nielsen # define SQR0(w) \ 1283b4e3dcbSSimon L. B. Nielsen SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >> 8 & 0xF] << 16 | \ 1293b4e3dcbSSimon L. B. Nielsen SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF] 1303b4e3dcbSSimon L. B. Nielsen # endif 1313b4e3dcbSSimon L. B. Nielsen 1321f13597dSJung-uk Kim # if !defined(OPENSSL_BN_ASM_GF2m) 1336f9291ceSJung-uk Kim /* 1346f9291ceSJung-uk Kim * Product of two polynomials a, b each with degree < BN_BITS2 - 1, result is 1356f9291ceSJung-uk Kim * a polynomial r with degree < 2 * BN_BITS - 1 The caller MUST ensure that 1366f9291ceSJung-uk Kim * the variables have the right amount of space allocated. 1373b4e3dcbSSimon L. B. Nielsen */ 1383b4e3dcbSSimon L. B. Nielsen # ifdef THIRTY_TWO_BIT 1396f9291ceSJung-uk Kim static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, 1406f9291ceSJung-uk Kim const BN_ULONG b) 1413b4e3dcbSSimon L. B. Nielsen { 1423b4e3dcbSSimon L. B. Nielsen register BN_ULONG h, l, s; 1433b4e3dcbSSimon L. B. Nielsen BN_ULONG tab[8], top2b = a >> 30; 1443b4e3dcbSSimon L. B. Nielsen register BN_ULONG a1, a2, a4; 1453b4e3dcbSSimon L. B. Nielsen 1466f9291ceSJung-uk Kim a1 = a & (0x3FFFFFFF); 1476f9291ceSJung-uk Kim a2 = a1 << 1; 1486f9291ceSJung-uk Kim a4 = a2 << 1; 1493b4e3dcbSSimon L. B. Nielsen 1506f9291ceSJung-uk Kim tab[0] = 0; 1516f9291ceSJung-uk Kim tab[1] = a1; 1526f9291ceSJung-uk Kim tab[2] = a2; 1536f9291ceSJung-uk Kim tab[3] = a1 ^ a2; 1546f9291ceSJung-uk Kim tab[4] = a4; 1556f9291ceSJung-uk Kim tab[5] = a1 ^ a4; 1566f9291ceSJung-uk Kim tab[6] = a2 ^ a4; 1576f9291ceSJung-uk Kim tab[7] = a1 ^ a2 ^ a4; 1583b4e3dcbSSimon L. B. Nielsen 1596f9291ceSJung-uk Kim s = tab[b & 0x7]; 1606f9291ceSJung-uk Kim l = s; 1616f9291ceSJung-uk Kim s = tab[b >> 3 & 0x7]; 1626f9291ceSJung-uk Kim l ^= s << 3; 1636f9291ceSJung-uk Kim h = s >> 29; 1646f9291ceSJung-uk Kim s = tab[b >> 6 & 0x7]; 1656f9291ceSJung-uk Kim l ^= s << 6; 1666f9291ceSJung-uk Kim h ^= s >> 26; 1676f9291ceSJung-uk Kim s = tab[b >> 9 & 0x7]; 1686f9291ceSJung-uk Kim l ^= s << 9; 1696f9291ceSJung-uk Kim h ^= s >> 23; 1706f9291ceSJung-uk Kim s = tab[b >> 12 & 0x7]; 1716f9291ceSJung-uk Kim l ^= s << 12; 1726f9291ceSJung-uk Kim h ^= s >> 20; 1736f9291ceSJung-uk Kim s = tab[b >> 15 & 0x7]; 1746f9291ceSJung-uk Kim l ^= s << 15; 1756f9291ceSJung-uk Kim h ^= s >> 17; 1766f9291ceSJung-uk Kim s = tab[b >> 18 & 0x7]; 1776f9291ceSJung-uk Kim l ^= s << 18; 1786f9291ceSJung-uk Kim h ^= s >> 14; 1796f9291ceSJung-uk Kim s = tab[b >> 21 & 0x7]; 1806f9291ceSJung-uk Kim l ^= s << 21; 1816f9291ceSJung-uk Kim h ^= s >> 11; 1826f9291ceSJung-uk Kim s = tab[b >> 24 & 0x7]; 1836f9291ceSJung-uk Kim l ^= s << 24; 1846f9291ceSJung-uk Kim h ^= s >> 8; 1856f9291ceSJung-uk Kim s = tab[b >> 27 & 0x7]; 1866f9291ceSJung-uk Kim l ^= s << 27; 1876f9291ceSJung-uk Kim h ^= s >> 5; 1886f9291ceSJung-uk Kim s = tab[b >> 30]; 1896f9291ceSJung-uk Kim l ^= s << 30; 1906f9291ceSJung-uk Kim h ^= s >> 2; 1913b4e3dcbSSimon L. B. Nielsen 1923b4e3dcbSSimon L. B. Nielsen /* compensate for the top two bits of a */ 1933b4e3dcbSSimon L. B. Nielsen 1946f9291ceSJung-uk Kim if (top2b & 01) { 1956f9291ceSJung-uk Kim l ^= b << 30; 1966f9291ceSJung-uk Kim h ^= b >> 2; 1976f9291ceSJung-uk Kim } 1986f9291ceSJung-uk Kim if (top2b & 02) { 1996f9291ceSJung-uk Kim l ^= b << 31; 2006f9291ceSJung-uk Kim h ^= b >> 1; 2016f9291ceSJung-uk Kim } 2023b4e3dcbSSimon L. B. Nielsen 2036f9291ceSJung-uk Kim *r1 = h; 2046f9291ceSJung-uk Kim *r0 = l; 2053b4e3dcbSSimon L. B. Nielsen } 2063b4e3dcbSSimon L. B. Nielsen # endif 2073b4e3dcbSSimon L. B. Nielsen # if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) 2086f9291ceSJung-uk Kim static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a, 2096f9291ceSJung-uk Kim const BN_ULONG b) 2103b4e3dcbSSimon L. B. Nielsen { 2113b4e3dcbSSimon L. B. Nielsen register BN_ULONG h, l, s; 2123b4e3dcbSSimon L. B. Nielsen BN_ULONG tab[16], top3b = a >> 61; 2133b4e3dcbSSimon L. B. Nielsen register BN_ULONG a1, a2, a4, a8; 2143b4e3dcbSSimon L. B. Nielsen 2156f9291ceSJung-uk Kim a1 = a & (0x1FFFFFFFFFFFFFFFULL); 2166f9291ceSJung-uk Kim a2 = a1 << 1; 2176f9291ceSJung-uk Kim a4 = a2 << 1; 2186f9291ceSJung-uk Kim a8 = a4 << 1; 2193b4e3dcbSSimon L. B. Nielsen 2206f9291ceSJung-uk Kim tab[0] = 0; 2216f9291ceSJung-uk Kim tab[1] = a1; 2226f9291ceSJung-uk Kim tab[2] = a2; 2236f9291ceSJung-uk Kim tab[3] = a1 ^ a2; 2246f9291ceSJung-uk Kim tab[4] = a4; 2256f9291ceSJung-uk Kim tab[5] = a1 ^ a4; 2266f9291ceSJung-uk Kim tab[6] = a2 ^ a4; 2276f9291ceSJung-uk Kim tab[7] = a1 ^ a2 ^ a4; 2286f9291ceSJung-uk Kim tab[8] = a8; 2296f9291ceSJung-uk Kim tab[9] = a1 ^ a8; 2306f9291ceSJung-uk Kim tab[10] = a2 ^ a8; 2316f9291ceSJung-uk Kim tab[11] = a1 ^ a2 ^ a8; 2326f9291ceSJung-uk Kim tab[12] = a4 ^ a8; 2336f9291ceSJung-uk Kim tab[13] = a1 ^ a4 ^ a8; 2346f9291ceSJung-uk Kim tab[14] = a2 ^ a4 ^ a8; 2356f9291ceSJung-uk Kim tab[15] = a1 ^ a2 ^ a4 ^ a8; 2363b4e3dcbSSimon L. B. Nielsen 2376f9291ceSJung-uk Kim s = tab[b & 0xF]; 2386f9291ceSJung-uk Kim l = s; 2396f9291ceSJung-uk Kim s = tab[b >> 4 & 0xF]; 2406f9291ceSJung-uk Kim l ^= s << 4; 2416f9291ceSJung-uk Kim h = s >> 60; 2426f9291ceSJung-uk Kim s = tab[b >> 8 & 0xF]; 2436f9291ceSJung-uk Kim l ^= s << 8; 2446f9291ceSJung-uk Kim h ^= s >> 56; 2456f9291ceSJung-uk Kim s = tab[b >> 12 & 0xF]; 2466f9291ceSJung-uk Kim l ^= s << 12; 2476f9291ceSJung-uk Kim h ^= s >> 52; 2486f9291ceSJung-uk Kim s = tab[b >> 16 & 0xF]; 2496f9291ceSJung-uk Kim l ^= s << 16; 2506f9291ceSJung-uk Kim h ^= s >> 48; 2516f9291ceSJung-uk Kim s = tab[b >> 20 & 0xF]; 2526f9291ceSJung-uk Kim l ^= s << 20; 2536f9291ceSJung-uk Kim h ^= s >> 44; 2546f9291ceSJung-uk Kim s = tab[b >> 24 & 0xF]; 2556f9291ceSJung-uk Kim l ^= s << 24; 2566f9291ceSJung-uk Kim h ^= s >> 40; 2576f9291ceSJung-uk Kim s = tab[b >> 28 & 0xF]; 2586f9291ceSJung-uk Kim l ^= s << 28; 2596f9291ceSJung-uk Kim h ^= s >> 36; 2606f9291ceSJung-uk Kim s = tab[b >> 32 & 0xF]; 2616f9291ceSJung-uk Kim l ^= s << 32; 2626f9291ceSJung-uk Kim h ^= s >> 32; 2636f9291ceSJung-uk Kim s = tab[b >> 36 & 0xF]; 2646f9291ceSJung-uk Kim l ^= s << 36; 2656f9291ceSJung-uk Kim h ^= s >> 28; 2666f9291ceSJung-uk Kim s = tab[b >> 40 & 0xF]; 2676f9291ceSJung-uk Kim l ^= s << 40; 2686f9291ceSJung-uk Kim h ^= s >> 24; 2696f9291ceSJung-uk Kim s = tab[b >> 44 & 0xF]; 2706f9291ceSJung-uk Kim l ^= s << 44; 2716f9291ceSJung-uk Kim h ^= s >> 20; 2726f9291ceSJung-uk Kim s = tab[b >> 48 & 0xF]; 2736f9291ceSJung-uk Kim l ^= s << 48; 2746f9291ceSJung-uk Kim h ^= s >> 16; 2756f9291ceSJung-uk Kim s = tab[b >> 52 & 0xF]; 2766f9291ceSJung-uk Kim l ^= s << 52; 2776f9291ceSJung-uk Kim h ^= s >> 12; 2786f9291ceSJung-uk Kim s = tab[b >> 56 & 0xF]; 2796f9291ceSJung-uk Kim l ^= s << 56; 2806f9291ceSJung-uk Kim h ^= s >> 8; 2816f9291ceSJung-uk Kim s = tab[b >> 60]; 2826f9291ceSJung-uk Kim l ^= s << 60; 2836f9291ceSJung-uk Kim h ^= s >> 4; 2843b4e3dcbSSimon L. B. Nielsen 2853b4e3dcbSSimon L. B. Nielsen /* compensate for the top three bits of a */ 2863b4e3dcbSSimon L. B. Nielsen 2876f9291ceSJung-uk Kim if (top3b & 01) { 2886f9291ceSJung-uk Kim l ^= b << 61; 2896f9291ceSJung-uk Kim h ^= b >> 3; 2906f9291ceSJung-uk Kim } 2916f9291ceSJung-uk Kim if (top3b & 02) { 2926f9291ceSJung-uk Kim l ^= b << 62; 2936f9291ceSJung-uk Kim h ^= b >> 2; 2946f9291ceSJung-uk Kim } 2956f9291ceSJung-uk Kim if (top3b & 04) { 2966f9291ceSJung-uk Kim l ^= b << 63; 2976f9291ceSJung-uk Kim h ^= b >> 1; 2986f9291ceSJung-uk Kim } 2993b4e3dcbSSimon L. B. Nielsen 3006f9291ceSJung-uk Kim *r1 = h; 3016f9291ceSJung-uk Kim *r0 = l; 3023b4e3dcbSSimon L. B. Nielsen } 3033b4e3dcbSSimon L. B. Nielsen # endif 3043b4e3dcbSSimon L. B. Nielsen 3056f9291ceSJung-uk Kim /* 3066f9291ceSJung-uk Kim * Product of two polynomials a, b each with degree < 2 * BN_BITS2 - 1, 3076f9291ceSJung-uk Kim * result is a polynomial r with degree < 4 * BN_BITS2 - 1 The caller MUST 3086f9291ceSJung-uk Kim * ensure that the variables have the right amount of space allocated. 3093b4e3dcbSSimon L. B. Nielsen */ 3106f9291ceSJung-uk Kim static void bn_GF2m_mul_2x2(BN_ULONG *r, const BN_ULONG a1, const BN_ULONG a0, 3116f9291ceSJung-uk Kim const BN_ULONG b1, const BN_ULONG b0) 3123b4e3dcbSSimon L. B. Nielsen { 3133b4e3dcbSSimon L. B. Nielsen BN_ULONG m1, m0; 3143b4e3dcbSSimon L. B. Nielsen /* r[3] = h1, r[2] = h0; r[1] = l1; r[0] = l0 */ 3153b4e3dcbSSimon L. B. Nielsen bn_GF2m_mul_1x1(r + 3, r + 2, a1, b1); 3163b4e3dcbSSimon L. B. Nielsen bn_GF2m_mul_1x1(r + 1, r, a0, b0); 3173b4e3dcbSSimon L. B. Nielsen bn_GF2m_mul_1x1(&m1, &m0, a0 ^ a1, b0 ^ b1); 3183b4e3dcbSSimon L. B. Nielsen /* Correction on m1 ^= l1 ^ h1; m0 ^= l0 ^ h0; */ 3193b4e3dcbSSimon L. B. Nielsen r[2] ^= m1 ^ r[1] ^ r[3]; /* h0 ^= m1 ^ l1 ^ h1; */ 3203b4e3dcbSSimon L. B. Nielsen r[1] = r[3] ^ r[2] ^ r[0] ^ m1 ^ m0; /* l1 ^= l0 ^ h0 ^ m0; */ 3213b4e3dcbSSimon L. B. Nielsen } 3221f13597dSJung-uk Kim # else 3236f9291ceSJung-uk Kim void bn_GF2m_mul_2x2(BN_ULONG *r, BN_ULONG a1, BN_ULONG a0, BN_ULONG b1, 3246f9291ceSJung-uk Kim BN_ULONG b0); 3251f13597dSJung-uk Kim # endif 3263b4e3dcbSSimon L. B. Nielsen 3276f9291ceSJung-uk Kim /* 3286f9291ceSJung-uk Kim * Add polynomials a and b and store result in r; r could be a or b, a and b 3293b4e3dcbSSimon L. B. Nielsen * could be equal; r is the bitwise XOR of a and b. 3303b4e3dcbSSimon L. B. Nielsen */ 3313b4e3dcbSSimon L. B. Nielsen int BN_GF2m_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 3323b4e3dcbSSimon L. B. Nielsen { 3333b4e3dcbSSimon L. B. Nielsen int i; 3343b4e3dcbSSimon L. B. Nielsen const BIGNUM *at, *bt; 3353b4e3dcbSSimon L. B. Nielsen 3363b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 3373b4e3dcbSSimon L. B. Nielsen bn_check_top(b); 3383b4e3dcbSSimon L. B. Nielsen 3396f9291ceSJung-uk Kim if (a->top < b->top) { 3406f9291ceSJung-uk Kim at = b; 3416f9291ceSJung-uk Kim bt = a; 3426f9291ceSJung-uk Kim } else { 3436f9291ceSJung-uk Kim at = a; 3446f9291ceSJung-uk Kim bt = b; 3456f9291ceSJung-uk Kim } 3463b4e3dcbSSimon L. B. Nielsen 3476a599222SSimon L. B. Nielsen if (bn_wexpand(r, at->top) == NULL) 3486a599222SSimon L. B. Nielsen return 0; 3493b4e3dcbSSimon L. B. Nielsen 3506f9291ceSJung-uk Kim for (i = 0; i < bt->top; i++) { 3513b4e3dcbSSimon L. B. Nielsen r->d[i] = at->d[i] ^ bt->d[i]; 3523b4e3dcbSSimon L. B. Nielsen } 3536f9291ceSJung-uk Kim for (; i < at->top; i++) { 3543b4e3dcbSSimon L. B. Nielsen r->d[i] = at->d[i]; 3553b4e3dcbSSimon L. B. Nielsen } 3563b4e3dcbSSimon L. B. Nielsen 3573b4e3dcbSSimon L. B. Nielsen r->top = at->top; 3583b4e3dcbSSimon L. B. Nielsen bn_correct_top(r); 3593b4e3dcbSSimon L. B. Nielsen 3603b4e3dcbSSimon L. B. Nielsen return 1; 3613b4e3dcbSSimon L. B. Nielsen } 3623b4e3dcbSSimon L. B. Nielsen 3636f9291ceSJung-uk Kim /*- 3646f9291ceSJung-uk Kim * Some functions allow for representation of the irreducible polynomials 3653b4e3dcbSSimon L. B. Nielsen * as an int[], say p. The irreducible f(t) is then of the form: 3663b4e3dcbSSimon L. B. Nielsen * t^p[0] + t^p[1] + ... + t^p[k] 3673b4e3dcbSSimon L. B. Nielsen * where m = p[0] > p[1] > ... > p[k] = 0. 3683b4e3dcbSSimon L. B. Nielsen */ 3693b4e3dcbSSimon L. B. Nielsen 3703b4e3dcbSSimon L. B. Nielsen /* Performs modular reduction of a and store result in r. r could be a. */ 3711f13597dSJung-uk Kim int BN_GF2m_mod_arr(BIGNUM *r, const BIGNUM *a, const int p[]) 3723b4e3dcbSSimon L. B. Nielsen { 3733b4e3dcbSSimon L. B. Nielsen int j, k; 3743b4e3dcbSSimon L. B. Nielsen int n, dN, d0, d1; 3753b4e3dcbSSimon L. B. Nielsen BN_ULONG zz, *z; 3763b4e3dcbSSimon L. B. Nielsen 3773b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 3783b4e3dcbSSimon L. B. Nielsen 3796f9291ceSJung-uk Kim if (!p[0]) { 3803b4e3dcbSSimon L. B. Nielsen /* reduction mod 1 => return 0 */ 3813b4e3dcbSSimon L. B. Nielsen BN_zero(r); 3823b4e3dcbSSimon L. B. Nielsen return 1; 3833b4e3dcbSSimon L. B. Nielsen } 3843b4e3dcbSSimon L. B. Nielsen 3856f9291ceSJung-uk Kim /* 3866f9291ceSJung-uk Kim * Since the algorithm does reduction in the r value, if a != r, copy the 3876f9291ceSJung-uk Kim * contents of a into r so we can do reduction in r. 3883b4e3dcbSSimon L. B. Nielsen */ 3896f9291ceSJung-uk Kim if (a != r) { 3906f9291ceSJung-uk Kim if (!bn_wexpand(r, a->top)) 3916f9291ceSJung-uk Kim return 0; 3926f9291ceSJung-uk Kim for (j = 0; j < a->top; j++) { 3933b4e3dcbSSimon L. B. Nielsen r->d[j] = a->d[j]; 3943b4e3dcbSSimon L. B. Nielsen } 3953b4e3dcbSSimon L. B. Nielsen r->top = a->top; 3963b4e3dcbSSimon L. B. Nielsen } 3973b4e3dcbSSimon L. B. Nielsen z = r->d; 3983b4e3dcbSSimon L. B. Nielsen 3993b4e3dcbSSimon L. B. Nielsen /* start reduction */ 4003b4e3dcbSSimon L. B. Nielsen dN = p[0] / BN_BITS2; 4016f9291ceSJung-uk Kim for (j = r->top - 1; j > dN;) { 4023b4e3dcbSSimon L. B. Nielsen zz = z[j]; 4036f9291ceSJung-uk Kim if (z[j] == 0) { 4046f9291ceSJung-uk Kim j--; 4056f9291ceSJung-uk Kim continue; 4066f9291ceSJung-uk Kim } 4073b4e3dcbSSimon L. B. Nielsen z[j] = 0; 4083b4e3dcbSSimon L. B. Nielsen 4096f9291ceSJung-uk Kim for (k = 1; p[k] != 0; k++) { 4103b4e3dcbSSimon L. B. Nielsen /* reducing component t^p[k] */ 4113b4e3dcbSSimon L. B. Nielsen n = p[0] - p[k]; 4126f9291ceSJung-uk Kim d0 = n % BN_BITS2; 4136f9291ceSJung-uk Kim d1 = BN_BITS2 - d0; 4143b4e3dcbSSimon L. B. Nielsen n /= BN_BITS2; 4153b4e3dcbSSimon L. B. Nielsen z[j - n] ^= (zz >> d0); 4166f9291ceSJung-uk Kim if (d0) 4176f9291ceSJung-uk Kim z[j - n - 1] ^= (zz << d1); 4183b4e3dcbSSimon L. B. Nielsen } 4193b4e3dcbSSimon L. B. Nielsen 4203b4e3dcbSSimon L. B. Nielsen /* reducing component t^0 */ 4213b4e3dcbSSimon L. B. Nielsen n = dN; 4223b4e3dcbSSimon L. B. Nielsen d0 = p[0] % BN_BITS2; 4233b4e3dcbSSimon L. B. Nielsen d1 = BN_BITS2 - d0; 4243b4e3dcbSSimon L. B. Nielsen z[j - n] ^= (zz >> d0); 4256f9291ceSJung-uk Kim if (d0) 4266f9291ceSJung-uk Kim z[j - n - 1] ^= (zz << d1); 4273b4e3dcbSSimon L. B. Nielsen } 4283b4e3dcbSSimon L. B. Nielsen 4293b4e3dcbSSimon L. B. Nielsen /* final round of reduction */ 4306f9291ceSJung-uk Kim while (j == dN) { 4313b4e3dcbSSimon L. B. Nielsen 4323b4e3dcbSSimon L. B. Nielsen d0 = p[0] % BN_BITS2; 4333b4e3dcbSSimon L. B. Nielsen zz = z[dN] >> d0; 4346f9291ceSJung-uk Kim if (zz == 0) 4356f9291ceSJung-uk Kim break; 4363b4e3dcbSSimon L. B. Nielsen d1 = BN_BITS2 - d0; 4373b4e3dcbSSimon L. B. Nielsen 438db522d3aSSimon L. B. Nielsen /* clear up the top d1 bits */ 439db522d3aSSimon L. B. Nielsen if (d0) 440db522d3aSSimon L. B. Nielsen z[dN] = (z[dN] << d1) >> d1; 441db522d3aSSimon L. B. Nielsen else 442db522d3aSSimon L. B. Nielsen z[dN] = 0; 4433b4e3dcbSSimon L. B. Nielsen z[0] ^= zz; /* reduction t^0 component */ 4443b4e3dcbSSimon L. B. Nielsen 4456f9291ceSJung-uk Kim for (k = 1; p[k] != 0; k++) { 4463b4e3dcbSSimon L. B. Nielsen BN_ULONG tmp_ulong; 4473b4e3dcbSSimon L. B. Nielsen 4483b4e3dcbSSimon L. B. Nielsen /* reducing component t^p[k] */ 4493b4e3dcbSSimon L. B. Nielsen n = p[k] / BN_BITS2; 4503b4e3dcbSSimon L. B. Nielsen d0 = p[k] % BN_BITS2; 4513b4e3dcbSSimon L. B. Nielsen d1 = BN_BITS2 - d0; 4523b4e3dcbSSimon L. B. Nielsen z[n] ^= (zz << d0); 4533b4e3dcbSSimon L. B. Nielsen tmp_ulong = zz >> d1; 4543b4e3dcbSSimon L. B. Nielsen if (d0 && tmp_ulong) 4553b4e3dcbSSimon L. B. Nielsen z[n + 1] ^= tmp_ulong; 4563b4e3dcbSSimon L. B. Nielsen } 4573b4e3dcbSSimon L. B. Nielsen 4583b4e3dcbSSimon L. B. Nielsen } 4593b4e3dcbSSimon L. B. Nielsen 4603b4e3dcbSSimon L. B. Nielsen bn_correct_top(r); 4613b4e3dcbSSimon L. B. Nielsen return 1; 4623b4e3dcbSSimon L. B. Nielsen } 4633b4e3dcbSSimon L. B. Nielsen 4646f9291ceSJung-uk Kim /* 4656f9291ceSJung-uk Kim * Performs modular reduction of a by p and store result in r. r could be a. 4663b4e3dcbSSimon L. B. Nielsen * This function calls down to the BN_GF2m_mod_arr implementation; this wrapper 4673b4e3dcbSSimon L. B. Nielsen * function is only provided for convenience; for best performance, use the 4683b4e3dcbSSimon L. B. Nielsen * BN_GF2m_mod_arr function. 4693b4e3dcbSSimon L. B. Nielsen */ 4703b4e3dcbSSimon L. B. Nielsen int BN_GF2m_mod(BIGNUM *r, const BIGNUM *a, const BIGNUM *p) 4713b4e3dcbSSimon L. B. Nielsen { 4723b4e3dcbSSimon L. B. Nielsen int ret = 0; 4731f13597dSJung-uk Kim int arr[6]; 4743b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 4753b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 4761f13597dSJung-uk Kim ret = BN_GF2m_poly2arr(p, arr, sizeof(arr) / sizeof(arr[0])); 4776f9291ceSJung-uk Kim if (!ret || ret > (int)(sizeof(arr) / sizeof(arr[0]))) { 4783b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD, BN_R_INVALID_LENGTH); 4791f13597dSJung-uk Kim return 0; 4803b4e3dcbSSimon L. B. Nielsen } 4813b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_arr(r, a, arr); 4823b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 4833b4e3dcbSSimon L. B. Nielsen return ret; 4843b4e3dcbSSimon L. B. Nielsen } 4853b4e3dcbSSimon L. B. Nielsen 4866f9291ceSJung-uk Kim /* 4876f9291ceSJung-uk Kim * Compute the product of two polynomials a and b, reduce modulo p, and store 4883b4e3dcbSSimon L. B. Nielsen * the result in r. r could be a or b; a could be b. 4893b4e3dcbSSimon L. B. Nielsen */ 4906f9291ceSJung-uk Kim int BN_GF2m_mod_mul_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 4916f9291ceSJung-uk Kim const int p[], BN_CTX *ctx) 4923b4e3dcbSSimon L. B. Nielsen { 4933b4e3dcbSSimon L. B. Nielsen int zlen, i, j, k, ret = 0; 4943b4e3dcbSSimon L. B. Nielsen BIGNUM *s; 4953b4e3dcbSSimon L. B. Nielsen BN_ULONG x1, x0, y1, y0, zz[4]; 4963b4e3dcbSSimon L. B. Nielsen 4973b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 4983b4e3dcbSSimon L. B. Nielsen bn_check_top(b); 4993b4e3dcbSSimon L. B. Nielsen 5006f9291ceSJung-uk Kim if (a == b) { 5013b4e3dcbSSimon L. B. Nielsen return BN_GF2m_mod_sqr_arr(r, a, p, ctx); 5023b4e3dcbSSimon L. B. Nielsen } 5033b4e3dcbSSimon L. B. Nielsen 5043b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 5056f9291ceSJung-uk Kim if ((s = BN_CTX_get(ctx)) == NULL) 5066f9291ceSJung-uk Kim goto err; 5073b4e3dcbSSimon L. B. Nielsen 5083b4e3dcbSSimon L. B. Nielsen zlen = a->top + b->top + 4; 5096f9291ceSJung-uk Kim if (!bn_wexpand(s, zlen)) 5106f9291ceSJung-uk Kim goto err; 5113b4e3dcbSSimon L. B. Nielsen s->top = zlen; 5123b4e3dcbSSimon L. B. Nielsen 5136f9291ceSJung-uk Kim for (i = 0; i < zlen; i++) 5146f9291ceSJung-uk Kim s->d[i] = 0; 5153b4e3dcbSSimon L. B. Nielsen 5166f9291ceSJung-uk Kim for (j = 0; j < b->top; j += 2) { 5173b4e3dcbSSimon L. B. Nielsen y0 = b->d[j]; 5183b4e3dcbSSimon L. B. Nielsen y1 = ((j + 1) == b->top) ? 0 : b->d[j + 1]; 5196f9291ceSJung-uk Kim for (i = 0; i < a->top; i += 2) { 5203b4e3dcbSSimon L. B. Nielsen x0 = a->d[i]; 5213b4e3dcbSSimon L. B. Nielsen x1 = ((i + 1) == a->top) ? 0 : a->d[i + 1]; 5223b4e3dcbSSimon L. B. Nielsen bn_GF2m_mul_2x2(zz, x1, x0, y1, y0); 5236f9291ceSJung-uk Kim for (k = 0; k < 4; k++) 5246f9291ceSJung-uk Kim s->d[i + j + k] ^= zz[k]; 5253b4e3dcbSSimon L. B. Nielsen } 5263b4e3dcbSSimon L. B. Nielsen } 5273b4e3dcbSSimon L. B. Nielsen 5283b4e3dcbSSimon L. B. Nielsen bn_correct_top(s); 5293b4e3dcbSSimon L. B. Nielsen if (BN_GF2m_mod_arr(r, s, p)) 5303b4e3dcbSSimon L. B. Nielsen ret = 1; 5313b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 5323b4e3dcbSSimon L. B. Nielsen 5333b4e3dcbSSimon L. B. Nielsen err: 5343b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 5353b4e3dcbSSimon L. B. Nielsen return ret; 5363b4e3dcbSSimon L. B. Nielsen } 5373b4e3dcbSSimon L. B. Nielsen 5386f9291ceSJung-uk Kim /* 5396f9291ceSJung-uk Kim * Compute the product of two polynomials a and b, reduce modulo p, and store 5406f9291ceSJung-uk Kim * the result in r. r could be a or b; a could equal b. This function calls 5416f9291ceSJung-uk Kim * down to the BN_GF2m_mod_mul_arr implementation; this wrapper function is 5426f9291ceSJung-uk Kim * only provided for convenience; for best performance, use the 5433b4e3dcbSSimon L. B. Nielsen * BN_GF2m_mod_mul_arr function. 5443b4e3dcbSSimon L. B. Nielsen */ 5456f9291ceSJung-uk Kim int BN_GF2m_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 5466f9291ceSJung-uk Kim const BIGNUM *p, BN_CTX *ctx) 5473b4e3dcbSSimon L. B. Nielsen { 5483b4e3dcbSSimon L. B. Nielsen int ret = 0; 5491f13597dSJung-uk Kim const int max = BN_num_bits(p) + 1; 5501f13597dSJung-uk Kim int *arr = NULL; 5513b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 5523b4e3dcbSSimon L. B. Nielsen bn_check_top(b); 5533b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 5546f9291ceSJung-uk Kim if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) 5556f9291ceSJung-uk Kim goto err; 5563b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_poly2arr(p, arr, max); 5576f9291ceSJung-uk Kim if (!ret || ret > max) { 5583b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD_MUL, BN_R_INVALID_LENGTH); 5593b4e3dcbSSimon L. B. Nielsen goto err; 5603b4e3dcbSSimon L. B. Nielsen } 5613b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_mul_arr(r, a, b, arr, ctx); 5623b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 5633b4e3dcbSSimon L. B. Nielsen err: 5646f9291ceSJung-uk Kim if (arr) 5656f9291ceSJung-uk Kim OPENSSL_free(arr); 5663b4e3dcbSSimon L. B. Nielsen return ret; 5673b4e3dcbSSimon L. B. Nielsen } 5683b4e3dcbSSimon L. B. Nielsen 5693b4e3dcbSSimon L. B. Nielsen /* Square a, reduce the result mod p, and store it in a. r could be a. */ 5706f9291ceSJung-uk Kim int BN_GF2m_mod_sqr_arr(BIGNUM *r, const BIGNUM *a, const int p[], 5716f9291ceSJung-uk Kim BN_CTX *ctx) 5723b4e3dcbSSimon L. B. Nielsen { 5733b4e3dcbSSimon L. B. Nielsen int i, ret = 0; 5743b4e3dcbSSimon L. B. Nielsen BIGNUM *s; 5753b4e3dcbSSimon L. B. Nielsen 5763b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 5773b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 5786f9291ceSJung-uk Kim if ((s = BN_CTX_get(ctx)) == NULL) 5796f9291ceSJung-uk Kim return 0; 5806f9291ceSJung-uk Kim if (!bn_wexpand(s, 2 * a->top)) 5816f9291ceSJung-uk Kim goto err; 5823b4e3dcbSSimon L. B. Nielsen 5836f9291ceSJung-uk Kim for (i = a->top - 1; i >= 0; i--) { 5843b4e3dcbSSimon L. B. Nielsen s->d[2 * i + 1] = SQR1(a->d[i]); 5853b4e3dcbSSimon L. B. Nielsen s->d[2 * i] = SQR0(a->d[i]); 5863b4e3dcbSSimon L. B. Nielsen } 5873b4e3dcbSSimon L. B. Nielsen 5883b4e3dcbSSimon L. B. Nielsen s->top = 2 * a->top; 5893b4e3dcbSSimon L. B. Nielsen bn_correct_top(s); 5906f9291ceSJung-uk Kim if (!BN_GF2m_mod_arr(r, s, p)) 5916f9291ceSJung-uk Kim goto err; 5923b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 5933b4e3dcbSSimon L. B. Nielsen ret = 1; 5943b4e3dcbSSimon L. B. Nielsen err: 5953b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 5963b4e3dcbSSimon L. B. Nielsen return ret; 5973b4e3dcbSSimon L. B. Nielsen } 5983b4e3dcbSSimon L. B. Nielsen 5996f9291ceSJung-uk Kim /* 6006f9291ceSJung-uk Kim * Square a, reduce the result mod p, and store it in a. r could be a. This 6016f9291ceSJung-uk Kim * function calls down to the BN_GF2m_mod_sqr_arr implementation; this 6026f9291ceSJung-uk Kim * wrapper function is only provided for convenience; for best performance, 6036f9291ceSJung-uk Kim * use the BN_GF2m_mod_sqr_arr function. 6043b4e3dcbSSimon L. B. Nielsen */ 6053b4e3dcbSSimon L. B. Nielsen int BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) 6063b4e3dcbSSimon L. B. Nielsen { 6073b4e3dcbSSimon L. B. Nielsen int ret = 0; 6081f13597dSJung-uk Kim const int max = BN_num_bits(p) + 1; 6091f13597dSJung-uk Kim int *arr = NULL; 6103b4e3dcbSSimon L. B. Nielsen 6113b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 6123b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 6136f9291ceSJung-uk Kim if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) 6146f9291ceSJung-uk Kim goto err; 6153b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_poly2arr(p, arr, max); 6166f9291ceSJung-uk Kim if (!ret || ret > max) { 6173b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD_SQR, BN_R_INVALID_LENGTH); 6183b4e3dcbSSimon L. B. Nielsen goto err; 6193b4e3dcbSSimon L. B. Nielsen } 6203b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_sqr_arr(r, a, arr, ctx); 6213b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 6223b4e3dcbSSimon L. B. Nielsen err: 6236f9291ceSJung-uk Kim if (arr) 6246f9291ceSJung-uk Kim OPENSSL_free(arr); 6253b4e3dcbSSimon L. B. Nielsen return ret; 6263b4e3dcbSSimon L. B. Nielsen } 6273b4e3dcbSSimon L. B. Nielsen 6286f9291ceSJung-uk Kim /* 6296f9291ceSJung-uk Kim * Invert a, reduce modulo p, and store the result in r. r could be a. Uses 6306f9291ceSJung-uk Kim * Modified Almost Inverse Algorithm (Algorithm 10) from Hankerson, D., 6316f9291ceSJung-uk Kim * Hernandez, J.L., and Menezes, A. "Software Implementation of Elliptic 6326f9291ceSJung-uk Kim * Curve Cryptography Over Binary Fields". 6333b4e3dcbSSimon L. B. Nielsen */ 6343b4e3dcbSSimon L. B. Nielsen int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) 6353b4e3dcbSSimon L. B. Nielsen { 6361f13597dSJung-uk Kim BIGNUM *b, *c = NULL, *u = NULL, *v = NULL, *tmp; 6373b4e3dcbSSimon L. B. Nielsen int ret = 0; 6383b4e3dcbSSimon L. B. Nielsen 6393b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 6403b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 6413b4e3dcbSSimon L. B. Nielsen 6423b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 6433b4e3dcbSSimon L. B. Nielsen 6446f9291ceSJung-uk Kim if ((b = BN_CTX_get(ctx)) == NULL) 6456f9291ceSJung-uk Kim goto err; 6466f9291ceSJung-uk Kim if ((c = BN_CTX_get(ctx)) == NULL) 6476f9291ceSJung-uk Kim goto err; 6486f9291ceSJung-uk Kim if ((u = BN_CTX_get(ctx)) == NULL) 6496f9291ceSJung-uk Kim goto err; 6506f9291ceSJung-uk Kim if ((v = BN_CTX_get(ctx)) == NULL) 6516f9291ceSJung-uk Kim goto err; 6523b4e3dcbSSimon L. B. Nielsen 6536f9291ceSJung-uk Kim if (!BN_GF2m_mod(u, a, p)) 6546f9291ceSJung-uk Kim goto err; 6556f9291ceSJung-uk Kim if (BN_is_zero(u)) 6566f9291ceSJung-uk Kim goto err; 6573b4e3dcbSSimon L. B. Nielsen 6586f9291ceSJung-uk Kim if (!BN_copy(v, p)) 6596f9291ceSJung-uk Kim goto err; 6601f13597dSJung-uk Kim # if 0 6616f9291ceSJung-uk Kim if (!BN_one(b)) 6626f9291ceSJung-uk Kim goto err; 6631f13597dSJung-uk Kim 6646f9291ceSJung-uk Kim while (1) { 6656f9291ceSJung-uk Kim while (!BN_is_odd(u)) { 6666f9291ceSJung-uk Kim if (BN_is_zero(u)) 6676f9291ceSJung-uk Kim goto err; 6686f9291ceSJung-uk Kim if (!BN_rshift1(u, u)) 6696f9291ceSJung-uk Kim goto err; 6706f9291ceSJung-uk Kim if (BN_is_odd(b)) { 6716f9291ceSJung-uk Kim if (!BN_GF2m_add(b, b, p)) 6726f9291ceSJung-uk Kim goto err; 6733b4e3dcbSSimon L. B. Nielsen } 6746f9291ceSJung-uk Kim if (!BN_rshift1(b, b)) 6756f9291ceSJung-uk Kim goto err; 6763b4e3dcbSSimon L. B. Nielsen } 6773b4e3dcbSSimon L. B. Nielsen 6786f9291ceSJung-uk Kim if (BN_abs_is_word(u, 1)) 6796f9291ceSJung-uk Kim break; 6803b4e3dcbSSimon L. B. Nielsen 6816f9291ceSJung-uk Kim if (BN_num_bits(u) < BN_num_bits(v)) { 6826f9291ceSJung-uk Kim tmp = u; 6836f9291ceSJung-uk Kim u = v; 6846f9291ceSJung-uk Kim v = tmp; 6856f9291ceSJung-uk Kim tmp = b; 6866f9291ceSJung-uk Kim b = c; 6876f9291ceSJung-uk Kim c = tmp; 6883b4e3dcbSSimon L. B. Nielsen } 6893b4e3dcbSSimon L. B. Nielsen 6906f9291ceSJung-uk Kim if (!BN_GF2m_add(u, u, v)) 6916f9291ceSJung-uk Kim goto err; 6926f9291ceSJung-uk Kim if (!BN_GF2m_add(b, b, c)) 6936f9291ceSJung-uk Kim goto err; 6943b4e3dcbSSimon L. B. Nielsen } 6951f13597dSJung-uk Kim # else 6961f13597dSJung-uk Kim { 6976f9291ceSJung-uk Kim int i, ubits = BN_num_bits(u), vbits = BN_num_bits(v), /* v is copy 6986f9291ceSJung-uk Kim * of p */ 6991f13597dSJung-uk Kim top = p->top; 7001f13597dSJung-uk Kim BN_ULONG *udp, *bdp, *vdp, *cdp; 7013b4e3dcbSSimon L. B. Nielsen 7026f9291ceSJung-uk Kim bn_wexpand(u, top); 7036f9291ceSJung-uk Kim udp = u->d; 7046f9291ceSJung-uk Kim for (i = u->top; i < top; i++) 7056f9291ceSJung-uk Kim udp[i] = 0; 7061f13597dSJung-uk Kim u->top = top; 7076f9291ceSJung-uk Kim bn_wexpand(b, top); 7086f9291ceSJung-uk Kim bdp = b->d; 7091f13597dSJung-uk Kim bdp[0] = 1; 7106f9291ceSJung-uk Kim for (i = 1; i < top; i++) 7116f9291ceSJung-uk Kim bdp[i] = 0; 7121f13597dSJung-uk Kim b->top = top; 7136f9291ceSJung-uk Kim bn_wexpand(c, top); 7146f9291ceSJung-uk Kim cdp = c->d; 7156f9291ceSJung-uk Kim for (i = 0; i < top; i++) 7166f9291ceSJung-uk Kim cdp[i] = 0; 7171f13597dSJung-uk Kim c->top = top; 7186f9291ceSJung-uk Kim vdp = v->d; /* It pays off to "cache" *->d pointers, 7196f9291ceSJung-uk Kim * because it allows optimizer to be more 7206f9291ceSJung-uk Kim * aggressive. But we don't have to "cache" 7216f9291ceSJung-uk Kim * p->d, because *p is declared 'const'... */ 7226f9291ceSJung-uk Kim while (1) { 7236f9291ceSJung-uk Kim while (ubits && !(udp[0] & 1)) { 7241f13597dSJung-uk Kim BN_ULONG u0, u1, b0, b1, mask; 7251f13597dSJung-uk Kim 7261f13597dSJung-uk Kim u0 = udp[0]; 7271f13597dSJung-uk Kim b0 = bdp[0]; 7281f13597dSJung-uk Kim mask = (BN_ULONG)0 - (b0 & 1); 7291f13597dSJung-uk Kim b0 ^= p->d[0] & mask; 7306f9291ceSJung-uk Kim for (i = 0; i < top - 1; i++) { 7311f13597dSJung-uk Kim u1 = udp[i + 1]; 7321f13597dSJung-uk Kim udp[i] = ((u0 >> 1) | (u1 << (BN_BITS2 - 1))) & BN_MASK2; 7331f13597dSJung-uk Kim u0 = u1; 7341f13597dSJung-uk Kim b1 = bdp[i + 1] ^ (p->d[i + 1] & mask); 7351f13597dSJung-uk Kim bdp[i] = ((b0 >> 1) | (b1 << (BN_BITS2 - 1))) & BN_MASK2; 7361f13597dSJung-uk Kim b0 = b1; 7371f13597dSJung-uk Kim } 7381f13597dSJung-uk Kim udp[i] = u0 >> 1; 7391f13597dSJung-uk Kim bdp[i] = b0 >> 1; 7401f13597dSJung-uk Kim ubits--; 7411f13597dSJung-uk Kim } 7421f13597dSJung-uk Kim 7436f9291ceSJung-uk Kim if (ubits <= BN_BITS2 && udp[0] == 1) 7446f9291ceSJung-uk Kim break; 7451f13597dSJung-uk Kim 7466f9291ceSJung-uk Kim if (ubits < vbits) { 7476f9291ceSJung-uk Kim i = ubits; 7486f9291ceSJung-uk Kim ubits = vbits; 7496f9291ceSJung-uk Kim vbits = i; 7506f9291ceSJung-uk Kim tmp = u; 7516f9291ceSJung-uk Kim u = v; 7526f9291ceSJung-uk Kim v = tmp; 7536f9291ceSJung-uk Kim tmp = b; 7546f9291ceSJung-uk Kim b = c; 7556f9291ceSJung-uk Kim c = tmp; 7566f9291ceSJung-uk Kim udp = vdp; 7576f9291ceSJung-uk Kim vdp = v->d; 7586f9291ceSJung-uk Kim bdp = cdp; 7596f9291ceSJung-uk Kim cdp = c->d; 7601f13597dSJung-uk Kim } 7616f9291ceSJung-uk Kim for (i = 0; i < top; i++) { 7621f13597dSJung-uk Kim udp[i] ^= vdp[i]; 7631f13597dSJung-uk Kim bdp[i] ^= cdp[i]; 7641f13597dSJung-uk Kim } 7656f9291ceSJung-uk Kim if (ubits == vbits) { 7661f13597dSJung-uk Kim BN_ULONG ul; 7671f13597dSJung-uk Kim int utop = (ubits - 1) / BN_BITS2; 7681f13597dSJung-uk Kim 7696f9291ceSJung-uk Kim while ((ul = udp[utop]) == 0 && utop) 7706f9291ceSJung-uk Kim utop--; 7711f13597dSJung-uk Kim ubits = utop * BN_BITS2 + BN_num_bits_word(ul); 7721f13597dSJung-uk Kim } 7731f13597dSJung-uk Kim } 7741f13597dSJung-uk Kim bn_correct_top(b); 7751f13597dSJung-uk Kim } 7761f13597dSJung-uk Kim # endif 7773b4e3dcbSSimon L. B. Nielsen 7786f9291ceSJung-uk Kim if (!BN_copy(r, b)) 7796f9291ceSJung-uk Kim goto err; 7803b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 7813b4e3dcbSSimon L. B. Nielsen ret = 1; 7823b4e3dcbSSimon L. B. Nielsen 7833b4e3dcbSSimon L. B. Nielsen err: 7846f9291ceSJung-uk Kim # ifdef BN_DEBUG /* BN_CTX_end would complain about the 7856f9291ceSJung-uk Kim * expanded form */ 7861f13597dSJung-uk Kim bn_correct_top(c); 7871f13597dSJung-uk Kim bn_correct_top(u); 7881f13597dSJung-uk Kim bn_correct_top(v); 7891f13597dSJung-uk Kim # endif 7903b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 7913b4e3dcbSSimon L. B. Nielsen return ret; 7923b4e3dcbSSimon L. B. Nielsen } 7933b4e3dcbSSimon L. B. Nielsen 7946f9291ceSJung-uk Kim /* 7956f9291ceSJung-uk Kim * Invert xx, reduce modulo p, and store the result in r. r could be xx. 7966f9291ceSJung-uk Kim * This function calls down to the BN_GF2m_mod_inv implementation; this 7976f9291ceSJung-uk Kim * wrapper function is only provided for convenience; for best performance, 7986f9291ceSJung-uk Kim * use the BN_GF2m_mod_inv function. 7993b4e3dcbSSimon L. B. Nielsen */ 8006f9291ceSJung-uk Kim int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const int p[], 8016f9291ceSJung-uk Kim BN_CTX *ctx) 8023b4e3dcbSSimon L. B. Nielsen { 8033b4e3dcbSSimon L. B. Nielsen BIGNUM *field; 8043b4e3dcbSSimon L. B. Nielsen int ret = 0; 8053b4e3dcbSSimon L. B. Nielsen 8063b4e3dcbSSimon L. B. Nielsen bn_check_top(xx); 8073b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 8086f9291ceSJung-uk Kim if ((field = BN_CTX_get(ctx)) == NULL) 8096f9291ceSJung-uk Kim goto err; 8106f9291ceSJung-uk Kim if (!BN_GF2m_arr2poly(p, field)) 8116f9291ceSJung-uk Kim goto err; 8123b4e3dcbSSimon L. B. Nielsen 8133b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_inv(r, xx, field, ctx); 8143b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 8153b4e3dcbSSimon L. B. Nielsen 8163b4e3dcbSSimon L. B. Nielsen err: 8173b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 8183b4e3dcbSSimon L. B. Nielsen return ret; 8193b4e3dcbSSimon L. B. Nielsen } 8203b4e3dcbSSimon L. B. Nielsen 8213b4e3dcbSSimon L. B. Nielsen # ifndef OPENSSL_SUN_GF2M_DIV 8226f9291ceSJung-uk Kim /* 8236f9291ceSJung-uk Kim * Divide y by x, reduce modulo p, and store the result in r. r could be x 8243b4e3dcbSSimon L. B. Nielsen * or y, x could equal y. 8253b4e3dcbSSimon L. B. Nielsen */ 8266f9291ceSJung-uk Kim int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, 8276f9291ceSJung-uk Kim const BIGNUM *p, BN_CTX *ctx) 8283b4e3dcbSSimon L. B. Nielsen { 8293b4e3dcbSSimon L. B. Nielsen BIGNUM *xinv = NULL; 8303b4e3dcbSSimon L. B. Nielsen int ret = 0; 8313b4e3dcbSSimon L. B. Nielsen 8323b4e3dcbSSimon L. B. Nielsen bn_check_top(y); 8333b4e3dcbSSimon L. B. Nielsen bn_check_top(x); 8343b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 8353b4e3dcbSSimon L. B. Nielsen 8363b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 8373b4e3dcbSSimon L. B. Nielsen xinv = BN_CTX_get(ctx); 8386f9291ceSJung-uk Kim if (xinv == NULL) 8396f9291ceSJung-uk Kim goto err; 8403b4e3dcbSSimon L. B. Nielsen 8416f9291ceSJung-uk Kim if (!BN_GF2m_mod_inv(xinv, x, p, ctx)) 8426f9291ceSJung-uk Kim goto err; 8436f9291ceSJung-uk Kim if (!BN_GF2m_mod_mul(r, y, xinv, p, ctx)) 8446f9291ceSJung-uk Kim goto err; 8453b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 8463b4e3dcbSSimon L. B. Nielsen ret = 1; 8473b4e3dcbSSimon L. B. Nielsen 8483b4e3dcbSSimon L. B. Nielsen err: 8493b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 8503b4e3dcbSSimon L. B. Nielsen return ret; 8513b4e3dcbSSimon L. B. Nielsen } 8523b4e3dcbSSimon L. B. Nielsen # else 8536f9291ceSJung-uk Kim /* 8546f9291ceSJung-uk Kim * Divide y by x, reduce modulo p, and store the result in r. r could be x 8556f9291ceSJung-uk Kim * or y, x could equal y. Uses algorithm Modular_Division_GF(2^m) from 8566f9291ceSJung-uk Kim * Chang-Shantz, S. "From Euclid's GCD to Montgomery Multiplication to the 8576f9291ceSJung-uk Kim * Great Divide". 8583b4e3dcbSSimon L. B. Nielsen */ 8596f9291ceSJung-uk Kim int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, 8606f9291ceSJung-uk Kim const BIGNUM *p, BN_CTX *ctx) 8613b4e3dcbSSimon L. B. Nielsen { 8623b4e3dcbSSimon L. B. Nielsen BIGNUM *a, *b, *u, *v; 8633b4e3dcbSSimon L. B. Nielsen int ret = 0; 8643b4e3dcbSSimon L. B. Nielsen 8653b4e3dcbSSimon L. B. Nielsen bn_check_top(y); 8663b4e3dcbSSimon L. B. Nielsen bn_check_top(x); 8673b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 8683b4e3dcbSSimon L. B. Nielsen 8693b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 8703b4e3dcbSSimon L. B. Nielsen 8713b4e3dcbSSimon L. B. Nielsen a = BN_CTX_get(ctx); 8723b4e3dcbSSimon L. B. Nielsen b = BN_CTX_get(ctx); 8733b4e3dcbSSimon L. B. Nielsen u = BN_CTX_get(ctx); 8743b4e3dcbSSimon L. B. Nielsen v = BN_CTX_get(ctx); 8756f9291ceSJung-uk Kim if (v == NULL) 8766f9291ceSJung-uk Kim goto err; 8773b4e3dcbSSimon L. B. Nielsen 8783b4e3dcbSSimon L. B. Nielsen /* reduce x and y mod p */ 8796f9291ceSJung-uk Kim if (!BN_GF2m_mod(u, y, p)) 8806f9291ceSJung-uk Kim goto err; 8816f9291ceSJung-uk Kim if (!BN_GF2m_mod(a, x, p)) 8826f9291ceSJung-uk Kim goto err; 8836f9291ceSJung-uk Kim if (!BN_copy(b, p)) 8846f9291ceSJung-uk Kim goto err; 8853b4e3dcbSSimon L. B. Nielsen 8866f9291ceSJung-uk Kim while (!BN_is_odd(a)) { 8876f9291ceSJung-uk Kim if (!BN_rshift1(a, a)) 8886f9291ceSJung-uk Kim goto err; 8896f9291ceSJung-uk Kim if (BN_is_odd(u)) 8906f9291ceSJung-uk Kim if (!BN_GF2m_add(u, u, p)) 8916f9291ceSJung-uk Kim goto err; 8926f9291ceSJung-uk Kim if (!BN_rshift1(u, u)) 8936f9291ceSJung-uk Kim goto err; 8943b4e3dcbSSimon L. B. Nielsen } 8953b4e3dcbSSimon L. B. Nielsen 8966f9291ceSJung-uk Kim do { 8976f9291ceSJung-uk Kim if (BN_GF2m_cmp(b, a) > 0) { 8986f9291ceSJung-uk Kim if (!BN_GF2m_add(b, b, a)) 8996f9291ceSJung-uk Kim goto err; 9006f9291ceSJung-uk Kim if (!BN_GF2m_add(v, v, u)) 9016f9291ceSJung-uk Kim goto err; 9026f9291ceSJung-uk Kim do { 9036f9291ceSJung-uk Kim if (!BN_rshift1(b, b)) 9046f9291ceSJung-uk Kim goto err; 9056f9291ceSJung-uk Kim if (BN_is_odd(v)) 9066f9291ceSJung-uk Kim if (!BN_GF2m_add(v, v, p)) 9076f9291ceSJung-uk Kim goto err; 9086f9291ceSJung-uk Kim if (!BN_rshift1(v, v)) 9096f9291ceSJung-uk Kim goto err; 9103b4e3dcbSSimon L. B. Nielsen } while (!BN_is_odd(b)); 9116f9291ceSJung-uk Kim } else if (BN_abs_is_word(a, 1)) 9123b4e3dcbSSimon L. B. Nielsen break; 9136f9291ceSJung-uk Kim else { 9146f9291ceSJung-uk Kim if (!BN_GF2m_add(a, a, b)) 9156f9291ceSJung-uk Kim goto err; 9166f9291ceSJung-uk Kim if (!BN_GF2m_add(u, u, v)) 9176f9291ceSJung-uk Kim goto err; 9186f9291ceSJung-uk Kim do { 9196f9291ceSJung-uk Kim if (!BN_rshift1(a, a)) 9206f9291ceSJung-uk Kim goto err; 9216f9291ceSJung-uk Kim if (BN_is_odd(u)) 9226f9291ceSJung-uk Kim if (!BN_GF2m_add(u, u, p)) 9236f9291ceSJung-uk Kim goto err; 9246f9291ceSJung-uk Kim if (!BN_rshift1(u, u)) 9256f9291ceSJung-uk Kim goto err; 9263b4e3dcbSSimon L. B. Nielsen } while (!BN_is_odd(a)); 9273b4e3dcbSSimon L. B. Nielsen } 9283b4e3dcbSSimon L. B. Nielsen } while (1); 9293b4e3dcbSSimon L. B. Nielsen 9306f9291ceSJung-uk Kim if (!BN_copy(r, u)) 9316f9291ceSJung-uk Kim goto err; 9323b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 9333b4e3dcbSSimon L. B. Nielsen ret = 1; 9343b4e3dcbSSimon L. B. Nielsen 9353b4e3dcbSSimon L. B. Nielsen err: 9363b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 9373b4e3dcbSSimon L. B. Nielsen return ret; 9383b4e3dcbSSimon L. B. Nielsen } 9393b4e3dcbSSimon L. B. Nielsen # endif 9403b4e3dcbSSimon L. B. Nielsen 9416f9291ceSJung-uk Kim /* 9426f9291ceSJung-uk Kim * Divide yy by xx, reduce modulo p, and store the result in r. r could be xx 9436f9291ceSJung-uk Kim * * or yy, xx could equal yy. This function calls down to the 9446f9291ceSJung-uk Kim * BN_GF2m_mod_div implementation; this wrapper function is only provided for 9456f9291ceSJung-uk Kim * convenience; for best performance, use the BN_GF2m_mod_div function. 9463b4e3dcbSSimon L. B. Nielsen */ 9476f9291ceSJung-uk Kim int BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *yy, const BIGNUM *xx, 9486f9291ceSJung-uk Kim const int p[], BN_CTX *ctx) 9493b4e3dcbSSimon L. B. Nielsen { 9503b4e3dcbSSimon L. B. Nielsen BIGNUM *field; 9513b4e3dcbSSimon L. B. Nielsen int ret = 0; 9523b4e3dcbSSimon L. B. Nielsen 9533b4e3dcbSSimon L. B. Nielsen bn_check_top(yy); 9543b4e3dcbSSimon L. B. Nielsen bn_check_top(xx); 9553b4e3dcbSSimon L. B. Nielsen 9563b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 9576f9291ceSJung-uk Kim if ((field = BN_CTX_get(ctx)) == NULL) 9586f9291ceSJung-uk Kim goto err; 9596f9291ceSJung-uk Kim if (!BN_GF2m_arr2poly(p, field)) 9606f9291ceSJung-uk Kim goto err; 9613b4e3dcbSSimon L. B. Nielsen 9623b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_div(r, yy, xx, field, ctx); 9633b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 9643b4e3dcbSSimon L. B. Nielsen 9653b4e3dcbSSimon L. B. Nielsen err: 9663b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 9673b4e3dcbSSimon L. B. Nielsen return ret; 9683b4e3dcbSSimon L. B. Nielsen } 9693b4e3dcbSSimon L. B. Nielsen 9706f9291ceSJung-uk Kim /* 9716f9291ceSJung-uk Kim * Compute the bth power of a, reduce modulo p, and store the result in r. r 9726f9291ceSJung-uk Kim * could be a. Uses simple square-and-multiply algorithm A.5.1 from IEEE 9736f9291ceSJung-uk Kim * P1363. 9743b4e3dcbSSimon L. B. Nielsen */ 9756f9291ceSJung-uk Kim int BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 9766f9291ceSJung-uk Kim const int p[], BN_CTX *ctx) 9773b4e3dcbSSimon L. B. Nielsen { 9783b4e3dcbSSimon L. B. Nielsen int ret = 0, i, n; 9793b4e3dcbSSimon L. B. Nielsen BIGNUM *u; 9803b4e3dcbSSimon L. B. Nielsen 9813b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 9823b4e3dcbSSimon L. B. Nielsen bn_check_top(b); 9833b4e3dcbSSimon L. B. Nielsen 9843b4e3dcbSSimon L. B. Nielsen if (BN_is_zero(b)) 9853b4e3dcbSSimon L. B. Nielsen return (BN_one(r)); 9863b4e3dcbSSimon L. B. Nielsen 9873b4e3dcbSSimon L. B. Nielsen if (BN_abs_is_word(b, 1)) 9883b4e3dcbSSimon L. B. Nielsen return (BN_copy(r, a) != NULL); 9893b4e3dcbSSimon L. B. Nielsen 9903b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 9916f9291ceSJung-uk Kim if ((u = BN_CTX_get(ctx)) == NULL) 9926f9291ceSJung-uk Kim goto err; 9933b4e3dcbSSimon L. B. Nielsen 9946f9291ceSJung-uk Kim if (!BN_GF2m_mod_arr(u, a, p)) 9956f9291ceSJung-uk Kim goto err; 9963b4e3dcbSSimon L. B. Nielsen 9973b4e3dcbSSimon L. B. Nielsen n = BN_num_bits(b) - 1; 9986f9291ceSJung-uk Kim for (i = n - 1; i >= 0; i--) { 9996f9291ceSJung-uk Kim if (!BN_GF2m_mod_sqr_arr(u, u, p, ctx)) 10006f9291ceSJung-uk Kim goto err; 10016f9291ceSJung-uk Kim if (BN_is_bit_set(b, i)) { 10026f9291ceSJung-uk Kim if (!BN_GF2m_mod_mul_arr(u, u, a, p, ctx)) 10036f9291ceSJung-uk Kim goto err; 10043b4e3dcbSSimon L. B. Nielsen } 10053b4e3dcbSSimon L. B. Nielsen } 10066f9291ceSJung-uk Kim if (!BN_copy(r, u)) 10076f9291ceSJung-uk Kim goto err; 10083b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 10093b4e3dcbSSimon L. B. Nielsen ret = 1; 10103b4e3dcbSSimon L. B. Nielsen err: 10113b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 10123b4e3dcbSSimon L. B. Nielsen return ret; 10133b4e3dcbSSimon L. B. Nielsen } 10143b4e3dcbSSimon L. B. Nielsen 10156f9291ceSJung-uk Kim /* 10166f9291ceSJung-uk Kim * Compute the bth power of a, reduce modulo p, and store the result in r. r 10176f9291ceSJung-uk Kim * could be a. This function calls down to the BN_GF2m_mod_exp_arr 10186f9291ceSJung-uk Kim * implementation; this wrapper function is only provided for convenience; 10196f9291ceSJung-uk Kim * for best performance, use the BN_GF2m_mod_exp_arr function. 10203b4e3dcbSSimon L. B. Nielsen */ 10216f9291ceSJung-uk Kim int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 10226f9291ceSJung-uk Kim const BIGNUM *p, BN_CTX *ctx) 10233b4e3dcbSSimon L. B. Nielsen { 10243b4e3dcbSSimon L. B. Nielsen int ret = 0; 10251f13597dSJung-uk Kim const int max = BN_num_bits(p) + 1; 10261f13597dSJung-uk Kim int *arr = NULL; 10273b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 10283b4e3dcbSSimon L. B. Nielsen bn_check_top(b); 10293b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 10306f9291ceSJung-uk Kim if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) 10316f9291ceSJung-uk Kim goto err; 10323b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_poly2arr(p, arr, max); 10336f9291ceSJung-uk Kim if (!ret || ret > max) { 10343b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD_EXP, BN_R_INVALID_LENGTH); 10353b4e3dcbSSimon L. B. Nielsen goto err; 10363b4e3dcbSSimon L. B. Nielsen } 10373b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_exp_arr(r, a, b, arr, ctx); 10383b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 10393b4e3dcbSSimon L. B. Nielsen err: 10406f9291ceSJung-uk Kim if (arr) 10416f9291ceSJung-uk Kim OPENSSL_free(arr); 10423b4e3dcbSSimon L. B. Nielsen return ret; 10433b4e3dcbSSimon L. B. Nielsen } 10443b4e3dcbSSimon L. B. Nielsen 10456f9291ceSJung-uk Kim /* 10466f9291ceSJung-uk Kim * Compute the square root of a, reduce modulo p, and store the result in r. 10476f9291ceSJung-uk Kim * r could be a. Uses exponentiation as in algorithm A.4.1 from IEEE P1363. 10483b4e3dcbSSimon L. B. Nielsen */ 10496f9291ceSJung-uk Kim int BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const int p[], 10506f9291ceSJung-uk Kim BN_CTX *ctx) 10513b4e3dcbSSimon L. B. Nielsen { 10523b4e3dcbSSimon L. B. Nielsen int ret = 0; 10533b4e3dcbSSimon L. B. Nielsen BIGNUM *u; 10543b4e3dcbSSimon L. B. Nielsen 10553b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 10563b4e3dcbSSimon L. B. Nielsen 10576f9291ceSJung-uk Kim if (!p[0]) { 10583b4e3dcbSSimon L. B. Nielsen /* reduction mod 1 => return 0 */ 10593b4e3dcbSSimon L. B. Nielsen BN_zero(r); 10603b4e3dcbSSimon L. B. Nielsen return 1; 10613b4e3dcbSSimon L. B. Nielsen } 10623b4e3dcbSSimon L. B. Nielsen 10633b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 10646f9291ceSJung-uk Kim if ((u = BN_CTX_get(ctx)) == NULL) 10656f9291ceSJung-uk Kim goto err; 10663b4e3dcbSSimon L. B. Nielsen 10676f9291ceSJung-uk Kim if (!BN_set_bit(u, p[0] - 1)) 10686f9291ceSJung-uk Kim goto err; 10693b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_exp_arr(r, a, u, p, ctx); 10703b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 10713b4e3dcbSSimon L. B. Nielsen 10723b4e3dcbSSimon L. B. Nielsen err: 10733b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 10743b4e3dcbSSimon L. B. Nielsen return ret; 10753b4e3dcbSSimon L. B. Nielsen } 10763b4e3dcbSSimon L. B. Nielsen 10776f9291ceSJung-uk Kim /* 10786f9291ceSJung-uk Kim * Compute the square root of a, reduce modulo p, and store the result in r. 10796f9291ceSJung-uk Kim * r could be a. This function calls down to the BN_GF2m_mod_sqrt_arr 10806f9291ceSJung-uk Kim * implementation; this wrapper function is only provided for convenience; 10816f9291ceSJung-uk Kim * for best performance, use the BN_GF2m_mod_sqrt_arr function. 10823b4e3dcbSSimon L. B. Nielsen */ 10833b4e3dcbSSimon L. B. Nielsen int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) 10843b4e3dcbSSimon L. B. Nielsen { 10853b4e3dcbSSimon L. B. Nielsen int ret = 0; 10861f13597dSJung-uk Kim const int max = BN_num_bits(p) + 1; 10871f13597dSJung-uk Kim int *arr = NULL; 10883b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 10893b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 10906f9291ceSJung-uk Kim if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) 10916f9291ceSJung-uk Kim goto err; 10923b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_poly2arr(p, arr, max); 10936f9291ceSJung-uk Kim if (!ret || ret > max) { 10943b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD_SQRT, BN_R_INVALID_LENGTH); 10953b4e3dcbSSimon L. B. Nielsen goto err; 10963b4e3dcbSSimon L. B. Nielsen } 10973b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_sqrt_arr(r, a, arr, ctx); 10983b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 10993b4e3dcbSSimon L. B. Nielsen err: 11006f9291ceSJung-uk Kim if (arr) 11016f9291ceSJung-uk Kim OPENSSL_free(arr); 11023b4e3dcbSSimon L. B. Nielsen return ret; 11033b4e3dcbSSimon L. B. Nielsen } 11043b4e3dcbSSimon L. B. Nielsen 11056f9291ceSJung-uk Kim /* 11066f9291ceSJung-uk Kim * Find r such that r^2 + r = a mod p. r could be a. If no r exists returns 11076f9291ceSJung-uk Kim * 0. Uses algorithms A.4.7 and A.4.6 from IEEE P1363. 11083b4e3dcbSSimon L. B. Nielsen */ 11096f9291ceSJung-uk Kim int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a_, const int p[], 11106f9291ceSJung-uk Kim BN_CTX *ctx) 11113b4e3dcbSSimon L. B. Nielsen { 11121f13597dSJung-uk Kim int ret = 0, count = 0, j; 11133b4e3dcbSSimon L. B. Nielsen BIGNUM *a, *z, *rho, *w, *w2, *tmp; 11143b4e3dcbSSimon L. B. Nielsen 11153b4e3dcbSSimon L. B. Nielsen bn_check_top(a_); 11163b4e3dcbSSimon L. B. Nielsen 11176f9291ceSJung-uk Kim if (!p[0]) { 11183b4e3dcbSSimon L. B. Nielsen /* reduction mod 1 => return 0 */ 11193b4e3dcbSSimon L. B. Nielsen BN_zero(r); 11203b4e3dcbSSimon L. B. Nielsen return 1; 11213b4e3dcbSSimon L. B. Nielsen } 11223b4e3dcbSSimon L. B. Nielsen 11233b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 11243b4e3dcbSSimon L. B. Nielsen a = BN_CTX_get(ctx); 11253b4e3dcbSSimon L. B. Nielsen z = BN_CTX_get(ctx); 11263b4e3dcbSSimon L. B. Nielsen w = BN_CTX_get(ctx); 11276f9291ceSJung-uk Kim if (w == NULL) 11286f9291ceSJung-uk Kim goto err; 11293b4e3dcbSSimon L. B. Nielsen 11306f9291ceSJung-uk Kim if (!BN_GF2m_mod_arr(a, a_, p)) 11316f9291ceSJung-uk Kim goto err; 11323b4e3dcbSSimon L. B. Nielsen 11336f9291ceSJung-uk Kim if (BN_is_zero(a)) { 11343b4e3dcbSSimon L. B. Nielsen BN_zero(r); 11353b4e3dcbSSimon L. B. Nielsen ret = 1; 11363b4e3dcbSSimon L. B. Nielsen goto err; 11373b4e3dcbSSimon L. B. Nielsen } 11383b4e3dcbSSimon L. B. Nielsen 11396f9291ceSJung-uk Kim if (p[0] & 0x1) { /* m is odd */ 11403b4e3dcbSSimon L. B. Nielsen /* compute half-trace of a */ 11416f9291ceSJung-uk Kim if (!BN_copy(z, a)) 11426f9291ceSJung-uk Kim goto err; 11436f9291ceSJung-uk Kim for (j = 1; j <= (p[0] - 1) / 2; j++) { 11446f9291ceSJung-uk Kim if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) 11456f9291ceSJung-uk Kim goto err; 11466f9291ceSJung-uk Kim if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) 11476f9291ceSJung-uk Kim goto err; 11486f9291ceSJung-uk Kim if (!BN_GF2m_add(z, z, a)) 11496f9291ceSJung-uk Kim goto err; 11503b4e3dcbSSimon L. B. Nielsen } 11513b4e3dcbSSimon L. B. Nielsen 11526f9291ceSJung-uk Kim } else { /* m is even */ 11536f9291ceSJung-uk Kim 11543b4e3dcbSSimon L. B. Nielsen rho = BN_CTX_get(ctx); 11553b4e3dcbSSimon L. B. Nielsen w2 = BN_CTX_get(ctx); 11563b4e3dcbSSimon L. B. Nielsen tmp = BN_CTX_get(ctx); 11576f9291ceSJung-uk Kim if (tmp == NULL) 11586f9291ceSJung-uk Kim goto err; 11596f9291ceSJung-uk Kim do { 11606f9291ceSJung-uk Kim if (!BN_rand(rho, p[0], 0, 0)) 11616f9291ceSJung-uk Kim goto err; 11626f9291ceSJung-uk Kim if (!BN_GF2m_mod_arr(rho, rho, p)) 11636f9291ceSJung-uk Kim goto err; 11643b4e3dcbSSimon L. B. Nielsen BN_zero(z); 11656f9291ceSJung-uk Kim if (!BN_copy(w, rho)) 11666f9291ceSJung-uk Kim goto err; 11676f9291ceSJung-uk Kim for (j = 1; j <= p[0] - 1; j++) { 11686f9291ceSJung-uk Kim if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) 11696f9291ceSJung-uk Kim goto err; 11706f9291ceSJung-uk Kim if (!BN_GF2m_mod_sqr_arr(w2, w, p, ctx)) 11716f9291ceSJung-uk Kim goto err; 11726f9291ceSJung-uk Kim if (!BN_GF2m_mod_mul_arr(tmp, w2, a, p, ctx)) 11736f9291ceSJung-uk Kim goto err; 11746f9291ceSJung-uk Kim if (!BN_GF2m_add(z, z, tmp)) 11756f9291ceSJung-uk Kim goto err; 11766f9291ceSJung-uk Kim if (!BN_GF2m_add(w, w2, rho)) 11776f9291ceSJung-uk Kim goto err; 11783b4e3dcbSSimon L. B. Nielsen } 11793b4e3dcbSSimon L. B. Nielsen count++; 11803b4e3dcbSSimon L. B. Nielsen } while (BN_is_zero(w) && (count < MAX_ITERATIONS)); 11816f9291ceSJung-uk Kim if (BN_is_zero(w)) { 11823b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR, BN_R_TOO_MANY_ITERATIONS); 11833b4e3dcbSSimon L. B. Nielsen goto err; 11843b4e3dcbSSimon L. B. Nielsen } 11853b4e3dcbSSimon L. B. Nielsen } 11863b4e3dcbSSimon L. B. Nielsen 11876f9291ceSJung-uk Kim if (!BN_GF2m_mod_sqr_arr(w, z, p, ctx)) 11886f9291ceSJung-uk Kim goto err; 11896f9291ceSJung-uk Kim if (!BN_GF2m_add(w, z, w)) 11906f9291ceSJung-uk Kim goto err; 11916f9291ceSJung-uk Kim if (BN_GF2m_cmp(w, a)) { 11923b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR, BN_R_NO_SOLUTION); 11933b4e3dcbSSimon L. B. Nielsen goto err; 11943b4e3dcbSSimon L. B. Nielsen } 11953b4e3dcbSSimon L. B. Nielsen 11966f9291ceSJung-uk Kim if (!BN_copy(r, z)) 11976f9291ceSJung-uk Kim goto err; 11983b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 11993b4e3dcbSSimon L. B. Nielsen 12003b4e3dcbSSimon L. B. Nielsen ret = 1; 12013b4e3dcbSSimon L. B. Nielsen 12023b4e3dcbSSimon L. B. Nielsen err: 12033b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 12043b4e3dcbSSimon L. B. Nielsen return ret; 12053b4e3dcbSSimon L. B. Nielsen } 12063b4e3dcbSSimon L. B. Nielsen 12076f9291ceSJung-uk Kim /* 12086f9291ceSJung-uk Kim * Find r such that r^2 + r = a mod p. r could be a. If no r exists returns 12096f9291ceSJung-uk Kim * 0. This function calls down to the BN_GF2m_mod_solve_quad_arr 12106f9291ceSJung-uk Kim * implementation; this wrapper function is only provided for convenience; 12116f9291ceSJung-uk Kim * for best performance, use the BN_GF2m_mod_solve_quad_arr function. 12123b4e3dcbSSimon L. B. Nielsen */ 12136f9291ceSJung-uk Kim int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, 12146f9291ceSJung-uk Kim BN_CTX *ctx) 12153b4e3dcbSSimon L. B. Nielsen { 12163b4e3dcbSSimon L. B. Nielsen int ret = 0; 12171f13597dSJung-uk Kim const int max = BN_num_bits(p) + 1; 12181f13597dSJung-uk Kim int *arr = NULL; 12193b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 12203b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 12216f9291ceSJung-uk Kim if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) 12226f9291ceSJung-uk Kim goto err; 12233b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_poly2arr(p, arr, max); 12246f9291ceSJung-uk Kim if (!ret || ret > max) { 12253b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD, BN_R_INVALID_LENGTH); 12263b4e3dcbSSimon L. B. Nielsen goto err; 12273b4e3dcbSSimon L. B. Nielsen } 12283b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_solve_quad_arr(r, a, arr, ctx); 12293b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 12303b4e3dcbSSimon L. B. Nielsen err: 12316f9291ceSJung-uk Kim if (arr) 12326f9291ceSJung-uk Kim OPENSSL_free(arr); 12333b4e3dcbSSimon L. B. Nielsen return ret; 12343b4e3dcbSSimon L. B. Nielsen } 12353b4e3dcbSSimon L. B. Nielsen 12366f9291ceSJung-uk Kim /* 12376f9291ceSJung-uk Kim * Convert the bit-string representation of a polynomial ( \sum_{i=0}^n a_i * 12386f9291ceSJung-uk Kim * x^i) into an array of integers corresponding to the bits with non-zero 12396f9291ceSJung-uk Kim * coefficient. Array is terminated with -1. Up to max elements of the array 12406f9291ceSJung-uk Kim * will be filled. Return value is total number of array elements that would 12416f9291ceSJung-uk Kim * be filled if array was large enough. 12423b4e3dcbSSimon L. B. Nielsen */ 12431f13597dSJung-uk Kim int BN_GF2m_poly2arr(const BIGNUM *a, int p[], int max) 12443b4e3dcbSSimon L. B. Nielsen { 12453b4e3dcbSSimon L. B. Nielsen int i, j, k = 0; 12463b4e3dcbSSimon L. B. Nielsen BN_ULONG mask; 12473b4e3dcbSSimon L. B. Nielsen 12481f13597dSJung-uk Kim if (BN_is_zero(a)) 12493b4e3dcbSSimon L. B. Nielsen return 0; 12503b4e3dcbSSimon L. B. Nielsen 12516f9291ceSJung-uk Kim for (i = a->top - 1; i >= 0; i--) { 12523b4e3dcbSSimon L. B. Nielsen if (!a->d[i]) 12533b4e3dcbSSimon L. B. Nielsen /* skip word if a->d[i] == 0 */ 12543b4e3dcbSSimon L. B. Nielsen continue; 12553b4e3dcbSSimon L. B. Nielsen mask = BN_TBIT; 12566f9291ceSJung-uk Kim for (j = BN_BITS2 - 1; j >= 0; j--) { 12576f9291ceSJung-uk Kim if (a->d[i] & mask) { 12586f9291ceSJung-uk Kim if (k < max) 12596f9291ceSJung-uk Kim p[k] = BN_BITS2 * i + j; 12603b4e3dcbSSimon L. B. Nielsen k++; 12613b4e3dcbSSimon L. B. Nielsen } 12623b4e3dcbSSimon L. B. Nielsen mask >>= 1; 12633b4e3dcbSSimon L. B. Nielsen } 12643b4e3dcbSSimon L. B. Nielsen } 12653b4e3dcbSSimon L. B. Nielsen 12661f13597dSJung-uk Kim if (k < max) { 12671f13597dSJung-uk Kim p[k] = -1; 12681f13597dSJung-uk Kim k++; 12691f13597dSJung-uk Kim } 12701f13597dSJung-uk Kim 12713b4e3dcbSSimon L. B. Nielsen return k; 12723b4e3dcbSSimon L. B. Nielsen } 12733b4e3dcbSSimon L. B. Nielsen 12746f9291ceSJung-uk Kim /* 12756f9291ceSJung-uk Kim * Convert the coefficient array representation of a polynomial to a 12761f13597dSJung-uk Kim * bit-string. The array must be terminated by -1. 12773b4e3dcbSSimon L. B. Nielsen */ 12781f13597dSJung-uk Kim int BN_GF2m_arr2poly(const int p[], BIGNUM *a) 12793b4e3dcbSSimon L. B. Nielsen { 12803b4e3dcbSSimon L. B. Nielsen int i; 12813b4e3dcbSSimon L. B. Nielsen 12823b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 12833b4e3dcbSSimon L. B. Nielsen BN_zero(a); 12846f9291ceSJung-uk Kim for (i = 0; p[i] != -1; i++) { 12853b4e3dcbSSimon L. B. Nielsen if (BN_set_bit(a, p[i]) == 0) 12863b4e3dcbSSimon L. B. Nielsen return 0; 12873b4e3dcbSSimon L. B. Nielsen } 12883b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 12893b4e3dcbSSimon L. B. Nielsen 12903b4e3dcbSSimon L. B. Nielsen return 1; 12913b4e3dcbSSimon L. B. Nielsen } 12923b4e3dcbSSimon L. B. Nielsen 12931f13597dSJung-uk Kim #endif 1294