bn_sqr.c revision 55714
1181876Sjhb/* crypto/bn/bn_sqr.c */ 2249344Sglebius/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3204494Srwatson * All rights reserved. 4204494Srwatson * 5204494Srwatson * This package is an SSL implementation written 6181876Sjhb * by Eric Young (eay@cryptsoft.com). 7181876Sjhb * The implementation was written so as to conform with Netscapes SSL. 8204494Srwatson * 9181876Sjhb * This library is free for commercial and non-commercial use as long as 10181876Sjhb * the following conditions are aheared to. The following conditions 11204494Srwatson * apply to all code found in this distribution, be it the RC4, RSA, 12204494Srwatson * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13204494Srwatson * included with this distribution is covered by the same copyright terms 14181876Sjhb * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15181876Sjhb * 16181876Sjhb * Copyright remains Eric Young's, and as such any Copyright notices in 17181876Sjhb * the code are not to be removed. 18181876Sjhb * If this package is used in a product, Eric Young should be given attribution 19181876Sjhb * as the author of the parts of the library used. 20181876Sjhb * This can be in the form of a textual message at program startup or 21181876Sjhb * in documentation (online or textual) provided with the package. 22181876Sjhb * 23181876Sjhb * Redistribution and use in source and binary forms, with or without 24181876Sjhb * modification, are permitted provided that the following conditions 25181876Sjhb * are met: 26181876Sjhb * 1. Redistributions of source code must retain the copyright 27181876Sjhb * notice, this list of conditions and the following disclaimer. 28181876Sjhb * 2. Redistributions in binary form must reproduce the above copyright 29181876Sjhb * notice, this list of conditions and the following disclaimer in the 30181876Sjhb * documentation and/or other materials provided with the distribution. 31181876Sjhb * 3. All advertising materials mentioning features or use of this software 32181876Sjhb * must display the following acknowledgement: 33181876Sjhb * "This product includes cryptographic software written by 34181876Sjhb * Eric Young (eay@cryptsoft.com)" 35181876Sjhb * The word 'cryptographic' can be left out if the rouines from the library 36181876Sjhb * being used are not cryptographic related :-). 37181876Sjhb * 4. If you include any Windows specific code (or a derivative thereof) from 38181876Sjhb * the apps directory (application code) you must include an acknowledgement: 39181876Sjhb * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40181876Sjhb * 41181876Sjhb * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42181876Sjhb * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43181876Sjhb * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44181876Sjhb * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45181876Sjhb * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46181876Sjhb * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47181876Sjhb * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48181876Sjhb * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49181876Sjhb * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50181876Sjhb * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51181876Sjhb * SUCH DAMAGE. 52217744Suqs * 53217744Suqs * The licence and distribution terms for any publically available version or 54249344Sglebius * derivative of this code cannot be changed. i.e. this code cannot simply be 55217744Suqs * copied and put under another distribution licence 56181876Sjhb * [including the GNU Public Licence.] 57249344Sglebius */ 58249344Sglebius 59249344Sglebius#include <stdio.h> 60181876Sjhb#include "cryptlib.h" 61181876Sjhb#include "bn_lcl.h" 62181876Sjhb 63181876Sjhb/* r must not be a */ 64204494Srwatson/* I've just gone over this and it is now %20 faster on x86 - eay - 27 Jun 96 */ 65204494Srwatsonint BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx) 66204494Srwatson { 67204494Srwatson int max,al; 68181876Sjhb BIGNUM *tmp,*rr; 69181876Sjhb 70181876Sjhb#ifdef BN_COUNT 71249344Sglebiusprintf("BN_sqr %d * %d\n",a->top,a->top); 72181876Sjhb#endif 73181876Sjhb bn_check_top(a); 74181876Sjhb tmp= &(ctx->bn[ctx->tos]); 75181876Sjhb rr=(a != r)?r: (&ctx->bn[ctx->tos+1]); 76181876Sjhb 77181876Sjhb al=a->top; 78181876Sjhb if (al <= 0) 79181876Sjhb { 80181876Sjhb r->top=0; 81181876Sjhb return(1); 82181876Sjhb } 83181876Sjhb 84181876Sjhb max=(al+al); 85181876Sjhb if (bn_wexpand(rr,max+1) == NULL) return(0); 86181876Sjhb 87181876Sjhb r->neg=0; 88181876Sjhb if (al == 4) 89181876Sjhb { 90181876Sjhb#ifndef BN_SQR_COMBA 91181876Sjhb BN_ULONG t[8]; 92181876Sjhb bn_sqr_normal(rr->d,a->d,4,t); 93181876Sjhb#else 94181876Sjhb bn_sqr_comba4(rr->d,a->d); 95249344Sglebius#endif 96249344Sglebius } 97249344Sglebius else if (al == 8) 98249344Sglebius { 99249344Sglebius#ifndef BN_SQR_COMBA 100249344Sglebius BN_ULONG t[16]; 101249344Sglebius bn_sqr_normal(rr->d,a->d,8,t); 102249344Sglebius#else 103249344Sglebius bn_sqr_comba8(rr->d,a->d); 104181876Sjhb#endif 105181876Sjhb } 106181876Sjhb else 107181876Sjhb { 108181876Sjhb#if defined(BN_RECURSION) 109181876Sjhb if (al < BN_SQR_RECURSIVE_SIZE_NORMAL) 110181876Sjhb { 111217744Suqs BN_ULONG t[BN_SQR_RECURSIVE_SIZE_NORMAL*2]; 112181876Sjhb bn_sqr_normal(rr->d,a->d,al,t); 113181876Sjhb } 114181876Sjhb else 115181876Sjhb { 116181876Sjhb int j,k; 117181876Sjhb 118181876Sjhb j=BN_num_bits_word((BN_ULONG)al); 119181876Sjhb j=1<<(j-1); 120181876Sjhb k=j+j; 121181876Sjhb if (al == j) 122181876Sjhb { 123181876Sjhb if (bn_wexpand(a,k*2) == NULL) return(0); 124181876Sjhb if (bn_wexpand(tmp,k*2) == NULL) return(0); 125181876Sjhb bn_sqr_recursive(rr->d,a->d,al,tmp->d); 126181876Sjhb } 127181876Sjhb else 128181876Sjhb { 129181876Sjhb if (bn_wexpand(tmp,max) == NULL) return(0); 130181876Sjhb bn_sqr_normal(rr->d,a->d,al,tmp->d); 131181876Sjhb } 132181876Sjhb } 133181876Sjhb#else 134181876Sjhb if (bn_wexpand(tmp,max) == NULL) return(0); 135181876Sjhb bn_sqr_normal(rr->d,a->d,al,tmp->d); 136181876Sjhb#endif 137181876Sjhb } 138181876Sjhb 139181876Sjhb rr->top=max; 140181876Sjhb if ((max > 0) && (rr->d[max-1] == 0)) rr->top--; 141181876Sjhb if (rr != r) BN_copy(r,rr); 142181876Sjhb return(1); 143181876Sjhb } 144181876Sjhb 145181876Sjhb/* tmp must have 2*n words */ 146181876Sjhbvoid bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp) 147181876Sjhb { 148181876Sjhb int i,j,max; 149181876Sjhb BN_ULONG *ap,*rp; 150181876Sjhb 151181876Sjhb max=n*2; 152223758Sattilio ap=a; 153223758Sattilio rp=r; 154181876Sjhb rp[0]=rp[max-1]=0; 155181876Sjhb rp++; 156181876Sjhb j=n; 157181876Sjhb 158181876Sjhb if (--j > 0) 159181876Sjhb { 160181876Sjhb ap++; 161181876Sjhb rp[j]=bn_mul_words(rp,ap,j,ap[-1]); 162181876Sjhb rp+=2; 163181876Sjhb } 164181876Sjhb 165181876Sjhb for (i=n-2; i>0; i--) 166181876Sjhb { 167181876Sjhb j--; 168181876Sjhb ap++; 169181876Sjhb rp[j]=bn_mul_add_words(rp,ap,j,ap[-1]); 170181876Sjhb rp+=2; 171181876Sjhb } 172181876Sjhb 173181876Sjhb bn_add_words(r,r,r,max); 174181876Sjhb 175204494Srwatson /* There will not be a carry */ 176262740Sglebius 177262740Sglebius bn_sqr_words(tmp,a,n); 178262740Sglebius 179262740Sglebius bn_add_words(r,r,tmp,max); 180262740Sglebius } 181262740Sglebius 182262740Sglebius#ifdef BN_RECURSION 183262740Sglebius/* r is 2*n words in size, 184262740Sglebius * a and b are both n words in size. 185262740Sglebius * n must be a power of 2. 186204494Srwatson * We multiply and return the result. 187204494Srwatson * t must be 2*n words in size 188204494Srwatson * We calulate 189204494Srwatson * a[0]*b[0] 190204494Srwatson * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) 191204494Srwatson * a[1]*b[1] 192204494Srwatson */ 193204494Srwatsonvoid bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *t) 194204494Srwatson { 195204494Srwatson int n=n2/2; 196204494Srwatson int zero,c1; 197204494Srwatson BN_ULONG ln,lo,*p; 198204494Srwatson 199204494Srwatson#ifdef BN_COUNT 200204494Srwatsonprintf(" bn_sqr_recursive %d * %d\n",n2,n2); 201204494Srwatson#endif 202204494Srwatson if (n2 == 4) 203204494Srwatson { 204204494Srwatson#ifndef BN_SQR_COMBA 205204494Srwatson bn_sqr_normal(r,a,4,t); 206204494Srwatson#else 207204494Srwatson bn_sqr_comba4(r,a); 208204494Srwatson#endif 209204494Srwatson return; 210204494Srwatson } 211204494Srwatson else if (n2 == 8) 212204494Srwatson { 213204494Srwatson#ifndef BN_SQR_COMBA 214204494Srwatson bn_sqr_normal(r,a,8,t); 215204494Srwatson#else 216204494Srwatson bn_sqr_comba8(r,a); 217204494Srwatson#endif 218204494Srwatson return; 219204494Srwatson } 220204494Srwatson if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL) 221217744Suqs { 222204494Srwatson bn_sqr_normal(r,a,n2,t); 223217744Suqs return; 224204494Srwatson } 225217744Suqs /* r=(a[0]-a[1])*(a[1]-a[0]) */ 226204494Srwatson c1=bn_cmp_words(a,&(a[n]),n); 227217744Suqs zero=0; 228217744Suqs if (c1 > 0) 229204494Srwatson bn_sub_words(t,a,&(a[n]),n); 230204494Srwatson else if (c1 < 0) 231204494Srwatson bn_sub_words(t,&(a[n]),a,n); 232204494Srwatson else 233204494Srwatson zero=1; 234204494Srwatson 235204494Srwatson /* The result will always be negative unless it is zero */ 236204494Srwatson p= &(t[n2*2]); 237204494Srwatson 238204494Srwatson if (!zero) 239204494Srwatson bn_sqr_recursive(&(t[n2]),t,n,p); 240204494Srwatson else 241204494Srwatson memset(&(t[n2]),0,n*sizeof(BN_ULONG)); 242204494Srwatson bn_sqr_recursive(r,a,n,p); 243204494Srwatson bn_sqr_recursive(&(r[n2]),&(a[n]),n,p); 244204494Srwatson 245204494Srwatson /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero 246204494Srwatson * r[10] holds (a[0]*b[0]) 247204494Srwatson * r[32] holds (b[1]*b[1]) 248204494Srwatson */ 249217744Suqs 250204494Srwatson c1=(int)(bn_add_words(t,r,&(r[n2]),n2)); 251204494Srwatson 252204494Srwatson /* t[32] is negative */ 253204494Srwatson c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2)); 254204494Srwatson 255204494Srwatson /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1]) 256204494Srwatson * r[10] holds (a[0]*a[0]) 257204494Srwatson * r[32] holds (a[1]*a[1]) 258204494Srwatson * c1 holds the carry bits 259204494Srwatson */ 260204494Srwatson c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2)); 261204494Srwatson if (c1) 262204494Srwatson { 263204494Srwatson p= &(r[n+n2]); 264204494Srwatson lo= *p; 265204494Srwatson ln=(lo+c1)&BN_MASK2; 266204494Srwatson *p=ln; 267204494Srwatson 268204494Srwatson /* The overflow will stop before we over write 269204494Srwatson * words we should not overwrite */ 270204494Srwatson if (ln < (BN_ULONG)c1) 271204494Srwatson { 272204494Srwatson do { 273204494Srwatson p++; 274204494Srwatson lo= *p; 275204494Srwatson ln=(lo+1)&BN_MASK2; 276204494Srwatson *p=ln; 277204494Srwatson } while (ln == 0); 278204494Srwatson } 279204494Srwatson } 280204494Srwatson } 281204494Srwatson#endif 282204494Srwatson