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_sqrt.c
Go to the documentation of this file.
1
/* crypto/bn/bn_sqrt.c */
2
/* Written by Lenka Fibikova <
[email protected]
>
3
* and Bodo Moeller for the OpenSSL project. */
4
/* ====================================================================
5
* Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved.
6
*
7
* Redistribution and use in source and binary forms, with or without
8
* modification, are permitted provided that the following conditions
9
* are met:
10
*
11
* 1. Redistributions of source code must retain the above copyright
12
* notice, this list of conditions and the following disclaimer.
13
*
14
* 2. Redistributions in binary form must reproduce the above copyright
15
* notice, this list of conditions and the following disclaimer in
16
* the documentation and/or other materials provided with the
17
* distribution.
18
*
19
* 3. All advertising materials mentioning features or use of this
20
* software must display the following acknowledgment:
21
* "This product includes software developed by the OpenSSL Project
22
* for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
23
*
24
* 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
25
* endorse or promote products derived from this software without
26
* prior written permission. For written permission, please contact
27
*
[email protected]
.
28
*
29
* 5. Products derived from this software may not be called "OpenSSL"
30
* nor may "OpenSSL" appear in their names without prior written
31
* permission of the OpenSSL Project.
32
*
33
* 6. Redistributions of any form whatsoever must retain the following
34
* acknowledgment:
35
* "This product includes software developed by the OpenSSL Project
36
* for use in the OpenSSL Toolkit (http://www.openssl.org/)"
37
*
38
* THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
39
* EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
40
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
41
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
42
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
43
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
44
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
45
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
46
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
47
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
48
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
49
* OF THE POSSIBILITY OF SUCH DAMAGE.
50
* ====================================================================
51
*
52
* This product includes cryptographic software written by Eric Young
53
* (
[email protected]
). This product includes software written by Tim
54
* Hudson (
[email protected]
).
55
*
56
*/
57
58
#if defined( INC_ALL )
59
#include "
ec_lcl.h
"
60
#else
61
#include "
bn/ec_lcl.h
"
62
#endif
/* Compiler-specific includes */
63
64
#if defined( USE_ECDH ) || defined( USE_ECDSA )
65
66
BIGNUM
*
BN_mod_sqrt
(
BIGNUM
*in,
const
BIGNUM
*a,
const
BIGNUM
*
p
,
BN_CTX
*ctx)
67
/* Returns 'ret' such that
68
* ret^2 == a (mod p),
69
* using the Tonelli/Shanks algorithm (cf. Henri Cohen, "A Course
70
* in Algebraic Computational Number Theory", algorithm 1.5.1).
71
* 'p' must be prime!
72
*/
73
{
74
BIGNUM
*ret = in;
75
int
err = 1;
76
int
r;
77
BIGNUM
*A, *b, *q, *t, *x, *y;
78
int
e, i, j;
79
80
if
(!
BN_is_odd
(p) ||
BN_abs_is_word
(p, 1))
81
{
82
if
(
BN_abs_is_word
(p, 2))
83
{
84
if
(ret == NULL)
85
ret =
BN_new
();
86
if
(ret == NULL)
87
goto
end;
88
if
(!
BN_set_word
(ret,
BN_is_bit_set
(a, 0)))
89
{
90
if
(ret != in)
91
BN_free
(ret);
92
return
NULL;
93
}
94
bn_check_top
(ret);
95
return
ret;
96
}
97
98
BNerr
(
BN_F_BN_MOD_SQRT
,
BN_R_P_IS_NOT_PRIME
);
99
return
(NULL);
100
}
101
102
if
(
BN_is_zero
(a) ||
BN_is_one
(a))
103
{
104
if
(ret == NULL)
105
ret =
BN_new
();
106
if
(ret == NULL)
107
goto
end;
108
if
(!
BN_set_word
(ret,
BN_is_one
(a)))
109
{
110
if
(ret != in)
111
BN_free
(ret);
112
return
NULL;
113
}
114
bn_check_top
(ret);
115
return
ret;
116
}
117
118
BN_CTX_start
(ctx);
119
A =
BN_CTX_get
(ctx);
120
b =
BN_CTX_get
(ctx);
121
q =
BN_CTX_get
(ctx);
122
t =
BN_CTX_get
(ctx);
123
x =
BN_CTX_get
(ctx);
124
y =
BN_CTX_get
(ctx);
125
if
(y == NULL)
goto
end;
126
127
if
(ret == NULL)
128
ret =
BN_new
();
129
if
(ret == NULL)
goto
end;
130
131
/* A = a mod p */
132
if
(!
BN_nnmod
(A, a, p, ctx))
goto
end;
133
134
/* now write |p| - 1 as 2^e*q where q is odd */
135
e = 1;
136
while
(!
BN_is_bit_set
(p, e))
137
e++;
138
/* we'll set q later (if needed) */
139
140
if
(e == 1)
141
{
142
/* The easy case: (|p|-1)/2 is odd, so 2 has an inverse
143
* modulo (|p|-1)/2, and square roots can be computed
144
* directly by modular exponentiation.
145
* We have
146
* 2 * (|p|+1)/4 == 1 (mod (|p|-1)/2),
147
* so we can use exponent (|p|+1)/4, i.e. (|p|-3)/4 + 1.
148
*/
149
if
(!
BN_rshift
(q, p, 2))
goto
end;
150
q->
neg
= 0;
151
if
(!
BN_add_word
(q, 1))
goto
end;
152
if
(!
BN_mod_exp
(ret, A, q, p, ctx))
goto
end;
153
err = 0;
154
goto
vrfy;
155
}
156
157
if
(e == 2)
158
{
159
/* |p| == 5 (mod 8)
160
*
161
* In this case 2 is always a non-square since
162
* Legendre(2,p) = (-1)^((p^2-1)/8) for any odd prime.
163
* So if a really is a square, then 2*a is a non-square.
164
* Thus for
165
* b := (2*a)^((|p|-5)/8),
166
* i := (2*a)*b^2
167
* we have
168
* i^2 = (2*a)^((1 + (|p|-5)/4)*2)
169
* = (2*a)^((p-1)/2)
170
* = -1;
171
* so if we set
172
* x := a*b*(i-1),
173
* then
174
* x^2 = a^2 * b^2 * (i^2 - 2*i + 1)
175
* = a^2 * b^2 * (-2*i)
176
* = a*(-i)*(2*a*b^2)
177
* = a*(-i)*i
178
* = a.
179
*
180
* (This is due to A.O.L. Atkin,
181
* <URL: http://listserv.nodak.edu/scripts/wa.exe?A2=ind9211&L=nmbrthry&O=T&P=562>,
182
* November 1992.)
183
*/
184
185
/* t := 2*a */
186
if
(!
BN_mod_lshift1_quick
(t, A, p))
goto
end;
187
188
/* b := (2*a)^((|p|-5)/8) */
189
if
(!
BN_rshift
(q, p, 3))
goto
end;
190
q->
neg
= 0;
191
if
(!
BN_mod_exp
(b, t, q, p, ctx))
goto
end;
192
193
/* y := b^2 */
194
if
(!
BN_mod_sqr
(y, b, p, ctx))
goto
end;
195
196
/* t := (2*a)*b^2 - 1*/
197
if
(!
BN_mod_mul
(t, t, y, p, ctx))
goto
end;
198
if
(!
BN_sub_word
(t, 1))
goto
end;
199
200
/* x = a*b*t */
201
if
(!
BN_mod_mul
(x, A, b, p, ctx))
goto
end;
202
if
(!
BN_mod_mul
(x, x, t, p, ctx))
goto
end;
203
204
if
(!
BN_copy
(ret, x))
goto
end;
205
err = 0;
206
goto
vrfy;
207
}
208
209
/* e > 2, so we really have to use the Tonelli/Shanks algorithm.
210
* First, find some y that is not a square. */
211
if
(!
BN_copy
(q, p))
goto
end;
/* use 'q' as temp */
212
q->
neg
= 0;
213
i = 2;
214
do
215
{
216
/* For efficiency, try small numbers first;
217
* if this fails, try random numbers.
218
*/
219
if
(i < 22)
220
{
221
if
(!
BN_set_word
(y, i))
goto
end;
222
}
223
else
224
{
225
if
(!
BN_pseudo_rand
(y,
BN_num_bits
(p), 0, 0))
goto
end;
226
if
(
BN_ucmp
(y, p) >= 0)
227
{
228
if
(!(p->
neg
?
BN_add
:
BN_sub
)(y, y, p))
goto
end;
229
}
230
/* now 0 <= y < |p| */
231
if
(
BN_is_zero
(y))
232
if
(!
BN_set_word
(y, i))
goto
end;
233
}
234
235
r =
BN_kronecker
(y, q, ctx);
/* here 'q' is |p| */
236
if
(r < -1)
goto
end;
237
if
(r == 0)
238
{
239
/* m divides p */
240
BNerr
(
BN_F_BN_MOD_SQRT
,
BN_R_P_IS_NOT_PRIME
);
241
goto
end;
242
}
243
}
244
while
(r == 1 && ++i < 82);
245
246
if
(r != -1)
247
{
248
/* Many rounds and still no non-square -- this is more likely
249
* a bug than just bad luck.
250
* Even if p is not prime, we should have found some y
251
* such that r == -1.
252
*/
253
BNerr
(
BN_F_BN_MOD_SQRT
,
BN_R_TOO_MANY_ITERATIONS
);
254
goto
end;
255
}
256
257
/* Here's our actual 'q': */
258
if
(!
BN_rshift
(q, q, e))
goto
end;
259
260
/* Now that we have some non-square, we can find an element
261
* of order 2^e by computing its q'th power. */
262
if
(!
BN_mod_exp
(y, y, q, p, ctx))
goto
end;
263
if
(
BN_is_one
(y))
264
{
265
BNerr
(
BN_F_BN_MOD_SQRT
,
BN_R_P_IS_NOT_PRIME
);
266
goto
end;
267
}
268
269
/* Now we know that (if p is indeed prime) there is an integer
270
* k, 0 <= k < 2^e, such that
271
*
272
* a^q * y^k == 1 (mod p).
273
*
274
* As a^q is a square and y is not, k must be even.
275
* q+1 is even, too, so there is an element
276
*
277
* X := a^((q+1)/2) * y^(k/2),
278
*
279
* and it satisfies
280
*
281
* X^2 = a^q * a * y^k
282
* = a,
283
*
284
* so it is the square root that we are looking for.
285
*/
286
287
/* t := (q-1)/2 (note that q is odd) */
288
if
(!
BN_rshift1
(t, q))
goto
end;
289
290
/* x := a^((q-1)/2) */
291
if
(
BN_is_zero
(t))
/* special case: p = 2^e + 1 */
292
{
293
if
(!
BN_nnmod
(t, A, p, ctx))
goto
end;
294
if
(
BN_is_zero
(t))
295
{
296
/* special case: a == 0 (mod p) */
297
BN_zero
(ret);
298
err = 0;
299
goto
end;
300
}
301
else
302
if
(!
BN_one
(x))
goto
end;
303
}
304
else
305
{
306
if
(!
BN_mod_exp
(x, A, t, p, ctx))
goto
end;
307
if
(
BN_is_zero
(x))
308
{
309
/* special case: a == 0 (mod p) */
310
BN_zero
(ret);
311
err = 0;
312
goto
end;
313
}
314
}
315
316
/* b := a*x^2 (= a^q) */
317
if
(!
BN_mod_sqr
(b, x, p, ctx))
goto
end;
318
if
(!
BN_mod_mul
(b, b, A, p, ctx))
goto
end;
319
320
/* x := a*x (= a^((q+1)/2)) */
321
if
(!
BN_mod_mul
(x, x, A, p, ctx))
goto
end;
322
323
while
(1)
324
{
325
/* Now b is a^q * y^k for some even k (0 <= k < 2^E
326
* where E refers to the original value of e, which we
327
* don't keep in a variable), and x is a^((q+1)/2) * y^(k/2).
328
*
329
* We have a*b = x^2,
330
* y^2^(e-1) = -1,
331
* b^2^(e-1) = 1.
332
*/
333
334
if
(
BN_is_one
(b))
335
{
336
if
(!
BN_copy
(ret, x))
goto
end;
337
err = 0;
338
goto
vrfy;
339
}
340
341
342
/* find smallest i such that b^(2^i) = 1 */
343
i = 1;
344
if
(!
BN_mod_sqr
(t, b, p, ctx))
goto
end;
345
while
(!
BN_is_one
(t))
346
{
347
i++;
348
if
(i == e)
349
{
350
BNerr
(
BN_F_BN_MOD_SQRT
,
BN_R_NOT_A_SQUARE
);
351
goto
end;
352
}
353
if
(!
BN_mod_mul
(t, t, t, p, ctx))
goto
end;
354
}
355
356
357
/* t := y^2^(e - i - 1) */
358
if
(!
BN_copy
(t, y))
goto
end;
359
for
(j = e - i - 1; j > 0; j--)
360
{
361
if
(!
BN_mod_sqr
(t, t, p, ctx))
goto
end;
362
}
363
if
(!
BN_mod_mul
(y, t, t, p, ctx))
goto
end;
364
if
(!
BN_mod_mul
(x, x, t, p, ctx))
goto
end;
365
if
(!
BN_mod_mul
(b, b, y, p, ctx))
goto
end;
366
e = i;
367
}
368
369
vrfy:
370
if
(!err)
371
{
372
/* verify the result -- the input might have been not a square
373
* (test added in 0.9.8) */
374
375
if
(!
BN_mod_sqr
(x, ret, p, ctx))
376
err = 1;
377
378
if
(!err && 0 !=
BN_cmp
(x, A))
379
{
380
BNerr
(
BN_F_BN_MOD_SQRT
,
BN_R_NOT_A_SQUARE
);
381
err = 1;
382
}
383
}
384
385
end:
386
if
(err)
387
{
388
if
(ret != NULL && ret != in)
389
{
390
BN_clear_free
(ret);
391
}
392
ret = NULL;
393
}
394
BN_CTX_end
(ctx);
395
bn_check_top
(ret);
396
return
ret;
397
}
398
399
#endif
/* USE_ECDH || USE_ECDSA */
Generated on Thu Jan 10 2013 10:00:43 for cryptlib by
1.8.2