1/* mpi-mul.c - MPI functions 2 * Copyright (C) 1994, 1996, 1998, 2001, 2002, 2003 Free Software Foundation, Inc. 3 * 4 * This file is part of Libgcrypt. 5 * 6 * Libgcrypt is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU Lesser General Public License as 8 * published by the Free Software Foundation; either version 2.1 of 9 * the License, or (at your option) any later version. 10 * 11 * Libgcrypt is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU Lesser General Public License for more details. 15 * 16 * You should have received a copy of the GNU Lesser General Public 17 * License along with this program; if not, write to the Free Software 18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA 19 * 20 * Note: This code is heavily based on the GNU MP Library. 21 * Actually it's the same code with only minor changes in the 22 * way the data is stored; this is to support the abstraction 23 * of an optional secure memory allocation which may be used 24 * to avoid revealing of sensitive data due to paging etc. 25 */ 26 27#include <config.h> 28#include <stdio.h> 29#include <stdlib.h> 30#include "mpi-internal.h" 31 32 33void 34gcry_mpi_mul_ui( gcry_mpi_t prod, gcry_mpi_t mult, unsigned long small_mult ) 35{ 36 mpi_size_t size, prod_size; 37 mpi_ptr_t prod_ptr; 38 mpi_limb_t cy; 39 int sign; 40 41 size = mult->nlimbs; 42 sign = mult->sign; 43 44 if( !size || !small_mult ) { 45 prod->nlimbs = 0; 46 prod->sign = 0; 47 return; 48 } 49 50 prod_size = size + 1; 51 if( prod->alloced < prod_size ) 52 mpi_resize( prod, prod_size ); 53 prod_ptr = prod->d; 54 55 cy = _gcry_mpih_mul_1( prod_ptr, mult->d, size, (mpi_limb_t)small_mult ); 56 if( cy ) 57 prod_ptr[size++] = cy; 58 prod->nlimbs = size; 59 prod->sign = sign; 60} 61 62 63void 64gcry_mpi_mul_2exp( gcry_mpi_t w, gcry_mpi_t u, unsigned long cnt) 65{ 66 mpi_size_t usize, wsize, limb_cnt; 67 mpi_ptr_t wp; 68 mpi_limb_t wlimb; 69 int usign, wsign; 70 71 usize = u->nlimbs; 72 usign = u->sign; 73 74 if( !usize ) { 75 w->nlimbs = 0; 76 w->sign = 0; 77 return; 78 } 79 80 limb_cnt = cnt / BITS_PER_MPI_LIMB; 81 wsize = usize + limb_cnt + 1; 82 if( w->alloced < wsize ) 83 mpi_resize(w, wsize ); 84 wp = w->d; 85 wsize = usize + limb_cnt; 86 wsign = usign; 87 88 cnt %= BITS_PER_MPI_LIMB; 89 if( cnt ) { 90 wlimb = _gcry_mpih_lshift( wp + limb_cnt, u->d, usize, cnt ); 91 if( wlimb ) { 92 wp[wsize] = wlimb; 93 wsize++; 94 } 95 } 96 else { 97 MPN_COPY_DECR( wp + limb_cnt, u->d, usize ); 98 } 99 100 /* Zero all whole limbs at low end. Do it here and not before calling 101 * mpn_lshift, not to lose for U == W. */ 102 MPN_ZERO( wp, limb_cnt ); 103 104 w->nlimbs = wsize; 105 w->sign = wsign; 106} 107 108 109void 110gcry_mpi_mul( gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v) 111{ 112 mpi_size_t usize, vsize, wsize; 113 mpi_ptr_t up, vp, wp; 114 mpi_limb_t cy; 115 int usign, vsign, usecure, vsecure, sign_product; 116 int assign_wp=0; 117 mpi_ptr_t tmp_limb=NULL; 118 unsigned int tmp_limb_nlimbs = 0; 119 120 if( u->nlimbs < v->nlimbs ) { /* Swap U and V. */ 121 usize = v->nlimbs; 122 usign = v->sign; 123 usecure = mpi_is_secure(v); 124 up = v->d; 125 vsize = u->nlimbs; 126 vsign = u->sign; 127 vsecure = mpi_is_secure(u); 128 vp = u->d; 129 } 130 else { 131 usize = u->nlimbs; 132 usign = u->sign; 133 usecure = mpi_is_secure(u); 134 up = u->d; 135 vsize = v->nlimbs; 136 vsign = v->sign; 137 vsecure = mpi_is_secure(v); 138 vp = v->d; 139 } 140 sign_product = usign ^ vsign; 141 wp = w->d; 142 143 /* Ensure W has space enough to store the result. */ 144 wsize = usize + vsize; 145 if ( !mpi_is_secure (w) && (mpi_is_secure (u) || mpi_is_secure (v)) ) { 146 /* w is not allocated in secure space but u or v is. To make sure 147 * that no temporray results are stored in w, we temporary use 148 * a newly allocated limb space for w */ 149 wp = mpi_alloc_limb_space( wsize, 1 ); 150 assign_wp = 2; /* mark it as 2 so that we can later copy it back to 151 * mormal memory */ 152 } 153 else if( w->alloced < wsize ) { 154 if( wp == up || wp == vp ) { 155 wp = mpi_alloc_limb_space( wsize, mpi_is_secure(w) ); 156 assign_wp = 1; 157 } 158 else { 159 mpi_resize(w, wsize ); 160 wp = w->d; 161 } 162 } 163 else { /* Make U and V not overlap with W. */ 164 if( wp == up ) { 165 /* W and U are identical. Allocate temporary space for U. */ 166 tmp_limb_nlimbs = usize; 167 up = tmp_limb = mpi_alloc_limb_space( usize, usecure ); 168 /* Is V identical too? Keep it identical with U. */ 169 if( wp == vp ) 170 vp = up; 171 /* Copy to the temporary space. */ 172 MPN_COPY( up, wp, usize ); 173 } 174 else if( wp == vp ) { 175 /* W and V are identical. Allocate temporary space for V. */ 176 tmp_limb_nlimbs = vsize; 177 vp = tmp_limb = mpi_alloc_limb_space( vsize, vsecure ); 178 /* Copy to the temporary space. */ 179 MPN_COPY( vp, wp, vsize ); 180 } 181 } 182 183 if( !vsize ) 184 wsize = 0; 185 else { 186 cy = _gcry_mpih_mul( wp, up, usize, vp, vsize ); 187 wsize -= cy? 0:1; 188 } 189 190 if( assign_wp ) { 191 if (assign_wp == 2) { 192 /* copy the temp wp from secure memory back to normal memory */ 193 mpi_ptr_t tmp_wp = mpi_alloc_limb_space (wsize, 0); 194 MPN_COPY (tmp_wp, wp, wsize); 195 _gcry_mpi_free_limb_space (wp, 0); 196 wp = tmp_wp; 197 } 198 _gcry_mpi_assign_limb_space( w, wp, wsize ); 199 } 200 w->nlimbs = wsize; 201 w->sign = sign_product; 202 if( tmp_limb ) 203 _gcry_mpi_free_limb_space (tmp_limb, tmp_limb_nlimbs); 204} 205 206 207void 208gcry_mpi_mulm( gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, gcry_mpi_t m) 209{ 210 gcry_mpi_mul(w, u, v); 211 _gcry_mpi_fdiv_r( w, w, m ); 212} 213