- chunk is freed differently
[strongswan.git] / Source / charon / utils / gmp_helper.c
1 /**
2 * @file gmp_helper.c
3 *
4 * @brief Class with helper functions for gmp operations
5 *
6 */
7
8 /*
9 * Copyright (C) 1999, 2000, 2001 Henry Spencer.
10 * Copyright (C) 2005 Jan Hutter, Martin Willi
11 * Hochschule fuer Technik Rapperswil
12 *
13 * This program is free software; you can redistribute it and/or modify it
14 * under the terms of the GNU General Public License as published by the
15 * Free Software Foundation; either version 2 of the License, or (at your
16 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
17 *
18 * This program is distributed in the hope that it will be useful, but
19 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
20 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 * for more details.
22 */
23
24 #include <stdio.h>
25
26 #include "gmp_helper.h"
27
28 #include <utils/allocator.h>
29 #include <utils/randomizer.h>
30
31 /**
32 * Number of times the probabilistic primality test is applied
33 */
34 #define PRIMECHECK_ROUNDS 30
35
36 typedef struct private_gmp_helper_t private_gmp_helper_t;
37
38 /**
39 * Private data of an gmp_helper_t object.
40 */
41 struct private_gmp_helper_t {
42 /**
43 * public gmp_helper_t interface
44 */
45 gmp_helper_t public;
46
47 };
48
49
50 /**
51 * Implements private_gmp_helper_t's chunk_to_mpz function.
52 * See #private_gmp_helper_t.chunk_to_mpz for description.
53 */
54 static void chunk_to_mpz(private_gmp_helper_t *this, mpz_t *mpz_value, chunk_t data)
55 {
56 size_t i;
57
58 mpz_init_set_ui(*(mpz_value), 0);
59
60 for (i = 0; i < data.len; i++)
61 {
62 mpz_mul_ui(*(mpz_value),*(mpz_value), 1 << 8);
63 mpz_add_ui(*(mpz_value),*(mpz_value), data.ptr[i]);
64 }
65 }
66
67 /**
68 * Implements private_gmp_helper_t's mpz_to_chunk function.
69 * See #private_gmp_helper_t.mpz_to_chunk for description.
70 */
71 static status_t mpz_to_chunk (private_gmp_helper_t *this,mpz_t *mpz_value, chunk_t *data,size_t bytes)
72 {
73 mpz_t temp1, temp2;
74 status_t status = SUCCESS;
75 int i;
76 chunk_t tmp_chunk;
77
78 tmp_chunk.len = bytes;
79 tmp_chunk.ptr = allocator_alloc(tmp_chunk.len);
80
81 if (tmp_chunk.ptr == NULL)
82 {
83 allocator_free_chunk(&tmp_chunk);
84 return OUT_OF_RES;
85 }
86
87 /* free memory */
88 memset(tmp_chunk.ptr,0,tmp_chunk.len);
89
90 mpz_init(temp1);
91 mpz_init(temp2);
92
93 mpz_set(temp1, *mpz_value);
94
95 for (i = tmp_chunk.len-1; i >= 0; i--)
96 {
97 tmp_chunk.ptr[i] = mpz_mdivmod_ui(temp2, NULL, temp1, 1 << 8);
98 mpz_set(temp1, temp2);
99
100 }
101
102 if (mpz_sgn(temp1) != 0)
103 {
104 fprintf (stderr,"value %d\n",mpz_sgn(temp1));
105 status = FAILED;
106 }
107 mpz_clear(temp1);
108 mpz_clear(temp2);
109 *data = tmp_chunk;
110 if (status != SUCCESS)
111 {
112 allocator_free_chunk(&tmp_chunk);
113 }
114 return status;
115 }
116
117 /**
118 * Implements gmp_helper_t's init_prime function.
119 * See #gmp_helper_t.init_prime for description.
120 */
121 static status_t init_prime (private_gmp_helper_t *this, mpz_t *prime, int bytes)
122 {
123 randomizer_t *randomizer;
124 chunk_t random_bytes;
125 status_t status;
126 randomizer = randomizer_create();
127
128 if (randomizer == NULL)
129 {
130 return OUT_OF_RES;
131 }
132
133 /* TODO change to true random device ? */
134 // status = randomizer->allocate_random_bytes(randomizer,bytes, &random_bytes);
135 status = randomizer->allocate_pseudo_random_bytes(randomizer,bytes, &random_bytes);
136
137 /* make sure most significant bit is set */
138 random_bytes.ptr[0] = random_bytes.ptr[0] | 0x80;
139
140
141 /* not needed anymore */
142 randomizer->destroy(randomizer);
143 if (status != SUCCESS)
144 {
145 return status;
146 }
147
148 /* convert chunk to mpz value */
149 this->public.chunk_to_mpz(&(this->public),prime, random_bytes);
150
151 /* chunk is not used anymore */
152 allocator_free(random_bytes.ptr);
153 random_bytes.ptr = NULL;
154
155 /* composites are possible but should never occur */
156 mpz_nextprime (*(prime),*(prime));
157
158 return SUCCESS;
159 }
160
161
162 static status_t init_prime_fast (private_gmp_helper_t *this, mpz_t *prime, int bytes){
163 randomizer_t *randomizer;
164 chunk_t random_bytes;
165 status_t status;
166 unsigned long tries;
167 size_t length;
168
169
170 randomizer = randomizer_create();
171
172 if (randomizer == NULL)
173 {
174 return OUT_OF_RES;
175 }
176
177 /* TODO change to true random device ? */
178 // status = randomizer->allocate_random_bytes(randomizer,bytes, &random_bytes);
179 status = randomizer->allocate_pseudo_random_bytes(randomizer,bytes, &random_bytes);
180
181 /* make sure most significant bit is set */
182 random_bytes.ptr[0] = random_bytes.ptr[0] | 0x80;
183 /* not needed anymore */
184 randomizer->destroy(randomizer);
185 if (status != SUCCESS)
186 {
187 return status;
188 }
189
190 /* convert chunk to mpz value */
191 this->public.chunk_to_mpz(&(this->public),prime, random_bytes);
192
193 /* chunk is not used anymore */
194 allocator_free(random_bytes.ptr);
195 random_bytes.ptr = NULL;
196
197 /* make value odd */
198 if (mpz_fdiv_ui(*prime, 2) != 1)
199 {
200 /* make value odd */
201 mpz_add_ui(*prime,*prime,1);
202 }
203
204 tries = 1;
205
206 /* starting find a prime */
207 while (!mpz_probab_prime_p(*prime, PRIMECHECK_ROUNDS))
208 {
209 /* not a prime, increase by 2 */
210 mpz_add_ui(*prime, *prime, 2);
211 tries++;
212 }
213
214 length = mpz_sizeinbase(*prime, 2);
215
216
217 /* check bit length of primee */
218 if ((length < (bytes * 8)) || (length > ((bytes * 8) + 1)))
219 {
220 return FAILED;
221 }
222
223
224 if (length == ((bytes * 8) + 1))
225 {
226 /* carry out occured! retry */
227 mpz_clear(*prime);
228
229 /* recursive call */
230 return this->public.init_prime_fast(&(this->public),prime, bytes);
231 }
232
233 return SUCCESS;
234 }
235
236
237 /**
238 * Implements gmp_helper_t's destroy function.
239 * See #gmp_helper_t.destroy for description.
240 */
241 static status_t destroy(private_gmp_helper_t *this)
242 {
243 allocator_free(this);
244 return SUCCESS;
245 }
246
247 /*
248 * Described in header
249 */
250 gmp_helper_t *gmp_helper_create()
251 {
252 private_gmp_helper_t *this = allocator_alloc_thing(private_gmp_helper_t);
253 if ((this == NULL))
254 {
255 return NULL;
256 }
257
258 /* public functions */
259 this->public.destroy = (status_t (*)(gmp_helper_t *)) destroy;
260 this->public.init_prime = (status_t (*) (gmp_helper_t *, mpz_t *, int)) init_prime;
261 this->public.init_prime_fast = (status_t (*) (gmp_helper_t *, mpz_t *, int)) init_prime_fast;
262
263 /* private functions */
264 this->public.chunk_to_mpz = (void (*) (gmp_helper_t *,mpz_t *, chunk_t )) chunk_to_mpz;
265 this->public.mpz_to_chunk = (status_t (*) (gmp_helper_t *,mpz_t *, chunk_t *,size_t )) mpz_to_chunk;
266
267 return &(this->public);
268 }