Use Huffman code in BLISS signature
authorAndreas Steffen <andreas.steffen@strongswan.org>
Thu, 11 Dec 2014 16:11:17 +0000 (17:11 +0100)
committerAndreas Steffen <andreas.steffen@strongswan.org>
Fri, 12 Dec 2014 11:00:20 +0000 (12:00 +0100)
src/libstrongswan/plugins/bliss/Makefile.am
src/libstrongswan/plugins/bliss/bliss_huffman.c
src/libstrongswan/plugins/bliss/bliss_huffman_code.h
src/libstrongswan/plugins/bliss/bliss_huffman_coder.c [new file with mode: 0644]
src/libstrongswan/plugins/bliss/bliss_huffman_coder.h [new file with mode: 0644]
src/libstrongswan/plugins/bliss/bliss_private_key.c
src/libstrongswan/plugins/bliss/bliss_signature.c

index 27d179b..75dc92e 100644 (file)
@@ -23,6 +23,7 @@ libbliss_la_SOURCES = \
        bliss_fft.h bliss_fft.c \
        bliss_huffman_code.h bliss_huffman_code.c \
        bliss_huffman_code_1.c bliss_huffman_code_3.c bliss_huffman_code_4.c \
+       bliss_huffman_coder.h bliss_huffman_coder.c \
        bliss_sampler.h bliss_sampler.c
 libbliss_la_LIBADD = libbliss-params.la
 
index 5b66601..a26c894 100644 (file)
@@ -81,16 +81,14 @@ static double code_node(node_t *node, int *index, uint8_t bits, uint32_t code)
 
 }
 
