1 /* 2 * Copyright (C) 2008 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package java.math; 18 19 /* 20 * In contrast to BigIntegers this class doesn't fake two's complement representation. 21 * Any Bit-Operations, including Shifting, solely regard the unsigned magnitude. 22 * Moreover BigInt objects are mutable and offer efficient in-place-operations. 23 */ 24 final class BigInt { 25 26 /* Fields used for the internal representation. */ 27 transient long bignum = 0; 28 29 @Override protected void finalize() throws Throwable { 30 try { 31 if (this.bignum != 0) { 32 NativeBN.BN_free(this.bignum); 33 this.bignum = 0; 34 } 35 } finally { 36 super.finalize(); 37 } 38 } 39 40 @Override 41 public String toString() { 42 return this.decString(); 43 } 44 45 long getNativeBIGNUM() { 46 return this.bignum; 47 } 48 49 private void makeValid() { 50 if (this.bignum == 0) { 51 this.bignum = NativeBN.BN_new(); 52 } 53 } 54 55 private static BigInt newBigInt() { 56 BigInt bi = new BigInt(); 57 bi.bignum = NativeBN.BN_new(); 58 return bi; 59 } 60 61 62 static int cmp(BigInt a, BigInt b) { 63 return NativeBN.BN_cmp(a.bignum, b.bignum); 64 } 65 66 67 void putCopy(BigInt from) { 68 this.makeValid(); 69 NativeBN.BN_copy(this.bignum, from.bignum); 70 } 71 72 BigInt copy() { 73 BigInt bi = new BigInt(); 74 bi.putCopy(this); 75 return bi; 76 } 77 78 79 void putLongInt(long val) { 80 this.makeValid(); 81 NativeBN.putLongInt(this.bignum, val); 82 } 83 84 void putULongInt(long val, boolean neg) { 85 this.makeValid(); 86 NativeBN.putULongInt(this.bignum, val, neg); 87 } 88 89 private NumberFormatException invalidBigInteger(String s) { 90 throw new NumberFormatException("Invalid BigInteger: " + s); 91 } 92 93 void putDecString(String original) { 94 String s = checkString(original, 10); 95 this.makeValid(); 96 int usedLen = NativeBN.BN_dec2bn(this.bignum, s); 97 if (usedLen < s.length()) { 98 throw invalidBigInteger(original); 99 } 100 } 101 102 void putHexString(String original) { 103 String s = checkString(original, 16); 104 this.makeValid(); 105 int usedLen = NativeBN.BN_hex2bn(this.bignum, s); 106 if (usedLen < s.length()) { 107 throw invalidBigInteger(original); 108 } 109 } 110 111 /** 112 * Returns a string suitable for passing to OpenSSL. 113 * Throws if 's' doesn't match Java's rules for valid BigInteger strings. 114 * BN_dec2bn and BN_hex2bn do very little checking, so we need to manually 115 * ensure we comply with Java's rules. 116 * http://code.google.com/p/android/issues/detail?id=7036 117 */ 118 String checkString(String s, int base) { 119 if (s == null) { 120 throw new NullPointerException("s == null"); 121 } 122 // A valid big integer consists of an optional '-' or '+' followed by 123 // one or more digit characters appropriate to the given base, 124 // and no other characters. 125 int charCount = s.length(); 126 int i = 0; 127 if (charCount > 0) { 128 char ch = s.charAt(0); 129 if (ch == '+') { 130 // Java supports leading +, but OpenSSL doesn't, so we need to strip it. 131 s = s.substring(1); 132 --charCount; 133 } else if (ch == '-') { 134 ++i; 135 } 136 } 137 if (charCount - i == 0) { 138 throw invalidBigInteger(s); 139 } 140 boolean nonAscii = false; 141 for (; i < charCount; ++i) { 142 char ch = s.charAt(i); 143 if (Character.digit(ch, base) == -1) { 144 throw invalidBigInteger(s); 145 } 146 if (ch > 128) { 147 nonAscii = true; 148 } 149 } 150 return nonAscii ? toAscii(s, base) : s; 151 } 152 153 // Java supports non-ASCII decimal digits, but OpenSSL doesn't. 154 // We need to translate the decimal digits but leave any other characters alone. 155 // This method assumes it's being called on a string that has already been validated. 156 private static String toAscii(String s, int base) { 157 int length = s.length(); 158 StringBuilder result = new StringBuilder(length); 159 for (int i = 0; i < length; ++i) { 160 char ch = s.charAt(i); 161 int value = Character.digit(ch, base); 162 if (value >= 0 && value <= 9) { 163 ch = (char) ('0' + value); 164 } 165 result.append(ch); 166 } 167 return result.toString(); 168 } 169 170 void putBigEndian(byte[] a, boolean neg) { 171 this.makeValid(); 172 NativeBN.BN_bin2bn(a, a.length, neg, this.bignum); 173 } 174 175 void putLittleEndianInts(int[] a, boolean neg) { 176 this.makeValid(); 177 NativeBN.litEndInts2bn(a, a.length, neg, this.bignum); 178 } 179 180 void putBigEndianTwosComplement(byte[] a) { 181 this.makeValid(); 182 NativeBN.twosComp2bn(a, a.length, this.bignum); 183 } 184 185 186 long longInt() { 187 return NativeBN.longInt(this.bignum); 188 } 189 190 String decString() { 191 return NativeBN.BN_bn2dec(this.bignum); 192 } 193 194 String hexString() { 195 return NativeBN.BN_bn2hex(this.bignum); 196 } 197 198 byte[] bigEndianMagnitude() { 199 return NativeBN.BN_bn2bin(this.bignum); 200 } 201 202 int[] littleEndianIntsMagnitude() { 203 return NativeBN.bn2litEndInts(this.bignum); 204 } 205 206 int sign() { 207 return NativeBN.sign(this.bignum); 208 } 209 210 void setSign(int val) { 211 if (val > 0) { 212 NativeBN.BN_set_negative(this.bignum, 0); 213 } else { 214 if (val < 0) NativeBN.BN_set_negative(this.bignum, 1); 215 } 216 } 217 218 boolean twosCompFitsIntoBytes(int desiredByteCount) { 219 int actualByteCount = (NativeBN.bitLength(this.bignum) + 7) / 8; 220 return actualByteCount <= desiredByteCount; 221 } 222 223 int bitLength() { 224 return NativeBN.bitLength(this.bignum); 225 } 226 227 boolean isBitSet(int n) { 228 return NativeBN.BN_is_bit_set(this.bignum, n); 229 } 230 231 // n > 0: shift left (multiply) 232 static BigInt shift(BigInt a, int n) { 233 BigInt r = newBigInt(); 234 NativeBN.BN_shift(r.bignum, a.bignum, n); 235 return r; 236 } 237 238 void shift(int n) { 239 NativeBN.BN_shift(this.bignum, this.bignum, n); 240 } 241 242 void addPositiveInt(int w) { 243 NativeBN.BN_add_word(this.bignum, w); 244 } 245 246 void multiplyByPositiveInt(int w) { 247 NativeBN.BN_mul_word(this.bignum, w); 248 } 249 250 static int remainderByPositiveInt(BigInt a, int w) { 251 return NativeBN.BN_mod_word(a.bignum, w); 252 } 253 254 static BigInt addition(BigInt a, BigInt b) { 255 BigInt r = newBigInt(); 256 NativeBN.BN_add(r.bignum, a.bignum, b.bignum); 257 return r; 258 } 259 260 void add(BigInt a) { 261 NativeBN.BN_add(this.bignum, this.bignum, a.bignum); 262 } 263 264 static BigInt subtraction(BigInt a, BigInt b) { 265 BigInt r = newBigInt(); 266 NativeBN.BN_sub(r.bignum, a.bignum, b.bignum); 267 return r; 268 } 269 270 271 static BigInt gcd(BigInt a, BigInt b) { 272 BigInt r = newBigInt(); 273 NativeBN.BN_gcd(r.bignum, a.bignum, b.bignum); 274 return r; 275 } 276 277 static BigInt product(BigInt a, BigInt b) { 278 BigInt r = newBigInt(); 279 NativeBN.BN_mul(r.bignum, a.bignum, b.bignum); 280 return r; 281 } 282 283 static BigInt bigExp(BigInt a, BigInt p) { 284 // Sign of p is ignored! 285 BigInt r = newBigInt(); 286 NativeBN.BN_exp(r.bignum, a.bignum, p.bignum); 287 return r; 288 } 289 290 static BigInt exp(BigInt a, int p) { 291 // Sign of p is ignored! 292 BigInt power = new BigInt(); 293 power.putLongInt(p); 294 return bigExp(a, power); 295 // OPTIONAL: 296 // int BN_sqr(BigInteger r, BigInteger a, BN_CTX ctx); 297 // int BN_sqr(BIGNUM *r, const BIGNUM *a,BN_CTX *ctx); 298 } 299 300 static void division(BigInt dividend, BigInt divisor, BigInt quotient, BigInt remainder) { 301 long quot, rem; 302 if (quotient != null) { 303 quotient.makeValid(); 304 quot = quotient.bignum; 305 } else { 306 quot = 0; 307 } 308 if (remainder != null) { 309 remainder.makeValid(); 310 rem = remainder.bignum; 311 } else { 312 rem = 0; 313 } 314 NativeBN.BN_div(quot, rem, dividend.bignum, divisor.bignum); 315 } 316 317 static BigInt modulus(BigInt a, BigInt m) { 318 // Sign of p is ignored! ? 319 BigInt r = newBigInt(); 320 NativeBN.BN_nnmod(r.bignum, a.bignum, m.bignum); 321 return r; 322 } 323 324 static BigInt modExp(BigInt a, BigInt p, BigInt m) { 325 // Sign of p is ignored! 326 BigInt r = newBigInt(); 327 NativeBN.BN_mod_exp(r.bignum, a.bignum, p.bignum, m.bignum); 328 return r; 329 } 330 331 332 static BigInt modInverse(BigInt a, BigInt m) { 333 BigInt r = newBigInt(); 334 NativeBN.BN_mod_inverse(r.bignum, a.bignum, m.bignum); 335 return r; 336 } 337 338 339 static BigInt generatePrimeDefault(int bitLength) { 340 BigInt r = newBigInt(); 341 NativeBN.BN_generate_prime_ex(r.bignum, bitLength, false, 0, 0, 0); 342 return r; 343 } 344 345 boolean isPrime(int certainty) { 346 return NativeBN.BN_is_prime_ex(bignum, certainty, 0); 347 } 348 } 349
