Branch data Line data Source code
1 : : /* crypto/bn/bn_kron.c */
2 : : /* ====================================================================
3 : : * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved.
4 : : *
5 : : * Redistribution and use in source and binary forms, with or without
6 : : * modification, are permitted provided that the following conditions
7 : : * are met:
8 : : *
9 : : * 1. Redistributions of source code must retain the above copyright
10 : : * notice, this list of conditions and the following disclaimer.
11 : : *
12 : : * 2. Redistributions in binary form must reproduce the above copyright
13 : : * notice, this list of conditions and the following disclaimer in
14 : : * the documentation and/or other materials provided with the
15 : : * distribution.
16 : : *
17 : : * 3. All advertising materials mentioning features or use of this
18 : : * software must display the following acknowledgment:
19 : : * "This product includes software developed by the OpenSSL Project
20 : : * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
21 : : *
22 : : * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
23 : : * endorse or promote products derived from this software without
24 : : * prior written permission. For written permission, please contact
25 : : * openssl-core@openssl.org.
26 : : *
27 : : * 5. Products derived from this software may not be called "OpenSSL"
28 : : * nor may "OpenSSL" appear in their names without prior written
29 : : * permission of the OpenSSL Project.
30 : : *
31 : : * 6. Redistributions of any form whatsoever must retain the following
32 : : * acknowledgment:
33 : : * "This product includes software developed by the OpenSSL Project
34 : : * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
35 : : *
36 : : * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
37 : : * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
38 : : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
39 : : * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
40 : : * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41 : : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
42 : : * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43 : : * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44 : : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
45 : : * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46 : : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
47 : : * OF THE POSSIBILITY OF SUCH DAMAGE.
48 : : * ====================================================================
49 : : *
50 : : * This product includes cryptographic software written by Eric Young
51 : : * (eay@cryptsoft.com). This product includes software written by Tim
52 : : * Hudson (tjh@cryptsoft.com).
53 : : *
54 : : */
55 : :
56 : : #include "cryptlib.h"
57 : : #include "bn_lcl.h"
58 : :
59 : : /* least significant word */
60 : : #define BN_lsw(n) (((n)->top == 0) ? (BN_ULONG) 0 : (n)->d[0])
61 : :
62 : : /* Returns -2 for errors because both -1 and 0 are valid results. */
63 : 138 : int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
64 : : {
65 : : int i;
66 : 138 : int ret = -2; /* avoid 'uninitialized' warning */
67 : 138 : int err = 0;
68 : : BIGNUM *A, *B, *tmp;
69 : : /* In 'tab', only odd-indexed entries are relevant:
70 : : * For any odd BIGNUM n,
71 : : * tab[BN_lsw(n) & 7]
72 : : * is $(-1)^{(n^2-1)/8}$ (using TeX notation).
73 : : * Note that the sign of n does not matter.
74 : : */
75 : : static const int tab[8] = {0, 1, 0, -1, 0, -1, 0, 1};
76 : :
77 : : bn_check_top(a);
78 : : bn_check_top(b);
79 : :
80 : 138 : BN_CTX_start(ctx);
81 : 138 : A = BN_CTX_get(ctx);
82 : 138 : B = BN_CTX_get(ctx);
83 [ + - ]: 138 : if (B == NULL) goto end;
84 : :
85 : 138 : err = !BN_copy(A, a);
86 [ + - ]: 138 : if (err) goto end;
87 : 138 : err = !BN_copy(B, b);
88 [ + - ]: 138 : if (err) goto end;
89 : :
90 : : /*
91 : : * Kronecker symbol, imlemented according to Henri Cohen,
92 : : * "A Course in Computational Algebraic Number Theory"
93 : : * (algorithm 1.4.10).
94 : : */
95 : :
96 : : /* Cohen's step 1: */
97 : :
98 [ - + ]: 138 : if (BN_is_zero(B))
99 : : {
100 [ # # ][ # # ]: 0 : ret = BN_abs_is_word(A, 1);
101 : 0 : goto end;
102 : : }
103 : :
104 : : /* Cohen's step 2: */
105 : :
106 [ + - ][ + + ]: 138 : if (!BN_is_odd(A) && !BN_is_odd(B))
[ + - ][ + - ]
107 : : {
108 : : ret = 0;
109 : : goto end;
110 : : }
111 : :
112 : : /* now B is non-zero */
113 : : i = 0;
114 [ - + ]: 138 : while (!BN_is_bit_set(B, i))
115 : 0 : i++;
116 : 138 : err = !BN_rshift(B, B, i);
117 [ + - ]: 138 : if (err) goto end;
118 [ - + ]: 138 : if (i & 1)
119 : : {
120 : : /* i is odd */
121 : : /* (thus B was even, thus A must be odd!) */
122 : :
123 : : /* set 'ret' to $(-1)^{(A^2-1)/8}$ */
124 [ # # ]: 0 : ret = tab[BN_lsw(A) & 7];
125 : : }
126 : : else
127 : : {
128 : : /* i is even */
129 : : ret = 1;
130 : : }
131 : :
132 [ + + ]: 138 : if (B->neg)
133 : : {
134 : 100 : B->neg = 0;
135 [ + + ]: 100 : if (A->neg)
136 : 138 : ret = -ret;
137 : : }
138 : :
139 : : /* now B is positive and odd, so what remains to be done is
140 : : * to compute the Jacobi symbol (A/B) and multiply it by 'ret' */
141 : :
142 : : while (1)
143 : : {
144 : : /* Cohen's step 3: */
145 : :
146 : : /* B is positive and odd */
147 : :
148 [ + + ]: 18900 : if (BN_is_zero(A))
149 : : {
150 [ + - ][ + - ]: 138 : ret = BN_is_one(B) ? ret : 0;
[ + - ]
151 : 138 : goto end;
152 : : }
153 : :
154 : : /* now A is non-zero */
155 : : i = 0;
156 [ + + ]: 39963 : while (!BN_is_bit_set(A, i))
157 : 21201 : i++;
158 : 18762 : err = !BN_rshift(A, A, i);
159 [ + - ]: 18762 : if (err) goto end;
160 [ + + ]: 18762 : if (i & 1)
161 : : {
162 : : /* i is odd */
163 : : /* multiply 'ret' by $(-1)^{(B^2-1)/8}$ */
164 [ + - ]: 6873 : ret = ret * tab[BN_lsw(B) & 7];
165 : : }
166 : :
167 : : /* Cohen's step 4: */
168 : : /* multiply 'ret' by $(-1)^{(A-1)(B-1)/4}$ */
169 [ + + ][ + - ]: 18762 : if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2)
[ + - ][ + - ]
[ + + ]
170 : 4603 : ret = -ret;
171 : :
172 : : /* (A, B) := (B mod |A|, |A|) */
173 : 18762 : err = !BN_nnmod(B, B, A, ctx);
174 [ + - ]: 18762 : if (err) goto end;
175 : 18762 : tmp = A; A = B; B = tmp;
176 : 18762 : tmp->neg = 0;
177 : 18762 : }
178 : : end:
179 : 138 : BN_CTX_end(ctx);
180 [ + - ]: 138 : if (err)
181 : : return -2;
182 : : else
183 : 138 : return ret;
184 : : }
|
