/* This file is part of libbrandt.
* Copyright (C) 2016 GNUnet e.V.
*
* libbrandt 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 3 of the License, or (at your option) any later
* version.
*
* libbrandt 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.
*
* You should have received a copy of the GNU General Public License along with
* libbrandt. If not, see .
*/
/**
* @file crypto.c
* @brief Implementation of the crypto primitives.
* @author Markus Teich
*/
#include "platform.h"
#include
#include "crypto.h"
#include "internals.h"
#include "util.h"
#define CURVE "Ed25519"
struct zkp_challenge_dl {
struct ec_mpi g;
struct ec_mpi v;
struct ec_mpi a;
};
struct zkp_challenge_2dle {
struct ec_mpi g1;
struct ec_mpi g2;
struct ec_mpi v;
struct ec_mpi w;
struct ec_mpi a;
struct ec_mpi b;
};
struct zkp_challenge_0og {
struct ec_mpi g;
struct ec_mpi alpha;
struct ec_mpi beta;
struct ec_mpi a1;
struct ec_mpi a2;
struct ec_mpi b1;
struct ec_mpi b2;
};
static gcry_ctx_t ec_ctx;
static gcry_mpi_point_t ec_gen;
static gcry_mpi_point_t ec_zero;
static gcry_mpi_t ec_n;
static struct GNUNET_CRYPTO_EccDlogContext *ec_dlogctx;
/**
* brandt_crypto_init initializes the crypto system and must be called before
* any other function from this file.
*
* @param[in] dlogctx Pointer to the prepared dlog context.
*/
void
brandt_crypto_init (struct GNUNET_CRYPTO_EccDlogContext *dlogctx)
{
gcry_error_t rc;
ec_dlogctx = dlogctx;
rc = gcry_mpi_ec_new (&ec_ctx, NULL, CURVE);
brandt_assert_gpgerr (rc);
ec_gen = gcry_mpi_ec_get_point ("g", ec_ctx, 0);
brandt_assert (NULL != ec_gen);
ec_zero = gcry_mpi_point_new (0);
brandt_assert (NULL != ec_zero);
gcry_mpi_ec_sub (ec_zero, ec_gen, ec_gen, ec_ctx);
ec_n = gcry_mpi_ec_get_mpi ("n", ec_ctx, 1);
brandt_assert (NULL != ec_n);
}
/* --- EC --- */
/**
* ec_skey_create
*
* @param[out] skey where to store the generated secret key. This has to be an
* already initialized mpi.
*/
void
ec_skey_create (gcry_mpi_t skey)
{
gcry_mpi_t ret;
gcry_sexp_t s_keyparam;
gcry_sexp_t priv_sexp;
gcry_sexp_t priv_key;
gcry_sexp_t priv_key2;
gcry_error_t rc;
rc = gcry_sexp_build (&s_keyparam, NULL, "(genkey(ecc(curve \"" CURVE "\")"
"(flags)))");
brandt_assert_gpgerr (rc);
rc = gcry_pk_genkey (&priv_sexp, s_keyparam);
brandt_assert_gpgerr (rc);
gcry_sexp_release (s_keyparam);
priv_key = gcry_sexp_find_token (priv_sexp, "private-key", 11);
brandt_assert (NULL != priv_key);
gcry_sexp_release (priv_sexp);
priv_key2 = gcry_sexp_find_token (priv_key, "d", 1);
brandt_assert (NULL != priv_key2);
gcry_sexp_release (priv_key);
ret = gcry_sexp_nth_mpi (priv_key2, 1, GCRYMPI_FMT_USG);
brandt_assert (NULL != ret);
gcry_sexp_release (priv_key2);
gcry_mpi_snatch (skey, ret);
}
/**
* ec_keypair_create creates a new keypair by creating a random secret key first
* and multipyling the base point with it to get the public key.
*
* @param[out] pkey where to store the generated public key
* @param[out] skey where to store the generated secret key. May be NULL if
* you're not interested in the secret key and just need a random point.
*/
void
ec_keypair_create (gcry_mpi_point_t pkey, gcry_mpi_t skey)
{
gcry_mpi_t sk;
brandt_assert (NULL != pkey);
sk = (NULL == skey) ? gcry_mpi_new (256) : skey;
ec_skey_create (sk);
gcry_mpi_ec_mul (pkey, sk, ec_gen, ec_ctx);
if (NULL == skey)
gcry_mpi_release (sk);
}
/**
* ec_keypair_create_base
*
* @param[out] pkey where to store the generated public key
* @param[out] skey where to store the generated secret key
* @param[in] base which base point should be used to calculate the public key
*/
void
ec_keypair_create_base (gcry_mpi_point_t pkey,
gcry_mpi_t skey,
const gcry_mpi_point_t base)
{
brandt_assert (NULL != pkey);
brandt_assert (NULL != skey);
brandt_assert (NULL != base);
ec_skey_create (skey);
gcry_mpi_ec_mul (pkey, skey, base, ec_ctx);
}
/**
* ec_point_copy creates a copy of one curve point
*
* @param[out] dst where to store the copy
* @param[in] src the input point to be copied
*/
void
ec_point_copy (gcry_mpi_point_t dst, const gcry_mpi_point_t src)
{
gcry_mpi_t x = gcry_mpi_new (256);
gcry_mpi_t y = gcry_mpi_new (256);
gcry_mpi_t z = gcry_mpi_new (256);
brandt_assert (dst && src);
gcry_mpi_point_get (x, y, z, src);
gcry_mpi_point_snatch_set (dst, x, y, z);
}
/**
* ec_point_cmp compares two curve points
*
* @param[in] a the first point
* @param[in] b the second point
* @return 0 if @a a and @a b represent the same point on the curve, something
* else otherwise
*/
int
ec_point_cmp (const gcry_mpi_point_t a, const gcry_mpi_point_t b)
{
int ret = 1;
gcry_mpi_t ax = gcry_mpi_new (256);
gcry_mpi_t bx = gcry_mpi_new (256);
gcry_mpi_t ay = gcry_mpi_new (256);
gcry_mpi_t by = gcry_mpi_new (256);
brandt_assert (a && b);
if (!ax || !bx || !ay || !by)
{
weprintf ("could not init point in point_cmp");
return 1;
}
if (!gcry_mpi_ec_get_affine (ax, ay, a, ec_ctx) &&
!gcry_mpi_ec_get_affine (bx, by, b, ec_ctx))
{
ret = gcry_mpi_cmp (ax, bx) || gcry_mpi_cmp (ay, by);
}
gcry_mpi_release (ax);
gcry_mpi_release (bx);
gcry_mpi_release (ay);
gcry_mpi_release (by);
return ret;
}
/**
* mpi_serialize outputs the given MPI value to the given destination buffer in
* network byte order. The MPI @a src may not be negative.
*
* @param[out] dst where to output to
* @param[in] src value to write to @a dst
*/
void
mpi_serialize (struct ec_mpi *dst, gcry_mpi_t src)
{
size_t rsize = 0;
if (gcry_mpi_get_flag (src, GCRYMPI_FLAG_OPAQUE))
{ /* Store opaque MPIs left aligned. Used by Ed25519 point compression */
unsigned int nbits;
const void *vp = gcry_mpi_get_opaque (src, &nbits);
brandt_assert (vp);
rsize = (nbits + 7) / 8;
if (rsize > sizeof (struct ec_mpi))
rsize = sizeof (struct ec_mpi);
memcpy (dst, vp, rsize);
if (rsize < sizeof (struct ec_mpi))
memset (((char *)dst) + rsize, 0, sizeof (struct ec_mpi) - rsize);
}
else
{ /* Store regular MPIs as unsigned ints right aligned into the buffer. */
char *cp = (char *)dst;
gcry_error_t rc;
rc = gcry_mpi_print (GCRYMPI_FMT_USG, (void *)dst,
sizeof (struct ec_mpi), &rsize, src);
brandt_assert_gpgerr (rc);
/* Shift the output to the right, if shorter than available space */
if (rsize && rsize < sizeof (struct ec_mpi))
{
memmove (&cp[sizeof (struct ec_mpi) - rsize], dst, rsize);
memset (dst, 0, sizeof (struct ec_mpi) - rsize);
}
}
}
/**
* mpi_parse converts src buffer into MPI value.
* The buffer is interpreted as network byte order, unsigned integer.
*
* @param[out] dst where to store MPI value. Must be initialized.
* @param[in] src raw data source (GCRYMPI_FMT_USG)
*/
void
mpi_parse (gcry_mpi_t dst, const struct ec_mpi *src)
{
gcry_mpi_t ret;
gcry_error_t rc;
rc = gcry_mpi_scan (&ret,
GCRYMPI_FMT_USG,
src,
sizeof (struct ec_mpi),
NULL);
brandt_assert_gpgerr (rc);
gcry_mpi_snatch (dst, ret);
}
/**
* ec_point_serialize outputs the given curve point to the @a dst buffer.
*
* @param[out] dst where to write the raw data to
* @param[in] src curve point to write to @a dst
*/
void
ec_point_serialize (struct ec_mpi *dst, const gcry_mpi_point_t src)
{
gcry_sexp_t s;
gcry_ctx_t ctx;
gcry_error_t rc;
gcry_mpi_t q;
brandt_assert (dst);
rc = gcry_sexp_build (&s, NULL, "(public-key(ecc(curve " CURVE ")))");
brandt_assert_gpgerr (rc);
brandt_assert (NULL != s);
rc = gcry_mpi_ec_new (&ctx, s, NULL);
brandt_assert_gpgerr (rc);
gcry_sexp_release (s);
rc = gcry_mpi_ec_set_point ("q", src, ctx);
brandt_assert_gpgerr (rc);
q = gcry_mpi_ec_get_mpi ("q@eddsa", ctx, 0);
brandt_assert (NULL != q);
gcry_ctx_release (ctx);
mpi_serialize (dst, q);
gcry_mpi_release (q);
}
/**
* ec_point_parse parses a point on the Ed25519 curve from @a src into @a dst.
*
* @param[out] dst where to store the curve point. Must be initialized
* @param[in] src raw data source
*/
void
ec_point_parse (gcry_mpi_point_t dst, const struct ec_mpi *src)
{
gcry_sexp_t s;
gcry_ctx_t ctx;
gcry_mpi_point_t ret;
gcry_error_t rc;
rc = gcry_sexp_build (&s, NULL, "(public-key(ecc(curve " CURVE ")(q %b)))",
sizeof (struct ec_mpi), src);
brandt_assert_gpgerr (rc);
rc = gcry_mpi_ec_new (&ctx, s, NULL);
brandt_assert_gpgerr (rc);
gcry_sexp_release (s);
ret = gcry_mpi_ec_get_point ("q", ctx, 0);
brandt_assert (ret);
gcry_ctx_release (ctx);
gcry_mpi_ec_mul (dst, GCRYMPI_CONST_ONE, ret, ec_ctx);
gcry_mpi_point_release (ret);
}
/**
* smc_free1 releases all points in @a dst and frees the memory
*
* @param[in,out] dst The 1 dimensional array to clean up
* @param[in] size1 size of the first dimension
*/
void
smc_free1 (gcry_mpi_point_t *dst, uint16_t size1)
{
if (NULL == dst)
return;
for (uint16_t i = 0; i < size1; i++)
if (NULL != dst[i])
gcry_mpi_point_release (dst[i]);
free (dst);
}
/**
* smc_init1 creates a 1 dimensional array of curve points. Make sure to
* initialize the values before using them, they are not automatically set to
* the zero point!
*
* @param[in] size1 size of the first dimension
* @return a pointer to the array or NULL on error.
* If not used anymore use smc_free2 to reclaim the memory.
*/
gcry_mpi_point_t *
smc_init1 (uint16_t size1)
{
gcry_mpi_point_t *ret;
ret = GNUNET_new_array (size1, gcry_mpi_point_t);
for (uint16_t i = 0; i < size1; i++)
{
if (NULL == (ret[i] = gcry_mpi_point_new (0)))
{
weprintf ("could not init point in 1 dimensional array. "
"out of memory?");
smc_free1 (ret, size1);
return NULL;
}
}
return ret;
}
/**
* smc_free2 releases all points in @a dst and frees the memory
*
* @param[in,out] dst The 2 dimensional array to clean up
* @param[in] size1 size of the first dimension
* @param[in] size2 size of the second dimension
*/
void
smc_free2 (gcry_mpi_point_t **dst, uint16_t size1, uint16_t size2)
{
if (NULL == dst)
return;
for (uint16_t i = 0; i < size1; i++)
for (uint16_t j = 0; j < size2; j++)
if (NULL != dst[i][j])
gcry_mpi_point_release (dst[i][j]);
free (dst);
}
/**
* smc_init2 creates a 2 dimensional array of curve points. Make sure to
* initialize the values before using them, they are not automatically set to
* the zero point!
*
* @param[in] size1 size of the first dimension
* @param[in] size2 size of the second dimension
* @return a pointer to the array or NULL on error.
* If not used anymore use smc_free2 to reclaim the memory.
*/
gcry_mpi_point_t **
smc_init2 (uint16_t size1, uint16_t size2)
{
gcry_mpi_point_t **ret;
gcry_mpi_point_t *data;
if (NULL == (ret = calloc (size1, sizeof (*ret) + size2 * sizeof (**ret))))
{
weprintf ("could not alloc memory for 2 dimensional point array");
return NULL;
}
data = (gcry_mpi_point_t *)&ret[size1];
for (uint16_t i = 0; i < size1; i++)
{
ret[i] = &data[i * size2];
for (uint16_t j = 0; j < size2; j++)
{
if (NULL == (ret[i][j] = gcry_mpi_point_new (0)))
{
weprintf ("could not init point in 2 dimensional array. "
"out of memory?");
smc_free2 (ret, size1, size2);
return NULL;
}
}
}
return ret;
}
/**
* smc_free3 releases all points in @a dst and frees the memory
*
* @param[in,out] dst The 3 dimensional array to clean up
* @param[in] size1 size of the first dimension
* @param[in] size2 size of the second dimension
* @param[in] size3 size of the third dimension
*/
void
smc_free3 (gcry_mpi_point_t ***dst,
uint16_t size1,
uint16_t size2,
uint16_t size3)
{
if (NULL == dst)
return;
for (uint16_t i = 0; i < size1; i++)
for (uint16_t j = 0; j < size2; j++)
for (uint16_t k = 0; k < size3; k++)
if (NULL != dst[i][j][k])
gcry_mpi_point_release (dst[i][j][k]);
free (dst);
}
/**
* smc_init3 creates a 3 dimensional array of curve points. Make sure to
* initialize the values before using them, they are not automatically set to
* the zero point!
*
* @param[in] size1 size of the first dimension
* @param[in] size2 size of the second dimension
* @param[in] size3 size of the third dimension
* @return a pointer to the array or NULL on error.
* If not used anymore use smc_free3 to reclaim the memory.
*/
gcry_mpi_point_t ***
smc_init3 (uint16_t size1, uint16_t size2, uint16_t size3)
{
gcry_mpi_point_t ***ret;
gcry_mpi_point_t **layer1;
gcry_mpi_point_t *layer2;
if (NULL == (ret = calloc (size1, sizeof (*ret) +
size2 * sizeof (**ret) +
size2 * size3 * sizeof (***ret))))
{
weprintf ("could not alloc memory for 3 dimensional point array");
return NULL;
}
layer1 = (gcry_mpi_point_t **)&ret[size1];
layer2 = (gcry_mpi_point_t *)&layer1[size1 * size2];
for (uint16_t i = 0; i < size1; i++)
{
ret[i] = &layer1[i * size2];
for (uint16_t j = 0; j < size2; j++)
{
layer1[i * size2 + j] = &layer2[(i * size2 + j) * size3];
for (uint16_t k = 0; k < size3; k++)
{
if (NULL == (ret[i][j][k] = gcry_mpi_point_new (0)))
{
weprintf ("could not init point in 2 dimensional array. "
"out of memory?");
smc_free3 (ret, size1, size2, size3);
return NULL;
}
}
}
}
return ret;
}
/**
* smc_sums_partial calculates sums up until the current index and stores them
* in @a out. \f$\forall i \leq len: out_i=\sum_{h=1}^iin_h\f$
*
* @param[out] out Where to store the resulting sums. Points must already be
* initialized beforehand.
* @param[in] in Input points.
* @param[in] len The length of @a out. @a in must be at least @a step times @a
* len elements long.
* @param[in] stepi The amount of items to advance in @a in each step. Can be
* used to sum over multi-dimensional arrays.
* @param[in] stepo The amount of items to advance in @a out each step. Can be
* used to store the sum in multi-dimensional arrays.
*/
static void
smc_sums_partial (gcry_mpi_point_t out[],
gcry_mpi_point_t in[],
uint16_t len,
uint16_t stepi,
uint16_t stepo)
{
brandt_assert (NULL != out);
for (uint16_t i = 0, o = 0; o < len * stepo; i += stepi, o += stepo)
gcry_mpi_ec_add (out[o], (o ? out[o - stepo] : ec_zero), in[i], ec_ctx);
}
/**
* smc_sum calculates the sum of all input points.
* \f$out=\sum_{i=1}^{len}in_i\f$
*
* @param[out] out Where to store the result
* @param[in] in Input points.
* @param[in] len The amount of summands to use from @a in. @a in must be at
* least @a step times @a len elements long.
* @param[in] step The amount of items to advance in @a in each step. Can be
* used to sum over multi-dimensional arrays.
*/
static void
smc_sum (gcry_mpi_point_t out,
gcry_mpi_point_t in[],
uint16_t len,
uint16_t step)
{
brandt_assert (NULL != out);
ec_point_copy (out, ec_zero);
for (uint16_t i = 0; i < len * step; i += step)
gcry_mpi_ec_add (out, out, in[i], ec_ctx);
}
/**
* smc_gen_keyshare creates the private keyshare and computes the
* public key share
*
* @param[in] ad Pointer to the BRANDT_Auction struct to operate on
* @param[out] buflen Size of the returned message buffer in bytes
* @return A buffer containing the public key share
* which needs to be broadcast
*/
unsigned char *
smc_gen_keyshare (struct BRANDT_Auction *ad, size_t *buflen)
{
unsigned char *ret;
struct proof_dl *proof1;
struct msg_head *head;
struct ec_mpi *pubkey_share;
brandt_assert (ad && buflen);
*buflen = (sizeof (*head) +
sizeof (*pubkey_share) +
sizeof (*proof1));
ret = GNUNET_new_array (*buflen, unsigned char);
if (NULL == (ad->y = smc_init1 (ad->n)))
{
weprintf ("unable to alloc memory for key shares");
return NULL;
}
head = (struct msg_head *)ret;
head->prot_version = htonl (0);
head->msg_type = htonl (msg_init);
proof1 = (struct proof_dl *)(ret + sizeof (*head) + sizeof (*pubkey_share));
ad->x = gcry_mpi_new (256);
ec_skey_create (ad->x);
smc_zkp_dl (ad->y[ad->i], ad->x, proof1);
pubkey_share = (struct ec_mpi *)(ret + sizeof (*head));
ec_point_serialize (pubkey_share, ad->y[ad->i]);
return ret;
}
int
smc_recv_keyshare (struct BRANDT_Auction *ad,
const unsigned char *buf,
size_t buflen,
uint16_t sender)
{
int ret = 0;
struct proof_dl *proof1;
gcry_mpi_point_t y = gcry_mpi_point_new (0);
brandt_assert (ad && buf);
if (buflen != (sizeof (struct ec_mpi) + sizeof (*proof1)))
{
weprintf ("wrong size of received key share");
goto quit;
}
proof1 = (struct proof_dl *)(buf + sizeof (struct ec_mpi));
ec_point_parse (y, (struct ec_mpi *)buf);
if (smc_zkp_dl_check (y, proof1))
{
weprintf ("wrong zkp1 for public key share received");
goto quit;
}
ec_point_copy (ad->y[sender], y);
ret = 1;
quit:
gcry_mpi_point_release (y);
return ret;
}
/**
* smc_encrypt_bid encrypts the own bid with the shared public key and packs it
* into a message together with proofs of correctnes.
*
* @param[in] ad Pointer to the BRANDT_Auction struct to operate on
* @param[out] buflen Size of the returned message buffer in bytes
* @return A buffer containing the encrypted bid
* which needs to be broadcast
*/
unsigned char *
smc_encrypt_bid (struct BRANDT_Auction *ad, size_t *buflen)
{
unsigned char *ret;
unsigned char *cur;
struct proof_0og *proof3;
struct msg_head *head;
gcry_mpi_t r_sum;
gcry_mpi_t r_part;
brandt_assert (ad && buflen);
*buflen = (sizeof (*head) + /* msg header */
ad->k * /* k * (alpha, beta, proof3) */
(sizeof (struct ec_mpi) * 2 + /* alpha, beta */
sizeof (*proof3)) +
sizeof (struct proof_2dle));
ret = GNUNET_new_array (*buflen, unsigned char);
if (NULL == (ad->alpha = smc_init2 (ad->n, ad->k)) ||
NULL == (ad->beta = smc_init2 (ad->n, ad->k)))
{
weprintf ("unable to alloc memory for encrypted bids");
return NULL;
}
head = (struct msg_head *)ret;
head->prot_version = htonl (0);
head->msg_type = htonl (msg_bid);
cur = ret + sizeof (*head);
ad->Y = gcry_mpi_point_new (0);
smc_sum (ad->Y, ad->y, ad->n, 1);
r_sum = gcry_mpi_new (256);
r_part = gcry_mpi_new (256);
for (uint16_t j = 0; j < ad->k; j++)
{
proof3 = (struct proof_0og *)(cur + 2 * sizeof (struct ec_mpi));
smc_zkp_0og (j == ad->b,
ad->Y,
r_part,
ad->alpha[ad->i][j],
ad->beta[ad->i][j],
proof3);
ec_point_serialize ((struct ec_mpi *)cur, ad->alpha[ad->i][j]);
ec_point_serialize (&((struct ec_mpi *)cur)[1], ad->beta[ad->i][j]);
gcry_mpi_addm (r_sum, r_sum, r_part, ec_n);
cur += 2 * sizeof (struct ec_mpi) + sizeof (struct proof_0og);
}
smc_zkp_2dle (NULL, NULL, ad->Y, ec_gen, r_sum, (struct proof_2dle *)cur);
gcry_mpi_release (r_sum);
gcry_mpi_release (r_part);
return ret;
}
int
smc_recv_encrypted_bid (struct BRANDT_Auction *ad,
const unsigned char *buf,
size_t buflen,
uint16_t sender)
{
int ret = 0;
const unsigned char *cur = buf;
struct proof_0og *proof3;
gcry_mpi_point_t **ct; /* ciphertexts */
gcry_mpi_point_t alpha_sum = gcry_mpi_point_new (0);
gcry_mpi_point_t beta_sum = gcry_mpi_point_new (0);
brandt_assert (ad && buf);
if (buflen != (ad->k * (sizeof (struct ec_mpi) * 2 + sizeof (*proof3)) +
sizeof (struct proof_2dle)) ||
NULL == (ct = smc_init2 (2, ad->k)))
{
weprintf ("wrong size of received encrypted bid");
goto quit;
}
ec_point_copy (alpha_sum, ec_zero);
ec_point_copy (beta_sum, ec_zero);
for (uint16_t j = 0; j < ad->k; j++)
{
ec_point_parse (ct[0][j], (struct ec_mpi *)cur);
ec_point_parse (ct[1][j], &((struct ec_mpi *)cur)[1]);
proof3 = (struct proof_0og *)(cur + 2 * sizeof (struct ec_mpi));
if (smc_zkp_0og_check (ad->Y, ct[0][j], ct[1][j], proof3))
{
weprintf ("wrong zkp3 for alpha, beta received");
goto quit;
}
gcry_mpi_ec_add (alpha_sum, alpha_sum, ct[0][j], ec_ctx);
gcry_mpi_ec_add (beta_sum, beta_sum, ct[1][j], ec_ctx);
cur += 2 * sizeof (struct ec_mpi) + sizeof (struct proof_0og);
}
gcry_mpi_ec_sub (alpha_sum, alpha_sum, ec_gen, ec_ctx);
if (smc_zkp_2dle_check (alpha_sum,
beta_sum,
ad->Y,
ec_gen,
(struct proof_2dle *)cur))
{
weprintf ("wrong zkp2 for alpha, beta received");
goto quit;
}
for (uint16_t j = 0; j < ad->k; j++)
{
ec_point_copy (ad->alpha[sender][j], ct[0][j]);
ec_point_copy (ad->beta[sender][j], ct[1][j]);
}
smc_free2 (ct, 2, ad->k);
ret = 1; /* finally success */
quit:
gcry_mpi_point_release (alpha_sum);
gcry_mpi_point_release (beta_sum);
return ret;
}
/**
* fp_pub_compute_outcome computes the outcome for first price auctions with a
* public outcome and packs it into a message buffer together with proofs of
* correctnes.
*
* @param[in] ad Pointer to the BRANDT_Auction struct to operate on
* @param[out] buflen Size of the returned message buffer in bytes
* @return A buffer containing the encrypted outcome vectors
* which needs to be broadcast
*/
unsigned char *
fp_pub_compute_outcome (struct BRANDT_Auction *ad, size_t *buflen)
{
unsigned char *ret;
unsigned char *cur;
struct msg_head *head;
gcry_mpi_t coeff = gcry_mpi_copy (GCRYMPI_CONST_ONE);
gcry_mpi_point_t tmp = gcry_mpi_point_new (0);
gcry_mpi_point_t *tlta1;
gcry_mpi_point_t *tltb1;
gcry_mpi_point_t **tlta2;
gcry_mpi_point_t **tltb2;
struct ec_mpi *gamma;
struct ec_mpi *delta;
struct proof_2dle *proof2;
brandt_assert (ad && buflen);
*buflen = (sizeof (*head) +
ad->k * (sizeof (*gamma) +
sizeof (*delta) +
sizeof (*proof2)));
ret = GNUNET_new_array (*buflen, unsigned char);
if (NULL == (ad->gamma2 = smc_init2 (ad->n, ad->k)) ||
NULL == (ad->delta2 = smc_init2 (ad->n, ad->k)) ||
NULL == (ad->tmpa1 = smc_init1 (ad->k)) ||
NULL == (ad->tmpb1 = smc_init1 (ad->k)))
{
weprintf ("unable to alloc memory for first price outcome computation");
return NULL;
}
head = (struct msg_head *)ret;
head->prot_version = htonl (0);
head->msg_type = htonl (msg_outcome);
cur = ret + sizeof (*head);
/* create temporary lookup tables with partial sums */
tlta1 = smc_init1 (ad->k);
tltb1 = smc_init1 (ad->k);
tlta2 = smc_init2 (ad->n, ad->k);
tltb2 = smc_init2 (ad->n, ad->k);
/* temporary lookup table for sum of bid vectors */
for (uint16_t i = 0; i < ad->n; i++)
{
smc_sums_partial (tlta2[i], ad->alpha[i], ad->k, 1, 1);
smc_sums_partial (tltb2[i], ad->beta[i], ad->k, 1, 1);
for (uint16_t j = 0; j < ad->k; j++)
{
gcry_mpi_ec_sub (tlta2[i][j],
tlta2[i][ad->k - 1],
tlta2[i][j],
ec_ctx);
gcry_mpi_ec_sub (tltb2[i][j],
tltb2[i][ad->k - 1],
tltb2[i][j],
ec_ctx);
}
brandt_assert (!ec_point_cmp (ec_zero, tlta2[i][ad->k - 1]));
brandt_assert (!ec_point_cmp (ec_zero, tltb2[i][ad->k - 1]));
}
for (uint16_t j = 0; j < ad->k; j++)
{
smc_sum (tlta1[j], &tlta2[0][j], ad->n, ad->k);
smc_sum (tltb1[j], &tltb2[0][j], ad->n, ad->k);
}
smc_free2 (tlta2, ad->n, ad->k);
smc_free2 (tltb2, ad->n, ad->k);
brandt_assert (!ec_point_cmp (ec_zero, tlta1[ad->k - 1]));
brandt_assert (!ec_point_cmp (ec_zero, tltb1[ad->k - 1]));
/* initialize tmp array with zeroes, since we are calculating a sum */
for (uint16_t j = 0; j < ad->k; j++)
{
ec_point_copy (ad->tmpa1[j], ec_zero);
ec_point_copy (ad->tmpb1[j], ec_zero);
}
/* store the \sum_{i=1}^n2^{i-1}b_i in tmp1 until outcome determination,
* since it is needed each time a gamma,delta pair is received from another
* bidder */
for (uint16_t i = 0; i < ad->n; i++)
{
for (uint16_t j = 0; j < ad->k; j++)
{
gcry_mpi_ec_mul (tmp, coeff, ad->alpha[i][j], ec_ctx);
gcry_mpi_ec_add (ad->tmpa1[j], ad->tmpa1[j], tmp, ec_ctx);
gcry_mpi_ec_mul (tmp, coeff, ad->beta[i][j], ec_ctx);
gcry_mpi_ec_add (ad->tmpb1[j], ad->tmpb1[j], tmp, ec_ctx);
}
gcry_mpi_lshift (coeff, coeff, 1);
}
for (uint16_t j = 0; j < ad->k; j++)
{
gamma = (struct ec_mpi *)cur;
delta = &((struct ec_mpi *)cur)[1];
proof2 = (struct proof_2dle *)(cur + 2 * sizeof (struct ec_mpi));
/* copy unmasked outcome to all other bidder layers so they don't
* have to be recomputed to check the ZK proof_2dle's from other
* bidders when receiving their outcome messages */
for (uint16_t a = 0; a < ad->n; a++)
{
ec_point_copy (ad->gamma2[a][j], tlta1[j]);
ec_point_copy (ad->delta2[a][j], tltb1[j]);
}
/* apply random masking for losing bidders */
smc_zkp_2dle (ad->gamma2[ad->i][j],
ad->delta2[ad->i][j],
tlta1[j],
tltb1[j],
NULL,
proof2);
ec_point_serialize (gamma, ad->gamma2[ad->i][j]);
ec_point_serialize (delta, ad->delta2[ad->i][j]);
/* add winner determination for own gamma,delta */
gcry_mpi_ec_add (ad->gamma2[ad->i][j],
ad->gamma2[ad->i][j],
ad->tmpa1[j],
ec_ctx);
gcry_mpi_ec_add (ad->delta2[ad->i][j],
ad->delta2[ad->i][j],
ad->tmpb1[j],
ec_ctx);
cur += sizeof (*gamma) + sizeof (*delta) + sizeof (*proof2);
}
gcry_mpi_release (coeff);
gcry_mpi_point_release (tmp);
smc_free1 (tlta1, ad->k);
smc_free1 (tltb1, ad->k);
return ret;
}
int
fp_pub_recv_outcome (struct BRANDT_Auction *ad,
const unsigned char *buf,
size_t buflen,
uint16_t sender)
{
int ret = 0;
const unsigned char *cur = buf;
struct proof_2dle *proof2;
gcry_mpi_point_t gamma = gcry_mpi_point_new (0);
gcry_mpi_point_t delta = gcry_mpi_point_new (0);
brandt_assert (ad && buf);
if (buflen != (ad->k * (2 * sizeof (struct ec_mpi) + sizeof (*proof2))))
{
weprintf ("wrong size of received outcome");
goto quit;
}
for (uint16_t j = 0; j < ad->k; j++)
{
ec_point_parse (gamma, (struct ec_mpi *)cur);
ec_point_parse (delta, &((struct ec_mpi *)cur)[1]);
proof2 = (struct proof_2dle *)(cur + 2 * sizeof (struct ec_mpi));
if (smc_zkp_2dle_check (gamma,
delta,
ad->gamma2[sender][j],
ad->delta2[sender][j],
proof2))
{
weprintf ("wrong zkp2 for gamma, delta received");
goto quit;
}
ec_point_copy (ad->gamma2[sender][j], gamma);
ec_point_copy (ad->delta2[sender][j], delta);
/* add winner determination summand */
gcry_mpi_ec_add (ad->gamma2[sender][j],
ad->gamma2[sender][j],
ad->tmpa1[j],
ec_ctx);
gcry_mpi_ec_add (ad->delta2[sender][j],
ad->delta2[sender][j],
ad->tmpb1[j],
ec_ctx);
cur += 2 * sizeof (struct ec_mpi) + sizeof (*proof2);
}
ret = 1;
quit:
gcry_mpi_point_release (gamma);
gcry_mpi_point_release (delta);
return ret;
}
/**
* fp_pub_decrypt_outcome decrypts part of the outcome and packs it into a
* message buffer together with proofs of correctnes.
*
* @param[in] ad Pointer to the BRANDT_Auction struct to operate on
* @param[out] buflen Size of the returned message buffer in bytes
* @return A buffer containing the own share of the decrypted outcome
* which needs to be broadcast
*/
unsigned char *
fp_pub_decrypt_outcome (struct BRANDT_Auction *ad, size_t *buflen)
{
unsigned char *ret;
unsigned char *cur;
struct msg_head *head;
gcry_mpi_point_t tmp = gcry_mpi_point_new (0);
struct ec_mpi *phi;
struct proof_2dle *proof2;
brandt_assert (ad && buflen);
*buflen = (sizeof (*head) + ad->k * (sizeof (*phi) + sizeof (*proof2)));
ret = GNUNET_new_array (*buflen, unsigned char);
if (NULL == (ad->phi2 = smc_init2 (ad->n, ad->k)))
{
weprintf ("unable to alloc memory for first price outcome decryption");
return NULL;
}
head = (struct msg_head *)ret;
head->prot_version = htonl (0);
head->msg_type = htonl (msg_decrypt);
cur = ret + sizeof (*head);
for (uint16_t j = 0; j < ad->k; j++)
{
phi = (struct ec_mpi *)cur;
proof2 = (struct proof_2dle *)(cur + sizeof (*phi));
smc_sum (tmp, &ad->delta2[0][j], ad->n, ad->k);
/* copy still encrypted outcome to all other bidder layers so they
* don't have to be recomputed to check the ZK proof_2dle's from
* other bidders when receiving their outcome decryption messages */
for (uint16_t a = 0; a < ad->n; a++)
ec_point_copy (ad->phi2[a][j], tmp);
/* decrypt outcome component and prove the correct key was used */
smc_zkp_2dle (ad->phi2[ad->i][j],
NULL,
tmp,
ec_gen,
ad->x,
proof2);
ec_point_serialize (phi, ad->phi2[ad->i][j]);
cur += sizeof (*phi) + sizeof (*proof2);
}
gcry_mpi_point_release (tmp);
return ret;
}
int
fp_pub_recv_decryption (struct BRANDT_Auction *ad,
const unsigned char *buf,
size_t buflen,
uint16_t sender)
{
int ret = 0;
const unsigned char *cur = buf;
struct proof_2dle *proof2;
gcry_mpi_point_t phi = gcry_mpi_point_new (0);
brandt_assert (ad && buf);
if (buflen != (ad->k * (sizeof (struct ec_mpi) + sizeof (*proof2))))
{
weprintf ("wrong size of received outcome decryption");
goto quit;
}
for (uint16_t j = 0; j < ad->k; j++)
{
ec_point_parse (phi, (struct ec_mpi *)cur);
proof2 = (struct proof_2dle *)(cur + sizeof (struct ec_mpi));
if (smc_zkp_2dle_check (phi,
ad->y[sender],
ad->phi2[sender][j],
ec_gen,
proof2))
{
weprintf ("wrong zkp2 for phi, y received");
goto quit;
}
ec_point_copy (ad->phi2[sender][j], phi);
cur += sizeof (struct ec_mpi) + sizeof (*proof2);
}
ret = 1;
quit:
gcry_mpi_point_release (phi);
return ret;
}
int32_t
fp_pub_determine_outcome (struct BRANDT_Auction *ad, uint16_t *winner)
{
int32_t ret = -1;
int dlogi = -1;
gcry_mpi_t dlog = gcry_mpi_new (256);
gcry_mpi_point_t sum_gamma = gcry_mpi_point_new (0);
gcry_mpi_point_t sum_phi = gcry_mpi_point_new (0);
brandt_assert (ad);
for (uint16_t j = ad->k - 1; j >= 0; j--)
{
smc_sum (sum_gamma, &ad->gamma2[0][j], ad->n, ad->k);
smc_sum (sum_phi, &ad->phi2[0][j], ad->n, ad->k);
gcry_mpi_ec_sub (sum_gamma, sum_gamma, sum_phi, ec_ctx);
/* first non-zero component determines the price */
if (ec_point_cmp (sum_gamma, ec_zero))
{
ret = j;
break;
}
}
dlogi = GNUNET_CRYPTO_ecc_dlog (ec_dlogctx, sum_gamma);
brandt_assert (dlogi > 0);
gcry_mpi_set_ui (dlog, (unsigned long)dlogi);
for (uint16_t i = 0; i < ad->n; i++)
{
if (gcry_mpi_test_bit (dlog, i))
{
if (winner)
*winner = i;
break;
}
}
gcry_mpi_release (dlog);
gcry_mpi_point_release (sum_gamma);
gcry_mpi_point_release (sum_phi);
return ret;
}
/**
* fp_priv_compute_outcome computes encrypted outcome shares and packs them into
* a message buffer together with proofs of correctnes.
*
* @param[in] ad Pointer to the BRANDT_Auction struct to operate on
* @param[out] buflen Size of the returned message buffer in bytes
* @return A buffer containing the encrypted outcome vectors
* which needs to be broadcast
*/
unsigned char *
fp_priv_compute_outcome (struct BRANDT_Auction *ad, size_t *buflen)
{
unsigned char *ret;
unsigned char *cur;
struct msg_head *head;
gcry_mpi_point_t tmpa = gcry_mpi_point_new (0);
gcry_mpi_point_t tmpb = gcry_mpi_point_new (0);
gcry_mpi_point_t *tlta1;
gcry_mpi_point_t *tltb1;
gcry_mpi_point_t **tlta2;
gcry_mpi_point_t **tltb2;
gcry_mpi_point_t **tlta3;
gcry_mpi_point_t **tltb3;
struct ec_mpi *gamma;
struct ec_mpi *delta;
struct proof_2dle *proof2;
brandt_assert (ad && buflen);
*buflen = (sizeof (*head) + /* msg header */
ad->n * ad->k * /* nk * (gamma, delta, proof2) */
(sizeof (*gamma) + sizeof (*delta) + sizeof (*proof2)));
ret = GNUNET_new_array (*buflen, unsigned char);
if (NULL == (ad->gamma3 = smc_init3 (ad->n, ad->n, ad->k)) ||
NULL == (ad->delta3 = smc_init3 (ad->n, ad->n, ad->k)))
{
weprintf ("unable to alloc memory for first price outcome computation");
return NULL;
}
head = (struct msg_head *)ret;
head->prot_version = htonl (0);
head->msg_type = htonl (msg_outcome);
cur = ret + sizeof (*head);
/* create temporary lookup tables with partial sums */
tlta1 = smc_init1 (ad->k);
tltb1 = smc_init1 (ad->k);
tlta2 = smc_init2 (ad->n, ad->k);
tltb2 = smc_init2 (ad->n, ad->k);
tlta3 = smc_init2 (ad->n, ad->k);
tltb3 = smc_init2 (ad->n, ad->k);
/* temporary lookup table for first summand (no one has a higher bid) */
for (uint16_t i = 0; i < ad->n; i++)
{
smc_sums_partial (tlta2[i], ad->alpha[i], ad->k, 1, 1);
smc_sums_partial (tltb2[i], ad->beta[i], ad->k, 1, 1);
for (uint16_t j = 0; j < ad->k; j++)
{
gcry_mpi_ec_sub (tlta3[i][j],
tlta2[i][ad->k - 1],
tlta2[i][j],
ec_ctx);
gcry_mpi_ec_sub (tltb3[i][j],
tltb2[i][ad->k - 1],
tltb2[i][j],
ec_ctx);
}
brandt_assert (!ec_point_cmp (ec_zero, tlta3[i][ad->k - 1]));
brandt_assert (!ec_point_cmp (ec_zero, tltb3[i][ad->k - 1]));
}
for (uint16_t j = 0; j < ad->k; j++)
{
smc_sum (tlta1[j], &tlta3[0][j], ad->n, ad->k);
smc_sum (tltb1[j], &tltb3[0][j], ad->n, ad->k);
}
brandt_assert (!ec_point_cmp (ec_zero, tlta1[ad->k - 1]));
brandt_assert (!ec_point_cmp (ec_zero, tltb1[ad->k - 1]));
/* \todo: merge into one nested i,j loop and one nested j,i loop? */
/* temporary lookup table for second summand (my bid is not lower) */
for (uint16_t i = 0; i < ad->n; i++)
{
for (uint16_t j = 0; j < ad->k; j++)
{
gcry_mpi_ec_sub (tlta2[i][j], tlta2[i][j], ad->alpha[i][j], ec_ctx);
gcry_mpi_ec_sub (tltb2[i][j], tltb2[i][j], ad->beta[i][j], ec_ctx);
}
brandt_assert (!ec_point_cmp (ec_zero, tlta2[i][0]));
brandt_assert (!ec_point_cmp (ec_zero, tltb2[i][0]));
}
/* temporary lookup table for third summand (no one with a lower index has
* the same bid) */
for (uint16_t j = 0; j < ad->k; j++)
{
smc_sums_partial (&tlta3[0][j], &ad->alpha[0][j], ad->n, ad->k, ad->k);
smc_sums_partial (&tltb3[0][j], &ad->beta[0][j], ad->n, ad->k, ad->k);
for (uint16_t i = 0; i < ad->n; i++)
{
gcry_mpi_ec_sub (tlta3[i][j], tlta3[i][j], ad->alpha[i][j], ec_ctx);
gcry_mpi_ec_sub (tltb3[i][j], tltb3[i][j], ad->beta[i][j], ec_ctx);
}
brandt_assert (!ec_point_cmp (ec_zero, tlta3[0][j]));
brandt_assert (!ec_point_cmp (ec_zero, tltb3[0][j]));
}
for (uint16_t i = 0; i < ad->n; i++)
{
for (uint16_t j = 0; j < ad->k; j++)
{
gamma = (struct ec_mpi *)cur;
delta = &((struct ec_mpi *)cur)[1];
proof2 = (struct proof_2dle *)(cur + 2 * sizeof (struct ec_mpi));
/* compute inner gamma */
gcry_mpi_ec_add (tmpa, tlta1[j], tlta2[i][j], ec_ctx);
gcry_mpi_ec_add (tmpa, tmpa, tlta3[i][j], ec_ctx);
/* compute inner delta */
gcry_mpi_ec_add (tmpb, tltb1[j], tltb2[i][j], ec_ctx);
gcry_mpi_ec_add (tmpb, tmpb, tltb3[i][j], ec_ctx);
/* copy unmasked outcome to all other bidder layers so they don't
* have to be recomputed to check the ZK proof_2dle's from other
* bidders when receiving their outcome messages */
for (uint16_t a = 0; a < ad->n; a++)
{
ec_point_copy (ad->gamma3[a][i][j], tmpa);
ec_point_copy (ad->delta3[a][i][j], tmpb);
}
/* apply random masking for losing bidders */
smc_zkp_2dle (ad->gamma3[ad->i][i][j],
ad->delta3[ad->i][i][j],
tmpa,
tmpb,
NULL,
proof2);
ec_point_serialize (gamma, ad->gamma3[ad->i][i][j]);
ec_point_serialize (delta, ad->delta3[ad->i][i][j]);
cur += sizeof (*gamma) + sizeof (*delta) + sizeof (*proof2);
}
}
gcry_mpi_point_release (tmpa);
gcry_mpi_point_release (tmpb);
smc_free1 (tlta1, ad->k);
smc_free1 (tltb1, ad->k);
smc_free2 (tlta2, ad->n, ad->k);
smc_free2 (tltb2, ad->n, ad->k);
smc_free2 (tlta3, ad->n, ad->k);
smc_free2 (tltb3, ad->n, ad->k);
return ret;
}
int
fp_priv_recv_outcome (struct BRANDT_Auction *ad,
const unsigned char *buf,
size_t buflen,
uint16_t sender)
{
int ret = 0;
const unsigned char *cur = buf;
struct proof_2dle *proof2;
gcry_mpi_point_t gamma = gcry_mpi_point_new (0);
gcry_mpi_point_t delta = gcry_mpi_point_new (0);
brandt_assert (ad && buf);
if (buflen != (ad->n * ad->k *
(2 * sizeof (struct ec_mpi) + sizeof (*proof2))))
{
weprintf ("wrong size of received outcome");
goto quit;
}
for (uint16_t i = 0; i < ad->n; i++)
{
for (uint16_t j = 0; j < ad->k; j++)
{
ec_point_parse (gamma, (struct ec_mpi *)cur);
ec_point_parse (delta, &((struct ec_mpi *)cur)[1]);
proof2 = (struct proof_2dle *)(cur + 2 * sizeof (struct ec_mpi));
if (smc_zkp_2dle_check (gamma,
delta,
ad->gamma3[sender][i][j],
ad->delta3[sender][i][j],
proof2))
{
weprintf ("wrong zkp2 for gamma, delta received");
goto quit;
}
ec_point_copy (ad->gamma3[sender][i][j], gamma);
ec_point_copy (ad->delta3[sender][i][j], delta);
cur += 2 * sizeof (struct ec_mpi) + sizeof (*proof2);
}
}
ret = 1;
quit:
gcry_mpi_point_release (gamma);
gcry_mpi_point_release (delta);
return ret;
}
/**
* fp_priv_decrypt_outcome decrypts the own shares of the outcome and packs them
* into a message buffer together with proofs of correctnes.
*
* @param[in] ad Pointer to the BRANDT_Auction struct to operate on
* @param[out] buflen Size of the returned message buffer in bytes
* @return A buffer containing the own share of the decrypted outcome
* which needs to be broadcast
*/
unsigned char *
fp_priv_decrypt_outcome (struct BRANDT_Auction *ad, size_t *buflen)
{
unsigned char *ret;
unsigned char *cur;
struct msg_head *head;
gcry_mpi_point_t tmp = gcry_mpi_point_new (0);
struct ec_mpi *phi;
struct proof_2dle *proof2;
brandt_assert (ad && buflen);
*buflen = (sizeof (*head) +
ad->n * ad->k * (sizeof (*phi) + sizeof (*proof2)));
ret = GNUNET_new_array (*buflen, unsigned char);
if (NULL == (ad->phi3 = smc_init3 (ad->n, ad->n, ad->k)))
{
weprintf ("unable to alloc memory for first price outcome decryption");
return NULL;
}
head = (struct msg_head *)ret;
head->prot_version = htonl (0);
head->msg_type = htonl (msg_decrypt);
cur = ret + sizeof (*head);
for (uint16_t i = 0; i < ad->n; i++)
{
for (uint16_t j = 0; j < ad->k; j++)
{
phi = (struct ec_mpi *)cur;
proof2 = (struct proof_2dle *)(cur + sizeof (*phi));
smc_sum (tmp, &ad->delta3[0][i][j], ad->n, ad->n * ad->k);
/* copy still encrypted outcome to all other bidder layers so they
* don't have to be recomputed to check the ZK proof_2dle's from
* other bidders when receiving their outcome decryption messages */
for (uint16_t a = 0; a < ad->n; a++)
ec_point_copy (ad->phi3[a][i][j], tmp);
/* decrypt outcome component and prove the correct key was used */
smc_zkp_2dle (ad->phi3[ad->i][i][j],
NULL,
tmp,
ec_gen,
ad->x,
proof2);
ec_point_serialize (phi, ad->phi3[ad->i][i][j]);
cur += sizeof (*phi) + sizeof (*proof2);
}
}
gcry_mpi_point_release (tmp);
return ret;
}
int
fp_priv_recv_decryption (struct BRANDT_Auction *ad,
const unsigned char *buf,
size_t buflen,
uint16_t sender)
{
int ret = 0;
const unsigned char *cur = buf;
struct proof_2dle *proof2;
gcry_mpi_point_t phi = gcry_mpi_point_new (0);
brandt_assert (ad && buf);
if (buflen != (ad->n * ad->k * (sizeof (struct ec_mpi) + sizeof (*proof2))))
{
weprintf ("wrong size of received outcome decryption");
goto quit;
}
for (uint16_t i = 0; i < ad->n; i++)
{
for (uint16_t j = 0; j < ad->k; j++)
{
ec_point_parse (phi, (struct ec_mpi *)cur);
proof2 = (struct proof_2dle *)(cur + sizeof (struct ec_mpi));
if (smc_zkp_2dle_check (phi,
ad->y[sender],
ad->phi3[sender][i][j],
ec_gen,
proof2))
{
weprintf ("wrong zkp2 for phi, y received");
goto quit;
}
ec_point_copy (ad->phi3[sender][i][j], phi);
cur += sizeof (struct ec_mpi) + sizeof (*proof2);
}
}
ret = 1;
quit:
gcry_mpi_point_release (phi);
return ret;
}
int32_t
fp_priv_determine_outcome (struct BRANDT_Auction *ad)
{
int32_t ret = -1;
gcry_mpi_point_t sum_gamma = gcry_mpi_point_new (0);
gcry_mpi_point_t sum_phi = gcry_mpi_point_new (0);
brandt_assert (ad);
for (uint16_t j = 0; j < ad->k; j++)
{
smc_sum (sum_gamma, &ad->gamma3[0][ad->i][j], ad->n, ad->n * ad->k);
smc_sum (sum_phi, &ad->phi3[0][ad->i][j], ad->n, ad->n * ad->k);
gcry_mpi_ec_sub (sum_gamma, sum_gamma, sum_phi, ec_ctx);
if (!ec_point_cmp (sum_gamma, ec_zero))
{
if (-1 != ret)
{
weprintf ("multiple winning prices detected");
return -1;
}
ret = j;
}
}
gcry_mpi_point_release (sum_gamma);
gcry_mpi_point_release (sum_phi);
return ret;
}
/**
* smc_zkp_dl creates a proof of knowledge of @a x with \f$v = xg\f$ where
* \f$g\f$ is the base point on Ed25519.
*
* @param[out] v output point. Must be known to the verifier.
* @param[in] x private key. Knowledge of this number is certified in the proof
* @param[out] proof pointer where to save the output proof structure. Must be
* shared with the verifier.
*/
void
smc_zkp_dl (gcry_mpi_point_t v,
const gcry_mpi_t x,
struct proof_dl *proof)
{
struct zkp_challenge_dl challenge;
gcry_mpi_point_t a = gcry_mpi_point_new (0);
gcry_mpi_t r = gcry_mpi_new (256);
gcry_mpi_t c;
gcry_mpi_t z = gcry_mpi_new (256);
/* v = xg */
gcry_mpi_ec_mul (v, x, ec_gen, ec_ctx);
/* a = zg */
ec_keypair_create (a, z);
/* compute challenge c */
ec_point_serialize (&challenge.g, ec_gen);
ec_point_serialize (&challenge.v, v);
ec_point_serialize (&challenge.a, a);
GNUNET_CRYPTO_kdf_mod_mpi (&c,
ec_n,
NULL,
0,
&challenge,
sizeof (challenge),
"libbrandt zkp dl");
/* r = z + cx */
gcry_mpi_mulm (r, c, x, ec_n);
gcry_mpi_addm (r, r, z, ec_n);
ec_point_serialize (&proof->a, a);
mpi_serialize (&proof->r, r);
gcry_mpi_point_release (a);
gcry_mpi_release (r);
gcry_mpi_release (c);
gcry_mpi_release (z);
}
/**
* smc_zkp_dl_check verifies a proof of knowledge of \f$x = ECDL_g(v)\f$ where
* \f$g\f$ is the base point on Ed25519.
*
* @param[in] v input point. Received from the prover.
* @param[in] proof pointer to the proof structure. Received from the prover.
* @return 0 if the proof is correct, something else otherwise
*/
int
smc_zkp_dl_check (const gcry_mpi_point_t v,
const struct proof_dl *proof)
{
int ret;
struct zkp_challenge_dl challenge;
gcry_mpi_point_t a = gcry_mpi_point_new (0);
gcry_mpi_t r = gcry_mpi_new (256);
gcry_mpi_t c;
gcry_mpi_point_t left = gcry_mpi_point_new (0);
gcry_mpi_point_t right = gcry_mpi_point_new (0);
ec_point_parse (a, &proof->a);
mpi_parse (r, &proof->r);
/* compute challenge c */
ec_point_serialize (&challenge.g, ec_gen);
ec_point_serialize (&challenge.v, v);
ec_point_serialize (&challenge.a, a);
GNUNET_CRYPTO_kdf_mod_mpi (&c,
ec_n,
NULL,
0,
&challenge,
sizeof (challenge),
"libbrandt zkp dl");
/* rg =? a + cv */
gcry_mpi_ec_mul (left, r, ec_gen, ec_ctx);
gcry_mpi_ec_mul (right, c, v, ec_ctx);
gcry_mpi_ec_add (right, a, right, ec_ctx);
ret = ec_point_cmp (left, right);
gcry_mpi_point_release (a);
gcry_mpi_release (r);
gcry_mpi_release (c);
gcry_mpi_point_release (left);
gcry_mpi_point_release (right);
return ret;
}
/**
* smc_zkp_2dle creates a proof that two ECDLs are equal without revealing the
* ECDL. \f$v=xg_1, w=xg_2\f$ are calculated as well and can be returned to the
* caller if needed.
*
* @param[out] v first output point. May be NULL if not needed by the caller.
* Must be known to the verifier.
* @param[out] w second output point. May be NULL if not needed by the caller.
* Must be known to the verifier.
* @param[in] g1 first base point. Must be known to the verifier.
* @param[in] g2 second base point. Must be known to the verifier.
* @param[in] x private number to prove knowledge of. May be NULL if not used by
* the caller.
* @param[out] proof pointer where to save the output proof structure. Must be
* shared with the verifier.
*/
void
smc_zkp_2dle (gcry_mpi_point_t v,
gcry_mpi_point_t w,
const gcry_mpi_point_t g1,
const gcry_mpi_point_t g2,
const gcry_mpi_t x,
struct proof_2dle *proof)
{
struct zkp_challenge_2dle challenge;
gcry_mpi_point_t rv;
gcry_mpi_point_t rw;
gcry_mpi_t rx;
gcry_mpi_point_t a = gcry_mpi_point_new (0);
gcry_mpi_point_t b = gcry_mpi_point_new (0);
gcry_mpi_t r = gcry_mpi_new (256);
gcry_mpi_t c;
gcry_mpi_t z = gcry_mpi_new (256);
rv = (NULL == v) ? gcry_mpi_point_new (0) : v;
rw = (NULL == w) ? gcry_mpi_point_new (0) : w;
rx = (NULL == x) ? gcry_mpi_new (256) : x;
if (NULL == x)
ec_skey_create (rx);
/* v = x*g1 */
gcry_mpi_ec_mul (rv, rx, g1, ec_ctx);
/* w = x*g2 */
gcry_mpi_ec_mul (rw, rx, g2, ec_ctx);
/* a = z*g1 */
ec_keypair_create_base (a, z, g1);
/* b = z*g2 */
gcry_mpi_ec_mul (b, z, g2, ec_ctx);
/* compute challenge c */
ec_point_serialize (&challenge.g1, g1);
ec_point_serialize (&challenge.g2, g2);
ec_point_serialize (&challenge.v, rv);
ec_point_serialize (&challenge.w, rw);
ec_point_serialize (&challenge.a, a);
ec_point_serialize (&challenge.b, b);
GNUNET_CRYPTO_kdf_mod_mpi (&c,
ec_n,
NULL,
0,
&challenge,
sizeof (challenge),
"libbrandt zkp 2dle");
/* r = z + cx */
gcry_mpi_mulm (r, c, rx, ec_n);
gcry_mpi_addm (r, r, z, ec_n);
mpi_serialize (&proof->r, r);
ec_point_serialize (&proof->a, a);
ec_point_serialize (&proof->b, b);
if (NULL == v)
gcry_mpi_point_release (rv);
if (NULL == w)
gcry_mpi_point_release (rw);
if (NULL == x)
gcry_mpi_release (rx);
gcry_mpi_point_release (a);
gcry_mpi_point_release (b);
gcry_mpi_release (r);
gcry_mpi_release (c);
gcry_mpi_release (z);
}
/**
* smc_zkp_2dle_check verifies a proof of knowledge of \f$x\f$ with \f$v=xg_1\f$
* and \f$w=xg_2\f$.
*
* @param[in] v first input point.
* @param[in] w second input point.
* @param[in] g1 first base point.
* @param[in] g2 second base point.
* @param[in] proof pointer to the proof structure. Received from the prover.
* @return 0 if the proof is correct, something else otherwise
*/
int
smc_zkp_2dle_check (const gcry_mpi_point_t v,
const gcry_mpi_point_t w,
const gcry_mpi_point_t g1,
const gcry_mpi_point_t g2,
const struct proof_2dle *proof)
{
int ret;
struct zkp_challenge_2dle challenge;
gcry_mpi_point_t a = gcry_mpi_point_new (0);
gcry_mpi_point_t b = gcry_mpi_point_new (0);
gcry_mpi_t r = gcry_mpi_new (256);
gcry_mpi_t c;
gcry_mpi_point_t left = gcry_mpi_point_new (0);
gcry_mpi_point_t right = gcry_mpi_point_new (0);
mpi_parse (r, &proof->r);
ec_point_parse (a, &proof->a);
ec_point_parse (b, &proof->b);
/* compute challenge c */
ec_point_serialize (&challenge.g1, g1);
ec_point_serialize (&challenge.g2, g2);
ec_point_serialize (&challenge.v, v);
ec_point_serialize (&challenge.w, w);
ec_point_serialize (&challenge.a, a);
ec_point_serialize (&challenge.b, b);
GNUNET_CRYPTO_kdf_mod_mpi (&c,
ec_n,
NULL,
0,
&challenge,
sizeof (challenge),
"libbrandt zkp 2dle");
/* r*g1 =? a + cv */
gcry_mpi_ec_mul (left, r, g1, ec_ctx);
gcry_mpi_ec_mul (right, c, v, ec_ctx);
gcry_mpi_ec_add (right, a, right, ec_ctx);
ret = ec_point_cmp (left, right);
/* r*g2 =? b + cw */
gcry_mpi_ec_mul (left, r, g2, ec_ctx);
gcry_mpi_ec_mul (right, c, w, ec_ctx);
gcry_mpi_ec_add (right, b, right, ec_ctx);
ret |= ec_point_cmp (left, right);
gcry_mpi_point_release (a);
gcry_mpi_point_release (b);
gcry_mpi_release (r);
gcry_mpi_release (c);
gcry_mpi_point_release (left);
gcry_mpi_point_release (right);
return ret;
}
/**
* smc_zkp_0og encrypts one of two values and creates a proof that the
* ciphertext decrypts to either one of those two values without revealing which
* one was encrypted. The two values are the zero point or the base point of the
* Ed25519 curve. Encryption is done via ElGamal: \f$(\alpha,\beta)=(m+ry,rg)\f$
* where \f$m\f$ is the value to encrypt, \f$y\f$ is the public key and \f$g\f$
* is the base point. The nonce \f$r\f$ is generated as well and can be returned
* to the caller if he needs it (e.g. for another proof).
*
* @param[in] m_is_gen if true, the base point is encrypted, else the zero point
* is encrypted.
* @param[in] y public key to use for encryption.
* @param[out] r random number used for encryption. May be NULL if caller
* doesn't need it.
* @param[out] alpha first part of the ciphertext output
* @param[out] beta second part of the ciphertext output
* @param[out] proof pointer where to save the output proof structure. Must be
* shared with the verifier.
*/
void
smc_zkp_0og (int m_is_gen,
const gcry_mpi_point_t y,
gcry_mpi_t r,
gcry_mpi_point_t alpha,
gcry_mpi_point_t beta,
struct proof_0og *proof)
{
struct zkp_challenge_0og challenge;
gcry_mpi_point_t a1 = gcry_mpi_point_new (0);
gcry_mpi_point_t a2 = gcry_mpi_point_new (0);
gcry_mpi_point_t b1 = gcry_mpi_point_new (0);
gcry_mpi_point_t b2 = gcry_mpi_point_new (0);
gcry_mpi_t d1 = gcry_mpi_new (256);
gcry_mpi_t d2 = gcry_mpi_new (256);
gcry_mpi_t r1 = gcry_mpi_new (256);
gcry_mpi_t r2 = gcry_mpi_new (256);
gcry_mpi_t c;
gcry_mpi_t rr;
gcry_mpi_t w = gcry_mpi_new (256);
rr = (NULL == r) ? gcry_mpi_new (256) : r;
/* beta = r*g */
ec_keypair_create (beta, rr);
gcry_mpi_mod (rr, rr, ec_n);
/* alpha = m + r*y */
gcry_mpi_ec_mul (alpha, rr, y, ec_ctx);
gcry_mpi_ec_add (alpha, m_is_gen ? ec_gen : ec_zero, alpha, ec_ctx);
if (!m_is_gen)
{ /* m == 0 */
ec_keypair_create_base (a1, d1, beta);
gcry_mpi_mod (d1, d1, ec_n);
ec_keypair_create_base (b1, r1, y);
gcry_mpi_mod (r1, r1, ec_n);
/* a1 = r1*g + d1*beta */
gcry_mpi_ec_mul (a2, r1, ec_gen, ec_ctx);
gcry_mpi_ec_add (a1, a2, a1, ec_ctx);
/* b1 = r1*y + d1*(alpha-g) */
gcry_mpi_ec_sub (b2, alpha, ec_gen, ec_ctx);
gcry_mpi_ec_mul (a2, d1, b2, ec_ctx);
gcry_mpi_ec_add (b1, b1, a2, ec_ctx);
/* a2 = w * g */
ec_keypair_create_base (a2, w, ec_gen);
gcry_mpi_mod (w, w, ec_n);
/* b2 = w * y */
gcry_mpi_ec_mul (b2, w, y, ec_ctx);
}
else
{ /* m == g */
ec_keypair_create_base (a2, d2, beta);
gcry_mpi_mod (d2, d2, ec_n);
ec_keypair_create_base (b2, r2, y);
gcry_mpi_mod (r2, r2, ec_n);
/* a2 = r2*g + d2*beta */
gcry_mpi_ec_mul (a1, r2, ec_gen, ec_ctx);
gcry_mpi_ec_add (a2, a1, a2, ec_ctx);
/* b2 = r2*y + d2*(alpha-0) */
/* useless subtraction to have same amount of operations as in m == 0 */
gcry_mpi_ec_sub (b1, alpha, ec_zero, ec_ctx);
gcry_mpi_ec_mul (a1, d2, b1, ec_ctx);
gcry_mpi_ec_add (b2, b2, a1, ec_ctx);
/* a1 = w * g */
ec_keypair_create_base (a1, w, ec_gen);
gcry_mpi_mod (w, w, ec_n);
/* b1 = w * y */
gcry_mpi_ec_mul (b1, w, y, ec_ctx);
}
/* compute challenge c */
ec_point_serialize (&challenge.g, ec_gen);
ec_point_serialize (&challenge.alpha, alpha);
ec_point_serialize (&challenge.beta, beta);
ec_point_serialize (&challenge.a1, a1);
ec_point_serialize (&challenge.a2, a2);
ec_point_serialize (&challenge.b1, b1);
ec_point_serialize (&challenge.b2, b2);
GNUNET_CRYPTO_kdf_mod_mpi (&c,
ec_n,
NULL,
0,
&challenge,
sizeof (challenge),
"libbrandt zkp 0og");
if (!m_is_gen)
{ /* m == 0 */
/* d2 = c - d1 */
gcry_mpi_subm (d2, c, d1, ec_n);
/* r2 = w - r*d2 */
gcry_mpi_mulm (r2, rr, d2, ec_n);
gcry_mpi_subm (r2, w, r2, ec_n);
}
else
{ /* m == g */
/* d1 = c - d2 */
gcry_mpi_subm (d1, c, d2, ec_n);
/* r1 = w - r*d1 */
gcry_mpi_mulm (r1, rr, d1, ec_n);
gcry_mpi_subm (r1, w, r1, ec_n);
}
ec_point_serialize (&proof->a1, a1);
ec_point_serialize (&proof->a2, a2);
ec_point_serialize (&proof->b1, b1);
ec_point_serialize (&proof->b2, b2);
mpi_serialize (&proof->d1, d1);
mpi_serialize (&proof->d2, d2);
mpi_serialize (&proof->r1, r1);
mpi_serialize (&proof->r2, r2);
gcry_mpi_point_release (a1);
gcry_mpi_point_release (a2);
gcry_mpi_point_release (b1);
gcry_mpi_point_release (b2);
gcry_mpi_release (d1);
gcry_mpi_release (d2);
gcry_mpi_release (r1);
gcry_mpi_release (r2);
gcry_mpi_release (c);
if (NULL == r)
gcry_mpi_release (rr);
gcry_mpi_release (w);
}
/**
* smc_zkp_0og_check verifies a proof that \f$(\alpha,\beta\f$ decrypts either
* to the base point \f$g\f$ or the zero point.
*
* @param[in] y the public key used for encryption
* @param[in] alpha first part of the ciphertext
* @param[in] beta second part of the ciphertext
* @param[in] proof pointer to the proof structure. Received from the prover.
* @return 0 if the proof is correct, something else otherwise
*/
int
smc_zkp_0og_check (const gcry_mpi_point_t y,
const gcry_mpi_point_t alpha,
const gcry_mpi_point_t beta,
const struct proof_0og *proof)
{
int ret;
struct zkp_challenge_0og challenge;
gcry_mpi_point_t a1 = gcry_mpi_point_new (0);
gcry_mpi_point_t a2 = gcry_mpi_point_new (0);
gcry_mpi_point_t b1 = gcry_mpi_point_new (0);
gcry_mpi_point_t b2 = gcry_mpi_point_new (0);
gcry_mpi_t d1 = gcry_mpi_new (256);
gcry_mpi_t d2 = gcry_mpi_new (256);
gcry_mpi_t r1 = gcry_mpi_new (256);
gcry_mpi_t r2 = gcry_mpi_new (256);
gcry_mpi_t c;
gcry_mpi_t sum = gcry_mpi_new (256);
gcry_mpi_point_t right = gcry_mpi_point_new (0);
gcry_mpi_point_t tmp = gcry_mpi_point_new (0);
ec_point_parse (a1, &proof->a1);
ec_point_parse (a2, &proof->a2);
ec_point_parse (b1, &proof->b1);
ec_point_parse (b2, &proof->b2);
mpi_parse (d1, &proof->d1);
mpi_parse (d2, &proof->d2);
mpi_parse (r1, &proof->r1);
mpi_parse (r2, &proof->r2);
/* compute challenge c */
ec_point_serialize (&challenge.g, ec_gen);
ec_point_serialize (&challenge.alpha, alpha);
ec_point_serialize (&challenge.beta, beta);
ec_point_serialize (&challenge.a1, a1);
ec_point_serialize (&challenge.a2, a2);
ec_point_serialize (&challenge.b1, b1);
ec_point_serialize (&challenge.b2, b2);
GNUNET_CRYPTO_kdf_mod_mpi (&c,
ec_n,
NULL,
0,
&challenge,
sizeof (challenge),
"libbrandt zkp 0og");
/* c == d1 + d2 */
gcry_mpi_addm (sum, d1, d2, ec_n);
ret = gcry_mpi_cmp (c, sum);
/* a1 == r1*g + d1*beta */
gcry_mpi_ec_mul (tmp, r1, ec_gen, ec_ctx);
gcry_mpi_ec_mul (right, d1, beta, ec_ctx);
gcry_mpi_ec_add (right, tmp, right, ec_ctx);
ret |= ec_point_cmp (a1, right) << 1;
/* b1 == r1*y + d1*(alpha-g) */
gcry_mpi_ec_sub (right, alpha, ec_gen, ec_ctx);
gcry_mpi_ec_mul (tmp, d1, right, ec_ctx);
gcry_mpi_ec_mul (right, r1, y, ec_ctx);
gcry_mpi_ec_add (right, right, tmp, ec_ctx);
ret |= ec_point_cmp (b1, right) << 2;
/* a2 == r2*g + d2*beta */
gcry_mpi_ec_mul (tmp, d2, beta, ec_ctx);
gcry_mpi_ec_mul (right, r2, ec_gen, ec_ctx);
gcry_mpi_ec_add (right, right, tmp, ec_ctx);
ret |= ec_point_cmp (a2, right) << 3;
/* b2 == r2*y + d2*alpha */
gcry_mpi_ec_mul (tmp, d2, alpha, ec_ctx);
gcry_mpi_ec_mul (right, r2, y, ec_ctx);
gcry_mpi_ec_add (right, right, tmp, ec_ctx);
ret |= ec_point_cmp (b2, right) << 4;
gcry_mpi_point_release (a1);
gcry_mpi_point_release (a2);
gcry_mpi_point_release (b1);
gcry_mpi_point_release (b2);
gcry_mpi_release (d1);
gcry_mpi_release (d2);
gcry_mpi_release (r1);
gcry_mpi_release (r2);
gcry_mpi_release (c);
gcry_mpi_release (sum);
gcry_mpi_point_release (right);
gcry_mpi_point_release (tmp);
if (ret)
weprintf ("ret: 0x%x", ret);
return ret;
}