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