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
bn_gcd.c
Go to the documentation of this file.
1
/* crypto/bn/bn_gcd.c */
2
/* Copyright (C) 1995-1998 Eric Young (
[email protected]
)
3
* All rights reserved.
4
*
5
* This package is an SSL implementation written
6
* by Eric Young (
[email protected]
).
7
* The implementation was written so as to conform with Netscapes SSL.
8
*
9
* This library is free for commercial and non-commercial use as long as
10
* the following conditions are aheared to. The following conditions
11
* apply to all code found in this distribution, be it the RC4, RSA,
12
* lhash, DES, etc., code; not just the SSL code. The SSL documentation
13
* included with this distribution is covered by the same copyright terms
14
* except that the holder is Tim Hudson (
[email protected]
).
15
*
16
* Copyright remains Eric Young's, and as such any Copyright notices in
17
* the code are not to be removed.
18
* If this package is used in a product, Eric Young should be given attribution
19
* as the author of the parts of the library used.
20
* This can be in the form of a textual message at program startup or
21
* in documentation (online or textual) provided with the package.
22
*
23
* Redistribution and use in source and binary forms, with or without
24
* modification, are permitted provided that the following conditions
25
* are met:
26
* 1. Redistributions of source code must retain the copyright
27
* notice, this list of conditions and the following disclaimer.
28
* 2. Redistributions in binary form must reproduce the above copyright
29
* notice, this list of conditions and the following disclaimer in the
30
* documentation and/or other materials provided with the distribution.
31
* 3. All advertising materials mentioning features or use of this software
32
* must display the following acknowledgement:
33
* "This product includes cryptographic software written by
34
* Eric Young (
[email protected]
)"
35
* The word 'cryptographic' can be left out if the rouines from the library
36
* being used are not cryptographic related :-).
37
* 4. If you include any Windows specific code (or a derivative thereof) from
38
* the apps directory (application code) you must include an acknowledgement:
39
* "This product includes software written by Tim Hudson (
[email protected]
)"
40
*
41
* THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51
* SUCH DAMAGE.
52
*
53
* The licence and distribution terms for any publically available version or
54
* derivative of this code cannot be changed. i.e. this code cannot simply be
55
* copied and put under another distribution licence
56
* [including the GNU Public Licence.]
57
*/
58
/* ====================================================================
59
* Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved.
60
*
61
* Redistribution and use in source and binary forms, with or without
62
* modification, are permitted provided that the following conditions
63
* are met:
64
*
65
* 1. Redistributions of source code must retain the above copyright
66
* notice, this list of conditions and the following disclaimer.
67
*
68
* 2. Redistributions in binary form must reproduce the above copyright
69
* notice, this list of conditions and the following disclaimer in
70
* the documentation and/or other materials provided with the
71
* distribution.
72
*
73
* 3. All advertising materials mentioning features or use of this
74
* software must display the following acknowledgment:
75
* "This product includes software developed by the OpenSSL Project
76
* for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
77
*
78
* 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
79
* endorse or promote products derived from this software without
80
* prior written permission. For written permission, please contact
81
*
[email protected]
.
82
*
83
* 5. Products derived from this software may not be called "OpenSSL"
84
* nor may "OpenSSL" appear in their names without prior written
85
* permission of the OpenSSL Project.
86
*
87
* 6. Redistributions of any form whatsoever must retain the following
88
* acknowledgment:
89
* "This product includes software developed by the OpenSSL Project
90
* for use in the OpenSSL Toolkit (http://www.openssl.org/)"
91
*
92
* THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
93
* EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
94
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
95
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
96
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
97
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
98
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
99
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
100
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
101
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
102
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
103
* OF THE POSSIBILITY OF SUCH DAMAGE.
104
* ====================================================================
105
*
106
* This product includes cryptographic software written by Eric Young
107
* (
[email protected]
). This product includes software written by Tim
108
* Hudson (
[email protected]
).
109
*
110
*/
111
112
#if defined( INC_ALL )
113
#include "
bn_lcl.h
"
114
#else
115
#include "
bn/bn_lcl.h
"
116
#endif
/* Compiler-specific includes */
117
118
static
BIGNUM
*euclid(
BIGNUM
*a,
BIGNUM
*b);
119
120
int
BN_gcd
(
BIGNUM
*r,
const
BIGNUM
*in_a,
const
BIGNUM
*in_b,
BN_CTX
*ctx)
121
{
122
BIGNUM
*a,*b,*t;
123
int
ret=0;
124
125
bn_check_top
(in_a);
126
bn_check_top
(in_b);
127
128
BN_CTX_start
(ctx);
129
a =
BN_CTX_get
(ctx);
130
b =
BN_CTX_get
(ctx);
131
if
(a == NULL || b == NULL)
goto
err;
132
133
if
(
BN_copy
(a,in_a) == NULL)
goto
err;
134
if
(
BN_copy
(b,in_b) == NULL)
goto
err;
135
a->
neg
= 0;
136
b->
neg
= 0;
137
138
if
(
BN_cmp
(a,b) < 0) { t=a; a=b; b=t; }
139
t=euclid(a,b);
140
if
(t == NULL)
goto
err;
141
142
if
(
BN_copy
(r,t) == NULL)
goto
err;
143
ret=1;
144
err:
145
BN_CTX_end
(ctx);
146
bn_check_top
(r);
147
return
(ret);
148
}
149
150
static
BIGNUM
*euclid(
BIGNUM
*a,
BIGNUM
*b)
151
{
152
BIGNUM
*t;
153
int
shifts=0;
154
155
bn_check_top
(a);
156
bn_check_top
(b);
157
158
/* 0 <= b <= a */
159
while
(!
BN_is_zero
(b))
160
{
161
/* 0 < b <= a */
162
163
if
(
BN_is_odd
(a))
164
{
165
if
(
BN_is_odd
(b))
166
{
167
if
(!
BN_sub
(a,a,b))
goto
err;
168
if
(!
BN_rshift1
(a,a))
goto
err;
169
if
(
BN_cmp
(a,b) < 0)
170
{ t=a; a=b; b=t; }
171
}
172
else
/* a odd - b even */
173
{
174
if
(!
BN_rshift1
(b,b))
goto
err;
175
if
(
BN_cmp
(a,b) < 0)
176
{ t=a; a=b; b=t; }
177
}
178
}
179
else
/* a is even */
180
{
181
if
(
BN_is_odd
(b))
182
{
183
if
(!
BN_rshift1
(a,a))
goto
err;
184
if
(
BN_cmp
(a,b) < 0)
185
{ t=a; a=b; b=t; }
186
}
187
else
/* a even - b even */
188
{
189
if
(!
BN_rshift1
(a,a))
goto
err;
190
if
(!
BN_rshift1
(b,b))
goto
err;
191
shifts++;
192
}
193
}
194
/* 0 <= b <= a */
195
}
196
197
if
(shifts)
198
{
199
if
(!
BN_lshift
(a,a,shifts))
goto
err;
200
}
201
bn_check_top
(a);
202
return
(a);
203
err:
204
return
(NULL);
205
}
206
207
208
/* solves ax == 1 (mod n) */
209
BIGNUM
*
BN_mod_inverse
(
BIGNUM
*in,
210
const
BIGNUM
*a,
const
BIGNUM
*
n
,
BN_CTX
*ctx)
211
{
212
BIGNUM
*A,*B,*
X
,*Y,*M,*D,*T,*R=NULL;
213
BIGNUM
*ret=NULL;
214
int
sign;
215
216
bn_check_top
(a);
217
bn_check_top
(n);
218
219
BN_CTX_start
(ctx);
220
A =
BN_CTX_get
(ctx);
221
B =
BN_CTX_get
(ctx);
222
X =
BN_CTX_get
(ctx);
223
D =
BN_CTX_get
(ctx);
224
M =
BN_CTX_get
(ctx);
225
Y =
BN_CTX_get
(ctx);
226
T =
BN_CTX_get
(ctx);
227
if
(T == NULL)
goto
err;
228
229
if
(in == NULL)
230
R=
BN_new
();
231
else
232
R=in;
233
if
(R == NULL)
goto
err;
234
235
BN_one
(X);
236
BN_zero
(Y);
237
if
(
BN_copy
(B,a) == NULL)
goto
err;
238
if
(
BN_copy
(A,n) == NULL)
goto
err;
239
A->
neg
= 0;
240
if
(B->
neg
|| (
BN_ucmp
(B, A) >= 0))
241
{
242
if
(!
BN_nnmod
(B, B, A, ctx))
goto
err;
243
}
244
sign = -1;
245
/* From B = a mod |n|, A = |n| it follows that
246
*
247
* 0 <= B < A,
248
* -sign*X*a == B (mod |n|),
249
* sign*Y*a == A (mod |n|).
250
*/
251
252
if
(
BN_is_odd
(n) && (
BN_num_bits
(n) <= (
BN_BITS
<= 32 ? 450 : 2048)))
253
{
254
/* Binary inversion algorithm; requires odd modulus.
255
* This is faster than the general algorithm if the modulus
256
* is sufficiently small (about 400 .. 500 bits on 32-bit
257
* sytems, but much more on 64-bit systems) */
258
int
shift;
259
260
while
(!
BN_is_zero
(B))
261
{
262
/*
263
* 0 < B < |n|,
264
* 0 < A <= |n|,
265
* (1) -sign*X*a == B (mod |n|),
266
* (2) sign*Y*a == A (mod |n|)
267
*/
268
269
/* Now divide B by the maximum possible power of two in the integers,
270
* and divide X by the same value mod |n|.
271
* When we're done, (1) still holds. */
272
shift = 0;
273
while
(!
BN_is_bit_set
(B, shift))
/* note that 0 < B */
274
{
275
shift++;
276
277
if
(
BN_is_odd
(X))
278
{
279
if
(!
BN_uadd
(X, X, n))
goto
err;
280
}
281
/* now X is even, so we can easily divide it by two */
282
if
(!
BN_rshift1
(X, X))
goto
err;
283
}
284
if
(shift > 0)
285
{
286
if
(!
BN_rshift
(B, B, shift))
goto
err;
287
}
288
289
290
/* Same for A and Y. Afterwards, (2) still holds. */
291
shift = 0;
292
while
(!
BN_is_bit_set
(A, shift))
/* note that 0 < A */
293
{
294
shift++;
295
296
if
(
BN_is_odd
(Y))
297
{
298
if
(!
BN_uadd
(Y, Y, n))
goto
err;
299
}
300
/* now Y is even */
301
if
(!
BN_rshift1
(Y, Y))
goto
err;
302
}
303
if
(shift > 0)
304
{
305
if
(!
BN_rshift
(A, A, shift))
goto
err;
306
}
307
308
309
/* We still have (1) and (2).
310
* Both A and B are odd.
311
* The following computations ensure that
312
*
313
* 0 <= B < |n|,
314
* 0 < A < |n|,
315
* (1) -sign*X*a == B (mod |n|),
316
* (2) sign*Y*a == A (mod |n|),
317
*
318
* and that either A or B is even in the next iteration.
319
*/
320
if
(
BN_ucmp
(B, A) >= 0)
321
{
322
/* -sign*(X + Y)*a == B - A (mod |n|) */
323
if
(!
BN_uadd
(X, X, Y))
goto
err;
324
/* NB: we could use BN_mod_add_quick(X, X, Y, n), but that
325
* actually makes the algorithm slower */
326
if
(!
BN_usub
(B, B, A))
goto
err;
327
}
328
else
329
{
330
/* sign*(X + Y)*a == A - B (mod |n|) */
331
if
(!
BN_uadd
(Y, Y, X))
goto
err;
332
/* as above, BN_mod_add_quick(Y, Y, X, n) would slow things down */
333
if
(!
BN_usub
(A, A, B))
goto
err;
334
}
335
}
336
}
337
else
338
{
339
/* general inversion algorithm */
340
341
while
(!
BN_is_zero
(B))
342
{
343
BIGNUM
*tmp;
344
345
/*
346
* 0 < B < A,
347
* (*) -sign*X*a == B (mod |n|),
348
* sign*Y*a == A (mod |n|)
349
*/
350
351
/* (D, M) := (A/B, A%B) ... */
352
if
(
BN_num_bits
(A) ==
BN_num_bits
(B))
353
{
354
if
(!
BN_one
(D))
goto
err;
355
if
(!
BN_sub
(M,A,B))
goto
err;
356
}
357
else
if
(
BN_num_bits
(A) ==
BN_num_bits
(B) + 1)
358
{
359
/* A/B is 1, 2, or 3 */
360
if
(!
BN_lshift1
(T,B))
goto
err;
361
if
(
BN_ucmp
(A,T) < 0)
362
{
363
/* A < 2*B, so D=1 */
364
if
(!
BN_one
(D))
goto
err;
365
if
(!
BN_sub
(M,A,B))
goto
err;
366
}
367
else
368
{
369
/* A >= 2*B, so D=2 or D=3 */
370
if
(!
BN_sub
(M,A,T))
goto
err;
371
if
(!
BN_add
(D,T,B))
goto
err;
/* use D (:= 3*B) as temp */
372
if
(
BN_ucmp
(A,D) < 0)
373
{
374
/* A < 3*B, so D=2 */
375
if
(!
BN_set_word
(D,2))
goto
err;
376
/* M (= A - 2*B) already has the correct value */
377
}
378
else
379
{
380
/* only D=3 remains */
381
if
(!
BN_set_word
(D,3))
goto
err;
382
/* currently M = A - 2*B, but we need M = A - 3*B */
383
if
(!
BN_sub
(M,M,B))
goto
err;
384
}
385
}
386
}
387
else
388
{
389
if
(!
BN_div
(D,M,A,B,ctx))
goto
err;
390
}
391
392
/* Now
393
* A = D*B + M;
394
* thus we have
395
* (**) sign*Y*a == D*B + M (mod |n|).
396
*/
397
398
tmp=A;
/* keep the BIGNUM object, the value does not matter */
399
400
/* (A, B) := (B, A mod B) ... */
401
A=B;
402
B=M;
403
/* ... so we have 0 <= B < A again */
404
405
/* Since the former M is now B and the former B is now A,
406
* (**) translates into
407
* sign*Y*a == D*A + B (mod |n|),
408
* i.e.
409
* sign*Y*a - D*A == B (mod |n|).
410
* Similarly, (*) translates into
411
* -sign*X*a == A (mod |n|).
412
*
413
* Thus,
414
* sign*Y*a + D*sign*X*a == B (mod |n|),
415
* i.e.
416
* sign*(Y + D*X)*a == B (mod |n|).
417
*
418
* So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at
419
* -sign*X*a == B (mod |n|),
420
* sign*Y*a == A (mod |n|).
421
* Note that X and Y stay non-negative all the time.
422
*/
423
424
/* most of the time D is very small, so we can optimize tmp := D*X+Y */
425
if
(
BN_is_one
(D))
426
{
427
if
(!
BN_add
(tmp,X,Y))
goto
err;
428
}
429
else
430
{
431
if
(
BN_is_word
(D,2))
432
{
433
if
(!
BN_lshift1
(tmp,X))
goto
err;
434
}
435
else
if
(
BN_is_word
(D,4))
436
{
437
if
(!
BN_lshift
(tmp,X,2))
goto
err;
438
}
439
else
if
(D->
top
== 1)
440
{
441
if
(!
BN_copy
(tmp,X))
goto
err;
442
if
(!
BN_mul_word
(tmp,D->
d
[0]))
goto
err;
443
}
444
else
445
{
446
if
(!
BN_mul
(tmp,D,X,ctx))
goto
err;
447
}
448
if
(!
BN_add
(tmp,tmp,Y))
goto
err;
449
}
450
451
M=Y;
/* keep the BIGNUM object, the value does not matter */
452
Y=X;
453
X=tmp;
454
sign = -sign;
455
}
456
}
457
458
/*
459
* The while loop (Euclid's algorithm) ends when
460
* A == gcd(a,n);
461
* we have
462
* sign*Y*a == A (mod |n|),
463
* where Y is non-negative.
464
*/
465
466
if
(sign < 0)
467
{
468
if
(!
BN_sub
(Y,n,Y))
goto
err;
469
}
470
/* Now Y*a == A (mod |n|). */
471
472
473
if
(
BN_is_one
(A))
474
{
475
/* Y*a == 1 (mod |n|) */
476
if
(!Y->
neg
&&
BN_ucmp
(Y,n) < 0)
477
{
478
if
(!
BN_copy
(R,Y))
goto
err;
479
}
480
else
481
{
482
if
(!
BN_nnmod
(R,Y,n,ctx))
goto
err;
483
}
484
}
485
else
486
{
487
BNerr
(
BN_F_BN_MOD_INVERSE
,
BN_R_NO_INVERSE
);
488
goto
err;
489
}
490
ret=R;
491
err:
492
if
((ret == NULL) && (in == NULL))
BN_free
(R);
493
BN_CTX_end
(ctx);
494
if
(ret)
495
bn_check_top
(ret);
496
return
(ret);
497
}
Generated on Thu Jan 10 2013 10:00:43 for cryptlib by
1.8.2