c9417dae024230e43fea90bcbc5df2dc003abf59
[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 "allocator.h"
29 #include "randomizer.h"
30
31 /**
32 * Number of times the probabilistic primality test is applied
33 */
34 #define PRIMECHECK_ROUNDS 30
35
36 /**
37 * Private data of an gmp_helper_t object.
38 *
39 */
40 typedef struct private_gmp_helper_s private_gmp_helper_t;
41
42 struct private_gmp_helper_s {
43 /**
44 * public gmp_helper_t interface
45 */
46 gmp_helper_t public;
47
48 };
49
50
51 /**
52 * Implements private_gmp_helper_t's chunk_to_mpz function.
53 * See #private_gmp_helper_t.chunk_to_mpz for description.
54 */
55 static void chunk_to_mpz(private_gmp_helper_t *this, mpz_t *mpz_value, chunk_t data)
56 {
57 size_t i;
58
59 mpz_init_set_ui(*(mpz_value), 0);
60
61 for (i = 0; i < data.len; i++)
62 {
63 mpz_mul_ui(*(mpz_value),*(mpz_value), 1 << 8);
64 mpz_add_ui(*(mpz_value),*(mpz_value), data.ptr[i]);
65 }
66 }
67
68 /**
69 * Implements private_gmp_helper_t's mpz_to_chunk function.
70 * See #private_gmp_helper_t.mpz_to_chunk for description.
71 */
72 static status_t mpz_to_chunk (private_gmp_helper_t *this,mpz_t *mpz_value, chunk_t *data,size_t bytes)
73 {
74 mpz_t temp1, temp2;
75 status_t status = SUCCESS;
76 int i;
77 chunk_t tmp_chunk;
78
79 tmp_chunk.len = bytes;
80 tmp_chunk.ptr = allocator_alloc(tmp_chunk.len);
81
82 if (tmp_chunk.ptr == NULL)
83 {
84 allocator_free_chunk(tmp_chunk);
85 return OUT_OF_RES;
86 }
87
88 /* free memory */
89 memset(tmp_chunk.ptr,0,tmp_chunk.len);
90
91 mpz_init(temp1);
92 mpz_init(temp2);
93
94 mpz_set(temp1, *mpz_value);
95
96 for (i = tmp_chunk.len-1; i >= 0; i--)
97 {
98 tmp_chunk.ptr[i] = mpz_mdivmod_ui(temp2, NULL, temp1, 1 << 8);
99 mpz_set(temp1, temp2);
100
101 }
102
103 if (mpz_sgn(temp1) != 0)
104 {
105 fprintf (stderr,"value %d\n",mpz_sgn(temp1));
106 status = FAILED;
107 }
108 mpz_clear(temp1);
109 mpz_clear(temp2);
110 *data = tmp_chunk;
111 if (status != SUCCESS)
112 {
113 allocator_free_chunk(tmp_chunk);
114 }
115 return status;
116 }
117
118 /**
119 * Implements gmp_helper_t's init_prime function.
120 * See #gmp_helper_t.init_prime for description.
121 */
122 static status_t init_prime (private_gmp_helper_t *this, mpz_t *prime, int bytes)
123 {
124 randomizer_t *randomizer;
125 chunk_t random_bytes;
126 status_t status;
127 randomizer = randomizer_create();
128
129 if (randomizer == NULL)
130 {
131 return OUT_OF_RES;
132 }
133
134 /* TODO change to true random device ? */
135 // status = randomizer->allocate_random_bytes(randomizer,bytes, &random_bytes);
136 status = randomizer->allocate_pseudo_random_bytes(randomizer,bytes, &random_bytes);
137
138 /* make sure most significant bit is set */
139 random_bytes.ptr[0] = random_bytes.ptr[0] | 0x80;
140
141
142 /* not needed anymore */
143 randomizer->destroy(randomizer);
144 if (status != SUCCESS)
145 {
146 return status;
147 }
148
149 /* convert chunk to mpz value */
150 this->public.chunk_to_mpz(&(this->public),prime, random_bytes);
151
152 /* chunk is not used anymore */
153 allocator_free(random_bytes.ptr);
154 random_bytes.ptr = NULL;
155
156 /* composites are possible but should never occur */
157 mpz_nextprime (*(prime),*(prime));
158
159 return SUCCESS;
160 }
161
162
163 static status_t init_prime_fast (private_gmp_helper_t *this, mpz_t *prime, int bytes){
164 randomizer_t *randomizer;
165 chunk_t random_bytes;
166 status_t status;
167 unsigned long tries;
168 size_t length;
169
170
171 randomizer = randomizer_create();
172
173 if (randomizer == NULL)
174 {
175 return OUT_OF_RES;
176 }
177
178 /* TODO change to true random device ? */
179 // status = randomizer->allocate_random_bytes(randomizer,bytes, &random_bytes);
180 status = randomizer->allocate_pseudo_random_bytes(randomizer,bytes, &random_bytes);
181
182 /* make sure most significant bit is set */
183 random_bytes.ptr[0] = random_bytes.ptr[0] | 0x80;
184 /* not needed anymore */
185 randomizer->destroy(randomizer);
186 if (status != SUCCESS)
187 {
188 return status;
189 }
190
191 /* convert chunk to mpz value */
192 this->public.chunk_to_mpz(&(this->public),prime, random_bytes);
193
194 /* chunk is not used anymore */
195 allocator_free(random_bytes.ptr);
196 random_bytes.ptr = NULL;
197
198 /* make value odd */
199 if (mpz_fdiv_ui(*prime, 2) != 1)
200 {
201 /* make value odd */
202 mpz_add_ui(*prime,*prime,1);
203 }
204
205 tries = 1;
206
207 /* starting find a prime */
208 while (!mpz_probab_prime_p(*prime, PRIMECHECK_ROUNDS))
209 {
210 /* not a prime, increase by 2 */
211 mpz_add_ui(*prime, *prime, 2);
212 tries++;
213 }
214
215 length = mpz_sizeinbase(*prime, 2);
216
217
218 /* check bit length of primee */
219 if ((length < (bytes * 8)) || (length > ((bytes * 8) + 1)))
220 {
221 return FAILED;
222 }
223
224
225 if (length == ((bytes * 8) + 1))
226 {
227 /* carry out occured! retry */
228 mpz_clear(*prime);
229
230 /* recursive call */
231 return this->public.init_prime_fast(&(this->public),prime, bytes);
232 }
233
234 return SUCCESS;
235 }
236
237
238 /**
239 * Implements gmp_helper_t's destroy function.
240 * See #gmp_helper_t.destroy for description.
241 */
242 static status_t destroy(private_gmp_helper_t *this)
243 {
244 allocator_free(this);
245 return SUCCESS;
246 }
247
248 /*
249 * Described in header
250 */
251 gmp_helper_t *gmp_helper_create()
252 {
253 private_gmp_helper_t *this = allocator_alloc_thing(private_gmp_helper_t);
254 if ((this == NULL))
255 {
256 return NULL;
257 }
258
259 /* public functions */
260 this->public.destroy = (status_t (*)(gmp_helper_t *)) destroy;
261 this->public.init_prime = (status_t (*) (gmp_helper_t *, mpz_t *, int)) init_prime;
262 this->public.init_prime_fast = (status_t (*) (gmp_helper_t *, mpz_t *, int)) init_prime_fast;
263
264 /* private functions */
265 this->public.chunk_to_mpz = (void (*) (gmp_helper_t *,mpz_t *, chunk_t )) chunk_to_mpz;
266 this->public.mpz_to_chunk = (status_t (*) (gmp_helper_t *,mpz_t *, chunk_t *,size_t )) mpz_to_chunk;
267
268 return &(this->public);
269 }