diff options
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 | |||