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 }