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 int 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 int getNativeBIGNUM() { 46 return this.bignum; 47 } 48 49 static int consumeErrors(StringBuilder sb) { 50 int cnt = 0; 51 int e, reason; 52 while ((e = NativeBN.ERR_get_error()) != 0) { 53 reason = e & 255; 54 if (reason == 103) { 55 throw new ArithmeticException("BigInteger division by zero"); 56 } 57 if (reason == 108) { 58 throw new ArithmeticException("BigInteger not invertible"); 59 } 60 if (reason == 65) { 61 throw new OutOfMemoryError(); 62 } 63 sb.append(e).append(": "); 64 String s = NativeBN.ERR_error_string(e); 65 sb.append(s); 66 cnt++; 67 } 68 return cnt; 69 } 70 71 private static void Check(boolean success) { 72 if (!success) { 73 StringBuilder sb = new StringBuilder("(openssl)ERR: "); 74 int cnt = consumeErrors(sb); 75 if (cnt > 0) 76 throw new ArithmeticException(sb.toString()); 77 } 78 } 79 80 81 private void makeValid() { 82 if (this.bignum == 0) { 83 this.bignum = NativeBN.BN_new(); 84 Check(this.bignum != 0); 85 } 86 } 87 88 private static BigInt newBigInt() { 89 BigInt bi = new BigInt(); 90 bi.bignum = NativeBN.BN_new(); 91 Check(bi.bignum != 0); 92 return bi; 93 } 94 95 96 static int cmp(BigInt a, BigInt b) { 97 return NativeBN.BN_cmp(a.bignum, b.bignum); 98 } 99 100 101 void putCopy(BigInt from) { 102 this.makeValid(); 103 Check(NativeBN.BN_copy(this.bignum, from.bignum)); 104 } 105 106 BigInt copy() { 107 BigInt bi = new BigInt(); 108 bi.putCopy(this); 109 return bi; 110 } 111 112 113 void putLongInt(long val) { 114 this.makeValid(); 115 Check(NativeBN.putLongInt(this.bignum, val)); 116 } 117 118 void putULongInt(long val, boolean neg) { 119 this.makeValid(); 120 Check(NativeBN.putULongInt(this.bignum, val, neg)); 121 } 122 123 private NumberFormatException invalidBigInteger(String s) { 124 throw new NumberFormatException("Invalid BigInteger: " + s); 125 } 126 127 void putDecString(String original) { 128 String s = checkString(original, 10); 129 this.makeValid(); 130 int usedLen = NativeBN.BN_dec2bn(this.bignum, s); 131 Check((usedLen > 0)); 132 if (usedLen < s.length()) { 133 throw invalidBigInteger(original); 134 } 135 } 136 137 void putHexString(String original) { 138 String s = checkString(original, 16); 139 this.makeValid(); 140 int usedLen = NativeBN.BN_hex2bn(this.bignum, s); 141 Check((usedLen > 0)); 142 if (usedLen < s.length()) { 143 throw invalidBigInteger(original); 144 } 145 } 146 147 /** 148 * Returns a string suitable for passing to OpenSSL. 149 * Throws if 's' doesn't match Java's rules for valid BigInteger strings. 150 * BN_dec2bn and BN_hex2bn do very little checking, so we need to manually 151 * ensure we comply with Java's rules. 152 * http://code.google.com/p/android/issues/detail?id=7036 153 */ 154 String checkString(String s, int base) { 155 if (s == null) { 156 throw new NullPointerException(); 157 } 158 // A valid big integer consists of an optional '-' or '+' followed by 159 // one or more digit characters appropriate to the given base, 160 // and no other characters. 161 int charCount = s.length(); 162 int i = 0; 163 if (charCount > 0) { 164 char ch = s.charAt(0); 165 if (ch == '+') { 166 // Java supports leading +, but OpenSSL doesn't, so we need to strip it. 167 s = s.substring(1); 168 --charCount; 169 } else if (ch == '-') { 170 ++i; 171 } 172 } 173 if (charCount - i == 0) { 174 throw invalidBigInteger(s); 175 } 176 boolean nonAscii = false; 177 for (; i < charCount; ++i) { 178 char ch = s.charAt(i); 179 if (Character.digit(ch, base) == -1) { 180 throw invalidBigInteger(s); 181 } 182 if (ch > 128) { 183 nonAscii = true; 184 } 185 } 186 return nonAscii ? toAscii(s, base) : s; 187 } 188 189 // Java supports non-ASCII decimal digits, but OpenSSL doesn't. 190 // We need to translate the decimal digits but leave any other characters alone. 191 // This method assumes it's being called on a string that has already been validated. 192 private static String toAscii(String s, int base) { 193 int length = s.length(); 194 StringBuilder result = new StringBuilder(length); 195 for (int i = 0; i < length; ++i) { 196 char ch = s.charAt(i); 197 int value = Character.digit(ch, base); 198 if (value >= 0 && value <= 9) { 199 ch = (char) ('0' + value); 200 } 201 result.append(ch); 202 } 203 return result.toString(); 204 } 205 206 void putBigEndian(byte[] a, boolean neg) { 207 this.makeValid(); 208 Check(NativeBN.BN_bin2bn(a, a.length, neg, this.bignum)); 209 } 210 211 void putLittleEndianInts(int[] a, boolean neg) { 212 this.makeValid(); 213 Check(NativeBN.litEndInts2bn(a, a.length, neg, this.bignum)); 214 } 215 216 void putBigEndianTwosComplement(byte[] a) { 217 this.makeValid(); 218 Check(NativeBN.twosComp2bn(a, a.length, this.bignum)); 219 } 220 221 222 long longInt() { 223 return NativeBN.longInt(this.bignum); 224 } 225 226 String decString() { 227 return NativeBN.BN_bn2dec(this.bignum); 228 } 229 230 String hexString() { 231 return NativeBN.BN_bn2hex(this.bignum); 232 } 233 234 byte[] bigEndianMagnitude() { 235 return NativeBN.BN_bn2bin(this.bignum); 236 } 237 238 int[] littleEndianIntsMagnitude() { 239 return NativeBN.bn2litEndInts(this.bignum); 240 } 241 242 int sign() { 243 return NativeBN.sign(this.bignum); 244 } 245 246 void setSign(int val) { 247 if (val > 0) { 248 NativeBN.BN_set_negative(this.bignum, 0); 249 } else { 250 if (val < 0) NativeBN.BN_set_negative(this.bignum, 1); 251 } 252 } 253 254 boolean twosCompFitsIntoBytes(int desiredByteCount) { 255 int actualByteCount = (NativeBN.bitLength(this.bignum) + 7) / 8; 256 return actualByteCount <= desiredByteCount; 257 } 258 259 int bitLength() { 260 return NativeBN.bitLength(this.bignum); 261 } 262 263 boolean isBitSet(int n) { 264 return NativeBN.BN_is_bit_set(this.bignum, n); 265 } 266 267 // n > 0: shift left (multiply) 268 static BigInt shift(BigInt a, int n) { 269 BigInt r = newBigInt(); 270 Check(NativeBN.BN_shift(r.bignum, a.bignum, n)); 271 return r; 272 } 273 274 void shift(int n) { 275 Check(NativeBN.BN_shift(this.bignum, this.bignum, n)); 276 } 277 278 void addPositiveInt(int w) { 279 Check(NativeBN.BN_add_word(this.bignum, w)); 280 } 281 282 void multiplyByPositiveInt(int w) { 283 Check(NativeBN.BN_mul_word(this.bignum, w)); 284 } 285 286 static int remainderByPositiveInt(BigInt a, int w) { 287 int rem = NativeBN.BN_mod_word(a.bignum, w); 288 Check(rem != -1); 289 return rem; 290 } 291 292 static BigInt addition(BigInt a, BigInt b) { 293 BigInt r = newBigInt(); 294 Check(NativeBN.BN_add(r.bignum, a.bignum, b.bignum)); 295 return r; 296 } 297 298 void add(BigInt a) { 299 Check(NativeBN.BN_add(this.bignum, this.bignum, a.bignum)); 300 } 301 302 static BigInt subtraction(BigInt a, BigInt b) { 303 BigInt r = newBigInt(); 304 Check(NativeBN.BN_sub(r.bignum, a.bignum, b.bignum)); 305 return r; 306 } 307 308 309 static BigInt gcd(BigInt a, BigInt b) { 310 BigInt r = newBigInt(); 311 Check(NativeBN.BN_gcd(r.bignum, a.bignum, b.bignum)); 312 return r; 313 } 314 315 static BigInt product(BigInt a, BigInt b) { 316 BigInt r = newBigInt(); 317 Check(NativeBN.BN_mul(r.bignum, a.bignum, b.bignum)); 318 return r; 319 } 320 321 static BigInt bigExp(BigInt a, BigInt p) { 322 // Sign of p is ignored! 323 BigInt r = newBigInt(); 324 Check(NativeBN.BN_exp(r.bignum, a.bignum, p.bignum)); 325 return r; 326 } 327 328 static BigInt exp(BigInt a, int p) { 329 // Sign of p is ignored! 330 BigInt power = new BigInt(); 331 power.putLongInt(p); 332 return bigExp(a, power); 333 // OPTIONAL: 334 // int BN_sqr(BigInteger r, BigInteger a, BN_CTX ctx); 335 // int BN_sqr(BIGNUM *r, const BIGNUM *a,BN_CTX *ctx); 336 } 337 338 static void division(BigInt dividend, BigInt divisor, 339 BigInt quotient, BigInt remainder) { 340 int quot, rem; 341 if (quotient != null) { 342 quotient.makeValid(); 343 quot = quotient.bignum; 344 } else { 345 quot = 0; 346 } 347 if (remainder != null) { 348 remainder.makeValid(); 349 rem = remainder.bignum; 350 } else { 351 rem = 0; 352 } 353 Check(NativeBN.BN_div(quot, rem, dividend.bignum, divisor.bignum)); 354 } 355 356 static BigInt modulus(BigInt a, BigInt m) { 357 // Sign of p is ignored! ? 358 BigInt r = newBigInt(); 359 Check(NativeBN.BN_nnmod(r.bignum, a.bignum, m.bignum)); 360 return r; 361 } 362 363 static BigInt modExp(BigInt a, BigInt p, BigInt m) { 364 // Sign of p is ignored! 365 BigInt r = newBigInt(); 366 Check(NativeBN.BN_mod_exp(r.bignum, a.bignum, p.bignum, m.bignum)); 367 368 // OPTIONAL: 369 // int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); 370 return r; 371 } 372 373 374 static BigInt modInverse(BigInt a, BigInt m) { 375 BigInt r = newBigInt(); 376 Check(NativeBN.BN_mod_inverse(r.bignum, a.bignum, m.bignum)); 377 return r; 378 } 379 380 381 static BigInt generatePrimeDefault(int bitLength) { 382 BigInt r = newBigInt(); 383 Check(NativeBN.BN_generate_prime_ex(r.bignum, bitLength, false, 0, 0, 0)); 384 return r; 385 } 386 387 boolean isPrime(int certainty) { 388 return NativeBN.BN_is_prime_ex(bignum, certainty, 0); 389 } 390 } 391
