Coverage Report

Created: 2024-11-21 07:03

/src/openssl/crypto/bn/bn_kron.c
Line
Count
Source (jump to first uncovered line)
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
533k
#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
544
{
19
544
    int i;
20
544
    int ret = -2;               /* avoid 'uninitialized' warning */
21
544
    int err = 0;
22
544
    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
544
    static const int tab[8] = { 0, 1, 0, -1, 0, -1, 0, 1 };
31
32
544
    bn_check_top(a);
33
544
    bn_check_top(b);
34
35
544
    BN_CTX_start(ctx);
36
544
    A = BN_CTX_get(ctx);
37
544
    B = BN_CTX_get(ctx);
38
544
    if (B == NULL)
39
0
        goto end;
40
41
544
    err = !BN_copy(A, a);
42
544
    if (err)
43
0
        goto end;
44
544
    err = !BN_copy(B, b);
45
544
    if (err)
46
0
        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
544
    if (BN_is_zero(B)) {
57
23
        ret = BN_abs_is_word(A, 1);
58
23
        goto end;
59
23
    }
60
61
    /* Cohen's step 2: */
62
63
521
    if (!BN_is_odd(A) && !BN_is_odd(B)) {
64
26
        ret = 0;
65
26
        goto end;
66
26
    }
67
68
    /* now  B  is non-zero */
69
495
    i = 0;
70
1.64k
    while (!BN_is_bit_set(B, i))
71
1.14k
        i++;
72
495
    err = !BN_rshift(B, B, i);
73
495
    if (err)
74
0
        goto end;
75
495
    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
48
        ret = tab[BN_lsw(A) & 7];
81
447
    } else {
82
        /* i is even */
83
447
        ret = 1;
84
447
    }
85
86
495
    if (B->neg) {
87
0
        B->neg = 0;
88
0
        if (A->neg)
89
0
            ret = -ret;
90
0
    }
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
226k
    while (1) {
98
        /* Cohen's step 3: */
99
100
        /*  B  is positive and odd */
101
102
226k
        if (BN_is_zero(A)) {
103
495
            ret = BN_is_one(B) ? ret : 0;
104
495
            goto end;
105
495
        }
106
107
        /* now  A  is non-zero */
108
225k
        i = 0;
109
477k
        while (!BN_is_bit_set(A, i))
110
251k
            i++;
111
225k
        err = !BN_rshift(A, A, i);
112
225k
        if (err)
113
0
            goto end;
114
225k
        if (i & 1) {
115
            /* i is odd */
116
            /* multiply 'ret' by  $(-1)^{(B^2-1)/8}$ */
117
81.7k
            ret = ret * tab[BN_lsw(B) & 7];
118
81.7k
        }
119
120
        /* Cohen's step 4: */
121
        /* multiply 'ret' by  $(-1)^{(A-1)(B-1)/4}$ */
122
225k
        if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2)
123
55.9k
            ret = -ret;
124
125
        /* (A, B) := (B mod |A|, |A|) */
126
225k
        err = !BN_nnmod(B, B, A, ctx);
127
225k
        if (err)
128
0
            goto end;
129
225k
        tmp = A;
130
225k
        A = B;
131
225k
        B = tmp;
132
225k
        tmp->neg = 0;
133
225k
    }
134
544
 end:
135
544
    BN_CTX_end(ctx);
136
544
    if (err)
137
0
        return -2;
138
544
    else
139
544
        return ret;
140
544
}