-#define NO_NODE                -1
-#define NO_TUPLE       -1
-
 static void write_node(node_t *node)
 {
        int16_t node_0, node_1, tuple;
 
-       node_0 = node->l ? node->l->index : NO_NODE;
-       node_1 = node->r ? node->r->index : NO_NODE;
-       tuple = node->tuple ? node->tuple->index : NO_TUPLE;
+       node_0 = node->l ? node->l->index : BLISS_HUFFMAN_CODE_NO_NODE;
+       node_1 = node->r ? node->r->index : BLISS_HUFFMAN_CODE_NO_NODE;
+       tuple = node->tuple ? node->tuple->index : BLISS_HUFFMAN_CODE_NO_TUPLE;
+
        printf("\t{ %3d, %3d, %3d },  /* %3d: ", node_0, node_1, tuple, node->index);
 
        if (node->tuple)
index ede769e..df8511b 100644 (file)
@@ -34,6 +34,9 @@ struct bliss_huffman_code_tuple_t {
        uint16_t bits;
 };
 
+#define BLISS_HUFFMAN_CODE_NO_TUPLE            -1
+#define BLISS_HUFFMAN_CODE_NO_NODE             -1
+
 struct bliss_huffman_code_node_t {
        int16_t node_0;
        int16_t node_1;
diff --git a/src/libstrongswan/plugins/bliss/bliss_huffman_coder.c b/src/libstrongswan/plugins/bliss/bliss_huffman_coder.c
new file mode 100644 (file)
index 0000000..018ae0e
--- /dev/null
@@ -0,0 +1,138 @@
+/*
+ * Copyright (C) 2014 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY;https://www.hsr.ch/HSR-intern-Anmeldung.4409.0.html?&no_cache=1 without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * for more details.
+ */
+
+#include "bliss_huffman_coder.h"
+
+typedef struct private_bliss_huffman_coder_t private_bliss_huffman_coder_t;
+
+/**
+ * Private data structure for bliss_huffman_coder_t object
+ */
+struct private_bliss_huffman_coder_t {
+       /**
+        * Public interface.
+        */
+       bliss_huffman_coder_t public;
+
+       /**
+        * Bitpacker to write to or read from
+        */
+       bliss_bitpacker_t *packer;
+
+       /**
+        * Huffman code table to be used
+        */
+       bliss_huffman_code_t *code;
+
+       /**
+     * Maximum index into tuples table
+        */
+       int index_max;
+
+       /**
+     * Number of encoded or decoded bits
+        */
+       size_t bits;
+
+};
+
+METHOD(bliss_huffman_coder_t, get_bits, size_t,
+       private_bliss_huffman_coder_t *this)
+{
+       return this->bits;
+}
+
+METHOD(bliss_huffman_coder_t, encode, bool,
+       private_bliss_huffman_coder_t *this, int32_t z1, int16_t z2)
+{
+       uint32_t code;
+       uint16_t bits;
+       int index;
+
+       index = z1 * (2*this->code->n_z2 - 1) + z2 + this->code->n_z2 - 1;
+       if (index >= this->index_max)
+       {
+               DBG1(DBG_LIB, "index exceeded in Huffman encoding table");
+               return FALSE;
+       }
+       code = this->code->tuples[index].code;
+       bits = this->code->tuples[index].bits;
+       if (!this->packer->write_bits(this->packer, code, bits))
+       {
+               DBG1(DBG_LIB, "bitpacker exceeded its buffer");
+               return FALSE;
+       }
+       this->bits += bits;
+
+       return TRUE;
+}
+
+METHOD(bliss_huffman_coder_t, decode, bool,
+       private_bliss_huffman_coder_t *this, int32_t *z1, int16_t *z2)
+{
+       bliss_huffman_code_node_t *node;
+       uint32_t bit;
+
+       node = this->code->nodes;
+       while (node->tuple == BLISS_HUFFMAN_CODE_NO_TUPLE)
+       {
+               if (node->node_0 == BLISS_HUFFMAN_CODE_NO_NODE ||
+                       node->node_1 == BLISS_HUFFMAN_CODE_NO_NODE)
+               {
+                       DBG1(DBG_LIB, "error in Huffman decoding table");
+                       return FALSE;
+               }
+               if (!this->packer->read_bits(this->packer, &bit, 1))
+               {
+                       DBG1(DBG_LIB, "bitpacker depleted its buffer");
+                       return FALSE;
+               }
+               node = &this->code->nodes[bit ? node->node_1 : node->node_0];
+               this->bits++;
+       }
+       *z1 = node->tuple / (2*this->code->n_z2 - 1);
+       *z2 = node->tuple - (2*this->code->n_z2 - 1) * (*z1) - this->code->n_z2 + 1;
+
+       return TRUE;
+}
+
+METHOD(bliss_huffman_coder_t, destroy, void,
+       private_bliss_huffman_coder_t *this)
+{
+       free(this);
+}
+
+/**
+ * See header.
+ */
+bliss_huffman_coder_t *bliss_huffman_coder_create(bliss_huffman_code_t *code,
+                                                                                                 bliss_bitpacker_t *packer)
+{
+       private_bliss_huffman_coder_t *this;
+
+       INIT(this,
+               .public = {
+                       .get_bits = _get_bits,
+                       .encode = _encode,
+                       .decode = _decode,
+                       .destroy = _destroy,
+               },
+               .packer = packer,
+               .code = code,
+               .index_max = (2*code->n_z2 - 1) * code->n_z1,           
+       );
+
+       return &this->public;
+}
diff --git a/src/libstrongswan/plugins/bliss/bliss_huffman_coder.h b/src/libstrongswan/plugins/bliss/bliss_huffman_coder.h
new file mode 100644 (file)
index 0000000..59abc49
--- /dev/null
@@ -0,0 +1,77 @@
+/*
+ * Copyright (C) 2014 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * for more details.
+ */
+
+/**
+ * @defgroup bliss_huffman_coder bliss_huffman_coder
+ * @{ @ingroup bliss_p
+ */
+
+#ifndef BLISS_HUFFMAN_CODER_H_
+#define BLISS_HUFFMAN_CODER_H_
+
+#include "bliss_huffman_code.h"
+#include "bliss_bitpacker.h"
+
+#include <library.h>
+
+typedef struct bliss_huffman_coder_t bliss_huffman_coder_t;
+
+/**
+ * Encodes and decodes binary Huffman codes
+ */
+struct bliss_huffman_coder_t {
+
+       /**
+        * Get number of encoded or decoded bits
+        *
+        * @result                      Number of bits
+        */
+       size_t (*get_bits)(bliss_huffman_coder_t *this);
+
+       /**
+        * Encode a (z1, z2) tuple using a Huffman code
+        *
+        * @param z1            z1 value to be encoded
+        * @param z2            z2 value to be encoded
+        * @result                      TRUE if value could be encoded
+        */
+       bool (*encode)(bliss_huffman_coder_t *this, int32_t z1, int16_t z2);
+
+
+       /**
+        * Decode a (z1, z2) tuple using a Huffman code
+        *
+        * @param z1            Decoded z1 value returned
+        * @param z2            Decoded z2 value returned
+        * @result                      TRUE if value could be decoded from bitpacker
+        */
+       bool (*decode)(bliss_huffman_coder_t *this, int32_t *z1, int16_t *z2);
+
+       /**
+        * Destroy bliss_huffman_coder_t object
+        */
+       void (*destroy)(bliss_huffman_coder_t *this);
+};
+
+/**
+ * Create a bliss_huffman_coder_t object
+ *
+ * @param code                 Huffman code table
+ * @param packer               Bitpacker to write to or read from
+ */
+bliss_huffman_coder_t* bliss_huffman_coder_create(bliss_huffman_code_t *code,
+                                                                                                 bliss_bitpacker_t *packer);
+
+#endif /** BLISS_HUFFMAN_CODER_H_ @}*/
index f75ae8e..5582223 100644 (file)
@@ -369,14 +369,19 @@ static bool sign_bliss_with_sha512(private_bliss_private_key_t *this,
                {
                        continue;
                }
+
+               *signature = sig->get_encoding(sig);
+               if (signature->len == 0)
+               {
+                       DBG1(DBG_LIB, "inefficient Huffman coding of signature");
+                       continue;
+               }
                DBG2(DBG_LIB, "signature generation needed %u round%s", tests,
                                          (tests == 1) ? "" : "s");
                break;
        }
        success = TRUE;
 
-       *signature = sig->get_encoding(sig);
-
 end:
        /* cleanup */
        sampler->destroy(sampler);
index 861d4ce..ca385ee 100644 (file)
@@ -15,6 +15,7 @@
 
 #include "bliss_signature.h"
 #include "bliss_bitpacker.h"
+#include "bliss_huffman_coder.h"
 
 
 typedef struct private_bliss_signature_t private_bliss_signature_t;
@@ -54,34 +55,61 @@ METHOD(bliss_signature_t, get_encoding, chunk_t,
        private_bliss_signature_t *this)
 {
        bliss_bitpacker_t *packer;
+       bliss_huffman_coder_t *coder;
+       bliss_huffman_code_t *code;
+       int32_t z1;
+       uint32_t z1_sign;
        uint16_t z2d_bits;
-       chunk_t encoding;
+       chunk_t encoding = chunk_empty;
        int i;
 
        z2d_bits = this->set->z1_bits - this->set->d;
 
+       /* Get Huffman code for this BLISS parameter set */
+       code = bliss_huffman_code_get_by_id(this->set->id);
+       if (!code)
+       {
+               DBG1(DBG_LIB, "no Huffman code found for parameter set %N",
+                        bliss_param_set_id_names, this->set->id);
+               return chunk_empty;
+       }
+
        packer = bliss_bitpacker_create(this->set->n * this->set->z1_bits +
                                                                        this->set->n * z2d_bits +
                                                                        this->set->kappa * this->set->n_bits);
+       coder = bliss_huffman_coder_create(code, packer);
 
        for (i = 0; i < this->set->n; i++)
        {
-               packer->write_bits(packer, this->z1[i], this->set->z1_bits);
-       }
-       for (i = 0; i < this->set->n; i++)
-       {
-               packer->write_bits(packer, this->z2d[i], z2d_bits);
+               /* determine and remove the sign of z1[i]*/
+               z1_sign = this->z1[i] < 0;
+               z1 = z1_sign ? -this->z1[i] : this->z1[i];
+
+               if (!packer->write_bits(packer, z1_sign, 1) ||
+                       !packer->write_bits(packer, z1 & 0xff, 8) ||
+                       !coder->encode(coder, z1 >> 8, this->z2d[i]))
+               {
+                       goto end;
+               }
        }
        for (i = 0; i < this->set->kappa; i++)
        {
-               packer->write_bits(packer, this->c_indices[i], this->set->n_bits);
+               if (!packer->write_bits(packer, this->c_indices[i], this->set->n_bits))
+               {
+                       goto end;
+               }
        }
        encoding = packer->extract_buf(packer);
 
+       DBG2(DBG_LIB, "efficiency of Huffman coder is %6.4f bits/tuple (%u bits)",
+                                  coder->get_bits(coder)/(double)(this->set->n), 
+                                  coder->get_bits(coder));
        DBG2(DBG_LIB, "generated BLISS signature (%u bits encoded in %u bytes)",
                                   packer->get_bits(packer), encoding.len);
-       packer->destroy(packer);
 
+       end:
+       coder->destroy(coder);
+       packer->destroy(packer);
        return encoding;
 }
 
@@ -133,17 +161,19 @@ bliss_signature_t *bliss_signature_create_from_data(bliss_param_set_t *set,
 {
        private_bliss_signature_t *this;
        bliss_bitpacker_t *packer;
-       uint32_t z1_sign, z1_mask, value;
-       uint16_t z2d_sign, z2d_mask, z1_bits, z2d_bits;
+       bliss_huffman_coder_t *coder;
+       bliss_huffman_code_t *code;
+       uint32_t z1_sign, z1_low, value;
+       int32_t z1;
+       int16_t z2;
        int i;
 
-       z1_bits  = set->z1_bits;
-       z2d_bits = set->z1_bits - set->d;
-
-       if (8 * encoding.len < set->n * set->z1_bits + set->n * z2d_bits +
-                                                  set->kappa * set->n_bits)
+       /* Get Huffman code for this BLISS parameter set */
+       code = bliss_huffman_code_get_by_id(set->id);
+       if (!code)
        {
-               DBG1(DBG_LIB, "incorrect BLISS signature size");
+               DBG1(DBG_LIB, "no Huffman code found for parameter set %N",
+                        bliss_param_set_id_names, set->id);
                return NULL;
        }
 
@@ -160,27 +190,33 @@ bliss_signature_t *bliss_signature_create_from_data(bliss_param_set_t *set,
        );
 
        packer = bliss_bitpacker_create_from_data(encoding);
-
-       z1_sign =   1 << (z1_bits - 1);
-       z1_mask = ((1 << (32 - z1_bits)) - 1) << z1_bits;
+       coder = bliss_huffman_coder_create(code, packer);
 
        for (i = 0; i < set->n; i++)
        {
-               packer->read_bits(packer, &value, z1_bits);
-               this->z1[i] = value & z1_sign ? value | z1_mask : value;
+               if (!packer->read_bits(packer, &z1_sign, 1) ||
+                       !packer->read_bits(packer, &z1_low, 8) ||
+                       !coder->decode(coder, &z1, &z2))
+               {
+                       coder->destroy(coder);
+                       packer->destroy(packer);
+                       destroy(this);
+                       return NULL;
+               }
+               z1 = (z1 << 8) + z1_low;
+               this->z1[i] = z1_sign ? -z1 : z1;
+               this->z2d[i] = z2;
        }
+       coder->destroy(coder);
 
-       z2d_sign =   1 << (z2d_bits - 1);
-       z2d_mask = ((1 << (16 - z2d_bits)) - 1) << z2d_bits;
-
-       for (i = 0; i < set->n; i++)
-       {
-               packer->read_bits(packer, &value, z2d_bits);
-               this->z2d[i] = value & z2d_sign ? value | z2d_mask : value;
-       }
        for (i = 0; i < set->kappa; i++)
        {
-               packer->read_bits(packer, &value, set->n_bits);
+               if (!packer->read_bits(packer, &value, set->n_bits))
+               {
+                       packer->destroy(packer);
+                       destroy(this);
+                       return NULL;
+               }
                this->c_indices[i] = value;
        }
        packer->destroy(packer);