src/libstrongswan/plugins/bliss/bliss_sampler.c

   1 /*
   2  * Copyright (C) 2014 Andreas Steffen
   3  * HSR Hochschule fuer Technik Rapperswil
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the
   7  * Free Software Foundation; either version 2 of the License, or (at your
   8  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  12  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * for more details.
  14  */
  15
  16 #include "bliss_sampler.h"
  17
  18 typedef struct private_bliss_sampler_t private_bliss_sampler_t;
  19
  20 #include <crypto/xofs/xof_bitspender.h>
  21
  22 /**
  23  * Private data of a bliss_sampler_t object.
  24  */
  25 struct private_bliss_sampler_t {
  26
  27         /**
  28          * Public interface.
  29          */
  30         bliss_sampler_t public;
  31
  32         /**
  33          * BLISS parameter the rejection sampling is to be based on
  34          */
  35         const bliss_param_set_t *set;
  36
  37         /**
  38          * Bitspender used for random rejection sampling
  39          */
  40         xof_bitspender_t *bitspender;
  41
  42 };
  43
  44 METHOD(bliss_sampler_t, bernoulli_exp, bool,
  45         private_bliss_sampler_t *this, uint32_t x, bool *accepted)
  46 {
  47         uint32_t x_mask;
  48         uint8_t u;
  49         const uint8_t *c;
  50         int i;
  51
  52         x_mask = 1 << (this->set->c_rows - 1);
  53         c = this->set->c;
  54         c += (this->set->c_rows - 1) * this->set->c_cols;
  55
  56         while (x_mask > 0)
  57         {
  58                 if (x & x_mask)
  59                 {
  60                         for (i = 0; i < this->set->c_cols; i++)
  61                         {
  62                                 if (!this->bitspender->get_byte(this->bitspender, &u))
  63                                 {
  64                                         return FALSE;
  65                                 }
  66                                 if (u < c[i])
  67                                 {
  68                                         break;
  69                                 }
  70                                 else if (u > c[i])
  71                                 {
  72                                         *accepted = FALSE;
  73                                         return TRUE;
  74                                 }
  75                         }
  76                 }
  77                 x_mask >>= 1;
  78                 c -= this->set->c_cols;
  79         }
  80
  81         *accepted = TRUE;
  82         return TRUE;
  83 }
  84
  85 METHOD(bliss_sampler_t, bernoulli_cosh, bool,
  86         private_bliss_sampler_t *this, int32_t x, bool *accepted)
  87 {
  88         uint32_t u;
  89
  90         x = 2 * (x < 0 ? -x : x);
  91
  92         while (TRUE)
  93         {
  94                 if (!bernoulli_exp(this, x, accepted))
  95                 {
  96                         return FALSE;
  97                 }
  98                 if (*accepted)
  99                 {
 100                         return TRUE;
 101                 }
 102                 if (!this->bitspender->get_bits(this->bitspender, 1, &u))
 103                 {
 104                         return FALSE;
 105                 }
 106                 if (u)
 107                 {
 108                         continue;
 109                 }
 110                 if (!bernoulli_exp(this, x, accepted))
 111                 {
 112                         return FALSE;
 113                 }
 114                 if (!(*accepted))
 115                 {
 116                         return TRUE;
 117                 }
 118         }
 119 }
 120
 121 #define MAX_SAMPLE_INDEX        16
 122
 123 METHOD(bliss_sampler_t, pos_binary, bool,
 124         private_bliss_sampler_t *this, uint32_t *x)
 125 {
 126         uint32_t u, i;
 127
 128         while (TRUE)
 129         {
 130                 for (i = 0; i <= MAX_SAMPLE_INDEX; i++)
 131                 {
 132                         if (!this->bitspender->get_bits(this->bitspender,
 133                                                                                         i ? (2*i - 1) : 1, &u))
 134                         {
 135                                 return FALSE;
 136                         }
 137                         if (u == 0)
 138                         {
 139                                 *x = i;
 140                                 return TRUE;
 141                         }
 142                         if ((u >> 1) != 0)
 143                         {
 144                                 break;
 145                         }
 146                 }
 147                 if (i > MAX_SAMPLE_INDEX)
 148                 {
 149                         return FALSE;
 150                 }
 151         }
 152 }
 153
 154 METHOD(bliss_sampler_t, gaussian, bool,
 155         private_bliss_sampler_t *this, int32_t *z)
 156 {
 157         uint32_t u, x, y, z_pos;
 158         bool accepted;
 159
 160         while (TRUE)
 161         {
 162                 if (!pos_binary(this, &x))
 163                 {
 164                         return FALSE;
 165                 }
 166
 167                 do
 168                 {
 169                         if (!this->bitspender->get_bits(this->bitspender,
 170                                                                                         this->set->k_sigma_bits, &y))
 171                         {
 172                                 return FALSE;
 173                         }
 174                 }
 175                 while (y >= this->set->k_sigma);
 176
 177                 if (!bernoulli_exp(this, y * (y + 2*this->set->k_sigma * x), &accepted))
 178                 {
 179                         return FALSE;
 180                 }
 181                 if (accepted)
 182                 {
 183                         if (!this->bitspender->get_bits(this->bitspender, 1, &u))
 184                         {
 185                                 return FALSE;
 186                         }
 187                         if (x || y || u)
 188                         {
 189                                 break;
 190                         }
 191                 }
 192         }
 193
 194         z_pos = this->set->k_sigma * x + y;
 195         *z = u ? z_pos : -z_pos;
 196
 197         return TRUE;
 198 }
 199
 200 METHOD(bliss_sampler_t, sign, bool,
 201         private_bliss_sampler_t *this, bool *positive)
 202 {
 203         uint32_t u;
 204
 205         if (!this->bitspender->get_bits(this->bitspender, 1, &u))
 206         {
 207                 return FALSE;
 208         }
 209         *positive = u;
 210
 211         return TRUE;
 212 }
 213
 214 METHOD(bliss_sampler_t, destroy, void,
 215         private_bliss_sampler_t *this)
 216 {
 217         this->bitspender->destroy(this->bitspender);
 218         free(this);
 219 }
 220
 221
 222 /**
 223  * See header.
 224  */
 225 bliss_sampler_t *bliss_sampler_create(ext_out_function_t alg, chunk_t seed,
 226                                                                           const bliss_param_set_t *set)
 227 {
 228         private_bliss_sampler_t *this;
 229         xof_bitspender_t *bitspender;
 230
 231         bitspender = xof_bitspender_create(alg, seed, FALSE);
 232         if (!bitspender)
 233         {
 234                 return NULL;
 235         }
 236
 237         INIT(this,
 238                 .public = {
 239                         .bernoulli_exp = _bernoulli_exp,
 240                         .bernoulli_cosh = _bernoulli_cosh,
 241                         .pos_binary = _pos_binary,
 242                         .gaussian = _gaussian,
 243                         .sign = _sign,
 244                         .destroy = _destroy,
 245                 },
 246                 .set = set,
 247                 .bitspender = bitspender,
 248         );
 249
 250         return &this->public;
 251 }