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_recp.c
Go to the documentation of this file.
1
/* crypto/bn/bn_recp.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
void
BN_RECP_CTX_init
(
BN_RECP_CTX
*recp)
67
{
68
BN_init
(&(recp->
N
));
69
BN_init
(&(recp->
Nr
));
70
recp->
num_bits
=0;
71
recp->
flags
=0;
72
}
73
74
BN_RECP_CTX
*
BN_RECP_CTX_new
(
void
)
75
{
76
BN_RECP_CTX
*ret;
77
78
if
((ret=(
BN_RECP_CTX
*)
clBnAlloc
(
"BN_RECP_CTX_new"
,
sizeof
(
BN_RECP_CTX
))) == NULL)
79
return
(NULL);
80
81
BN_RECP_CTX_init
(ret);
82
ret->
flags
=
BN_FLG_MALLOCED
;
83
return
(ret);
84
}
85
86
void
BN_RECP_CTX_free
(
BN_RECP_CTX
*recp)
87
{
88
if
(recp == NULL)
89
return
;
90
91
BN_free
(&(recp->
N
));
92
BN_free
(&(recp->
Nr
));
93
if
(recp->
flags
&
BN_FLG_MALLOCED
)
94
OPENSSL_free
(recp);
95
}
96
97
int
BN_RECP_CTX_set
(
BN_RECP_CTX
*recp,
const
BIGNUM
*d,
BN_CTX
*ctx)
98
{
99
if
(!
BN_copy
(&(recp->
N
),d))
return
0;
100
BN_zero
(&(recp->
Nr
));
101
recp->
num_bits
=
BN_num_bits
(d);
102
recp->
shift
=0;
103
return
(1);
104
}
105
106
int
BN_mod_mul_reciprocal
(
BIGNUM
*r,
const
BIGNUM
*x,
const
BIGNUM
*y,
107
BN_RECP_CTX
*recp,
BN_CTX
*ctx)
108
{
109
int
ret=0;
110
BIGNUM
*a;
111
const
BIGNUM
*ca;
112
113
BN_CTX_start
(ctx);
114
if
((a =
BN_CTX_get
(ctx)) == NULL)
goto
err;
115
if
(y != NULL)
116
{
117
if
(x == y)
118
{
if
(!
BN_sqr
(a,x,ctx))
goto
err; }
119
else
120
{
if
(!
BN_mul
(a,x,y,ctx))
goto
err; }
121
ca = a;
122
}
123
else
124
ca=x;
/* Just do the mod */
125
126
ret =
BN_div_recp
(NULL,r,ca,recp,ctx);
127
err:
128
BN_CTX_end
(ctx);
129
bn_check_top
(r);
130
return
(ret);
131
}
132
133
int
BN_div_recp
(
BIGNUM
*dv,
BIGNUM
*rem,
const
BIGNUM
*m,
134
BN_RECP_CTX
*recp,
BN_CTX
*ctx)
135
{
136
int
i,j,ret=0;
137
BIGNUM
*a,*b,*d,*r;
138
139
BN_CTX_start
(ctx);
140
a=
BN_CTX_get
(ctx);
141
b=
BN_CTX_get
(ctx);
142
if
(dv != NULL)
143
d=dv;
144
else
145
d=
BN_CTX_get
(ctx);
146
if
(rem != NULL)
147
r=rem;
148
else
149
r=
BN_CTX_get
(ctx);
150
if
(a == NULL || b == NULL || d == NULL || r == NULL)
goto
err;
151
152
if
(
BN_ucmp
(m,&(recp->
N
)) < 0)
153
{
154
BN_zero
(d);
155
if
(!
BN_copy
(r,m))
return
0;
156
BN_CTX_end
(ctx);
157
return
(1);
158
}
159
160
/* We want the remainder
161
* Given input of ABCDEF / ab
162
* we need multiply ABCDEF by 3 digests of the reciprocal of ab
163
*
164
*/
165
166
/* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */
167
i=
BN_num_bits
(m);
168
j=recp->
num_bits
<<1;
169
if
(j>i) i=j;
170
171
/* Nr := round(2^i / N) */
172
if
(i != recp->
shift
)
173
recp->
shift
=
BN_reciprocal
(&(recp->
Nr
),&(recp->
N
),
174
i,ctx);
/* BN_reciprocal returns i, or -1 for an error */
175
if
(recp->
shift
== -1)
goto
err;
176
177
/* d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|
178
* = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|
179
* <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
180
* = |m/N|
181
*/
182
if
(!
BN_rshift
(a,m,recp->
num_bits
))
goto
err;
183
if
(!
BN_mul
(b,a,&(recp->
Nr
),ctx))
goto
err;
184
if
(!
BN_rshift
(d,b,i-recp->
num_bits
))
goto
err;
185
d->
neg
=0;
186
187
if
(!
BN_mul
(b,&(recp->
N
),d,ctx))
goto
err;
188
if
(!
BN_usub
(r,m,b))
goto
err;
189
r->
neg
=0;
190
191
#if 1
192
j=0;
193
while
(
BN_ucmp
(r,&(recp->
N
)) >= 0)
194
{
195
if
(j++ > 2)
196
{
197
BNerr
(
BN_F_BN_DIV_RECP
,
BN_R_BAD_RECIPROCAL
);
198
goto
err;
199
}
200
if
(!
BN_usub
(r,r,&(recp->
N
)))
goto
err;
201
if
(!
BN_add_word
(d,1))
goto
err;
202
}
203
#endif
204
205
r->
neg
=
BN_is_zero
(r)?0:m->
neg
;
206
d->
neg
=m->
neg
^recp->
N
.
neg
;
207
ret=1;
208
err:
209
BN_CTX_end
(ctx);
210
if
(dv)
bn_check_top
(dv);
211
if
(rem)
bn_check_top
(rem);
212
return
(ret);
213
}
214
215
/* len is the expected size of the result
216
* We actually calculate with an extra word of precision, so
217
* we can do faster division if the remainder is not required.
218
*/
219
/* r := 2^len / m */
220
int
BN_reciprocal
(
BIGNUM
*r,
const
BIGNUM
*m,
int
len,
BN_CTX
*ctx)
221
{
222
int
ret= -1;
223
BIGNUM
*t;
224
225
BN_CTX_start
(ctx);
226
if
((t =
BN_CTX_get
(ctx)) == NULL)
goto
err;
227
228
if
(!
BN_set_bit
(t,len))
goto
err;
229
230
if
(!
BN_div
(r,NULL,t,m,ctx))
goto
err;
231
232
ret=len;
233
err:
234
bn_check_top
(r);
235
BN_CTX_end
(ctx);
236
return
(ret);
237
}
Generated on Thu Jan 10 2013 10:00:43 for cryptlib by
1.8.2