OLD | NEW |
1 /* crypto/bn/bn_mont.c */ | 1 /* crypto/bn/bn_mont.c */ |
2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | 2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
3 * All rights reserved. | 3 * All rights reserved. |
4 * | 4 * |
5 * This package is an SSL implementation written | 5 * This package is an SSL implementation written |
6 * by Eric Young (eay@cryptsoft.com). | 6 * by Eric Young (eay@cryptsoft.com). |
7 * The implementation was written so as to conform with Netscapes SSL. | 7 * The implementation was written so as to conform with Netscapes SSL. |
8 * | 8 * |
9 * This library is free for commercial and non-commercial use as long as | 9 * This library is free for commercial and non-commercial use as long as |
10 * the following conditions are aheared to. The following conditions | 10 * the following conditions are aheared to. The following conditions |
(...skipping 104 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
115 * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and | 115 * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and |
116 * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf | 116 * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf |
117 */ | 117 */ |
118 | 118 |
119 #include <stdio.h> | 119 #include <stdio.h> |
120 #include "cryptlib.h" | 120 #include "cryptlib.h" |
121 #include "bn_lcl.h" | 121 #include "bn_lcl.h" |
122 | 122 |
123 #define MONT_WORD /* use the faster word-based algorithm */ | 123 #define MONT_WORD /* use the faster word-based algorithm */ |
124 | 124 |
125 #if defined(MONT_WORD) && defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32) | 125 #ifdef MONT_WORD |
126 /* This condition means we have a specific non-default build: | |
127 * In the 0.9.8 branch, OPENSSL_BN_ASM_MONT is normally not set for any | |
128 * BN_BITS2<=32 platform; an explicit "enable-montasm" is required. | |
129 * I.e., if we are here, the user intentionally deviates from the | |
130 * normal stable build to get better Montgomery performance from | |
131 * the 0.9.9-dev backport. | |
132 * | |
133 * In this case only, we also enable BN_from_montgomery_word() | |
134 * (another non-stable feature from 0.9.9-dev). | |
135 */ | |
136 #define MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD | |
137 #endif | |
138 | |
139 #ifdef MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD | |
140 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont); | 126 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont); |
141 #endif | 127 #endif |
142 | 128 |
143 | |
144 | |
145 int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, | 129 int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
146 BN_MONT_CTX *mont, BN_CTX *ctx) | 130 BN_MONT_CTX *mont, BN_CTX *ctx) |
147 { | 131 { |
148 BIGNUM *tmp; | 132 BIGNUM *tmp; |
149 int ret=0; | 133 int ret=0; |
150 #if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD) | 134 #if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD) |
151 int num = mont->N.top; | 135 int num = mont->N.top; |
152 | 136 |
153 if (num>1 && a->top==num && b->top==num) | 137 if (num>1 && a->top==num && b->top==num) |
154 { | 138 { |
155 if (bn_wexpand(r,num) == NULL) return(0); | 139 if (bn_wexpand(r,num) == NULL) return(0); |
156 #if 0 /* for OpenSSL 0.9.9 mont->n0 */ | |
157 if (bn_mul_mont(r->d,a->d,b->d,mont->N.d,mont->n0,num)) | 140 if (bn_mul_mont(r->d,a->d,b->d,mont->N.d,mont->n0,num)) |
158 #else | |
159 if (bn_mul_mont(r->d,a->d,b->d,mont->N.d,&mont->n0,num)) | |
160 #endif | |
161 { | 141 { |
162 r->neg = a->neg^b->neg; | 142 r->neg = a->neg^b->neg; |
163 r->top = num; | 143 r->top = num; |
164 bn_correct_top(r); | 144 bn_correct_top(r); |
165 return(1); | 145 return(1); |
166 } | 146 } |
167 } | 147 } |
168 #endif | 148 #endif |
169 | 149 |
170 BN_CTX_start(ctx); | 150 BN_CTX_start(ctx); |
171 tmp = BN_CTX_get(ctx); | 151 tmp = BN_CTX_get(ctx); |
172 if (tmp == NULL) goto err; | 152 if (tmp == NULL) goto err; |
173 | 153 |
174 bn_check_top(tmp); | 154 bn_check_top(tmp); |
175 if (a == b) | 155 if (a == b) |
176 { | 156 { |
177 if (!BN_sqr(tmp,a,ctx)) goto err; | 157 if (!BN_sqr(tmp,a,ctx)) goto err; |
178 } | 158 } |
179 else | 159 else |
180 { | 160 { |
181 if (!BN_mul(tmp,a,b,ctx)) goto err; | 161 if (!BN_mul(tmp,a,b,ctx)) goto err; |
182 } | 162 } |
183 /* reduce from aRR to aR */ | 163 /* reduce from aRR to aR */ |
184 #ifdef MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD | 164 #ifdef MONT_WORD |
185 if (!BN_from_montgomery_word(r,tmp,mont)) goto err; | 165 if (!BN_from_montgomery_word(r,tmp,mont)) goto err; |
186 #else | 166 #else |
187 if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err; | 167 if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err; |
188 #endif | 168 #endif |
189 bn_check_top(r); | 169 bn_check_top(r); |
190 ret=1; | 170 ret=1; |
191 err: | 171 err: |
192 BN_CTX_end(ctx); | 172 BN_CTX_end(ctx); |
193 return(ret); | 173 return(ret); |
194 } | 174 } |
195 | 175 |
196 #ifdef MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD | 176 #ifdef MONT_WORD |
197 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) | 177 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) |
198 { | 178 { |
199 BIGNUM *n; | 179 BIGNUM *n; |
200 BN_ULONG *ap,*np,*rp,n0,v,*nrp; | 180 BN_ULONG *ap,*np,*rp,n0,v,*nrp; |
201 int al,nl,max,i,x,ri; | 181 int al,nl,max,i,x,ri; |
202 | 182 |
203 n= &(mont->N); | 183 n= &(mont->N); |
204 /* mont->ri is the size of mont->N in bits (rounded up | 184 /* mont->ri is the size of mont->N in bits (rounded up |
205 to the word size) */ | 185 to the word size) */ |
206 al=ri=mont->ri/BN_BITS2; | 186 al=ri=mont->ri/BN_BITS2; |
207 | 187 |
208 nl=n->top; | 188 nl=n->top; |
209 if ((al == 0) || (nl == 0)) { ret->top=0; return(1); } | 189 if ((al == 0) || (nl == 0)) { ret->top=0; return(1); } |
210 | 190 |
211 max=(nl+al+1); /* allow for overflow (no?) XXX */ | 191 max=(nl+al+1); /* allow for overflow (no?) XXX */ |
212 if (bn_wexpand(r,max) == NULL) return(0); | 192 if (bn_wexpand(r,max) == NULL) return(0); |
213 | 193 |
214 r->neg^=n->neg; | 194 r->neg^=n->neg; |
215 np=n->d; | 195 np=n->d; |
216 rp=r->d; | 196 rp=r->d; |
217 nrp= &(r->d[nl]); | 197 nrp= &(r->d[nl]); |
218 | 198 |
219 /* clear the top words of T */ | 199 /* clear the top words of T */ |
| 200 #if 1 |
220 for (i=r->top; i<max; i++) /* memset? XXX */ | 201 for (i=r->top; i<max; i++) /* memset? XXX */ |
221 r->d[i]=0; | 202 r->d[i]=0; |
| 203 #else |
| 204 memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG)); |
| 205 #endif |
222 | 206 |
223 r->top=max; | 207 r->top=max; |
224 #if 0 /* for OpenSSL 0.9.9 mont->n0 */ | |
225 n0=mont->n0[0]; | 208 n0=mont->n0[0]; |
226 #else | |
227 n0=mont->n0; | |
228 #endif | |
229 | 209 |
230 #ifdef BN_COUNT | 210 #ifdef BN_COUNT |
231 fprintf(stderr,"word BN_from_montgomery_word %d * %d\n",nl,nl); | 211 fprintf(stderr,"word BN_from_montgomery_word %d * %d\n",nl,nl); |
232 #endif | 212 #endif |
233 for (i=0; i<nl; i++) | 213 for (i=0; i<nl; i++) |
234 { | 214 { |
235 #ifdef __TANDEM | 215 #ifdef __TANDEM |
236 { | 216 { |
237 long long t1; | 217 long long t1; |
238 long long t2; | 218 long long t2; |
(...skipping 24 matching lines...) Expand all Loading... |
263 | 243 |
264 /* mont->ri will be a multiple of the word size and below code | 244 /* mont->ri will be a multiple of the word size and below code |
265 * is kind of BN_rshift(ret,r,mont->ri) equivalent */ | 245 * is kind of BN_rshift(ret,r,mont->ri) equivalent */ |
266 if (r->top <= ri) | 246 if (r->top <= ri) |
267 { | 247 { |
268 ret->top=0; | 248 ret->top=0; |
269 return(1); | 249 return(1); |
270 } | 250 } |
271 al=r->top-ri; | 251 al=r->top-ri; |
272 | 252 |
| 253 #define BRANCH_FREE 1 |
| 254 #if BRANCH_FREE |
273 if (bn_wexpand(ret,ri) == NULL) return(0); | 255 if (bn_wexpand(ret,ri) == NULL) return(0); |
274 x=0-(((al-ri)>>(sizeof(al)*8-1))&1); | 256 x=0-(((al-ri)>>(sizeof(al)*8-1))&1); |
275 ret->top=x=(ri&~x)|(al&x); /* min(ri,al) */ | 257 ret->top=x=(ri&~x)|(al&x); /* min(ri,al) */ |
276 ret->neg=r->neg; | 258 ret->neg=r->neg; |
277 | 259 |
278 rp=ret->d; | 260 rp=ret->d; |
279 ap=&(r->d[ri]); | 261 ap=&(r->d[ri]); |
280 | 262 |
281 { | 263 { |
282 size_t m1,m2; | 264 size_t m1,m2; |
283 | 265 |
284 v=bn_sub_words(rp,ap,np,ri); | 266 v=bn_sub_words(rp,ap,np,ri); |
285 /* this ----------------^^ works even in al<ri case | 267 /* this ----------------^^ works even in al<ri case |
286 * thanks to zealous zeroing of top of the vector in the | 268 * thanks to zealous zeroing of top of the vector in the |
287 * beginning. */ | 269 * beginning. */ |
288 | 270 |
289 /* if (al==ri && !v) || al>ri) nrp=rp; else nrp=ap; */ | 271 /* if (al==ri && !v) || al>ri) nrp=rp; else nrp=ap; */ |
290 /* in other words if subtraction result is real, then | 272 /* in other words if subtraction result is real, then |
291 * trick unconditional memcpy below to perform in-place | 273 * trick unconditional memcpy below to perform in-place |
292 * "refresh" instead of actual copy. */ | 274 * "refresh" instead of actual copy. */ |
293 m1=0-(size_t)(((al-ri)>>(sizeof(al)*8-1))&1); /* al<ri */ | 275 m1=0-(size_t)(((al-ri)>>(sizeof(al)*8-1))&1); /* al<ri */ |
294 m2=0-(size_t)(((ri-al)>>(sizeof(al)*8-1))&1); /* al>ri */ | 276 m2=0-(size_t)(((ri-al)>>(sizeof(al)*8-1))&1); /* al>ri */ |
295 m1|=m2; /* (al!=ri) */ | 277 m1|=m2; /* (al!=ri) */ |
296 m1|=(0-(size_t)v); /* (al!=ri || v) */ | 278 m1|=(0-(size_t)v); /* (al!=ri || v) */ |
297 m1&=~m2; /* (al!=ri || v) && !al>ri */ | 279 m1&=~m2; /* (al!=ri || v) && !al>ri */ |
298 » nrp=(BN_ULONG *)(((size_t)rp&~m1)|((size_t)ap&m1)); | 280 » nrp=(BN_ULONG *)(((PTR_SIZE_INT)rp&~m1)|((PTR_SIZE_INT)ap&m1)); |
299 } | 281 } |
300 | 282 |
301 /* 'i<ri' is chosen to eliminate dependency on input data, even | 283 /* 'i<ri' is chosen to eliminate dependency on input data, even |
302 * though it results in redundant copy in al<ri case. */ | 284 * though it results in redundant copy in al<ri case. */ |
303 for (i=0,ri-=4; i<ri; i+=4) | 285 for (i=0,ri-=4; i<ri; i+=4) |
304 { | 286 { |
305 BN_ULONG t1,t2,t3,t4; | 287 BN_ULONG t1,t2,t3,t4; |
306 | 288 |
307 t1=nrp[i+0]; | 289 t1=nrp[i+0]; |
308 t2=nrp[i+1]; | 290 t2=nrp[i+1]; |
309 t3=nrp[i+2]; ap[i+0]=0; | 291 t3=nrp[i+2]; ap[i+0]=0; |
310 t4=nrp[i+3]; ap[i+1]=0; | 292 t4=nrp[i+3]; ap[i+1]=0; |
311 rp[i+0]=t1; ap[i+2]=0; | 293 rp[i+0]=t1; ap[i+2]=0; |
312 rp[i+1]=t2; ap[i+3]=0; | 294 rp[i+1]=t2; ap[i+3]=0; |
313 rp[i+2]=t3; | 295 rp[i+2]=t3; |
314 rp[i+3]=t4; | 296 rp[i+3]=t4; |
315 } | 297 } |
316 for (ri+=4; i<ri; i++) | 298 for (ri+=4; i<ri; i++) |
317 rp[i]=nrp[i], ap[i]=0; | 299 rp[i]=nrp[i], ap[i]=0; |
318 bn_correct_top(r); | 300 bn_correct_top(r); |
319 bn_correct_top(ret); | 301 bn_correct_top(ret); |
320 bn_check_top(ret); | |
321 | |
322 return(1); | |
323 } | |
324 | |
325 int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, | |
326 BN_CTX *ctx) | |
327 { | |
328 int retn=0; | |
329 BIGNUM *t; | |
330 | |
331 BN_CTX_start(ctx); | |
332 if ((t = BN_CTX_get(ctx)) && BN_copy(t,a)) | |
333 retn = BN_from_montgomery_word(ret,t,mont); | |
334 BN_CTX_end(ctx); | |
335 return retn; | |
336 } | |
337 | |
338 #else /* !MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD */ | |
339 | |
340 int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, | |
341 BN_CTX *ctx) | |
342 { | |
343 int retn=0; | |
344 | |
345 #ifdef MONT_WORD | |
346 BIGNUM *n,*r; | |
347 BN_ULONG *ap,*np,*rp,n0,v,*nrp; | |
348 int al,nl,max,i,x,ri; | |
349 | |
350 BN_CTX_start(ctx); | |
351 if ((r = BN_CTX_get(ctx)) == NULL) goto err; | |
352 | |
353 if (!BN_copy(r,a)) goto err; | |
354 n= &(mont->N); | |
355 | |
356 ap=a->d; | |
357 /* mont->ri is the size of mont->N in bits (rounded up | |
358 to the word size) */ | |
359 al=ri=mont->ri/BN_BITS2; | |
360 | |
361 nl=n->top; | |
362 if ((al == 0) || (nl == 0)) { r->top=0; return(1); } | |
363 | |
364 max=(nl+al+1); /* allow for overflow (no?) XXX */ | |
365 if (bn_wexpand(r,max) == NULL) goto err; | |
366 | |
367 r->neg=a->neg^n->neg; | |
368 np=n->d; | |
369 rp=r->d; | |
370 nrp= &(r->d[nl]); | |
371 | |
372 /* clear the top words of T */ | |
373 #if 1 | |
374 for (i=r->top; i<max; i++) /* memset? XXX */ | |
375 r->d[i]=0; | |
376 #else | 302 #else |
377 » memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG)); | 303 » if (bn_wexpand(ret,al) == NULL) return(0); |
378 #endif | |
379 | |
380 » r->top=max; | |
381 » n0=mont->n0; | |
382 | |
383 #ifdef BN_COUNT | |
384 » fprintf(stderr,"word BN_from_montgomery %d * %d\n",nl,nl); | |
385 #endif | |
386 » for (i=0; i<nl; i++) | |
387 » » { | |
388 #ifdef __TANDEM | |
389 { | |
390 long long t1; | |
391 long long t2; | |
392 long long t3; | |
393 t1 = rp[0] * (n0 & 0177777); | |
394 t2 = 037777600000l; | |
395 t2 = n0 & t2; | |
396 t3 = rp[0] & 0177777; | |
397 t2 = (t3 * t2) & BN_MASK2; | |
398 t1 = t1 + t2; | |
399 v=bn_mul_add_words(rp,np,nl,(BN_ULONG) t1); | |
400 } | |
401 #else | |
402 » » v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2); | |
403 #endif | |
404 » » nrp++; | |
405 » » rp++; | |
406 » » if (((nrp[-1]+=v)&BN_MASK2) >= v) | |
407 » » » continue; | |
408 » » else | |
409 » » » { | |
410 » » » if (((++nrp[0])&BN_MASK2) != 0) continue; | |
411 » » » if (((++nrp[1])&BN_MASK2) != 0) continue; | |
412 » » » for (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ; | |
413 » » » } | |
414 » » } | |
415 » bn_correct_top(r); | |
416 » | |
417 » /* mont->ri will be a multiple of the word size and below code | |
418 » * is kind of BN_rshift(ret,r,mont->ri) equivalent */ | |
419 » if (r->top <= ri) | |
420 » » { | |
421 » » ret->top=0; | |
422 » » retn=1; | |
423 » » goto err; | |
424 » » } | |
425 » al=r->top-ri; | |
426 | |
427 # define BRANCH_FREE 1 | |
428 # if BRANCH_FREE | |
429 » if (bn_wexpand(ret,ri) == NULL) goto err; | |
430 » x=0-(((al-ri)>>(sizeof(al)*8-1))&1); | |
431 » ret->top=x=(ri&~x)|(al&x);» /* min(ri,al) */ | |
432 » ret->neg=r->neg; | |
433 | |
434 » rp=ret->d; | |
435 » ap=&(r->d[ri]); | |
436 | |
437 » { | |
438 » size_t m1,m2; | |
439 | |
440 » v=bn_sub_words(rp,ap,np,ri); | |
441 » /* this ----------------^^ works even in al<ri case | |
442 » * thanks to zealous zeroing of top of the vector in the | |
443 » * beginning. */ | |
444 | |
445 » /* if (al==ri && !v) || al>ri) nrp=rp; else nrp=ap; */ | |
446 » /* in other words if subtraction result is real, then | |
447 » * trick unconditional memcpy below to perform in-place | |
448 » * "refresh" instead of actual copy. */ | |
449 » m1=0-(size_t)(((al-ri)>>(sizeof(al)*8-1))&1);» /* al<ri */ | |
450 » m2=0-(size_t)(((ri-al)>>(sizeof(al)*8-1))&1);» /* al>ri */ | |
451 » m1|=m2;»» » /* (al!=ri) */ | |
452 » m1|=(0-(size_t)v);» /* (al!=ri || v) */ | |
453 » m1&=~m2;» » /* (al!=ri || v) && !al>ri */ | |
454 » nrp=(BN_ULONG *)(((size_t)rp&~m1)|((size_t)ap&m1)); | |
455 » } | |
456 | |
457 » /* 'i<ri' is chosen to eliminate dependency on input data, even | |
458 » * though it results in redundant copy in al<ri case. */ | |
459 » for (i=0,ri-=4; i<ri; i+=4) | |
460 » » { | |
461 » » BN_ULONG t1,t2,t3,t4; | |
462 » » | |
463 » » t1=nrp[i+0]; | |
464 » » t2=nrp[i+1]; | |
465 » » t3=nrp[i+2];» ap[i+0]=0; | |
466 » » t4=nrp[i+3];» ap[i+1]=0; | |
467 » » rp[i+0]=t1;» ap[i+2]=0; | |
468 » » rp[i+1]=t2;» ap[i+3]=0; | |
469 » » rp[i+2]=t3; | |
470 » » rp[i+3]=t4; | |
471 » » } | |
472 » for (ri+=4; i<ri; i++) | |
473 » » rp[i]=nrp[i], ap[i]=0; | |
474 » bn_correct_top(r); | |
475 » bn_correct_top(ret); | |
476 # else | |
477 » if (bn_wexpand(ret,al) == NULL) goto err; | |
478 ret->top=al; | 304 ret->top=al; |
479 ret->neg=r->neg; | 305 ret->neg=r->neg; |
480 | 306 |
481 rp=ret->d; | 307 rp=ret->d; |
482 ap=&(r->d[ri]); | 308 ap=&(r->d[ri]); |
483 al-=4; | 309 al-=4; |
484 for (i=0; i<al; i+=4) | 310 for (i=0; i<al; i+=4) |
485 { | 311 { |
486 BN_ULONG t1,t2,t3,t4; | 312 BN_ULONG t1,t2,t3,t4; |
487 | 313 |
488 t1=ap[i+0]; | 314 t1=ap[i+0]; |
489 t2=ap[i+1]; | 315 t2=ap[i+1]; |
490 t3=ap[i+2]; | 316 t3=ap[i+2]; |
491 t4=ap[i+3]; | 317 t4=ap[i+3]; |
492 rp[i+0]=t1; | 318 rp[i+0]=t1; |
493 rp[i+1]=t2; | 319 rp[i+1]=t2; |
494 rp[i+2]=t3; | 320 rp[i+2]=t3; |
495 rp[i+3]=t4; | 321 rp[i+3]=t4; |
496 } | 322 } |
497 al+=4; | 323 al+=4; |
498 for (; i<al; i++) | 324 for (; i<al; i++) |
499 rp[i]=ap[i]; | 325 rp[i]=ap[i]; |
500 # endif | 326 |
501 #else /* !MONT_WORD */ | 327 » if (BN_ucmp(ret, &(mont->N)) >= 0) |
| 328 » » { |
| 329 » » if (!BN_usub(ret,ret,&(mont->N))) return(0); |
| 330 » » } |
| 331 #endif |
| 332 » bn_check_top(ret); |
| 333 |
| 334 » return(1); |
| 335 » } |
| 336 #endif» /* MONT_WORD */ |
| 337 |
| 338 int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, |
| 339 » BN_CTX *ctx) |
| 340 » { |
| 341 » int retn=0; |
| 342 #ifdef MONT_WORD |
| 343 » BIGNUM *t; |
| 344 |
| 345 » BN_CTX_start(ctx); |
| 346 » if ((t = BN_CTX_get(ctx)) && BN_copy(t,a)) |
| 347 » » retn = BN_from_montgomery_word(ret,t,mont); |
| 348 » BN_CTX_end(ctx); |
| 349 #else /* !MONT_WORD */ |
502 BIGNUM *t1,*t2; | 350 BIGNUM *t1,*t2; |
503 | 351 |
504 BN_CTX_start(ctx); | 352 BN_CTX_start(ctx); |
505 t1 = BN_CTX_get(ctx); | 353 t1 = BN_CTX_get(ctx); |
506 t2 = BN_CTX_get(ctx); | 354 t2 = BN_CTX_get(ctx); |
507 if (t1 == NULL || t2 == NULL) goto err; | 355 if (t1 == NULL || t2 == NULL) goto err; |
508 | 356 |
509 if (!BN_copy(t1,a)) goto err; | 357 if (!BN_copy(t1,a)) goto err; |
510 BN_mask_bits(t1,mont->ri); | 358 BN_mask_bits(t1,mont->ri); |
511 | 359 |
512 if (!BN_mul(t2,t1,&mont->Ni,ctx)) goto err; | 360 if (!BN_mul(t2,t1,&mont->Ni,ctx)) goto err; |
513 BN_mask_bits(t2,mont->ri); | 361 BN_mask_bits(t2,mont->ri); |
514 | 362 |
515 if (!BN_mul(t1,t2,&mont->N,ctx)) goto err; | 363 if (!BN_mul(t1,t2,&mont->N,ctx)) goto err; |
516 if (!BN_add(t2,a,t1)) goto err; | 364 if (!BN_add(t2,a,t1)) goto err; |
517 if (!BN_rshift(ret,t2,mont->ri)) goto err; | 365 if (!BN_rshift(ret,t2,mont->ri)) goto err; |
518 #endif /* MONT_WORD */ | |
519 | 366 |
520 #if !defined(BRANCH_FREE) || BRANCH_FREE==0 | |
521 if (BN_ucmp(ret, &(mont->N)) >= 0) | 367 if (BN_ucmp(ret, &(mont->N)) >= 0) |
522 { | 368 { |
523 if (!BN_usub(ret,ret,&(mont->N))) goto err; | 369 if (!BN_usub(ret,ret,&(mont->N))) goto err; |
524 } | 370 } |
525 #endif | |
526 retn=1; | 371 retn=1; |
527 bn_check_top(ret); | 372 bn_check_top(ret); |
528 err: | 373 err: |
529 BN_CTX_end(ctx); | 374 BN_CTX_end(ctx); |
| 375 #endif /* MONT_WORD */ |
530 return(retn); | 376 return(retn); |
531 } | 377 } |
532 #endif /* MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD */ | |
533 | 378 |
534 BN_MONT_CTX *BN_MONT_CTX_new(void) | 379 BN_MONT_CTX *BN_MONT_CTX_new(void) |
535 { | 380 { |
536 BN_MONT_CTX *ret; | 381 BN_MONT_CTX *ret; |
537 | 382 |
538 if ((ret=(BN_MONT_CTX *)OPENSSL_malloc(sizeof(BN_MONT_CTX))) == NULL) | 383 if ((ret=(BN_MONT_CTX *)OPENSSL_malloc(sizeof(BN_MONT_CTX))) == NULL) |
539 return(NULL); | 384 return(NULL); |
540 | 385 |
541 BN_MONT_CTX_init(ret); | 386 BN_MONT_CTX_init(ret); |
542 ret->flags=BN_FLG_MALLOCED; | 387 ret->flags=BN_FLG_MALLOCED; |
543 return(ret); | 388 return(ret); |
544 } | 389 } |
545 | 390 |
546 void BN_MONT_CTX_init(BN_MONT_CTX *ctx) | 391 void BN_MONT_CTX_init(BN_MONT_CTX *ctx) |
547 { | 392 { |
548 ctx->ri=0; | 393 ctx->ri=0; |
549 BN_init(&(ctx->RR)); | 394 BN_init(&(ctx->RR)); |
550 BN_init(&(ctx->N)); | 395 BN_init(&(ctx->N)); |
551 BN_init(&(ctx->Ni)); | 396 BN_init(&(ctx->Ni)); |
552 #if 0 /* for OpenSSL 0.9.9 mont->n0 */ | |
553 ctx->n0[0] = ctx->n0[1] = 0; | 397 ctx->n0[0] = ctx->n0[1] = 0; |
554 #else | |
555 ctx->n0 = 0; | |
556 #endif | |
557 ctx->flags=0; | 398 ctx->flags=0; |
558 } | 399 } |
559 | 400 |
560 void BN_MONT_CTX_free(BN_MONT_CTX *mont) | 401 void BN_MONT_CTX_free(BN_MONT_CTX *mont) |
561 { | 402 { |
562 if(mont == NULL) | 403 if(mont == NULL) |
563 return; | 404 return; |
564 | 405 |
565 BN_free(&(mont->RR)); | 406 BN_free(&(mont->RR)); |
566 BN_free(&(mont->N)); | 407 BN_free(&(mont->N)); |
(...skipping 11 matching lines...) Expand all Loading... |
578 if((Ri = BN_CTX_get(ctx)) == NULL) goto err; | 419 if((Ri = BN_CTX_get(ctx)) == NULL) goto err; |
579 R= &(mont->RR); /* grab RR as a temp */ | 420 R= &(mont->RR); /* grab RR as a temp */ |
580 if (!BN_copy(&(mont->N),mod)) goto err; /* Set N */ | 421 if (!BN_copy(&(mont->N),mod)) goto err; /* Set N */ |
581 mont->N.neg = 0; | 422 mont->N.neg = 0; |
582 | 423 |
583 #ifdef MONT_WORD | 424 #ifdef MONT_WORD |
584 { | 425 { |
585 BIGNUM tmod; | 426 BIGNUM tmod; |
586 BN_ULONG buf[2]; | 427 BN_ULONG buf[2]; |
587 | 428 |
588 mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2; | |
589 BN_zero(R); | |
590 #if 0 /* for OpenSSL 0.9.9 mont->n0, would be "#if defined(OPENSSL_BN_ASM_MONT)
&& (BN_BITS2<=32)", | |
591 only certain BN_BITS2<=32 platforms actually need this */ | |
592 if (!(BN_set_bit(R,2*BN_BITS2))) goto err; /* R */ | |
593 #else | |
594 if (!(BN_set_bit(R,BN_BITS2))) goto err; /* R */ | |
595 #endif | |
596 | |
597 buf[0]=mod->d[0]; /* tmod = N mod word size */ | |
598 buf[1]=0; | |
599 | |
600 BN_init(&tmod); | 429 BN_init(&tmod); |
601 tmod.d=buf; | 430 tmod.d=buf; |
602 tmod.top = buf[0] != 0 ? 1 : 0; | |
603 tmod.dmax=2; | 431 tmod.dmax=2; |
604 tmod.neg=0; | 432 tmod.neg=0; |
605 | 433 |
606 #if 0 /* for OpenSSL 0.9.9 mont->n0, would be "#if defined(OPENSSL_BN_ASM_MONT)
&& (BN_BITS2<=32)"; | 434 » » mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2; |
607 only certain BN_BITS2<=32 platforms actually need this */ | 435 |
| 436 #if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32) |
| 437 » » /* Only certain BN_BITS2<=32 platforms actually make use of |
| 438 » » * n0[1], and we could use the #else case (with a shorter R |
| 439 » » * value) for the others. However, currently only the assembler |
| 440 » » * files do know which is which. */ |
| 441 |
| 442 » » BN_zero(R); |
| 443 » » if (!(BN_set_bit(R,2*BN_BITS2))) goto err; |
| 444 |
608 tmod.top=0; | 445 tmod.top=0; |
609 if ((buf[0] = mod->d[0])) tmod.top=1; | 446 if ((buf[0] = mod->d[0])) tmod.top=1; |
610 if ((buf[1] = mod->top>1 ? mod->d[1] : 0)) tmod.top=2; | 447 if ((buf[1] = mod->top>1 ? mod->d[1] : 0)) tmod.top=2; |
611 | 448 |
612 if ((BN_mod_inverse(Ri,R,&tmod,ctx)) == NULL) | 449 if ((BN_mod_inverse(Ri,R,&tmod,ctx)) == NULL) |
613 goto err; | 450 goto err; |
614 if (!BN_lshift(Ri,Ri,2*BN_BITS2)) goto err; /* R*Ri */ | 451 if (!BN_lshift(Ri,Ri,2*BN_BITS2)) goto err; /* R*Ri */ |
615 if (!BN_is_zero(Ri)) | 452 if (!BN_is_zero(Ri)) |
616 { | 453 { |
617 if (!BN_sub_word(Ri,1)) goto err; | 454 if (!BN_sub_word(Ri,1)) goto err; |
618 } | 455 } |
619 else /* if N mod word size == 1 */ | 456 else /* if N mod word size == 1 */ |
620 { | 457 { |
621 if (bn_expand(Ri,(int)sizeof(BN_ULONG)*2) == NULL) | 458 if (bn_expand(Ri,(int)sizeof(BN_ULONG)*2) == NULL) |
622 goto err; | 459 goto err; |
623 /* Ri-- (mod double word size) */ | 460 /* Ri-- (mod double word size) */ |
624 Ri->neg=0; | 461 Ri->neg=0; |
625 Ri->d[0]=BN_MASK2; | 462 Ri->d[0]=BN_MASK2; |
626 Ri->d[1]=BN_MASK2; | 463 Ri->d[1]=BN_MASK2; |
627 Ri->top=2; | 464 Ri->top=2; |
628 } | 465 } |
629 if (!BN_div(Ri,NULL,Ri,&tmod,ctx)) goto err; | 466 if (!BN_div(Ri,NULL,Ri,&tmod,ctx)) goto err; |
630 /* Ni = (R*Ri-1)/N, | 467 /* Ni = (R*Ri-1)/N, |
631 * keep only couple of least significant words: */ | 468 * keep only couple of least significant words: */ |
632 mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0; | 469 mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0; |
633 mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0; | 470 mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0; |
634 #else | 471 #else |
| 472 BN_zero(R); |
| 473 if (!(BN_set_bit(R,BN_BITS2))) goto err; /* R */ |
| 474 |
| 475 buf[0]=mod->d[0]; /* tmod = N mod word size */ |
| 476 buf[1]=0; |
| 477 tmod.top = buf[0] != 0 ? 1 : 0; |
635 /* Ri = R^-1 mod N*/ | 478 /* Ri = R^-1 mod N*/ |
636 if ((BN_mod_inverse(Ri,R,&tmod,ctx)) == NULL) | 479 if ((BN_mod_inverse(Ri,R,&tmod,ctx)) == NULL) |
637 goto err; | 480 goto err; |
638 if (!BN_lshift(Ri,Ri,BN_BITS2)) goto err; /* R*Ri */ | 481 if (!BN_lshift(Ri,Ri,BN_BITS2)) goto err; /* R*Ri */ |
639 if (!BN_is_zero(Ri)) | 482 if (!BN_is_zero(Ri)) |
640 { | 483 { |
641 if (!BN_sub_word(Ri,1)) goto err; | 484 if (!BN_sub_word(Ri,1)) goto err; |
642 } | 485 } |
643 else /* if N mod word size == 1 */ | 486 else /* if N mod word size == 1 */ |
644 { | 487 { |
645 if (!BN_set_word(Ri,BN_MASK2)) goto err; /* Ri-- (mod w
ord size) */ | 488 if (!BN_set_word(Ri,BN_MASK2)) goto err; /* Ri-- (mod w
ord size) */ |
646 } | 489 } |
647 if (!BN_div(Ri,NULL,Ri,&tmod,ctx)) goto err; | 490 if (!BN_div(Ri,NULL,Ri,&tmod,ctx)) goto err; |
648 /* Ni = (R*Ri-1)/N, | 491 /* Ni = (R*Ri-1)/N, |
649 * keep only least significant word: */ | 492 * keep only least significant word: */ |
650 # if 0 /* for OpenSSL 0.9.9 mont->n0 */ | |
651 mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0; | 493 mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0; |
652 mont->n0[1] = 0; | 494 mont->n0[1] = 0; |
653 # else | |
654 mont->n0 = (Ri->top > 0) ? Ri->d[0] : 0; | |
655 # endif | |
656 #endif | 495 #endif |
657 } | 496 } |
658 #else /* !MONT_WORD */ | 497 #else /* !MONT_WORD */ |
659 { /* bignum version */ | 498 { /* bignum version */ |
660 mont->ri=BN_num_bits(&mont->N); | 499 mont->ri=BN_num_bits(&mont->N); |
661 BN_zero(R); | 500 BN_zero(R); |
662 if (!BN_set_bit(R,mont->ri)) goto err; /* R = 2^ri */ | 501 if (!BN_set_bit(R,mont->ri)) goto err; /* R = 2^ri */ |
663 /* Ri = R^-1 mod N*/ | 502 /* Ri = R^-1 mod N*/ |
664 if ((BN_mod_inverse(Ri,R,&mont->N,ctx)) == NULL) | 503 if ((BN_mod_inverse(Ri,R,&mont->N,ctx)) == NULL) |
665 goto err; | 504 goto err; |
(...skipping 16 matching lines...) Expand all Loading... |
682 } | 521 } |
683 | 522 |
684 BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from) | 523 BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from) |
685 { | 524 { |
686 if (to == from) return(to); | 525 if (to == from) return(to); |
687 | 526 |
688 if (!BN_copy(&(to->RR),&(from->RR))) return NULL; | 527 if (!BN_copy(&(to->RR),&(from->RR))) return NULL; |
689 if (!BN_copy(&(to->N),&(from->N))) return NULL; | 528 if (!BN_copy(&(to->N),&(from->N))) return NULL; |
690 if (!BN_copy(&(to->Ni),&(from->Ni))) return NULL; | 529 if (!BN_copy(&(to->Ni),&(from->Ni))) return NULL; |
691 to->ri=from->ri; | 530 to->ri=from->ri; |
692 #if 0 /* for OpenSSL 0.9.9 mont->n0 */ | |
693 to->n0[0]=from->n0[0]; | 531 to->n0[0]=from->n0[0]; |
694 to->n0[1]=from->n0[1]; | 532 to->n0[1]=from->n0[1]; |
695 #else | |
696 to->n0=from->n0; | |
697 #endif | |
698 return(to); | 533 return(to); |
699 } | 534 } |
700 | 535 |
701 BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock, | 536 BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock, |
702 const BIGNUM *mod, BN_CTX *ctx) | 537 const BIGNUM *mod, BN_CTX *ctx) |
703 { | 538 { |
704 int got_write_lock = 0; | 539 int got_write_lock = 0; |
705 BN_MONT_CTX *ret; | 540 BN_MONT_CTX *ret; |
706 | 541 |
707 CRYPTO_r_lock(lock); | 542 CRYPTO_r_lock(lock); |
(...skipping 15 matching lines...) Expand all Loading... |
723 | 558 |
724 ret = *pmont; | 559 ret = *pmont; |
725 | 560 |
726 if (got_write_lock) | 561 if (got_write_lock) |
727 CRYPTO_w_unlock(lock); | 562 CRYPTO_w_unlock(lock); |
728 else | 563 else |
729 CRYPTO_r_unlock(lock); | 564 CRYPTO_r_unlock(lock); |
730 | 565 |
731 return ret; | 566 return ret; |
732 } | 567 } |
OLD | NEW |