summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn
diff options
context:
space:
mode:
authorryker <>1998-10-05 20:13:14 +0000
committerryker <>1998-10-05 20:13:14 +0000
commitfe5d0717e2760d02faf23bf5a714f17b33ae4abb (patch)
tree8d4ad346f10a36bdd90b503d222bda6b4ecd0037 /src/lib/libcrypto/bn
parent75bf5ead4149b2b67781def7ace1ec720ae1753e (diff)
parentaeeae06a79815dc190061534d47236cec09f9e32 (diff)
downloadopenbsd-fe5d0717e2760d02faf23bf5a714f17b33ae4abb.tar.gz
openbsd-fe5d0717e2760d02faf23bf5a714f17b33ae4abb.tar.bz2
openbsd-fe5d0717e2760d02faf23bf5a714f17b33ae4abb.zip
This commit was generated by cvs2git to track changes on a CVS vendor
branch.
Diffstat (limited to 'src/lib/libcrypto/bn')
-rw-r--r--src/lib/libcrypto/bn/asm/bn-586.pl314
-rw-r--r--src/lib/libcrypto/bn/asm/pa-risc2.s416
-rw-r--r--src/lib/libcrypto/bn/bn_add.c167
-rw-r--r--src/lib/libcrypto/bn/bn_blind.c143
-rw-r--r--src/lib/libcrypto/bn/bn_div.c286
-rw-r--r--src/lib/libcrypto/bn/bn_err.c111
-rw-r--r--src/lib/libcrypto/bn/bn_exp.c553
-rw-r--r--src/lib/libcrypto/bn/bn_gcd.c203
-rw-r--r--src/lib/libcrypto/bn/bn_lcl.h199
-rw-r--r--src/lib/libcrypto/bn/bn_lib.c611
-rw-r--r--src/lib/libcrypto/bn/bn_mod.c97
-rw-r--r--src/lib/libcrypto/bn/bn_mont.c306
-rw-r--r--src/lib/libcrypto/bn/bn_mpi.c134
-rw-r--r--src/lib/libcrypto/bn/bn_mul.c209
-rw-r--r--src/lib/libcrypto/bn/bn_prime.c473
-rw-r--r--src/lib/libcrypto/bn/bn_prime.h325
-rw-r--r--src/lib/libcrypto/bn/bn_prime.pl56
-rw-r--r--src/lib/libcrypto/bn/bn_print.c333
-rw-r--r--src/lib/libcrypto/bn/bn_rand.c121
-rw-r--r--src/lib/libcrypto/bn/bn_recp.c125
-rw-r--r--src/lib/libcrypto/bn/bn_shift.c210
-rw-r--r--src/lib/libcrypto/bn/bn_sqr.c122
-rw-r--r--src/lib/libcrypto/bn/bn_word.c204
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
6push(@INC,"perlasm","../../perlasm");
7require "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
19sub 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
102sub 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
175sub 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
231sub 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
243sub 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
15bn_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
29L$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
111L$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
121bn_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
134L$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
196L$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
204bn_sqr_words
205 .PROC
206 .CALLINFO FRAME=0,NO_CALLS
207 .ENTRY
208 ldo 28(%r26),%r19
209 ldo 12(%r25),%r28
210L$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
260L$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
271L$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
279bn_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
297L$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
317L$0052
318 comb,>> %r5,%r3,L$0053
319 subi 32,%r24,%r24
320 sub %r3,%r5,%r3
321L$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
333L$0054
334 extru %r5,15,16,%r23
335 extru %r5,31,16,%r28
336L$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
342L$0058
343 .IMPORT $$divU,MILLICODE
344 bl $$divU,%r31
345 copy %r23,%r25
346L$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
362L$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
374L$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
397L$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
404L$0056
405 or %r7,%r29,%r28
406L$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 */
64int BN_add(r, a, b)
65BIGNUM *r;
66BIGNUM *a;
67BIGNUM *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 */
121void bn_qadd(r,a,b)
122BIGNUM *r;
123BIGNUM *a;
124BIGNUM *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
63BN_BLINDING *BN_BLINDING_new(A,Ai,mod)
64BIGNUM *A;
65BIGNUM *Ai;
66BIGNUM *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);
79err:
80 if (ret != NULL) BN_BLINDING_free(ret);
81 return(ret);
82 }
83
84void BN_BLINDING_free(r)
85BN_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
92int BN_BLINDING_update(b,ctx)
93BN_BLINDING *b;
94BN_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;
108err:
109 return(ret);
110 }
111
112int BN_BLINDING_convert(n,b,ctx)
113BIGNUM *n;
114BN_BLINDING *b;
115BN_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
125int BN_BLINDING_invert(n,b,ctx)
126BIGNUM *n;
127BN_BLINDING *b;
128BN_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
65int BN_div(dv, rem, m, d,ctx)
66BIGNUM *dv;
67BIGNUM *rem;
68BIGNUM *m;
69BIGNUM *d;
70BN_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
122int BN_div(dv, rm, num, divisor,ctx)
123BIGNUM *dv;
124BIGNUM *rm;
125BIGNUM *num;
126BIGNUM *divisor;
127BN_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);
282err:
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
64static 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
84static 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
98void 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 */
64int BN_mod_mul(ret, a, b, m, ctx)
65BIGNUM *ret;
66BIGNUM *a;
67BIGNUM *b;
68BIGNUM *m;
69BN_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;
81err:
82 ctx->tos--;
83 return(r);
84 }
85
86#if 0
87/* this one works - simple but works */
88int BN_mod_exp(r,a,p,m,ctx)
89BIGNUM *r,*a,*p,*m;
90BN_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;
116err:
117 ctx->tos-=2;
118 return(ret);
119 }
120
121#endif
122
123/* this one works - simple but works */
124int BN_exp(r,a,p,ctx)
125BIGNUM *r,*a,*p;
126BN_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;
150err:
151 ctx->tos-=2;
152 return(ret);
153 }
154
155int BN_mod_exp(r,a,p,m,ctx)
156BIGNUM *r;
157BIGNUM *a;
158BIGNUM *p;
159BIGNUM *m;
160BN_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 */
185int BN_mod_exp_recp(r,a,p,m,ctx)
186BIGNUM *r;
187BIGNUM *a;
188BIGNUM *p;
189BIGNUM *m;
190BN_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;
292err:
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 */
301int BN_mod_exp_mont(r,a,p,m,ctx,in_mont)
302BIGNUM *r;
303BIGNUM *a;
304BIGNUM *p;
305BIGNUM *m;
306BN_CTX *ctx;
307BN_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;
433err:
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 :-) */
443int BN_mod_exp_simple(r,a,p,m,ctx)
444BIGNUM *r;
445BIGNUM *a;
446BIGNUM *p;
447BIGNUM *m;
448BN_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;
547err:
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
64static BIGNUM *euclid(BIGNUM *a, BIGNUM *b);
65#else
66static BIGNUM *euclid();
67#endif
68
69int BN_gcd(r,in_a,in_b,ctx)
70BIGNUM *r,*in_a,*in_b;
71BN_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;
88err:
89 return(ret);
90 }
91
92static BIGNUM *euclid(a,b)
93BIGNUM *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);
140err:
141 return(NULL);
142 }
143
144/* solves ax == 1 (mod n) */
145BIGNUM *BN_mod_inverse(a, n, ctx)
146BIGNUM *a;
147BIGNUM *n;
148BN_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;
198err:
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
65extern "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
180BIGNUM *bn_expand2(BIGNUM *b, int bits);
181
182#ifdef X86_ASM
183void bn_add_words(BN_ULONG *r,BN_ULONG *a,int num);
184#endif
185
186#else
187
188BIGNUM *bn_expand2();
189#ifdef X86_ASM
190BN_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
63char *BN_version="Big Number part of SSLeay 0.9.0b 29-Jun-1998";
64
65BIGNUM *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
73char *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
92int BN_num_bits_word(l)
93BN_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
180int BN_num_bits(a)
181BIGNUM *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
199void BN_clear_free(a)
200BIGNUM *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
212void BN_free(a)
213BIGNUM *a;
214 {
215 if (a == NULL) return;
216 if (a->d != NULL) Free(a->d);
217 Free(a);
218 }
219
220BIGNUM *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);
236err:
237 BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE);
238 return(NULL);
239 }
240
241BN_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);
263err:
264 for (j=0; j<i; j++)
265 BN_free(ret->bn[j]);
266 Free(ret);
267err2:
268 BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE);
269 return(NULL);
270 }
271
272void BN_CTX_free(c)
273BN_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
282BIGNUM *bn_expand2(b, words)
283BIGNUM *b;
284int 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
303BIGNUM *BN_dup(a)
304BIGNUM *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
313BIGNUM *BN_copy(a, b)
314BIGNUM *a;
315BIGNUM *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
368void BN_clear(a)
369BIGNUM *a;
370 {
371 memset(a->d,0,a->max*sizeof(a->d[0]));
372 a->top=0;
373 a->neg=0;
374 }
375
376unsigned long BN_get_word(a)
377BIGNUM *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
400int BN_set_word(a,w)
401BIGNUM *a;
402unsigned 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 */
428BIGNUM *BN_bin2bn(s, len, ret)
429unsigned char *s;
430int len;
431BIGNUM *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 */
468int BN_bn2bin(a, to)
469BIGNUM *a;
470unsigned 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
484int BN_ucmp(a, b)
485BIGNUM *a;
486BIGNUM *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
505int BN_cmp(a, b)
506BIGNUM *a;
507BIGNUM *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
544int BN_set_bit(a, n)
545BIGNUM *a;
546int 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
562int BN_clear_bit(a, n)
563BIGNUM *a;
564int 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
576int BN_is_bit_set(a, n)
577BIGNUM *a;
578int 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
589int BN_mask_bits(a,n)
590BIGNUM *a;
591int 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 */
64int BN_mod(rem, m, d,ctx)
65BIGNUM *rem;
66BIGNUM *m;
67BIGNUM *d;
68BN_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
63int BN_mod_mul_montgomery(r,a,b,mont,ctx)
64BIGNUM *r,*a,*b;
65BN_MONT_CTX *mont;
66BN_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);
84err:
85 return(0);
86 }
87
88#define MONT_WORD
89
90#ifdef MONT_WORD
91int BN_from_montgomery(ret,a,mont,ctx)
92BIGNUM *ret;
93BIGNUM *a;
94BN_MONT_CTX *mont;
95BN_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;
184err:
185 return(retn);
186 }
187#else
188int BN_from_montgomery(r,a,mont,ctx)
189BIGNUM *r;
190BIGNUM *a;
191BN_MONT_CTX *mont;
192BN_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);
214err:
215 return(0);
216 }
217#endif
218
219BN_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
237void BN_MONT_CTX_free(mont)
238BN_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
246int BN_MONT_CTX_set(mont,mod,ctx)
247BN_MONT_CTX *mont;
248BIGNUM *mod;
249BN_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);
303err:
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
63int BN_bn2mpi(a,d)
64BIGNUM *a;
65unsigned 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
93BIGNUM *BN_mpi2bn(d,n,a)
94unsigned char *d;
95int n;
96BIGNUM *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) */
65int BN_mul(r, a, b)
66BIGNUM *r;
67BIGNUM *a;
68BIGNUM *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
104int limit=16;
105
106typedef struct bn_pool_st
107 {
108 int used;
109 int tos;
110 STACK *sk;
111 } BN_POOL;
112
113BIGNUM *BN_POOL_push(bp)
114BN_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
133void BN_POOL_pop(bp,num)
134BN_POOL *bp;
135int num;
136 {
137 bp->used-=num;
138 }
139
140int BN_mul(r,a,b)
141BIGNUM *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 */
157int BN_mm(m, A, B, bp)
158BIGNUM *m,*A,*B;
159BN_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
72static int witness(BIGNUM *a, BIGNUM *n, BN_CTX *ctx,BN_CTX *ctx2,
73 BN_MONT_CTX *mont);
74static int probable_prime(BIGNUM *rnd, int bits);
75static int probable_prime_dh(BIGNUM *rnd, int bits,
76 BIGNUM *add, BIGNUM *rem, BN_CTX *ctx);
77static int probable_prime_dh_strong(BIGNUM *rnd, int bits,
78 BIGNUM *add, BIGNUM *rem, BN_CTX *ctx);
79#else
80static int witness();
81static int probable_prime();
82static int probable_prime_dh();
83static int probable_prime_dh_strong();
84#endif
85
86BIGNUM *BN_generate_prime(bits,strong,add,rem,callback,cb_arg)
87int bits;
88int strong;
89BIGNUM *add;
90BIGNUM *rem;
91void (*callback)(P_I_I_P);
92char *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;
105loop:
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;
157err:
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
164int BN_is_prime(a,checks,callback,ctx_passed,cb_arg)
165BIGNUM *a;
166int checks;
167void (*callback)(P_I_I_P);
168BN_CTX *ctx_passed;
169char *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;
204err:
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
217static int witness(a,n,ctx,ctx2,mont)
218BIGNUM *a;
219BIGNUM *n;
220BN_CTX *ctx,*ctx2;
221BN_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;
278err:
279 ctx->tos-=3;
280 ctx2->tos-=3;
281 return(ret);
282 }
283
284static int probable_prime(rnd, bits)
285BIGNUM *rnd;
286int 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
313static int probable_prime_dh(rnd, bits, add, rem,ctx)
314BIGNUM *rnd;
315int bits;
316BIGNUM *add;
317BIGNUM *rem;
318BN_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;
348err:
349 ctx->tos--;
350 return(ret);
351 }
352
353static int probable_prime_dh_strong(p, bits, padd, rem,ctx)
354BIGNUM *p;
355int bits;
356BIGNUM *padd;
357BIGNUM *rem;
358BN_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;
401err:
402 ctx->tos-=3;
403 return(ret);
404 }
405
406#if 0
407static int witness(a, n,ctx)
408BIGNUM *a;
409BIGNUM *n;
410BN_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;
469err:
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
64static 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
7push(@primes,2);
8$p=1;
9loop: 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
21print <<"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
30EOF
31
32for ($i=0; $i <= $#primes; $i++)
33 {
34 if ($primes[$i] > 256)
35 {
36 $eight=$i;
37 last;
38 }
39 }
40
41printf "#ifndef EIGHT_BIT\n";
42printf "#define NUMPRIMES %d\n",$num;
43printf "#else\n";
44printf "#define NUMPRIMES %d\n",$eight;
45printf "#endif\n";
46print "static unsigned int primes[NUMPRIMES]=\n\t{\n\t";
47$init=0;
48for ($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 }
54print "\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
65static char *Hex="0123456789ABCDEF";
66
67/* Must 'Free' the returned data */
68char *BN_bn2hex(a)
69BIGNUM *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';
99err:
100 return(buf);
101 }
102
103/* Must 'Free' the returned data */
104char *BN_bn2dec(a)
105BIGNUM *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 }
153err:
154 if (bn_data != NULL) Free(bn_data);
155 if (t != NULL) BN_free(t);
156 return(buf);
157 }
158
159int BN_hex2bn(bn,a)
160BIGNUM **bn;
161char *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);
222err:
223 if (*bn == NULL) BN_free(ret);
224 return(0);
225 }
226
227int BN_dec2bn(bn,a)
228BIGNUM **bn;
229char *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);
281err:
282 if (*bn == NULL) BN_free(ret);
283 return(0);
284 }
285
286#ifndef NO_BIO
287
288#ifndef NO_FP_API
289int BN_print_fp(fp, a)
290FILE *fp;
291BIGNUM *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
305int BN_print(bp, a)
306BIO *bp;
307BIGNUM *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;
329end:
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
65int BN_rand(rnd, bits, top, bottom)
66BIGNUM *rnd;
67int bits;
68int top;
69int 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;
113err:
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
63int BN_mod_mul_reciprocal(r, x, y, m, i, nb, ctx)
64BIGNUM *r;
65BIGNUM *x;
66BIGNUM *y;
67BIGNUM *m;
68BIGNUM *i;
69int nb;
70BN_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;
101err:
102 ctx->tos-=4;
103 return(ret);
104 }
105
106int BN_reciprocal(r, m,ctx)
107BIGNUM *r;
108BIGNUM *m;
109BN_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;
121err:
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
63int BN_lshift1(r, a)
64BIGNUM *r;
65BIGNUM *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
97int BN_rshift1(r, a)
98BIGNUM *r;
99BIGNUM *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
128int BN_lshift(r, a, n)
129BIGNUM *r;
130BIGNUM *a;
131int 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
163int BN_rshift(r, a, n)
164BIGNUM *r;
165BIGNUM *a;
166int 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 */
65int BN_sqr(r, a, ctx)
66BIGNUM *r;
67BIGNUM *a;
68BN_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
63BN_ULONG BN_mod_word(a, w)
64BIGNUM *a;
65unsigned 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
88BN_ULONG BN_div_word(a, w)
89BIGNUM *a;
90unsigned 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
112int BN_add_word(a, w)
113BIGNUM *a;
114unsigned 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
145int BN_sub_word(a, w)
146BIGNUM *a;
147unsigned 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
186int BN_mul_word(a,w)
187BIGNUM *a;
188unsigned 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
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-12-26 01:00:56 +0000