summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_kron.c
diff options
context:
space:
mode:
authorjsing <>2014-05-08 13:20:49 +0000
committerjsing <>2014-05-08 13:20:49 +0000
commit2e8879604fe3abbc2431ca79a4a923f1e87da75e (patch)
tree18398455223278c0cb2bd44f57e4499a4370f665 /src/lib/libcrypto/bn/bn_kron.c
parentf7d9a959949e5f3918c1cf2b27fb4cd7b62d07d5 (diff)
downloadopenbsd-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.c82
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. */
63int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 63int
64 { 64BN_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
178end: 180end:
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}