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); 4537bded2dbSJung-uk Kim if (d0 && (tmp_ulong = zz >> d1)) 4543b4e3dcbSSimon L. B. Nielsen z[n + 1] ^= tmp_ulong; 4553b4e3dcbSSimon L. B. Nielsen } 4563b4e3dcbSSimon L. B. Nielsen 4573b4e3dcbSSimon L. B. Nielsen } 4583b4e3dcbSSimon L. B. Nielsen 4593b4e3dcbSSimon L. B. Nielsen bn_correct_top(r); 4603b4e3dcbSSimon L. B. Nielsen return 1; 4613b4e3dcbSSimon L. B. Nielsen } 4623b4e3dcbSSimon L. B. Nielsen 4636f9291ceSJung-uk Kim /* 4646f9291ceSJung-uk Kim * Performs modular reduction of a by p and store result in r. r could be a. 4653b4e3dcbSSimon L. B. Nielsen * This function calls down to the BN_GF2m_mod_arr implementation; this wrapper 4663b4e3dcbSSimon L. B. Nielsen * function is only provided for convenience; for best performance, use the 4673b4e3dcbSSimon L. B. Nielsen * BN_GF2m_mod_arr function. 4683b4e3dcbSSimon L. B. Nielsen */ 4693b4e3dcbSSimon L. B. Nielsen int BN_GF2m_mod(BIGNUM *r, const BIGNUM *a, const BIGNUM *p) 4703b4e3dcbSSimon L. B. Nielsen { 4713b4e3dcbSSimon L. B. Nielsen int ret = 0; 4721f13597dSJung-uk Kim int arr[6]; 4733b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 4743b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 4751f13597dSJung-uk Kim ret = BN_GF2m_poly2arr(p, arr, sizeof(arr) / sizeof(arr[0])); 4766f9291ceSJung-uk Kim if (!ret || ret > (int)(sizeof(arr) / sizeof(arr[0]))) { 4773b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD, BN_R_INVALID_LENGTH); 4781f13597dSJung-uk Kim return 0; 4793b4e3dcbSSimon L. B. Nielsen } 4803b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_arr(r, a, arr); 4813b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 4823b4e3dcbSSimon L. B. Nielsen return ret; 4833b4e3dcbSSimon L. B. Nielsen } 4843b4e3dcbSSimon L. B. Nielsen 4856f9291ceSJung-uk Kim /* 4866f9291ceSJung-uk Kim * Compute the product of two polynomials a and b, reduce modulo p, and store 4873b4e3dcbSSimon L. B. Nielsen * the result in r. r could be a or b; a could be b. 4883b4e3dcbSSimon L. B. Nielsen */ 4896f9291ceSJung-uk Kim int BN_GF2m_mod_mul_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 4906f9291ceSJung-uk Kim const int p[], BN_CTX *ctx) 4913b4e3dcbSSimon L. B. Nielsen { 4923b4e3dcbSSimon L. B. Nielsen int zlen, i, j, k, ret = 0; 4933b4e3dcbSSimon L. B. Nielsen BIGNUM *s; 4943b4e3dcbSSimon L. B. Nielsen BN_ULONG x1, x0, y1, y0, zz[4]; 4953b4e3dcbSSimon L. B. Nielsen 4963b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 4973b4e3dcbSSimon L. B. Nielsen bn_check_top(b); 4983b4e3dcbSSimon L. B. Nielsen 4996f9291ceSJung-uk Kim if (a == b) { 5003b4e3dcbSSimon L. B. Nielsen return BN_GF2m_mod_sqr_arr(r, a, p, ctx); 5013b4e3dcbSSimon L. B. Nielsen } 5023b4e3dcbSSimon L. B. Nielsen 5033b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 5046f9291ceSJung-uk Kim if ((s = BN_CTX_get(ctx)) == NULL) 5056f9291ceSJung-uk Kim goto err; 5063b4e3dcbSSimon L. B. Nielsen 5073b4e3dcbSSimon L. B. Nielsen zlen = a->top + b->top + 4; 5086f9291ceSJung-uk Kim if (!bn_wexpand(s, zlen)) 5096f9291ceSJung-uk Kim goto err; 5103b4e3dcbSSimon L. B. Nielsen s->top = zlen; 5113b4e3dcbSSimon L. B. Nielsen 5126f9291ceSJung-uk Kim for (i = 0; i < zlen; i++) 5136f9291ceSJung-uk Kim s->d[i] = 0; 5143b4e3dcbSSimon L. B. Nielsen 5156f9291ceSJung-uk Kim for (j = 0; j < b->top; j += 2) { 5163b4e3dcbSSimon L. B. Nielsen y0 = b->d[j]; 5173b4e3dcbSSimon L. B. Nielsen y1 = ((j + 1) == b->top) ? 0 : b->d[j + 1]; 5186f9291ceSJung-uk Kim for (i = 0; i < a->top; i += 2) { 5193b4e3dcbSSimon L. B. Nielsen x0 = a->d[i]; 5203b4e3dcbSSimon L. B. Nielsen x1 = ((i + 1) == a->top) ? 0 : a->d[i + 1]; 5213b4e3dcbSSimon L. B. Nielsen bn_GF2m_mul_2x2(zz, x1, x0, y1, y0); 5226f9291ceSJung-uk Kim for (k = 0; k < 4; k++) 5236f9291ceSJung-uk Kim s->d[i + j + k] ^= zz[k]; 5243b4e3dcbSSimon L. B. Nielsen } 5253b4e3dcbSSimon L. B. Nielsen } 5263b4e3dcbSSimon L. B. Nielsen 5273b4e3dcbSSimon L. B. Nielsen bn_correct_top(s); 5283b4e3dcbSSimon L. B. Nielsen if (BN_GF2m_mod_arr(r, s, p)) 5293b4e3dcbSSimon L. B. Nielsen ret = 1; 5303b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 5313b4e3dcbSSimon L. B. Nielsen 5323b4e3dcbSSimon L. B. Nielsen err: 5333b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 5343b4e3dcbSSimon L. B. Nielsen return ret; 5353b4e3dcbSSimon L. B. Nielsen } 5363b4e3dcbSSimon L. B. Nielsen 5376f9291ceSJung-uk Kim /* 5386f9291ceSJung-uk Kim * Compute the product of two polynomials a and b, reduce modulo p, and store 5396f9291ceSJung-uk Kim * the result in r. r could be a or b; a could equal b. This function calls 5406f9291ceSJung-uk Kim * down to the BN_GF2m_mod_mul_arr implementation; this wrapper function is 5416f9291ceSJung-uk Kim * only provided for convenience; for best performance, use the 5423b4e3dcbSSimon L. B. Nielsen * BN_GF2m_mod_mul_arr function. 5433b4e3dcbSSimon L. B. Nielsen */ 5446f9291ceSJung-uk Kim int BN_GF2m_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 5456f9291ceSJung-uk Kim const BIGNUM *p, BN_CTX *ctx) 5463b4e3dcbSSimon L. B. Nielsen { 5473b4e3dcbSSimon L. B. Nielsen int ret = 0; 5481f13597dSJung-uk Kim const int max = BN_num_bits(p) + 1; 5491f13597dSJung-uk Kim int *arr = NULL; 5503b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 5513b4e3dcbSSimon L. B. Nielsen bn_check_top(b); 5523b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 5536f9291ceSJung-uk Kim if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) 5546f9291ceSJung-uk Kim goto err; 5553b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_poly2arr(p, arr, max); 5566f9291ceSJung-uk Kim if (!ret || ret > max) { 5573b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD_MUL, BN_R_INVALID_LENGTH); 5583b4e3dcbSSimon L. B. Nielsen goto err; 5593b4e3dcbSSimon L. B. Nielsen } 5603b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_mul_arr(r, a, b, arr, ctx); 5613b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 5623b4e3dcbSSimon L. B. Nielsen err: 5636f9291ceSJung-uk Kim if (arr) 5646f9291ceSJung-uk Kim OPENSSL_free(arr); 5653b4e3dcbSSimon L. B. Nielsen return ret; 5663b4e3dcbSSimon L. B. Nielsen } 5673b4e3dcbSSimon L. B. Nielsen 5683b4e3dcbSSimon L. B. Nielsen /* Square a, reduce the result mod p, and store it in a. r could be a. */ 5696f9291ceSJung-uk Kim int BN_GF2m_mod_sqr_arr(BIGNUM *r, const BIGNUM *a, const int p[], 5706f9291ceSJung-uk Kim BN_CTX *ctx) 5713b4e3dcbSSimon L. B. Nielsen { 5723b4e3dcbSSimon L. B. Nielsen int i, ret = 0; 5733b4e3dcbSSimon L. B. Nielsen BIGNUM *s; 5743b4e3dcbSSimon L. B. Nielsen 5753b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 5763b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 5776f9291ceSJung-uk Kim if ((s = BN_CTX_get(ctx)) == NULL) 57880815a77SJung-uk Kim goto err; 5796f9291ceSJung-uk Kim if (!bn_wexpand(s, 2 * a->top)) 5806f9291ceSJung-uk Kim goto err; 5813b4e3dcbSSimon L. B. Nielsen 5826f9291ceSJung-uk Kim for (i = a->top - 1; i >= 0; i--) { 5833b4e3dcbSSimon L. B. Nielsen s->d[2 * i + 1] = SQR1(a->d[i]); 5843b4e3dcbSSimon L. B. Nielsen s->d[2 * i] = SQR0(a->d[i]); 5853b4e3dcbSSimon L. B. Nielsen } 5863b4e3dcbSSimon L. B. Nielsen 5873b4e3dcbSSimon L. B. Nielsen s->top = 2 * a->top; 5883b4e3dcbSSimon L. B. Nielsen bn_correct_top(s); 5896f9291ceSJung-uk Kim if (!BN_GF2m_mod_arr(r, s, p)) 5906f9291ceSJung-uk Kim goto err; 5913b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 5923b4e3dcbSSimon L. B. Nielsen ret = 1; 5933b4e3dcbSSimon L. B. Nielsen err: 5943b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 5953b4e3dcbSSimon L. B. Nielsen return ret; 5963b4e3dcbSSimon L. B. Nielsen } 5973b4e3dcbSSimon L. B. Nielsen 5986f9291ceSJung-uk Kim /* 5996f9291ceSJung-uk Kim * Square a, reduce the result mod p, and store it in a. r could be a. This 6006f9291ceSJung-uk Kim * function calls down to the BN_GF2m_mod_sqr_arr implementation; this 6016f9291ceSJung-uk Kim * wrapper function is only provided for convenience; for best performance, 6026f9291ceSJung-uk Kim * use the BN_GF2m_mod_sqr_arr function. 6033b4e3dcbSSimon L. B. Nielsen */ 6043b4e3dcbSSimon L. B. Nielsen int BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) 6053b4e3dcbSSimon L. B. Nielsen { 6063b4e3dcbSSimon L. B. Nielsen int ret = 0; 6071f13597dSJung-uk Kim const int max = BN_num_bits(p) + 1; 6081f13597dSJung-uk Kim int *arr = NULL; 6093b4e3dcbSSimon L. B. Nielsen 6103b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 6113b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 6126f9291ceSJung-uk Kim if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) 6136f9291ceSJung-uk Kim goto err; 6143b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_poly2arr(p, arr, max); 6156f9291ceSJung-uk Kim if (!ret || ret > max) { 6163b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD_SQR, BN_R_INVALID_LENGTH); 6173b4e3dcbSSimon L. B. Nielsen goto err; 6183b4e3dcbSSimon L. B. Nielsen } 6193b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_sqr_arr(r, a, arr, ctx); 6203b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 6213b4e3dcbSSimon L. B. Nielsen err: 6226f9291ceSJung-uk Kim if (arr) 6236f9291ceSJung-uk Kim OPENSSL_free(arr); 6243b4e3dcbSSimon L. B. Nielsen return ret; 6253b4e3dcbSSimon L. B. Nielsen } 6263b4e3dcbSSimon L. B. Nielsen 6276f9291ceSJung-uk Kim /* 6286f9291ceSJung-uk Kim * Invert a, reduce modulo p, and store the result in r. r could be a. Uses 6296f9291ceSJung-uk Kim * Modified Almost Inverse Algorithm (Algorithm 10) from Hankerson, D., 6306f9291ceSJung-uk Kim * Hernandez, J.L., and Menezes, A. "Software Implementation of Elliptic 6316f9291ceSJung-uk Kim * Curve Cryptography Over Binary Fields". 6323b4e3dcbSSimon L. B. Nielsen */ 6333b4e3dcbSSimon L. B. Nielsen int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) 6343b4e3dcbSSimon L. B. Nielsen { 6351f13597dSJung-uk Kim BIGNUM *b, *c = NULL, *u = NULL, *v = NULL, *tmp; 6363b4e3dcbSSimon L. B. Nielsen int ret = 0; 6373b4e3dcbSSimon L. B. Nielsen 6383b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 6393b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 6403b4e3dcbSSimon L. B. Nielsen 6413b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 6423b4e3dcbSSimon L. B. Nielsen 6436f9291ceSJung-uk Kim if ((b = BN_CTX_get(ctx)) == NULL) 6446f9291ceSJung-uk Kim goto err; 6456f9291ceSJung-uk Kim if ((c = BN_CTX_get(ctx)) == NULL) 6466f9291ceSJung-uk Kim goto err; 6476f9291ceSJung-uk Kim if ((u = BN_CTX_get(ctx)) == NULL) 6486f9291ceSJung-uk Kim goto err; 6496f9291ceSJung-uk Kim if ((v = BN_CTX_get(ctx)) == NULL) 6506f9291ceSJung-uk Kim goto err; 6513b4e3dcbSSimon L. B. Nielsen 6526f9291ceSJung-uk Kim if (!BN_GF2m_mod(u, a, p)) 6536f9291ceSJung-uk Kim goto err; 6546f9291ceSJung-uk Kim if (BN_is_zero(u)) 6556f9291ceSJung-uk Kim goto err; 6563b4e3dcbSSimon L. B. Nielsen 6576f9291ceSJung-uk Kim if (!BN_copy(v, p)) 6586f9291ceSJung-uk Kim goto err; 6591f13597dSJung-uk Kim # if 0 6606f9291ceSJung-uk Kim if (!BN_one(b)) 6616f9291ceSJung-uk Kim goto err; 6621f13597dSJung-uk Kim 6636f9291ceSJung-uk Kim while (1) { 6646f9291ceSJung-uk Kim while (!BN_is_odd(u)) { 6656f9291ceSJung-uk Kim if (BN_is_zero(u)) 6666f9291ceSJung-uk Kim goto err; 6676f9291ceSJung-uk Kim if (!BN_rshift1(u, u)) 6686f9291ceSJung-uk Kim goto err; 6696f9291ceSJung-uk Kim if (BN_is_odd(b)) { 6706f9291ceSJung-uk Kim if (!BN_GF2m_add(b, b, p)) 6716f9291ceSJung-uk Kim goto err; 6723b4e3dcbSSimon L. B. Nielsen } 6736f9291ceSJung-uk Kim if (!BN_rshift1(b, b)) 6746f9291ceSJung-uk Kim goto err; 6753b4e3dcbSSimon L. B. Nielsen } 6763b4e3dcbSSimon L. B. Nielsen 6776f9291ceSJung-uk Kim if (BN_abs_is_word(u, 1)) 6786f9291ceSJung-uk Kim break; 6793b4e3dcbSSimon L. B. Nielsen 6806f9291ceSJung-uk Kim if (BN_num_bits(u) < BN_num_bits(v)) { 6816f9291ceSJung-uk Kim tmp = u; 6826f9291ceSJung-uk Kim u = v; 6836f9291ceSJung-uk Kim v = tmp; 6846f9291ceSJung-uk Kim tmp = b; 6856f9291ceSJung-uk Kim b = c; 6866f9291ceSJung-uk Kim c = tmp; 6873b4e3dcbSSimon L. B. Nielsen } 6883b4e3dcbSSimon L. B. Nielsen 6896f9291ceSJung-uk Kim if (!BN_GF2m_add(u, u, v)) 6906f9291ceSJung-uk Kim goto err; 6916f9291ceSJung-uk Kim if (!BN_GF2m_add(b, b, c)) 6926f9291ceSJung-uk Kim goto err; 6933b4e3dcbSSimon L. B. Nielsen } 6941f13597dSJung-uk Kim # else 6951f13597dSJung-uk Kim { 696ed6b93beSJung-uk Kim int i; 697ed6b93beSJung-uk Kim int ubits = BN_num_bits(u); 698ed6b93beSJung-uk Kim int vbits = BN_num_bits(v); /* v is copy of p */ 699ed6b93beSJung-uk Kim int top = p->top; 7001f13597dSJung-uk Kim BN_ULONG *udp, *bdp, *vdp, *cdp; 7013b4e3dcbSSimon L. B. Nielsen 70280815a77SJung-uk Kim if (!bn_wexpand(u, top)) 70380815a77SJung-uk Kim goto err; 7046f9291ceSJung-uk Kim udp = u->d; 7056f9291ceSJung-uk Kim for (i = u->top; i < top; i++) 7066f9291ceSJung-uk Kim udp[i] = 0; 7071f13597dSJung-uk Kim u->top = top; 70880815a77SJung-uk Kim if (!bn_wexpand(b, top)) 70980815a77SJung-uk Kim goto err; 7106f9291ceSJung-uk Kim bdp = b->d; 7111f13597dSJung-uk Kim bdp[0] = 1; 7126f9291ceSJung-uk Kim for (i = 1; i < top; i++) 7136f9291ceSJung-uk Kim bdp[i] = 0; 7141f13597dSJung-uk Kim b->top = top; 71580815a77SJung-uk Kim if (!bn_wexpand(c, top)) 71680815a77SJung-uk Kim goto err; 7176f9291ceSJung-uk Kim cdp = c->d; 7186f9291ceSJung-uk Kim for (i = 0; i < top; i++) 7196f9291ceSJung-uk Kim cdp[i] = 0; 7201f13597dSJung-uk Kim c->top = top; 7216f9291ceSJung-uk Kim vdp = v->d; /* It pays off to "cache" *->d pointers, 7226f9291ceSJung-uk Kim * because it allows optimizer to be more 7236f9291ceSJung-uk Kim * aggressive. But we don't have to "cache" 7246f9291ceSJung-uk Kim * p->d, because *p is declared 'const'... */ 7256f9291ceSJung-uk Kim while (1) { 7266f9291ceSJung-uk Kim while (ubits && !(udp[0] & 1)) { 7271f13597dSJung-uk Kim BN_ULONG u0, u1, b0, b1, mask; 7281f13597dSJung-uk Kim 7291f13597dSJung-uk Kim u0 = udp[0]; 7301f13597dSJung-uk Kim b0 = bdp[0]; 7311f13597dSJung-uk Kim mask = (BN_ULONG)0 - (b0 & 1); 7321f13597dSJung-uk Kim b0 ^= p->d[0] & mask; 7336f9291ceSJung-uk Kim for (i = 0; i < top - 1; i++) { 7341f13597dSJung-uk Kim u1 = udp[i + 1]; 7351f13597dSJung-uk Kim udp[i] = ((u0 >> 1) | (u1 << (BN_BITS2 - 1))) & BN_MASK2; 7361f13597dSJung-uk Kim u0 = u1; 7371f13597dSJung-uk Kim b1 = bdp[i + 1] ^ (p->d[i + 1] & mask); 7381f13597dSJung-uk Kim bdp[i] = ((b0 >> 1) | (b1 << (BN_BITS2 - 1))) & BN_MASK2; 7391f13597dSJung-uk Kim b0 = b1; 7401f13597dSJung-uk Kim } 7411f13597dSJung-uk Kim udp[i] = u0 >> 1; 7421f13597dSJung-uk Kim bdp[i] = b0 >> 1; 7431f13597dSJung-uk Kim ubits--; 7441f13597dSJung-uk Kim } 7451f13597dSJung-uk Kim 746ed6b93beSJung-uk Kim if (ubits <= BN_BITS2) { 747ed6b93beSJung-uk Kim if (udp[0] == 0) /* poly was reducible */ 748ed6b93beSJung-uk Kim goto err; 749ed6b93beSJung-uk Kim if (udp[0] == 1) 7506f9291ceSJung-uk Kim break; 751ed6b93beSJung-uk Kim } 7521f13597dSJung-uk Kim 7536f9291ceSJung-uk Kim if (ubits < vbits) { 7546f9291ceSJung-uk Kim i = ubits; 7556f9291ceSJung-uk Kim ubits = vbits; 7566f9291ceSJung-uk Kim vbits = i; 7576f9291ceSJung-uk Kim tmp = u; 7586f9291ceSJung-uk Kim u = v; 7596f9291ceSJung-uk Kim v = tmp; 7606f9291ceSJung-uk Kim tmp = b; 7616f9291ceSJung-uk Kim b = c; 7626f9291ceSJung-uk Kim c = tmp; 7636f9291ceSJung-uk Kim udp = vdp; 7646f9291ceSJung-uk Kim vdp = v->d; 7656f9291ceSJung-uk Kim bdp = cdp; 7666f9291ceSJung-uk Kim cdp = c->d; 7671f13597dSJung-uk Kim } 7686f9291ceSJung-uk Kim for (i = 0; i < top; i++) { 7691f13597dSJung-uk Kim udp[i] ^= vdp[i]; 7701f13597dSJung-uk Kim bdp[i] ^= cdp[i]; 7711f13597dSJung-uk Kim } 7726f9291ceSJung-uk Kim if (ubits == vbits) { 7731f13597dSJung-uk Kim BN_ULONG ul; 7741f13597dSJung-uk Kim int utop = (ubits - 1) / BN_BITS2; 7751f13597dSJung-uk Kim 7766f9291ceSJung-uk Kim while ((ul = udp[utop]) == 0 && utop) 7776f9291ceSJung-uk Kim utop--; 7781f13597dSJung-uk Kim ubits = utop * BN_BITS2 + BN_num_bits_word(ul); 7791f13597dSJung-uk Kim } 7801f13597dSJung-uk Kim } 7811f13597dSJung-uk Kim bn_correct_top(b); 7821f13597dSJung-uk Kim } 7831f13597dSJung-uk Kim # endif 7843b4e3dcbSSimon L. B. Nielsen 7856f9291ceSJung-uk Kim if (!BN_copy(r, b)) 7866f9291ceSJung-uk Kim goto err; 7873b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 7883b4e3dcbSSimon L. B. Nielsen ret = 1; 7893b4e3dcbSSimon L. B. Nielsen 7903b4e3dcbSSimon L. B. Nielsen err: 7916f9291ceSJung-uk Kim # ifdef BN_DEBUG /* BN_CTX_end would complain about the 7926f9291ceSJung-uk Kim * expanded form */ 7931f13597dSJung-uk Kim bn_correct_top(c); 7941f13597dSJung-uk Kim bn_correct_top(u); 7951f13597dSJung-uk Kim bn_correct_top(v); 7961f13597dSJung-uk Kim # endif 7973b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 7983b4e3dcbSSimon L. B. Nielsen return ret; 7993b4e3dcbSSimon L. B. Nielsen } 8003b4e3dcbSSimon L. B. Nielsen 8016f9291ceSJung-uk Kim /* 8026f9291ceSJung-uk Kim * Invert xx, reduce modulo p, and store the result in r. r could be xx. 8036f9291ceSJung-uk Kim * This function calls down to the BN_GF2m_mod_inv implementation; this 8046f9291ceSJung-uk Kim * wrapper function is only provided for convenience; for best performance, 8056f9291ceSJung-uk Kim * use the BN_GF2m_mod_inv function. 8063b4e3dcbSSimon L. B. Nielsen */ 8076f9291ceSJung-uk Kim int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const int p[], 8086f9291ceSJung-uk Kim BN_CTX *ctx) 8093b4e3dcbSSimon L. B. Nielsen { 8103b4e3dcbSSimon L. B. Nielsen BIGNUM *field; 8113b4e3dcbSSimon L. B. Nielsen int ret = 0; 8123b4e3dcbSSimon L. B. Nielsen 8133b4e3dcbSSimon L. B. Nielsen bn_check_top(xx); 8143b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 8156f9291ceSJung-uk Kim if ((field = BN_CTX_get(ctx)) == NULL) 8166f9291ceSJung-uk Kim goto err; 8176f9291ceSJung-uk Kim if (!BN_GF2m_arr2poly(p, field)) 8186f9291ceSJung-uk Kim goto err; 8193b4e3dcbSSimon L. B. Nielsen 8203b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_inv(r, xx, field, ctx); 8213b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 8223b4e3dcbSSimon L. B. Nielsen 8233b4e3dcbSSimon L. B. Nielsen err: 8243b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 8253b4e3dcbSSimon L. B. Nielsen return ret; 8263b4e3dcbSSimon L. B. Nielsen } 8273b4e3dcbSSimon L. B. Nielsen 8283b4e3dcbSSimon L. B. Nielsen # ifndef OPENSSL_SUN_GF2M_DIV 8296f9291ceSJung-uk Kim /* 8306f9291ceSJung-uk Kim * Divide y by x, reduce modulo p, and store the result in r. r could be x 8313b4e3dcbSSimon L. B. Nielsen * or y, x could equal y. 8323b4e3dcbSSimon L. B. Nielsen */ 8336f9291ceSJung-uk Kim int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, 8346f9291ceSJung-uk Kim const BIGNUM *p, BN_CTX *ctx) 8353b4e3dcbSSimon L. B. Nielsen { 8363b4e3dcbSSimon L. B. Nielsen BIGNUM *xinv = NULL; 8373b4e3dcbSSimon L. B. Nielsen int ret = 0; 8383b4e3dcbSSimon L. B. Nielsen 8393b4e3dcbSSimon L. B. Nielsen bn_check_top(y); 8403b4e3dcbSSimon L. B. Nielsen bn_check_top(x); 8413b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 8423b4e3dcbSSimon L. B. Nielsen 8433b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 8443b4e3dcbSSimon L. B. Nielsen xinv = BN_CTX_get(ctx); 8456f9291ceSJung-uk Kim if (xinv == NULL) 8466f9291ceSJung-uk Kim goto err; 8473b4e3dcbSSimon L. B. Nielsen 8486f9291ceSJung-uk Kim if (!BN_GF2m_mod_inv(xinv, x, p, ctx)) 8496f9291ceSJung-uk Kim goto err; 8506f9291ceSJung-uk Kim if (!BN_GF2m_mod_mul(r, y, xinv, p, ctx)) 8516f9291ceSJung-uk Kim goto err; 8523b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 8533b4e3dcbSSimon L. B. Nielsen ret = 1; 8543b4e3dcbSSimon L. B. Nielsen 8553b4e3dcbSSimon L. B. Nielsen err: 8563b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 8573b4e3dcbSSimon L. B. Nielsen return ret; 8583b4e3dcbSSimon L. B. Nielsen } 8593b4e3dcbSSimon L. B. Nielsen # else 8606f9291ceSJung-uk Kim /* 8616f9291ceSJung-uk Kim * Divide y by x, reduce modulo p, and store the result in r. r could be x 8626f9291ceSJung-uk Kim * or y, x could equal y. Uses algorithm Modular_Division_GF(2^m) from 8636f9291ceSJung-uk Kim * Chang-Shantz, S. "From Euclid's GCD to Montgomery Multiplication to the 8646f9291ceSJung-uk Kim * Great Divide". 8653b4e3dcbSSimon L. B. Nielsen */ 8666f9291ceSJung-uk Kim int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, 8676f9291ceSJung-uk Kim const BIGNUM *p, BN_CTX *ctx) 8683b4e3dcbSSimon L. B. Nielsen { 8693b4e3dcbSSimon L. B. Nielsen BIGNUM *a, *b, *u, *v; 8703b4e3dcbSSimon L. B. Nielsen int ret = 0; 8713b4e3dcbSSimon L. B. Nielsen 8723b4e3dcbSSimon L. B. Nielsen bn_check_top(y); 8733b4e3dcbSSimon L. B. Nielsen bn_check_top(x); 8743b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 8753b4e3dcbSSimon L. B. Nielsen 8763b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 8773b4e3dcbSSimon L. B. Nielsen 8783b4e3dcbSSimon L. B. Nielsen a = BN_CTX_get(ctx); 8793b4e3dcbSSimon L. B. Nielsen b = BN_CTX_get(ctx); 8803b4e3dcbSSimon L. B. Nielsen u = BN_CTX_get(ctx); 8813b4e3dcbSSimon L. B. Nielsen v = BN_CTX_get(ctx); 8826f9291ceSJung-uk Kim if (v == NULL) 8836f9291ceSJung-uk Kim goto err; 8843b4e3dcbSSimon L. B. Nielsen 8853b4e3dcbSSimon L. B. Nielsen /* reduce x and y mod p */ 8866f9291ceSJung-uk Kim if (!BN_GF2m_mod(u, y, p)) 8876f9291ceSJung-uk Kim goto err; 8886f9291ceSJung-uk Kim if (!BN_GF2m_mod(a, x, p)) 8896f9291ceSJung-uk Kim goto err; 8906f9291ceSJung-uk Kim if (!BN_copy(b, p)) 8916f9291ceSJung-uk Kim goto err; 8923b4e3dcbSSimon L. B. Nielsen 8936f9291ceSJung-uk Kim while (!BN_is_odd(a)) { 8946f9291ceSJung-uk Kim if (!BN_rshift1(a, a)) 8956f9291ceSJung-uk Kim goto err; 8966f9291ceSJung-uk Kim if (BN_is_odd(u)) 8976f9291ceSJung-uk Kim if (!BN_GF2m_add(u, u, p)) 8986f9291ceSJung-uk Kim goto err; 8996f9291ceSJung-uk Kim if (!BN_rshift1(u, u)) 9006f9291ceSJung-uk Kim goto err; 9013b4e3dcbSSimon L. B. Nielsen } 9023b4e3dcbSSimon L. B. Nielsen 9036f9291ceSJung-uk Kim do { 9046f9291ceSJung-uk Kim if (BN_GF2m_cmp(b, a) > 0) { 9056f9291ceSJung-uk Kim if (!BN_GF2m_add(b, b, a)) 9066f9291ceSJung-uk Kim goto err; 9076f9291ceSJung-uk Kim if (!BN_GF2m_add(v, v, u)) 9086f9291ceSJung-uk Kim goto err; 9096f9291ceSJung-uk Kim do { 9106f9291ceSJung-uk Kim if (!BN_rshift1(b, b)) 9116f9291ceSJung-uk Kim goto err; 9126f9291ceSJung-uk Kim if (BN_is_odd(v)) 9136f9291ceSJung-uk Kim if (!BN_GF2m_add(v, v, p)) 9146f9291ceSJung-uk Kim goto err; 9156f9291ceSJung-uk Kim if (!BN_rshift1(v, v)) 9166f9291ceSJung-uk Kim goto err; 9173b4e3dcbSSimon L. B. Nielsen } while (!BN_is_odd(b)); 9186f9291ceSJung-uk Kim } else if (BN_abs_is_word(a, 1)) 9193b4e3dcbSSimon L. B. Nielsen break; 9206f9291ceSJung-uk Kim else { 9216f9291ceSJung-uk Kim if (!BN_GF2m_add(a, a, b)) 9226f9291ceSJung-uk Kim goto err; 9236f9291ceSJung-uk Kim if (!BN_GF2m_add(u, u, v)) 9246f9291ceSJung-uk Kim goto err; 9256f9291ceSJung-uk Kim do { 9266f9291ceSJung-uk Kim if (!BN_rshift1(a, a)) 9276f9291ceSJung-uk Kim goto err; 9286f9291ceSJung-uk Kim if (BN_is_odd(u)) 9296f9291ceSJung-uk Kim if (!BN_GF2m_add(u, u, p)) 9306f9291ceSJung-uk Kim goto err; 9316f9291ceSJung-uk Kim if (!BN_rshift1(u, u)) 9326f9291ceSJung-uk Kim goto err; 9333b4e3dcbSSimon L. B. Nielsen } while (!BN_is_odd(a)); 9343b4e3dcbSSimon L. B. Nielsen } 9353b4e3dcbSSimon L. B. Nielsen } while (1); 9363b4e3dcbSSimon L. B. Nielsen 9376f9291ceSJung-uk Kim if (!BN_copy(r, u)) 9386f9291ceSJung-uk Kim goto err; 9393b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 9403b4e3dcbSSimon L. B. Nielsen ret = 1; 9413b4e3dcbSSimon L. B. Nielsen 9423b4e3dcbSSimon L. B. Nielsen err: 9433b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 9443b4e3dcbSSimon L. B. Nielsen return ret; 9453b4e3dcbSSimon L. B. Nielsen } 9463b4e3dcbSSimon L. B. Nielsen # endif 9473b4e3dcbSSimon L. B. Nielsen 9486f9291ceSJung-uk Kim /* 9496f9291ceSJung-uk Kim * Divide yy by xx, reduce modulo p, and store the result in r. r could be xx 9506f9291ceSJung-uk Kim * * or yy, xx could equal yy. This function calls down to the 9516f9291ceSJung-uk Kim * BN_GF2m_mod_div implementation; this wrapper function is only provided for 9526f9291ceSJung-uk Kim * convenience; for best performance, use the BN_GF2m_mod_div function. 9533b4e3dcbSSimon L. B. Nielsen */ 9546f9291ceSJung-uk Kim int BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *yy, const BIGNUM *xx, 9556f9291ceSJung-uk Kim const int p[], BN_CTX *ctx) 9563b4e3dcbSSimon L. B. Nielsen { 9573b4e3dcbSSimon L. B. Nielsen BIGNUM *field; 9583b4e3dcbSSimon L. B. Nielsen int ret = 0; 9593b4e3dcbSSimon L. B. Nielsen 9603b4e3dcbSSimon L. B. Nielsen bn_check_top(yy); 9613b4e3dcbSSimon L. B. Nielsen bn_check_top(xx); 9623b4e3dcbSSimon L. B. Nielsen 9633b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 9646f9291ceSJung-uk Kim if ((field = BN_CTX_get(ctx)) == NULL) 9656f9291ceSJung-uk Kim goto err; 9666f9291ceSJung-uk Kim if (!BN_GF2m_arr2poly(p, field)) 9676f9291ceSJung-uk Kim goto err; 9683b4e3dcbSSimon L. B. Nielsen 9693b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_div(r, yy, xx, field, ctx); 9703b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 9713b4e3dcbSSimon L. B. Nielsen 9723b4e3dcbSSimon L. B. Nielsen err: 9733b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 9743b4e3dcbSSimon L. B. Nielsen return ret; 9753b4e3dcbSSimon L. B. Nielsen } 9763b4e3dcbSSimon L. B. Nielsen 9776f9291ceSJung-uk Kim /* 9786f9291ceSJung-uk Kim * Compute the bth power of a, reduce modulo p, and store the result in r. r 9796f9291ceSJung-uk Kim * could be a. Uses simple square-and-multiply algorithm A.5.1 from IEEE 9806f9291ceSJung-uk Kim * P1363. 9813b4e3dcbSSimon L. B. Nielsen */ 9826f9291ceSJung-uk Kim int BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 9836f9291ceSJung-uk Kim const int p[], BN_CTX *ctx) 9843b4e3dcbSSimon L. B. Nielsen { 9853b4e3dcbSSimon L. B. Nielsen int ret = 0, i, n; 9863b4e3dcbSSimon L. B. Nielsen BIGNUM *u; 9873b4e3dcbSSimon L. B. Nielsen 9883b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 9893b4e3dcbSSimon L. B. Nielsen bn_check_top(b); 9903b4e3dcbSSimon L. B. Nielsen 9913b4e3dcbSSimon L. B. Nielsen if (BN_is_zero(b)) 9923b4e3dcbSSimon L. B. Nielsen return (BN_one(r)); 9933b4e3dcbSSimon L. B. Nielsen 9943b4e3dcbSSimon L. B. Nielsen if (BN_abs_is_word(b, 1)) 9953b4e3dcbSSimon L. B. Nielsen return (BN_copy(r, a) != NULL); 9963b4e3dcbSSimon L. B. Nielsen 9973b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 9986f9291ceSJung-uk Kim if ((u = BN_CTX_get(ctx)) == NULL) 9996f9291ceSJung-uk Kim goto err; 10003b4e3dcbSSimon L. B. Nielsen 10016f9291ceSJung-uk Kim if (!BN_GF2m_mod_arr(u, a, p)) 10026f9291ceSJung-uk Kim goto err; 10033b4e3dcbSSimon L. B. Nielsen 10043b4e3dcbSSimon L. B. Nielsen n = BN_num_bits(b) - 1; 10056f9291ceSJung-uk Kim for (i = n - 1; i >= 0; i--) { 10066f9291ceSJung-uk Kim if (!BN_GF2m_mod_sqr_arr(u, u, p, ctx)) 10076f9291ceSJung-uk Kim goto err; 10086f9291ceSJung-uk Kim if (BN_is_bit_set(b, i)) { 10096f9291ceSJung-uk Kim if (!BN_GF2m_mod_mul_arr(u, u, a, p, ctx)) 10106f9291ceSJung-uk Kim goto err; 10113b4e3dcbSSimon L. B. Nielsen } 10123b4e3dcbSSimon L. B. Nielsen } 10136f9291ceSJung-uk Kim if (!BN_copy(r, u)) 10146f9291ceSJung-uk Kim goto err; 10153b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 10163b4e3dcbSSimon L. B. Nielsen ret = 1; 10173b4e3dcbSSimon L. B. Nielsen err: 10183b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 10193b4e3dcbSSimon L. B. Nielsen return ret; 10203b4e3dcbSSimon L. B. Nielsen } 10213b4e3dcbSSimon L. B. Nielsen 10226f9291ceSJung-uk Kim /* 10236f9291ceSJung-uk Kim * Compute the bth power of a, reduce modulo p, and store the result in r. r 10246f9291ceSJung-uk Kim * could be a. This function calls down to the BN_GF2m_mod_exp_arr 10256f9291ceSJung-uk Kim * implementation; this wrapper function is only provided for convenience; 10266f9291ceSJung-uk Kim * for best performance, use the BN_GF2m_mod_exp_arr function. 10273b4e3dcbSSimon L. B. Nielsen */ 10286f9291ceSJung-uk Kim int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 10296f9291ceSJung-uk Kim const BIGNUM *p, BN_CTX *ctx) 10303b4e3dcbSSimon L. B. Nielsen { 10313b4e3dcbSSimon L. B. Nielsen int ret = 0; 10321f13597dSJung-uk Kim const int max = BN_num_bits(p) + 1; 10331f13597dSJung-uk Kim int *arr = NULL; 10343b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 10353b4e3dcbSSimon L. B. Nielsen bn_check_top(b); 10363b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 10376f9291ceSJung-uk Kim if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) 10386f9291ceSJung-uk Kim goto err; 10393b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_poly2arr(p, arr, max); 10406f9291ceSJung-uk Kim if (!ret || ret > max) { 10413b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD_EXP, BN_R_INVALID_LENGTH); 10423b4e3dcbSSimon L. B. Nielsen goto err; 10433b4e3dcbSSimon L. B. Nielsen } 10443b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_exp_arr(r, a, b, arr, ctx); 10453b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 10463b4e3dcbSSimon L. B. Nielsen err: 10476f9291ceSJung-uk Kim if (arr) 10486f9291ceSJung-uk Kim OPENSSL_free(arr); 10493b4e3dcbSSimon L. B. Nielsen return ret; 10503b4e3dcbSSimon L. B. Nielsen } 10513b4e3dcbSSimon L. B. Nielsen 10526f9291ceSJung-uk Kim /* 10536f9291ceSJung-uk Kim * Compute the square root of a, reduce modulo p, and store the result in r. 10546f9291ceSJung-uk Kim * r could be a. Uses exponentiation as in algorithm A.4.1 from IEEE P1363. 10553b4e3dcbSSimon L. B. Nielsen */ 10566f9291ceSJung-uk Kim int BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const int p[], 10576f9291ceSJung-uk Kim BN_CTX *ctx) 10583b4e3dcbSSimon L. B. Nielsen { 10593b4e3dcbSSimon L. B. Nielsen int ret = 0; 10603b4e3dcbSSimon L. B. Nielsen BIGNUM *u; 10613b4e3dcbSSimon L. B. Nielsen 10623b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 10633b4e3dcbSSimon L. B. Nielsen 10646f9291ceSJung-uk Kim if (!p[0]) { 10653b4e3dcbSSimon L. B. Nielsen /* reduction mod 1 => return 0 */ 10663b4e3dcbSSimon L. B. Nielsen BN_zero(r); 10673b4e3dcbSSimon L. B. Nielsen return 1; 10683b4e3dcbSSimon L. B. Nielsen } 10693b4e3dcbSSimon L. B. Nielsen 10703b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 10716f9291ceSJung-uk Kim if ((u = BN_CTX_get(ctx)) == NULL) 10726f9291ceSJung-uk Kim goto err; 10733b4e3dcbSSimon L. B. Nielsen 10746f9291ceSJung-uk Kim if (!BN_set_bit(u, p[0] - 1)) 10756f9291ceSJung-uk Kim goto err; 10763b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_exp_arr(r, a, u, p, ctx); 10773b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 10783b4e3dcbSSimon L. B. Nielsen 10793b4e3dcbSSimon L. B. Nielsen err: 10803b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 10813b4e3dcbSSimon L. B. Nielsen return ret; 10823b4e3dcbSSimon L. B. Nielsen } 10833b4e3dcbSSimon L. B. Nielsen 10846f9291ceSJung-uk Kim /* 10856f9291ceSJung-uk Kim * Compute the square root of a, reduce modulo p, and store the result in r. 10866f9291ceSJung-uk Kim * r could be a. This function calls down to the BN_GF2m_mod_sqrt_arr 10876f9291ceSJung-uk Kim * implementation; this wrapper function is only provided for convenience; 10886f9291ceSJung-uk Kim * for best performance, use the BN_GF2m_mod_sqrt_arr function. 10893b4e3dcbSSimon L. B. Nielsen */ 10903b4e3dcbSSimon L. B. Nielsen int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) 10913b4e3dcbSSimon L. B. Nielsen { 10923b4e3dcbSSimon L. B. Nielsen int ret = 0; 10931f13597dSJung-uk Kim const int max = BN_num_bits(p) + 1; 10941f13597dSJung-uk Kim int *arr = NULL; 10953b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 10963b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 10976f9291ceSJung-uk Kim if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) 10986f9291ceSJung-uk Kim goto err; 10993b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_poly2arr(p, arr, max); 11006f9291ceSJung-uk Kim if (!ret || ret > max) { 11013b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD_SQRT, BN_R_INVALID_LENGTH); 11023b4e3dcbSSimon L. B. Nielsen goto err; 11033b4e3dcbSSimon L. B. Nielsen } 11043b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_sqrt_arr(r, a, arr, ctx); 11053b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 11063b4e3dcbSSimon L. B. Nielsen err: 11076f9291ceSJung-uk Kim if (arr) 11086f9291ceSJung-uk Kim OPENSSL_free(arr); 11093b4e3dcbSSimon L. B. Nielsen return ret; 11103b4e3dcbSSimon L. B. Nielsen } 11113b4e3dcbSSimon L. B. Nielsen 11126f9291ceSJung-uk Kim /* 11136f9291ceSJung-uk Kim * Find r such that r^2 + r = a mod p. r could be a. If no r exists returns 11146f9291ceSJung-uk Kim * 0. Uses algorithms A.4.7 and A.4.6 from IEEE P1363. 11153b4e3dcbSSimon L. B. Nielsen */ 11166f9291ceSJung-uk Kim int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a_, const int p[], 11176f9291ceSJung-uk Kim BN_CTX *ctx) 11183b4e3dcbSSimon L. B. Nielsen { 11191f13597dSJung-uk Kim int ret = 0, count = 0, j; 11203b4e3dcbSSimon L. B. Nielsen BIGNUM *a, *z, *rho, *w, *w2, *tmp; 11213b4e3dcbSSimon L. B. Nielsen 11223b4e3dcbSSimon L. B. Nielsen bn_check_top(a_); 11233b4e3dcbSSimon L. B. Nielsen 11246f9291ceSJung-uk Kim if (!p[0]) { 11253b4e3dcbSSimon L. B. Nielsen /* reduction mod 1 => return 0 */ 11263b4e3dcbSSimon L. B. Nielsen BN_zero(r); 11273b4e3dcbSSimon L. B. Nielsen return 1; 11283b4e3dcbSSimon L. B. Nielsen } 11293b4e3dcbSSimon L. B. Nielsen 11303b4e3dcbSSimon L. B. Nielsen BN_CTX_start(ctx); 11313b4e3dcbSSimon L. B. Nielsen a = BN_CTX_get(ctx); 11323b4e3dcbSSimon L. B. Nielsen z = BN_CTX_get(ctx); 11333b4e3dcbSSimon L. B. Nielsen w = BN_CTX_get(ctx); 11346f9291ceSJung-uk Kim if (w == NULL) 11356f9291ceSJung-uk Kim goto err; 11363b4e3dcbSSimon L. B. Nielsen 11376f9291ceSJung-uk Kim if (!BN_GF2m_mod_arr(a, a_, p)) 11386f9291ceSJung-uk Kim goto err; 11393b4e3dcbSSimon L. B. Nielsen 11406f9291ceSJung-uk Kim if (BN_is_zero(a)) { 11413b4e3dcbSSimon L. B. Nielsen BN_zero(r); 11423b4e3dcbSSimon L. B. Nielsen ret = 1; 11433b4e3dcbSSimon L. B. Nielsen goto err; 11443b4e3dcbSSimon L. B. Nielsen } 11453b4e3dcbSSimon L. B. Nielsen 11466f9291ceSJung-uk Kim if (p[0] & 0x1) { /* m is odd */ 11473b4e3dcbSSimon L. B. Nielsen /* compute half-trace of a */ 11486f9291ceSJung-uk Kim if (!BN_copy(z, a)) 11496f9291ceSJung-uk Kim goto err; 11506f9291ceSJung-uk Kim for (j = 1; j <= (p[0] - 1) / 2; j++) { 11516f9291ceSJung-uk Kim if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) 11526f9291ceSJung-uk Kim goto err; 11536f9291ceSJung-uk Kim if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) 11546f9291ceSJung-uk Kim goto err; 11556f9291ceSJung-uk Kim if (!BN_GF2m_add(z, z, a)) 11566f9291ceSJung-uk Kim goto err; 11573b4e3dcbSSimon L. B. Nielsen } 11583b4e3dcbSSimon L. B. Nielsen 11596f9291ceSJung-uk Kim } else { /* m is even */ 11606f9291ceSJung-uk Kim 11613b4e3dcbSSimon L. B. Nielsen rho = BN_CTX_get(ctx); 11623b4e3dcbSSimon L. B. Nielsen w2 = BN_CTX_get(ctx); 11633b4e3dcbSSimon L. B. Nielsen tmp = BN_CTX_get(ctx); 11646f9291ceSJung-uk Kim if (tmp == NULL) 11656f9291ceSJung-uk Kim goto err; 11666f9291ceSJung-uk Kim do { 11676f9291ceSJung-uk Kim if (!BN_rand(rho, p[0], 0, 0)) 11686f9291ceSJung-uk Kim goto err; 11696f9291ceSJung-uk Kim if (!BN_GF2m_mod_arr(rho, rho, p)) 11706f9291ceSJung-uk Kim goto err; 11713b4e3dcbSSimon L. B. Nielsen BN_zero(z); 11726f9291ceSJung-uk Kim if (!BN_copy(w, rho)) 11736f9291ceSJung-uk Kim goto err; 11746f9291ceSJung-uk Kim for (j = 1; j <= p[0] - 1; j++) { 11756f9291ceSJung-uk Kim if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx)) 11766f9291ceSJung-uk Kim goto err; 11776f9291ceSJung-uk Kim if (!BN_GF2m_mod_sqr_arr(w2, w, p, ctx)) 11786f9291ceSJung-uk Kim goto err; 11796f9291ceSJung-uk Kim if (!BN_GF2m_mod_mul_arr(tmp, w2, a, p, ctx)) 11806f9291ceSJung-uk Kim goto err; 11816f9291ceSJung-uk Kim if (!BN_GF2m_add(z, z, tmp)) 11826f9291ceSJung-uk Kim goto err; 11836f9291ceSJung-uk Kim if (!BN_GF2m_add(w, w2, rho)) 11846f9291ceSJung-uk Kim goto err; 11853b4e3dcbSSimon L. B. Nielsen } 11863b4e3dcbSSimon L. B. Nielsen count++; 11873b4e3dcbSSimon L. B. Nielsen } while (BN_is_zero(w) && (count < MAX_ITERATIONS)); 11886f9291ceSJung-uk Kim if (BN_is_zero(w)) { 11893b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR, BN_R_TOO_MANY_ITERATIONS); 11903b4e3dcbSSimon L. B. Nielsen goto err; 11913b4e3dcbSSimon L. B. Nielsen } 11923b4e3dcbSSimon L. B. Nielsen } 11933b4e3dcbSSimon L. B. Nielsen 11946f9291ceSJung-uk Kim if (!BN_GF2m_mod_sqr_arr(w, z, p, ctx)) 11956f9291ceSJung-uk Kim goto err; 11966f9291ceSJung-uk Kim if (!BN_GF2m_add(w, z, w)) 11976f9291ceSJung-uk Kim goto err; 11986f9291ceSJung-uk Kim if (BN_GF2m_cmp(w, a)) { 11993b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR, BN_R_NO_SOLUTION); 12003b4e3dcbSSimon L. B. Nielsen goto err; 12013b4e3dcbSSimon L. B. Nielsen } 12023b4e3dcbSSimon L. B. Nielsen 12036f9291ceSJung-uk Kim if (!BN_copy(r, z)) 12046f9291ceSJung-uk Kim goto err; 12053b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 12063b4e3dcbSSimon L. B. Nielsen 12073b4e3dcbSSimon L. B. Nielsen ret = 1; 12083b4e3dcbSSimon L. B. Nielsen 12093b4e3dcbSSimon L. B. Nielsen err: 12103b4e3dcbSSimon L. B. Nielsen BN_CTX_end(ctx); 12113b4e3dcbSSimon L. B. Nielsen return ret; 12123b4e3dcbSSimon L. B. Nielsen } 12133b4e3dcbSSimon L. B. Nielsen 12146f9291ceSJung-uk Kim /* 12156f9291ceSJung-uk Kim * Find r such that r^2 + r = a mod p. r could be a. If no r exists returns 12166f9291ceSJung-uk Kim * 0. This function calls down to the BN_GF2m_mod_solve_quad_arr 12176f9291ceSJung-uk Kim * implementation; this wrapper function is only provided for convenience; 12186f9291ceSJung-uk Kim * for best performance, use the BN_GF2m_mod_solve_quad_arr function. 12193b4e3dcbSSimon L. B. Nielsen */ 12206f9291ceSJung-uk Kim int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, 12216f9291ceSJung-uk Kim BN_CTX *ctx) 12223b4e3dcbSSimon L. B. Nielsen { 12233b4e3dcbSSimon L. B. Nielsen int ret = 0; 12241f13597dSJung-uk Kim const int max = BN_num_bits(p) + 1; 12251f13597dSJung-uk Kim int *arr = NULL; 12263b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 12273b4e3dcbSSimon L. B. Nielsen bn_check_top(p); 12286f9291ceSJung-uk Kim if ((arr = (int *)OPENSSL_malloc(sizeof(int) * max)) == NULL) 12296f9291ceSJung-uk Kim goto err; 12303b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_poly2arr(p, arr, max); 12316f9291ceSJung-uk Kim if (!ret || ret > max) { 12323b4e3dcbSSimon L. B. Nielsen BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD, BN_R_INVALID_LENGTH); 12333b4e3dcbSSimon L. B. Nielsen goto err; 12343b4e3dcbSSimon L. B. Nielsen } 12353b4e3dcbSSimon L. B. Nielsen ret = BN_GF2m_mod_solve_quad_arr(r, a, arr, ctx); 12363b4e3dcbSSimon L. B. Nielsen bn_check_top(r); 12373b4e3dcbSSimon L. B. Nielsen err: 12386f9291ceSJung-uk Kim if (arr) 12396f9291ceSJung-uk Kim OPENSSL_free(arr); 12403b4e3dcbSSimon L. B. Nielsen return ret; 12413b4e3dcbSSimon L. B. Nielsen } 12423b4e3dcbSSimon L. B. Nielsen 12436f9291ceSJung-uk Kim /* 12446f9291ceSJung-uk Kim * Convert the bit-string representation of a polynomial ( \sum_{i=0}^n a_i * 12456f9291ceSJung-uk Kim * x^i) into an array of integers corresponding to the bits with non-zero 12466f9291ceSJung-uk Kim * coefficient. Array is terminated with -1. Up to max elements of the array 12476f9291ceSJung-uk Kim * will be filled. Return value is total number of array elements that would 12486f9291ceSJung-uk Kim * be filled if array was large enough. 12493b4e3dcbSSimon L. B. Nielsen */ 12501f13597dSJung-uk Kim int BN_GF2m_poly2arr(const BIGNUM *a, int p[], int max) 12513b4e3dcbSSimon L. B. Nielsen { 12523b4e3dcbSSimon L. B. Nielsen int i, j, k = 0; 12533b4e3dcbSSimon L. B. Nielsen BN_ULONG mask; 12543b4e3dcbSSimon L. B. Nielsen 12551f13597dSJung-uk Kim if (BN_is_zero(a)) 12563b4e3dcbSSimon L. B. Nielsen return 0; 12573b4e3dcbSSimon L. B. Nielsen 12586f9291ceSJung-uk Kim for (i = a->top - 1; i >= 0; i--) { 12593b4e3dcbSSimon L. B. Nielsen if (!a->d[i]) 12603b4e3dcbSSimon L. B. Nielsen /* skip word if a->d[i] == 0 */ 12613b4e3dcbSSimon L. B. Nielsen continue; 12623b4e3dcbSSimon L. B. Nielsen mask = BN_TBIT; 12636f9291ceSJung-uk Kim for (j = BN_BITS2 - 1; j >= 0; j--) { 12646f9291ceSJung-uk Kim if (a->d[i] & mask) { 12656f9291ceSJung-uk Kim if (k < max) 12666f9291ceSJung-uk Kim p[k] = BN_BITS2 * i + j; 12673b4e3dcbSSimon L. B. Nielsen k++; 12683b4e3dcbSSimon L. B. Nielsen } 12693b4e3dcbSSimon L. B. Nielsen mask >>= 1; 12703b4e3dcbSSimon L. B. Nielsen } 12713b4e3dcbSSimon L. B. Nielsen } 12723b4e3dcbSSimon L. B. Nielsen 12731f13597dSJung-uk Kim if (k < max) { 12741f13597dSJung-uk Kim p[k] = -1; 12751f13597dSJung-uk Kim k++; 12761f13597dSJung-uk Kim } 12771f13597dSJung-uk Kim 12783b4e3dcbSSimon L. B. Nielsen return k; 12793b4e3dcbSSimon L. B. Nielsen } 12803b4e3dcbSSimon L. B. Nielsen 12816f9291ceSJung-uk Kim /* 12826f9291ceSJung-uk Kim * Convert the coefficient array representation of a polynomial to a 12831f13597dSJung-uk Kim * bit-string. The array must be terminated by -1. 12843b4e3dcbSSimon L. B. Nielsen */ 12851f13597dSJung-uk Kim int BN_GF2m_arr2poly(const int p[], BIGNUM *a) 12863b4e3dcbSSimon L. B. Nielsen { 12873b4e3dcbSSimon L. B. Nielsen int i; 12883b4e3dcbSSimon L. B. Nielsen 12893b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 12903b4e3dcbSSimon L. B. Nielsen BN_zero(a); 12916f9291ceSJung-uk Kim for (i = 0; p[i] != -1; i++) { 12923b4e3dcbSSimon L. B. Nielsen if (BN_set_bit(a, p[i]) == 0) 12933b4e3dcbSSimon L. B. Nielsen return 0; 12943b4e3dcbSSimon L. B. Nielsen } 12953b4e3dcbSSimon L. B. Nielsen bn_check_top(a); 12963b4e3dcbSSimon L. B. Nielsen 12973b4e3dcbSSimon L. B. Nielsen return 1; 12983b4e3dcbSSimon L. B. Nielsen } 12993b4e3dcbSSimon L. B. Nielsen 13001f13597dSJung-uk Kim #endif 1301