1d9e397b599b13d642138480a28c14db7a136bf0Adam Langley/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * All rights reserved. 3d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 4d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * This package is an SSL implementation written 5d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * by Eric Young (eay@cryptsoft.com). 6d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * The implementation was written so as to conform with Netscapes SSL. 7d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 8d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * This library is free for commercial and non-commercial use as long as 9d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * the following conditions are aheared to. The following conditions 10d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * apply to all code found in this distribution, be it the RC4, RSA, 11d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * lhash, DES, etc., code; not just the SSL code. The SSL documentation 12d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * included with this distribution is covered by the same copyright terms 13d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * except that the holder is Tim Hudson (tjh@cryptsoft.com). 14d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 15d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Copyright remains Eric Young's, and as such any Copyright notices in 16d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * the code are not to be removed. 17d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * If this package is used in a product, Eric Young should be given attribution 18d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * as the author of the parts of the library used. 19d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * This can be in the form of a textual message at program startup or 20d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * in documentation (online or textual) provided with the package. 21d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 22d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Redistribution and use in source and binary forms, with or without 23d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * modification, are permitted provided that the following conditions 24d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * are met: 25d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 1. Redistributions of source code must retain the copyright 26d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * notice, this list of conditions and the following disclaimer. 27d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 2. Redistributions in binary form must reproduce the above copyright 28d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * notice, this list of conditions and the following disclaimer in the 29d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * documentation and/or other materials provided with the distribution. 30d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 3. All advertising materials mentioning features or use of this software 31d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * must display the following acknowledgement: 32d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * "This product includes cryptographic software written by 33d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Eric Young (eay@cryptsoft.com)" 34d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * The word 'cryptographic' can be left out if the rouines from the library 35d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * being used are not cryptographic related :-). 36d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 4. If you include any Windows specific code (or a derivative thereof) from 37d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * the apps directory (application code) you must include an acknowledgement: 38d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 39d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 40d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 44d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * SUCH DAMAGE. 51d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 52d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * The licence and distribution terms for any publically available version or 53d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * derivative of this code cannot be changed. i.e. this code cannot simply be 54d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * copied and put under another distribution licence 55d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * [including the GNU Public Licence.] */ 56d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 57d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <openssl/bn.h> 58d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 59d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include "internal.h" 60d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 61d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 62d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_ucmp(const BIGNUM *a, const BIGNUM *b) { 63d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int i; 64d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_ULONG t1, t2, *ap, *bp; 65d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 66d9e397b599b13d642138480a28c14db7a136bf0Adam Langley i = a->top - b->top; 67d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (i != 0) { 68d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return i; 69d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 70d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 71d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ap = a->d; 72d9e397b599b13d642138480a28c14db7a136bf0Adam Langley bp = b->d; 73d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = a->top - 1; i >= 0; i--) { 74d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t1 = ap[i]; 75d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t2 = bp[i]; 76d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (t1 != t2) { 77d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return (t1 > t2) ? 1 : -1; 78d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 79d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 80d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 81d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 82d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 83d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 84d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_cmp(const BIGNUM *a, const BIGNUM *b) { 85d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int i; 86d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int gt, lt; 87d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_ULONG t1, t2; 88d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 89d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if ((a == NULL) || (b == NULL)) { 90d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a != NULL) { 91d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return -1; 92d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else if (b != NULL) { 93d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 94d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 95d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 96d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 97d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 98d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 99d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->neg != b->neg) { 100d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->neg) { 101d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return -1; 102d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 103d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 104d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 105d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->neg == 0) { 106d9e397b599b13d642138480a28c14db7a136bf0Adam Langley gt = 1; 107d9e397b599b13d642138480a28c14db7a136bf0Adam Langley lt = -1; 108d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 109d9e397b599b13d642138480a28c14db7a136bf0Adam Langley gt = -1; 110d9e397b599b13d642138480a28c14db7a136bf0Adam Langley lt = 1; 111d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 112d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 113d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->top > b->top) { 114d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return gt; 115d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 116d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->top < b->top) { 117d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return lt; 118d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 119d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 120d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = a->top - 1; i >= 0; i--) { 121d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t1 = a->d[i]; 122d9e397b599b13d642138480a28c14db7a136bf0Adam Langley t2 = b->d[i]; 123d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (t1 > t2) { 124d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return gt; 125d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } if (t1 < t2) { 126d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return lt; 127d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 128d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 129d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 130d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 131d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 132d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 133d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) { 134d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int i; 135d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_ULONG aa, bb; 136d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 137d9e397b599b13d642138480a28c14db7a136bf0Adam Langley aa = a[n - 1]; 138d9e397b599b13d642138480a28c14db7a136bf0Adam Langley bb = b[n - 1]; 139d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (aa != bb) { 140d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return (aa > bb) ? 1 : -1; 141d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 142d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 143d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = n - 2; i >= 0; i--) { 144d9e397b599b13d642138480a28c14db7a136bf0Adam Langley aa = a[i]; 145d9e397b599b13d642138480a28c14db7a136bf0Adam Langley bb = b[i]; 146d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (aa != bb) { 147d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return (aa > bb) ? 1 : -1; 148d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 149d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 150d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 151d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 152d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 153d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) { 154d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int n, i; 155d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n = cl - 1; 156d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 157d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (dl < 0) { 158d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = dl; i < 0; i++) { 159d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (b[n - i] != 0) { 160d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return -1; /* a < b */ 161d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 162d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 163d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 164d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (dl > 0) { 165d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = dl; i > 0; i--) { 166d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a[n + i] != 0) { 167d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; /* a > b */ 168d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 169d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 170d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 171d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 172d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return bn_cmp_words(a, b, cl); 173d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 174d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 175d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_abs_is_word(const BIGNUM *bn, BN_ULONG w) { 176d9e397b599b13d642138480a28c14db7a136bf0Adam Langley switch (bn->top) { 177d9e397b599b13d642138480a28c14db7a136bf0Adam Langley case 1: 178d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return bn->d[0] == w; 179d9e397b599b13d642138480a28c14db7a136bf0Adam Langley case 0: 180d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return w == 0; 181d9e397b599b13d642138480a28c14db7a136bf0Adam Langley default: 182d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 183d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 184d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 185d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 186d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_is_zero(const BIGNUM *bn) { 187d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return bn->top == 0; 188d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 189d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 190d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_is_one(const BIGNUM *bn) { 191d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return bn->neg == 0 && BN_abs_is_word(bn, 1); 192d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 193d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 194d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_is_word(const BIGNUM *bn, BN_ULONG w) { 195d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return BN_abs_is_word(bn, w) && (w == 0 || bn->neg == 0); 196d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 197d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 198d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint BN_is_odd(const BIGNUM *bn) { 199d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return bn->top > 0 && (bn->d[0] & 1) == 1; 200d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 201