Absolute File Name: | /home/opencoverage/opencoverage/guest-scripts/openssl/src/crypto/bn/bn_kron.c |
Source code | Switch to Preprocessed file |
Line | Source | Count | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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_lcl.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)
| 0-21124 | ||||||||||||||||||
39 | goto end; never executed: goto end; | 0 | ||||||||||||||||||
40 | - | |||||||||||||||||||
41 | err = !BN_copy(A, a); | - | ||||||||||||||||||
42 | if (err)
| 0-21124 | ||||||||||||||||||
43 | goto end; never executed: goto end; | 0 | ||||||||||||||||||
44 | err = !BN_copy(B, b); | - | ||||||||||||||||||
45 | if (err)
| 0-21124 | ||||||||||||||||||
46 | goto end; never executed: goto end; | 0 | ||||||||||||||||||
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)) {
| 0-21124 | ||||||||||||||||||
57 | ret = BN_abs_is_word(A, 1); | - | ||||||||||||||||||
58 | goto end; never executed: goto end; | 0 | ||||||||||||||||||
59 | } | - | ||||||||||||||||||
60 | - | |||||||||||||||||||
61 | /* Cohen's step 2: */ | - | ||||||||||||||||||
62 | - | |||||||||||||||||||
63 | if (!BN_is_odd(A) && !BN_is_odd(B)) {
| 0-10723 | ||||||||||||||||||
64 | ret = 0; | - | ||||||||||||||||||
65 | goto end; never executed: goto end; | 0 | ||||||||||||||||||
66 | } | - | ||||||||||||||||||
67 | - | |||||||||||||||||||
68 | /* now B is non-zero */ | - | ||||||||||||||||||
69 | i = 0; | - | ||||||||||||||||||
70 | while (!BN_is_bit_set(B, i))
| 0-21124 | ||||||||||||||||||
71 | i++; never executed: i++; | 0 | ||||||||||||||||||
72 | err = !BN_rshift(B, B, i); | - | ||||||||||||||||||
73 | if (err)
| 0-21124 | ||||||||||||||||||
74 | goto end; never executed: goto end; | 0 | ||||||||||||||||||
75 | if (i & 1) {
| 0-21124 | ||||||||||||||||||
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 { never executed: end of block | 0 | ||||||||||||||||||
82 | /* i is even */ | - | ||||||||||||||||||
83 | ret = 1; | - | ||||||||||||||||||
84 | } executed 21124 times by 1 test: end of block Executed by:
| 21124 | ||||||||||||||||||
85 | - | |||||||||||||||||||
86 | if (B->neg) {
| 100-21024 | ||||||||||||||||||
87 | B->neg = 0; | - | ||||||||||||||||||
88 | if (A->neg)
| 50 | ||||||||||||||||||
89 | ret = -ret; executed 50 times by 1 test: ret = -ret; Executed by:
| 50 | ||||||||||||||||||
90 | } executed 100 times by 1 test: end of block Executed by:
| 100 | ||||||||||||||||||
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)) {
| 21124-101152 | ||||||||||||||||||
103 | ret = BN_is_one(B) ? ret : 0;
| 5-21119 | ||||||||||||||||||
104 | goto end; executed 21124 times by 1 test: goto end; Executed by:
| 21124 | ||||||||||||||||||
105 | } | - | ||||||||||||||||||
106 | - | |||||||||||||||||||
107 | /* now A is non-zero */ | - | ||||||||||||||||||
108 | i = 0; | - | ||||||||||||||||||
109 | while (!BN_is_bit_set(A, i))
| 100720-101152 | ||||||||||||||||||
110 | i++; executed 100720 times by 1 test: i++; Executed by:
| 100720 | ||||||||||||||||||
111 | err = !BN_rshift(A, A, i); | - | ||||||||||||||||||
112 | if (err)
| 0-101152 | ||||||||||||||||||
113 | goto end; never executed: goto end; | 0 | ||||||||||||||||||
114 | if (i & 1) {
| 33446-67706 | ||||||||||||||||||
115 | /* i is odd */ | - | ||||||||||||||||||
116 | /* multiply 'ret' by $(-1)^{(B^2-1)/8}$ */ | - | ||||||||||||||||||
117 | ret = ret * tab[BN_lsw(B) & 7]; | - | ||||||||||||||||||
118 | } executed 33446 times by 1 test: end of block Executed by:
| 33446 | ||||||||||||||||||
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)
| 0-101102 | ||||||||||||||||||
123 | ret = -ret; executed 16549 times by 1 test: ret = -ret; Executed by:
| 16549 | ||||||||||||||||||
124 | - | |||||||||||||||||||
125 | /* (A, B) := (B mod |A|, |A|) */ | - | ||||||||||||||||||
126 | err = !BN_nnmod(B, B, A, ctx); | - | ||||||||||||||||||
127 | if (err)
| 0-101152 | ||||||||||||||||||
128 | goto end; never executed: goto end; | 0 | ||||||||||||||||||
129 | tmp = A; | - | ||||||||||||||||||
130 | A = B; | - | ||||||||||||||||||
131 | B = tmp; | - | ||||||||||||||||||
132 | tmp->neg = 0; | - | ||||||||||||||||||
133 | } executed 101152 times by 1 test: end of block Executed by:
| 101152 | ||||||||||||||||||
134 | end: code before this statement never executed: end: | 0 | ||||||||||||||||||
135 | BN_CTX_end(ctx); | - | ||||||||||||||||||
136 | if (err)
| 0-21124 | ||||||||||||||||||
137 | return -2; never executed: return -2; | 0 | ||||||||||||||||||
138 | else | - | ||||||||||||||||||
139 | return ret; executed 21124 times by 1 test: return ret; Executed by:
| 21124 | ||||||||||||||||||
140 | } | - | ||||||||||||||||||
Source code | Switch to Preprocessed file |