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_sqr.c
Go to the documentation of this file.
1
/* crypto/bn/bn_sqr.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
#include <stdio.h>
60
#if defined( INC_ALL )
61
#include "
bn_lcl.h
"
62
#else
63
#include "
bn/bn_lcl.h
"
64
#endif
/* Compiler-specific includes */
65
66
/* r must not be a */
67
/* I've just gone over this and it is now %20 faster on x86 - eay - 27 Jun 96 */
68
int
BN_sqr
(
BIGNUM
*r,
const
BIGNUM
*a,
BN_CTX
*ctx)
69
{
70
int
max
,al;
71
int
ret = 0;
72
BIGNUM
*tmp,*rr;
73
74
#ifdef BN_COUNT
75
fprintf(stderr,
"BN_sqr %d * %d\n"
,a->
top
,a->
top
);
76
#endif
77
bn_check_top
(a);
78
79
al=a->
top
;
80
if
(al <= 0)
81
{
82
r->
top
=0;
83
return
1;
84
}
85
86
BN_CTX_start
(ctx);
87
rr=(a != r) ? r :
BN_CTX_get
(ctx);
88
tmp=
BN_CTX_get
(ctx);
89
if
(!rr || !tmp)
goto
err;
90
91
max = 2 * al;
/* Non-zero (from above) */
92
if
(
bn_wexpand
(rr,max) == NULL)
goto
err;
93
94
if
(al == 4)
95
{
96
#ifndef BN_SQR_COMBA
97
BN_ULONG
t[8];
98
bn_sqr_normal
(rr->
d
,a->
d
,4,t);
99
#else
100
bn_sqr_comba4
(rr->
d
,a->
d
);
101
#endif
102
}
103
else
if
(al == 8)
104
{
105
#ifndef BN_SQR_COMBA
106
BN_ULONG
t[16];
107
bn_sqr_normal
(rr->
d
,a->
d
,8,t);
108
#else
109
bn_sqr_comba8
(rr->
d
,a->
d
);
110
#endif
111
}
112
else
113
{
114
#if defined(BN_RECURSION)
115
if
(al <
BN_SQR_RECURSIVE_SIZE_NORMAL
)
116
{
117
BN_ULONG
t[
BN_SQR_RECURSIVE_SIZE_NORMAL
*2];
118
bn_sqr_normal
(rr->
d
,a->
d
,al,t);
119
}
120
else
121
{
122
int
j,k;
123
124
j=
BN_num_bits_word
((
BN_ULONG
)al);
125
j=1<<(j-1);
126
k=j+j;
127
if
(al == j)
128
{
129
if
(
bn_wexpand
(tmp,k*2) == NULL)
goto
err;
130
bn_sqr_recursive
(rr->
d
,a->
d
,al,tmp->
d
);
131
}
132
else
133
{
134
if
(
bn_wexpand
(tmp,max) == NULL)
goto
err;
135
bn_sqr_normal
(rr->
d
,a->
d
,al,tmp->
d
);
136
}
137
}
138
#else
139
if
(
bn_wexpand
(tmp,max) == NULL)
goto
err;
140
bn_sqr_normal
(rr->
d
,a->
d
,al,tmp->
d
);
141
#endif
142
}
143
144
rr->
neg
=0;
145
/* If the most-significant half of the top word of 'a' is zero, then
146
* the square of 'a' will max-1 words. */
147
if
(a->
d
[al - 1] == (a->
d
[al - 1] &
BN_MASK2l
))
148
rr->
top
= max - 1;
149
else
150
rr->
top
=
max
;
151
if
(rr != r)
BN_copy
(r,rr);
152
ret = 1;
153
err:
154
if
(rr)
bn_check_top
(rr);
155
if
(tmp)
bn_check_top
(tmp);
156
BN_CTX_end
(ctx);
157
return
(ret);
158
}
159
160
/* tmp must have 2*n words */
161
void
bn_sqr_normal
(
BN_ULONG
*r,
const
BN_ULONG
*a,
int
n
,
BN_ULONG
*tmp)
162
{
163
int
i,j,
max
;
164
const
BN_ULONG
*ap;
165
BN_ULONG
*rp;
166
167
max=n*2;
168
ap=a;
169
rp=r;
170
rp[0]=rp[max-1]=0;
171
rp++;
172
j=
n
;
173
174
if
(--j > 0)
175
{
176
ap++;
177
rp[j]=
bn_mul_words
(rp,ap,j,ap[-1]);
178
rp+=2;
179
}
180
181
for
(i=n-2; i>0; i--)
182
{
183
j--;
184
ap++;
185
rp[j]=
bn_mul_add_words
(rp,ap,j,ap[-1]);
186
rp+=2;
187
}
188
189
bn_add_words
(r,r,r,max);
190
191
/* There will not be a carry */
192
193
bn_sqr_words
(tmp,a,n);
194
195
bn_add_words
(r,r,tmp,max);
196
}
197
198
#ifdef BN_RECURSION
199
/* r is 2*n words in size,
200
* a and b are both n words in size. (There's not actually a 'b' here ...)
201
* n must be a power of 2.
202
* We multiply and return the result.
203
* t must be 2*n words in size
204
* We calculate
205
* a[0]*b[0]
206
* a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
207
* a[1]*b[1]
208
*/
209
void
bn_sqr_recursive
(
BN_ULONG
*r,
const
BN_ULONG
*a,
int
n2,
BN_ULONG
*t)
210
{
211
int
n
=n2/2;
212
int
zero,c1;
213
BN_ULONG
ln,lo,*
p
;
214
215
#ifdef BN_COUNT
216
fprintf(stderr,
" bn_sqr_recursive %d * %d\n"
,n2,n2);
217
#endif
218
if
(n2 == 4)
219
{
220
#ifndef BN_SQR_COMBA
221
bn_sqr_normal
(r,a,4,t);
222
#else
223
bn_sqr_comba4
(r,a);
224
#endif
225
return
;
226
}
227
else
if
(n2 == 8)
228
{
229
#ifndef BN_SQR_COMBA
230
bn_sqr_normal
(r,a,8,t);
231
#else
232
bn_sqr_comba8
(r,a);
233
#endif
234
return
;
235
}
236
if
(n2 <
BN_SQR_RECURSIVE_SIZE_NORMAL
)
237
{
238
bn_sqr_normal
(r,a,n2,t);
239
return
;
240
}
241
/* r=(a[0]-a[1])*(a[1]-a[0]) */
242
c1=
bn_cmp_words
(a,&(a[n]),n);
243
zero=0;
244
if
(c1 > 0)
245
bn_sub_words
(t,a,&(a[n]),n);
246
else
if
(c1 < 0)
247
bn_sub_words
(t,&(a[n]),a,n);
248
else
249
zero=1;
250
251
/* The result will always be negative unless it is zero */
252
p= &(t[n2*2]);
253
254
if
(!zero)
255
bn_sqr_recursive
(&(t[n2]),t,n,p);
256
else
257
memset(&(t[n2]),0,n2*
sizeof
(
BN_ULONG
));
258
bn_sqr_recursive
(r,a,n,p);
259
bn_sqr_recursive
(&(r[n2]),&(a[n]),n,p);
260
261
/* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
262
* r[10] holds (a[0]*b[0])
263
* r[32] holds (b[1]*b[1])
264
*/
265
266
c1=(int)(
bn_add_words
(t,r,&(r[n2]),n2));
267
268
/* t[32] is negative */
269
c1-=(int)(
bn_sub_words
(&(t[n2]),t,&(t[n2]),n2));
270
271
/* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
272
* r[10] holds (a[0]*a[0])
273
* r[32] holds (a[1]*a[1])
274
* c1 holds the carry bits
275
*/
276
c1+=(int)(
bn_add_words
(&(r[n]),&(r[
n
]),&(t[n2]),n2));
277
if
(c1)
278
{
279
p= &(r[n+n2]);
280
lo= *
p
;
281
ln=(lo+c1)&
BN_MASK2
;
282
*p=ln;
283
284
/* The overflow will stop before we over write
285
* words we should not overwrite */
286
if
(ln < (
BN_ULONG
)c1)
287
{
288
do
{
289
p++;
290
lo= *
p
;
291
ln=(lo+1)&
BN_MASK2
;
292
*p=ln;
293
}
while
(ln == 0);
294
}
295
}
296
}
297
#endif
Generated on Thu Jan 10 2013 10:00:43 for cryptlib by
1.8.2