1 /*
2 * Copyright (c) 2003 Bob Deblier
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 *
18 */
19
20 /*!\file mpnumber.c
21 * \brief Multi-precision numbers.
22 * \author Bob Deblier <bob.deblier@telenet.be>
23 * \ingroup MP_m
24 */
25
26 #define BEECRYPT_DLL_EXPORT
27
28 #if HAVE_CONFIG_H
29 # include "config.h"
30 #endif
31
32 #include "beecrypt/mpnumber.h"
33
mpnzero(mpnumber * n)34 void mpnzero(mpnumber* n)
35 {
36 n->size = 0;
37 n->data = (mpw*) 0;
38 }
39
mpnsize(mpnumber * n,size_t size)40 void mpnsize(mpnumber* n, size_t size)
41 {
42 if (size)
43 {
44 if (n->data)
45 {
46 if (n->size != size)
47 {
48 if (size < n->size)
49 {
50 register size_t offset = n->size - size;
51
52 memmove(n->data, n->data + offset, offset * sizeof(mpw));
53 }
54 n->data = (mpw*) realloc(n->data, size * sizeof(mpw));
55 }
56 }
57 else
58 n->data = (mpw*) malloc(size * sizeof(mpw));
59
60 if (n->data == (mpw*) 0)
61 n->size = 0;
62 else
63 n->size = size;
64
65 }
66 else if (n->data)
67 {
68 free(n->data);
69 n->data = (mpw*) 0;
70 n->size = 0;
71 }
72 }
73
mpninit(mpnumber * n,size_t size,const mpw * data)74 void mpninit(mpnumber* n, size_t size, const mpw* data)
75 {
76 n->size = size;
77 n->data = (mpw*) malloc(size * sizeof(mpw));
78
79 if (n->data)
80 mpcopy(size, n->data, data);
81 }
82
mpnfree(mpnumber * n)83 void mpnfree(mpnumber* n)
84 {
85 if (n->data)
86 {
87 free(n->data);
88 n->data = (mpw*) 0;
89 }
90 n->size = 0;
91 }
92
mpncopy(mpnumber * n,const mpnumber * copy)93 void mpncopy(mpnumber* n, const mpnumber* copy)
94 {
95 mpnset(n, copy->size, copy->data);
96 }
97
mpnwipe(mpnumber * n)98 void mpnwipe(mpnumber* n)
99 {
100 if (n->data != (mpw*) 0)
101 mpzero(n->size, n->data);
102 }
103
mpnset(mpnumber * n,size_t size,const mpw * data)104 void mpnset(mpnumber* n, size_t size, const mpw* data)
105 {
106 if (size)
107 {
108 if (n->data)
109 {
110 if (n->size != size)
111 n->data = (mpw*) realloc(n->data, size * sizeof(mpw));
112 }
113 else
114 n->data = (mpw*) malloc(size * sizeof(mpw));
115
116 if (n->data)
117 mpcopy(n->size = size, n->data, data);
118 else
119 n->size = 0;
120 }
121 else if (n->data)
122 {
123 free(n->data);
124 n->data = (mpw*) 0;
125 n->size = 0;
126 }
127 }
128
mpnsetw(mpnumber * n,mpw val)129 void mpnsetw(mpnumber* n, mpw val)
130 {
131 if (n->data)
132 {
133 if (n->size != 1)
134 n->data = (mpw*) realloc(n->data, sizeof(mpw));
135 }
136 else
137 n->data = (mpw*) malloc(sizeof(mpw));
138
139 if (n->data)
140 {
141 n->size = 1;
142 n->data[0] = val;
143 }
144 else
145 n->size = 0;
146 }
147
mpnsetbin(mpnumber * n,const byte * osdata,size_t ossize)148 int mpnsetbin(mpnumber* n, const byte* osdata, size_t ossize)
149 {
150 int rc = -1;
151 size_t size;
152
153 /* skip zero bytes */
154 while ((*osdata == 0) && ossize)
155 {
156 osdata++;
157 ossize--;
158 }
159
160 size = MP_BYTES_TO_WORDS(ossize + MP_WBYTES - 1);
161
162 if (n->data)
163 {
164 if (n->size != size)
165 n->data = (mpw*) realloc(n->data, size * sizeof(mpw));
166 }
167 else
168 n->data = (mpw*) malloc(size * sizeof(mpw));
169
170 if (n->data)
171 {
172 n->size = size;
173
174 rc = os2ip(n->data, size, osdata, ossize);
175 }
176 else
177 n->size = 0;
178
179 return rc;
180 }
181
mpnsethex(mpnumber * n,const char * hex)182 int mpnsethex(mpnumber* n, const char* hex)
183 {
184 int rc = -1;
185 size_t len = strlen(hex);
186 size_t size = MP_NIBBLES_TO_WORDS(len + MP_WNIBBLES - 1);
187
188 if (n->data)
189 {
190 if (n->size != size)
191 n->data = (mpw*) realloc(n->data, size * sizeof(mpw));
192 }
193 else
194 n->data = (mpw*) malloc(size * sizeof(mpw));
195
196 if (n->data)
197 {
198 n->size = size;
199
200 rc = hs2ip(n->data, size, hex, len);
201 }
202 else
203 n->size = 0;
204
205 return rc;
206 }
207
mpninv(mpnumber * inv,const mpnumber * k,const mpnumber * mod)208 int mpninv(mpnumber* inv, const mpnumber* k, const mpnumber* mod)
209 {
210 int rc = 0;
211 size_t size = mod->size;
212 mpw* wksp = (mpw*) malloc((7*size+6) * sizeof(mpw));
213
214 if (wksp)
215 {
216 mpnsize(inv, size);
217 mpsetx(size, wksp, k->size, k->data);
218 rc = mpextgcd_w(size, mod->data, wksp, inv->data, wksp+size);
219 free(wksp);
220 }
221
222 return rc;
223 }
224
mpntrbits(mpnumber * n,size_t bits)225 size_t mpntrbits(mpnumber* n, size_t bits)
226 {
227 size_t sigbits = mpbits(n->size, n->data);
228 size_t offset = 0;
229
230 if (sigbits <= bits)
231 {
232 /* no need to truncate */
233 return sigbits;
234 }
235 else
236 {
237 size_t allbits = MP_WORDS_TO_BITS(n->size);
238
239 while ((allbits - bits) >= MP_WBITS)
240 {
241 /* zero a word */
242 n->data[offset++] = 0;
243 allbits -= MP_WBITS;
244 }
245
246 if ((allbits - bits))
247 {
248 /* mask the next word */
249 n->data[offset] &= (MP_ALLMASK >> (MP_WBITS - bits));
250 }
251 /* resize the number */
252 mpnsize(n, n->size - offset);
253
254 /* finally return the number of remaining bits */
255 return mpbits(n->size, n->data);
256 }
257 }
258
mpnbits(const mpnumber * n)259 size_t mpnbits(const mpnumber* n)
260 {
261 return mpbits(n->size, n->data);
262 }
263