| 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 | }
|
|---|
