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 }