1/* 2 * Copyright (c) 2000-2001,2011,2014 Apple Inc. All Rights Reserved. 3 * 4 * The contents of this file constitute Original Code as defined in and are 5 * subject to the Apple Public Source License Version 1.2 (the 'License'). 6 * You may not use this file except in compliance with the License. Please obtain 7 * a copy of the License at http://www.apple.com/publicsource and read it before 8 * using this file. 9 * 10 * This Original Code and all software distributed under the License are 11 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS 12 * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT 13 * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR 14 * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the 15 * specific language governing rights and limitations under the License. 16 */ 17 18 19/* crypto/bn/bn_mont.c */ 20/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 21 * All rights reserved. 22 * 23 * This package is an SSL implementation written 24 * by Eric Young (eay@cryptsoft.com). 25 * The implementation was written so as to conform with Netscapes SSL. 26 * 27 * This library is free for commercial and non-commercial use as long as 28 * the following conditions are aheared to. The following conditions 29 * apply to all code found in this distribution, be it the RC4, RSA, 30 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 31 * included with this distribution is covered by the same copyright terms 32 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 33 * 34 * Copyright remains Eric Young's, and as such any Copyright notices in 35 * the code are not to be removed. 36 * If this package is used in a product, Eric Young should be given attribution 37 * as the author of the parts of the library used. 38 * This can be in the form of a textual message at program startup or 39 * in documentation (online or textual) provided with the package. 40 * 41 * Redistribution and use in source and binary forms, with or without 42 * modification, are permitted provided that the following conditions 43 * are met: 44 * 1. Redistributions of source code must retain the copyright 45 * notice, this list of conditions and the following disclaimer. 46 * 2. Redistributions in binary form must reproduce the above copyright 47 * notice, this list of conditions and the following disclaimer in the 48 * documentation and/or other materials provided with the distribution. 49 * 3. All advertising materials mentioning features or use of this software 50 * must display the following acknowledgement: 51 * "This product includes cryptographic software written by 52 * Eric Young (eay@cryptsoft.com)" 53 * The word 'cryptographic' can be left out if the rouines from the library 54 * being used are not cryptographic related :-). 55 * 4. If you include any Windows specific code (or a derivative thereof) from 56 * the apps directory (application code) you must include an acknowledgement: 57 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 58 * 59 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 60 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 61 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 62 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 63 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 64 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 65 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 66 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 67 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 68 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 69 * SUCH DAMAGE. 70 * 71 * The licence and distribution terms for any publically available version or 72 * derivative of this code cannot be changed. i.e. this code cannot simply be 73 * copied and put under another distribution licence 74 * [including the GNU Public Licence.] 75 */ 76 77/* 78 * Details about Montgomery multiplication algorithms can be found at 79 * http://security.ece.orst.edu/publications.html, e.g. 80 * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and 81 * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf 82 */ 83 84#include <stdio.h> 85#include "cryptlib.h" 86#include "bn_lcl.h" 87 88#define MONT_WORD /* use the faster word-based algorithm */ 89 90int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b, 91 BN_MONT_CTX *mont, BN_CTX *ctx) 92 { 93 BIGNUM *tmp,*tmp2; 94 int ret=0; 95 96 BN_CTX_start(ctx); 97 tmp = BN_CTX_get(ctx); 98 tmp2 = BN_CTX_get(ctx); 99 if (tmp == NULL || tmp2 == NULL) goto err; 100 101 bn_check_top(tmp); 102 bn_check_top(tmp2); 103 104 if (a == b) 105 { 106#if 0 107 bn_wexpand(tmp,a->top*2); 108 bn_wexpand(tmp2,a->top*4); 109 bn_sqr_recursive(tmp->d,a->d,a->top,tmp2->d); 110 tmp->top=a->top*2; 111 if (tmp->d[tmp->top-1] == 0) 112 tmp->top--; 113#else 114 if (!BN_sqr(tmp,a,ctx)) goto err; 115#endif 116 } 117 else 118 { 119 if (!BN_mul(tmp,a,b,ctx)) goto err; 120 } 121 /* reduce from aRR to aR */ 122 if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err; 123 ret=1; 124err: 125 BN_CTX_end(ctx); 126 return(ret); 127 } 128 129int BN_from_montgomery(BIGNUM *ret, BIGNUM *a, BN_MONT_CTX *mont, 130 BN_CTX *ctx) 131 { 132 int retn=0; 133 134#ifdef MONT_WORD 135 BIGNUM *n,*r; 136 BN_ULONG *ap,*np,*rp,n0,v,*nrp; 137 int al,nl,max,i,x,ri; 138 139 BN_CTX_start(ctx); 140 if ((r = BN_CTX_get(ctx)) == NULL) goto err; 141 142 if (!BN_copy(r,a)) goto err; 143 n= &(mont->N); 144 145 ap=a->d; 146 /* mont->ri is the size of mont->N in bits (rounded up 147 to the word size) */ 148 al=ri=mont->ri/BN_BITS2; 149 150 nl=n->top; 151 if ((al == 0) || (nl == 0)) { r->top=0; return(1); } 152 153 max=(nl+al+1); /* allow for overflow (no?) XXX */ 154 if (bn_wexpand(r,max) == NULL) goto err; 155 if (bn_wexpand(ret,max) == NULL) goto err; 156 157 r->neg=a->neg^n->neg; 158 np=n->d; 159 rp=r->d; 160 nrp= &(r->d[nl]); 161 162 /* clear the top words of T */ 163#if 1 164 for (i=r->top; i<max; i++) /* memset? XXX */ 165 r->d[i]=0; 166#else 167 memset(&(r->d[r->top]),0,(max-r->top)*sizeof(BN_ULONG)); 168#endif 169 170 r->top=max; 171 n0=mont->n0; 172 173#ifdef BN_COUNT 174 printf("word BN_from_montgomery %d * %d\n",nl,nl); 175#endif 176 for (i=0; i<nl; i++) 177 { 178 v=bn_mul_add_words(rp,np,nl,(rp[0]*n0)&BN_MASK2); 179 nrp++; 180 rp++; 181 if (((nrp[-1]+=v)&BN_MASK2) >= v) 182 continue; 183 else 184 { 185 if (((++nrp[0])&BN_MASK2) != 0) continue; 186 if (((++nrp[1])&BN_MASK2) != 0) continue; 187 for (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ; 188 } 189 } 190 bn_fix_top(r); 191 192 /* mont->ri will be a multiple of the word size */ 193#if 0 194 BN_rshift(ret,r,mont->ri); 195#else 196 x=ri; 197 rp=ret->d; 198 ap= &(r->d[x]); 199 if (r->top < x) 200 al=0; 201 else 202 al=r->top-x; 203 ret->top=al; 204 al-=4; 205 for (i=0; i<al; i+=4) 206 { 207 BN_ULONG t1,t2,t3,t4; 208 209 t1=ap[i+0]; 210 t2=ap[i+1]; 211 t3=ap[i+2]; 212 t4=ap[i+3]; 213 rp[i+0]=t1; 214 rp[i+1]=t2; 215 rp[i+2]=t3; 216 rp[i+3]=t4; 217 } 218 al+=4; 219 for (; i<al; i++) 220 rp[i]=ap[i]; 221#endif 222#else /* !MONT_WORD */ 223 BIGNUM *t1,*t2; 224 225 BN_CTX_start(ctx); 226 t1 = BN_CTX_get(ctx); 227 t2 = BN_CTX_get(ctx); 228 if (t1 == NULL || t2 == NULL) goto err; 229 230 if (!BN_copy(t1,a)) goto err; 231 BN_mask_bits(t1,mont->ri); 232 233 if (!BN_mul(t2,t1,&mont->Ni,ctx)) goto err; 234 BN_mask_bits(t2,mont->ri); 235 236 if (!BN_mul(t1,t2,&mont->N,ctx)) goto err; 237 if (!BN_add(t2,a,t1)) goto err; 238 BN_rshift(ret,t2,mont->ri); 239#endif /* MONT_WORD */ 240 241 if (BN_ucmp(ret, &(mont->N)) >= 0) 242 { 243 BN_usub(ret,ret,&(mont->N)); 244 } 245 retn=1; 246 err: 247 BN_CTX_end(ctx); 248 return(retn); 249 } 250 251BN_MONT_CTX *BN_MONT_CTX_new(void) 252 { 253 BN_MONT_CTX *ret; 254 255 if ((ret=(BN_MONT_CTX *)Malloc(sizeof(BN_MONT_CTX))) == NULL) 256 return(NULL); 257 258 BN_MONT_CTX_init(ret); 259 ret->flags=BN_FLG_MALLOCED; 260 return(ret); 261 } 262 263void BN_MONT_CTX_init(BN_MONT_CTX *ctx) 264 { 265 ctx->ri=0; 266 BN_init(&(ctx->RR)); 267 BN_init(&(ctx->N)); 268 BN_init(&(ctx->Ni)); 269 ctx->flags=0; 270 } 271 272void BN_MONT_CTX_free(BN_MONT_CTX *mont) 273 { 274 if(mont == NULL) 275 return; 276 277 BN_free(&(mont->RR)); 278 BN_free(&(mont->N)); 279 BN_free(&(mont->Ni)); 280 if (mont->flags & BN_FLG_MALLOCED) 281 Free(mont); 282 } 283 284int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx) 285 { 286 BIGNUM Ri,*R; 287 288 BN_init(&Ri); 289 R= &(mont->RR); /* grab RR as a temp */ 290 BN_copy(&(mont->N),mod); /* Set N */ 291 292#ifdef MONT_WORD 293 { 294 BIGNUM tmod; 295 BN_ULONG buf[2]; 296 297 mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2; 298 BN_zero(R); 299 BN_set_bit(R,BN_BITS2); /* R */ 300 301 buf[0]=mod->d[0]; /* tmod = N mod word size */ 302 buf[1]=0; 303 tmod.d=buf; 304 tmod.top=1; 305 tmod.max=2; 306 tmod.neg=mod->neg; 307 /* Ri = R^-1 mod N*/ 308 if ((BN_mod_inverse(&Ri,R,&tmod,ctx)) == NULL) 309 goto err; 310 BN_lshift(&Ri,&Ri,BN_BITS2); /* R*Ri */ 311 if (!BN_is_zero(&Ri)) 312 BN_sub_word(&Ri,1); 313 else /* if N mod word size == 1 */ 314 BN_set_word(&Ri,BN_MASK2); /* Ri-- (mod word size) */ 315 BN_div(&Ri,NULL,&Ri,&tmod,ctx); /* Ni = (R*Ri-1)/N, 316 * keep only least significant word: */ 317 mont->n0=Ri.d[0]; 318 BN_free(&Ri); 319 } 320#else /* !MONT_WORD */ 321 { /* bignum version */ 322 mont->ri=BN_num_bits(mod); 323 BN_zero(R); 324 BN_set_bit(R,mont->ri); /* R = 2^ri */ 325 /* Ri = R^-1 mod N*/ 326 if ((BN_mod_inverse(&Ri,R,mod,ctx)) == NULL) 327 goto err; 328 BN_lshift(&Ri,&Ri,mont->ri); /* R*Ri */ 329 BN_sub_word(&Ri,1); 330 /* Ni = (R*Ri-1) / N */ 331 BN_div(&(mont->Ni),NULL,&Ri,mod,ctx); 332 BN_free(&Ri); 333 } 334#endif 335 336 /* setup RR for conversions */ 337 BN_zero(&(mont->RR)); 338 BN_set_bit(&(mont->RR),mont->ri*2); 339 BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx); 340 341 return(1); 342err: 343 return(0); 344 } 345 346BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from) 347 { 348 if (to == from) return(to); 349 350 BN_copy(&(to->RR),&(from->RR)); 351 BN_copy(&(to->N),&(from->N)); 352 BN_copy(&(to->Ni),&(from->Ni)); 353 to->ri=from->ri; 354 to->n0=from->n0; 355 return(to); 356 } 357 358