1656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* crypto/bn/bn_recp.c */ 2656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * All rights reserved. 4656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 5656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * This package is an SSL implementation written 6656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * by Eric Young (eay@cryptsoft.com). 7656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * The implementation was written so as to conform with Netscapes SSL. 8656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 9656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * This library is free for commercial and non-commercial use as long as 10656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * the following conditions are aheared to. The following conditions 11656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * apply to all code found in this distribution, be it the RC4, RSA, 12656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * included with this distribution is covered by the same copyright terms 14656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 16656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Copyright remains Eric Young's, and as such any Copyright notices in 17656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * the code are not to be removed. 18656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * If this package is used in a product, Eric Young should be given attribution 19656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * as the author of the parts of the library used. 20656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * This can be in the form of a textual message at program startup or 21656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * in documentation (online or textual) provided with the package. 22656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 23656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Redistribution and use in source and binary forms, with or without 24656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * modification, are permitted provided that the following conditions 25656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * are met: 26656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 1. Redistributions of source code must retain the copyright 27656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * notice, this list of conditions and the following disclaimer. 28656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 2. Redistributions in binary form must reproduce the above copyright 29656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * notice, this list of conditions and the following disclaimer in the 30656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * documentation and/or other materials provided with the distribution. 31656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 3. All advertising materials mentioning features or use of this software 32656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * must display the following acknowledgement: 33656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * "This product includes cryptographic software written by 34656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Eric Young (eay@cryptsoft.com)" 35656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * The word 'cryptographic' can be left out if the rouines from the library 36656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * being used are not cryptographic related :-). 37656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 4. If you include any Windows specific code (or a derivative thereof) from 38656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * the apps directory (application code) you must include an acknowledgement: 39656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 41656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * SUCH DAMAGE. 52656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 53656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * The licence and distribution terms for any publically available version or 54656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * derivative of this code cannot be changed. i.e. this code cannot simply be 55656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * copied and put under another distribution licence 56656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * [including the GNU Public Licence.] 57656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 58656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 59656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#include <stdio.h> 60656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#include "cryptlib.h" 61656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#include "bn_lcl.h" 62656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 63656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectvoid BN_RECP_CTX_init(BN_RECP_CTX *recp) 64656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 65656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_init(&(recp->N)); 66656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_init(&(recp->Nr)); 67656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project recp->num_bits=0; 68656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project recp->flags=0; 69656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 70656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 71656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source ProjectBN_RECP_CTX *BN_RECP_CTX_new(void) 72656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 73656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_RECP_CTX *ret; 74656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 75656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if ((ret=(BN_RECP_CTX *)OPENSSL_malloc(sizeof(BN_RECP_CTX))) == NULL) 76656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(NULL); 77656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 78656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_RECP_CTX_init(ret); 79656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ret->flags=BN_FLG_MALLOCED; 80656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(ret); 81656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 82656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 83656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectvoid BN_RECP_CTX_free(BN_RECP_CTX *recp) 84656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 85656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if(recp == NULL) 86656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return; 87656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 88656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_free(&(recp->N)); 89656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_free(&(recp->Nr)); 90656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (recp->flags & BN_FLG_MALLOCED) 91656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project OPENSSL_free(recp); 92656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 93656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 94656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectint BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx) 95656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 96656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_copy(&(recp->N),d)) return 0; 97656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_zero(&(recp->Nr)); 98656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project recp->num_bits=BN_num_bits(d); 99656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project recp->shift=0; 100656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(1); 101656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 102656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 103656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectint BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y, 104656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_RECP_CTX *recp, BN_CTX *ctx) 105656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 106656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int ret=0; 107656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *a; 108656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project const BIGNUM *ca; 109656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 110656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_start(ctx); 111656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if ((a = BN_CTX_get(ctx)) == NULL) goto err; 112656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (y != NULL) 113656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 114656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (x == y) 115656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { if (!BN_sqr(a,x,ctx)) goto err; } 116656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 117656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { if (!BN_mul(a,x,y,ctx)) goto err; } 118656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ca = a; 119656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 120656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 121656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ca=x; /* Just do the mod */ 122656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 123656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ret = BN_div_recp(NULL,r,ca,recp,ctx); 124656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projecterr: 125656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_end(ctx); 126656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(r); 127656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(ret); 128656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 129656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 130656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectint BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, 131656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_RECP_CTX *recp, BN_CTX *ctx) 132656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 133656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int i,j,ret=0; 134656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *a,*b,*d,*r; 135656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 136656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_start(ctx); 137656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project a=BN_CTX_get(ctx); 138656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project b=BN_CTX_get(ctx); 139656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (dv != NULL) 140656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project d=dv; 141656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 142656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project d=BN_CTX_get(ctx); 143656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (rem != NULL) 144656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r=rem; 145656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 146656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r=BN_CTX_get(ctx); 147656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (a == NULL || b == NULL || d == NULL || r == NULL) goto err; 148656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 149656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (BN_ucmp(m,&(recp->N)) < 0) 150656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 151656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_zero(d); 152656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_copy(r,m)) return 0; 153656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_end(ctx); 154656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(1); 155656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 156656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 157656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* We want the remainder 158656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Given input of ABCDEF / ab 159656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * we need multiply ABCDEF by 3 digests of the reciprocal of ab 160656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 161656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 162656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 163656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */ 164656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project i=BN_num_bits(m); 165656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project j=recp->num_bits<<1; 166656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (j>i) i=j; 167656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 168656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Nr := round(2^i / N) */ 169656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (i != recp->shift) 170656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project recp->shift=BN_reciprocal(&(recp->Nr),&(recp->N), 171656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project i,ctx); /* BN_reciprocal returns i, or -1 for an error */ 172656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (recp->shift == -1) goto err; 173656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 174656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))| 175656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))| 176656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)| 177656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * = |m/N| 178656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 179656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift(a,m,recp->num_bits)) goto err; 180656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_mul(b,a,&(recp->Nr),ctx)) goto err; 181656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_rshift(d,b,i-recp->num_bits)) goto err; 182656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project d->neg=0; 183656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 184656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_mul(b,&(recp->N),d,ctx)) goto err; 185656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_usub(r,m,b)) goto err; 186656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r->neg=0; 187656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 188656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#if 1 189656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project j=0; 190656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project while (BN_ucmp(r,&(recp->N)) >= 0) 191656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 192656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (j++ > 2) 193656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 194656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BNerr(BN_F_BN_DIV_RECP,BN_R_BAD_RECIPROCAL); 195656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto err; 196656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 197656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_usub(r,r,&(recp->N))) goto err; 198656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_add_word(d,1)) goto err; 199656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 200656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 201656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 202656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r->neg=BN_is_zero(r)?0:m->neg; 203656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project d->neg=m->neg^recp->N.neg; 204656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ret=1; 205656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projecterr: 206656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_end(ctx); 207656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(dv); 208656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(rem); 209656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(ret); 210656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 211656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 212656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* len is the expected size of the result 213656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * We actually calculate with an extra word of precision, so 214656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * we can do faster division if the remainder is not required. 215656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 216656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* r := 2^len / m */ 217656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectint BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx) 218656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 219656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int ret= -1; 220656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *t; 221656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 222656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_start(ctx); 223656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if((t = BN_CTX_get(ctx)) == NULL) goto err; 224656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 225656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_set_bit(t,len)) goto err; 226656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 227656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!BN_div(r,NULL,t,m,ctx)) goto err; 228656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 229656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ret=len; 230656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projecterr: 231656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(r); 232656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_end(ctx); 233656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(ret); 234656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 235