diff options
author | ryker <> | 1998-10-05 20:13:14 +0000 |
---|---|---|
committer | ryker <> | 1998-10-05 20:13:14 +0000 |
commit | aeeae06a79815dc190061534d47236cec09f9e32 (patch) | |
tree | 851692b9c2f9c04f077666855641900f19fdb217 /src/lib/libcrypto/bn | |
parent | a4f79641824cbf9f60ca9d1168d1fcc46717a82a (diff) | |
download | openbsd-aeeae06a79815dc190061534d47236cec09f9e32.tar.gz openbsd-aeeae06a79815dc190061534d47236cec09f9e32.tar.bz2 openbsd-aeeae06a79815dc190061534d47236cec09f9e32.zip |
Import of SSLeay-0.9.0b with RSA and IDEA stubbed + OpenBSD build
functionality for shared libs.
Note that routines such as sslv2_init and friends that use RSA will
not work due to lack of RSA in this library.
Needs documentation and help from ports for easy upgrade to full
functionality where legally possible.
Diffstat (limited to 'src/lib/libcrypto/bn')
23 files changed, 5718 insertions, 0 deletions
diff --git a/src/lib/libcrypto/bn/asm/bn-586.pl b/src/lib/libcrypto/bn/asm/bn-586.pl new file mode 100644 index 0000000000..19d425ee96 --- /dev/null +++ b/src/lib/libcrypto/bn/asm/bn-586.pl | |||
@@ -0,0 +1,314 @@ | |||
1 | #!/usr/bin/perl | ||
2 | # | ||
3 | |||
4 | #!/usr/local/bin/perl | ||
5 | |||
6 | push(@INC,"perlasm","../../perlasm"); | ||
7 | require "x86asm.pl"; | ||
8 | |||
9 | &asm_init($ARGV[0],"bn-586.pl"); | ||
10 | |||
11 | &bn_mul_add_words("bn_mul_add_words"); | ||
12 | &bn_mul_words("bn_mul_words"); | ||
13 | &bn_sqr_words("bn_sqr_words"); | ||
14 | &bn_div64("bn_div64"); | ||
15 | &bn_add_words("bn_add_words"); | ||
16 | |||
17 | &asm_finish(); | ||
18 | |||
19 | sub bn_mul_add_words | ||
20 | { | ||
21 | local($name)=@_; | ||
22 | |||
23 | &function_begin($name,""); | ||
24 | |||
25 | &comment(""); | ||
26 | $Low="eax"; | ||
27 | $High="edx"; | ||
28 | $a="ebx"; | ||
29 | $w="ebp"; | ||
30 | $r="edi"; | ||
31 | $c="esi"; | ||
32 | |||
33 | &xor($c,$c); # clear carry | ||
34 | &mov($r,&wparam(0)); # | ||
35 | |||
36 | &mov("ecx",&wparam(2)); # | ||
37 | &mov($a,&wparam(1)); # | ||
38 | |||
39 | &and("ecx",0xfffffff8); # num / 8 | ||
40 | &mov($w,&wparam(3)); # | ||
41 | |||
42 | &push("ecx"); # Up the stack for a tmp variable | ||
43 | |||
44 | &jz(&label("maw_finish")); | ||
45 | |||
46 | &set_label("maw_loop",0); | ||
47 | |||
48 | &mov(&swtmp(0),"ecx"); # | ||
49 | |||
50 | for ($i=0; $i<32; $i+=4) | ||
51 | { | ||
52 | &comment("Round $i"); | ||
53 | |||
54 | &mov("eax",&DWP($i,$a,"",0)); # *a | ||
55 | &mul($w); # *a * w | ||
56 | &add("eax",$c); # L(t)+= *r | ||
57 | &mov($c,&DWP($i,$r,"",0)); # L(t)+= *r | ||
58 | &adc("edx",0); # H(t)+=carry | ||
59 | &add("eax",$c); # L(t)+=c | ||
60 | &adc("edx",0); # H(t)+=carry | ||
61 | &mov(&DWP($i,$r,"",0),"eax"); # *r= L(t); | ||
62 | &mov($c,"edx"); # c= H(t); | ||
63 | } | ||
64 | |||
65 | &comment(""); | ||
66 | &mov("ecx",&swtmp(0)); # | ||
67 | &add($a,32); | ||
68 | &add($r,32); | ||
69 | &sub("ecx",8); | ||
70 | &jnz(&label("maw_loop")); | ||
71 | |||
72 | &set_label("maw_finish",0); | ||
73 | &mov("ecx",&wparam(2)); # get num | ||
74 | &and("ecx",7); | ||
75 | &jnz(&label("maw_finish2")); # helps branch prediction | ||
76 | &jmp(&label("maw_end")); | ||
77 | |||
78 | &set_label("maw_finish2",1); | ||
79 | for ($i=0; $i<7; $i++) | ||
80 | { | ||
81 | &comment("Tail Round $i"); | ||
82 | &mov("eax",&DWP($i*4,$a,"",0));# *a | ||
83 | &mul($w); # *a * w | ||
84 | &add("eax",$c); # L(t)+=c | ||
85 | &mov($c,&DWP($i*4,$r,"",0)); # L(t)+= *r | ||
86 | &adc("edx",0); # H(t)+=carry | ||
87 | &add("eax",$c); | ||
88 | &adc("edx",0); # H(t)+=carry | ||
89 | &dec("ecx") if ($i != 7-1); | ||
90 | &mov(&DWP($i*4,$r,"",0),"eax"); # *r= L(t); | ||
91 | &mov($c,"edx"); # c= H(t); | ||
92 | &jz(&label("maw_end")) if ($i != 7-1); | ||
93 | } | ||
94 | &set_label("maw_end",0); | ||
95 | &mov("eax",$c); | ||
96 | |||
97 | &pop("ecx"); # clear variable from | ||
98 | |||
99 | &function_end($name); | ||
100 | } | ||
101 | |||
102 | sub bn_mul_words | ||
103 | { | ||
104 | local($name)=@_; | ||
105 | |||
106 | &function_begin($name,""); | ||
107 | |||
108 | &comment(""); | ||
109 | $Low="eax"; | ||
110 | $High="edx"; | ||
111 | $a="ebx"; | ||
112 | $w="ecx"; | ||
113 | $r="edi"; | ||
114 | $c="esi"; | ||
115 | $num="ebp"; | ||
116 | |||
117 | &xor($c,$c); # clear carry | ||
118 | &mov($r,&wparam(0)); # | ||
119 | &mov($a,&wparam(1)); # | ||
120 | &mov($num,&wparam(2)); # | ||
121 | &mov($w,&wparam(3)); # | ||
122 | |||
123 | &and($num,0xfffffff8); # num / 8 | ||
124 | &jz(&label("mw_finish")); | ||
125 | |||
126 | &set_label("mw_loop",0); | ||
127 | for ($i=0; $i<32; $i+=4) | ||
128 | { | ||
129 | &comment("Round $i"); | ||
130 | |||
131 | &mov("eax",&DWP($i,$a,"",0)); # *a | ||
132 | &mul($w); # *a * w | ||
133 | &add("eax",$c); # L(t)+=c | ||
134 | # XXX | ||
135 | |||
136 | &adc("edx",0); # H(t)+=carry | ||
137 | &mov(&DWP($i,$r,"",0),"eax"); # *r= L(t); | ||
138 | |||
139 | &mov($c,"edx"); # c= H(t); | ||
140 | } | ||
141 | |||
142 | &comment(""); | ||
143 | &add($a,32); | ||
144 | &add($r,32); | ||
145 | &sub($num,8); | ||
146 | &jz(&label("mw_finish")); | ||
147 | &jmp(&label("mw_loop")); | ||
148 | |||
149 | &set_label("mw_finish",0); | ||
150 | &mov($num,&wparam(2)); # get num | ||
151 | &and($num,7); | ||
152 | &jnz(&label("mw_finish2")); | ||
153 | &jmp(&label("mw_end")); | ||
154 | |||
155 | &set_label("mw_finish2",1); | ||
156 | for ($i=0; $i<7; $i++) | ||
157 | { | ||
158 | &comment("Tail Round $i"); | ||
159 | &mov("eax",&DWP($i*4,$a,"",0));# *a | ||
160 | &mul($w); # *a * w | ||
161 | &add("eax",$c); # L(t)+=c | ||
162 | # XXX | ||
163 | &adc("edx",0); # H(t)+=carry | ||
164 | &mov(&DWP($i*4,$r,"",0),"eax");# *r= L(t); | ||
165 | &mov($c,"edx"); # c= H(t); | ||
166 | &dec($num) if ($i != 7-1); | ||
167 | &jz(&label("mw_end")) if ($i != 7-1); | ||
168 | } | ||
169 | &set_label("mw_end",0); | ||
170 | &mov("eax",$c); | ||
171 | |||
172 | &function_end($name); | ||
173 | } | ||
174 | |||
175 | sub bn_sqr_words | ||
176 | { | ||
177 | local($name)=@_; | ||
178 | |||
179 | &function_begin($name,""); | ||
180 | |||
181 | &comment(""); | ||
182 | $r="esi"; | ||
183 | $a="edi"; | ||
184 | $num="ebx"; | ||
185 | |||
186 | &mov($r,&wparam(0)); # | ||
187 | &mov($a,&wparam(1)); # | ||
188 | &mov($num,&wparam(2)); # | ||
189 | |||
190 | &and($num,0xfffffff8); # num / 8 | ||
191 | &jz(&label("sw_finish")); | ||
192 | |||
193 | &set_label("sw_loop",0); | ||
194 | for ($i=0; $i<32; $i+=4) | ||
195 | { | ||
196 | &comment("Round $i"); | ||
197 | &mov("eax",&DWP($i,$a,"",0)); # *a | ||
198 | # XXX | ||
199 | &mul("eax"); # *a * *a | ||
200 | &mov(&DWP($i*2,$r,"",0),"eax"); # | ||
201 | &mov(&DWP($i*2+4,$r,"",0),"edx");# | ||
202 | } | ||
203 | |||
204 | &comment(""); | ||
205 | &add($a,32); | ||
206 | &add($r,64); | ||
207 | &sub($num,8); | ||
208 | &jnz(&label("sw_loop")); | ||
209 | |||
210 | &set_label("sw_finish",0); | ||
211 | &mov($num,&wparam(2)); # get num | ||
212 | &and($num,7); | ||
213 | &jz(&label("sw_end")); | ||
214 | |||
215 | for ($i=0; $i<7; $i++) | ||
216 | { | ||
217 | &comment("Tail Round $i"); | ||
218 | &mov("eax",&DWP($i*4,$a,"",0)); # *a | ||
219 | # XXX | ||
220 | &mul("eax"); # *a * *a | ||
221 | &mov(&DWP($i*8,$r,"",0),"eax"); # | ||
222 | &dec($num) if ($i != 7-1); | ||
223 | &mov(&DWP($i*8+4,$r,"",0),"edx"); | ||
224 | &jz(&label("sw_end")) if ($i != 7-1); | ||
225 | } | ||
226 | &set_label("sw_end",0); | ||
227 | |||
228 | &function_end($name); | ||
229 | } | ||
230 | |||
231 | sub bn_div64 | ||
232 | { | ||
233 | local($name)=@_; | ||
234 | |||
235 | &function_begin($name,""); | ||
236 | &mov("edx",&wparam(0)); # | ||
237 | &mov("eax",&wparam(1)); # | ||
238 | &mov("ebx",&wparam(2)); # | ||
239 | &div("ebx"); | ||
240 | &function_end($name); | ||
241 | } | ||
242 | |||
243 | sub bn_add_words | ||
244 | { | ||
245 | local($name)=@_; | ||
246 | |||
247 | &function_begin($name,""); | ||
248 | |||
249 | &comment(""); | ||
250 | $a="esi"; | ||
251 | $b="edi"; | ||
252 | $c="eax"; | ||
253 | $r="ebx"; | ||
254 | $tmp1="ecx"; | ||
255 | $tmp2="edx"; | ||
256 | $num="ebp"; | ||
257 | |||
258 | &mov($r,&wparam(0)); # get r | ||
259 | &mov($a,&wparam(1)); # get a | ||
260 | &mov($b,&wparam(2)); # get b | ||
261 | &mov($num,&wparam(3)); # get num | ||
262 | &xor($c,$c); # clear carry | ||
263 | &and($num,0xfffffff8); # num / 8 | ||
264 | |||
265 | &jz(&label("aw_finish")); | ||
266 | |||
267 | &set_label("aw_loop",0); | ||
268 | for ($i=0; $i<8; $i++) | ||
269 | { | ||
270 | &comment("Round $i"); | ||
271 | |||
272 | &mov($tmp1,&DWP($i*4,$a,"",0)); # *a | ||
273 | &mov($tmp2,&DWP($i*4,$b,"",0)); # *b | ||
274 | &add($tmp1,$c); | ||
275 | &mov($c,0); | ||
276 | &adc($c,$c); | ||
277 | &add($tmp1,$tmp2); | ||
278 | &adc($c,0); | ||
279 | &mov(&DWP($i*4,$r,"",0),$tmp1); # *r | ||
280 | } | ||
281 | |||
282 | &comment(""); | ||
283 | &add($a,32); | ||
284 | &add($b,32); | ||
285 | &add($r,32); | ||
286 | &sub($num,8); | ||
287 | &jnz(&label("aw_loop")); | ||
288 | |||
289 | &set_label("aw_finish",0); | ||
290 | &mov($num,&wparam(3)); # get num | ||
291 | &and($num,7); | ||
292 | &jz(&label("aw_end")); | ||
293 | |||
294 | for ($i=0; $i<7; $i++) | ||
295 | { | ||
296 | &comment("Tail Round $i"); | ||
297 | &mov($tmp1,&DWP($i*4,$a,"",0)); # *a | ||
298 | &mov($tmp2,&DWP($i*4,$b,"",0));# *b | ||
299 | &add($tmp1,$c); | ||
300 | &mov($c,0); | ||
301 | &adc($c,$c); | ||
302 | &add($tmp1,$tmp2); | ||
303 | &adc($c,0); | ||
304 | &dec($num) if ($i != 6); | ||
305 | &mov(&DWP($i*4,$r,"",0),$tmp1); # *a | ||
306 | &jz(&label("aw_end")) if ($i != 6); | ||
307 | } | ||
308 | &set_label("aw_end",0); | ||
309 | |||
310 | &mov("eax",$c); | ||
311 | |||
312 | &function_end($name); | ||
313 | } | ||
314 | |||
diff --git a/src/lib/libcrypto/bn/asm/pa-risc2.s b/src/lib/libcrypto/bn/asm/pa-risc2.s new file mode 100644 index 0000000000..c2725996a4 --- /dev/null +++ b/src/lib/libcrypto/bn/asm/pa-risc2.s | |||
@@ -0,0 +1,416 @@ | |||
1 | .SPACE $PRIVATE$ | ||
2 | .SUBSPA $DATA$,QUAD=1,ALIGN=8,ACCESS=31 | ||
3 | .SUBSPA $BSS$,QUAD=1,ALIGN=8,ACCESS=31,ZERO,SORT=82 | ||
4 | .SPACE $TEXT$ | ||
5 | .SUBSPA $LIT$,QUAD=0,ALIGN=8,ACCESS=44 | ||
6 | .SUBSPA $CODE$,QUAD=0,ALIGN=8,ACCESS=44,CODE_ONLY | ||
7 | .IMPORT $global$,DATA | ||
8 | .IMPORT $$dyncall,MILLICODE | ||
9 | ; gcc_compiled.: | ||
10 | .SPACE $TEXT$ | ||
11 | .SUBSPA $CODE$ | ||
12 | |||
13 | .align 4 | ||
14 | .EXPORT bn_mul_add_words,ENTRY,PRIV_LEV=3,ARGW0=GR,ARGW1=GR,ARGW2=GR,ARGW3=GR,RTNVAL=GR | ||
15 | bn_mul_add_words | ||
16 | .PROC | ||
17 | .CALLINFO FRAME=64,CALLS,SAVE_RP,ENTRY_GR=4 | ||
18 | .ENTRY | ||
19 | stw %r2,-20(0,%r30) | ||
20 | stwm %r4,64(0,%r30) | ||
21 | copy %r24,%r31 | ||
22 | stw %r3,-60(0,%r30) | ||
23 | ldi 0,%r20 | ||
24 | ldo 12(%r26),%r2 | ||
25 | stw %r23,-16(0,%r30) | ||
26 | copy %r25,%r3 | ||
27 | ldo 12(%r3),%r1 | ||
28 | fldws -16(0,%r30),%fr8L | ||
29 | L$0010 | ||
30 | copy %r20,%r25 | ||
31 | ldi 0,%r24 | ||
32 | fldws 0(0,%r3),%fr9L | ||
33 | ldw 0(0,%r26),%r19 | ||
34 | xmpyu %fr8L,%fr9L,%fr9 | ||
35 | fstds %fr9,-16(0,%r30) | ||
36 | copy %r19,%r23 | ||
37 | ldw -16(0,%r30),%r28 | ||
38 | ldw -12(0,%r30),%r29 | ||
39 | ldi 0,%r22 | ||
40 | add %r23,%r29,%r29 | ||
41 | addc %r22,%r28,%r28 | ||
42 | add %r25,%r29,%r29 | ||
43 | addc %r24,%r28,%r28 | ||
44 | copy %r28,%r21 | ||
45 | ldi 0,%r20 | ||
46 | copy %r21,%r20 | ||
47 | addib,= -1,%r31,L$0011 | ||
48 | stw %r29,0(0,%r26) | ||
49 | copy %r20,%r25 | ||
50 | ldi 0,%r24 | ||
51 | fldws -8(0,%r1),%fr9L | ||
52 | ldw -8(0,%r2),%r19 | ||
53 | xmpyu %fr8L,%fr9L,%fr9 | ||
54 | fstds %fr9,-16(0,%r30) | ||
55 | copy %r19,%r23 | ||
56 | ldw -16(0,%r30),%r28 | ||
57 | ldw -12(0,%r30),%r29 | ||
58 | ldi 0,%r22 | ||
59 | add %r23,%r29,%r29 | ||
60 | addc %r22,%r28,%r28 | ||
61 | add %r25,%r29,%r29 | ||
62 | addc %r24,%r28,%r28 | ||
63 | copy %r28,%r21 | ||
64 | ldi 0,%r20 | ||
65 | copy %r21,%r20 | ||
66 | addib,= -1,%r31,L$0011 | ||
67 | stw %r29,-8(0,%r2) | ||
68 | copy %r20,%r25 | ||
69 | ldi 0,%r24 | ||
70 | fldws -4(0,%r1),%fr9L | ||
71 | ldw -4(0,%r2),%r19 | ||
72 | xmpyu %fr8L,%fr9L,%fr9 | ||
73 | fstds %fr9,-16(0,%r30) | ||
74 | copy %r19,%r23 | ||
75 | ldw -16(0,%r30),%r28 | ||
76 | ldw -12(0,%r30),%r29 | ||
77 | ldi 0,%r22 | ||
78 | add %r23,%r29,%r29 | ||
79 | addc %r22,%r28,%r28 | ||
80 | add %r25,%r29,%r29 | ||
81 | addc %r24,%r28,%r28 | ||
82 | copy %r28,%r21 | ||
83 | ldi 0,%r20 | ||
84 | copy %r21,%r20 | ||
85 | addib,= -1,%r31,L$0011 | ||
86 | stw %r29,-4(0,%r2) | ||
87 | copy %r20,%r25 | ||
88 | ldi 0,%r24 | ||
89 | fldws 0(0,%r1),%fr9L | ||
90 | ldw 0(0,%r2),%r19 | ||
91 | xmpyu %fr8L,%fr9L,%fr9 | ||
92 | fstds %fr9,-16(0,%r30) | ||
93 | copy %r19,%r23 | ||
94 | ldw -16(0,%r30),%r28 | ||
95 | ldw -12(0,%r30),%r29 | ||
96 | ldi 0,%r22 | ||
97 | add %r23,%r29,%r29 | ||
98 | addc %r22,%r28,%r28 | ||
99 | add %r25,%r29,%r29 | ||
100 | addc %r24,%r28,%r28 | ||
101 | copy %r28,%r21 | ||
102 | ldi 0,%r20 | ||
103 | copy %r21,%r20 | ||
104 | addib,= -1,%r31,L$0011 | ||
105 | stw %r29,0(0,%r2) | ||
106 | ldo 16(%r1),%r1 | ||
107 | ldo 16(%r3),%r3 | ||
108 | ldo 16(%r2),%r2 | ||
109 | bl L$0010,0 | ||
110 | ldo 16(%r26),%r26 | ||
111 | L$0011 | ||
112 | copy %r20,%r28 | ||
113 | ldw -84(0,%r30),%r2 | ||
114 | ldw -60(0,%r30),%r3 | ||
115 | bv 0(%r2) | ||
116 | ldwm -64(0,%r30),%r4 | ||
117 | .EXIT | ||
118 | .PROCEND | ||
119 | .align 4 | ||
120 | .EXPORT bn_mul_words,ENTRY,PRIV_LEV=3,ARGW0=GR,ARGW1=GR,ARGW2=GR,ARGW3=GR,RTNVAL=GR | ||
121 | bn_mul_words | ||
122 | .PROC | ||
123 | .CALLINFO FRAME=64,CALLS,SAVE_RP,ENTRY_GR=3 | ||
124 | .ENTRY | ||
125 | stw %r2,-20(0,%r30) | ||
126 | copy %r25,%r2 | ||
127 | stwm %r4,64(0,%r30) | ||
128 | copy %r24,%r19 | ||
129 | ldi 0,%r28 | ||
130 | stw %r23,-16(0,%r30) | ||
131 | ldo 12(%r26),%r31 | ||
132 | ldo 12(%r2),%r29 | ||
133 | fldws -16(0,%r30),%fr8L | ||
134 | L$0026 | ||
135 | fldws 0(0,%r2),%fr9L | ||
136 | xmpyu %fr8L,%fr9L,%fr9 | ||
137 | fstds %fr9,-16(0,%r30) | ||
138 | copy %r28,%r21 | ||
139 | ldi 0,%r20 | ||
140 | ldw -16(0,%r30),%r24 | ||
141 | ldw -12(0,%r30),%r25 | ||
142 | add %r21,%r25,%r25 | ||
143 | addc %r20,%r24,%r24 | ||
144 | copy %r24,%r23 | ||
145 | ldi 0,%r22 | ||
146 | copy %r23,%r28 | ||
147 | addib,= -1,%r19,L$0027 | ||
148 | stw %r25,0(0,%r26) | ||
149 | fldws -8(0,%r29),%fr9L | ||
150 | xmpyu %fr8L,%fr9L,%fr9 | ||
151 | fstds %fr9,-16(0,%r30) | ||
152 | copy %r28,%r21 | ||
153 | ldi 0,%r20 | ||
154 | ldw -16(0,%r30),%r24 | ||
155 | ldw -12(0,%r30),%r25 | ||
156 | add %r21,%r25,%r25 | ||
157 | addc %r20,%r24,%r24 | ||
158 | copy %r24,%r23 | ||
159 | ldi 0,%r22 | ||
160 | copy %r23,%r28 | ||
161 | addib,= -1,%r19,L$0027 | ||
162 | stw %r25,-8(0,%r31) | ||
163 | fldws -4(0,%r29),%fr9L | ||
164 | xmpyu %fr8L,%fr9L,%fr9 | ||
165 | fstds %fr9,-16(0,%r30) | ||
166 | copy %r28,%r21 | ||
167 | ldi 0,%r20 | ||
168 | ldw -16(0,%r30),%r24 | ||
169 | ldw -12(0,%r30),%r25 | ||
170 | add %r21,%r25,%r25 | ||
171 | addc %r20,%r24,%r24 | ||
172 | copy %r24,%r23 | ||
173 | ldi 0,%r22 | ||
174 | copy %r23,%r28 | ||
175 | addib,= -1,%r19,L$0027 | ||
176 | stw %r25,-4(0,%r31) | ||
177 | fldws 0(0,%r29),%fr9L | ||
178 | xmpyu %fr8L,%fr9L,%fr9 | ||
179 | fstds %fr9,-16(0,%r30) | ||
180 | copy %r28,%r21 | ||
181 | ldi 0,%r20 | ||
182 | ldw -16(0,%r30),%r24 | ||
183 | ldw -12(0,%r30),%r25 | ||
184 | add %r21,%r25,%r25 | ||
185 | addc %r20,%r24,%r24 | ||
186 | copy %r24,%r23 | ||
187 | ldi 0,%r22 | ||
188 | copy %r23,%r28 | ||
189 | addib,= -1,%r19,L$0027 | ||
190 | stw %r25,0(0,%r31) | ||
191 | ldo 16(%r29),%r29 | ||
192 | ldo 16(%r2),%r2 | ||
193 | ldo 16(%r31),%r31 | ||
194 | bl L$0026,0 | ||
195 | ldo 16(%r26),%r26 | ||
196 | L$0027 | ||
197 | ldw -84(0,%r30),%r2 | ||
198 | bv 0(%r2) | ||
199 | ldwm -64(0,%r30),%r4 | ||
200 | .EXIT | ||
201 | .PROCEND | ||
202 | .align 4 | ||
203 | .EXPORT bn_sqr_words,ENTRY,PRIV_LEV=3,ARGW0=GR,ARGW1=GR,ARGW2=GR | ||
204 | bn_sqr_words | ||
205 | .PROC | ||
206 | .CALLINFO FRAME=0,NO_CALLS | ||
207 | .ENTRY | ||
208 | ldo 28(%r26),%r19 | ||
209 | ldo 12(%r25),%r28 | ||
210 | L$0042 | ||
211 | fldws 0(0,%r25),%fr8L | ||
212 | fldws 0(0,%r25),%fr8R | ||
213 | xmpyu %fr8L,%fr8R,%fr8 | ||
214 | fstds %fr8,-16(0,%r30) | ||
215 | ldw -16(0,%r30),%r22 | ||
216 | ldw -12(0,%r30),%r23 | ||
217 | stw %r23,0(0,%r26) | ||
218 | copy %r22,%r21 | ||
219 | ldi 0,%r20 | ||
220 | addib,= -1,%r24,L$0049 | ||
221 | stw %r21,-24(0,%r19) | ||
222 | fldws -8(0,%r28),%fr8L | ||
223 | fldws -8(0,%r28),%fr8R | ||
224 | xmpyu %fr8L,%fr8R,%fr8 | ||
225 | fstds %fr8,-16(0,%r30) | ||
226 | ldw -16(0,%r30),%r22 | ||
227 | ldw -12(0,%r30),%r23 | ||
228 | stw %r23,-20(0,%r19) | ||
229 | copy %r22,%r21 | ||
230 | ldi 0,%r20 | ||
231 | addib,= -1,%r24,L$0049 | ||
232 | stw %r21,-16(0,%r19) | ||
233 | fldws -4(0,%r28),%fr8L | ||
234 | fldws -4(0,%r28),%fr8R | ||
235 | xmpyu %fr8L,%fr8R,%fr8 | ||
236 | fstds %fr8,-16(0,%r30) | ||
237 | ldw -16(0,%r30),%r22 | ||
238 | ldw -12(0,%r30),%r23 | ||
239 | stw %r23,-12(0,%r19) | ||
240 | copy %r22,%r21 | ||
241 | ldi 0,%r20 | ||
242 | addib,= -1,%r24,L$0049 | ||
243 | stw %r21,-8(0,%r19) | ||
244 | fldws 0(0,%r28),%fr8L | ||
245 | fldws 0(0,%r28),%fr8R | ||
246 | xmpyu %fr8L,%fr8R,%fr8 | ||
247 | fstds %fr8,-16(0,%r30) | ||
248 | ldw -16(0,%r30),%r22 | ||
249 | ldw -12(0,%r30),%r23 | ||
250 | stw %r23,-4(0,%r19) | ||
251 | copy %r22,%r21 | ||
252 | ldi 0,%r20 | ||
253 | addib,= -1,%r24,L$0049 | ||
254 | stw %r21,0(0,%r19) | ||
255 | ldo 16(%r28),%r28 | ||
256 | ldo 16(%r25),%r25 | ||
257 | ldo 32(%r19),%r19 | ||
258 | bl L$0042,0 | ||
259 | ldo 32(%r26),%r26 | ||
260 | L$0049 | ||
261 | bv,n 0(%r2) | ||
262 | .EXIT | ||
263 | .PROCEND | ||
264 | .IMPORT BN_num_bits_word,CODE | ||
265 | .IMPORT fprintf,CODE | ||
266 | .IMPORT __iob,DATA | ||
267 | .SPACE $TEXT$ | ||
268 | .SUBSPA $LIT$ | ||
269 | |||
270 | .align 4 | ||
271 | L$C0000 | ||
272 | .STRING "Division would overflow (%d)\x0a\x00" | ||
273 | .IMPORT abort,CODE | ||
274 | .SPACE $TEXT$ | ||
275 | .SUBSPA $CODE$ | ||
276 | |||
277 | .align 4 | ||
278 | .EXPORT bn_div64,ENTRY,PRIV_LEV=3,ARGW0=GR,ARGW1=GR,ARGW2=GR,RTNVAL=GR | ||
279 | bn_div64 | ||
280 | .PROC | ||
281 | .CALLINFO FRAME=128,CALLS,SAVE_RP,ENTRY_GR=8 | ||
282 | .ENTRY | ||
283 | stw %r2,-20(0,%r30) | ||
284 | stwm %r8,128(0,%r30) | ||
285 | stw %r7,-124(0,%r30) | ||
286 | stw %r4,-112(0,%r30) | ||
287 | stw %r3,-108(0,%r30) | ||
288 | copy %r26,%r3 | ||
289 | copy %r25,%r4 | ||
290 | stw %r6,-120(0,%r30) | ||
291 | ldi 0,%r7 | ||
292 | stw %r5,-116(0,%r30) | ||
293 | movb,<> %r24,%r5,L$0051 | ||
294 | ldi 2,%r6 | ||
295 | bl L$0068,0 | ||
296 | ldi -1,%r28 | ||
297 | L$0051 | ||
298 | .CALL ARGW0=GR | ||
299 | bl BN_num_bits_word,%r2 | ||
300 | copy %r5,%r26 | ||
301 | copy %r28,%r24 | ||
302 | ldi 32,%r19 | ||
303 | comb,= %r19,%r24,L$0052 | ||
304 | subi 31,%r24,%r19 | ||
305 | mtsar %r19 | ||
306 | zvdepi 1,32,%r19 | ||
307 | comb,>>= %r19,%r3,L$0052 | ||
308 | addil LR'__iob-$global$+32,%r27 | ||
309 | ldo RR'__iob-$global$+32(%r1),%r26 | ||
310 | ldil LR'L$C0000,%r25 | ||
311 | .CALL ARGW0=GR,ARGW1=GR,ARGW2=GR | ||
312 | bl fprintf,%r2 | ||
313 | ldo RR'L$C0000(%r25),%r25 | ||
314 | .CALL | ||
315 | bl abort,%r2 | ||
316 | nop | ||
317 | L$0052 | ||
318 | comb,>> %r5,%r3,L$0053 | ||
319 | subi 32,%r24,%r24 | ||
320 | sub %r3,%r5,%r3 | ||
321 | L$0053 | ||
322 | comib,= 0,%r24,L$0054 | ||
323 | subi 31,%r24,%r19 | ||
324 | mtsar %r19 | ||
325 | zvdep %r5,32,%r5 | ||
326 | zvdep %r3,32,%r21 | ||
327 | subi 32,%r24,%r20 | ||
328 | mtsar %r20 | ||
329 | vshd 0,%r4,%r20 | ||
330 | or %r21,%r20,%r3 | ||
331 | mtsar %r19 | ||
332 | zvdep %r4,32,%r4 | ||
333 | L$0054 | ||
334 | extru %r5,15,16,%r23 | ||
335 | extru %r5,31,16,%r28 | ||
336 | L$0055 | ||
337 | extru %r3,15,16,%r19 | ||
338 | comb,<> %r23,%r19,L$0058 | ||
339 | copy %r3,%r26 | ||
340 | bl L$0059,0 | ||
341 | zdepi -1,31,16,%r29 | ||
342 | L$0058 | ||
343 | .IMPORT $$divU,MILLICODE | ||
344 | bl $$divU,%r31 | ||
345 | copy %r23,%r25 | ||
346 | L$0059 | ||
347 | stw %r29,-16(0,%r30) | ||
348 | fldws -16(0,%r30),%fr10L | ||
349 | stw %r28,-16(0,%r30) | ||
350 | fldws -16(0,%r30),%fr10R | ||
351 | stw %r23,-16(0,%r30) | ||
352 | xmpyu %fr10L,%fr10R,%fr8 | ||
353 | fldws -16(0,%r30),%fr10R | ||
354 | fstws %fr8R,-16(0,%r30) | ||
355 | xmpyu %fr10L,%fr10R,%fr9 | ||
356 | ldw -16(0,%r30),%r8 | ||
357 | fstws %fr9R,-16(0,%r30) | ||
358 | copy %r8,%r22 | ||
359 | ldw -16(0,%r30),%r8 | ||
360 | extru %r4,15,16,%r24 | ||
361 | copy %r8,%r21 | ||
362 | L$0060 | ||
363 | sub %r3,%r21,%r20 | ||
364 | copy %r20,%r19 | ||
365 | depi 0,31,16,%r19 | ||
366 | comib,<> 0,%r19,L$0061 | ||
367 | zdep %r20,15,16,%r19 | ||
368 | addl %r19,%r24,%r19 | ||
369 | comb,>>= %r19,%r22,L$0061 | ||
370 | sub %r22,%r28,%r22 | ||
371 | sub %r21,%r23,%r21 | ||
372 | bl L$0060,0 | ||
373 | ldo -1(%r29),%r29 | ||
374 | L$0061 | ||
375 | stw %r29,-16(0,%r30) | ||
376 | fldws -16(0,%r30),%fr10L | ||
377 | stw %r28,-16(0,%r30) | ||
378 | fldws -16(0,%r30),%fr10R | ||
379 | xmpyu %fr10L,%fr10R,%fr8 | ||
380 | fstws %fr8R,-16(0,%r30) | ||
381 | ldw -16(0,%r30),%r8 | ||
382 | stw %r23,-16(0,%r30) | ||
383 | fldws -16(0,%r30),%fr10R | ||
384 | copy %r8,%r19 | ||
385 | xmpyu %fr10L,%fr10R,%fr8 | ||
386 | fstws %fr8R,-16(0,%r30) | ||
387 | extru %r19,15,16,%r20 | ||
388 | ldw -16(0,%r30),%r8 | ||
389 | zdep %r19,15,16,%r19 | ||
390 | addl %r8,%r20,%r20 | ||
391 | comclr,<<= %r19,%r4,0 | ||
392 | addi 1,%r20,%r20 | ||
393 | comb,<<= %r20,%r3,L$0066 | ||
394 | sub %r4,%r19,%r4 | ||
395 | addl %r3,%r5,%r3 | ||
396 | ldo -1(%r29),%r29 | ||
397 | L$0066 | ||
398 | addib,= -1,%r6,L$0056 | ||
399 | sub %r3,%r20,%r3 | ||
400 | zdep %r29,15,16,%r7 | ||
401 | shd %r3,%r4,16,%r3 | ||
402 | bl L$0055,0 | ||
403 | zdep %r4,15,16,%r4 | ||
404 | L$0056 | ||
405 | or %r7,%r29,%r28 | ||
406 | L$0068 | ||
407 | ldw -148(0,%r30),%r2 | ||
408 | ldw -124(0,%r30),%r7 | ||
409 | ldw -120(0,%r30),%r6 | ||
410 | ldw -116(0,%r30),%r5 | ||
411 | ldw -112(0,%r30),%r4 | ||
412 | ldw -108(0,%r30),%r3 | ||
413 | bv 0(%r2) | ||
414 | ldwm -128(0,%r30),%r8 | ||
415 | .EXIT | ||
416 | .PROCEND | ||
diff --git a/src/lib/libcrypto/bn/bn_add.c b/src/lib/libcrypto/bn/bn_add.c new file mode 100644 index 0000000000..efb2e312e8 --- /dev/null +++ b/src/lib/libcrypto/bn/bn_add.c | |||
@@ -0,0 +1,167 @@ | |||
1 | /* crypto/bn/bn_add.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include "cryptlib.h" | ||
61 | #include "bn_lcl.h" | ||
62 | |||
63 | /* r can == a or b */ | ||
64 | int BN_add(r, a, b) | ||
65 | BIGNUM *r; | ||
66 | BIGNUM *a; | ||
67 | BIGNUM *b; | ||
68 | { | ||
69 | int i; | ||
70 | BIGNUM *tmp; | ||
71 | |||
72 | /* a + b a+b | ||
73 | * a + -b a-b | ||
74 | * -a + b b-a | ||
75 | * -a + -b -(a+b) | ||
76 | */ | ||
77 | if (a->neg ^ b->neg) | ||
78 | { | ||
79 | /* only one is negative */ | ||
80 | if (a->neg) | ||
81 | { tmp=a; a=b; b=tmp; } | ||
82 | |||
83 | /* we are now a - b */ | ||
84 | |||
85 | if (BN_ucmp(a,b) < 0) | ||
86 | { | ||
87 | if (bn_wexpand(r,b->top) == NULL) return(0); | ||
88 | bn_qsub(r,b,a); | ||
89 | r->neg=1; | ||
90 | } | ||
91 | else | ||
92 | { | ||
93 | if (bn_wexpand(r,a->top) == NULL) return(0); | ||
94 | bn_qsub(r,a,b); | ||
95 | r->neg=0; | ||
96 | } | ||
97 | return(1); | ||
98 | } | ||
99 | |||
100 | if (a->neg) /* both are neg */ | ||
101 | r->neg=1; | ||
102 | else | ||
103 | r->neg=0; | ||
104 | |||
105 | i=(a->top > b->top); | ||
106 | |||
107 | if (i) | ||
108 | { | ||
109 | if (bn_wexpand(r,a->top+1) == NULL) return(0); | ||
110 | bn_qadd(r,a,b); | ||
111 | } | ||
112 | else | ||
113 | { | ||
114 | if (bn_wexpand(r,b->top+1) == NULL) return(0); | ||
115 | bn_qadd(r,b,a); | ||
116 | } | ||
117 | return(1); | ||
118 | } | ||
119 | |||
120 | /* unsigned add of b to a, r must be large enough */ | ||
121 | void bn_qadd(r,a,b) | ||
122 | BIGNUM *r; | ||
123 | BIGNUM *a; | ||
124 | BIGNUM *b; | ||
125 | { | ||
126 | register int i; | ||
127 | int max,min; | ||
128 | BN_ULONG *ap,*bp,*rp,carry,t1; | ||
129 | |||
130 | max=a->top; | ||
131 | min=b->top; | ||
132 | r->top=max; | ||
133 | |||
134 | ap=a->d; | ||
135 | bp=b->d; | ||
136 | rp=r->d; | ||
137 | carry=0; | ||
138 | |||
139 | carry=bn_add_words(rp,ap,bp,min); | ||
140 | rp+=min; | ||
141 | ap+=min; | ||
142 | bp+=min; | ||
143 | i=min; | ||
144 | |||
145 | if (carry) | ||
146 | { | ||
147 | while (i < max) | ||
148 | { | ||
149 | i++; | ||
150 | t1= *(ap++); | ||
151 | if ((*(rp++)=(t1+1)&BN_MASK2) >= t1) | ||
152 | { | ||
153 | carry=0; | ||
154 | break; | ||
155 | } | ||
156 | } | ||
157 | if ((i >= max) && carry) | ||
158 | { | ||
159 | *(rp++)=1; | ||
160 | r->top++; | ||
161 | } | ||
162 | } | ||
163 | for (; i<max; i++) | ||
164 | *(rp++)= *(ap++); | ||
165 | /* memcpy(rp,ap,sizeof(*ap)*(max-i));*/ | ||
166 | } | ||
167 | |||
diff --git a/src/lib/libcrypto/bn/bn_blind.c b/src/lib/libcrypto/bn/bn_blind.c new file mode 100644 index 0000000000..a7b34f0bf0 --- /dev/null +++ b/src/lib/libcrypto/bn/bn_blind.c | |||
@@ -0,0 +1,143 @@ | |||
1 | /* crypto/bn/bn_blind.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include "cryptlib.h" | ||
61 | #include "bn_lcl.h" | ||
62 | |||
63 | BN_BLINDING *BN_BLINDING_new(A,Ai,mod) | ||
64 | BIGNUM *A; | ||
65 | BIGNUM *Ai; | ||
66 | BIGNUM *mod; | ||
67 | { | ||
68 | BN_BLINDING *ret=NULL; | ||
69 | |||
70 | if ((ret=(BN_BLINDING *)Malloc(sizeof(BN_BLINDING))) == NULL) | ||
71 | BNerr(BN_F_BN_BLINDING_NEW,ERR_R_MALLOC_FAILURE); | ||
72 | memset(ret,0,sizeof(BN_BLINDING)); | ||
73 | if ((ret->A=BN_new()) == NULL) goto err; | ||
74 | if ((ret->Ai=BN_new()) == NULL) goto err; | ||
75 | if (!BN_copy(ret->A,A)) goto err; | ||
76 | if (!BN_copy(ret->Ai,Ai)) goto err; | ||
77 | ret->mod=mod; | ||
78 | return(ret); | ||
79 | err: | ||
80 | if (ret != NULL) BN_BLINDING_free(ret); | ||
81 | return(ret); | ||
82 | } | ||
83 | |||
84 | void BN_BLINDING_free(r) | ||
85 | BN_BLINDING *r; | ||
86 | { | ||
87 | if (r->A != NULL) BN_free(r->A ); | ||
88 | if (r->Ai != NULL) BN_free(r->Ai); | ||
89 | Free(r); | ||
90 | } | ||
91 | |||
92 | int BN_BLINDING_update(b,ctx) | ||
93 | BN_BLINDING *b; | ||
94 | BN_CTX *ctx; | ||
95 | { | ||
96 | int ret=0; | ||
97 | |||
98 | if ((b->A == NULL) || (b->Ai == NULL)) | ||
99 | { | ||
100 | BNerr(BN_F_BN_BLINDING_UPDATE,BN_R_NOT_INITALISED); | ||
101 | goto err; | ||
102 | } | ||
103 | |||
104 | if (!BN_mod_mul(b->A,b->A,b->A,b->mod,ctx)) goto err; | ||
105 | if (!BN_mod_mul(b->Ai,b->Ai,b->Ai,b->mod,ctx)) goto err; | ||
106 | |||
107 | ret=1; | ||
108 | err: | ||
109 | return(ret); | ||
110 | } | ||
111 | |||
112 | int BN_BLINDING_convert(n,b,ctx) | ||
113 | BIGNUM *n; | ||
114 | BN_BLINDING *b; | ||
115 | BN_CTX *ctx; | ||
116 | { | ||
117 | if ((b->A == NULL) || (b->Ai == NULL)) | ||
118 | { | ||
119 | BNerr(BN_F_BN_BLINDING_CONVERT,BN_R_NOT_INITALISED); | ||
120 | return(0); | ||
121 | } | ||
122 | return(BN_mod_mul(n,n,b->A,b->mod,ctx)); | ||
123 | } | ||
124 | |||
125 | int BN_BLINDING_invert(n,b,ctx) | ||
126 | BIGNUM *n; | ||
127 | BN_BLINDING *b; | ||
128 | BN_CTX *ctx; | ||
129 | { | ||
130 | int ret; | ||
131 | if ((b->A == NULL) || (b->Ai == NULL)) | ||
132 | { | ||
133 | BNerr(BN_F_BN_BLINDING_INVERT,BN_R_NOT_INITALISED); | ||
134 | return(0); | ||
135 | } | ||
136 | if ((ret=BN_mod_mul(n,n,b->Ai,b->mod,ctx)) >= 0) | ||
137 | { | ||
138 | if (!BN_BLINDING_update(b,ctx)) | ||
139 | return(0); | ||
140 | } | ||
141 | return(ret); | ||
142 | } | ||
143 | |||
diff --git a/src/lib/libcrypto/bn/bn_div.c b/src/lib/libcrypto/bn/bn_div.c new file mode 100644 index 0000000000..2263bdc7da --- /dev/null +++ b/src/lib/libcrypto/bn/bn_div.c | |||
@@ -0,0 +1,286 @@ | |||
1 | /* crypto/bn/bn_div.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include "cryptlib.h" | ||
61 | #include "bn_lcl.h" | ||
62 | |||
63 | /* The old slow way */ | ||
64 | #if 0 | ||
65 | int BN_div(dv, rem, m, d,ctx) | ||
66 | BIGNUM *dv; | ||
67 | BIGNUM *rem; | ||
68 | BIGNUM *m; | ||
69 | BIGNUM *d; | ||
70 | BN_CTX *ctx; | ||
71 | { | ||
72 | int i,nm,nd; | ||
73 | BIGNUM *D; | ||
74 | |||
75 | if (BN_is_zero(d)) | ||
76 | { | ||
77 | BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO); | ||
78 | return(0); | ||
79 | } | ||
80 | |||
81 | if (BN_ucmp(m,d) < 0) | ||
82 | { | ||
83 | if (rem != NULL) | ||
84 | { if (BN_copy(rem,m) == NULL) return(0); } | ||
85 | if (dv != NULL) BN_zero(dv); | ||
86 | return(1); | ||
87 | } | ||
88 | |||
89 | D=ctx->bn[ctx->tos]; | ||
90 | if (dv == NULL) dv=ctx->bn[ctx->tos+1]; | ||
91 | if (rem == NULL) rem=ctx->bn[ctx->tos+2]; | ||
92 | |||
93 | nd=BN_num_bits(d); | ||
94 | nm=BN_num_bits(m); | ||
95 | if (BN_copy(D,d) == NULL) return(0); | ||
96 | if (BN_copy(rem,m) == NULL) return(0); | ||
97 | |||
98 | /* The next 2 are needed so we can do a dv->d[0]|=1 later | ||
99 | * since BN_lshift1 will only work once there is a value :-) */ | ||
100 | BN_zero(dv); | ||
101 | dv->top=1; | ||
102 | |||
103 | if (!BN_lshift(D,D,nm-nd)) return(0); | ||
104 | for (i=nm-nd; i>=0; i--) | ||
105 | { | ||
106 | if (!BN_lshift1(dv,dv)) return(0); | ||
107 | if (BN_ucmp(rem,D) >= 0) | ||
108 | { | ||
109 | dv->d[0]|=1; | ||
110 | bn_qsub(rem,rem,D); | ||
111 | } | ||
112 | /* CAN IMPROVE (and have now :=) */ | ||
113 | if (!BN_rshift1(D,D)) return(0); | ||
114 | } | ||
115 | rem->neg=BN_is_zero(rem)?0:m->neg; | ||
116 | dv->neg=m->neg^d->neg; | ||
117 | return(1); | ||
118 | } | ||
119 | |||
120 | #else | ||
121 | |||
122 | int BN_div(dv, rm, num, divisor,ctx) | ||
123 | BIGNUM *dv; | ||
124 | BIGNUM *rm; | ||
125 | BIGNUM *num; | ||
126 | BIGNUM *divisor; | ||
127 | BN_CTX *ctx; | ||
128 | { | ||
129 | int norm_shift,i,j,loop; | ||
130 | BIGNUM *tmp,wnum,*snum,*sdiv,*res; | ||
131 | BN_ULONG *resp,*wnump; | ||
132 | BN_ULONG d0,d1; | ||
133 | int num_n,div_n; | ||
134 | |||
135 | if (BN_is_zero(divisor)) | ||
136 | { | ||
137 | BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO); | ||
138 | return(0); | ||
139 | } | ||
140 | |||
141 | if (BN_ucmp(num,divisor) < 0) | ||
142 | { | ||
143 | if (rm != NULL) | ||
144 | { if (BN_copy(rm,num) == NULL) return(0); } | ||
145 | if (dv != NULL) BN_zero(dv); | ||
146 | return(1); | ||
147 | } | ||
148 | |||
149 | tmp=ctx->bn[ctx->tos]; | ||
150 | tmp->neg=0; | ||
151 | snum=ctx->bn[ctx->tos+1]; | ||
152 | sdiv=ctx->bn[ctx->tos+2]; | ||
153 | if (dv == NULL) | ||
154 | res=ctx->bn[ctx->tos+3]; | ||
155 | else res=dv; | ||
156 | |||
157 | /* First we normalise the numbers */ | ||
158 | norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2); | ||
159 | BN_lshift(sdiv,divisor,norm_shift); | ||
160 | sdiv->neg=0; | ||
161 | norm_shift+=BN_BITS2; | ||
162 | BN_lshift(snum,num,norm_shift); | ||
163 | snum->neg=0; | ||
164 | div_n=sdiv->top; | ||
165 | num_n=snum->top; | ||
166 | loop=num_n-div_n; | ||
167 | |||
168 | /* Lets setup a 'window' into snum | ||
169 | * This is the part that corresponds to the current | ||
170 | * 'area' being divided */ | ||
171 | wnum.d= &(snum->d[loop]); | ||
172 | wnum.top= div_n; | ||
173 | wnum.max= snum->max; /* a bit of a lie */ | ||
174 | wnum.neg= 0; | ||
175 | |||
176 | /* Get the top 2 words of sdiv */ | ||
177 | /* i=sdiv->top; */ | ||
178 | d0=sdiv->d[div_n-1]; | ||
179 | d1=(div_n == 1)?0:sdiv->d[div_n-2]; | ||
180 | |||
181 | /* pointer to the 'top' of snum */ | ||
182 | wnump= &(snum->d[num_n-1]); | ||
183 | |||
184 | /* Setup to 'res' */ | ||
185 | res->neg= (num->neg^divisor->neg); | ||
186 | res->top=loop; | ||
187 | if (!bn_wexpand(res,(loop+1))) goto err; | ||
188 | resp= &(res->d[loop-1]); | ||
189 | |||
190 | /* space for temp */ | ||
191 | if (!bn_wexpand(tmp,(div_n+1))) goto err; | ||
192 | |||
193 | if (BN_ucmp(&wnum,sdiv) >= 0) | ||
194 | { | ||
195 | bn_qsub(&wnum,&wnum,sdiv); | ||
196 | *resp=1; | ||
197 | res->d[res->top-1]=1; | ||
198 | } | ||
199 | else | ||
200 | res->top--; | ||
201 | resp--; | ||
202 | |||
203 | for (i=0; i<loop-1; i++) | ||
204 | { | ||
205 | BN_ULONG q,n0,n1; | ||
206 | BN_ULONG l0; | ||
207 | |||
208 | wnum.d--; wnum.top++; | ||
209 | n0=wnump[0]; | ||
210 | n1=wnump[-1]; | ||
211 | if (n0 == d0) | ||
212 | q=BN_MASK2; | ||
213 | else | ||
214 | q=bn_div64(n0,n1,d0); | ||
215 | { | ||
216 | #ifdef BN_LLONG | ||
217 | BN_ULLONG t1,t2,rem; | ||
218 | t1=((BN_ULLONG)n0<<BN_BITS2)|n1; | ||
219 | for (;;) | ||
220 | { | ||
221 | t2=(BN_ULLONG)d1*q; | ||
222 | rem=t1-(BN_ULLONG)q*d0; | ||
223 | if ((rem>>BN_BITS2) || | ||
224 | (t2 <= ((BN_ULLONG)(rem<<BN_BITS2)+wnump[-2]))) | ||
225 | break; | ||
226 | q--; | ||
227 | } | ||
228 | #else | ||
229 | BN_ULONG t1l,t1h,t2l,t2h,t3l,t3h,ql,qh,t3t; | ||
230 | t1h=n0; | ||
231 | t1l=n1; | ||
232 | for (;;) | ||
233 | { | ||
234 | t2l=LBITS(d1); t2h=HBITS(d1); | ||
235 | ql =LBITS(q); qh =HBITS(q); | ||
236 | mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1*q; */ | ||
237 | |||
238 | t3t=LBITS(d0); t3h=HBITS(d0); | ||
239 | mul64(t3t,t3h,ql,qh); /* t3=t1-(BN_ULLONG)q*d0; */ | ||
240 | t3l=(t1l-t3t)&BN_MASK2; | ||
241 | if (t3l > t1l) t3h++; | ||
242 | t3h=(t1h-t3h)&BN_MASK2; | ||
243 | |||
244 | /*if ((t3>>BN_BITS2) || | ||
245 | (t2 <= ((t3<<BN_BITS2)+wnump[-2]))) | ||
246 | break; */ | ||
247 | if (t3h) break; | ||
248 | if (t2h < t3l) break; | ||
249 | if ((t2h == t3l) && (t2l <= wnump[-2])) break; | ||
250 | |||
251 | q--; | ||
252 | } | ||
253 | #endif | ||
254 | } | ||
255 | l0=bn_mul_words(tmp->d,sdiv->d,div_n,q); | ||
256 | tmp->d[div_n]=l0; | ||
257 | for (j=div_n+1; j>0; j--) | ||
258 | if (tmp->d[j-1]) break; | ||
259 | tmp->top=j; | ||
260 | |||
261 | j=wnum.top; | ||
262 | BN_sub(&wnum,&wnum,tmp); | ||
263 | |||
264 | snum->top=snum->top+wnum.top-j; | ||
265 | |||
266 | if (wnum.neg) | ||
267 | { | ||
268 | q--; | ||
269 | j=wnum.top; | ||
270 | BN_add(&wnum,&wnum,sdiv); | ||
271 | snum->top+=wnum.top-j; | ||
272 | } | ||
273 | *(resp--)=q; | ||
274 | wnump--; | ||
275 | } | ||
276 | if (rm != NULL) | ||
277 | { | ||
278 | BN_rshift(rm,snum,norm_shift); | ||
279 | rm->neg=num->neg; | ||
280 | } | ||
281 | return(1); | ||
282 | err: | ||
283 | return(0); | ||
284 | } | ||
285 | |||
286 | #endif | ||
diff --git a/src/lib/libcrypto/bn/bn_err.c b/src/lib/libcrypto/bn/bn_err.c new file mode 100644 index 0000000000..029ae810d5 --- /dev/null +++ b/src/lib/libcrypto/bn/bn_err.c | |||
@@ -0,0 +1,111 @@ | |||
1 | /* lib/bn/bn_err.c */ | ||
2 | /* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include <stdio.h> | ||
59 | #include "err.h" | ||
60 | #include "bn.h" | ||
61 | |||
62 | /* BEGIN ERROR CODES */ | ||
63 | #ifndef NO_ERR | ||
64 | static ERR_STRING_DATA BN_str_functs[]= | ||
65 | { | ||
66 | {ERR_PACK(0,BN_F_BN_BLINDING_CONVERT,0), "BN_BLINDING_convert"}, | ||
67 | {ERR_PACK(0,BN_F_BN_BLINDING_INVERT,0), "BN_BLINDING_invert"}, | ||
68 | {ERR_PACK(0,BN_F_BN_BLINDING_NEW,0), "BN_BLINDING_new"}, | ||
69 | {ERR_PACK(0,BN_F_BN_BLINDING_UPDATE,0), "BN_BLINDING_update"}, | ||
70 | {ERR_PACK(0,BN_F_BN_BN2DEC,0), "BN_bn2dec"}, | ||
71 | {ERR_PACK(0,BN_F_BN_BN2HEX,0), "BN_bn2hex"}, | ||
72 | {ERR_PACK(0,BN_F_BN_CTX_NEW,0), "BN_CTX_new"}, | ||
73 | {ERR_PACK(0,BN_F_BN_DIV,0), "BN_div"}, | ||
74 | {ERR_PACK(0,BN_F_BN_EXPAND2,0), "bn_expand2"}, | ||
75 | {ERR_PACK(0,BN_F_BN_MOD_EXP_MONT,0), "BN_mod_exp_mont"}, | ||
76 | {ERR_PACK(0,BN_F_BN_MOD_INVERSE,0), "BN_mod_inverse"}, | ||
77 | {ERR_PACK(0,BN_F_BN_MOD_MUL_RECIPROCAL,0), "BN_mod_mul_reciprocal"}, | ||
78 | {ERR_PACK(0,BN_F_BN_MPI2BN,0), "BN_mpi2bn"}, | ||
79 | {ERR_PACK(0,BN_F_BN_NEW,0), "BN_new"}, | ||
80 | {ERR_PACK(0,BN_F_BN_RAND,0), "BN_rand"}, | ||
81 | {0,NULL}, | ||
82 | }; | ||
83 | |||
84 | static ERR_STRING_DATA BN_str_reasons[]= | ||
85 | { | ||
86 | {BN_R_BAD_RECIPROCAL ,"bad reciprocal"}, | ||
87 | {BN_R_CALLED_WITH_EVEN_MODULUS ,"called with even modulus"}, | ||
88 | {BN_R_DIV_BY_ZERO ,"div by zero"}, | ||
89 | {BN_R_ENCODING_ERROR ,"encoding error"}, | ||
90 | {BN_R_INVALID_LENGTH ,"invalid length"}, | ||
91 | {BN_R_NOT_INITALISED ,"not initalised"}, | ||
92 | {BN_R_NO_INVERSE ,"no inverse"}, | ||
93 | {0,NULL}, | ||
94 | }; | ||
95 | |||
96 | #endif | ||
97 | |||
98 | void ERR_load_BN_strings() | ||
99 | { | ||
100 | static int init=1; | ||
101 | |||
102 | if (init); | ||
103 | {; | ||
104 | init=0; | ||
105 | #ifndef NO_ERR | ||
106 | ERR_load_strings(ERR_LIB_BN,BN_str_functs); | ||
107 | ERR_load_strings(ERR_LIB_BN,BN_str_reasons); | ||
108 | #endif | ||
109 | |||
110 | } | ||
111 | } | ||
diff --git a/src/lib/libcrypto/bn/bn_exp.c b/src/lib/libcrypto/bn/bn_exp.c new file mode 100644 index 0000000000..c056a5083f --- /dev/null +++ b/src/lib/libcrypto/bn/bn_exp.c | |||
@@ -0,0 +1,553 @@ | |||
1 | /* crypto/bn/bn_exp.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include "cryptlib.h" | ||
61 | #include "bn_lcl.h" | ||
62 | |||
63 | /* slow but works */ | ||
64 | int BN_mod_mul(ret, a, b, m, ctx) | ||
65 | BIGNUM *ret; | ||
66 | BIGNUM *a; | ||
67 | BIGNUM *b; | ||
68 | BIGNUM *m; | ||
69 | BN_CTX *ctx; | ||
70 | { | ||
71 | BIGNUM *t; | ||
72 | int r=0; | ||
73 | |||
74 | t=ctx->bn[ctx->tos++]; | ||
75 | if (a == b) | ||
76 | { if (!BN_sqr(t,a,ctx)) goto err; } | ||
77 | else | ||
78 | { if (!BN_mul(t,a,b)) goto err; } | ||
79 | if (!BN_mod(ret,t,m,ctx)) goto err; | ||
80 | r=1; | ||
81 | err: | ||
82 | ctx->tos--; | ||
83 | return(r); | ||
84 | } | ||
85 | |||
86 | #if 0 | ||
87 | /* this one works - simple but works */ | ||
88 | int BN_mod_exp(r,a,p,m,ctx) | ||
89 | BIGNUM *r,*a,*p,*m; | ||
90 | BN_CTX *ctx; | ||
91 | { | ||
92 | int i,bits,ret=0; | ||
93 | BIGNUM *v,*tmp; | ||
94 | |||
95 | v=ctx->bn[ctx->tos++]; | ||
96 | tmp=ctx->bn[ctx->tos++]; | ||
97 | |||
98 | if (BN_copy(v,a) == NULL) goto err; | ||
99 | bits=BN_num_bits(p); | ||
100 | |||
101 | if (BN_is_odd(p)) | ||
102 | { if (BN_copy(r,a) == NULL) goto err; } | ||
103 | else { if (BN_one(r)) goto err; } | ||
104 | |||
105 | for (i=1; i<bits; i++) | ||
106 | { | ||
107 | if (!BN_sqr(tmp,v,ctx)) goto err; | ||
108 | if (!BN_mod(v,tmp,m,ctx)) goto err; | ||
109 | if (BN_is_bit_set(p,i)) | ||
110 | { | ||
111 | if (!BN_mul(tmp,r,v)) goto err; | ||
112 | if (!BN_mod(r,tmp,m,ctx)) goto err; | ||
113 | } | ||
114 | } | ||
115 | ret=1; | ||
116 | err: | ||
117 | ctx->tos-=2; | ||
118 | return(ret); | ||
119 | } | ||
120 | |||
121 | #endif | ||
122 | |||
123 | /* this one works - simple but works */ | ||
124 | int BN_exp(r,a,p,ctx) | ||
125 | BIGNUM *r,*a,*p; | ||
126 | BN_CTX *ctx; | ||
127 | { | ||
128 | int i,bits,ret=0; | ||
129 | BIGNUM *v,*tmp; | ||
130 | |||
131 | v=ctx->bn[ctx->tos++]; | ||
132 | tmp=ctx->bn[ctx->tos++]; | ||
133 | |||
134 | if (BN_copy(v,a) == NULL) goto err; | ||
135 | bits=BN_num_bits(p); | ||
136 | |||
137 | if (BN_is_odd(p)) | ||
138 | { if (BN_copy(r,a) == NULL) goto err; } | ||
139 | else { if (BN_one(r)) goto err; } | ||
140 | |||
141 | for (i=1; i<bits; i++) | ||
142 | { | ||
143 | if (!BN_sqr(tmp,v,ctx)) goto err; | ||
144 | if (BN_is_bit_set(p,i)) | ||
145 | { | ||
146 | if (!BN_mul(tmp,r,v)) goto err; | ||
147 | } | ||
148 | } | ||
149 | ret=1; | ||
150 | err: | ||
151 | ctx->tos-=2; | ||
152 | return(ret); | ||
153 | } | ||
154 | |||
155 | int BN_mod_exp(r,a,p,m,ctx) | ||
156 | BIGNUM *r; | ||
157 | BIGNUM *a; | ||
158 | BIGNUM *p; | ||
159 | BIGNUM *m; | ||
160 | BN_CTX *ctx; | ||
161 | { | ||
162 | int ret; | ||
163 | |||
164 | #ifdef MONT_MUL_MOD | ||
165 | /* I have finally been able to take out this pre-condition of | ||
166 | * the top bit being set. It was caused by an error in BN_div | ||
167 | * with negatives. There was also another problem when for a^b%m | ||
168 | * a >= m. eay 07-May-97 */ | ||
169 | /* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */ | ||
170 | |||
171 | if (BN_is_odd(m)) | ||
172 | { ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); } | ||
173 | else | ||
174 | #endif | ||
175 | #ifdef RECP_MUL_MOD | ||
176 | { ret=BN_mod_exp_recp(r,a,p,m,ctx); } | ||
177 | #else | ||
178 | { ret=BN_mod_exp_simple(r,a,p,m,ctx); } | ||
179 | #endif | ||
180 | |||
181 | return(ret); | ||
182 | } | ||
183 | |||
184 | /* #ifdef RECP_MUL_MOD */ | ||
185 | int BN_mod_exp_recp(r,a,p,m,ctx) | ||
186 | BIGNUM *r; | ||
187 | BIGNUM *a; | ||
188 | BIGNUM *p; | ||
189 | BIGNUM *m; | ||
190 | BN_CTX *ctx; | ||
191 | { | ||
192 | int nb,i,j,bits,ret=0,wstart,wend,window,wvalue; | ||
193 | int start=1; | ||
194 | BIGNUM *d,*aa; | ||
195 | BIGNUM *val[16]; | ||
196 | |||
197 | d=ctx->bn[ctx->tos++]; | ||
198 | aa=ctx->bn[ctx->tos++]; | ||
199 | bits=BN_num_bits(p); | ||
200 | |||
201 | if (bits == 0) | ||
202 | { | ||
203 | BN_one(r); | ||
204 | return(1); | ||
205 | } | ||
206 | nb=BN_reciprocal(d,m,ctx); | ||
207 | if (nb == -1) goto err; | ||
208 | |||
209 | val[0]=BN_new(); | ||
210 | if (!BN_mod(val[0],a,m,ctx)) goto err; /* 1 */ | ||
211 | if (!BN_mod_mul_reciprocal(aa,val[0],val[0],m,d,nb,ctx)) | ||
212 | goto err; /* 2 */ | ||
213 | |||
214 | if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */ | ||
215 | window=1; | ||
216 | else if (bits >= 256) | ||
217 | window=5; /* max size of window */ | ||
218 | else if (bits >= 128) | ||
219 | window=4; | ||
220 | else | ||
221 | window=3; | ||
222 | |||
223 | j=1<<(window-1); | ||
224 | for (i=1; i<j; i++) | ||
225 | { | ||
226 | val[i]=BN_new(); | ||
227 | if (!BN_mod_mul_reciprocal(val[i],val[i-1],aa,m,d,nb,ctx)) | ||
228 | goto err; | ||
229 | } | ||
230 | for (; i<16; i++) | ||
231 | val[i]=NULL; | ||
232 | |||
233 | start=1; /* This is used to avoid multiplication etc | ||
234 | * when there is only the value '1' in the | ||
235 | * buffer. */ | ||
236 | wvalue=0; /* The 'value' of the window */ | ||
237 | wstart=bits-1; /* The top bit of the window */ | ||
238 | wend=0; /* The bottom bit of the window */ | ||
239 | |||
240 | if (!BN_one(r)) goto err; | ||
241 | |||
242 | for (;;) | ||
243 | { | ||
244 | if (BN_is_bit_set(p,wstart) == 0) | ||
245 | { | ||
246 | if (!start) | ||
247 | if (!BN_mod_mul_reciprocal(r,r,r,m,d,nb,ctx)) | ||
248 | goto err; | ||
249 | if (wstart == 0) break; | ||
250 | wstart--; | ||
251 | continue; | ||
252 | } | ||
253 | /* We now have wstart on a 'set' bit, we now need to work out | ||
254 | * how bit a window to do. To do this we need to scan | ||
255 | * forward until the last set bit before the end of the | ||
256 | * window */ | ||
257 | j=wstart; | ||
258 | wvalue=1; | ||
259 | wend=0; | ||
260 | for (i=1; i<window; i++) | ||
261 | { | ||
262 | if (wstart-i < 0) break; | ||
263 | if (BN_is_bit_set(p,wstart-i)) | ||
264 | { | ||
265 | wvalue<<=(i-wend); | ||
266 | wvalue|=1; | ||
267 | wend=i; | ||
268 | } | ||
269 | } | ||
270 | |||
271 | /* wend is the size of the current window */ | ||
272 | j=wend+1; | ||
273 | /* add the 'bytes above' */ | ||
274 | if (!start) | ||
275 | for (i=0; i<j; i++) | ||
276 | { | ||
277 | if (!BN_mod_mul_reciprocal(r,r,r,m,d,nb,ctx)) | ||
278 | goto err; | ||
279 | } | ||
280 | |||
281 | /* wvalue will be an odd number < 2^window */ | ||
282 | if (!BN_mod_mul_reciprocal(r,r,val[wvalue>>1],m,d,nb,ctx)) | ||
283 | goto err; | ||
284 | |||
285 | /* move the 'window' down further */ | ||
286 | wstart-=wend+1; | ||
287 | wvalue=0; | ||
288 | start=0; | ||
289 | if (wstart < 0) break; | ||
290 | } | ||
291 | ret=1; | ||
292 | err: | ||
293 | ctx->tos-=2; | ||
294 | for (i=0; i<16; i++) | ||
295 | if (val[i] != NULL) BN_clear_free(val[i]); | ||
296 | return(ret); | ||
297 | } | ||
298 | /* #endif */ | ||
299 | |||
300 | /* #ifdef MONT_MUL_MOD */ | ||
301 | int BN_mod_exp_mont(r,a,p,m,ctx,in_mont) | ||
302 | BIGNUM *r; | ||
303 | BIGNUM *a; | ||
304 | BIGNUM *p; | ||
305 | BIGNUM *m; | ||
306 | BN_CTX *ctx; | ||
307 | BN_MONT_CTX *in_mont; | ||
308 | { | ||
309 | #define TABLE_SIZE 16 | ||
310 | int i,j,bits,ret=0,wstart,wend,window,wvalue; | ||
311 | int start=1; | ||
312 | BIGNUM *d,*aa; | ||
313 | BIGNUM *val[TABLE_SIZE]; | ||
314 | BN_MONT_CTX *mont=NULL; | ||
315 | |||
316 | if (!(m->d[0] & 1)) | ||
317 | { | ||
318 | BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS); | ||
319 | return(0); | ||
320 | } | ||
321 | d=ctx->bn[ctx->tos++]; | ||
322 | bits=BN_num_bits(p); | ||
323 | if (bits == 0) | ||
324 | { | ||
325 | BN_one(r); | ||
326 | return(1); | ||
327 | } | ||
328 | |||
329 | /* If this is not done, things will break in the montgomery | ||
330 | * part */ | ||
331 | |||
332 | #if 1 | ||
333 | if (in_mont != NULL) | ||
334 | mont=in_mont; | ||
335 | else | ||
336 | #endif | ||
337 | { | ||
338 | if ((mont=BN_MONT_CTX_new()) == NULL) goto err; | ||
339 | if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; | ||
340 | } | ||
341 | |||
342 | val[0]=BN_new(); | ||
343 | if (BN_ucmp(a,m) >= 0) | ||
344 | { | ||
345 | BN_mod(val[0],a,m,ctx); | ||
346 | aa=val[0]; | ||
347 | } | ||
348 | else | ||
349 | aa=a; | ||
350 | if (!BN_to_montgomery(val[0],aa,mont,ctx)) goto err; /* 1 */ | ||
351 | if (!BN_mod_mul_montgomery(d,val[0],val[0],mont,ctx)) goto err; /* 2 */ | ||
352 | |||
353 | if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */ | ||
354 | window=1; | ||
355 | else if (bits > 250) | ||
356 | window=5; /* max size of window */ | ||
357 | else if (bits >= 120) | ||
358 | window=4; | ||
359 | else | ||
360 | window=3; | ||
361 | |||
362 | j=1<<(window-1); | ||
363 | for (i=1; i<j; i++) | ||
364 | { | ||
365 | val[i]=BN_new(); | ||
366 | if (!BN_mod_mul_montgomery(val[i],val[i-1],d,mont,ctx)) | ||
367 | goto err; | ||
368 | } | ||
369 | for (; i<TABLE_SIZE; i++) | ||
370 | val[i]=NULL; | ||
371 | |||
372 | start=1; /* This is used to avoid multiplication etc | ||
373 | * when there is only the value '1' in the | ||
374 | * buffer. */ | ||
375 | wvalue=0; /* The 'value' of the window */ | ||
376 | wstart=bits-1; /* The top bit of the window */ | ||
377 | wend=0; /* The bottom bit of the window */ | ||
378 | |||
379 | if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err; | ||
380 | for (;;) | ||
381 | { | ||
382 | if (BN_is_bit_set(p,wstart) == 0) | ||
383 | { | ||
384 | if (!start) | ||
385 | { | ||
386 | if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) | ||
387 | goto err; | ||
388 | } | ||
389 | if (wstart == 0) break; | ||
390 | wstart--; | ||
391 | continue; | ||
392 | } | ||
393 | /* We now have wstart on a 'set' bit, we now need to work out | ||
394 | * how bit a window to do. To do this we need to scan | ||
395 | * forward until the last set bit before the end of the | ||
396 | * window */ | ||
397 | j=wstart; | ||
398 | wvalue=1; | ||
399 | wend=0; | ||
400 | for (i=1; i<window; i++) | ||
401 | { | ||
402 | if (wstart-i < 0) break; | ||
403 | if (BN_is_bit_set(p,wstart-i)) | ||
404 | { | ||
405 | wvalue<<=(i-wend); | ||
406 | wvalue|=1; | ||
407 | wend=i; | ||
408 | } | ||
409 | } | ||
410 | |||
411 | /* wend is the size of the current window */ | ||
412 | j=wend+1; | ||
413 | /* add the 'bytes above' */ | ||
414 | if (!start) | ||
415 | for (i=0; i<j; i++) | ||
416 | { | ||
417 | if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) | ||
418 | goto err; | ||
419 | } | ||
420 | |||
421 | /* wvalue will be an odd number < 2^window */ | ||
422 | if (!BN_mod_mul_montgomery(r,r,val[wvalue>>1],mont,ctx)) | ||
423 | goto err; | ||
424 | |||
425 | /* move the 'window' down further */ | ||
426 | wstart-=wend+1; | ||
427 | wvalue=0; | ||
428 | start=0; | ||
429 | if (wstart < 0) break; | ||
430 | } | ||
431 | BN_from_montgomery(r,r,mont,ctx); | ||
432 | ret=1; | ||
433 | err: | ||
434 | if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); | ||
435 | ctx->tos--; | ||
436 | for (i=0; i<TABLE_SIZE; i++) | ||
437 | if (val[i] != NULL) BN_clear_free(val[i]); | ||
438 | return(ret); | ||
439 | } | ||
440 | /* #endif */ | ||
441 | |||
442 | /* The old fallback, simple version :-) */ | ||
443 | int BN_mod_exp_simple(r,a,p,m,ctx) | ||
444 | BIGNUM *r; | ||
445 | BIGNUM *a; | ||
446 | BIGNUM *p; | ||
447 | BIGNUM *m; | ||
448 | BN_CTX *ctx; | ||
449 | { | ||
450 | int i,j,bits,ret=0,wstart,wend,window,wvalue; | ||
451 | int start=1; | ||
452 | BIGNUM *d; | ||
453 | BIGNUM *val[16]; | ||
454 | |||
455 | d=ctx->bn[ctx->tos++]; | ||
456 | bits=BN_num_bits(p); | ||
457 | |||
458 | if (bits == 0) | ||
459 | { | ||
460 | BN_one(r); | ||
461 | return(1); | ||
462 | } | ||
463 | |||
464 | val[0]=BN_new(); | ||
465 | if (!BN_mod(val[0],a,m,ctx)) goto err; /* 1 */ | ||
466 | if (!BN_mod_mul(d,val[0],val[0],m,ctx)) | ||
467 | goto err; /* 2 */ | ||
468 | |||
469 | if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */ | ||
470 | window=1; | ||
471 | else if (bits >= 256) | ||
472 | window=5; /* max size of window */ | ||
473 | else if (bits >= 128) | ||
474 | window=4; | ||
475 | else | ||
476 | window=3; | ||
477 | |||
478 | j=1<<(window-1); | ||
479 | for (i=1; i<j; i++) | ||
480 | { | ||
481 | val[i]=BN_new(); | ||
482 | if (!BN_mod_mul(val[i],val[i-1],d,m,ctx)) | ||
483 | goto err; | ||
484 | } | ||
485 | for (; i<16; i++) | ||
486 | val[i]=NULL; | ||
487 | |||
488 | start=1; /* This is used to avoid multiplication etc | ||
489 | * when there is only the value '1' in the | ||
490 | * buffer. */ | ||
491 | wvalue=0; /* The 'value' of the window */ | ||
492 | wstart=bits-1; /* The top bit of the window */ | ||
493 | wend=0; /* The bottom bit of the window */ | ||
494 | |||
495 | if (!BN_one(r)) goto err; | ||
496 | |||
497 | for (;;) | ||
498 | { | ||
499 | if (BN_is_bit_set(p,wstart) == 0) | ||
500 | { | ||
501 | if (!start) | ||
502 | if (!BN_mod_mul(r,r,r,m,ctx)) | ||
503 | goto err; | ||
504 | if (wstart == 0) break; | ||
505 | wstart--; | ||
506 | continue; | ||
507 | } | ||
508 | /* We now have wstart on a 'set' bit, we now need to work out | ||
509 | * how bit a window to do. To do this we need to scan | ||
510 | * forward until the last set bit before the end of the | ||
511 | * window */ | ||
512 | j=wstart; | ||
513 | wvalue=1; | ||
514 | wend=0; | ||
515 | for (i=1; i<window; i++) | ||
516 | { | ||
517 | if (wstart-i < 0) break; | ||
518 | if (BN_is_bit_set(p,wstart-i)) | ||
519 | { | ||
520 | wvalue<<=(i-wend); | ||
521 | wvalue|=1; | ||
522 | wend=i; | ||
523 | } | ||
524 | } | ||
525 | |||
526 | /* wend is the size of the current window */ | ||
527 | j=wend+1; | ||
528 | /* add the 'bytes above' */ | ||
529 | if (!start) | ||
530 | for (i=0; i<j; i++) | ||
531 | { | ||
532 | if (!BN_mod_mul(r,r,r,m,ctx)) | ||
533 | goto err; | ||
534 | } | ||
535 | |||
536 | /* wvalue will be an odd number < 2^window */ | ||
537 | if (!BN_mod_mul(r,r,val[wvalue>>1],m,ctx)) | ||
538 | goto err; | ||
539 | |||
540 | /* move the 'window' down further */ | ||
541 | wstart-=wend+1; | ||
542 | wvalue=0; | ||
543 | start=0; | ||
544 | if (wstart < 0) break; | ||
545 | } | ||
546 | ret=1; | ||
547 | err: | ||
548 | ctx->tos--; | ||
549 | for (i=0; i<16; i++) | ||
550 | if (val[i] != NULL) BN_clear_free(val[i]); | ||
551 | return(ret); | ||
552 | } | ||
553 | |||
diff --git a/src/lib/libcrypto/bn/bn_gcd.c b/src/lib/libcrypto/bn/bn_gcd.c new file mode 100644 index 0000000000..071bba3b4b --- /dev/null +++ b/src/lib/libcrypto/bn/bn_gcd.c | |||
@@ -0,0 +1,203 @@ | |||
1 | /* crypto/bn/bn_gcd.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include "cryptlib.h" | ||
61 | #include "bn_lcl.h" | ||
62 | |||
63 | #ifndef NOPROTO | ||
64 | static BIGNUM *euclid(BIGNUM *a, BIGNUM *b); | ||
65 | #else | ||
66 | static BIGNUM *euclid(); | ||
67 | #endif | ||
68 | |||
69 | int BN_gcd(r,in_a,in_b,ctx) | ||
70 | BIGNUM *r,*in_a,*in_b; | ||
71 | BN_CTX *ctx; | ||
72 | { | ||
73 | BIGNUM *a,*b,*t; | ||
74 | int ret=0; | ||
75 | |||
76 | a=ctx->bn[ctx->tos]; | ||
77 | b=ctx->bn[ctx->tos+1]; | ||
78 | |||
79 | if (BN_copy(a,in_a) == NULL) goto err; | ||
80 | if (BN_copy(b,in_b) == NULL) goto err; | ||
81 | |||
82 | if (BN_cmp(a,b) < 0) { t=a; a=b; b=t; } | ||
83 | t=euclid(a,b); | ||
84 | if (t == NULL) goto err; | ||
85 | |||
86 | if (BN_copy(r,t) == NULL) goto err; | ||
87 | ret=1; | ||
88 | err: | ||
89 | return(ret); | ||
90 | } | ||
91 | |||
92 | static BIGNUM *euclid(a,b) | ||
93 | BIGNUM *a,*b; | ||
94 | { | ||
95 | BIGNUM *t; | ||
96 | int shifts=0; | ||
97 | |||
98 | for (;;) | ||
99 | { | ||
100 | if (BN_is_zero(b)) | ||
101 | break; | ||
102 | |||
103 | if (BN_is_odd(a)) | ||
104 | { | ||
105 | if (BN_is_odd(b)) | ||
106 | { | ||
107 | if (!BN_sub(a,a,b)) goto err; | ||
108 | if (!BN_rshift1(a,a)) goto err; | ||
109 | if (BN_cmp(a,b) < 0) | ||
110 | { t=a; a=b; b=t; } | ||
111 | } | ||
112 | else /* a odd - b even */ | ||
113 | { | ||
114 | if (!BN_rshift1(b,b)) goto err; | ||
115 | if (BN_cmp(a,b) < 0) | ||
116 | { t=a; a=b; b=t; } | ||
117 | } | ||
118 | } | ||
119 | else /* a is even */ | ||
120 | { | ||
121 | if (BN_is_odd(b)) | ||
122 | { | ||
123 | if (!BN_rshift1(a,a)) goto err; | ||
124 | if (BN_cmp(a,b) < 0) | ||
125 | { t=a; a=b; b=t; } | ||
126 | } | ||
127 | else /* a even - b even */ | ||
128 | { | ||
129 | if (!BN_rshift1(a,a)) goto err; | ||
130 | if (!BN_rshift1(b,b)) goto err; | ||
131 | shifts++; | ||
132 | } | ||
133 | } | ||
134 | } | ||
135 | if (shifts) | ||
136 | { | ||
137 | if (!BN_lshift(a,a,shifts)) goto err; | ||
138 | } | ||
139 | return(a); | ||
140 | err: | ||
141 | return(NULL); | ||
142 | } | ||
143 | |||
144 | /* solves ax == 1 (mod n) */ | ||
145 | BIGNUM *BN_mod_inverse(a, n, ctx) | ||
146 | BIGNUM *a; | ||
147 | BIGNUM *n; | ||
148 | BN_CTX *ctx; | ||
149 | { | ||
150 | BIGNUM *A,*B,*X,*Y,*M,*D,*R; | ||
151 | BIGNUM *ret=NULL,*T; | ||
152 | int sign; | ||
153 | |||
154 | A=ctx->bn[ctx->tos]; | ||
155 | B=ctx->bn[ctx->tos+1]; | ||
156 | X=ctx->bn[ctx->tos+2]; | ||
157 | D=ctx->bn[ctx->tos+3]; | ||
158 | M=ctx->bn[ctx->tos+4]; | ||
159 | Y=ctx->bn[ctx->tos+5]; | ||
160 | ctx->tos+=6; | ||
161 | R=BN_new(); | ||
162 | if (R == NULL) goto err; | ||
163 | |||
164 | BN_zero(X); | ||
165 | BN_one(Y); | ||
166 | if (BN_copy(A,a) == NULL) goto err; | ||
167 | if (BN_copy(B,n) == NULL) goto err; | ||
168 | sign=1; | ||
169 | |||
170 | while (!BN_is_zero(B)) | ||
171 | { | ||
172 | if (!BN_div(D,M,A,B,ctx)) goto err; | ||
173 | T=A; | ||
174 | A=B; | ||
175 | B=M; | ||
176 | /* T has a struct, M does not */ | ||
177 | |||
178 | if (!BN_mul(T,D,X)) goto err; | ||
179 | if (!BN_add(T,T,Y)) goto err; | ||
180 | M=Y; | ||
181 | Y=X; | ||
182 | X=T; | ||
183 | sign= -sign; | ||
184 | } | ||
185 | if (sign < 0) | ||
186 | { | ||
187 | if (!BN_sub(Y,n,Y)) goto err; | ||
188 | } | ||
189 | |||
190 | if (BN_is_one(A)) | ||
191 | { if (!BN_mod(R,Y,n,ctx)) goto err; } | ||
192 | else | ||
193 | { | ||
194 | BNerr(BN_F_BN_MOD_INVERSE,BN_R_NO_INVERSE); | ||
195 | goto err; | ||
196 | } | ||
197 | ret=R; | ||
198 | err: | ||
199 | if ((ret == NULL) && (R != NULL)) BN_free(R); | ||
200 | ctx->tos-=6; | ||
201 | return(ret); | ||
202 | } | ||
203 | |||
diff --git a/src/lib/libcrypto/bn/bn_lcl.h b/src/lib/libcrypto/bn/bn_lcl.h new file mode 100644 index 0000000000..edfd788338 --- /dev/null +++ b/src/lib/libcrypto/bn/bn_lcl.h | |||
@@ -0,0 +1,199 @@ | |||
1 | /* crypto/bn/bn_lcl.h */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #ifndef HEADER_BN_LCL_H | ||
60 | #define HEADER_BN_LCL_H | ||
61 | |||
62 | #include "bn.h" | ||
63 | |||
64 | #ifdef __cplusplus | ||
65 | extern "C" { | ||
66 | #endif | ||
67 | |||
68 | /************************************************************* | ||
69 | * Using the long long type | ||
70 | */ | ||
71 | #define Lw(t) (((BN_ULONG)(t))&BN_MASK2) | ||
72 | #define Hw(t) (((BN_ULONG)((t)>>BN_BITS2))&BN_MASK2) | ||
73 | |||
74 | #define bn_fix_top(a) \ | ||
75 | { \ | ||
76 | BN_ULONG *fix_top_l; \ | ||
77 | for (fix_top_l= &((a)->d[(a)->top-1]); (a)->top > 0; (a)->top--) \ | ||
78 | if (*(fix_top_l--)) break; \ | ||
79 | } | ||
80 | |||
81 | /* #define bn_expand(n,b) ((((b)/BN_BITS2) <= (n)->max)?(n):bn_expand2((n),(b))) */ | ||
82 | |||
83 | #ifdef BN_LLONG | ||
84 | #define mul_add(r,a,w,c) { \ | ||
85 | BN_ULLONG t; \ | ||
86 | t=(BN_ULLONG)w * (a) + (r) + (c); \ | ||
87 | (r)= Lw(t); \ | ||
88 | (c)= Hw(t); \ | ||
89 | } | ||
90 | |||
91 | #define mul(r,a,w,c) { \ | ||
92 | BN_ULLONG t; \ | ||
93 | t=(BN_ULLONG)w * (a) + (c); \ | ||
94 | (r)= Lw(t); \ | ||
95 | (c)= Hw(t); \ | ||
96 | } | ||
97 | |||
98 | #else | ||
99 | /************************************************************* | ||
100 | * No long long type | ||
101 | */ | ||
102 | |||
103 | #define LBITS(a) ((a)&BN_MASK2l) | ||
104 | #define HBITS(a) (((a)>>BN_BITS4)&BN_MASK2l) | ||
105 | #define L2HBITS(a) ((BN_ULONG)((a)&BN_MASK2l)<<BN_BITS4) | ||
106 | |||
107 | #define LLBITS(a) ((a)&BN_MASKl) | ||
108 | #define LHBITS(a) (((a)>>BN_BITS2)&BN_MASKl) | ||
109 | #define LL2HBITS(a) ((BN_ULLONG)((a)&BN_MASKl)<<BN_BITS2) | ||
110 | |||
111 | #define mul64(l,h,bl,bh) \ | ||
112 | { \ | ||
113 | BN_ULONG m,m1,lt,ht; \ | ||
114 | \ | ||
115 | lt=l; \ | ||
116 | ht=h; \ | ||
117 | m =(bh)*(lt); \ | ||
118 | lt=(bl)*(lt); \ | ||
119 | m1=(bl)*(ht); \ | ||
120 | ht =(bh)*(ht); \ | ||
121 | m=(m+m1)&BN_MASK2; if (m < m1) ht+=L2HBITS(1L); \ | ||
122 | ht+=HBITS(m); \ | ||
123 | m1=L2HBITS(m); \ | ||
124 | lt=(lt+m1)&BN_MASK2; if (lt < m1) ht++; \ | ||
125 | (l)=lt; \ | ||
126 | (h)=ht; \ | ||
127 | } | ||
128 | |||
129 | #define sqr64(lo,ho,in) \ | ||
130 | { \ | ||
131 | BN_ULONG l,h,m; \ | ||
132 | \ | ||
133 | h=(in); \ | ||
134 | l=LBITS(h); \ | ||
135 | h=HBITS(h); \ | ||
136 | m =(l)*(h); \ | ||
137 | l*=l; \ | ||
138 | h*=h; \ | ||
139 | h+=(m&BN_MASK2h1)>>(BN_BITS4-1); \ | ||
140 | m =(m&BN_MASK2l)<<(BN_BITS4+1); \ | ||
141 | l=(l+m)&BN_MASK2; if (l < m) h++; \ | ||
142 | (lo)=l; \ | ||
143 | (ho)=h; \ | ||
144 | } | ||
145 | |||
146 | #define mul_add(r,a,bl,bh,c) { \ | ||
147 | BN_ULONG l,h; \ | ||
148 | \ | ||
149 | h= (a); \ | ||
150 | l=LBITS(h); \ | ||
151 | h=HBITS(h); \ | ||
152 | mul64(l,h,(bl),(bh)); \ | ||
153 | \ | ||
154 | /* non-multiply part */ \ | ||
155 | l=(l+(c))&BN_MASK2; if (l < (c)) h++; \ | ||
156 | (c)=(r); \ | ||
157 | l=(l+(c))&BN_MASK2; if (l < (c)) h++; \ | ||
158 | (c)=h&BN_MASK2; \ | ||
159 | (r)=l; \ | ||
160 | } | ||
161 | |||
162 | #define mul(r,a,bl,bh,c) { \ | ||
163 | BN_ULONG l,h; \ | ||
164 | \ | ||
165 | h= (a); \ | ||
166 | l=LBITS(h); \ | ||
167 | h=HBITS(h); \ | ||
168 | mul64(l,h,(bl),(bh)); \ | ||
169 | \ | ||
170 | /* non-multiply part */ \ | ||
171 | l+=(c); if ((l&BN_MASK2) < (c)) h++; \ | ||
172 | (c)=h&BN_MASK2; \ | ||
173 | (r)=l&BN_MASK2; \ | ||
174 | } | ||
175 | |||
176 | #endif | ||
177 | |||
178 | #ifndef NOPROTO | ||
179 | |||
180 | BIGNUM *bn_expand2(BIGNUM *b, int bits); | ||
181 | |||
182 | #ifdef X86_ASM | ||
183 | void bn_add_words(BN_ULONG *r,BN_ULONG *a,int num); | ||
184 | #endif | ||
185 | |||
186 | #else | ||
187 | |||
188 | BIGNUM *bn_expand2(); | ||
189 | #ifdef X86_ASM | ||
190 | BN_ULONG bn_add_words(); | ||
191 | #endif | ||
192 | |||
193 | #endif | ||
194 | |||
195 | #ifdef __cplusplus | ||
196 | } | ||
197 | #endif | ||
198 | |||
199 | #endif | ||
diff --git a/src/lib/libcrypto/bn/bn_lib.c b/src/lib/libcrypto/bn/bn_lib.c new file mode 100644 index 0000000000..bfe7628ad4 --- /dev/null +++ b/src/lib/libcrypto/bn/bn_lib.c | |||
@@ -0,0 +1,611 @@ | |||
1 | /* crypto/bn/bn_lib.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include "cryptlib.h" | ||
61 | #include "bn_lcl.h" | ||
62 | |||
63 | char *BN_version="Big Number part of SSLeay 0.9.0b 29-Jun-1998"; | ||
64 | |||
65 | BIGNUM *BN_value_one() | ||
66 | { | ||
67 | static BN_ULONG data_one=1L; | ||
68 | static BIGNUM const_one={&data_one,1,1,0}; | ||
69 | |||
70 | return(&const_one); | ||
71 | } | ||
72 | |||
73 | char *BN_options() | ||
74 | { | ||
75 | static int init=0; | ||
76 | static char data[16]; | ||
77 | |||
78 | if (!init) | ||
79 | { | ||
80 | init++; | ||
81 | #ifdef BN_LLONG | ||
82 | sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULLONG)*8, | ||
83 | (int)sizeof(BN_ULONG)*8); | ||
84 | #else | ||
85 | sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULONG)*8, | ||
86 | (int)sizeof(BN_ULONG)*8); | ||
87 | #endif | ||
88 | } | ||
89 | return(data); | ||
90 | } | ||
91 | |||
92 | int BN_num_bits_word(l) | ||
93 | BN_ULONG l; | ||
94 | { | ||
95 | static char bits[256]={ | ||
96 | 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4, | ||
97 | 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, | ||
98 | 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, | ||
99 | 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, | ||
100 | 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, | ||
101 | 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, | ||
102 | 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, | ||
103 | 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, | ||
104 | 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, | ||
105 | 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, | ||
106 | 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, | ||
107 | 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, | ||
108 | 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, | ||
109 | 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, | ||
110 | 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, | ||
111 | 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, | ||
112 | }; | ||
113 | |||
114 | #ifdef SIXTY_FOUR_BIT_LONG | ||
115 | if (l & 0xffffffff00000000L) | ||
116 | { | ||
117 | if (l & 0xffff000000000000L) | ||
118 | { | ||
119 | if (l & 0xff00000000000000L) | ||
120 | { | ||
121 | return(bits[l>>56]+56); | ||
122 | } | ||
123 | else return(bits[l>>48]+48); | ||
124 | } | ||
125 | else | ||
126 | { | ||
127 | if (l & 0x0000ff0000000000L) | ||
128 | { | ||
129 | return(bits[l>>40]+40); | ||
130 | } | ||
131 | else return(bits[l>>32]+32); | ||
132 | } | ||
133 | } | ||
134 | else | ||
135 | #else | ||
136 | #ifdef SIXTY_FOUR_BIT | ||
137 | if (l & 0xffffffff00000000LL) | ||
138 | { | ||
139 | if (l & 0xffff000000000000LL) | ||
140 | { | ||
141 | if (l & 0xff00000000000000LL) | ||
142 | { | ||
143 | return(bits[l>>56]+56); | ||
144 | } | ||
145 | else return(bits[l>>48]+48); | ||
146 | } | ||
147 | else | ||
148 | { | ||
149 | if (l & 0x0000ff0000000000LL) | ||
150 | { | ||
151 | return(bits[l>>40]+40); | ||
152 | } | ||
153 | else return(bits[l>>32]+32); | ||
154 | } | ||
155 | } | ||
156 | else | ||
157 | #endif | ||
158 | #endif | ||
159 | { | ||
160 | #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) | ||
161 | if (l & 0xffff0000L) | ||
162 | { | ||
163 | if (l & 0xff000000L) | ||
164 | return(bits[l>>24L]+24); | ||
165 | else return(bits[l>>16L]+16); | ||
166 | } | ||
167 | else | ||
168 | #endif | ||
169 | { | ||
170 | #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) | ||
171 | if (l & 0xff00L) | ||
172 | return(bits[l>>8]+8); | ||
173 | else | ||
174 | #endif | ||
175 | return(bits[l ] ); | ||
176 | } | ||
177 | } | ||
178 | } | ||
179 | |||
180 | int BN_num_bits(a) | ||
181 | BIGNUM *a; | ||
182 | { | ||
183 | BN_ULONG l; | ||
184 | int i; | ||
185 | |||
186 | if (a->top == 0) return(0); | ||
187 | l=a->d[a->top-1]; | ||
188 | i=(a->top-1)*BN_BITS2; | ||
189 | if (l == 0) | ||
190 | { | ||
191 | #if !defined(NO_STDIO) && !defined(WIN16) | ||
192 | fprintf(stderr,"BAD TOP VALUE\n"); | ||
193 | #endif | ||
194 | abort(); | ||
195 | } | ||
196 | return(i+BN_num_bits_word(l)); | ||
197 | } | ||
198 | |||
199 | void BN_clear_free(a) | ||
200 | BIGNUM *a; | ||
201 | { | ||
202 | if (a == NULL) return; | ||
203 | if (a->d != NULL) | ||
204 | { | ||
205 | memset(a->d,0,a->max*sizeof(a->d[0])); | ||
206 | Free(a->d); | ||
207 | } | ||
208 | memset(a,0,sizeof(BIGNUM)); | ||
209 | Free(a); | ||
210 | } | ||
211 | |||
212 | void BN_free(a) | ||
213 | BIGNUM *a; | ||
214 | { | ||
215 | if (a == NULL) return; | ||
216 | if (a->d != NULL) Free(a->d); | ||
217 | Free(a); | ||
218 | } | ||
219 | |||
220 | BIGNUM *BN_new() | ||
221 | { | ||
222 | BIGNUM *ret; | ||
223 | BN_ULONG *p; | ||
224 | |||
225 | ret=(BIGNUM *)Malloc(sizeof(BIGNUM)); | ||
226 | if (ret == NULL) goto err; | ||
227 | ret->top=0; | ||
228 | ret->neg=0; | ||
229 | ret->max=(BN_DEFAULT_BITS/BN_BITS2); | ||
230 | p=(BN_ULONG *)Malloc(sizeof(BN_ULONG)*(ret->max+1)); | ||
231 | if (p == NULL) goto err; | ||
232 | ret->d=p; | ||
233 | |||
234 | memset(p,0,(ret->max+1)*sizeof(p[0])); | ||
235 | return(ret); | ||
236 | err: | ||
237 | BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE); | ||
238 | return(NULL); | ||
239 | } | ||
240 | |||
241 | BN_CTX *BN_CTX_new() | ||
242 | { | ||
243 | BN_CTX *ret; | ||
244 | BIGNUM *n; | ||
245 | int i,j; | ||
246 | |||
247 | ret=(BN_CTX *)Malloc(sizeof(BN_CTX)); | ||
248 | if (ret == NULL) goto err2; | ||
249 | |||
250 | for (i=0; i<BN_CTX_NUM; i++) | ||
251 | { | ||
252 | n=BN_new(); | ||
253 | if (n == NULL) goto err; | ||
254 | ret->bn[i]=n; | ||
255 | } | ||
256 | |||
257 | /* There is actually an extra one, this is for debugging my | ||
258 | * stuff */ | ||
259 | ret->bn[BN_CTX_NUM]=NULL; | ||
260 | |||
261 | ret->tos=0; | ||
262 | return(ret); | ||
263 | err: | ||
264 | for (j=0; j<i; j++) | ||
265 | BN_free(ret->bn[j]); | ||
266 | Free(ret); | ||
267 | err2: | ||
268 | BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE); | ||
269 | return(NULL); | ||
270 | } | ||
271 | |||
272 | void BN_CTX_free(c) | ||
273 | BN_CTX *c; | ||
274 | { | ||
275 | int i; | ||
276 | |||
277 | for (i=0; i<BN_CTX_NUM; i++) | ||
278 | BN_clear_free(c->bn[i]); | ||
279 | Free(c); | ||
280 | } | ||
281 | |||
282 | BIGNUM *bn_expand2(b, words) | ||
283 | BIGNUM *b; | ||
284 | int words; | ||
285 | { | ||
286 | BN_ULONG *p; | ||
287 | |||
288 | if (words > b->max) | ||
289 | { | ||
290 | p=(BN_ULONG *)Realloc(b->d,sizeof(BN_ULONG)*(words+1)); | ||
291 | if (p == NULL) | ||
292 | { | ||
293 | BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE); | ||
294 | return(NULL); | ||
295 | } | ||
296 | b->d=p; | ||
297 | memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG)); | ||
298 | b->max=words; | ||
299 | } | ||
300 | return(b); | ||
301 | } | ||
302 | |||
303 | BIGNUM *BN_dup(a) | ||
304 | BIGNUM *a; | ||
305 | { | ||
306 | BIGNUM *r; | ||
307 | |||
308 | r=BN_new(); | ||
309 | if (r == NULL) return(NULL); | ||
310 | return((BIGNUM *)BN_copy(r,a)); | ||
311 | } | ||
312 | |||
313 | BIGNUM *BN_copy(a, b) | ||
314 | BIGNUM *a; | ||
315 | BIGNUM *b; | ||
316 | { | ||
317 | int i; | ||
318 | BN_ULONG *A,*B; | ||
319 | |||
320 | if (a == b) return(a); | ||
321 | if (bn_wexpand(a,b->top) == NULL) return(NULL); | ||
322 | |||
323 | #if 1 | ||
324 | A=a->d; | ||
325 | B=b->d; | ||
326 | for (i=b->top&(~7); i>0; i-=8) | ||
327 | { | ||
328 | A[0]=B[0]; | ||
329 | A[1]=B[1]; | ||
330 | A[2]=B[2]; | ||
331 | A[3]=B[3]; | ||
332 | A[4]=B[4]; | ||
333 | A[5]=B[5]; | ||
334 | A[6]=B[6]; | ||
335 | A[7]=B[7]; | ||
336 | A+=8; | ||
337 | B+=8; | ||
338 | } | ||
339 | switch (b->top&7) | ||
340 | { | ||
341 | case 7: | ||
342 | A[6]=B[6]; | ||
343 | case 6: | ||
344 | A[5]=B[5]; | ||
345 | case 5: | ||
346 | A[4]=B[4]; | ||
347 | case 4: | ||
348 | A[3]=B[3]; | ||
349 | case 3: | ||
350 | A[2]=B[2]; | ||
351 | case 2: | ||
352 | A[1]=B[1]; | ||
353 | case 1: | ||
354 | A[0]=B[0]; | ||
355 | } | ||
356 | #else | ||
357 | memcpy(a->d,b->d,sizeof(b->d[0])*b->top); | ||
358 | #endif | ||
359 | |||
360 | /* memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/ | ||
361 | a->top=b->top; | ||
362 | if (a->top == 0) | ||
363 | a->d[0]=0; | ||
364 | a->neg=b->neg; | ||
365 | return(a); | ||
366 | } | ||
367 | |||
368 | void BN_clear(a) | ||
369 | BIGNUM *a; | ||
370 | { | ||
371 | memset(a->d,0,a->max*sizeof(a->d[0])); | ||
372 | a->top=0; | ||
373 | a->neg=0; | ||
374 | } | ||
375 | |||
376 | unsigned long BN_get_word(a) | ||
377 | BIGNUM *a; | ||
378 | { | ||
379 | int i,n; | ||
380 | unsigned long ret=0; | ||
381 | |||
382 | n=BN_num_bytes(a); | ||
383 | if (n > sizeof(unsigned long)) | ||
384 | #ifdef SIXTY_FOUR_BIT_LONG | ||
385 | return(BN_MASK2); | ||
386 | #else | ||
387 | return(0xFFFFFFFFL); | ||
388 | #endif | ||
389 | for (i=a->top-1; i>=0; i--) | ||
390 | { | ||
391 | #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */ | ||
392 | ret<<=BN_BITS4; /* stops the compiler complaining */ | ||
393 | ret<<=BN_BITS4; | ||
394 | #endif | ||
395 | ret|=a->d[i]; | ||
396 | } | ||
397 | return(ret); | ||
398 | } | ||
399 | |||
400 | int BN_set_word(a,w) | ||
401 | BIGNUM *a; | ||
402 | unsigned long w; | ||
403 | { | ||
404 | int i,n; | ||
405 | if (bn_expand(a,sizeof(unsigned long)*8) == NULL) return(0); | ||
406 | |||
407 | n=sizeof(unsigned long)/BN_BYTES; | ||
408 | a->neg=0; | ||
409 | a->top=0; | ||
410 | a->d[0]=(BN_ULONG)w&BN_MASK2; | ||
411 | if (a->d[0] != 0) a->top=1; | ||
412 | for (i=1; i<n; i++) | ||
413 | { | ||
414 | /* the following is done instead of | ||
415 | * w>>=BN_BITS2 so compilers don't complain | ||
416 | * on builds where sizeof(long) == BN_TYPES */ | ||
417 | #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */ | ||
418 | w>>=BN_BITS4; | ||
419 | w>>=BN_BITS4; | ||
420 | #endif | ||
421 | a->d[i]=(BN_ULONG)w&BN_MASK2; | ||
422 | if (a->d[i] != 0) a->top=i+1; | ||
423 | } | ||
424 | return(1); | ||
425 | } | ||
426 | |||
427 | /* ignore negative */ | ||
428 | BIGNUM *BN_bin2bn(s, len, ret) | ||
429 | unsigned char *s; | ||
430 | int len; | ||
431 | BIGNUM *ret; | ||
432 | { | ||
433 | unsigned int i,m; | ||
434 | unsigned int n; | ||
435 | BN_ULONG l; | ||
436 | |||
437 | if (ret == NULL) ret=BN_new(); | ||
438 | if (ret == NULL) return(NULL); | ||
439 | l=0; | ||
440 | n=len; | ||
441 | if (n == 0) | ||
442 | { | ||
443 | ret->top=0; | ||
444 | return(ret); | ||
445 | } | ||
446 | if (bn_expand(ret,(int)(n+2)*8) == NULL) | ||
447 | return(NULL); | ||
448 | i=((n-1)/BN_BYTES)+1; | ||
449 | m=((n-1)%(BN_BYTES)); | ||
450 | ret->top=i; | ||
451 | while (n-- > 0) | ||
452 | { | ||
453 | l=(l<<8L)| *(s++); | ||
454 | if (m-- == 0) | ||
455 | { | ||
456 | ret->d[--i]=l; | ||
457 | l=0; | ||
458 | m=BN_BYTES-1; | ||
459 | } | ||
460 | } | ||
461 | /* need to call this due to clear byte at top if avoiding | ||
462 | * having the top bit set (-ve number) */ | ||
463 | bn_fix_top(ret); | ||
464 | return(ret); | ||
465 | } | ||
466 | |||
467 | /* ignore negative */ | ||
468 | int BN_bn2bin(a, to) | ||
469 | BIGNUM *a; | ||
470 | unsigned char *to; | ||
471 | { | ||
472 | int n,i; | ||
473 | BN_ULONG l; | ||
474 | |||
475 | n=i=BN_num_bytes(a); | ||
476 | while (i-- > 0) | ||
477 | { | ||
478 | l=a->d[i/BN_BYTES]; | ||
479 | *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff; | ||
480 | } | ||
481 | return(n); | ||
482 | } | ||
483 | |||
484 | int BN_ucmp(a, b) | ||
485 | BIGNUM *a; | ||
486 | BIGNUM *b; | ||
487 | { | ||
488 | int i; | ||
489 | BN_ULONG t1,t2,*ap,*bp; | ||
490 | |||
491 | i=a->top-b->top; | ||
492 | if (i != 0) return(i); | ||
493 | ap=a->d; | ||
494 | bp=b->d; | ||
495 | for (i=a->top-1; i>=0; i--) | ||
496 | { | ||
497 | t1= ap[i]; | ||
498 | t2= bp[i]; | ||
499 | if (t1 != t2) | ||
500 | return(t1 > t2?1:-1); | ||
501 | } | ||
502 | return(0); | ||
503 | } | ||
504 | |||
505 | int BN_cmp(a, b) | ||
506 | BIGNUM *a; | ||
507 | BIGNUM *b; | ||
508 | { | ||
509 | int i; | ||
510 | int gt,lt; | ||
511 | BN_ULONG t1,t2; | ||
512 | |||
513 | if ((a == NULL) || (b == NULL)) | ||
514 | { | ||
515 | if (a != NULL) | ||
516 | return(-1); | ||
517 | else if (b != NULL) | ||
518 | return(1); | ||
519 | else | ||
520 | return(0); | ||
521 | } | ||
522 | if (a->neg != b->neg) | ||
523 | { | ||
524 | if (a->neg) | ||
525 | return(-1); | ||
526 | else return(1); | ||
527 | } | ||
528 | if (a->neg == 0) | ||
529 | { gt=1; lt= -1; } | ||
530 | else { gt= -1; lt=1; } | ||
531 | |||
532 | if (a->top > b->top) return(gt); | ||
533 | if (a->top < b->top) return(lt); | ||
534 | for (i=a->top-1; i>=0; i--) | ||
535 | { | ||
536 | t1=a->d[i]; | ||
537 | t2=b->d[i]; | ||
538 | if (t1 > t2) return(gt); | ||
539 | if (t1 < t2) return(lt); | ||
540 | } | ||
541 | return(0); | ||
542 | } | ||
543 | |||
544 | int BN_set_bit(a, n) | ||
545 | BIGNUM *a; | ||
546 | int n; | ||
547 | { | ||
548 | int i,j; | ||
549 | |||
550 | i=n/BN_BITS2; | ||
551 | j=n%BN_BITS2; | ||
552 | if (a->top <= i) | ||
553 | { | ||
554 | if (bn_expand(a,n) == NULL) return(0); | ||
555 | a->top=i+1; | ||
556 | } | ||
557 | |||
558 | a->d[i]|=(1L<<j); | ||
559 | return(1); | ||
560 | } | ||
561 | |||
562 | int BN_clear_bit(a, n) | ||
563 | BIGNUM *a; | ||
564 | int n; | ||
565 | { | ||
566 | int i,j; | ||
567 | |||
568 | i=n/BN_BITS2; | ||
569 | j=n%BN_BITS2; | ||
570 | if (a->top <= i) return(0); | ||
571 | |||
572 | a->d[i]&=(~(1L<<j)); | ||
573 | return(1); | ||
574 | } | ||
575 | |||
576 | int BN_is_bit_set(a, n) | ||
577 | BIGNUM *a; | ||
578 | int n; | ||
579 | { | ||
580 | int i,j; | ||
581 | |||
582 | if (n < 0) return(0); | ||
583 | i=n/BN_BITS2; | ||
584 | j=n%BN_BITS2; | ||
585 | if (a->top <= i) return(0); | ||
586 | return((a->d[i]&(((BN_ULONG)1)<<j))?1:0); | ||
587 | } | ||
588 | |||
589 | int BN_mask_bits(a,n) | ||
590 | BIGNUM *a; | ||
591 | int n; | ||
592 | { | ||
593 | int b,w; | ||
594 | |||
595 | w=n/BN_BITS2; | ||
596 | b=n%BN_BITS2; | ||
597 | if (w >= a->top) return(0); | ||
598 | if (b == 0) | ||
599 | a->top=w; | ||
600 | else | ||
601 | { | ||
602 | a->top=w+1; | ||
603 | a->d[w]&= ~(BN_MASK2<<b); | ||
604 | while ((w >= 0) && (a->d[w] == 0)) | ||
605 | { | ||
606 | a->top--; | ||
607 | w--; | ||
608 | } | ||
609 | } | ||
610 | return(1); | ||
611 | } | ||
diff --git a/src/lib/libcrypto/bn/bn_mod.c b/src/lib/libcrypto/bn/bn_mod.c new file mode 100644 index 0000000000..c351aac14f --- /dev/null +++ b/src/lib/libcrypto/bn/bn_mod.c | |||
@@ -0,0 +1,97 @@ | |||
1 | /* crypto/bn/bn_mod.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include "cryptlib.h" | ||
61 | #include "bn_lcl.h" | ||
62 | |||
63 | /* rem != m */ | ||
64 | int BN_mod(rem, m, d,ctx) | ||
65 | BIGNUM *rem; | ||
66 | BIGNUM *m; | ||
67 | BIGNUM *d; | ||
68 | BN_CTX *ctx; | ||
69 | { | ||
70 | #if 0 /* The old slow way */ | ||
71 | int i,nm,nd; | ||
72 | BIGNUM *dv; | ||
73 | |||
74 | if (BN_ucmp(m,d) < 0) | ||
75 | return((BN_copy(rem,m) == NULL)?0:1); | ||
76 | |||
77 | dv=ctx->bn[ctx->tos]; | ||
78 | |||
79 | if (!BN_copy(rem,m)) return(0); | ||
80 | |||
81 | nm=BN_num_bits(rem); | ||
82 | nd=BN_num_bits(d); | ||
83 | if (!BN_lshift(dv,d,nm-nd)) return(0); | ||
84 | for (i=nm-nd; i>=0; i--) | ||
85 | { | ||
86 | if (BN_cmp(rem,dv) >= 0) | ||
87 | { | ||
88 | if (!BN_sub(rem,rem,dv)) return(0); | ||
89 | } | ||
90 | if (!BN_rshift1(dv,dv)) return(0); | ||
91 | } | ||
92 | return(1); | ||
93 | #else | ||
94 | return(BN_div(NULL,rem,m,d,ctx)); | ||
95 | #endif | ||
96 | } | ||
97 | |||
diff --git a/src/lib/libcrypto/bn/bn_mont.c b/src/lib/libcrypto/bn/bn_mont.c new file mode 100644 index 0000000000..e435df61f8 --- /dev/null +++ b/src/lib/libcrypto/bn/bn_mont.c | |||
@@ -0,0 +1,306 @@ | |||
1 | /* crypto/bn/bn_mont.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include "cryptlib.h" | ||
61 | #include "bn_lcl.h" | ||
62 | |||
63 | int BN_mod_mul_montgomery(r,a,b,mont,ctx) | ||
64 | BIGNUM *r,*a,*b; | ||
65 | BN_MONT_CTX *mont; | ||
66 | BN_CTX *ctx; | ||
67 | { | ||
68 | BIGNUM *tmp; | ||
69 | |||
70 | tmp=ctx->bn[ctx->tos++]; | ||
71 | |||
72 | if (a == b) | ||
73 | { | ||
74 | if (!BN_sqr(tmp,a,ctx)) goto err; | ||
75 | } | ||
76 | else | ||
77 | { | ||
78 | if (!BN_mul(tmp,a,b)) goto err; | ||
79 | } | ||
80 | /* reduce from aRR to aR */ | ||
81 | if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err; | ||
82 | ctx->tos--; | ||
83 | return(1); | ||
84 | err: | ||
85 | return(0); | ||
86 | } | ||
87 | |||
88 | #define MONT_WORD | ||
89 | |||
90 | #ifdef MONT_WORD | ||
91 | int BN_from_montgomery(ret,a,mont,ctx) | ||
92 | BIGNUM *ret; | ||
93 | BIGNUM *a; | ||
94 | BN_MONT_CTX *mont; | ||
95 | BN_CTX *ctx; | ||
96 | { | ||
97 | BIGNUM *n,*t1,*r; | ||
98 | BN_ULONG *ap,*np,*rp,n0,v; | ||
99 | int al,nl,max,i,x,ri; | ||
100 | int retn=0; | ||
101 | |||
102 | t1=ctx->bn[ctx->tos]; | ||
103 | r=ctx->bn[ctx->tos+1]; | ||
104 | |||
105 | if (!BN_copy(r,a)) goto err; | ||
106 | n=mont->N; | ||
107 | |||
108 | ap=a->d; | ||
109 | /* mont->ri is the size of mont->N in bits/words */ | ||
110 | al=ri=mont->ri/BN_BITS2; | ||
111 | |||
112 | nl=n->top; | ||
113 | if ((al == 0) || (nl == 0)) { r->top=0; return(1); } | ||
114 | |||
115 | max=(nl+al+1); /* allow for overflow (no?) XXX */ | ||
116 | if (bn_wexpand(r,max) == NULL) goto err; | ||
117 | if (bn_wexpand(ret,max) == NULL) goto err; | ||
118 | |||
119 | r->neg=a->neg^n->neg; | ||
120 | np=n->d; | ||
121 | rp=r->d; | ||
122 | |||
123 | /* clear the top words of T */ | ||
124 | #if 1 | ||
125 | for (i=r->top; i<max; i++) /* memset? XXX */ | ||
126 | r->d[i]=0; | ||
127 | #else | ||
128 | memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG)); | ||
129 | #endif | ||
130 | |||
131 | r->top=max; | ||
132 | n0=mont->n0; | ||
133 | |||
134 | for (i=0; i<nl; i++) | ||
135 | { | ||
136 | #if 0 | ||
137 | int x1,x2; | ||
138 | |||
139 | if (i+4 > nl) | ||
140 | { | ||
141 | x2=nl; | ||
142 | x1=0; | ||
143 | } | ||
144 | else | ||
145 | { | ||
146 | x2=i+4; | ||
147 | x1=nl-x2; | ||
148 | } | ||
149 | v=bn_mul_add_words(&(rp[x1]),&(np[x1]),x2,(rp[x1]*n0)&BN_MASK2); | ||
150 | #else | ||
151 | v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2); | ||
152 | #endif | ||
153 | |||
154 | if (((rp[nl]+=v)&BN_MASK2) < v) | ||
155 | { | ||
156 | for (x=(nl+1); (((++rp[x])&BN_MASK2) == 0); x++) | ||
157 | ; | ||
158 | } | ||
159 | rp++; | ||
160 | } | ||
161 | while (r->d[r->top-1] == 0) | ||
162 | r->top--; | ||
163 | |||
164 | /* mont->ri will be a multiple of the word size */ | ||
165 | #if 0 | ||
166 | BN_rshift(ret,r,mont->ri); | ||
167 | #else | ||
168 | ap=r->d; | ||
169 | rp=ret->d; | ||
170 | x=ri; | ||
171 | al=r->top-x; | ||
172 | for (i=0; i<al; i++) | ||
173 | { | ||
174 | rp[i]=ap[i+x]; | ||
175 | } | ||
176 | ret->top=al; | ||
177 | #endif | ||
178 | |||
179 | if (BN_ucmp(ret,mont->N) >= 0) | ||
180 | { | ||
181 | bn_qsub(ret,ret,mont->N); /* XXX */ | ||
182 | } | ||
183 | retn=1; | ||
184 | err: | ||
185 | return(retn); | ||
186 | } | ||
187 | #else | ||
188 | int BN_from_montgomery(r,a,mont,ctx) | ||
189 | BIGNUM *r; | ||
190 | BIGNUM *a; | ||
191 | BN_MONT_CTX *mont; | ||
192 | BN_CTX *ctx; | ||
193 | { | ||
194 | BIGNUM *t1,*t2; | ||
195 | |||
196 | t1=ctx->bn[ctx->tos]; | ||
197 | t2=ctx->bn[ctx->tos+1]; | ||
198 | |||
199 | if (!BN_copy(t1,a)) goto err; | ||
200 | /* can cheat */ | ||
201 | BN_mask_bits(t1,mont->ri); | ||
202 | |||
203 | if (!BN_mul(t2,t1,mont->Ni)) goto err; | ||
204 | BN_mask_bits(t2,mont->ri); | ||
205 | |||
206 | if (!BN_mul(t1,t2,mont->N)) goto err; | ||
207 | if (!BN_add(t2,a,t1)) goto err; | ||
208 | BN_rshift(r,t2,mont->ri); | ||
209 | |||
210 | if (BN_ucmp(r,mont->N) >= 0) | ||
211 | bn_qsub(r,r,mont->N); | ||
212 | |||
213 | return(1); | ||
214 | err: | ||
215 | return(0); | ||
216 | } | ||
217 | #endif | ||
218 | |||
219 | BN_MONT_CTX *BN_MONT_CTX_new() | ||
220 | { | ||
221 | BN_MONT_CTX *ret; | ||
222 | |||
223 | if ((ret=(BN_MONT_CTX *)Malloc(sizeof(BN_MONT_CTX))) == NULL) | ||
224 | return(NULL); | ||
225 | ret->ri=0; | ||
226 | ret->RR=BN_new(); | ||
227 | ret->N=BN_new(); | ||
228 | ret->Ni=NULL; | ||
229 | if ((ret->RR == NULL) || (ret->N == NULL)) | ||
230 | { | ||
231 | BN_MONT_CTX_free(ret); | ||
232 | return(NULL); | ||
233 | } | ||
234 | return(ret); | ||
235 | } | ||
236 | |||
237 | void BN_MONT_CTX_free(mont) | ||
238 | BN_MONT_CTX *mont; | ||
239 | { | ||
240 | if (mont->RR != NULL) BN_free(mont->RR); | ||
241 | if (mont->N != NULL) BN_free(mont->N); | ||
242 | if (mont->Ni != NULL) BN_free(mont->Ni); | ||
243 | Free(mont); | ||
244 | } | ||
245 | |||
246 | int BN_MONT_CTX_set(mont,mod,ctx) | ||
247 | BN_MONT_CTX *mont; | ||
248 | BIGNUM *mod; | ||
249 | BN_CTX *ctx; | ||
250 | { | ||
251 | BIGNUM *Ri=NULL,*R=NULL; | ||
252 | |||
253 | if (mont->RR == NULL) mont->RR=BN_new(); | ||
254 | if (mont->N == NULL) mont->N=BN_new(); | ||
255 | |||
256 | R=mont->RR; /* grab RR as a temp */ | ||
257 | BN_copy(mont->N,mod); /* Set N */ | ||
258 | |||
259 | #ifdef MONT_WORD | ||
260 | { | ||
261 | BIGNUM tmod; | ||
262 | BN_ULONG buf[2]; | ||
263 | /* int z; */ | ||
264 | |||
265 | mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2; | ||
266 | BN_lshift(R,BN_value_one(),BN_BITS2); /* R */ | ||
267 | /* I was bad, this modification of a passed variable was | ||
268 | * breaking the multithreaded stuff :-( | ||
269 | * z=mod->top; | ||
270 | * mod->top=1; */ | ||
271 | |||
272 | buf[0]=mod->d[0]; | ||
273 | buf[1]=0; | ||
274 | tmod.d=buf; | ||
275 | tmod.top=1; | ||
276 | tmod.max=mod->max; | ||
277 | tmod.neg=mod->neg; | ||
278 | |||
279 | if ((Ri=BN_mod_inverse(R,&tmod,ctx)) == NULL) goto err; /* Ri */ | ||
280 | BN_lshift(Ri,Ri,BN_BITS2); /* R*Ri */ | ||
281 | bn_qsub(Ri,Ri,BN_value_one()); /* R*Ri - 1 */ | ||
282 | BN_div(Ri,NULL,Ri,&tmod,ctx); | ||
283 | mont->n0=Ri->d[0]; | ||
284 | BN_free(Ri); | ||
285 | /* mod->top=z; */ | ||
286 | } | ||
287 | #else | ||
288 | mont->ri=BN_num_bits(mod); | ||
289 | BN_lshift(R,BN_value_one(),mont->ri); /* R */ | ||
290 | if ((Ri=BN_mod_inverse(R,mod,ctx)) == NULL) goto err; /* Ri */ | ||
291 | BN_lshift(Ri,Ri,mont->ri); /* R*Ri */ | ||
292 | bn_qsub(Ri,Ri,BN_value_one()); /* R*Ri - 1 */ | ||
293 | BN_div(Ri,NULL,Ri,mod,ctx); | ||
294 | if (mont->Ni != NULL) BN_free(mont->Ni); | ||
295 | mont->Ni=Ri; /* Ni=(R*Ri-1)/N */ | ||
296 | #endif | ||
297 | |||
298 | /* setup RR for conversions */ | ||
299 | BN_lshift(mont->RR,BN_value_one(),mont->ri*2); | ||
300 | BN_mod(mont->RR,mont->RR,mont->N,ctx); | ||
301 | |||
302 | return(1); | ||
303 | err: | ||
304 | return(0); | ||
305 | } | ||
306 | |||
diff --git a/src/lib/libcrypto/bn/bn_mpi.c b/src/lib/libcrypto/bn/bn_mpi.c new file mode 100644 index 0000000000..53945c1057 --- /dev/null +++ b/src/lib/libcrypto/bn/bn_mpi.c | |||
@@ -0,0 +1,134 @@ | |||
1 | /* crypto/bn/bn_mpi.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include "cryptlib.h" | ||
61 | #include "bn_lcl.h" | ||
62 | |||
63 | int BN_bn2mpi(a,d) | ||
64 | BIGNUM *a; | ||
65 | unsigned char *d; | ||
66 | { | ||
67 | int bits; | ||
68 | int num=0; | ||
69 | int ext=0; | ||
70 | long l; | ||
71 | |||
72 | bits=BN_num_bits(a); | ||
73 | num=(bits+7)/8; | ||
74 | if (bits > 0) | ||
75 | { | ||
76 | ext=((bits & 0x07) == 0); | ||
77 | } | ||
78 | if (d == NULL) | ||
79 | return(num+4+ext); | ||
80 | |||
81 | l=num+ext; | ||
82 | d[0]=(unsigned char)(l>>24)&0xff; | ||
83 | d[1]=(unsigned char)(l>>16)&0xff; | ||
84 | d[2]=(unsigned char)(l>> 8)&0xff; | ||
85 | d[3]=(unsigned char)(l )&0xff; | ||
86 | if (ext) d[4]=0; | ||
87 | num=BN_bn2bin(a,&(d[4+ext])); | ||
88 | if (a->neg) | ||
89 | d[4]|=0x80; | ||
90 | return(num+4+ext); | ||
91 | } | ||
92 | |||
93 | BIGNUM *BN_mpi2bn(d,n,a) | ||
94 | unsigned char *d; | ||
95 | int n; | ||
96 | BIGNUM *a; | ||
97 | { | ||
98 | long len; | ||
99 | int neg=0; | ||
100 | |||
101 | if (n < 4) | ||
102 | { | ||
103 | BNerr(BN_F_BN_MPI2BN,BN_R_INVALID_LENGTH); | ||
104 | return(NULL); | ||
105 | } | ||
106 | len=(d[0]<<24)|(d[1]<<16)|(d[2]<<8)|d[3]; | ||
107 | if ((len+4) != n) | ||
108 | { | ||
109 | BNerr(BN_F_BN_MPI2BN,BN_R_ENCODING_ERROR); | ||
110 | return(NULL); | ||
111 | } | ||
112 | |||
113 | if (a == NULL) a=BN_new(); | ||
114 | if (a == NULL) return(NULL); | ||
115 | |||
116 | if (len == 0) | ||
117 | { | ||
118 | a->neg=0; | ||
119 | a->top=0; | ||
120 | return(a); | ||
121 | } | ||
122 | d+=4; | ||
123 | if ((*d) & 0x80) | ||
124 | neg=1; | ||
125 | if (BN_bin2bn(d,(int)len,a) == NULL) | ||
126 | return(NULL); | ||
127 | a->neg=neg; | ||
128 | if (neg) | ||
129 | { | ||
130 | BN_clear_bit(a,BN_num_bits(a)-1); | ||
131 | } | ||
132 | return(a); | ||
133 | } | ||
134 | |||
diff --git a/src/lib/libcrypto/bn/bn_mul.c b/src/lib/libcrypto/bn/bn_mul.c new file mode 100644 index 0000000000..d0c04e1d4b --- /dev/null +++ b/src/lib/libcrypto/bn/bn_mul.c | |||
@@ -0,0 +1,209 @@ | |||
1 | /* crypto/bn/bn_mul.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include "cryptlib.h" | ||
61 | #include "bn_lcl.h" | ||
62 | |||
63 | /* r must be different to a and b */ | ||
64 | /* int BN_mmul(r, a, b) */ | ||
65 | int BN_mul(r, a, b) | ||
66 | BIGNUM *r; | ||
67 | BIGNUM *a; | ||
68 | BIGNUM *b; | ||
69 | { | ||
70 | int i; | ||
71 | int max,al,bl; | ||
72 | BN_ULONG *ap,*bp,*rp; | ||
73 | |||
74 | al=a->top; | ||
75 | bl=b->top; | ||
76 | if ((al == 0) || (bl == 0)) | ||
77 | { | ||
78 | r->top=0; | ||
79 | return(1); | ||
80 | } | ||
81 | |||
82 | max=(al+bl); | ||
83 | if (bn_wexpand(r,max) == NULL) return(0); | ||
84 | r->top=max; | ||
85 | r->neg=a->neg^b->neg; | ||
86 | ap=a->d; | ||
87 | bp=b->d; | ||
88 | rp=r->d; | ||
89 | |||
90 | rp[al]=bn_mul_words(rp,ap,al,*(bp++)); | ||
91 | rp++; | ||
92 | for (i=1; i<bl; i++) | ||
93 | { | ||
94 | rp[al]=bn_mul_add_words(rp,ap,al,*(bp++)); | ||
95 | rp++; | ||
96 | } | ||
97 | if (r->d[max-1] == 0) r->top--; | ||
98 | return(1); | ||
99 | } | ||
100 | |||
101 | #if 0 | ||
102 | #include "stack.h" | ||
103 | |||
104 | int limit=16; | ||
105 | |||
106 | typedef struct bn_pool_st | ||
107 | { | ||
108 | int used; | ||
109 | int tos; | ||
110 | STACK *sk; | ||
111 | } BN_POOL; | ||
112 | |||
113 | BIGNUM *BN_POOL_push(bp) | ||
114 | BN_POOL *bp; | ||
115 | { | ||
116 | BIGNUM *ret; | ||
117 | |||
118 | if (bp->used >= bp->tos) | ||
119 | { | ||
120 | ret=BN_new(); | ||
121 | sk_push(bp->sk,(char *)ret); | ||
122 | bp->tos++; | ||
123 | bp->used++; | ||
124 | } | ||
125 | else | ||
126 | { | ||
127 | ret=(BIGNUM *)sk_value(bp->sk,bp->used); | ||
128 | bp->used++; | ||
129 | } | ||
130 | return(ret); | ||
131 | } | ||
132 | |||
133 | void BN_POOL_pop(bp,num) | ||
134 | BN_POOL *bp; | ||
135 | int num; | ||
136 | { | ||
137 | bp->used-=num; | ||
138 | } | ||
139 | |||
140 | int BN_mul(r,a,b) | ||
141 | BIGNUM *r,*a,*b; | ||
142 | { | ||
143 | static BN_POOL bp; | ||
144 | static init=1; | ||
145 | |||
146 | if (init) | ||
147 | { | ||
148 | bp.used=0; | ||
149 | bp.tos=0; | ||
150 | bp.sk=sk_new_null(); | ||
151 | init=0; | ||
152 | } | ||
153 | return(BN_mm(r,a,b,&bp)); | ||
154 | } | ||
155 | |||
156 | /* r must be different to a and b */ | ||
157 | int BN_mm(m, A, B, bp) | ||
158 | BIGNUM *m,*A,*B; | ||
159 | BN_POOL *bp; | ||
160 | { | ||
161 | int i,num; | ||
162 | int an,bn; | ||
163 | BIGNUM *a,*b,*c,*d,*ac,*bd; | ||
164 | |||
165 | an=A->top; | ||
166 | bn=B->top; | ||
167 | if ((an <= limit) || (bn <= limit)) | ||
168 | { | ||
169 | return(BN_mmul(m,A,B)); | ||
170 | } | ||
171 | |||
172 | a=BN_POOL_push(bp); | ||
173 | b=BN_POOL_push(bp); | ||
174 | c=BN_POOL_push(bp); | ||
175 | d=BN_POOL_push(bp); | ||
176 | ac=BN_POOL_push(bp); | ||
177 | bd=BN_POOL_push(bp); | ||
178 | |||
179 | num=(an <= bn)?an:bn; | ||
180 | num=1<<(BN_num_bits_word(num-1)-1); | ||
181 | |||
182 | /* Are going to now chop things into 'num' word chunks. */ | ||
183 | num*=BN_BITS2; | ||
184 | |||
185 | BN_copy(a,A); | ||
186 | BN_mask_bits(a,num); | ||
187 | BN_rshift(b,A,num); | ||
188 | |||
189 | BN_copy(c,B); | ||
190 | BN_mask_bits(c,num); | ||
191 | BN_rshift(d,B,num); | ||
192 | |||
193 | BN_sub(ac ,b,a); | ||
194 | BN_sub(bd,c,d); | ||
195 | BN_mm(m,ac,bd,bp); | ||
196 | BN_mm(ac,a,c,bp); | ||
197 | BN_mm(bd,b,d,bp); | ||
198 | |||
199 | BN_add(m,m,ac); | ||
200 | BN_add(m,m,bd); | ||
201 | BN_lshift(m,m,num); | ||
202 | BN_lshift(bd,bd,num*2); | ||
203 | |||
204 | BN_add(m,m,ac); | ||
205 | BN_add(m,m,bd); | ||
206 | BN_POOL_pop(bp,6); | ||
207 | return(1); | ||
208 | } | ||
209 | #endif | ||
diff --git a/src/lib/libcrypto/bn/bn_prime.c b/src/lib/libcrypto/bn/bn_prime.c new file mode 100644 index 0000000000..0c85f70b59 --- /dev/null +++ b/src/lib/libcrypto/bn/bn_prime.c | |||
@@ -0,0 +1,473 @@ | |||
1 | /* crypto/bn/bn_prime.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include <time.h> | ||
61 | #include "cryptlib.h" | ||
62 | #include "bn_lcl.h" | ||
63 | #include "rand.h" | ||
64 | |||
65 | /* The quick seive algorithm approach to weeding out primes is | ||
66 | * Philip Zimmermann's, as implemented in PGP. I have had a read of | ||
67 | * his comments and implemented my own version. | ||
68 | */ | ||
69 | #include "bn_prime.h" | ||
70 | |||
71 | #ifndef NOPROTO | ||
72 | static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx,BN_CTX *ctx2, | ||
73 | BN_MONT_CTX *mont); | ||
74 | static int probable_prime(BIGNUM *rnd, int bits); | ||
75 | static int probable_prime_dh(BIGNUM *rnd, int bits, | ||
76 | BIGNUM *add, BIGNUM *rem, BN_CTX *ctx); | ||
77 | static int probable_prime_dh_strong(BIGNUM *rnd, int bits, | ||
78 | BIGNUM *add, BIGNUM *rem, BN_CTX *ctx); | ||
79 | #else | ||
80 | static int witness(); | ||
81 | static int probable_prime(); | ||
82 | static int probable_prime_dh(); | ||
83 | static int probable_prime_dh_strong(); | ||
84 | #endif | ||
85 | |||
86 | BIGNUM *BN_generate_prime(bits,strong,add,rem,callback,cb_arg) | ||
87 | int bits; | ||
88 | int strong; | ||
89 | BIGNUM *add; | ||
90 | BIGNUM *rem; | ||
91 | void (*callback)(P_I_I_P); | ||
92 | char *cb_arg; | ||
93 | { | ||
94 | BIGNUM *rnd=NULL; | ||
95 | BIGNUM *ret=NULL; | ||
96 | BIGNUM *t=NULL; | ||
97 | int i,j,c1=0; | ||
98 | BN_CTX *ctx; | ||
99 | |||
100 | ctx=BN_CTX_new(); | ||
101 | if (ctx == NULL) goto err; | ||
102 | if ((rnd=BN_new()) == NULL) goto err; | ||
103 | if (strong) | ||
104 | if ((t=BN_new()) == NULL) goto err; | ||
105 | loop: | ||
106 | /* make a random number and set the top and bottom bits */ | ||
107 | if (add == NULL) | ||
108 | { | ||
109 | if (!probable_prime(rnd,bits)) goto err; | ||
110 | } | ||
111 | else | ||
112 | { | ||
113 | if (strong) | ||
114 | { | ||
115 | if (!probable_prime_dh_strong(rnd,bits,add,rem,ctx)) | ||
116 | goto err; | ||
117 | } | ||
118 | else | ||
119 | { | ||
120 | if (!probable_prime_dh(rnd,bits,add,rem,ctx)) | ||
121 | goto err; | ||
122 | } | ||
123 | } | ||
124 | /* if (BN_mod_word(rnd,(BN_ULONG)3) == 1) goto loop; */ | ||
125 | if (callback != NULL) callback(0,c1++,cb_arg); | ||
126 | |||
127 | if (!strong) | ||
128 | { | ||
129 | i=BN_is_prime(rnd,BN_prime_checks,callback,ctx,cb_arg); | ||
130 | if (i == -1) goto err; | ||
131 | if (i == 0) goto loop; | ||
132 | } | ||
133 | else | ||
134 | { | ||
135 | /* for a strong prime generation, | ||
136 | * check that (p-1)/2 is prime. | ||
137 | * Since a prime is odd, We just | ||
138 | * need to divide by 2 */ | ||
139 | if (!BN_rshift1(t,rnd)) goto err; | ||
140 | |||
141 | for (i=0; i<BN_prime_checks; i++) | ||
142 | { | ||
143 | j=BN_is_prime(rnd,1,callback,ctx,cb_arg); | ||
144 | if (j == -1) goto err; | ||
145 | if (j == 0) goto loop; | ||
146 | |||
147 | j=BN_is_prime(t,1,callback,ctx,cb_arg); | ||
148 | if (j == -1) goto err; | ||
149 | if (j == 0) goto loop; | ||
150 | |||
151 | if (callback != NULL) callback(2,c1-1,cb_arg); | ||
152 | /* We have a strong prime test pass */ | ||
153 | } | ||
154 | } | ||
155 | /* we have a prime :-) */ | ||
156 | ret=rnd; | ||
157 | err: | ||
158 | if ((ret == NULL) && (rnd != NULL)) BN_free(rnd); | ||
159 | if (t != NULL) BN_free(t); | ||
160 | if (ctx != NULL) BN_CTX_free(ctx); | ||
161 | return(ret); | ||
162 | } | ||
163 | |||
164 | int BN_is_prime(a,checks,callback,ctx_passed,cb_arg) | ||
165 | BIGNUM *a; | ||
166 | int checks; | ||
167 | void (*callback)(P_I_I_P); | ||
168 | BN_CTX *ctx_passed; | ||
169 | char *cb_arg; | ||
170 | { | ||
171 | int i,j,c2=0,ret= -1; | ||
172 | BIGNUM *check; | ||
173 | BN_CTX *ctx=NULL,*ctx2=NULL; | ||
174 | BN_MONT_CTX *mont=NULL; | ||
175 | |||
176 | if (!BN_is_odd(a)) | ||
177 | return(0); | ||
178 | if (ctx_passed != NULL) | ||
179 | ctx=ctx_passed; | ||
180 | else | ||
181 | if ((ctx=BN_CTX_new()) == NULL) goto err; | ||
182 | |||
183 | if ((ctx2=BN_CTX_new()) == NULL) goto err; | ||
184 | if ((mont=BN_MONT_CTX_new()) == NULL) goto err; | ||
185 | |||
186 | check=ctx->bn[ctx->tos++]; | ||
187 | |||
188 | /* Setup the montgomery structure */ | ||
189 | if (!BN_MONT_CTX_set(mont,a,ctx2)) goto err; | ||
190 | |||
191 | for (i=0; i<checks; i++) | ||
192 | { | ||
193 | if (!BN_rand(check,BN_num_bits(a)-1,0,0)) goto err; | ||
194 | j=witness(check,a,ctx,ctx2,mont); | ||
195 | if (j == -1) goto err; | ||
196 | if (j) | ||
197 | { | ||
198 | ret=0; | ||
199 | goto err; | ||
200 | } | ||
201 | if (callback != NULL) callback(1,c2++,cb_arg); | ||
202 | } | ||
203 | ret=1; | ||
204 | err: | ||
205 | ctx->tos--; | ||
206 | if ((ctx_passed == NULL) && (ctx != NULL)) | ||
207 | BN_CTX_free(ctx); | ||
208 | if (ctx2 != NULL) | ||
209 | BN_CTX_free(ctx2); | ||
210 | if (mont != NULL) BN_MONT_CTX_free(mont); | ||
211 | |||
212 | return(ret); | ||
213 | } | ||
214 | |||
215 | #define RECP_MUL_MOD | ||
216 | |||
217 | static int witness(a,n,ctx,ctx2,mont) | ||
218 | BIGNUM *a; | ||
219 | BIGNUM *n; | ||
220 | BN_CTX *ctx,*ctx2; | ||
221 | BN_MONT_CTX *mont; | ||
222 | { | ||
223 | int k,i,ret= -1,good; | ||
224 | BIGNUM *d,*dd,*tmp,*d1,*d2,*n1; | ||
225 | BIGNUM *mont_one,*mont_n1,*mont_a; | ||
226 | |||
227 | d1=ctx->bn[ctx->tos]; | ||
228 | d2=ctx->bn[ctx->tos+1]; | ||
229 | n1=ctx->bn[ctx->tos+2]; | ||
230 | ctx->tos+=3; | ||
231 | |||
232 | mont_one=ctx2->bn[ctx2->tos]; | ||
233 | mont_n1=ctx2->bn[ctx2->tos+1]; | ||
234 | mont_a=ctx2->bn[ctx2->tos+2]; | ||
235 | ctx2->tos+=3; | ||
236 | |||
237 | d=d1; | ||
238 | dd=d2; | ||
239 | if (!BN_one(d)) goto err; | ||
240 | if (!BN_sub(n1,n,d)) goto err; /* n1=n-1; */ | ||
241 | k=BN_num_bits(n1); | ||
242 | |||
243 | if (!BN_to_montgomery(mont_one,BN_value_one(),mont,ctx2)) goto err; | ||
244 | if (!BN_to_montgomery(mont_n1,n1,mont,ctx2)) goto err; | ||
245 | if (!BN_to_montgomery(mont_a,a,mont,ctx2)) goto err; | ||
246 | |||
247 | BN_copy(d,mont_one); | ||
248 | for (i=k-1; i>=0; i--) | ||
249 | { | ||
250 | if ( (BN_cmp(d,mont_one) != 0) && | ||
251 | (BN_cmp(d,mont_n1) != 0)) | ||
252 | good=1; | ||
253 | else | ||
254 | good=0; | ||
255 | |||
256 | BN_mod_mul_montgomery(dd,d,d,mont,ctx2); | ||
257 | |||
258 | if (good && (BN_cmp(dd,mont_one) == 0)) | ||
259 | { | ||
260 | ret=1; | ||
261 | goto err; | ||
262 | } | ||
263 | if (BN_is_bit_set(n1,i)) | ||
264 | { | ||
265 | BN_mod_mul_montgomery(d,dd,mont_a,mont,ctx2); | ||
266 | } | ||
267 | else | ||
268 | { | ||
269 | tmp=d; | ||
270 | d=dd; | ||
271 | dd=tmp; | ||
272 | } | ||
273 | } | ||
274 | if (BN_cmp(d,mont_one) == 0) | ||
275 | i=0; | ||
276 | else i=1; | ||
277 | ret=i; | ||
278 | err: | ||
279 | ctx->tos-=3; | ||
280 | ctx2->tos-=3; | ||
281 | return(ret); | ||
282 | } | ||
283 | |||
284 | static int probable_prime(rnd, bits) | ||
285 | BIGNUM *rnd; | ||
286 | int bits; | ||
287 | { | ||
288 | int i; | ||
289 | MS_STATIC BN_ULONG mods[NUMPRIMES]; | ||
290 | BN_ULONG delta; | ||
291 | |||
292 | if (!BN_rand(rnd,bits,1,1)) return(0); | ||
293 | /* we now have a random number 'rand' to test. */ | ||
294 | for (i=1; i<NUMPRIMES; i++) | ||
295 | mods[i]=BN_mod_word(rnd,(BN_ULONG)primes[i]); | ||
296 | delta=0; | ||
297 | loop: for (i=1; i<NUMPRIMES; i++) | ||
298 | { | ||
299 | /* check that rnd is not a prime and also | ||
300 | * that gcd(rnd-1,primes) == 1 (except for 2) */ | ||
301 | if (((mods[i]+delta)%primes[i]) <= 1) | ||
302 | { | ||
303 | delta+=2; | ||
304 | /* perhaps need to check for overflow of | ||
305 | * delta (but delta can be upto 2^32) */ | ||
306 | goto loop; | ||
307 | } | ||
308 | } | ||
309 | if (!BN_add_word(rnd,delta)) return(0); | ||
310 | return(1); | ||
311 | } | ||
312 | |||
313 | static int probable_prime_dh(rnd, bits, add, rem,ctx) | ||
314 | BIGNUM *rnd; | ||
315 | int bits; | ||
316 | BIGNUM *add; | ||
317 | BIGNUM *rem; | ||
318 | BN_CTX *ctx; | ||
319 | { | ||
320 | int i,ret=0; | ||
321 | BIGNUM *t1; | ||
322 | |||
323 | t1=ctx->bn[ctx->tos++]; | ||
324 | |||
325 | if (!BN_rand(rnd,bits,0,1)) goto err; | ||
326 | |||
327 | /* we need ((rnd-rem) % add) == 0 */ | ||
328 | |||
329 | if (!BN_mod(t1,rnd,add,ctx)) goto err; | ||
330 | if (!BN_sub(rnd,rnd,t1)) goto err; | ||
331 | if (rem == NULL) | ||
332 | { if (!BN_add_word(rnd,1)) goto err; } | ||
333 | else | ||
334 | { if (!BN_add(rnd,rnd,rem)) goto err; } | ||
335 | |||
336 | /* we now have a random number 'rand' to test. */ | ||
337 | |||
338 | loop: for (i=1; i<NUMPRIMES; i++) | ||
339 | { | ||
340 | /* check that rnd is a prime */ | ||
341 | if (BN_mod_word(rnd,(BN_LONG)primes[i]) <= 1) | ||
342 | { | ||
343 | if (!BN_add(rnd,rnd,add)) goto err; | ||
344 | goto loop; | ||
345 | } | ||
346 | } | ||
347 | ret=1; | ||
348 | err: | ||
349 | ctx->tos--; | ||
350 | return(ret); | ||
351 | } | ||
352 | |||
353 | static int probable_prime_dh_strong(p, bits, padd, rem,ctx) | ||
354 | BIGNUM *p; | ||
355 | int bits; | ||
356 | BIGNUM *padd; | ||
357 | BIGNUM *rem; | ||
358 | BN_CTX *ctx; | ||
359 | { | ||
360 | int i,ret=0; | ||
361 | BIGNUM *t1,*qadd=NULL,*q=NULL; | ||
362 | |||
363 | bits--; | ||
364 | t1=ctx->bn[ctx->tos++]; | ||
365 | q=ctx->bn[ctx->tos++]; | ||
366 | qadd=ctx->bn[ctx->tos++]; | ||
367 | |||
368 | if (!BN_rshift1(qadd,padd)) goto err; | ||
369 | |||
370 | if (!BN_rand(q,bits,0,1)) goto err; | ||
371 | |||
372 | /* we need ((rnd-rem) % add) == 0 */ | ||
373 | if (!BN_mod(t1,q,qadd,ctx)) goto err; | ||
374 | if (!BN_sub(q,q,t1)) goto err; | ||
375 | if (rem == NULL) | ||
376 | { if (!BN_add_word(q,1)) goto err; } | ||
377 | else | ||
378 | { | ||
379 | if (!BN_rshift1(t1,rem)) goto err; | ||
380 | if (!BN_add(q,q,t1)) goto err; | ||
381 | } | ||
382 | |||
383 | /* we now have a random number 'rand' to test. */ | ||
384 | if (!BN_lshift1(p,q)) goto err; | ||
385 | if (!BN_add_word(p,1)) goto err; | ||
386 | |||
387 | loop: for (i=1; i<NUMPRIMES; i++) | ||
388 | { | ||
389 | /* check that p and q are prime */ | ||
390 | /* check that for p and q | ||
391 | * gcd(p-1,primes) == 1 (except for 2) */ | ||
392 | if ( (BN_mod_word(p,(BN_LONG)primes[i]) == 0) || | ||
393 | (BN_mod_word(q,(BN_LONG)primes[i]) == 0)) | ||
394 | { | ||
395 | if (!BN_add(p,p,padd)) goto err; | ||
396 | if (!BN_add(q,q,qadd)) goto err; | ||
397 | goto loop; | ||
398 | } | ||
399 | } | ||
400 | ret=1; | ||
401 | err: | ||
402 | ctx->tos-=3; | ||
403 | return(ret); | ||
404 | } | ||
405 | |||
406 | #if 0 | ||
407 | static int witness(a, n,ctx) | ||
408 | BIGNUM *a; | ||
409 | BIGNUM *n; | ||
410 | BN_CTX *ctx; | ||
411 | { | ||
412 | int k,i,nb,ret= -1; | ||
413 | BIGNUM *d,*dd,*tmp; | ||
414 | BIGNUM *d1,*d2,*x,*n1,*inv; | ||
415 | |||
416 | d1=ctx->bn[ctx->tos]; | ||
417 | d2=ctx->bn[ctx->tos+1]; | ||
418 | x=ctx->bn[ctx->tos+2]; | ||
419 | n1=ctx->bn[ctx->tos+3]; | ||
420 | inv=ctx->bn[ctx->tos+4]; | ||
421 | ctx->tos+=5; | ||
422 | |||
423 | d=d1; | ||
424 | dd=d2; | ||
425 | if (!BN_one(d)) goto err; | ||
426 | if (!BN_sub(n1,n,d)) goto err; /* n1=n-1; */ | ||
427 | k=BN_num_bits(n1); | ||
428 | |||
429 | /* i=BN_num_bits(n); */ | ||
430 | #ifdef RECP_MUL_MOD | ||
431 | nb=BN_reciprocal(inv,n,ctx); /**/ | ||
432 | if (nb == -1) goto err; | ||
433 | #endif | ||
434 | |||
435 | for (i=k-1; i>=0; i--) | ||
436 | { | ||
437 | if (BN_copy(x,d) == NULL) goto err; | ||
438 | #ifndef RECP_MUL_MOD | ||
439 | if (!BN_mod_mul(dd,d,d,n,ctx)) goto err; | ||
440 | #else | ||
441 | if (!BN_mod_mul_reciprocal(dd,d,d,n,inv,nb,ctx)) goto err; | ||
442 | #endif | ||
443 | if ( BN_is_one(dd) && | ||
444 | !BN_is_one(x) && | ||
445 | (BN_cmp(x,n1) != 0)) | ||
446 | { | ||
447 | ret=1; | ||
448 | goto err; | ||
449 | } | ||
450 | if (BN_is_bit_set(n1,i)) | ||
451 | { | ||
452 | #ifndef RECP_MUL_MOD | ||
453 | if (!BN_mod_mul(d,dd,a,n,ctx)) goto err; | ||
454 | #else | ||
455 | if (!BN_mod_mul_reciprocal(d,dd,a,n,inv,nb,ctx)) goto err; | ||
456 | #endif | ||
457 | } | ||
458 | else | ||
459 | { | ||
460 | tmp=d; | ||
461 | d=dd; | ||
462 | dd=tmp; | ||
463 | } | ||
464 | } | ||
465 | if (BN_is_one(d)) | ||
466 | i=0; | ||
467 | else i=1; | ||
468 | ret=i; | ||
469 | err: | ||
470 | ctx->tos-=5; | ||
471 | return(ret); | ||
472 | } | ||
473 | #endif | ||
diff --git a/src/lib/libcrypto/bn/bn_prime.h b/src/lib/libcrypto/bn/bn_prime.h new file mode 100644 index 0000000000..6fce0210cd --- /dev/null +++ b/src/lib/libcrypto/bn/bn_prime.h | |||
@@ -0,0 +1,325 @@ | |||
1 | /* crypto/bn/bn_prime.h */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #ifndef EIGHT_BIT | ||
60 | #define NUMPRIMES 2048 | ||
61 | #else | ||
62 | #define NUMPRIMES 54 | ||
63 | #endif | ||
64 | static unsigned int primes[NUMPRIMES]= | ||
65 | { | ||
66 | 2, 3, 5, 7, 11, 13, 17, 19, | ||
67 | 23, 29, 31, 37, 41, 43, 47, 53, | ||
68 | 59, 61, 67, 71, 73, 79, 83, 89, | ||
69 | 97, 101, 103, 107, 109, 113, 127, 131, | ||
70 | 137, 139, 149, 151, 157, 163, 167, 173, | ||
71 | 179, 181, 191, 193, 197, 199, 211, 223, | ||
72 | 227, 229, 233, 239, 241, 251, | ||
73 | #ifndef EIGHT_BIT | ||
74 | 257, 263, | ||
75 | 269, 271, 277, 281, 283, 293, 307, 311, | ||
76 | 313, 317, 331, 337, 347, 349, 353, 359, | ||
77 | 367, 373, 379, 383, 389, 397, 401, 409, | ||
78 | 419, 421, 431, 433, 439, 443, 449, 457, | ||
79 | 461, 463, 467, 479, 487, 491, 499, 503, | ||
80 | 509, 521, 523, 541, 547, 557, 563, 569, | ||
81 | 571, 577, 587, 593, 599, 601, 607, 613, | ||
82 | 617, 619, 631, 641, 643, 647, 653, 659, | ||
83 | 661, 673, 677, 683, 691, 701, 709, 719, | ||
84 | 727, 733, 739, 743, 751, 757, 761, 769, | ||
85 | 773, 787, 797, 809, 811, 821, 823, 827, | ||
86 | 829, 839, 853, 857, 859, 863, 877, 881, | ||
87 | 883, 887, 907, 911, 919, 929, 937, 941, | ||
88 | 947, 953, 967, 971, 977, 983, 991, 997, | ||
89 | 1009,1013,1019,1021,1031,1033,1039,1049, | ||
90 | 1051,1061,1063,1069,1087,1091,1093,1097, | ||
91 | 1103,1109,1117,1123,1129,1151,1153,1163, | ||
92 | 1171,1181,1187,1193,1201,1213,1217,1223, | ||
93 | 1229,1231,1237,1249,1259,1277,1279,1283, | ||
94 | 1289,1291,1297,1301,1303,1307,1319,1321, | ||
95 | 1327,1361,1367,1373,1381,1399,1409,1423, | ||
96 | 1427,1429,1433,1439,1447,1451,1453,1459, | ||
97 | 1471,1481,1483,1487,1489,1493,1499,1511, | ||
98 | 1523,1531,1543,1549,1553,1559,1567,1571, | ||
99 | 1579,1583,1597,1601,1607,1609,1613,1619, | ||
100 | 1621,1627,1637,1657,1663,1667,1669,1693, | ||
101 | 1697,1699,1709,1721,1723,1733,1741,1747, | ||
102 | 1753,1759,1777,1783,1787,1789,1801,1811, | ||
103 | 1823,1831,1847,1861,1867,1871,1873,1877, | ||
104 | 1879,1889,1901,1907,1913,1931,1933,1949, | ||
105 | 1951,1973,1979,1987,1993,1997,1999,2003, | ||
106 | 2011,2017,2027,2029,2039,2053,2063,2069, | ||
107 | 2081,2083,2087,2089,2099,2111,2113,2129, | ||
108 | 2131,2137,2141,2143,2153,2161,2179,2203, | ||
109 | 2207,2213,2221,2237,2239,2243,2251,2267, | ||
110 | 2269,2273,2281,2287,2293,2297,2309,2311, | ||
111 | 2333,2339,2341,2347,2351,2357,2371,2377, | ||
112 | 2381,2383,2389,2393,2399,2411,2417,2423, | ||
113 | 2437,2441,2447,2459,2467,2473,2477,2503, | ||
114 | 2521,2531,2539,2543,2549,2551,2557,2579, | ||
115 | 2591,2593,2609,2617,2621,2633,2647,2657, | ||
116 | 2659,2663,2671,2677,2683,2687,2689,2693, | ||
117 | 2699,2707,2711,2713,2719,2729,2731,2741, | ||
118 | 2749,2753,2767,2777,2789,2791,2797,2801, | ||
119 | 2803,2819,2833,2837,2843,2851,2857,2861, | ||
120 | 2879,2887,2897,2903,2909,2917,2927,2939, | ||
121 | 2953,2957,2963,2969,2971,2999,3001,3011, | ||
122 | 3019,3023,3037,3041,3049,3061,3067,3079, | ||
123 | 3083,3089,3109,3119,3121,3137,3163,3167, | ||
124 | 3169,3181,3187,3191,3203,3209,3217,3221, | ||
125 | 3229,3251,3253,3257,3259,3271,3299,3301, | ||
126 | 3307,3313,3319,3323,3329,3331,3343,3347, | ||
127 | 3359,3361,3371,3373,3389,3391,3407,3413, | ||
128 | 3433,3449,3457,3461,3463,3467,3469,3491, | ||
129 | 3499,3511,3517,3527,3529,3533,3539,3541, | ||
130 | 3547,3557,3559,3571,3581,3583,3593,3607, | ||
131 | 3613,3617,3623,3631,3637,3643,3659,3671, | ||
132 | 3673,3677,3691,3697,3701,3709,3719,3727, | ||
133 | 3733,3739,3761,3767,3769,3779,3793,3797, | ||
134 | 3803,3821,3823,3833,3847,3851,3853,3863, | ||
135 | 3877,3881,3889,3907,3911,3917,3919,3923, | ||
136 | 3929,3931,3943,3947,3967,3989,4001,4003, | ||
137 | 4007,4013,4019,4021,4027,4049,4051,4057, | ||
138 | 4073,4079,4091,4093,4099,4111,4127,4129, | ||
139 | 4133,4139,4153,4157,4159,4177,4201,4211, | ||
140 | 4217,4219,4229,4231,4241,4243,4253,4259, | ||
141 | 4261,4271,4273,4283,4289,4297,4327,4337, | ||
142 | 4339,4349,4357,4363,4373,4391,4397,4409, | ||
143 | 4421,4423,4441,4447,4451,4457,4463,4481, | ||
144 | 4483,4493,4507,4513,4517,4519,4523,4547, | ||
145 | 4549,4561,4567,4583,4591,4597,4603,4621, | ||
146 | 4637,4639,4643,4649,4651,4657,4663,4673, | ||
147 | 4679,4691,4703,4721,4723,4729,4733,4751, | ||
148 | 4759,4783,4787,4789,4793,4799,4801,4813, | ||
149 | 4817,4831,4861,4871,4877,4889,4903,4909, | ||
150 | 4919,4931,4933,4937,4943,4951,4957,4967, | ||
151 | 4969,4973,4987,4993,4999,5003,5009,5011, | ||
152 | 5021,5023,5039,5051,5059,5077,5081,5087, | ||
153 | 5099,5101,5107,5113,5119,5147,5153,5167, | ||
154 | 5171,5179,5189,5197,5209,5227,5231,5233, | ||
155 | 5237,5261,5273,5279,5281,5297,5303,5309, | ||
156 | 5323,5333,5347,5351,5381,5387,5393,5399, | ||
157 | 5407,5413,5417,5419,5431,5437,5441,5443, | ||
158 | 5449,5471,5477,5479,5483,5501,5503,5507, | ||
159 | 5519,5521,5527,5531,5557,5563,5569,5573, | ||
160 | 5581,5591,5623,5639,5641,5647,5651,5653, | ||
161 | 5657,5659,5669,5683,5689,5693,5701,5711, | ||
162 | 5717,5737,5741,5743,5749,5779,5783,5791, | ||
163 | 5801,5807,5813,5821,5827,5839,5843,5849, | ||
164 | 5851,5857,5861,5867,5869,5879,5881,5897, | ||
165 | 5903,5923,5927,5939,5953,5981,5987,6007, | ||
166 | 6011,6029,6037,6043,6047,6053,6067,6073, | ||
167 | 6079,6089,6091,6101,6113,6121,6131,6133, | ||
168 | 6143,6151,6163,6173,6197,6199,6203,6211, | ||
169 | 6217,6221,6229,6247,6257,6263,6269,6271, | ||
170 | 6277,6287,6299,6301,6311,6317,6323,6329, | ||
171 | 6337,6343,6353,6359,6361,6367,6373,6379, | ||
172 | 6389,6397,6421,6427,6449,6451,6469,6473, | ||
173 | 6481,6491,6521,6529,6547,6551,6553,6563, | ||
174 | 6569,6571,6577,6581,6599,6607,6619,6637, | ||
175 | 6653,6659,6661,6673,6679,6689,6691,6701, | ||
176 | 6703,6709,6719,6733,6737,6761,6763,6779, | ||
177 | 6781,6791,6793,6803,6823,6827,6829,6833, | ||
178 | 6841,6857,6863,6869,6871,6883,6899,6907, | ||
179 | 6911,6917,6947,6949,6959,6961,6967,6971, | ||
180 | 6977,6983,6991,6997,7001,7013,7019,7027, | ||
181 | 7039,7043,7057,7069,7079,7103,7109,7121, | ||
182 | 7127,7129,7151,7159,7177,7187,7193,7207, | ||
183 | 7211,7213,7219,7229,7237,7243,7247,7253, | ||
184 | 7283,7297,7307,7309,7321,7331,7333,7349, | ||
185 | 7351,7369,7393,7411,7417,7433,7451,7457, | ||
186 | 7459,7477,7481,7487,7489,7499,7507,7517, | ||
187 | 7523,7529,7537,7541,7547,7549,7559,7561, | ||
188 | 7573,7577,7583,7589,7591,7603,7607,7621, | ||
189 | 7639,7643,7649,7669,7673,7681,7687,7691, | ||
190 | 7699,7703,7717,7723,7727,7741,7753,7757, | ||
191 | 7759,7789,7793,7817,7823,7829,7841,7853, | ||
192 | 7867,7873,7877,7879,7883,7901,7907,7919, | ||
193 | 7927,7933,7937,7949,7951,7963,7993,8009, | ||
194 | 8011,8017,8039,8053,8059,8069,8081,8087, | ||
195 | 8089,8093,8101,8111,8117,8123,8147,8161, | ||
196 | 8167,8171,8179,8191,8209,8219,8221,8231, | ||
197 | 8233,8237,8243,8263,8269,8273,8287,8291, | ||
198 | 8293,8297,8311,8317,8329,8353,8363,8369, | ||
199 | 8377,8387,8389,8419,8423,8429,8431,8443, | ||
200 | 8447,8461,8467,8501,8513,8521,8527,8537, | ||
201 | 8539,8543,8563,8573,8581,8597,8599,8609, | ||
202 | 8623,8627,8629,8641,8647,8663,8669,8677, | ||
203 | 8681,8689,8693,8699,8707,8713,8719,8731, | ||
204 | 8737,8741,8747,8753,8761,8779,8783,8803, | ||
205 | 8807,8819,8821,8831,8837,8839,8849,8861, | ||
206 | 8863,8867,8887,8893,8923,8929,8933,8941, | ||
207 | 8951,8963,8969,8971,8999,9001,9007,9011, | ||
208 | 9013,9029,9041,9043,9049,9059,9067,9091, | ||
209 | 9103,9109,9127,9133,9137,9151,9157,9161, | ||
210 | 9173,9181,9187,9199,9203,9209,9221,9227, | ||
211 | 9239,9241,9257,9277,9281,9283,9293,9311, | ||
212 | 9319,9323,9337,9341,9343,9349,9371,9377, | ||
213 | 9391,9397,9403,9413,9419,9421,9431,9433, | ||
214 | 9437,9439,9461,9463,9467,9473,9479,9491, | ||
215 | 9497,9511,9521,9533,9539,9547,9551,9587, | ||
216 | 9601,9613,9619,9623,9629,9631,9643,9649, | ||
217 | 9661,9677,9679,9689,9697,9719,9721,9733, | ||
218 | 9739,9743,9749,9767,9769,9781,9787,9791, | ||
219 | 9803,9811,9817,9829,9833,9839,9851,9857, | ||
220 | 9859,9871,9883,9887,9901,9907,9923,9929, | ||
221 | 9931,9941,9949,9967,9973,10007,10009,10037, | ||
222 | 10039,10061,10067,10069,10079,10091,10093,10099, | ||
223 | 10103,10111,10133,10139,10141,10151,10159,10163, | ||
224 | 10169,10177,10181,10193,10211,10223,10243,10247, | ||
225 | 10253,10259,10267,10271,10273,10289,10301,10303, | ||
226 | 10313,10321,10331,10333,10337,10343,10357,10369, | ||
227 | 10391,10399,10427,10429,10433,10453,10457,10459, | ||
228 | 10463,10477,10487,10499,10501,10513,10529,10531, | ||
229 | 10559,10567,10589,10597,10601,10607,10613,10627, | ||
230 | 10631,10639,10651,10657,10663,10667,10687,10691, | ||
231 | 10709,10711,10723,10729,10733,10739,10753,10771, | ||
232 | 10781,10789,10799,10831,10837,10847,10853,10859, | ||
233 | 10861,10867,10883,10889,10891,10903,10909,10937, | ||
234 | 10939,10949,10957,10973,10979,10987,10993,11003, | ||
235 | 11027,11047,11057,11059,11069,11071,11083,11087, | ||
236 | 11093,11113,11117,11119,11131,11149,11159,11161, | ||
237 | 11171,11173,11177,11197,11213,11239,11243,11251, | ||
238 | 11257,11261,11273,11279,11287,11299,11311,11317, | ||
239 | 11321,11329,11351,11353,11369,11383,11393,11399, | ||
240 | 11411,11423,11437,11443,11447,11467,11471,11483, | ||
241 | 11489,11491,11497,11503,11519,11527,11549,11551, | ||
242 | 11579,11587,11593,11597,11617,11621,11633,11657, | ||
243 | 11677,11681,11689,11699,11701,11717,11719,11731, | ||
244 | 11743,11777,11779,11783,11789,11801,11807,11813, | ||
245 | 11821,11827,11831,11833,11839,11863,11867,11887, | ||
246 | 11897,11903,11909,11923,11927,11933,11939,11941, | ||
247 | 11953,11959,11969,11971,11981,11987,12007,12011, | ||
248 | 12037,12041,12043,12049,12071,12073,12097,12101, | ||
249 | 12107,12109,12113,12119,12143,12149,12157,12161, | ||
250 | 12163,12197,12203,12211,12227,12239,12241,12251, | ||
251 | 12253,12263,12269,12277,12281,12289,12301,12323, | ||
252 | 12329,12343,12347,12373,12377,12379,12391,12401, | ||
253 | 12409,12413,12421,12433,12437,12451,12457,12473, | ||
254 | 12479,12487,12491,12497,12503,12511,12517,12527, | ||
255 | 12539,12541,12547,12553,12569,12577,12583,12589, | ||
256 | 12601,12611,12613,12619,12637,12641,12647,12653, | ||
257 | 12659,12671,12689,12697,12703,12713,12721,12739, | ||
258 | 12743,12757,12763,12781,12791,12799,12809,12821, | ||
259 | 12823,12829,12841,12853,12889,12893,12899,12907, | ||
260 | 12911,12917,12919,12923,12941,12953,12959,12967, | ||
261 | 12973,12979,12983,13001,13003,13007,13009,13033, | ||
262 | 13037,13043,13049,13063,13093,13099,13103,13109, | ||
263 | 13121,13127,13147,13151,13159,13163,13171,13177, | ||
264 | 13183,13187,13217,13219,13229,13241,13249,13259, | ||
265 | 13267,13291,13297,13309,13313,13327,13331,13337, | ||
266 | 13339,13367,13381,13397,13399,13411,13417,13421, | ||
267 | 13441,13451,13457,13463,13469,13477,13487,13499, | ||
268 | 13513,13523,13537,13553,13567,13577,13591,13597, | ||
269 | 13613,13619,13627,13633,13649,13669,13679,13681, | ||
270 | 13687,13691,13693,13697,13709,13711,13721,13723, | ||
271 | 13729,13751,13757,13759,13763,13781,13789,13799, | ||
272 | 13807,13829,13831,13841,13859,13873,13877,13879, | ||
273 | 13883,13901,13903,13907,13913,13921,13931,13933, | ||
274 | 13963,13967,13997,13999,14009,14011,14029,14033, | ||
275 | 14051,14057,14071,14081,14083,14087,14107,14143, | ||
276 | 14149,14153,14159,14173,14177,14197,14207,14221, | ||
277 | 14243,14249,14251,14281,14293,14303,14321,14323, | ||
278 | 14327,14341,14347,14369,14387,14389,14401,14407, | ||
279 | 14411,14419,14423,14431,14437,14447,14449,14461, | ||
280 | 14479,14489,14503,14519,14533,14537,14543,14549, | ||
281 | 14551,14557,14561,14563,14591,14593,14621,14627, | ||
282 | 14629,14633,14639,14653,14657,14669,14683,14699, | ||
283 | 14713,14717,14723,14731,14737,14741,14747,14753, | ||
284 | 14759,14767,14771,14779,14783,14797,14813,14821, | ||
285 | 14827,14831,14843,14851,14867,14869,14879,14887, | ||
286 | 14891,14897,14923,14929,14939,14947,14951,14957, | ||
287 | 14969,14983,15013,15017,15031,15053,15061,15073, | ||
288 | 15077,15083,15091,15101,15107,15121,15131,15137, | ||
289 | 15139,15149,15161,15173,15187,15193,15199,15217, | ||
290 | 15227,15233,15241,15259,15263,15269,15271,15277, | ||
291 | 15287,15289,15299,15307,15313,15319,15329,15331, | ||
292 | 15349,15359,15361,15373,15377,15383,15391,15401, | ||
293 | 15413,15427,15439,15443,15451,15461,15467,15473, | ||
294 | 15493,15497,15511,15527,15541,15551,15559,15569, | ||
295 | 15581,15583,15601,15607,15619,15629,15641,15643, | ||
296 | 15647,15649,15661,15667,15671,15679,15683,15727, | ||
297 | 15731,15733,15737,15739,15749,15761,15767,15773, | ||
298 | 15787,15791,15797,15803,15809,15817,15823,15859, | ||
299 | 15877,15881,15887,15889,15901,15907,15913,15919, | ||
300 | 15923,15937,15959,15971,15973,15991,16001,16007, | ||
301 | 16033,16057,16061,16063,16067,16069,16073,16087, | ||
302 | 16091,16097,16103,16111,16127,16139,16141,16183, | ||
303 | 16187,16189,16193,16217,16223,16229,16231,16249, | ||
304 | 16253,16267,16273,16301,16319,16333,16339,16349, | ||
305 | 16361,16363,16369,16381,16411,16417,16421,16427, | ||
306 | 16433,16447,16451,16453,16477,16481,16487,16493, | ||
307 | 16519,16529,16547,16553,16561,16567,16573,16603, | ||
308 | 16607,16619,16631,16633,16649,16651,16657,16661, | ||
309 | 16673,16691,16693,16699,16703,16729,16741,16747, | ||
310 | 16759,16763,16787,16811,16823,16829,16831,16843, | ||
311 | 16871,16879,16883,16889,16901,16903,16921,16927, | ||
312 | 16931,16937,16943,16963,16979,16981,16987,16993, | ||
313 | 17011,17021,17027,17029,17033,17041,17047,17053, | ||
314 | 17077,17093,17099,17107,17117,17123,17137,17159, | ||
315 | 17167,17183,17189,17191,17203,17207,17209,17231, | ||
316 | 17239,17257,17291,17293,17299,17317,17321,17327, | ||
317 | 17333,17341,17351,17359,17377,17383,17387,17389, | ||
318 | 17393,17401,17417,17419,17431,17443,17449,17467, | ||
319 | 17471,17477,17483,17489,17491,17497,17509,17519, | ||
320 | 17539,17551,17569,17573,17579,17581,17597,17599, | ||
321 | 17609,17623,17627,17657,17659,17669,17681,17683, | ||
322 | 17707,17713,17729,17737,17747,17749,17761,17783, | ||
323 | 17789,17791,17807,17827,17837,17839,17851,17863, | ||
324 | #endif | ||
325 | }; | ||
diff --git a/src/lib/libcrypto/bn/bn_prime.pl b/src/lib/libcrypto/bn/bn_prime.pl new file mode 100644 index 0000000000..1b00c21a77 --- /dev/null +++ b/src/lib/libcrypto/bn/bn_prime.pl | |||
@@ -0,0 +1,56 @@ | |||
1 | #!/usr/bin/perl | ||
2 | # bn_prime.pl | ||
3 | |||
4 | $num=2048; | ||
5 | $num=$ARGV[0] if ($#ARGV >= 0); | ||
6 | |||
7 | push(@primes,2); | ||
8 | $p=1; | ||
9 | loop: while ($#primes < $num-1) | ||
10 | { | ||
11 | $p+=2; | ||
12 | $s=int(sqrt($p)); | ||
13 | |||
14 | for ($i=0; $primes[$i]<=$s; $i++) | ||
15 | { | ||
16 | next loop if (($p%$primes[$i]) == 0); | ||
17 | } | ||
18 | push(@primes,$p); | ||
19 | } | ||
20 | |||
21 | print <<"EOF"; | ||
22 | /* Auto generated by bn_prime.pl */ | ||
23 | /* Copyright (C) 1995-1997 Eric Young (eay\@mincom.oz.au). | ||
24 | * All rights reserved. | ||
25 | * Copyright remains Eric Young's, and as such any Copyright notices in | ||
26 | * the code are not to be removed. | ||
27 | * See the COPYRIGHT file in the SSLeay distribution for more details. | ||
28 | */ | ||
29 | |||
30 | EOF | ||
31 | |||
32 | for ($i=0; $i <= $#primes; $i++) | ||
33 | { | ||
34 | if ($primes[$i] > 256) | ||
35 | { | ||
36 | $eight=$i; | ||
37 | last; | ||
38 | } | ||
39 | } | ||
40 | |||
41 | printf "#ifndef EIGHT_BIT\n"; | ||
42 | printf "#define NUMPRIMES %d\n",$num; | ||
43 | printf "#else\n"; | ||
44 | printf "#define NUMPRIMES %d\n",$eight; | ||
45 | printf "#endif\n"; | ||
46 | print "static unsigned int primes[NUMPRIMES]=\n\t{\n\t"; | ||
47 | $init=0; | ||
48 | for ($i=0; $i <= $#primes; $i++) | ||
49 | { | ||
50 | printf "\n#ifndef EIGHT_BIT\n\t" if ($primes[$i] > 256) && !($init++); | ||
51 | printf("\n\t") if (($i%8) == 0) && ($i != 0); | ||
52 | printf("%4d,",$primes[$i]); | ||
53 | } | ||
54 | print "\n#endif\n\t};\n"; | ||
55 | |||
56 | |||
diff --git a/src/lib/libcrypto/bn/bn_print.c b/src/lib/libcrypto/bn/bn_print.c new file mode 100644 index 0000000000..2bcc11c852 --- /dev/null +++ b/src/lib/libcrypto/bn/bn_print.c | |||
@@ -0,0 +1,333 @@ | |||
1 | /* crypto/bn/bn_print.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include <ctype.h> | ||
61 | #include "cryptlib.h" | ||
62 | #include "buffer.h" | ||
63 | #include "bn_lcl.h" | ||
64 | |||
65 | static char *Hex="0123456789ABCDEF"; | ||
66 | |||
67 | /* Must 'Free' the returned data */ | ||
68 | char *BN_bn2hex(a) | ||
69 | BIGNUM *a; | ||
70 | { | ||
71 | int i,j,v,z=0; | ||
72 | char *buf; | ||
73 | char *p; | ||
74 | |||
75 | buf=(char *)Malloc(a->top*BN_BYTES*2+2); | ||
76 | if (buf == NULL) | ||
77 | { | ||
78 | BNerr(BN_F_BN_BN2HEX,ERR_R_MALLOC_FAILURE); | ||
79 | goto err; | ||
80 | } | ||
81 | p=buf; | ||
82 | if (a->neg) *(p++)='-'; | ||
83 | if (a->top == 0) *(p++)='0'; | ||
84 | for (i=a->top-1; i >=0; i--) | ||
85 | { | ||
86 | for (j=BN_BITS2-8; j >= 0; j-=8) | ||
87 | { | ||
88 | /* strip leading zeros */ | ||
89 | v=((int)(a->d[i]>>(long)j))&0xff; | ||
90 | if (z || (v != 0)) | ||
91 | { | ||
92 | *(p++)=Hex[v>>4]; | ||
93 | *(p++)=Hex[v&0x0f]; | ||
94 | z=1; | ||
95 | } | ||
96 | } | ||
97 | } | ||
98 | *p='\0'; | ||
99 | err: | ||
100 | return(buf); | ||
101 | } | ||
102 | |||
103 | /* Must 'Free' the returned data */ | ||
104 | char *BN_bn2dec(a) | ||
105 | BIGNUM *a; | ||
106 | { | ||
107 | int i=0,num; | ||
108 | char *buf=NULL; | ||
109 | char *p; | ||
110 | BIGNUM *t=NULL; | ||
111 | BN_ULONG *bn_data=NULL,*lp; | ||
112 | |||
113 | i=BN_num_bits(a)*3; | ||
114 | num=(i/10+i/1000+3)+1; | ||
115 | bn_data=(BN_ULONG *)Malloc((num/BN_DEC_NUM+1)*sizeof(BN_ULONG)); | ||
116 | buf=(char *)Malloc(num+3); | ||
117 | if ((buf == NULL) || (bn_data == NULL)) | ||
118 | { | ||
119 | BNerr(BN_F_BN_BN2DEC,ERR_R_MALLOC_FAILURE); | ||
120 | goto err; | ||
121 | } | ||
122 | if ((t=BN_dup(a)) == NULL) goto err; | ||
123 | |||
124 | p=buf; | ||
125 | lp=bn_data; | ||
126 | if (t->neg) *(p++)='-'; | ||
127 | if (t->top == 0) | ||
128 | { | ||
129 | *(p++)='0'; | ||
130 | *(p++)='\0'; | ||
131 | } | ||
132 | else | ||
133 | { | ||
134 | i=0; | ||
135 | while (!BN_is_zero(t)) | ||
136 | { | ||
137 | *lp=BN_div_word(t,BN_DEC_CONV); | ||
138 | lp++; | ||
139 | } | ||
140 | lp--; | ||
141 | /* We now have a series of blocks, BN_DEC_NUM chars | ||
142 | * in length, where the last one needs trucation. | ||
143 | * The blocks need to be reversed in order. */ | ||
144 | sprintf(p,BN_DEC_FMT1,*lp); | ||
145 | while (*p) p++; | ||
146 | while (lp != bn_data) | ||
147 | { | ||
148 | lp--; | ||
149 | sprintf(p,BN_DEC_FMT2,*lp); | ||
150 | while (*p) p++; | ||
151 | } | ||
152 | } | ||
153 | err: | ||
154 | if (bn_data != NULL) Free(bn_data); | ||
155 | if (t != NULL) BN_free(t); | ||
156 | return(buf); | ||
157 | } | ||
158 | |||
159 | int BN_hex2bn(bn,a) | ||
160 | BIGNUM **bn; | ||
161 | char *a; | ||
162 | { | ||
163 | BIGNUM *ret=NULL; | ||
164 | BN_ULONG l=0; | ||
165 | int neg=0,h,m,i,j,k,c; | ||
166 | int num; | ||
167 | |||
168 | if ((a == NULL) || (*a == '\0')) return(0); | ||
169 | |||
170 | if (*a == '-') { neg=1; a++; } | ||
171 | |||
172 | for (i=0; isxdigit(a[i]); i++) | ||
173 | ; | ||
174 | |||
175 | num=i+neg; | ||
176 | if (bn == NULL) return(num); | ||
177 | |||
178 | /* a is the start of the hex digets, and it is 'i' long */ | ||
179 | if (*bn == NULL) | ||
180 | { | ||
181 | if ((ret=BN_new()) == NULL) return(0); | ||
182 | } | ||
183 | else | ||
184 | { | ||
185 | ret= *bn; | ||
186 | BN_zero(ret); | ||
187 | } | ||
188 | |||
189 | /* i is the number of hex digests; */ | ||
190 | if (bn_expand(ret,i*4) == NULL) goto err; | ||
191 | |||
192 | j=i; /* least significate 'hex' */ | ||
193 | m=0; | ||
194 | h=0; | ||
195 | while (j > 0) | ||
196 | { | ||
197 | m=((BN_BYTES*2) <= j)?(BN_BYTES*2):j; | ||
198 | l=0; | ||
199 | for (;;) | ||
200 | { | ||
201 | c=a[j-m]; | ||
202 | if ((c >= '0') && (c <= '9')) k=c-'0'; | ||
203 | else if ((c >= 'a') && (c <= 'f')) k=c-'a'+10; | ||
204 | else if ((c >= 'A') && (c <= 'F')) k=c-'A'+10; | ||
205 | else k=0; /* paranoia */ | ||
206 | l=(l<<4)|k; | ||
207 | |||
208 | if (--m <= 0) | ||
209 | { | ||
210 | ret->d[h++]=l; | ||
211 | break; | ||
212 | } | ||
213 | } | ||
214 | j-=(BN_BYTES*2); | ||
215 | } | ||
216 | ret->top=h; | ||
217 | bn_fix_top(ret); | ||
218 | ret->neg=neg; | ||
219 | |||
220 | *bn=ret; | ||
221 | return(num); | ||
222 | err: | ||
223 | if (*bn == NULL) BN_free(ret); | ||
224 | return(0); | ||
225 | } | ||
226 | |||
227 | int BN_dec2bn(bn,a) | ||
228 | BIGNUM **bn; | ||
229 | char *a; | ||
230 | { | ||
231 | BIGNUM *ret=NULL; | ||
232 | BN_ULONG l=0; | ||
233 | int neg=0,i,j; | ||
234 | int num; | ||
235 | |||
236 | if ((a == NULL) || (*a == '\0')) return(0); | ||
237 | if (*a == '-') { neg=1; a++; } | ||
238 | |||
239 | for (i=0; isdigit(a[i]); i++) | ||
240 | ; | ||
241 | |||
242 | num=i+neg; | ||
243 | if (bn == NULL) return(num); | ||
244 | |||
245 | /* a is the start of the digets, and it is 'i' long. | ||
246 | * We chop it into BN_DEC_NUM digets at a time */ | ||
247 | if (*bn == NULL) | ||
248 | { | ||
249 | if ((ret=BN_new()) == NULL) return(0); | ||
250 | } | ||
251 | else | ||
252 | { | ||
253 | ret= *bn; | ||
254 | BN_zero(ret); | ||
255 | } | ||
256 | |||
257 | /* i is the number of digests, a bit of an over expand; */ | ||
258 | if (bn_expand(ret,i*4) == NULL) goto err; | ||
259 | |||
260 | j=BN_DEC_NUM-(i%BN_DEC_NUM); | ||
261 | if (j == BN_DEC_NUM) j=0; | ||
262 | l=0; | ||
263 | while (*a) | ||
264 | { | ||
265 | l*=10; | ||
266 | l+= *a-'0'; | ||
267 | a++; | ||
268 | if (++j == BN_DEC_NUM) | ||
269 | { | ||
270 | BN_mul_word(ret,BN_DEC_CONV); | ||
271 | BN_add_word(ret,l); | ||
272 | l=0; | ||
273 | j=0; | ||
274 | } | ||
275 | } | ||
276 | ret->neg=neg; | ||
277 | |||
278 | bn_fix_top(ret); | ||
279 | *bn=ret; | ||
280 | return(num); | ||
281 | err: | ||
282 | if (*bn == NULL) BN_free(ret); | ||
283 | return(0); | ||
284 | } | ||
285 | |||
286 | #ifndef NO_BIO | ||
287 | |||
288 | #ifndef NO_FP_API | ||
289 | int BN_print_fp(fp, a) | ||
290 | FILE *fp; | ||
291 | BIGNUM *a; | ||
292 | { | ||
293 | BIO *b; | ||
294 | int ret; | ||
295 | |||
296 | if ((b=BIO_new(BIO_s_file())) == NULL) | ||
297 | return(0); | ||
298 | BIO_set_fp(b,fp,BIO_NOCLOSE); | ||
299 | ret=BN_print(b,a); | ||
300 | BIO_free(b); | ||
301 | return(ret); | ||
302 | } | ||
303 | #endif | ||
304 | |||
305 | int BN_print(bp, a) | ||
306 | BIO *bp; | ||
307 | BIGNUM *a; | ||
308 | { | ||
309 | int i,j,v,z=0; | ||
310 | int ret=0; | ||
311 | |||
312 | if ((a->neg) && (BIO_write(bp,"-",1) != 1)) goto end; | ||
313 | if ((a->top == 0) && (BIO_write(bp,"0",1) != 1)) goto end; | ||
314 | for (i=a->top-1; i >=0; i--) | ||
315 | { | ||
316 | for (j=BN_BITS2-4; j >= 0; j-=4) | ||
317 | { | ||
318 | /* strip leading zeros */ | ||
319 | v=((int)(a->d[i]>>(long)j))&0x0f; | ||
320 | if (z || (v != 0)) | ||
321 | { | ||
322 | if (BIO_write(bp,&(Hex[v]),1) != 1) | ||
323 | goto end; | ||
324 | z=1; | ||
325 | } | ||
326 | } | ||
327 | } | ||
328 | ret=1; | ||
329 | end: | ||
330 | return(ret); | ||
331 | } | ||
332 | |||
333 | #endif | ||
diff --git a/src/lib/libcrypto/bn/bn_rand.c b/src/lib/libcrypto/bn/bn_rand.c new file mode 100644 index 0000000000..75b6b0493b --- /dev/null +++ b/src/lib/libcrypto/bn/bn_rand.c | |||
@@ -0,0 +1,121 @@ | |||
1 | /* crypto/bn/bn_rand.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include <time.h> | ||
61 | #include "cryptlib.h" | ||
62 | #include "bn_lcl.h" | ||
63 | #include "rand.h" | ||
64 | |||
65 | int BN_rand(rnd, bits, top, bottom) | ||
66 | BIGNUM *rnd; | ||
67 | int bits; | ||
68 | int top; | ||
69 | int bottom; | ||
70 | { | ||
71 | unsigned char *buf=NULL; | ||
72 | int ret=0,bit,bytes,mask; | ||
73 | time_t tim; | ||
74 | |||
75 | bytes=(bits+7)/8; | ||
76 | bit=(bits-1)%8; | ||
77 | mask=0xff<<bit; | ||
78 | |||
79 | buf=(unsigned char *)Malloc(bytes); | ||
80 | if (buf == NULL) | ||
81 | { | ||
82 | BNerr(BN_F_BN_RAND,ERR_R_MALLOC_FAILURE); | ||
83 | goto err; | ||
84 | } | ||
85 | |||
86 | /* make a random number and set the top and bottom bits */ | ||
87 | time(&tim); | ||
88 | RAND_seed((unsigned char *)&tim,sizeof(tim)); | ||
89 | |||
90 | RAND_bytes(buf,(int)bytes); | ||
91 | if (top) | ||
92 | { | ||
93 | if (bit == 0) | ||
94 | { | ||
95 | buf[0]=1; | ||
96 | buf[1]|=0x80; | ||
97 | } | ||
98 | else | ||
99 | { | ||
100 | buf[0]|=(3<<(bit-1)); | ||
101 | buf[0]&= ~(mask<<1); | ||
102 | } | ||
103 | } | ||
104 | else | ||
105 | { | ||
106 | buf[0]|=(1<<bit); | ||
107 | buf[0]&= ~(mask<<1); | ||
108 | } | ||
109 | if (bottom) /* set bottom bits to whatever odd is */ | ||
110 | buf[bytes-1]|=1; | ||
111 | if (!BN_bin2bn(buf,bytes,rnd)) goto err; | ||
112 | ret=1; | ||
113 | err: | ||
114 | if (buf != NULL) | ||
115 | { | ||
116 | memset(buf,0,bytes); | ||
117 | Free(buf); | ||
118 | } | ||
119 | return(ret); | ||
120 | } | ||
121 | |||
diff --git a/src/lib/libcrypto/bn/bn_recp.c b/src/lib/libcrypto/bn/bn_recp.c new file mode 100644 index 0000000000..72cd69d3fc --- /dev/null +++ b/src/lib/libcrypto/bn/bn_recp.c | |||
@@ -0,0 +1,125 @@ | |||
1 | /* crypto/bn/bn_recp.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include "cryptlib.h" | ||
61 | #include "bn_lcl.h" | ||
62 | |||
63 | int BN_mod_mul_reciprocal(r, x, y, m, i, nb, ctx) | ||
64 | BIGNUM *r; | ||
65 | BIGNUM *x; | ||
66 | BIGNUM *y; | ||
67 | BIGNUM *m; | ||
68 | BIGNUM *i; | ||
69 | int nb; | ||
70 | BN_CTX *ctx; | ||
71 | { | ||
72 | int ret=0,j; | ||
73 | BIGNUM *a,*b,*c,*d; | ||
74 | |||
75 | a=ctx->bn[ctx->tos++]; | ||
76 | b=ctx->bn[ctx->tos++]; | ||
77 | c=ctx->bn[ctx->tos++]; | ||
78 | d=ctx->bn[ctx->tos++]; | ||
79 | |||
80 | if (x == y) | ||
81 | { if (!BN_sqr(a,x,ctx)) goto err; } | ||
82 | else | ||
83 | { if (!BN_mul(a,x,y)) goto err; } | ||
84 | if (!BN_rshift(d,a,nb)) goto err; | ||
85 | if (!BN_mul(b,d,i)) goto err; | ||
86 | if (!BN_rshift(c,b,nb)) goto err; | ||
87 | if (!BN_mul(b,m,c)) goto err; | ||
88 | if (!BN_sub(r,a,b)) goto err; | ||
89 | j=0; | ||
90 | while (BN_cmp(r,m) >= 0) | ||
91 | { | ||
92 | if (j++ > 2) | ||
93 | { | ||
94 | BNerr(BN_F_BN_MOD_MUL_RECIPROCAL,BN_R_BAD_RECIPROCAL); | ||
95 | goto err; | ||
96 | } | ||
97 | if (!BN_sub(r,r,m)) goto err; | ||
98 | } | ||
99 | |||
100 | ret=1; | ||
101 | err: | ||
102 | ctx->tos-=4; | ||
103 | return(ret); | ||
104 | } | ||
105 | |||
106 | int BN_reciprocal(r, m,ctx) | ||
107 | BIGNUM *r; | ||
108 | BIGNUM *m; | ||
109 | BN_CTX *ctx; | ||
110 | { | ||
111 | int nm,ret= -1; | ||
112 | BIGNUM *t; | ||
113 | |||
114 | t=ctx->bn[ctx->tos++]; | ||
115 | |||
116 | nm=BN_num_bits(m); | ||
117 | if (!BN_lshift(t,BN_value_one(),nm*2)) goto err; | ||
118 | |||
119 | if (!BN_div(r,NULL,t,m,ctx)) goto err; | ||
120 | ret=nm; | ||
121 | err: | ||
122 | ctx->tos--; | ||
123 | return(ret); | ||
124 | } | ||
125 | |||
diff --git a/src/lib/libcrypto/bn/bn_shift.c b/src/lib/libcrypto/bn/bn_shift.c new file mode 100644 index 0000000000..944bf1794b --- /dev/null +++ b/src/lib/libcrypto/bn/bn_shift.c | |||
@@ -0,0 +1,210 @@ | |||
1 | /* crypto/bn/bn_shift.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include "cryptlib.h" | ||
61 | #include "bn_lcl.h" | ||
62 | |||
63 | int BN_lshift1(r, a) | ||
64 | BIGNUM *r; | ||
65 | BIGNUM *a; | ||
66 | { | ||
67 | register BN_ULONG *ap,*rp,t,c; | ||
68 | int i; | ||
69 | |||
70 | if (r != a) | ||
71 | { | ||
72 | r->neg=a->neg; | ||
73 | if (bn_wexpand(r,a->top+1) == NULL) return(0); | ||
74 | r->top=a->top; | ||
75 | } | ||
76 | else | ||
77 | { | ||
78 | if (bn_wexpand(r,a->top+1) == NULL) return(0); | ||
79 | } | ||
80 | ap=a->d; | ||
81 | rp=r->d; | ||
82 | c=0; | ||
83 | for (i=0; i<a->top; i++) | ||
84 | { | ||
85 | t= *(ap++); | ||
86 | *(rp++)=((t<<1)|c)&BN_MASK2; | ||
87 | c=(t & BN_TBIT)?1:0; | ||
88 | } | ||
89 | if (c) | ||
90 | { | ||
91 | *rp=1; | ||
92 | r->top++; | ||
93 | } | ||
94 | return(1); | ||
95 | } | ||
96 | |||
97 | int BN_rshift1(r, a) | ||
98 | BIGNUM *r; | ||
99 | BIGNUM *a; | ||
100 | { | ||
101 | BN_ULONG *ap,*rp,t,c; | ||
102 | int i; | ||
103 | |||
104 | if (BN_is_zero(a)) | ||
105 | { | ||
106 | BN_zero(r); | ||
107 | return(1); | ||
108 | } | ||
109 | if (a != r) | ||
110 | { | ||
111 | if (bn_wexpand(r,a->top) == NULL) return(0); | ||
112 | r->top=a->top; | ||
113 | r->neg=a->neg; | ||
114 | } | ||
115 | ap=a->d; | ||
116 | rp=r->d; | ||
117 | c=0; | ||
118 | for (i=a->top-1; i>=0; i--) | ||
119 | { | ||
120 | t=ap[i]; | ||
121 | rp[i]=((t>>1)&BN_MASK2)|c; | ||
122 | c=(t&1)?BN_TBIT:0; | ||
123 | } | ||
124 | bn_fix_top(r); | ||
125 | return(1); | ||
126 | } | ||
127 | |||
128 | int BN_lshift(r, a, n) | ||
129 | BIGNUM *r; | ||
130 | BIGNUM *a; | ||
131 | int n; | ||
132 | { | ||
133 | int i,nw,lb,rb; | ||
134 | BN_ULONG *t,*f; | ||
135 | BN_ULONG l; | ||
136 | |||
137 | r->neg=a->neg; | ||
138 | if (bn_wexpand(r,a->top+(n/BN_BITS2)+1) == NULL) return(0); | ||
139 | nw=n/BN_BITS2; | ||
140 | lb=n%BN_BITS2; | ||
141 | rb=BN_BITS2-lb; | ||
142 | f=a->d; | ||
143 | t=r->d; | ||
144 | t[a->top+nw]=0; | ||
145 | if (lb == 0) | ||
146 | for (i=a->top-1; i>=0; i--) | ||
147 | t[nw+i]=f[i]; | ||
148 | else | ||
149 | for (i=a->top-1; i>=0; i--) | ||
150 | { | ||
151 | l=f[i]; | ||
152 | t[nw+i+1]|=(l>>rb)&BN_MASK2; | ||
153 | t[nw+i]=(l<<lb)&BN_MASK2; | ||
154 | } | ||
155 | memset(t,0,nw*sizeof(t[0])); | ||
156 | /* for (i=0; i<nw; i++) | ||
157 | t[i]=0;*/ | ||
158 | r->top=a->top+nw+1; | ||
159 | bn_fix_top(r); | ||
160 | return(1); | ||
161 | } | ||
162 | |||
163 | int BN_rshift(r, a, n) | ||
164 | BIGNUM *r; | ||
165 | BIGNUM *a; | ||
166 | int n; | ||
167 | { | ||
168 | int i,j,nw,lb,rb; | ||
169 | BN_ULONG *t,*f; | ||
170 | BN_ULONG l,tmp; | ||
171 | |||
172 | nw=n/BN_BITS2; | ||
173 | rb=n%BN_BITS2; | ||
174 | lb=BN_BITS2-rb; | ||
175 | if (nw > a->top) | ||
176 | { | ||
177 | BN_zero(r); | ||
178 | return(1); | ||
179 | } | ||
180 | if (r != a) | ||
181 | { | ||
182 | r->neg=a->neg; | ||
183 | if (bn_wexpand(r,a->top-nw+1) == NULL) return(0); | ||
184 | } | ||
185 | |||
186 | f= &(a->d[nw]); | ||
187 | t=r->d; | ||
188 | j=a->top-nw; | ||
189 | r->top=j; | ||
190 | |||
191 | if (rb == 0) | ||
192 | { | ||
193 | for (i=j+1; i > 0; i--) | ||
194 | *(t++)= *(f++); | ||
195 | } | ||
196 | else | ||
197 | { | ||
198 | l= *(f++); | ||
199 | for (i=1; i<j; i++) | ||
200 | { | ||
201 | tmp =(l>>rb)&BN_MASK2; | ||
202 | l= *(f++); | ||
203 | *(t++) =(tmp|(l<<lb))&BN_MASK2; | ||
204 | } | ||
205 | *(t++) =(l>>rb)&BN_MASK2; | ||
206 | } | ||
207 | *t=0; | ||
208 | bn_fix_top(r); | ||
209 | return(1); | ||
210 | } | ||
diff --git a/src/lib/libcrypto/bn/bn_sqr.c b/src/lib/libcrypto/bn/bn_sqr.c new file mode 100644 index 0000000000..a8464610e5 --- /dev/null +++ b/src/lib/libcrypto/bn/bn_sqr.c | |||
@@ -0,0 +1,122 @@ | |||
1 | /* crypto/bn/bn_sqr.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include "cryptlib.h" | ||
61 | #include "bn_lcl.h" | ||
62 | |||
63 | /* r must not be a */ | ||
64 | /* I've just gone over this and it is now %20 faster on x86 - eay - 27 Jun 96 */ | ||
65 | int BN_sqr(r, a, ctx) | ||
66 | BIGNUM *r; | ||
67 | BIGNUM *a; | ||
68 | BN_CTX *ctx; | ||
69 | { | ||
70 | int i,j,max,al; | ||
71 | BIGNUM *tmp; | ||
72 | BN_ULONG *ap,*rp; | ||
73 | |||
74 | tmp=ctx->bn[ctx->tos]; | ||
75 | |||
76 | al=a->top; | ||
77 | if (al == 0) | ||
78 | { | ||
79 | r->top=0; | ||
80 | return(1); | ||
81 | } | ||
82 | |||
83 | max=(al*2); | ||
84 | if (bn_wexpand(r,1+max) == NULL) return(0); | ||
85 | if (bn_wexpand(tmp,1+max) == NULL) return(0); | ||
86 | |||
87 | r->neg=0; | ||
88 | |||
89 | ap=a->d; | ||
90 | rp=r->d; | ||
91 | rp[0]=rp[max-1]=0; | ||
92 | rp++; | ||
93 | j=al; | ||
94 | |||
95 | if (--j > 0) | ||
96 | { | ||
97 | ap++; | ||
98 | rp[j]=bn_mul_words(rp,ap,j,ap[-1]); | ||
99 | rp+=2; | ||
100 | } | ||
101 | |||
102 | for (i=2; i<al; i++) | ||
103 | { | ||
104 | j--; | ||
105 | ap++; | ||
106 | rp[j]=bn_mul_add_words(rp,ap,j,ap[-1]); | ||
107 | rp+=2; | ||
108 | } | ||
109 | |||
110 | bn_add_words(r->d,r->d,r->d,max); | ||
111 | |||
112 | /* There will not be a carry */ | ||
113 | |||
114 | bn_sqr_words(tmp->d,a->d,al); | ||
115 | |||
116 | bn_add_words(r->d,r->d,tmp->d,max); | ||
117 | |||
118 | r->top=max; | ||
119 | if (r->d[max-1] == 0) r->top--; | ||
120 | return(1); | ||
121 | } | ||
122 | |||
diff --git a/src/lib/libcrypto/bn/bn_word.c b/src/lib/libcrypto/bn/bn_word.c new file mode 100644 index 0000000000..4b3d0f011d --- /dev/null +++ b/src/lib/libcrypto/bn/bn_word.c | |||
@@ -0,0 +1,204 @@ | |||
1 | /* crypto/bn/bn_word.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
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 (tjh@cryptsoft.com). | ||
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 (eay@cryptsoft.com)" | ||
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 (tjh@cryptsoft.com)" | ||
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 | #include "cryptlib.h" | ||
61 | #include "bn_lcl.h" | ||
62 | |||
63 | BN_ULONG BN_mod_word(a, w) | ||
64 | BIGNUM *a; | ||
65 | unsigned long w; | ||
66 | { | ||
67 | #ifndef BN_LLONG | ||
68 | BN_ULONG ret=0; | ||
69 | #else | ||
70 | BN_ULLONG ret=0; | ||
71 | #endif | ||
72 | int i; | ||
73 | |||
74 | w&=BN_MASK2; | ||
75 | for (i=a->top-1; i>=0; i--) | ||
76 | { | ||
77 | #ifndef BN_LLONG | ||
78 | ret=((ret<<BN_BITS4)|((a->d[i]>>BN_BITS4)&BN_MASK2l))%(unsigned long)w; | ||
79 | ret=((ret<<BN_BITS4)|(a->d[i]&BN_MASK2l))%(unsigned long)w; | ||
80 | #else | ||
81 | ret=(BN_ULLONG)(((ret<<(BN_ULLONG)BN_BITS2)|a->d[i])% | ||
82 | (BN_ULLONG)w); | ||
83 | #endif | ||
84 | } | ||
85 | return((BN_ULONG)ret); | ||
86 | } | ||
87 | |||
88 | BN_ULONG BN_div_word(a, w) | ||
89 | BIGNUM *a; | ||
90 | unsigned long w; | ||
91 | { | ||
92 | BN_ULONG ret; | ||
93 | int i; | ||
94 | |||
95 | if (a->top == 0) return(0); | ||
96 | ret=0; | ||
97 | w&=BN_MASK2; | ||
98 | for (i=a->top-1; i>=0; i--) | ||
99 | { | ||
100 | BN_ULONG l,d; | ||
101 | |||
102 | l=a->d[i]; | ||
103 | d=bn_div64(ret,l,w); | ||
104 | ret=(l-((d*w)&BN_MASK2))&BN_MASK2; | ||
105 | a->d[i]=d; | ||
106 | } | ||
107 | if (a->d[a->top-1] == 0) | ||
108 | a->top--; | ||
109 | return(ret); | ||
110 | } | ||
111 | |||
112 | int BN_add_word(a, w) | ||
113 | BIGNUM *a; | ||
114 | unsigned long w; | ||
115 | { | ||
116 | BN_ULONG l; | ||
117 | int i; | ||
118 | |||
119 | if (a->neg) | ||
120 | { | ||
121 | a->neg=0; | ||
122 | i=BN_sub_word(a,w); | ||
123 | if (!BN_is_zero(a)) | ||
124 | a->neg=1; | ||
125 | return(i); | ||
126 | } | ||
127 | w&=BN_MASK2; | ||
128 | if (bn_wexpand(a,a->top+1) == NULL) return(0); | ||
129 | i=0; | ||
130 | for (;;) | ||
131 | { | ||
132 | l=(a->d[i]+(BN_ULONG)w)&BN_MASK2; | ||
133 | a->d[i]=l; | ||
134 | if (w > l) | ||
135 | w=1; | ||
136 | else | ||
137 | break; | ||
138 | i++; | ||
139 | } | ||
140 | if (i >= a->top) | ||
141 | a->top++; | ||
142 | return(1); | ||
143 | } | ||
144 | |||
145 | int BN_sub_word(a, w) | ||
146 | BIGNUM *a; | ||
147 | unsigned long w; | ||
148 | { | ||
149 | int i; | ||
150 | |||
151 | if (a->neg) | ||
152 | { | ||
153 | a->neg=0; | ||
154 | i=BN_add_word(a,w); | ||
155 | a->neg=1; | ||
156 | return(i); | ||
157 | } | ||
158 | |||
159 | w&=BN_MASK2; | ||
160 | if ((a->top == 1) && (a->d[0] < w)) | ||
161 | { | ||
162 | a->d[0]=w-a->d[0]; | ||
163 | a->neg=1; | ||
164 | return(1); | ||
165 | } | ||
166 | i=0; | ||
167 | for (;;) | ||
168 | { | ||
169 | if (a->d[i] >= w) | ||
170 | { | ||
171 | a->d[i]-=w; | ||
172 | break; | ||
173 | } | ||
174 | else | ||
175 | { | ||
176 | a->d[i]=(a->d[i]-w)&BN_MASK2; | ||
177 | i++; | ||
178 | w=1; | ||
179 | } | ||
180 | } | ||
181 | if ((a->d[i] == 0) && (i == (a->top-1))) | ||
182 | a->top--; | ||
183 | return(1); | ||
184 | } | ||
185 | |||
186 | int BN_mul_word(a,w) | ||
187 | BIGNUM *a; | ||
188 | unsigned long w; | ||
189 | { | ||
190 | BN_ULONG ll; | ||
191 | |||
192 | w&=BN_MASK2; | ||
193 | if (a->top) | ||
194 | { | ||
195 | ll=bn_mul_words(a->d,a->d,a->top,w); | ||
196 | if (ll) | ||
197 | { | ||
198 | if (bn_wexpand(a,a->top+1) == NULL) return(0); | ||
199 | a->d[a->top++]=ll; | ||
200 | } | ||
201 | } | ||
202 | return(0); | ||
203 | } | ||
204 | |||