cryptlib
3.4.1
Main Page
Namespaces
Classes
Files
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Properties
Macros
bn
ec_kron.c
Go to the documentation of this file.
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
*
[email protected]
.
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
* (
[email protected]
). This product includes software written by Tim
52
* Hudson (
[email protected]
).
53
*
54
*/
55
56
#if defined( INC_ALL )
57
#include "
ec_lcl.h
"
58
#else
59
#include "
bn/ec_lcl.h
"
60
#endif
/* Compiler-specific includes */
61
62
#if defined( USE_ECDH ) || defined( USE_ECDSA )
63
64
/* least significant word */
65
#define BN_lsw(n) (((n)->top == 0) ? (BN_ULONG) 0 : (n)->d[0])
66
67
/* Returns -2 for errors because both -1 and 0 are valid results. */
68
int
BN_kronecker
(
const
BIGNUM
*a,
const
BIGNUM
*b,
BN_CTX
*ctx)
69
{
70
int
i;
71
int
ret = -2;
/* avoid 'uninitialized' warning */
72
int
err = 0;
73
BIGNUM
*A, *B, *tmp;
74
/* In 'tab', only odd-indexed entries are relevant:
75
* For any odd BIGNUM n,
76
* tab[BN_lsw(n) & 7]
77
* is $(-1)^{(n^2-1)/8}$ (using TeX notation).
78
* Note that the sign of n does not matter.
79
*/
80
static
const
int
tab[8] = {0, 1, 0, -1, 0, -1, 0, 1};
81
82
bn_check_top
(a);
83
bn_check_top
(b);
84
85
BN_CTX_start
(ctx);
86
A =
BN_CTX_get
(ctx);
87
B =
BN_CTX_get
(ctx);
88
if
(B == NULL)
goto
end;
89
90
err = !
BN_copy
(A, a);
91
if
(err)
goto
end;
92
err = !
BN_copy
(B, b);
93
if
(err)
goto
end;
94
95
/*
96
* Kronecker symbol, imlemented according to Henri Cohen,
97
* "A Course in Computational Algebraic Number Theory"
98
* (algorithm 1.4.10).
99
*/
100
101
/* Cohen's step 1: */
102
103
if
(
BN_is_zero
(B))
104
{
105
ret =
BN_abs_is_word
(A, 1);
106
goto
end;
107
}
108
109
/* Cohen's step 2: */
110
111
if
(!
BN_is_odd
(A) && !
BN_is_odd
(B))
112
{
113
ret = 0;
114
goto
end;
115
}
116
117
/* now B is non-zero */
118
i = 0;
119
while
(!
BN_is_bit_set
(B, i))
120
i++;
121
err = !
BN_rshift
(B, B, i);
122
if
(err)
goto
end;
123
if
(i & 1)
124
{
125
/* i is odd */
126
/* (thus B was even, thus A must be odd!) */
127
128
/* set 'ret' to $(-1)^{(A^2-1)/8}$ */
129
ret = tab[BN_lsw(A) & 7];
130
}
131
else
132
{
133
/* i is even */
134
ret = 1;
135
}
136
137
if
(B->
neg
)
138
{
139
B->
neg
= 0;
140
if
(A->
neg
)
141
ret = -ret;
142
}
143
144
/* now B is positive and odd, so what remains to be done is
145
* to compute the Jacobi symbol (A/B) and multiply it by 'ret' */
146
147
while
(1)
148
{
149
/* Cohen's step 3: */
150
151
/* B is positive and odd */
152
153
if
(
BN_is_zero
(A))
154
{
155
ret =
BN_is_one
(B) ? ret : 0;
156
goto
end;
157
}
158
159
/* now A is non-zero */
160
i = 0;
161
while
(!
BN_is_bit_set
(A, i))
162
i++;
163
err = !
BN_rshift
(A, A, i);
164
if
(err)
goto
end;
165
if
(i & 1)
166
{
167
/* i is odd */
168
/* multiply 'ret' by $(-1)^{(B^2-1)/8}$ */
169
ret = ret * tab[BN_lsw(B) & 7];
170
}
171
172
/* Cohen's step 4: */
173
/* multiply 'ret' by $(-1)^{(A-1)(B-1)/4}$ */
174
if
((A->
neg
? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2)
175
ret = -ret;
176
177
/* (A, B) := (B mod |A|, |A|) */
178
err = !
BN_nnmod
(B, B, A, ctx);
179
if
(err)
goto
end;
180
tmp = A; A = B; B = tmp;
181
tmp->
neg
= 0;
182
}
183
end:
184
BN_CTX_end
(ctx);
185
if
(err)
186
return
-2;
187
else
188
return
ret;
189
}
190
191
#endif
/* USE_ECDH || USE_ECDSA */
Generated on Thu Jan 10 2013 10:00:43 for cryptlib by
1.8.2