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