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 #define LOG_TAG "NativeBN" 18 19 #include "JniException.h" 20 #include "jni.h" 21 #include <nativehelper/JNIHelp.h> 22 #include <nativehelper/JniConstants.h> 23 #include <nativehelper/ScopedPrimitiveArray.h> 24 #include <nativehelper/ScopedUtfChars.h> 25 #include <openssl/bn.h> 26 #include <openssl/crypto.h> 27 #include <openssl/err.h> 28 #include <stdio.h> 29 #include <algorithm> 30 #include <memory> 31 32 struct BN_CTX_Deleter { 33 void operator()(BN_CTX* p) const { 34 BN_CTX_free(p); 35 } 36 }; 37 typedef std::unique_ptr<BN_CTX, BN_CTX_Deleter> Unique_BN_CTX; 38 39 static BIGNUM* toBigNum(jlong address) { 40 return reinterpret_cast<BIGNUM*>(static_cast<uintptr_t>(address)); 41 } 42 43 static void throwException(JNIEnv* env) { 44 long error = ERR_get_error(); 45 // OpenSSL's error queue may contain multiple errors. Clean up after them. 46 ERR_clear_error(); 47 48 if (error == 0) { 49 // An operation failed but did not push to the error queue. Throw a default 50 // exception. 51 jniThrowException(env, "java/lang/ArithmeticException", "Operation failed"); 52 return; 53 } 54 55 char message[256]; 56 ERR_error_string_n(error, message, sizeof(message)); 57 int reason = ERR_GET_REASON(error); 58 if (reason == BN_R_DIV_BY_ZERO) { 59 jniThrowException(env, "java/lang/ArithmeticException", "BigInteger division by zero"); 60 } else if (reason == BN_R_NO_INVERSE) { 61 jniThrowException(env, "java/lang/ArithmeticException", "BigInteger not invertible"); 62 } else if (reason == ERR_R_MALLOC_FAILURE) { 63 jniThrowOutOfMemoryError(env, message); 64 } else { 65 jniThrowException(env, "java/lang/ArithmeticException", message); 66 } 67 } 68 69 static int isValidHandle(JNIEnv* env, jlong handle, const char* message) { 70 if (handle == 0) { 71 jniThrowNullPointerException(env, message); 72 return JNI_FALSE; 73 } 74 return JNI_TRUE; 75 } 76 77 static int oneValidHandle(JNIEnv* env, jlong a) { 78 return isValidHandle(env, a, "Mandatory handle (first) passed as null"); 79 } 80 81 static int twoValidHandles(JNIEnv* env, jlong a, jlong b) { 82 if (!oneValidHandle(env, a)) return JNI_FALSE; 83 return isValidHandle(env, b, "Mandatory handle (second) passed as null"); 84 } 85 86 static int threeValidHandles(JNIEnv* env, jlong a, jlong b, jlong c) { 87 if (!twoValidHandles(env, a, b)) return JNI_FALSE; 88 return isValidHandle(env, c, "Mandatory handle (third) passed as null"); 89 } 90 91 static int fourValidHandles(JNIEnv* env, jlong a, jlong b, jlong c, jlong d) { 92 if (!threeValidHandles(env, a, b, c)) return JNI_FALSE; 93 return isValidHandle(env, d, "Mandatory handle (fourth) passed as null"); 94 } 95 96 static jlong NativeBN_BN_new(JNIEnv* env, jclass) { 97 jlong result = static_cast<jlong>(reinterpret_cast<uintptr_t>(BN_new())); 98 if (!result) { 99 throwException(env); 100 } 101 return result; 102 } 103 104 static jlong NativeBN_getNativeFinalizer(JNIEnv*, jclass) { 105 return static_cast<jlong>(reinterpret_cast<uintptr_t>(&BN_free)); 106 } 107 108 static void NativeBN_BN_free(JNIEnv* env, jclass, jlong a) { 109 if (!oneValidHandle(env, a)) return; 110 BN_free(toBigNum(a)); 111 } 112 113 static int NativeBN_BN_cmp(JNIEnv* env, jclass, jlong a, jlong b) { 114 if (!twoValidHandles(env, a, b)) return 1; 115 return BN_cmp(toBigNum(a), toBigNum(b)); 116 } 117 118 static void NativeBN_BN_copy(JNIEnv* env, jclass, jlong to, jlong from) { 119 if (!twoValidHandles(env, to, from)) return; 120 if (!BN_copy(toBigNum(to), toBigNum(from))) { 121 throwException(env); 122 } 123 } 124 125 static void NativeBN_putULongInt(JNIEnv* env, jclass, jlong a0, jlong java_dw, jboolean neg) { 126 if (!oneValidHandle(env, a0)) return; 127 128 uint64_t dw = java_dw; 129 BIGNUM* a = toBigNum(a0); 130 131 if (!BN_set_u64(a, dw)) { 132 throwException(env); 133 return; 134 } 135 136 BN_set_negative(a, neg); 137 } 138 139 static void NativeBN_putLongInt(JNIEnv* env, jclass cls, jlong a, jlong dw) { 140 if (dw >= 0) { 141 NativeBN_putULongInt(env, cls, a, dw, JNI_FALSE); 142 } else { 143 NativeBN_putULongInt(env, cls, a, -dw, JNI_TRUE); 144 } 145 } 146 147 static int NativeBN_BN_dec2bn(JNIEnv* env, jclass, jlong a0, jstring str) { 148 if (!oneValidHandle(env, a0)) return -1; 149 ScopedUtfChars chars(env, str); 150 if (chars.c_str() == NULL) { 151 return -1; 152 } 153 BIGNUM* a = toBigNum(a0); 154 int result = BN_dec2bn(&a, chars.c_str()); 155 if (result == 0) { 156 throwException(env); 157 } 158 return result; 159 } 160 161 static int NativeBN_BN_hex2bn(JNIEnv* env, jclass, jlong a0, jstring str) { 162 if (!oneValidHandle(env, a0)) return -1; 163 ScopedUtfChars chars(env, str); 164 if (chars.c_str() == NULL) { 165 return -1; 166 } 167 BIGNUM* a = toBigNum(a0); 168 int result = BN_hex2bn(&a, chars.c_str()); 169 if (result == 0) { 170 throwException(env); 171 } 172 return result; 173 } 174 175 static void NativeBN_BN_bin2bn(JNIEnv* env, jclass, jbyteArray arr, int len, jboolean neg, jlong ret) { 176 if (!oneValidHandle(env, ret)) return; 177 ScopedByteArrayRO bytes(env, arr); 178 if (bytes.get() == NULL) { 179 return; 180 } 181 if (!BN_bin2bn(reinterpret_cast<const unsigned char*>(bytes.get()), len, toBigNum(ret))) { 182 throwException(env); 183 return; 184 } 185 186 BN_set_negative(toBigNum(ret), neg); 187 } 188 189 static void NativeBN_litEndInts2bn(JNIEnv* env, jclass, jintArray arr, int len, jboolean neg, jlong ret0) { 190 if (!oneValidHandle(env, ret0)) return; 191 BIGNUM* ret = toBigNum(ret0); 192 193 ScopedIntArrayRO scopedArray(env, arr); 194 195 if (scopedArray.get() == NULL) { 196 return; 197 } 198 199 // We can simply interpret the little-endian integer stream as a 200 // little-endian byte stream and use BN_le2bn. 201 const uint8_t* tmpBytes = reinterpret_cast<const uint8_t *>(scopedArray.get()); 202 size_t numBytes = len * sizeof(int); 203 204 if (!BN_le2bn(tmpBytes, numBytes, ret)) { 205 throwException(env); 206 } 207 208 BN_set_negative(ret, neg); 209 } 210 211 static void NativeBN_twosComp2bn(JNIEnv* env, jclass, jbyteArray arr, int bytesLen, jlong ret0) { 212 if (!oneValidHandle(env, ret0)) return; 213 BIGNUM* ret = toBigNum(ret0); 214 215 ScopedByteArrayRO bytes(env, arr); 216 if (bytes.get() == NULL) { 217 return; 218 } 219 220 if (bytesLen == 0) { 221 BN_zero(ret); 222 return; 223 } 224 225 const unsigned char* bytesTmp = reinterpret_cast<const unsigned char*>(bytes.get()); 226 227 if (!BN_bin2bn(bytesTmp, bytesLen, ret)) { 228 throwException(env); 229 return; 230 } 231 232 // Use the high bit to determine the sign in twos-complement. 233 BN_set_negative(ret, (bytes[0] & 0x80) != 0); 234 235 if (BN_is_negative(ret)) { 236 // For negative values, BN_bin2bn doesn't interpret the twos-complement 237 // representation, so ret is now (- value - 2^N). We can use nnmod_pow2 to set 238 // ret to (-value). 239 if (!BN_nnmod_pow2(ret, ret, bytesLen * 8)) { 240 throwException(env); 241 return; 242 } 243 244 // And now we correct the sign. 245 BN_set_negative(ret, 1); 246 } 247 } 248 249 static jlong NativeBN_longInt(JNIEnv* env, jclass, jlong a0) { 250 if (!oneValidHandle(env, a0)) return -1; 251 BIGNUM* a = toBigNum(a0); 252 uint64_t word; 253 254 if (BN_get_u64(a, &word)) { 255 return BN_is_negative(a) ? -((jlong) word) : word; 256 } else { 257 // This should be unreachable if our caller checks BigInt::twosCompFitsIntoBytes(8) 258 throwException(env); 259 return 0; 260 } 261 } 262 263 static char* leadingZerosTrimmed(char* s) { 264 char* p = s; 265 if (*p == '-') { 266 p++; 267 while ((*p == '0') && (*(p + 1) != 0)) { p++; } 268 p--; 269 *p = '-'; 270 } else { 271 while ((*p == '0') && (*(p + 1) != 0)) { p++; } 272 } 273 return p; 274 } 275 276 static jstring NativeBN_BN_bn2dec(JNIEnv* env, jclass, jlong a) { 277 if (!oneValidHandle(env, a)) return NULL; 278 char* tmpStr = BN_bn2dec(toBigNum(a)); 279 if (tmpStr == NULL) { 280 throwException(env); 281 return NULL; 282 } 283 char* retStr = leadingZerosTrimmed(tmpStr); 284 jstring returnJString = env->NewStringUTF(retStr); 285 OPENSSL_free(tmpStr); 286 return returnJString; 287 } 288 289 static jstring NativeBN_BN_bn2hex(JNIEnv* env, jclass, jlong a) { 290 if (!oneValidHandle(env, a)) return NULL; 291 char* tmpStr = BN_bn2hex(toBigNum(a)); 292 if (tmpStr == NULL) { 293 throwException(env); 294 return NULL; 295 } 296 char* retStr = leadingZerosTrimmed(tmpStr); 297 jstring returnJString = env->NewStringUTF(retStr); 298 OPENSSL_free(tmpStr); 299 return returnJString; 300 } 301 302 static jbyteArray NativeBN_BN_bn2bin(JNIEnv* env, jclass, jlong a0) { 303 if (!oneValidHandle(env, a0)) return NULL; 304 BIGNUM* a = toBigNum(a0); 305 jbyteArray result = env->NewByteArray(BN_num_bytes(a)); 306 if (result == NULL) { 307 return NULL; 308 } 309 ScopedByteArrayRW bytes(env, result); 310 if (bytes.get() == NULL) { 311 return NULL; 312 } 313 BN_bn2bin(a, reinterpret_cast<unsigned char*>(bytes.get())); 314 return result; 315 } 316 317 static jintArray NativeBN_bn2litEndInts(JNIEnv* env, jclass, jlong a0) { 318 if (!oneValidHandle(env, a0)) return NULL; 319 320 BIGNUM* a = toBigNum(a0); 321 322 // The number of integers we need is BN_num_bytes(a) / sizeof(int), rounded up 323 int intLen = (BN_num_bytes(a) + sizeof(int) - 1) / sizeof(int); 324 325 // Allocate our result with the JNI boilerplate 326 jintArray result = env->NewIntArray(intLen); 327 328 if (result == NULL) { 329 throwException(env); 330 return NULL; 331 } 332 333 ScopedIntArrayRW ints(env, result); 334 335 unsigned int* uints = reinterpret_cast<unsigned int*>(ints.get()); 336 if (uints == NULL) { 337 throwException(env); 338 return NULL; 339 } 340 341 // We can simply interpret a little-endian byte stream as a little-endian integer stream. 342 if (!BN_bn2le_padded(reinterpret_cast<uint8_t*>(uints), intLen * sizeof(int), a)) { 343 throwException(env); 344 return NULL; 345 } 346 347 return result; 348 } 349 350 static int NativeBN_sign(JNIEnv* env, jclass, jlong a) { 351 if (!oneValidHandle(env, a)) return -2; 352 if (BN_is_zero(toBigNum(a))) { 353 return 0; 354 } else if (BN_is_negative(toBigNum(a))) { 355 return -1; 356 } 357 return 1; 358 } 359 360 static void NativeBN_BN_set_negative(JNIEnv* env, jclass, jlong b, int n) { 361 if (!oneValidHandle(env, b)) return; 362 BN_set_negative(toBigNum(b), n); 363 } 364 365 static int NativeBN_bitLength(JNIEnv* env, jclass, jlong a0) { 366 if (!oneValidHandle(env, a0)) return JNI_FALSE; 367 BIGNUM* a = toBigNum(a0); 368 369 // If a is not negative, we can use BN_num_bits directly. 370 if (!BN_is_negative(a)) { 371 return BN_num_bits(a); 372 } 373 374 // In the negative case, the number of bits in a is the same as the number of bits in |a|, 375 // except one less when |a| is a power of two. 376 BIGNUM positiveA; 377 BN_init(&positiveA); 378 379 if (!BN_copy(&positiveA, a)) { 380 BN_free(&positiveA); 381 throwException(env); 382 return -1; 383 } 384 385 BN_set_negative(&positiveA, false); 386 int numBits = BN_is_pow2(&positiveA) ? BN_num_bits(&positiveA) - 1 : BN_num_bits(&positiveA); 387 388 BN_free(&positiveA); 389 return numBits; 390 } 391 392 static jboolean NativeBN_BN_is_bit_set(JNIEnv* env, jclass, jlong a, int n) { 393 if (!oneValidHandle(env, a)) return JNI_FALSE; 394 395 // NOTE: this is only called in the positive case, so BN_is_bit_set is fine here. 396 return BN_is_bit_set(toBigNum(a), n) ? JNI_TRUE : JNI_FALSE; 397 } 398 399 static void NativeBN_BN_shift(JNIEnv* env, jclass, jlong r, jlong a, int n) { 400 if (!twoValidHandles(env, r, a)) return; 401 int ok; 402 if (n >= 0) { 403 ok = BN_lshift(toBigNum(r), toBigNum(a), n); 404 } else { 405 ok = BN_rshift(toBigNum(r), toBigNum(a), -n); 406 } 407 if (!ok) { 408 throwException(env); 409 } 410 } 411 412 static void NativeBN_BN_add_word(JNIEnv* env, jclass, jlong a, BN_ULONG w) { 413 if (!oneValidHandle(env, a)) return; 414 if (!BN_add_word(toBigNum(a), w)) { 415 throwException(env); 416 } 417 } 418 419 static void NativeBN_BN_mul_word(JNIEnv* env, jclass, jlong a, BN_ULONG w) { 420 if (!oneValidHandle(env, a)) return; 421 if (!BN_mul_word(toBigNum(a), w)) { 422 throwException(env); 423 } 424 } 425 426 static BN_ULONG NativeBN_BN_mod_word(JNIEnv* env, jclass, jlong a, BN_ULONG w) { 427 if (!oneValidHandle(env, a)) return 0; 428 BN_ULONG result = BN_mod_word(toBigNum(a), w); 429 if (result == (BN_ULONG)-1) { 430 throwException(env); 431 } 432 return result; 433 } 434 435 static void NativeBN_BN_add(JNIEnv* env, jclass, jlong r, jlong a, jlong b) { 436 if (!threeValidHandles(env, r, a, b)) return; 437 if (!BN_add(toBigNum(r), toBigNum(a), toBigNum(b))) { 438 throwException(env); 439 } 440 } 441 442 static void NativeBN_BN_sub(JNIEnv* env, jclass, jlong r, jlong a, jlong b) { 443 if (!threeValidHandles(env, r, a, b)) return; 444 if (!BN_sub(toBigNum(r), toBigNum(a), toBigNum(b))) { 445 throwException(env); 446 } 447 } 448 449 static void NativeBN_BN_gcd(JNIEnv* env, jclass, jlong r, jlong a, jlong b) { 450 if (!threeValidHandles(env, r, a, b)) return; 451 Unique_BN_CTX ctx(BN_CTX_new()); 452 if (!BN_gcd(toBigNum(r), toBigNum(a), toBigNum(b), ctx.get())) { 453 throwException(env); 454 } 455 } 456 457 static void NativeBN_BN_mul(JNIEnv* env, jclass, jlong r, jlong a, jlong b) { 458 if (!threeValidHandles(env, r, a, b)) return; 459 Unique_BN_CTX ctx(BN_CTX_new()); 460 if (!BN_mul(toBigNum(r), toBigNum(a), toBigNum(b), ctx.get())) { 461 throwException(env); 462 } 463 } 464 465 static void NativeBN_BN_exp(JNIEnv* env, jclass, jlong r, jlong a, jlong p) { 466 if (!threeValidHandles(env, r, a, p)) return; 467 Unique_BN_CTX ctx(BN_CTX_new()); 468 if (!BN_exp(toBigNum(r), toBigNum(a), toBigNum(p), ctx.get())) { 469 throwException(env); 470 } 471 } 472 473 static void NativeBN_BN_div(JNIEnv* env, jclass, jlong dv, jlong rem, jlong m, jlong d) { 474 if (!fourValidHandles(env, (rem ? rem : dv), (dv ? dv : rem), m, d)) return; 475 Unique_BN_CTX ctx(BN_CTX_new()); 476 if (!BN_div(toBigNum(dv), toBigNum(rem), toBigNum(m), toBigNum(d), ctx.get())) { 477 throwException(env); 478 } 479 } 480 481 static void NativeBN_BN_nnmod(JNIEnv* env, jclass, jlong r, jlong a, jlong m) { 482 if (!threeValidHandles(env, r, a, m)) return; 483 Unique_BN_CTX ctx(BN_CTX_new()); 484 if (!BN_nnmod(toBigNum(r), toBigNum(a), toBigNum(m), ctx.get())) { 485 throwException(env); 486 } 487 } 488 489 static void NativeBN_BN_mod_exp(JNIEnv* env, jclass, jlong r, jlong a, jlong p, jlong m) { 490 if (!fourValidHandles(env, r, a, p, m)) return; 491 Unique_BN_CTX ctx(BN_CTX_new()); 492 if (!BN_mod_exp(toBigNum(r), toBigNum(a), toBigNum(p), toBigNum(m), ctx.get())) { 493 throwException(env); 494 } 495 } 496 497 static void NativeBN_BN_mod_inverse(JNIEnv* env, jclass, jlong ret, jlong a, jlong n) { 498 if (!threeValidHandles(env, ret, a, n)) return; 499 Unique_BN_CTX ctx(BN_CTX_new()); 500 if (!BN_mod_inverse(toBigNum(ret), toBigNum(a), toBigNum(n), ctx.get())) { 501 throwException(env); 502 } 503 } 504 505 static void NativeBN_BN_generate_prime_ex(JNIEnv* env, jclass, jlong ret, int bits, 506 jboolean safe, jlong add, jlong rem) { 507 if (!oneValidHandle(env, ret)) return; 508 if (!BN_generate_prime_ex(toBigNum(ret), bits, safe, toBigNum(add), toBigNum(rem), 509 NULL)) { 510 throwException(env); 511 } 512 } 513 514 static jboolean NativeBN_BN_primality_test(JNIEnv* env, jclass, jlong candidate, int checks, 515 jboolean do_trial_decryption) { 516 if (!oneValidHandle(env, candidate)) return JNI_FALSE; 517 Unique_BN_CTX ctx(BN_CTX_new()); 518 int is_probably_prime; 519 if (!BN_primality_test(&is_probably_prime, toBigNum(candidate), checks, ctx.get(), 520 do_trial_decryption, NULL)) { 521 throwException(env); 522 return JNI_FALSE; 523 } 524 return is_probably_prime ? JNI_TRUE : JNI_FALSE; 525 } 526 527 static JNINativeMethod gMethods[] = { 528 NATIVE_METHOD(NativeBN, BN_add, "(JJJ)V"), 529 NATIVE_METHOD(NativeBN, BN_add_word, "(JI)V"), 530 NATIVE_METHOD(NativeBN, BN_bin2bn, "([BIZJ)V"), 531 NATIVE_METHOD(NativeBN, BN_bn2bin, "(J)[B"), 532 NATIVE_METHOD(NativeBN, BN_bn2dec, "(J)Ljava/lang/String;"), 533 NATIVE_METHOD(NativeBN, BN_bn2hex, "(J)Ljava/lang/String;"), 534 NATIVE_METHOD(NativeBN, BN_cmp, "(JJ)I"), 535 NATIVE_METHOD(NativeBN, BN_copy, "(JJ)V"), 536 NATIVE_METHOD(NativeBN, BN_dec2bn, "(JLjava/lang/String;)I"), 537 NATIVE_METHOD(NativeBN, BN_div, "(JJJJ)V"), 538 NATIVE_METHOD(NativeBN, BN_exp, "(JJJ)V"), 539 NATIVE_METHOD(NativeBN, BN_free, "(J)V"), 540 NATIVE_METHOD(NativeBN, BN_gcd, "(JJJ)V"), 541 NATIVE_METHOD(NativeBN, BN_generate_prime_ex, "(JIZJJ)V"), 542 NATIVE_METHOD(NativeBN, BN_hex2bn, "(JLjava/lang/String;)I"), 543 NATIVE_METHOD(NativeBN, BN_is_bit_set, "(JI)Z"), 544 NATIVE_METHOD(NativeBN, BN_primality_test, "(JIZ)Z"), 545 NATIVE_METHOD(NativeBN, BN_mod_exp, "(JJJJ)V"), 546 NATIVE_METHOD(NativeBN, BN_mod_inverse, "(JJJ)V"), 547 NATIVE_METHOD(NativeBN, BN_mod_word, "(JI)I"), 548 NATIVE_METHOD(NativeBN, BN_mul, "(JJJ)V"), 549 NATIVE_METHOD(NativeBN, BN_mul_word, "(JI)V"), 550 NATIVE_METHOD(NativeBN, BN_new, "()J"), 551 NATIVE_METHOD(NativeBN, BN_nnmod, "(JJJ)V"), 552 NATIVE_METHOD(NativeBN, BN_set_negative, "(JI)V"), 553 NATIVE_METHOD(NativeBN, BN_shift, "(JJI)V"), 554 NATIVE_METHOD(NativeBN, BN_sub, "(JJJ)V"), 555 NATIVE_METHOD(NativeBN, bitLength, "(J)I"), 556 NATIVE_METHOD(NativeBN, bn2litEndInts, "(J)[I"), 557 NATIVE_METHOD(NativeBN, getNativeFinalizer, "()J"), 558 NATIVE_METHOD(NativeBN, litEndInts2bn, "([IIZJ)V"), 559 NATIVE_METHOD(NativeBN, longInt, "(J)J"), 560 NATIVE_METHOD(NativeBN, putLongInt, "(JJ)V"), 561 NATIVE_METHOD(NativeBN, putULongInt, "(JJZ)V"), 562 NATIVE_METHOD(NativeBN, sign, "(J)I"), 563 NATIVE_METHOD(NativeBN, twosComp2bn, "([BIJ)V"), 564 }; 565 void register_java_math_NativeBN(JNIEnv* env) { 566 jniRegisterNativeMethods(env, "java/math/NativeBN", gMethods, NELEM(gMethods)); 567 } 568