1/*
2 * Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (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. */
17int 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}
141