/src/libgcrypt/mpi/mpi-mul.c
Line | Count | Source (jump to first uncovered line) |
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, see <https://www.gnu.org/licenses/>. |
18 | | * SPDX-License-Identifier: LGPL-2.1-or-later |
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 | | |
33 | | void |
34 | | _gcry_mpi_mul_ui (gcry_mpi_t prod, gcry_mpi_t mult, unsigned long small_mult) |
35 | 4 | { |
36 | 4 | mpi_size_t size, prod_size; |
37 | 4 | mpi_ptr_t prod_ptr; |
38 | 4 | mpi_limb_t cy; |
39 | 4 | int sign; |
40 | | |
41 | 4 | size = mult->nlimbs; |
42 | 4 | sign = mult->sign; |
43 | | |
44 | 4 | if( !size || !small_mult ) { |
45 | 2 | prod->nlimbs = 0; |
46 | 2 | prod->sign = 0; |
47 | 2 | return; |
48 | 2 | } |
49 | | |
50 | 2 | prod_size = size + 1; |
51 | 2 | if( prod->alloced < prod_size ) |
52 | 1 | mpi_resize( prod, prod_size ); |
53 | 2 | prod_ptr = prod->d; |
54 | | |
55 | 2 | cy = _gcry_mpih_mul_1( prod_ptr, mult->d, size, (mpi_limb_t)small_mult ); |
56 | 2 | if( cy ) |
57 | 1 | prod_ptr[size++] = cy; |
58 | 2 | prod->nlimbs = size; |
59 | 2 | prod->sign = sign; |
60 | 2 | } |
61 | | |
62 | | |
63 | | void |
64 | | _gcry_mpi_mul_2exp (gcry_mpi_t w, gcry_mpi_t u, unsigned long cnt) |
65 | 3 | { |
66 | 3 | mpi_size_t usize, wsize, limb_cnt; |
67 | 3 | mpi_ptr_t wp; |
68 | 3 | mpi_limb_t wlimb; |
69 | 3 | int usign, wsign; |
70 | | |
71 | 3 | usize = u->nlimbs; |
72 | 3 | usign = u->sign; |
73 | | |
74 | 3 | if( !usize ) { |
75 | 0 | w->nlimbs = 0; |
76 | 0 | w->sign = 0; |
77 | 0 | return; |
78 | 0 | } |
79 | | |
80 | 3 | limb_cnt = cnt / BITS_PER_MPI_LIMB; |
81 | 3 | wsize = usize + limb_cnt + 1; |
82 | 3 | if( w->alloced < wsize ) |
83 | 3 | mpi_resize(w, wsize ); |
84 | 3 | wp = w->d; |
85 | 3 | wsize = usize + limb_cnt; |
86 | 3 | wsign = usign; |
87 | | |
88 | 3 | cnt %= BITS_PER_MPI_LIMB; |
89 | 3 | if( cnt ) { |
90 | 1 | wlimb = _gcry_mpih_lshift( wp + limb_cnt, u->d, usize, cnt ); |
91 | 1 | if( wlimb ) { |
92 | 0 | wp[wsize] = wlimb; |
93 | 0 | wsize++; |
94 | 0 | } |
95 | 1 | } |
96 | 2 | else { |
97 | 2 | MPN_COPY_DECR( wp + limb_cnt, u->d, usize ); |
98 | 2 | } |
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 | 3 | MPN_ZERO( wp, limb_cnt ); |
103 | | |
104 | 3 | w->nlimbs = wsize; |
105 | 3 | w->sign = wsign; |
106 | 3 | } |
107 | | |
108 | | |
109 | | void |
110 | | _gcry_mpi_mul (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v) |
111 | 18.3M | { |
112 | 18.3M | mpi_size_t usize, vsize, wsize; |
113 | 18.3M | mpi_ptr_t up, vp, wp; |
114 | 18.3M | mpi_limb_t cy; |
115 | 18.3M | int usign, vsign, usecure, vsecure, sign_product; |
116 | 18.3M | int assign_wp=0; |
117 | 18.3M | mpi_ptr_t tmp_limb=NULL; |
118 | 18.3M | unsigned int tmp_limb_nlimbs = 0; |
119 | | |
120 | 18.3M | if( u->nlimbs < v->nlimbs ) { /* Swap U and V. */ |
121 | 523k | usize = v->nlimbs; |
122 | 523k | usign = v->sign; |
123 | 523k | usecure = mpi_is_secure(v); |
124 | 523k | up = v->d; |
125 | 523k | vsize = u->nlimbs; |
126 | 523k | vsign = u->sign; |
127 | 523k | vsecure = mpi_is_secure(u); |
128 | 523k | vp = u->d; |
129 | 523k | } |
130 | 17.8M | else { |
131 | 17.8M | usize = u->nlimbs; |
132 | 17.8M | usign = u->sign; |
133 | 17.8M | usecure = mpi_is_secure(u); |
134 | 17.8M | up = u->d; |
135 | 17.8M | vsize = v->nlimbs; |
136 | 17.8M | vsign = v->sign; |
137 | 17.8M | vsecure = mpi_is_secure(v); |
138 | 17.8M | vp = v->d; |
139 | 17.8M | } |
140 | 18.3M | sign_product = usign ^ vsign; |
141 | 18.3M | wp = w->d; |
142 | | |
143 | | /* Ensure W has space enough to store the result. */ |
144 | 18.3M | wsize = usize + vsize; |
145 | 18.3M | 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 | 933 | wp = mpi_alloc_limb_space( wsize, 1 ); |
150 | 933 | assign_wp = 2; /* mark it as 2 so that we can later copy it back to |
151 | | * mormal memory */ |
152 | 933 | } |
153 | 18.3M | else if( w->alloced < wsize ) { |
154 | 35.0k | if( wp == up || wp == vp ) { |
155 | 7.90k | wp = mpi_alloc_limb_space( wsize, mpi_is_secure(w) ); |
156 | 7.90k | assign_wp = 1; |
157 | 7.90k | } |
158 | 27.1k | else { |
159 | 27.1k | mpi_resize(w, wsize ); |
160 | 27.1k | wp = w->d; |
161 | 27.1k | } |
162 | 35.0k | } |
163 | 18.3M | else { /* Make U and V not overlap with W. */ |
164 | 18.3M | if( wp == up ) { |
165 | | /* W and U are identical. Allocate temporary space for U. */ |
166 | 8.50M | tmp_limb_nlimbs = usize; |
167 | 8.50M | up = tmp_limb = mpi_alloc_limb_space( usize, usecure ); |
168 | | /* Is V identical too? Keep it identical with U. */ |
169 | 8.50M | if( wp == vp ) |
170 | 1.12M | vp = up; |
171 | | /* Copy to the temporary space. */ |
172 | 8.50M | MPN_COPY( up, wp, usize ); |
173 | 8.50M | } |
174 | 9.82M | else if( wp == vp ) { |
175 | | /* W and V are identical. Allocate temporary space for V. */ |
176 | 1.53M | tmp_limb_nlimbs = vsize; |
177 | 1.53M | vp = tmp_limb = mpi_alloc_limb_space( vsize, vsecure ); |
178 | | /* Copy to the temporary space. */ |
179 | 1.53M | MPN_COPY( vp, wp, vsize ); |
180 | 1.53M | } |
181 | 18.3M | } |
182 | | |
183 | 18.3M | if( !vsize ) |
184 | 232k | wsize = 0; |
185 | 18.1M | else { |
186 | 18.1M | cy = _gcry_mpih_mul( wp, up, usize, vp, vsize ); |
187 | 18.1M | wsize -= cy? 0:1; |
188 | 18.1M | } |
189 | | |
190 | 18.3M | if( assign_wp ) { |
191 | 8.83k | if (assign_wp == 2) { |
192 | | /* copy the temp wp from secure memory back to normal memory */ |
193 | 933 | mpi_ptr_t tmp_wp = mpi_alloc_limb_space (wsize, 0); |
194 | 933 | MPN_COPY (tmp_wp, wp, wsize); |
195 | 933 | _gcry_mpi_free_limb_space (wp, 0); |
196 | 933 | wp = tmp_wp; |
197 | 933 | } |
198 | 8.83k | _gcry_mpi_assign_limb_space( w, wp, wsize ); |
199 | 8.83k | } |
200 | 18.3M | w->nlimbs = wsize; |
201 | 18.3M | w->sign = sign_product; |
202 | 18.3M | if( tmp_limb ) |
203 | 10.0M | _gcry_mpi_free_limb_space (tmp_limb, tmp_limb_nlimbs); |
204 | 18.3M | } |
205 | | |
206 | | |
207 | | void |
208 | | _gcry_mpi_mulm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, gcry_mpi_t m) |
209 | 1.04M | { |
210 | 1.04M | gcry_mpi_t temp_m = NULL; |
211 | | |
212 | 1.04M | if (w == m) |
213 | 6 | { |
214 | 6 | temp_m = mpi_copy (m); |
215 | 6 | m = temp_m; |
216 | 6 | } |
217 | | |
218 | 1.04M | mpi_mul (w, u, v); |
219 | 1.04M | _gcry_mpi_tdiv_r (w, w, m); |
220 | | |
221 | 1.04M | if (temp_m) |
222 | 6 | mpi_free(temp_m); |
223 | 1.04M | } |