1c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org/* crypto/bn/bn_lib.c */ 2c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * All rights reserved. 4c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 5c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * This package is an SSL implementation written 6c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * by Eric Young (eay@cryptsoft.com). 7c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * The implementation was written so as to conform with Netscapes SSL. 8c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 9c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * This library is free for commercial and non-commercial use as long as 10c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * the following conditions are aheared to. The following conditions 11c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * apply to all code found in this distribution, be it the RC4, RSA, 12c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * included with this distribution is covered by the same copyright terms 14c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 16c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * Copyright remains Eric Young's, and as such any Copyright notices in 17c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * the code are not to be removed. 18c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * If this package is used in a product, Eric Young should be given attribution 19c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * as the author of the parts of the library used. 20c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * This can be in the form of a textual message at program startup or 21c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * in documentation (online or textual) provided with the package. 22c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 23c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * Redistribution and use in source and binary forms, with or without 24c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * modification, are permitted provided that the following conditions 25c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * are met: 26c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 1. Redistributions of source code must retain the copyright 27c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * notice, this list of conditions and the following disclaimer. 28c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 2. Redistributions in binary form must reproduce the above copyright 29c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * notice, this list of conditions and the following disclaimer in the 30c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * documentation and/or other materials provided with the distribution. 31c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 3. All advertising materials mentioning features or use of this software 32c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * must display the following acknowledgement: 33c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * "This product includes cryptographic software written by 34c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * Eric Young (eay@cryptsoft.com)" 35c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * The word 'cryptographic' can be left out if the rouines from the library 36c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * being used are not cryptographic related :-). 37c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 4. If you include any Windows specific code (or a derivative thereof) from 38c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * the apps directory (application code) you must include an acknowledgement: 39c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 41c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * SUCH DAMAGE. 52c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 53c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * The licence and distribution terms for any publically available version or 54c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * derivative of this code cannot be changed. i.e. this code cannot simply be 55c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * copied and put under another distribution licence 56c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * [including the GNU Public Licence.] 57c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org */ 58c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 59c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#ifndef BN_DEBUG 60c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org# undef NDEBUG /* avoid conflicting definitions */ 61c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org# define NDEBUG 62c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#endif 63c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 64c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#include <assert.h> 65c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#include <limits.h> 66c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#include <stdio.h> 67c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#include "cryptlib.h" 68c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#include "bn_lcl.h" 69c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 70c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgconst char BN_version[]="Big Number" OPENSSL_VERSION_PTEXT; 71c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 72c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org/* This stuff appears to be completely unused, so is deprecated */ 73c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#ifndef OPENSSL_NO_DEPRECATED 74c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org/* For a 32 bit machine 75c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 2 - 4 == 128 76c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 3 - 8 == 256 77c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 4 - 16 == 512 78c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 5 - 32 == 1024 79c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 6 - 64 == 2048 80c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 7 - 128 == 4096 81c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 8 - 256 == 8192 82c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org */ 83c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgstatic int bn_limit_bits=0; 84c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgstatic int bn_limit_num=8; /* (1<<bn_limit_bits) */ 85c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgstatic int bn_limit_bits_low=0; 86c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgstatic int bn_limit_num_low=8; /* (1<<bn_limit_bits_low) */ 87c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgstatic int bn_limit_bits_high=0; 88c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgstatic int bn_limit_num_high=8; /* (1<<bn_limit_bits_high) */ 89c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgstatic int bn_limit_bits_mont=0; 90c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgstatic int bn_limit_num_mont=8; /* (1<<bn_limit_bits_mont) */ 91c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 92c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgvoid BN_set_params(int mult, int high, int low, int mont) 93c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 94c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (mult >= 0) 95c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 96c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (mult > (int)(sizeof(int)*8)-1) 97c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org mult=sizeof(int)*8-1; 98c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_limit_bits=mult; 99c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_limit_num=1<<mult; 100c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 101c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (high >= 0) 102c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 103c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (high > (int)(sizeof(int)*8)-1) 104c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org high=sizeof(int)*8-1; 105c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_limit_bits_high=high; 106c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_limit_num_high=1<<high; 107c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 108c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (low >= 0) 109c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 110c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (low > (int)(sizeof(int)*8)-1) 111c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org low=sizeof(int)*8-1; 112c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_limit_bits_low=low; 113c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_limit_num_low=1<<low; 114c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 115c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (mont >= 0) 116c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 117c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (mont > (int)(sizeof(int)*8)-1) 118c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org mont=sizeof(int)*8-1; 119c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_limit_bits_mont=mont; 120c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_limit_num_mont=1<<mont; 121c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 122c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 123c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 124c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgint BN_get_params(int which) 125c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 126c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (which == 0) return(bn_limit_bits); 127c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else if (which == 1) return(bn_limit_bits_high); 128c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else if (which == 2) return(bn_limit_bits_low); 129c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else if (which == 3) return(bn_limit_bits_mont); 130c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else return(0); 131c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 132c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#endif 133c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 134c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgconst BIGNUM *BN_value_one(void) 135c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 136480da75abf485e7e2a6be5acc0f71842368792c0jnd@chromium.org static const BN_ULONG data_one=1L; 137480da75abf485e7e2a6be5acc0f71842368792c0jnd@chromium.org static const BIGNUM const_one={(BN_ULONG *)&data_one,1,1,0,BN_FLG_STATIC_DATA}; 138c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 139c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(&const_one); 140c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 141c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 142c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgint BN_num_bits_word(BN_ULONG l) 143c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 144480da75abf485e7e2a6be5acc0f71842368792c0jnd@chromium.org static const unsigned char bits[256]={ 145c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4, 146c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 147c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 148c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 149c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 150c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 151c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 152c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 153c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 154c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 155c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 156c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 157c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 158c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 159c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 160c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 161c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org }; 162c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 163c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#if defined(SIXTY_FOUR_BIT_LONG) 164c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (l & 0xffffffff00000000L) 165c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 166c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (l & 0xffff000000000000L) 167c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 168c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (l & 0xff00000000000000L) 169c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 170c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(bits[(int)(l>>56)]+56); 171c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 172c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else return(bits[(int)(l>>48)]+48); 173c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 174c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else 175c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 176c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (l & 0x0000ff0000000000L) 177c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 178c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(bits[(int)(l>>40)]+40); 179c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 180c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else return(bits[(int)(l>>32)]+32); 181c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 182c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 183c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else 184c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#else 185c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#ifdef SIXTY_FOUR_BIT 186c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (l & 0xffffffff00000000LL) 187c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 188c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (l & 0xffff000000000000LL) 189c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 190c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (l & 0xff00000000000000LL) 191c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 192c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(bits[(int)(l>>56)]+56); 193c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 194c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else return(bits[(int)(l>>48)]+48); 195c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 196c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else 197c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 198c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (l & 0x0000ff0000000000LL) 199c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 200c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(bits[(int)(l>>40)]+40); 201c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 202c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else return(bits[(int)(l>>32)]+32); 203c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 204c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 205c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else 206c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#endif 207c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#endif 208c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 209c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) 210c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (l & 0xffff0000L) 211c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 212c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (l & 0xff000000L) 213c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(bits[(int)(l>>24L)]+24); 214c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else return(bits[(int)(l>>16L)]+16); 215c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 216c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else 217c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#endif 218c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 219480da75abf485e7e2a6be5acc0f71842368792c0jnd@chromium.org#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) 220c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (l & 0xff00L) 221c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(bits[(int)(l>>8)]+8); 222c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else 223c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#endif 224c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(bits[(int)(l )] ); 225c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 226c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 227c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 228c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 229c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgint BN_num_bits(const BIGNUM *a) 230c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 231c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int i = a->top - 1; 232c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 233c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 234c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (BN_is_zero(a)) return 0; 235c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return ((i*BN_BITS2) + BN_num_bits_word(a->d[i])); 236c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 237c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 238c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgvoid BN_clear_free(BIGNUM *a) 239c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 240c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int i; 241c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 242c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a == NULL) return; 243c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 244c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a->d != NULL) 245c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 246c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org OPENSSL_cleanse(a->d,a->dmax*sizeof(a->d[0])); 247c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (!(BN_get_flags(a,BN_FLG_STATIC_DATA))) 248c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org OPENSSL_free(a->d); 249c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 250c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org i=BN_get_flags(a,BN_FLG_MALLOCED); 251c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org OPENSSL_cleanse(a,sizeof(BIGNUM)); 252c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (i) 253c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org OPENSSL_free(a); 254c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 255c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 256c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgvoid BN_free(BIGNUM *a) 257c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 258c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a == NULL) return; 259c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 260c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA))) 261c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org OPENSSL_free(a->d); 262c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a->flags & BN_FLG_MALLOCED) 263c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org OPENSSL_free(a); 264c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else 265c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 266c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#ifndef OPENSSL_NO_DEPRECATED 267c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->flags|=BN_FLG_FREE; 268c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#endif 269c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->d = NULL; 270c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 271c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 272c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 273c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgvoid BN_init(BIGNUM *a) 274c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 275c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org memset(a,0,sizeof(BIGNUM)); 276c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 277c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 278c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 279c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgBIGNUM *BN_new(void) 280c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 281c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BIGNUM *ret; 282c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 283c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if ((ret=(BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL) 284c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 285c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE); 286c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(NULL); 287c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 288c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org ret->flags=BN_FLG_MALLOCED; 289c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org ret->top=0; 290c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org ret->neg=0; 291c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org ret->dmax=0; 292c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org ret->d=NULL; 293c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(ret); 294c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(ret); 295c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 296c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 297c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org/* This is used both by bn_expand2() and bn_dup_expand() */ 298c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org/* The caller MUST check that words > b->dmax before calling this */ 299c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgstatic BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) 300c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 301c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BN_ULONG *A,*a = NULL; 302c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org const BN_ULONG *B; 303c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int i; 304c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 305c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(b); 306c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 307c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (words > (INT_MAX/(4*BN_BITS2))) 308c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 309c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_BIGNUM_TOO_LONG); 310c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return NULL; 311c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 312c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (BN_get_flags(b,BN_FLG_STATIC_DATA)) 313c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 314c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 315c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(NULL); 316c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 317c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*words); 318c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (A == NULL) 319c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 320c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BNerr(BN_F_BN_EXPAND_INTERNAL,ERR_R_MALLOC_FAILURE); 321c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(NULL); 322c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 323c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#if 1 324c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org B=b->d; 325c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org /* Check if the previous number needs to be copied */ 326c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (B != NULL) 327c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 328c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org for (i=b->top>>2; i>0; i--,A+=4,B+=4) 329c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 330c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org /* 331c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * The fact that the loop is unrolled 332c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 4-wise is a tribute to Intel. It's 333c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * the one that doesn't have enough 334c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * registers to accomodate more data. 335c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * I'd unroll it 8-wise otherwise:-) 336c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 337c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * <appro@fy.chalmers.se> 338c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org */ 339c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BN_ULONG a0,a1,a2,a3; 340c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3]; 341c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3; 342c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 343c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org switch (b->top&3) 344c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 345c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org case 3: A[2]=B[2]; 346c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org case 2: A[1]=B[1]; 347c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org case 1: A[0]=B[0]; 348c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org case 0: /* workaround for ultrix cc: without 'case 0', the optimizer does 349c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * the switch table by doing a=top&3; a--; goto jump_table[a]; 350c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * which fails for top== 0 */ 351c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org ; 352c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 353c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 354c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 355c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#else 356c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org memset(A,0,sizeof(BN_ULONG)*words); 357c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org memcpy(A,b->d,sizeof(b->d[0])*b->top); 358c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#endif 359c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 360c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(a); 361c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 362c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 363c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org/* This is an internal function that can be used instead of bn_expand2() 364c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * when there is a need to copy BIGNUMs instead of only expanding the 365c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * data part, while still expanding them. 366c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * Especially useful when needing to expand BIGNUMs that are declared 367c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * 'const' and should therefore not be changed. 368c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * The reason to use this instead of a BN_dup() followed by a bn_expand2() 369c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * is memory allocation overhead. A BN_dup() followed by a bn_expand2() 370c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * will allocate new memory for the BIGNUM data twice, and free it once, 371c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * while bn_dup_expand() makes sure allocation is made only once. 372c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org */ 373c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 374c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#ifndef OPENSSL_NO_DEPRECATED 375c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgBIGNUM *bn_dup_expand(const BIGNUM *b, int words) 376c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 377c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BIGNUM *r = NULL; 378c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 379c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(b); 380c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 381c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org /* This function does not work if 382c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * words <= b->dmax && top < words 383c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * because BN_dup() does not preserve 'dmax'! 384c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * (But bn_dup_expand() is not used anywhere yet.) 385c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org */ 386c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 387c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (words > b->dmax) 388c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 389c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BN_ULONG *a = bn_expand_internal(b, words); 390c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 391c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a) 392c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 393c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org r = BN_new(); 394c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (r) 395c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 396c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org r->top = b->top; 397c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org r->dmax = words; 398c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org r->neg = b->neg; 399c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org r->d = a; 400c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 401c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else 402c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 403c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org /* r == NULL, BN_new failure */ 404c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org OPENSSL_free(a); 405c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 406c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 407c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org /* If a == NULL, there was an error in allocation in 408c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_expand_internal(), and NULL should be returned */ 409c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 410c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else 411c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 412c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org r = BN_dup(b); 413c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 414c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 415c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(r); 416c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return r; 417c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 418c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#endif 419c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 420c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org/* This is an internal function that should not be used in applications. 421c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * It ensures that 'b' has enough room for a 'words' word number 422c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * and initialises any unused part of b->d with leading zeros. 423c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * It is mostly used by the various BIGNUM routines. If there is an error, 424c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * NULL is returned. If not, 'b' is returned. */ 425c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 426c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgBIGNUM *bn_expand2(BIGNUM *b, int words) 427c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 428c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(b); 429c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 430c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (words > b->dmax) 431c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 432c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BN_ULONG *a = bn_expand_internal(b, words); 433c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if(!a) return NULL; 434c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if(b->d) OPENSSL_free(b->d); 435c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org b->d=a; 436c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org b->dmax=words; 437c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 438c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 439c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org/* None of this should be necessary because of what b->top means! */ 440c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#if 0 441c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org /* NB: bn_wexpand() calls this only if the BIGNUM really has to grow */ 442c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (b->top < b->dmax) 443c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 444c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int i; 445c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BN_ULONG *A = &(b->d[b->top]); 446c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org for (i=(b->dmax - b->top)>>3; i>0; i--,A+=8) 447c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 448c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org A[0]=0; A[1]=0; A[2]=0; A[3]=0; 449c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org A[4]=0; A[5]=0; A[6]=0; A[7]=0; 450c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 451c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org for (i=(b->dmax - b->top)&7; i>0; i--,A++) 452c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org A[0]=0; 453c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org assert(A == &(b->d[b->dmax])); 454c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 455c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#endif 456c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(b); 457c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return b; 458c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 459c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 460c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgBIGNUM *BN_dup(const BIGNUM *a) 461c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 462c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BIGNUM *t; 463c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 464c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a == NULL) return NULL; 465c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 466c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 467c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org t = BN_new(); 468c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (t == NULL) return NULL; 469c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if(!BN_copy(t, a)) 470c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 471c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BN_free(t); 472c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return NULL; 473c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 474c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(t); 475c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return t; 476c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 477c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 478c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgBIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) 479c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 480c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int i; 481c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BN_ULONG *A; 482c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org const BN_ULONG *B; 483c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 484c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(b); 485c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 486c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a == b) return(a); 487c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (bn_wexpand(a,b->top) == NULL) return(NULL); 488c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 489c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#if 1 490c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org A=a->d; 491c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org B=b->d; 492c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org for (i=b->top>>2; i>0; i--,A+=4,B+=4) 493c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 494c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BN_ULONG a0,a1,a2,a3; 495c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3]; 496c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3; 497c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 498c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org switch (b->top&3) 499c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 500c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org case 3: A[2]=B[2]; 501c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org case 2: A[1]=B[1]; 502c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org case 1: A[0]=B[0]; 503c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org case 0: ; /* ultrix cc workaround, see comments in bn_expand_internal */ 504c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 505c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#else 506c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org memcpy(a->d,b->d,sizeof(b->d[0])*b->top); 507c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org#endif 508c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 509c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->top=b->top; 510c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->neg=b->neg; 511c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 512c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(a); 513c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 514c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 515c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgvoid BN_swap(BIGNUM *a, BIGNUM *b) 516c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 517c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int flags_old_a, flags_old_b; 518c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BN_ULONG *tmp_d; 519c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int tmp_top, tmp_dmax, tmp_neg; 520c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 521c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 522c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(b); 523c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 524c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org flags_old_a = a->flags; 525c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org flags_old_b = b->flags; 526c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 527c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org tmp_d = a->d; 528c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org tmp_top = a->top; 529c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org tmp_dmax = a->dmax; 530c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org tmp_neg = a->neg; 531c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 532c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->d = b->d; 533c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->top = b->top; 534c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->dmax = b->dmax; 535c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->neg = b->neg; 536c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 537c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org b->d = tmp_d; 538c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org b->top = tmp_top; 539c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org b->dmax = tmp_dmax; 540c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org b->neg = tmp_neg; 541c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 542c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->flags = (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA); 543c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org b->flags = (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA); 544c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 545c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(b); 546c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 547c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 548c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgvoid BN_clear(BIGNUM *a) 549c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 550c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 551c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a->d != NULL) 552c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org memset(a->d,0,a->dmax*sizeof(a->d[0])); 553c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->top=0; 554c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->neg=0; 555c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 556c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 557c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgBN_ULONG BN_get_word(const BIGNUM *a) 558c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 559c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a->top > 1) 560c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return BN_MASK2; 561c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else if (a->top == 1) 562c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return a->d[0]; 563c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org /* a->top == 0 */ 564c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return 0; 565c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 566c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 567c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgint BN_set_word(BIGNUM *a, BN_ULONG w) 568c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 569c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 570c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (bn_expand(a,(int)sizeof(BN_ULONG)*8) == NULL) return(0); 571c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->neg = 0; 572c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->d[0] = w; 573c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->top = (w ? 1 : 0); 574c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 575c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(1); 576c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 577c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 578c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgBIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) 579c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 580c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org unsigned int i,m; 581c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org unsigned int n; 582c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BN_ULONG l; 583c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BIGNUM *bn = NULL; 584c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 585c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (ret == NULL) 586c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org ret = bn = BN_new(); 587c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (ret == NULL) return(NULL); 588c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(ret); 589c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org l=0; 590c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org n=len; 591c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (n == 0) 592c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 593c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org ret->top=0; 594c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(ret); 595c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 596c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org i=((n-1)/BN_BYTES)+1; 597c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org m=((n-1)%(BN_BYTES)); 598c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (bn_wexpand(ret, (int)i) == NULL) 599c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 600c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (bn) BN_free(bn); 601c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return NULL; 602c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 603c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org ret->top=i; 604c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org ret->neg=0; 605c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org while (n--) 606c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 607c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org l=(l<<8L)| *(s++); 608c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (m-- == 0) 609c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 610c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org ret->d[--i]=l; 611c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org l=0; 612c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org m=BN_BYTES-1; 613c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 614c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 615c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org /* need to call this due to clear byte at top if avoiding 616c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org * having the top bit set (-ve number) */ 617c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_correct_top(ret); 618c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(ret); 619c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 620c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 621c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org/* ignore negative */ 622c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgint BN_bn2bin(const BIGNUM *a, unsigned char *to) 623c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 624c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int n,i; 625c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BN_ULONG l; 626c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 627c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 628c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org n=i=BN_num_bytes(a); 629c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org while (i--) 630c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 631c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org l=a->d[i/BN_BYTES]; 632c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff; 633c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 634c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(n); 635c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 636c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 637c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgint BN_ucmp(const BIGNUM *a, const BIGNUM *b) 638c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 639c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int i; 640c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BN_ULONG t1,t2,*ap,*bp; 641c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 642c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 643c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(b); 644c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 645c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org i=a->top-b->top; 646c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (i != 0) return(i); 647c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org ap=a->d; 648c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bp=b->d; 649c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org for (i=a->top-1; i>=0; i--) 650c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 651c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org t1= ap[i]; 652c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org t2= bp[i]; 653c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (t1 != t2) 654c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return((t1 > t2) ? 1 : -1); 655c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 656c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(0); 657c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 658c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 659c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgint BN_cmp(const BIGNUM *a, const BIGNUM *b) 660c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 661c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int i; 662c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int gt,lt; 663c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BN_ULONG t1,t2; 664c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 665c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if ((a == NULL) || (b == NULL)) 666c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 667c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a != NULL) 668c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(-1); 669c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else if (b != NULL) 670c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(1); 671c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else 672c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(0); 673c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 674c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 675c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 676c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(b); 677c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 678c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a->neg != b->neg) 679c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 680c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a->neg) 681c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(-1); 682c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else return(1); 683c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 684c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a->neg == 0) 685c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { gt=1; lt= -1; } 686c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else { gt= -1; lt=1; } 687c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 688c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a->top > b->top) return(gt); 689c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a->top < b->top) return(lt); 690c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org for (i=a->top-1; i>=0; i--) 691c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 692c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org t1=a->d[i]; 693c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org t2=b->d[i]; 694c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (t1 > t2) return(gt); 695c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (t1 < t2) return(lt); 696c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 697c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(0); 698c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 699c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 700c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgint BN_set_bit(BIGNUM *a, int n) 701c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 702c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int i,j,k; 703c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 704c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (n < 0) 705c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return 0; 706c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 707c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org i=n/BN_BITS2; 708c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org j=n%BN_BITS2; 709c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a->top <= i) 710c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 711c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (bn_wexpand(a,i+1) == NULL) return(0); 712c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org for(k=a->top; k<i+1; k++) 713c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->d[k]=0; 714c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->top=i+1; 715c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 716c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 717c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->d[i]|=(((BN_ULONG)1)<<j); 718c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 719c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(1); 720c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 721c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 722c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgint BN_clear_bit(BIGNUM *a, int n) 723c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 724c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int i,j; 725c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 726c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 727c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (n < 0) return 0; 728c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 729c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org i=n/BN_BITS2; 730c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org j=n%BN_BITS2; 731c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a->top <= i) return(0); 732c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 733c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->d[i]&=(~(((BN_ULONG)1)<<j)); 734c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_correct_top(a); 735c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(1); 736c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 737c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 738c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgint BN_is_bit_set(const BIGNUM *a, int n) 739c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 740c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int i,j; 741c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 742c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 743c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (n < 0) return 0; 744c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org i=n/BN_BITS2; 745c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org j=n%BN_BITS2; 746c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a->top <= i) return 0; 747480da75abf485e7e2a6be5acc0f71842368792c0jnd@chromium.org return (int)(((a->d[i])>>j)&((BN_ULONG)1)); 748c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 749c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 750c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgint BN_mask_bits(BIGNUM *a, int n) 751c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 752c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int b,w; 753c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 754c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_check_top(a); 755c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (n < 0) return 0; 756c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 757c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org w=n/BN_BITS2; 758c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org b=n%BN_BITS2; 759c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (w >= a->top) return 0; 760c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (b == 0) 761c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->top=w; 762c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else 763c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 764c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->top=w+1; 765c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->d[w]&= ~(BN_MASK2<<b); 766c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 767c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bn_correct_top(a); 768c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(1); 769c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 770c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 771c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgvoid BN_set_negative(BIGNUM *a, int b) 772c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 773c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (b && !BN_is_zero(a)) 774c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->neg = 1; 775c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org else 776c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org a->neg = 0; 777c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 778c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 779c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgint bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) 780c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 781c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int i; 782c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org BN_ULONG aa,bb; 783c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 784c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org aa=a[n-1]; 785c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bb=b[n-1]; 786c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (aa != bb) return((aa > bb)?1:-1); 787c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org for (i=n-2; i>=0; i--) 788c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 789c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org aa=a[i]; 790c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org bb=b[i]; 791c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (aa != bb) return((aa > bb)?1:-1); 792c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 793c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return(0); 794c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 795c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 796c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org/* Here follows a specialised variants of bn_cmp_words(). It has the 797c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org property of performing the operation on arrays of different sizes. 798c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org The sizes of those arrays is expressed through cl, which is the 799c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org common length ( basicall, min(len(a),len(b)) ), and dl, which is the 800c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org delta between the two lengths, calculated as len(a)-len(b). 801c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org All lengths are the number of BN_ULONGs... */ 802c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 803c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.orgint bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, 804c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int cl, int dl) 805c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 806c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org int n,i; 807c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org n = cl-1; 808c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org 809c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (dl < 0) 810c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 811c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org for (i=dl; i<0; i++) 812c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 813c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (b[n-i] != 0) 814c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return -1; /* a < b */ 815c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 816c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 817c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (dl > 0) 818c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 819c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org for (i=dl; i>0; i--) 820c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org { 821c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org if (a[n+i] != 0) 822c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return 1; /* a > b */ 823c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 824c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 825c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org return bn_cmp_words(a,b,cl); 826c9490d33b98b7affb729b5f1db13cb0a348471aagl@chromium.org } 827