| yuezonghe | 824eb0c | 2024-06-27 02:32:26 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved. |
| 3 | * |
| 4 | * Licensed under the OpenSSL license (the "License"). You may not use |
| 5 | * this file except in compliance with the License. You can obtain a copy |
| 6 | * in the file LICENSE in the source distribution or at |
| 7 | * https://www.openssl.org/source/license.html |
| 8 | */ |
| 9 | |
| 10 | #include "internal/cryptlib.h" |
| 11 | #include "bn_local.h" |
| 12 | |
| 13 | /* least significant word */ |
| 14 | #define BN_lsw(n) (((n)->top == 0) ? (BN_ULONG) 0 : (n)->d[0]) |
| 15 | |
| 16 | /* Returns -2 for errors because both -1 and 0 are valid results. */ |
| 17 | int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) |
| 18 | { |
| 19 | int i; |
| 20 | int ret = -2; /* avoid 'uninitialized' warning */ |
| 21 | int err = 0; |
| 22 | BIGNUM *A, *B, *tmp; |
| 23 | /*- |
| 24 | * In 'tab', only odd-indexed entries are relevant: |
| 25 | * For any odd BIGNUM n, |
| 26 | * tab[BN_lsw(n) & 7] |
| 27 | * is $(-1)^{(n^2-1)/8}$ (using TeX notation). |
| 28 | * Note that the sign of n does not matter. |
| 29 | */ |
| 30 | static const int tab[8] = { 0, 1, 0, -1, 0, -1, 0, 1 }; |
| 31 | |
| 32 | bn_check_top(a); |
| 33 | bn_check_top(b); |
| 34 | |
| 35 | BN_CTX_start(ctx); |
| 36 | A = BN_CTX_get(ctx); |
| 37 | B = BN_CTX_get(ctx); |
| 38 | if (B == NULL) |
| 39 | goto end; |
| 40 | |
| 41 | err = !BN_copy(A, a); |
| 42 | if (err) |
| 43 | goto end; |
| 44 | err = !BN_copy(B, b); |
| 45 | if (err) |
| 46 | goto end; |
| 47 | |
| 48 | /* |
| 49 | * Kronecker symbol, implemented according to Henri Cohen, |
| 50 | * "A Course in Computational Algebraic Number Theory" |
| 51 | * (algorithm 1.4.10). |
| 52 | */ |
| 53 | |
| 54 | /* Cohen's step 1: */ |
| 55 | |
| 56 | if (BN_is_zero(B)) { |
| 57 | ret = BN_abs_is_word(A, 1); |
| 58 | goto end; |
| 59 | } |
| 60 | |
| 61 | /* Cohen's step 2: */ |
| 62 | |
| 63 | if (!BN_is_odd(A) && !BN_is_odd(B)) { |
| 64 | ret = 0; |
| 65 | goto end; |
| 66 | } |
| 67 | |
| 68 | /* now B is non-zero */ |
| 69 | i = 0; |
| 70 | while (!BN_is_bit_set(B, i)) |
| 71 | i++; |
| 72 | err = !BN_rshift(B, B, i); |
| 73 | if (err) |
| 74 | goto end; |
| 75 | if (i & 1) { |
| 76 | /* i is odd */ |
| 77 | /* (thus B was even, thus A must be odd!) */ |
| 78 | |
| 79 | /* set 'ret' to $(-1)^{(A^2-1)/8}$ */ |
| 80 | ret = tab[BN_lsw(A) & 7]; |
| 81 | } else { |
| 82 | /* i is even */ |
| 83 | ret = 1; |
| 84 | } |
| 85 | |
| 86 | if (B->neg) { |
| 87 | B->neg = 0; |
| 88 | if (A->neg) |
| 89 | ret = -ret; |
| 90 | } |
| 91 | |
| 92 | /* |
| 93 | * now B is positive and odd, so what remains to be done is to compute |
| 94 | * the Jacobi symbol (A/B) and multiply it by 'ret' |
| 95 | */ |
| 96 | |
| 97 | while (1) { |
| 98 | /* Cohen's step 3: */ |
| 99 | |
| 100 | /* B is positive and odd */ |
| 101 | |
| 102 | if (BN_is_zero(A)) { |
| 103 | ret = BN_is_one(B) ? ret : 0; |
| 104 | goto end; |
| 105 | } |
| 106 | |
| 107 | /* now A is non-zero */ |
| 108 | i = 0; |
| 109 | while (!BN_is_bit_set(A, i)) |
| 110 | i++; |
| 111 | err = !BN_rshift(A, A, i); |
| 112 | if (err) |
| 113 | goto end; |
| 114 | if (i & 1) { |
| 115 | /* i is odd */ |
| 116 | /* multiply 'ret' by $(-1)^{(B^2-1)/8}$ */ |
| 117 | ret = ret * tab[BN_lsw(B) & 7]; |
| 118 | } |
| 119 | |
| 120 | /* Cohen's step 4: */ |
| 121 | /* multiply 'ret' by $(-1)^{(A-1)(B-1)/4}$ */ |
| 122 | if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2) |
| 123 | ret = -ret; |
| 124 | |
| 125 | /* (A, B) := (B mod |A|, |A|) */ |
| 126 | err = !BN_nnmod(B, B, A, ctx); |
| 127 | if (err) |
| 128 | goto end; |
| 129 | tmp = A; |
| 130 | A = B; |
| 131 | B = tmp; |
| 132 | tmp->neg = 0; |
| 133 | } |
| 134 | end: |
| 135 | BN_CTX_end(ctx); |
| 136 | if (err) |
| 137 | return -2; |
| 138 | else |
| 139 | return ret; |
| 140 | } |