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