diff options
author | jsing <> | 2014-05-08 13:20:49 +0000 |
---|---|---|
committer | jsing <> | 2014-05-08 13:20:49 +0000 |
commit | 2e8879604fe3abbc2431ca79a4a923f1e87da75e (patch) | |
tree | 18398455223278c0cb2bd44f57e4499a4370f665 /src/lib/libcrypto/bn/bn_kron.c | |
parent | f7d9a959949e5f3918c1cf2b27fb4cd7b62d07d5 (diff) | |
download | openbsd-2e8879604fe3abbc2431ca79a4a923f1e87da75e.tar.gz openbsd-2e8879604fe3abbc2431ca79a4a923f1e87da75e.tar.bz2 openbsd-2e8879604fe3abbc2431ca79a4a923f1e87da75e.zip |
Emergency knfectomie requested by tedu@.
Diffstat (limited to 'src/lib/libcrypto/bn/bn_kron.c')
-rw-r--r-- | src/lib/libcrypto/bn/bn_kron.c | 82 |
1 files changed, 42 insertions, 40 deletions
diff --git a/src/lib/libcrypto/bn/bn_kron.c b/src/lib/libcrypto/bn/bn_kron.c index 740359b752..bcc13b75d4 100644 --- a/src/lib/libcrypto/bn/bn_kron.c +++ b/src/lib/libcrypto/bn/bn_kron.c | |||
@@ -7,7 +7,7 @@ | |||
7 | * are met: | 7 | * are met: |
8 | * | 8 | * |
9 | * 1. Redistributions of source code must retain the above copyright | 9 | * 1. Redistributions of source code must retain the above copyright |
10 | * notice, this list of conditions and the following disclaimer. | 10 | * notice, this list of conditions and the following disclaimer. |
11 | * | 11 | * |
12 | * 2. Redistributions in binary form must reproduce the above copyright | 12 | * 2. Redistributions in binary form must reproduce the above copyright |
13 | * notice, this list of conditions and the following disclaimer in | 13 | * notice, this list of conditions and the following disclaimer in |
@@ -60,12 +60,14 @@ | |||
60 | #define BN_lsw(n) (((n)->top == 0) ? (BN_ULONG) 0 : (n)->d[0]) | 60 | #define BN_lsw(n) (((n)->top == 0) ? (BN_ULONG) 0 : (n)->d[0]) |
61 | 61 | ||
62 | /* Returns -2 for errors because both -1 and 0 are valid results. */ | 62 | /* Returns -2 for errors because both -1 and 0 are valid results. */ |
63 | int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) | 63 | int |
64 | { | 64 | BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) |
65 | { | ||
65 | int i; | 66 | int i; |
66 | int ret = -2; /* avoid 'uninitialized' warning */ | 67 | int ret = -2; /* avoid 'uninitialized' warning */ |
67 | int err = 0; | 68 | int err = 0; |
68 | BIGNUM *A, *B, *tmp; | 69 | BIGNUM *A, *B, *tmp; |
70 | |||
69 | /* In 'tab', only odd-indexed entries are relevant: | 71 | /* In 'tab', only odd-indexed entries are relevant: |
70 | * For any odd BIGNUM n, | 72 | * For any odd BIGNUM n, |
71 | * tab[BN_lsw(n) & 7] | 73 | * tab[BN_lsw(n) & 7] |
@@ -80,12 +82,15 @@ int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) | |||
80 | BN_CTX_start(ctx); | 82 | BN_CTX_start(ctx); |
81 | A = BN_CTX_get(ctx); | 83 | A = BN_CTX_get(ctx); |
82 | B = BN_CTX_get(ctx); | 84 | B = BN_CTX_get(ctx); |
83 | if (B == NULL) goto end; | 85 | if (B == NULL) |
84 | 86 | goto end; | |
87 | |||
85 | err = !BN_copy(A, a); | 88 | err = !BN_copy(A, a); |
86 | if (err) goto end; | 89 | if (err) |
90 | goto end; | ||
87 | err = !BN_copy(B, b); | 91 | err = !BN_copy(B, b); |
88 | if (err) goto end; | 92 | if (err) |
93 | goto end; | ||
89 | 94 | ||
90 | /* | 95 | /* |
91 | * Kronecker symbol, imlemented according to Henri Cohen, | 96 | * Kronecker symbol, imlemented according to Henri Cohen, |
@@ -95,90 +100,87 @@ int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) | |||
95 | 100 | ||
96 | /* Cohen's step 1: */ | 101 | /* Cohen's step 1: */ |
97 | 102 | ||
98 | if (BN_is_zero(B)) | 103 | if (BN_is_zero(B)) { |
99 | { | ||
100 | ret = BN_abs_is_word(A, 1); | 104 | ret = BN_abs_is_word(A, 1); |
101 | goto end; | 105 | goto end; |
102 | } | 106 | } |
103 | 107 | ||
104 | /* Cohen's step 2: */ | 108 | /* Cohen's step 2: */ |
105 | 109 | ||
106 | if (!BN_is_odd(A) && !BN_is_odd(B)) | 110 | if (!BN_is_odd(A) && !BN_is_odd(B)) { |
107 | { | ||
108 | ret = 0; | 111 | ret = 0; |
109 | goto end; | 112 | goto end; |
110 | } | 113 | } |
111 | 114 | ||
112 | /* now B is non-zero */ | 115 | /* now B is non-zero */ |
113 | i = 0; | 116 | i = 0; |
114 | while (!BN_is_bit_set(B, i)) | 117 | while (!BN_is_bit_set(B, i)) |
115 | i++; | 118 | i++; |
116 | err = !BN_rshift(B, B, i); | 119 | err = !BN_rshift(B, B, i); |
117 | if (err) goto end; | 120 | if (err) |
118 | if (i & 1) | 121 | goto end; |
119 | { | 122 | if (i & 1) { |
120 | /* i is odd */ | 123 | /* i is odd */ |
121 | /* (thus B was even, thus A must be odd!) */ | 124 | /* (thus B was even, thus A must be odd!) */ |
122 | 125 | ||
123 | /* set 'ret' to $(-1)^{(A^2-1)/8}$ */ | 126 | /* set 'ret' to $(-1)^{(A^2-1)/8}$ */ |
124 | ret = tab[BN_lsw(A) & 7]; | 127 | ret = tab[BN_lsw(A) & 7]; |
125 | } | 128 | } else { |
126 | else | ||
127 | { | ||
128 | /* i is even */ | 129 | /* i is even */ |
129 | ret = 1; | 130 | ret = 1; |
130 | } | 131 | } |
131 | 132 | ||
132 | if (B->neg) | 133 | if (B->neg) { |
133 | { | ||
134 | B->neg = 0; | 134 | B->neg = 0; |
135 | if (A->neg) | 135 | if (A->neg) |
136 | ret = -ret; | 136 | ret = -ret; |
137 | } | 137 | } |
138 | 138 | ||
139 | /* now B is positive and odd, so what remains to be done is | 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' */ | 140 | * to compute the Jacobi symbol (A/B) and multiply it by 'ret' */ |
141 | 141 | ||
142 | while (1) | 142 | while (1) { |
143 | { | ||
144 | /* Cohen's step 3: */ | 143 | /* Cohen's step 3: */ |
145 | 144 | ||
146 | /* B is positive and odd */ | 145 | /* B is positive and odd */ |
147 | 146 | ||
148 | if (BN_is_zero(A)) | 147 | if (BN_is_zero(A)) { |
149 | { | ||
150 | ret = BN_is_one(B) ? ret : 0; | 148 | ret = BN_is_one(B) ? ret : 0; |
151 | goto end; | 149 | goto end; |
152 | } | 150 | } |
153 | 151 | ||
154 | /* now A is non-zero */ | 152 | /* now A is non-zero */ |
155 | i = 0; | 153 | i = 0; |
156 | while (!BN_is_bit_set(A, i)) | 154 | while (!BN_is_bit_set(A, i)) |
157 | i++; | 155 | i++; |
158 | err = !BN_rshift(A, A, i); | 156 | err = !BN_rshift(A, A, i); |
159 | if (err) goto end; | 157 | if (err) |
160 | if (i & 1) | 158 | goto end; |
161 | { | 159 | if (i & 1) { |
162 | /* i is odd */ | 160 | /* i is odd */ |
163 | /* multiply 'ret' by $(-1)^{(B^2-1)/8}$ */ | 161 | /* multiply 'ret' by $(-1)^{(B^2-1)/8}$ */ |
164 | ret = ret * tab[BN_lsw(B) & 7]; | 162 | ret = ret * tab[BN_lsw(B) & 7]; |
165 | } | 163 | } |
166 | 164 | ||
167 | /* Cohen's step 4: */ | 165 | /* Cohen's step 4: */ |
168 | /* multiply 'ret' by $(-1)^{(A-1)(B-1)/4}$ */ | 166 | /* multiply 'ret' by $(-1)^{(A-1)(B-1)/4}$ */ |
169 | if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2) | 167 | if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2) |
170 | ret = -ret; | 168 | ret = -ret; |
171 | 169 | ||
172 | /* (A, B) := (B mod |A|, |A|) */ | 170 | /* (A, B) := (B mod |A|, |A|) */ |
173 | err = !BN_nnmod(B, B, A, ctx); | 171 | err = !BN_nnmod(B, B, A, ctx); |
174 | if (err) goto end; | 172 | if (err) |
175 | tmp = A; A = B; B = tmp; | 173 | goto end; |
174 | tmp = A; | ||
175 | A = B; | ||
176 | B = tmp; | ||
176 | tmp->neg = 0; | 177 | tmp->neg = 0; |
177 | } | 178 | } |
179 | |||
178 | end: | 180 | end: |
179 | BN_CTX_end(ctx); | 181 | BN_CTX_end(ctx); |
180 | if (err) | 182 | if (err) |
181 | return -2; | 183 | return -2; |
182 | else | 184 | else |
183 | return ret; | 185 | return ret; |
184 | } | 186 | } |