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_recp.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#include <stdio.h> 78#include "cryptlib.h" 79#include "bn_lcl.h" 80 81void BN_RECP_CTX_init(BN_RECP_CTX *recp) 82 { 83 BN_init(&(recp->N)); 84 BN_init(&(recp->Nr)); 85 recp->num_bits=0; 86 recp->flags=0; 87 } 88 89BN_RECP_CTX *BN_RECP_CTX_new(void) 90 { 91 BN_RECP_CTX *ret; 92 93 if ((ret=(BN_RECP_CTX *)Malloc(sizeof(BN_RECP_CTX))) == NULL) 94 return(NULL); 95 96 BN_RECP_CTX_init(ret); 97 ret->flags=BN_FLG_MALLOCED; 98 return(ret); 99 } 100 101void BN_RECP_CTX_free(BN_RECP_CTX *recp) 102 { 103 if(recp == NULL) 104 return; 105 106 BN_free(&(recp->N)); 107 BN_free(&(recp->Nr)); 108 if (recp->flags & BN_FLG_MALLOCED) 109 Free(recp); 110 } 111 112int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx) 113 { 114 BN_copy(&(recp->N),d); 115 BN_zero(&(recp->Nr)); 116 recp->num_bits=BN_num_bits(d); 117 recp->shift=0; 118 return(1); 119 } 120 121int BN_mod_mul_reciprocal(BIGNUM *r, BIGNUM *x, BIGNUM *y, BN_RECP_CTX *recp, 122 BN_CTX *ctx) 123 { 124 int ret=0; 125 BIGNUM *a; 126 127 BN_CTX_start(ctx); 128 if ((a = BN_CTX_get(ctx)) == NULL) goto err; 129 if (y != NULL) 130 { 131 if (x == y) 132 { if (!BN_sqr(a,x,ctx)) goto err; } 133 else 134 { if (!BN_mul(a,x,y,ctx)) goto err; } 135 } 136 else 137 a=x; /* Just do the mod */ 138 139 BN_div_recp(NULL,r,a,recp,ctx); 140 ret=1; 141err: 142 BN_CTX_end(ctx); 143 return(ret); 144 } 145 146int BN_div_recp(BIGNUM *dv, BIGNUM *rem, BIGNUM *m, BN_RECP_CTX *recp, 147 BN_CTX *ctx) 148 { 149 int i,j,ret=0; 150 BIGNUM *a,*b,*d,*r; 151 152 BN_CTX_start(ctx); 153 a=BN_CTX_get(ctx); 154 b=BN_CTX_get(ctx); 155 if (dv != NULL) 156 d=dv; 157 else 158 d=BN_CTX_get(ctx); 159 if (rem != NULL) 160 r=rem; 161 else 162 r=BN_CTX_get(ctx); 163 if (a == NULL || b == NULL || d == NULL || r == NULL) goto err; 164 165 if (BN_ucmp(m,&(recp->N)) < 0) 166 { 167 BN_zero(d); 168 BN_copy(r,m); 169 BN_CTX_end(ctx); 170 return(1); 171 } 172 173 /* We want the remainder 174 * Given input of ABCDEF / ab 175 * we need multiply ABCDEF by 3 digests of the reciprocal of ab 176 * 177 */ 178 i=BN_num_bits(m); 179 180 j=recp->num_bits<<1; 181 if (j>i) i=j; 182 j>>=1; 183 184 if (i != recp->shift) 185 recp->shift=BN_reciprocal(&(recp->Nr),&(recp->N), 186 i,ctx); 187 188 if (!BN_rshift(a,m,j)) goto err; 189 if (!BN_mul(b,a,&(recp->Nr),ctx)) goto err; 190 if (!BN_rshift(d,b,i-j)) goto err; 191 d->neg=0; 192 if (!BN_mul(b,&(recp->N),d,ctx)) goto err; 193 if (!BN_usub(r,m,b)) goto err; 194 r->neg=0; 195 196#if 1 197 j=0; 198 while (BN_ucmp(r,&(recp->N)) >= 0) 199 { 200 if (j++ > 2) 201 { 202 BNerr(BN_F_BN_MOD_MUL_RECIPROCAL,BN_R_BAD_RECIPROCAL); 203 goto err; 204 } 205 if (!BN_usub(r,r,&(recp->N))) goto err; 206 if (!BN_add_word(d,1)) goto err; 207 } 208#endif 209 210 r->neg=BN_is_zero(r)?0:m->neg; 211 d->neg=m->neg^recp->N.neg; 212 ret=1; 213err: 214 BN_CTX_end(ctx); 215 return(ret); 216 } 217 218/* len is the expected size of the result 219 * We actually calculate with an extra word of precision, so 220 * we can do faster division if the remainder is not required. 221 */ 222int BN_reciprocal(BIGNUM *r, BIGNUM *m, int len, BN_CTX *ctx) 223 { 224 int ret= -1; 225 BIGNUM t; 226 227 BN_init(&t); 228 229 BN_zero(&t); 230 if (!BN_set_bit(&t,len)) goto err; 231 232 if (!BN_div(r,NULL,&t,m,ctx)) goto err; 233 ret=len; 234err: 235 BN_free(&t); 236 return(ret); 237 } 238 239