]>
Commit | Line | Data |
---|---|---|
d02b48c6 | 1 | /* crypto/bn/bn_mont.c */ |
58964a49 | 2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
d02b48c6 RE |
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 | ||
1b3b0a54 | 59 | /* |
b99b1107 BM |
60 | * Details about Montgomery multiplication algorithms can be found at |
61 | * http://security.ece.orst.edu/publications.html, e.g. | |
62 | * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and | |
63 | * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf | |
1b3b0a54 RE |
64 | */ |
65 | ||
d02b48c6 RE |
66 | #include <stdio.h> |
67 | #include "cryptlib.h" | |
68 | #include "bn_lcl.h" | |
69 | ||
6535eb17 UM |
70 | #define MONT_WORD /* use the faster word-based algorithm */ |
71 | ||
020fc820 | 72 | int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
84c15db5 | 73 | BN_MONT_CTX *mont, BN_CTX *ctx) |
d02b48c6 | 74 | { |
757e392d | 75 | BIGNUM *tmp; |
0b8fa44e | 76 | int ret=0; |
dfeab068 | 77 | |
9b141126 UM |
78 | BN_CTX_start(ctx); |
79 | tmp = BN_CTX_get(ctx); | |
e1a8ac49 | 80 | if (tmp == NULL) goto err; |
d02b48c6 | 81 | |
dfeab068 | 82 | bn_check_top(tmp); |
d02b48c6 RE |
83 | if (a == b) |
84 | { | |
85 | if (!BN_sqr(tmp,a,ctx)) goto err; | |
86 | } | |
87 | else | |
88 | { | |
dfeab068 | 89 | if (!BN_mul(tmp,a,b,ctx)) goto err; |
d02b48c6 RE |
90 | } |
91 | /* reduce from aRR to aR */ | |
92 | if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err; | |
0b8fa44e | 93 | ret=1; |
d02b48c6 | 94 | err: |
0b8fa44e UM |
95 | BN_CTX_end(ctx); |
96 | return(ret); | |
d02b48c6 RE |
97 | } |
98 | ||
cbd48ba6 | 99 | int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, |
6b691a5c | 100 | BN_CTX *ctx) |
d02b48c6 | 101 | { |
e93f9a32 | 102 | int retn=0; |
d02b48c6 | 103 | |
6535eb17 UM |
104 | #ifdef MONT_WORD |
105 | BIGNUM *n,*r; | |
106 | BN_ULONG *ap,*np,*rp,n0,v,*nrp; | |
107 | int al,nl,max,i,x,ri; | |
d02b48c6 | 108 | |
6535eb17 UM |
109 | BN_CTX_start(ctx); |
110 | if ((r = BN_CTX_get(ctx)) == NULL) goto err; | |
d02b48c6 | 111 | |
6535eb17 UM |
112 | if (!BN_copy(r,a)) goto err; |
113 | n= &(mont->N); | |
d02b48c6 | 114 | |
6535eb17 UM |
115 | ap=a->d; |
116 | /* mont->ri is the size of mont->N in bits (rounded up | |
117 | to the word size) */ | |
118 | al=ri=mont->ri/BN_BITS2; | |
119 | ||
120 | nl=n->top; | |
121 | if ((al == 0) || (nl == 0)) { r->top=0; return(1); } | |
d02b48c6 | 122 | |
6535eb17 UM |
123 | max=(nl+al+1); /* allow for overflow (no?) XXX */ |
124 | if (bn_wexpand(r,max) == NULL) goto err; | |
125 | if (bn_wexpand(ret,max) == NULL) goto err; | |
d02b48c6 | 126 | |
6535eb17 UM |
127 | r->neg=a->neg^n->neg; |
128 | np=n->d; | |
129 | rp=r->d; | |
130 | nrp= &(r->d[nl]); | |
d02b48c6 | 131 | |
6535eb17 | 132 | /* clear the top words of T */ |
58964a49 | 133 | #if 1 |
6535eb17 UM |
134 | for (i=r->top; i<max; i++) /* memset? XXX */ |
135 | r->d[i]=0; | |
58964a49 | 136 | #else |
6535eb17 | 137 | memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG)); |
58964a49 | 138 | #endif |
d02b48c6 | 139 | |
6535eb17 UM |
140 | r->top=max; |
141 | n0=mont->n0; | |
d02b48c6 | 142 | |
dfeab068 | 143 | #ifdef BN_COUNT |
cbd48ba6 | 144 | fprintf(stderr,"word BN_from_montgomery %d * %d\n",nl,nl); |
dfeab068 | 145 | #endif |
6535eb17 UM |
146 | for (i=0; i<nl; i++) |
147 | { | |
2d978cbd DSH |
148 | #ifdef __TANDEM |
149 | { | |
150 | long long t1; | |
151 | long long t2; | |
152 | long long t3; | |
153 | t1 = rp[0] * (n0 & 0177777); | |
154 | t2 = 037777600000l; | |
155 | t2 = n0 & t2; | |
156 | t3 = rp[0] & 0177777; | |
157 | t2 = (t3 * t2) & BN_MASK2; | |
158 | t1 = t1 + t2; | |
159 | v=bn_mul_add_words(rp,np,nl,(BN_ULONG) t1); | |
160 | } | |
161 | #else | |
6535eb17 | 162 | v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2); |
2d978cbd | 163 | #endif |
6535eb17 UM |
164 | nrp++; |
165 | rp++; | |
166 | if (((nrp[-1]+=v)&BN_MASK2) >= v) | |
167 | continue; | |
168 | else | |
58964a49 | 169 | { |
6535eb17 UM |
170 | if (((++nrp[0])&BN_MASK2) != 0) continue; |
171 | if (((++nrp[1])&BN_MASK2) != 0) continue; | |
172 | for (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ; | |
58964a49 | 173 | } |
6535eb17 UM |
174 | } |
175 | bn_fix_top(r); | |
176 | ||
177 | /* mont->ri will be a multiple of the word size */ | |
dfeab068 | 178 | #if 0 |
6535eb17 | 179 | BN_rshift(ret,r,mont->ri); |
dfeab068 | 180 | #else |
1d84fd64 | 181 | ret->neg = r->neg; |
6535eb17 UM |
182 | x=ri; |
183 | rp=ret->d; | |
184 | ap= &(r->d[x]); | |
185 | if (r->top < x) | |
186 | al=0; | |
187 | else | |
188 | al=r->top-x; | |
189 | ret->top=al; | |
190 | al-=4; | |
191 | for (i=0; i<al; i+=4) | |
192 | { | |
193 | BN_ULONG t1,t2,t3,t4; | |
194 | ||
195 | t1=ap[i+0]; | |
196 | t2=ap[i+1]; | |
197 | t3=ap[i+2]; | |
198 | t4=ap[i+3]; | |
199 | rp[i+0]=t1; | |
200 | rp[i+1]=t2; | |
201 | rp[i+2]=t3; | |
202 | rp[i+3]=t4; | |
203 | } | |
204 | al+=4; | |
205 | for (; i<al; i++) | |
206 | rp[i]=ap[i]; | |
58964a49 | 207 | #endif |
6535eb17 UM |
208 | #else /* !MONT_WORD */ |
209 | BIGNUM *t1,*t2; | |
58964a49 | 210 | |
6535eb17 UM |
211 | BN_CTX_start(ctx); |
212 | t1 = BN_CTX_get(ctx); | |
213 | t2 = BN_CTX_get(ctx); | |
214 | if (t1 == NULL || t2 == NULL) goto err; | |
215 | ||
216 | if (!BN_copy(t1,a)) goto err; | |
217 | BN_mask_bits(t1,mont->ri); | |
218 | ||
219 | if (!BN_mul(t2,t1,&mont->Ni,ctx)) goto err; | |
220 | BN_mask_bits(t2,mont->ri); | |
221 | ||
222 | if (!BN_mul(t1,t2,&mont->N,ctx)) goto err; | |
223 | if (!BN_add(t2,a,t1)) goto err; | |
9cdf87f1 | 224 | if (!BN_rshift(ret,t2,mont->ri)) goto err; |
6535eb17 UM |
225 | #endif /* MONT_WORD */ |
226 | ||
227 | if (BN_ucmp(ret, &(mont->N)) >= 0) | |
58964a49 | 228 | { |
8dea52fa | 229 | if (!BN_usub(ret,ret,&(mont->N))) goto err; |
dfeab068 | 230 | } |
6535eb17 | 231 | retn=1; |
e93f9a32 | 232 | err: |
9b141126 | 233 | BN_CTX_end(ctx); |
e93f9a32 | 234 | return(retn); |
dfeab068 | 235 | } |
d02b48c6 | 236 | |
6b691a5c | 237 | BN_MONT_CTX *BN_MONT_CTX_new(void) |
d02b48c6 RE |
238 | { |
239 | BN_MONT_CTX *ret; | |
240 | ||
26a3a48d | 241 | if ((ret=(BN_MONT_CTX *)OPENSSL_malloc(sizeof(BN_MONT_CTX))) == NULL) |
d02b48c6 | 242 | return(NULL); |
dfeab068 RE |
243 | |
244 | BN_MONT_CTX_init(ret); | |
245 | ret->flags=BN_FLG_MALLOCED; | |
d02b48c6 RE |
246 | return(ret); |
247 | } | |
248 | ||
6b691a5c | 249 | void BN_MONT_CTX_init(BN_MONT_CTX *ctx) |
dfeab068 | 250 | { |
dfeab068 RE |
251 | ctx->ri=0; |
252 | BN_init(&(ctx->RR)); | |
253 | BN_init(&(ctx->N)); | |
254 | BN_init(&(ctx->Ni)); | |
255 | ctx->flags=0; | |
256 | } | |
257 | ||
6b691a5c | 258 | void BN_MONT_CTX_free(BN_MONT_CTX *mont) |
d02b48c6 | 259 | { |
e03ddfae BL |
260 | if(mont == NULL) |
261 | return; | |
262 | ||
dfeab068 RE |
263 | BN_free(&(mont->RR)); |
264 | BN_free(&(mont->N)); | |
265 | BN_free(&(mont->Ni)); | |
266 | if (mont->flags & BN_FLG_MALLOCED) | |
26a3a48d | 267 | OPENSSL_free(mont); |
d02b48c6 RE |
268 | } |
269 | ||
84c15db5 | 270 | int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx) |
d02b48c6 | 271 | { |
dfeab068 RE |
272 | BIGNUM Ri,*R; |
273 | ||
274 | BN_init(&Ri); | |
275 | R= &(mont->RR); /* grab RR as a temp */ | |
276 | BN_copy(&(mont->N),mod); /* Set N */ | |
8dea52fa | 277 | mont->N.neg = 0; |
dfeab068 | 278 | |
6535eb17 | 279 | #ifdef MONT_WORD |
dfeab068 RE |
280 | { |
281 | BIGNUM tmod; | |
282 | BN_ULONG buf[2]; | |
283 | ||
dfeab068 | 284 | mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2; |
9cdf87f1 RL |
285 | if (!(BN_zero(R))) goto err; |
286 | if (!(BN_set_bit(R,BN_BITS2))) goto err; /* R */ | |
dfeab068 | 287 | |
e93f9a32 | 288 | buf[0]=mod->d[0]; /* tmod = N mod word size */ |
dfeab068 RE |
289 | buf[1]=0; |
290 | tmod.d=buf; | |
291 | tmod.top=1; | |
2d978cbd | 292 | tmod.dmax=2; |
8dea52fa | 293 | tmod.neg=0; |
e93f9a32 | 294 | /* Ri = R^-1 mod N*/ |
dfeab068 RE |
295 | if ((BN_mod_inverse(&Ri,R,&tmod,ctx)) == NULL) |
296 | goto err; | |
8dea52fa | 297 | if (!BN_lshift(&Ri,&Ri,BN_BITS2)) goto err; /* R*Ri */ |
dfeab068 | 298 | if (!BN_is_zero(&Ri)) |
8dea52fa BM |
299 | { |
300 | if (!BN_sub_word(&Ri,1)) goto err; | |
301 | } | |
e93f9a32 | 302 | else /* if N mod word size == 1 */ |
8dea52fa BM |
303 | { |
304 | if (!BN_set_word(&Ri,BN_MASK2)) goto err; /* Ri-- (mod word size) */ | |
305 | } | |
306 | if (!BN_div(&Ri,NULL,&Ri,&tmod,ctx)) goto err; | |
307 | /* Ni = (R*Ri-1)/N, | |
308 | * keep only least significant word: */ | |
309 | mont->n0 = (Ri.top > 0) ? Ri.d[0] : 0; | |
dfeab068 | 310 | BN_free(&Ri); |
dfeab068 | 311 | } |
6535eb17 | 312 | #else /* !MONT_WORD */ |
e93f9a32 | 313 | { /* bignum version */ |
8dea52fa BM |
314 | mont->ri=BN_num_bits(&mont->N); |
315 | if (!BN_zero(R)) goto err; | |
316 | if (!BN_set_bit(R,mont->ri)) goto err; /* R = 2^ri */ | |
317 | /* Ri = R^-1 mod N*/ | |
318 | if ((BN_mod_inverse(&Ri,R,&mont->N,ctx)) == NULL) | |
dfeab068 | 319 | goto err; |
8dea52fa BM |
320 | if (!BN_lshift(&Ri,&Ri,mont->ri)) goto err; /* R*Ri */ |
321 | if (!BN_sub_word(&Ri,1)) goto err; | |
e93f9a32 | 322 | /* Ni = (R*Ri-1) / N */ |
8dea52fa | 323 | if (!BN_div(&(mont->Ni),NULL,&Ri,&mont->N,ctx)) goto err; |
dfeab068 RE |
324 | BN_free(&Ri); |
325 | } | |
d02b48c6 RE |
326 | #endif |
327 | ||
328 | /* setup RR for conversions */ | |
8dea52fa BM |
329 | if (!BN_zero(&(mont->RR))) goto err; |
330 | if (!BN_set_bit(&(mont->RR),mont->ri*2)) goto err; | |
331 | if (!BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx)) goto err; | |
d02b48c6 RE |
332 | |
333 | return(1); | |
334 | err: | |
335 | return(0); | |
336 | } | |
337 | ||
6b691a5c | 338 | BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from) |
dfeab068 RE |
339 | { |
340 | if (to == from) return(to); | |
341 | ||
156e8557 BM |
342 | if (!BN_copy(&(to->RR),&(from->RR))) return NULL; |
343 | if (!BN_copy(&(to->N),&(from->N))) return NULL; | |
344 | if (!BN_copy(&(to->Ni),&(from->Ni))) return NULL; | |
dfeab068 RE |
345 | to->ri=from->ri; |
346 | to->n0=from->n0; | |
347 | return(to); | |
348 | } | |
349 |