src/secretsharing/gnunet-service-secretsharing.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2013 GNUnet e.V.
   4
   5      GNUnet is free software: you can redistribute it and/or modify it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      Affero General Public License for more details.
  14
  15      You should have received a copy of the GNU Affero General Public License
  16      along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19 /**
  20  * @file secretsharing/gnunet-service-secretsharing.c
  21  * @brief secret sharing service
  22  * @author Florian Dold
  23  */
  24 #include "platform.h"
  25 #include "gnunet_util_lib.h"
  26 #include "gnunet_time_lib.h"
  27 #include "gnunet_signatures.h"
  28 #include "gnunet_consensus_service.h"
  29 #include "secretsharing.h"
  30 #include "secretsharing_protocol.h"
  31 #include <gcrypt.h>
  32
  33
  34 #define EXTRA_CHECKS 1
  35
  36
  37 /**
  38  * Info about a peer in a key generation session.
  39  */
  40 struct KeygenPeerInfo
  41 {
  42   /**
  43    * Peer identity of the peer.
  44    */
  45   struct GNUNET_PeerIdentity peer;
  46
  47   /**
  48    * The peer's paillier public key.
  49    * Freshly generated for each keygen session.
  50    */
  51   struct GNUNET_CRYPTO_PaillierPublicKey paillier_public_key;
  52
  53   /**
  54    * The peer's commitment to his presecret.
  55    */
  56   gcry_mpi_t presecret_commitment;
  57
  58   /**
  59    * Commitment to the preshare that is
  60    * intended for our peer.
  61    */
  62   gcry_mpi_t preshare_commitment;
  63
  64   /**
  65    * Sigma (exponentiated share) for this peer.
  66    */
  67   gcry_mpi_t sigma;
  68
  69   /**
  70    * Did we successfully receive the round1 element
  71    * of the peer?
  72    */
  73   int round1_valid;
  74
  75   /**
  76    * Did we successfully receive the round2 element
  77    * of the peer?
  78    */
  79   int round2_valid;
  80 };
  81
  82
  83 /**
  84  * Information about a peer in a decrypt session.
  85  */
  86 struct DecryptPeerInfo
  87 {
  88   /**
  89    * Identity of the peer.
  90    */
  91   struct GNUNET_PeerIdentity peer;
  92
  93   /**
  94    * Original index in the key generation round.
  95    * Necessary for computing the lagrange coefficients.
  96    */
  97   unsigned int original_index;
  98
  99   /**
 100    * Set to the partial decryption of
 101    * this peer, or NULL if we did not
 102    * receive a partial decryption from this
 103    * peer or the zero knowledge proof failed.
 104    */
 105   gcry_mpi_t partial_decryption;
 106 };
 107
 108
 109 /**
 110  * State we keep per client.
 111  */
 112 struct ClientState;
 113
 114
 115 /**
 116  * Session to establish a threshold-shared secret.
 117  */
 118 struct KeygenSession
 119 {
 120
 121   /**
 122    * Current consensus, used for both DKG rounds.
 123    */
 124   struct GNUNET_CONSENSUS_Handle *consensus;
 125
 126   /**
 127    * Which client is this for?
 128    */
 129   struct ClientState *cs;
 130
 131   /**
 132    * Randomly generated coefficients of the polynomial for sharing our
 133    * pre-secret, where 'preshares[0]' is our pre-secret.  Contains 'threshold'
 134    * elements, thus represents a polynomial of degree 'threshold-1', which can
 135    * be interpolated with 'threshold' data points.
 136    *
 137    * The pre-secret-shares 'i=1,...,num_peers' are given by evaluating this
 138    * polyomial at 'i' for share i.
 139    */
 140   gcry_mpi_t *presecret_polynomial;
 141
 142   /**
 143    * Minimum number of shares required to restore the secret.
 144    * Also the number of coefficients for the polynomial representing
 145    * the sharing.  Obviously, the polynomial then has degree threshold-1.
 146    */
 147   unsigned int threshold;
 148
 149   /**
 150    * Total number of peers.
 151    */
 152   unsigned int num_peers;
 153
 154   /**
 155    * Index of the local peer.
 156    */
 157   unsigned int local_peer;
 158
 159   /**
 160    * Information about all participating peers.
 161    * Array of size 'num_peers'.
 162    */
 163   struct KeygenPeerInfo *info;
 164
 165   /**
 166    * List of all peers involved in the secret sharing session.
 167    */
 168   struct GNUNET_PeerIdentity *peers;
 169
 170   /**
 171    * Identifier for this session.
 172    */
 173   struct GNUNET_HashCode session_id;
 174
 175   /**
 176    * Paillier private key of our peer.
 177    */
 178   struct GNUNET_CRYPTO_PaillierPrivateKey paillier_private_key;
 179
 180   /**
 181    * When would we like the key to be established?
 182    */
 183   struct GNUNET_TIME_Absolute deadline;
 184
 185   /**
 186    * When does the DKG start?  Necessary to compute fractions of the
 187    * operation's desired time interval.
 188    */
 189   struct GNUNET_TIME_Absolute start_time;
 190
 191   /**
 192    * Index of the local peer in the ordered list
 193    * of peers in the session.
 194    */
 195   unsigned int local_peer_idx;
 196
 197   /**
 198    * Share of our peer.  Once preshares from other peers are received, they
 199    * will be added to 'my'share.
 200    */
 201   gcry_mpi_t my_share;
 202
 203   /**
 204    * Public key, will be updated when a round2 element arrives.
 205    */
 206   gcry_mpi_t public_key;
 207 };
 208
 209
 210 /**
 211  * Session to cooperatively decrypt a value.
 212  */
 213 struct DecryptSession
 214 {
 215
 216   /**
 217    * Handle to the consensus over partial decryptions.
 218    */
 219   struct GNUNET_CONSENSUS_Handle *consensus;
 220
 221   /**
 222    * Which client is this for?
 223    */
 224   struct ClientState *cs;
 225
 226   /**
 227    * When should we start communicating for decryption?
 228    */
 229   struct GNUNET_TIME_Absolute start;
 230
 231   /**
 232    * When would we like the ciphertext to be
 233    * decrypted?
 234    */
 235   struct GNUNET_TIME_Absolute deadline;
 236
 237   /**
 238    * Ciphertext we want to decrypt.
 239    */
 240   struct GNUNET_SECRETSHARING_Ciphertext ciphertext;
 241
 242   /**
 243    * Share of the local peer.
 244    * Containts other important information, such as
 245    * the list of other peers.
 246    */
 247   struct GNUNET_SECRETSHARING_Share *share;
 248
 249   /**
 250    * State information about other peers.
 251    */
 252   struct DecryptPeerInfo *info;
 253 };
 254
 255
 256 /**
 257  * State we keep per client.
 258  */
 259 struct ClientState
 260 {
 261   /**
 262    * Decrypt session of the client, if any.
 263    */
 264   struct DecryptSession *decrypt_session;
 265
 266   /**
 267    * Keygen session of the client, if any.
 268    */
 269   struct KeygenSession *keygen_session;
 270
 271   /**
 272    * Client this is about.
 273    */
 274   struct GNUNET_SERVICE_Client *client;
 275
 276   /**
 277    * MQ to talk to @a client.
 278    */
 279   struct GNUNET_MQ_Handle *mq;
 280
 281 };
 282
 283
 284 /**
 285  * The ElGamal prime field order as libgcrypt mpi.
 286  * Initialized in #init_crypto_constants.
 287  */
 288 static gcry_mpi_t elgamal_q;
 289
 290 /**
 291  * Modulus of the prime field used for ElGamal.
 292  * Initialized in #init_crypto_constants.
 293  */
 294 static gcry_mpi_t elgamal_p;
 295
 296 /**
 297  * Generator for prime field of order 'elgamal_q'.
 298  * Initialized in #init_crypto_constants.
 299  */
 300 static gcry_mpi_t elgamal_g;
 301
 302 /**
 303  * Peer that runs this service.
 304  */
 305 static struct GNUNET_PeerIdentity my_peer;
 306
 307 /**
 308  * Peer that runs this service.
 309  */
 310 static struct GNUNET_CRYPTO_EddsaPrivateKey *my_peer_private_key;
 311
 312 /**
 313  * Configuration of this service.
 314  */
 315 static const struct GNUNET_CONFIGURATION_Handle *cfg;
 316
 317
 318 /**
 319  * Get the peer info belonging to a peer identity in a keygen session.
 320  *
 321  * @param ks The keygen session.
 322  * @param peer The peer identity.
 323  * @return The Keygen peer info, or NULL if the peer could not be found.
 324  */
 325 static struct KeygenPeerInfo *
 326 get_keygen_peer_info (const struct KeygenSession *ks,
 327                       const struct GNUNET_PeerIdentity *peer)
 328 {
 329   unsigned int i;
 330   for (i = 0; i < ks->num_peers; i++)
 331     if (0 == memcmp (peer, &ks->info[i].peer, sizeof (struct GNUNET_PeerIdentity)))
 332       return &ks->info[i];
 333   return NULL;
 334 }
 335
 336
 337 /**
 338  * Get the peer info belonging to a peer identity in a decrypt session.
 339  *
 340  * @param ds The decrypt session.
 341  * @param peer The peer identity.
 342  * @return The decrypt peer info, or NULL if the peer could not be found.
 343  */
 344 static struct DecryptPeerInfo *
 345 get_decrypt_peer_info (const struct DecryptSession *ds,
 346                        const struct GNUNET_PeerIdentity *peer)
 347 {
 348   unsigned int i;
 349   for (i = 0; i < ds->share->num_peers; i++)
 350     if (0 == memcmp (peer, &ds->info[i].peer, sizeof (struct GNUNET_PeerIdentity)))
 351       return &ds->info[i];
 352   return NULL;
 353 }
 354
 355
 356 /**
 357  * Interpolate between two points in time.
 358  *
 359  * @param start start time
 360  * @param end end time
 361  * @param num numerator of the scale factor
 362  * @param denum denumerator of the scale factor
 363  */
 364 static struct GNUNET_TIME_Absolute
 365 time_between (struct GNUNET_TIME_Absolute start,
 366               struct GNUNET_TIME_Absolute end,
 367               int num, int denum)
 368 {
 369   struct GNUNET_TIME_Absolute result;
 370   uint64_t diff;
 371
 372   GNUNET_assert (start.abs_value_us <= end.abs_value_us);
 373   diff = end.abs_value_us - start.abs_value_us;
 374   result.abs_value_us = start.abs_value_us + ((diff * num) / denum);
 375
 376   return result;
 377 }
 378
 379
 380 /**
 381  * Compare two peer identities.  Indended to be used with qsort or bsearch.
 382  *
 383  * @param p1 Some peer identity.
 384  * @param p2 Some peer identity.
 385  * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
 386  */
 387 static int
 388 peer_id_cmp (const void *p1, const void *p2)
 389 {
 390   return memcmp (p1,
 391                  p2,
 392                  sizeof (struct GNUNET_PeerIdentity));
 393 }
 394
 395
 396 /**
 397  * Get the index of a peer in an array of peers
 398  *
 399  * @param haystack Array of peers.
 400  * @param n Size of @a haystack.
 401  * @param needle Peer to find
 402  * @return Index of @a needle in @a haystack, or -1 if peer
 403  *         is not in the list.
 404  */
 405 static int
 406 peer_find (const struct GNUNET_PeerIdentity *haystack, unsigned int n,
 407            const struct GNUNET_PeerIdentity *needle)
 408 {
 409   unsigned int i;
 410
 411   for (i = 0; i < n; i++)
 412     if (0 == memcmp (&haystack[i],
 413                      needle,
 414                      sizeof (struct GNUNET_PeerIdentity)))
 415       return i;
 416   return -1;
 417 }
 418
 419
 420 /**
 421  * Normalize the given list of peers, by including the local peer
 422  * (if it is missing) and sorting the peers by their identity.
 423  *
 424  * @param listed Peers in the unnormalized list.
 425  * @param num_listed Peers in the un-normalized list.
 426  * @param[out] num_normalized Number of peers in the normalized list.
 427  * @param[out] my_peer_idx Index of the local peer in the normalized list.
 428  * @return Normalized list, must be free'd by the caller.
 429  */
 430 static struct GNUNET_PeerIdentity *
 431 normalize_peers (struct GNUNET_PeerIdentity *listed,
 432                  unsigned int num_listed,
 433                  unsigned int *num_normalized,
 434                  unsigned int *my_peer_idx)
 435 {
 436   unsigned int local_peer_in_list;
 437   /* number of peers in the normalized list */
 438   unsigned int n;
 439   struct GNUNET_PeerIdentity *normalized;
 440
 441   local_peer_in_list = GNUNET_YES;
 442   n = num_listed;
 443   if (peer_find (listed, num_listed, &my_peer) < 0)
 444   {
 445     local_peer_in_list = GNUNET_NO;
 446     n += 1;
 447   }
 448
 449   normalized = GNUNET_new_array (n,
 450                                  struct GNUNET_PeerIdentity);
 451
 452   if (GNUNET_NO == local_peer_in_list)
 453     normalized[n - 1] = my_peer;
 454
 455   GNUNET_memcpy (normalized,
 456           listed,
 457           num_listed * sizeof (struct GNUNET_PeerIdentity));
 458   qsort (normalized,
 459          n,
 460          sizeof (struct GNUNET_PeerIdentity),
 461          &peer_id_cmp);
 462
 463   if (NULL != my_peer_idx)
 464     *my_peer_idx = peer_find (normalized, n, &my_peer);
 465   if (NULL != num_normalized)
 466     *num_normalized = n;
 467
 468   return normalized;
 469 }
 470
 471
 472 /**
 473  * Get a the j-th lagrange coefficient for a set of indices.
 474  *
 475  * @param[out] coeff the lagrange coefficient
 476  * @param j lagrange coefficient we want to compute
 477  * @param indices indices
 478  * @param num number of indices in @a indices
 479  */
 480 static void
 481 compute_lagrange_coefficient (gcry_mpi_t coeff, unsigned int j,
 482                               unsigned int *indices,
 483                               unsigned int num)
 484 {
 485   unsigned int i;
 486   /* numerator */
 487   gcry_mpi_t n;
 488   /* denominator */
 489   gcry_mpi_t d;
 490   /* temp value for l-j */
 491   gcry_mpi_t tmp;
 492
 493   GNUNET_assert (0 != coeff);
 494
 495   GNUNET_assert (0 != (n = gcry_mpi_new (0)));
 496   GNUNET_assert (0 != (d = gcry_mpi_new (0)));
 497   GNUNET_assert (0 != (tmp = gcry_mpi_new (0)));
 498
 499   gcry_mpi_set_ui (n, 1);
 500   gcry_mpi_set_ui (d, 1);
 501
 502   for (i = 0; i < num; i++)
 503   {
 504     unsigned int l = indices[i];
 505     if (l == j)
 506       continue;
 507     gcry_mpi_mul_ui (n, n, l + 1);
 508     // d <- d * (l-j)
 509     gcry_mpi_set_ui (tmp, l + 1);
 510     gcry_mpi_sub_ui (tmp, tmp, j + 1);
 511     gcry_mpi_mul (d, d, tmp);
 512   }
 513
 514   // gcry_mpi_invm does not like negative numbers ...
 515   gcry_mpi_mod (d, d, elgamal_q);
 516
 517   GNUNET_assert (gcry_mpi_cmp_ui (d, 0) > 0);
 518
 519   // now we do the actual division, with everything mod q, as we
 520   // are not operating on elements from <g>, but on exponents
 521   GNUNET_assert (0 != gcry_mpi_invm (d, d, elgamal_q));
 522
 523   gcry_mpi_mulm (coeff, n, d, elgamal_q);
 524
 525   gcry_mpi_release (n);
 526   gcry_mpi_release (d);
 527   gcry_mpi_release (tmp);
 528 }
 529
 530
 531 /**
 532  * Destroy a decrypt session, removing it from
 533  * the linked list of decrypt sessions.
 534  *
 535  * @param ds decrypt session to destroy
 536  */
 537 static void
 538 decrypt_session_destroy (struct DecryptSession *ds)
 539 {
 540   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 541               "destroying decrypt session\n");
 542   if (NULL != ds->cs)
 543   {
 544     ds->cs->decrypt_session = NULL;
 545     ds->cs = NULL;
 546   }
 547   if (NULL != ds->consensus)
 548   {
 549     GNUNET_CONSENSUS_destroy (ds->consensus);
 550     ds->consensus = NULL;
 551   }
 552
 553   if (NULL != ds->info)
 554   {
 555     for (unsigned int i = 0; i < ds->share->num_peers; i++)
 556     {
 557       if (NULL != ds->info[i].partial_decryption)
 558       {
 559         gcry_mpi_release (ds->info[i].partial_decryption);
 560         ds->info[i].partial_decryption = NULL;
 561       }
 562     }
 563     GNUNET_free (ds->info);
 564     ds->info = NULL;
 565   }
 566   if (NULL != ds->share)
 567   {
 568     GNUNET_SECRETSHARING_share_destroy (ds->share);
 569     ds->share = NULL;
 570   }
 571
 572   GNUNET_free (ds);
 573 }
 574
 575
 576 static void
 577 keygen_info_destroy (struct KeygenPeerInfo *info)
 578 {
 579   if (NULL != info->sigma)
 580   {
 581     gcry_mpi_release (info->sigma);
 582     info->sigma = NULL;
 583   }
 584   if (NULL != info->presecret_commitment)
 585   {
 586     gcry_mpi_release (info->presecret_commitment);
 587     info->presecret_commitment = NULL;
 588   }
 589   if (NULL != info->preshare_commitment)
 590   {
 591     gcry_mpi_release (info->preshare_commitment);
 592     info->preshare_commitment = NULL;
 593   }
 594 }
 595
 596
 597 static void
 598 keygen_session_destroy (struct KeygenSession *ks)
 599 {
 600   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 601               "destroying keygen session\n");
 602
 603   if (NULL != ks->cs)
 604   {
 605     ks->cs->keygen_session = NULL;
 606     ks->cs = NULL;
 607   }
 608   if (NULL != ks->info)
 609   {
 610     for (unsigned int i = 0; i < ks->num_peers; i++)
 611       keygen_info_destroy (&ks->info[i]);
 612     GNUNET_free (ks->info);
 613     ks->info = NULL;
 614   }
 615
 616   if (NULL != ks->consensus)
 617   {
 618     GNUNET_CONSENSUS_destroy (ks->consensus);
 619     ks->consensus = NULL;
 620   }
 621
 622   if (NULL != ks->presecret_polynomial)
 623   {
 624     for (unsigned int i = 0; i < ks->threshold; i++)
 625     {
 626       GNUNET_assert (NULL != ks->presecret_polynomial[i]);
 627       gcry_mpi_release (ks->presecret_polynomial[i]);
 628       ks->presecret_polynomial[i] = NULL;
 629     }
 630     GNUNET_free (ks->presecret_polynomial);
 631     ks->presecret_polynomial = NULL;
 632   }
 633   if (NULL != ks->my_share)
 634   {
 635     gcry_mpi_release (ks->my_share);
 636     ks->my_share = NULL;
 637   }
 638   if (NULL != ks->public_key)
 639   {
 640     gcry_mpi_release (ks->public_key);
 641     ks->public_key = NULL;
 642   }
 643   if (NULL != ks->peers)
 644   {
 645     GNUNET_free (ks->peers);
 646     ks->peers = NULL;
 647   }
 648   GNUNET_free (ks);
 649 }
 650
 651
 652 /**
 653  * Task run during shutdown.
 654  *
 655  * @param cls unused
 656  * @param tc unused
 657  */
 658 static void
 659 cleanup_task (void *cls)
 660 {
 661   /* Nothing to do! */
 662 }
 663
 664
 665
 666 /**
 667  * Generate the random coefficients of our pre-secret polynomial
 668  *
 669  * @param ks the session
 670  */
 671 static void
 672 generate_presecret_polynomial (struct KeygenSession *ks)
 673 {
 674   int i;
 675   gcry_mpi_t v;
 676
 677   GNUNET_assert (NULL == ks->presecret_polynomial);
 678   ks->presecret_polynomial = GNUNET_new_array (ks->threshold,
 679                                                gcry_mpi_t);
 680   for (i = 0; i < ks->threshold; i++)
 681   {
 682     v = ks->presecret_polynomial[i] = gcry_mpi_new (GNUNET_SECRETSHARING_ELGAMAL_BITS);
 683     GNUNET_assert (NULL != v);
 684     // Randomize v such that 0 < v < elgamal_q.
 685     // The '- 1' is necessary as bitlength(q) = bitlength(p) - 1.
 686     do
 687     {
 688       gcry_mpi_randomize (v, GNUNET_SECRETSHARING_ELGAMAL_BITS - 1, GCRY_WEAK_RANDOM);
 689     } while ((gcry_mpi_cmp_ui (v, 0) == 0) || (gcry_mpi_cmp (v, elgamal_q) >= 0));
 690   }
 691 }
 692
 693
 694 /**
 695  * Consensus element handler for round one.
 696  * We should get one ephemeral key for each peer.
 697  *
 698  * @param cls Closure (keygen session).
 699  * @param element The element from consensus, or
 700  *                NULL if consensus failed.
 701  */
 702 static void
 703 keygen_round1_new_element (void *cls,
 704                            const struct GNUNET_SET_Element *element)
 705 {
 706   const struct GNUNET_SECRETSHARING_KeygenCommitData *d;
 707   struct KeygenSession *ks = cls;
 708   struct KeygenPeerInfo *info;
 709
 710   if (NULL == element)
 711   {
 712     GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "round1 consensus failed\n");
 713     return;
 714   }
 715
 716   /* elements have fixed size */
 717   if (element->size != sizeof (struct GNUNET_SECRETSHARING_KeygenCommitData))
 718   {
 719     GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 720                 "keygen commit data with wrong size (%u) in consensus, %u expected\n",
 721                 (unsigned int) element->size,
 722                 (unsigned int) sizeof (struct GNUNET_SECRETSHARING_KeygenCommitData));
 723     return;
 724   }
 725
 726   GNUNET_log (GNUNET_ERROR_TYPE_INFO, "got round1 element\n");
 727
 728   d = element->data;
 729   info = get_keygen_peer_info (ks, &d->peer);
 730
 731   if (NULL == info)
 732   {
 733     GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen commit data with wrong peer identity (%s) in consensus\n",
 734                 GNUNET_i2s (&d->peer));
 735     return;
 736   }
 737
 738   /* Check that the right amount of data has been signed. */
 739   if (d->purpose.size !=
 740       htonl (element->size - offsetof (struct GNUNET_SECRETSHARING_KeygenCommitData, purpose)))
 741   {
 742     GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen commit data with wrong signature purpose size in consensus\n");
 743     return;
 744   }
 745
 746   if (GNUNET_OK != GNUNET_CRYPTO_eddsa_verify (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG1,
 747                                                &d->purpose, &d->signature, &d->peer.public_key))
 748   {
 749     GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen commit data with invalid signature in consensus\n");
 750     return;
 751   }
 752   info->paillier_public_key = d->pubkey;
 753   GNUNET_CRYPTO_mpi_scan_unsigned (&info->presecret_commitment, &d->commitment, 512 / 8);
 754   info->round1_valid = GNUNET_YES;
 755 }
 756
 757
 758 /**
 759  * Evaluate the polynomial with coefficients @a coeff at @a x.
 760  * The i-th element in @a coeff corresponds to the coefficient of x^i.
 761  *
 762  * @param[out] z result of the evaluation
 763  * @param coeff array of coefficients
 764  * @param num_coeff number of coefficients
 765  * @param x where to evaluate the polynomial
 766  * @param m what group are we operating in?
 767  */
 768 static void
 769 horner_eval (gcry_mpi_t z, gcry_mpi_t *coeff, unsigned int num_coeff, gcry_mpi_t x, gcry_mpi_t m)
 770 {
 771   unsigned int i;
 772
 773   gcry_mpi_set_ui (z, 0);
 774   for (i = 0; i < num_coeff; i++)
 775   {
 776     // z <- zx + c
 777     gcry_mpi_mul (z, z, x);
 778     gcry_mpi_addm (z, z, coeff[num_coeff - i - 1], m);
 779   }
 780 }
 781
 782
 783 static void
 784 keygen_round2_conclude (void *cls)
 785 {
 786   struct KeygenSession *ks = cls;
 787   struct GNUNET_SECRETSHARING_SecretReadyMessage *m;
 788   struct GNUNET_MQ_Envelope *ev;
 789   size_t share_size;
 790   unsigned int i;
 791   unsigned int j;
 792   struct GNUNET_SECRETSHARING_Share *share;
 793
 794   GNUNET_log (GNUNET_ERROR_TYPE_INFO, "round2 conclude\n");
 795
 796   GNUNET_CONSENSUS_destroy (ks->consensus);
 797   ks->consensus = NULL;
 798
 799   share = GNUNET_new (struct GNUNET_SECRETSHARING_Share);
 800
 801   share->num_peers = 0;
 802
 803   for (i = 0; i < ks->num_peers; i++)
 804     if (GNUNET_YES == ks->info[i].round2_valid)
 805       share->num_peers++;
 806
 807   share->peers = GNUNET_new_array (share->num_peers,
 808                                    struct GNUNET_PeerIdentity);
 809   share->sigmas =
 810       GNUNET_new_array (share->num_peers,
 811                         struct GNUNET_SECRETSHARING_FieldElement);
 812   share->original_indices = GNUNET_new_array (share->num_peers,
 813                                               uint16_t);
 814
 815   /* maybe we're not even in the list of peers? */
 816   share->my_peer = share->num_peers;
 817
 818   j = 0; /* running index of valid peers */
 819   for (i = 0; i < ks->num_peers; i++)
 820   {
 821     if (GNUNET_YES == ks->info[i].round2_valid)
 822     {
 823       share->peers[j] = ks->info[i].peer;
 824       GNUNET_CRYPTO_mpi_print_unsigned (&share->sigmas[j],
 825                                         GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
 826                                         ks->info[i].sigma);
 827       share->original_indices[i] = j;
 828       if (0 == memcmp (&share->peers[i], &my_peer, sizeof (struct GNUNET_PeerIdentity)))
 829         share->my_peer = j;
 830       j += 1;
 831     }
 832   }
 833
 834   if (share->my_peer == share->num_peers)
 835   {
 836     GNUNET_log (GNUNET_ERROR_TYPE_INFO, "P%u: peer identity not in share\n", ks->local_peer_idx);
 837   }
 838
 839   GNUNET_CRYPTO_mpi_print_unsigned (&share->my_share, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
 840                                     ks->my_share);
 841   GNUNET_CRYPTO_mpi_print_unsigned (&share->public_key, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
 842                                     ks->public_key);
 843
 844   GNUNET_log (GNUNET_ERROR_TYPE_INFO, "keygen completed with %u peers\n", share->num_peers);
 845
 846   /* Write the share. If 0 peers completed the dkg, an empty
 847    * share will be sent. */
 848
 849   GNUNET_assert (GNUNET_OK == GNUNET_SECRETSHARING_share_write (share, NULL, 0, &share_size));
 850
 851   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "writing share of size %u\n",
 852               (unsigned int) share_size);
 853
 854   ev = GNUNET_MQ_msg_extra (m, share_size,
 855                             GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_SECRET_READY);
 856
 857   GNUNET_assert (GNUNET_OK == GNUNET_SECRETSHARING_share_write (share, &m[1], share_size, NULL));
 858
 859   GNUNET_SECRETSHARING_share_destroy (share);
 860   share = NULL;
 861
 862   GNUNET_MQ_send (ks->cs->mq,
 863                   ev);
 864 }
 865
 866
 867
 868 static void
 869 restore_fair (const struct GNUNET_CRYPTO_PaillierPublicKey *ppub,
 870               const struct GNUNET_SECRETSHARING_FairEncryption *fe,
 871               gcry_mpi_t x, gcry_mpi_t xres)
 872 {
 873   gcry_mpi_t a_1;
 874   gcry_mpi_t a_2;
 875   gcry_mpi_t b_1;
 876   gcry_mpi_t b_2;
 877   gcry_mpi_t big_a;
 878   gcry_mpi_t big_b;
 879   gcry_mpi_t big_t;
 880   gcry_mpi_t n;
 881   gcry_mpi_t t_1;
 882   gcry_mpi_t t_2;
 883   gcry_mpi_t t;
 884   gcry_mpi_t r;
 885   gcry_mpi_t v;
 886
 887
 888   GNUNET_assert (NULL != (n = gcry_mpi_new (0)));
 889   GNUNET_assert (NULL != (t = gcry_mpi_new (0)));
 890   GNUNET_assert (NULL != (t_1 = gcry_mpi_new (0)));
 891   GNUNET_assert (NULL != (t_2 = gcry_mpi_new (0)));
 892   GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
 893   GNUNET_assert (NULL != (big_t = gcry_mpi_new (0)));
 894   GNUNET_assert (NULL != (v = gcry_mpi_new (0)));
 895   GNUNET_assert (NULL != (big_a = gcry_mpi_new (0)));
 896   GNUNET_assert (NULL != (big_b = gcry_mpi_new (0)));
 897
 898   // a = (N,0)^T
 899   GNUNET_CRYPTO_mpi_scan_unsigned (&a_1, ppub, sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
 900   GNUNET_assert (NULL != (a_2 = gcry_mpi_new (0)));
 901   gcry_mpi_set_ui (a_2, 0);
 902   // b = (x,1)^T
 903   GNUNET_assert (NULL != (b_1 = gcry_mpi_new (0)));
 904   gcry_mpi_set (b_1, x);
 905   GNUNET_assert (NULL != (b_2 = gcry_mpi_new (0)));
 906   gcry_mpi_set_ui (b_2, 1);
 907
 908   // A = a DOT a
 909   gcry_mpi_mul (t, a_1, a_1);
 910   gcry_mpi_mul (big_a, a_2, a_2);
 911   gcry_mpi_add (big_a, big_a, t);
 912
 913   // B = b DOT b
 914   gcry_mpi_mul (t, b_1, b_1);
 915   gcry_mpi_mul (big_b, b_2, b_2);
 916   gcry_mpi_add (big_b, big_b, t);
 917
 918   while (1)
 919   {
 920     // n = a DOT b
 921     gcry_mpi_mul (t, a_1, b_1);
 922     gcry_mpi_mul (n, a_2, b_2);
 923     gcry_mpi_add (n, n, t);
 924
 925     // r = nearest(n/B)
 926     gcry_mpi_div (r, NULL, n, big_b, 0);
 927
 928     // T := A - 2rn + rrB
 929     gcry_mpi_mul (v, r, n);
 930     gcry_mpi_mul_ui (v, v, 2);
 931     gcry_mpi_sub (big_t, big_a, v);
 932     gcry_mpi_mul (v, r, r);
 933     gcry_mpi_mul (v, v, big_b);
 934     gcry_mpi_add (big_t, big_t, v);
 935
 936     if (gcry_mpi_cmp (big_t, big_b) >= 0)
 937     {
 938       break;
 939     }
 940
 941     // t = a - rb
 942     gcry_mpi_mul (v, r, b_1);
 943     gcry_mpi_sub (t_1, a_1, v);
 944     gcry_mpi_mul (v, r, b_2);
 945     gcry_mpi_sub (t_2, a_2, v);
 946
 947     // a = b
 948     gcry_mpi_set (a_1, b_1);
 949     gcry_mpi_set (a_2, b_2);
 950     // b = t
 951     gcry_mpi_set (b_1, t_1);
 952     gcry_mpi_set (b_2, t_2);
 953
 954     gcry_mpi_set (big_a, big_b);
 955     gcry_mpi_set (big_b, big_t);
 956   }
 957
 958   {
 959     gcry_mpi_t paillier_n;
 960
 961     GNUNET_CRYPTO_mpi_scan_unsigned (&paillier_n, ppub, sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
 962
 963     gcry_mpi_set (xres, b_2);
 964     gcry_mpi_invm (xres, xres, elgamal_q);
 965     gcry_mpi_mulm (xres, xres, b_1, elgamal_q);
 966   }
 967
 968   gcry_mpi_release (a_1);
 969   gcry_mpi_release (a_2);
 970   gcry_mpi_release (b_1);
 971   gcry_mpi_release (b_2);
 972   gcry_mpi_release (big_a);
 973   gcry_mpi_release (big_b);
 974   gcry_mpi_release (big_t);
 975   gcry_mpi_release (n);
 976   gcry_mpi_release (t_1);
 977   gcry_mpi_release (t_2);
 978   gcry_mpi_release (t);
 979   gcry_mpi_release (r);
 980   gcry_mpi_release (v);
 981 }
 982
 983
 984 static void
 985 get_fair_encryption_challenge (const struct GNUNET_SECRETSHARING_FairEncryption *fe, gcry_mpi_t e)
 986 {
 987   struct {
 988     struct GNUNET_CRYPTO_PaillierCiphertext c;
 989     char h[GNUNET_SECRETSHARING_ELGAMAL_BITS / 8];
 990     char t1[GNUNET_SECRETSHARING_ELGAMAL_BITS / 8];
 991     char t2[GNUNET_CRYPTO_PAILLIER_BITS * 2 / 8];
 992   } hash_data;
 993   struct GNUNET_HashCode e_hash;
 994
 995   GNUNET_memcpy (&hash_data.c, &fe->c, sizeof (struct GNUNET_CRYPTO_PaillierCiphertext));
 996   GNUNET_memcpy (&hash_data.h, &fe->h, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
 997   GNUNET_memcpy (&hash_data.t1, &fe->t1, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
 998   GNUNET_memcpy (&hash_data.t2, &fe->t2, GNUNET_CRYPTO_PAILLIER_BITS * 2 / 8);
 999
1000   GNUNET_CRYPTO_mpi_scan_unsigned (&e, &e_hash, sizeof (struct GNUNET_HashCode));
1001   gcry_mpi_mod (e, e, elgamal_q);
1002 }
1003
1004
1005 static int
1006 verify_fair (const struct GNUNET_CRYPTO_PaillierPublicKey *ppub, const struct GNUNET_SECRETSHARING_FairEncryption *fe)
1007 {
1008   gcry_mpi_t n;
1009   gcry_mpi_t n_sq;
1010   gcry_mpi_t z;
1011   gcry_mpi_t t1;
1012   gcry_mpi_t t2;
1013   gcry_mpi_t e;
1014   gcry_mpi_t w;
1015   gcry_mpi_t tmp1;
1016   gcry_mpi_t tmp2;
1017   gcry_mpi_t y;
1018   gcry_mpi_t big_y;
1019   int res;
1020
1021   GNUNET_assert (NULL != (n_sq = gcry_mpi_new (0)));
1022   GNUNET_assert (NULL != (tmp1 = gcry_mpi_new (0)));
1023   GNUNET_assert (NULL != (tmp2 = gcry_mpi_new (0)));
1024   GNUNET_assert (NULL != (e = gcry_mpi_new (0)));
1025
1026   get_fair_encryption_challenge (fe, e);
1027
1028   GNUNET_CRYPTO_mpi_scan_unsigned (&n, ppub, sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
1029   GNUNET_CRYPTO_mpi_scan_unsigned (&t1, fe->t1, GNUNET_CRYPTO_PAILLIER_BITS / 8);
1030   GNUNET_CRYPTO_mpi_scan_unsigned (&z, fe->z, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1031   GNUNET_CRYPTO_mpi_scan_unsigned (&y, fe->h, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1032   GNUNET_CRYPTO_mpi_scan_unsigned (&w, fe->w, GNUNET_CRYPTO_PAILLIER_BITS / 8);
1033   GNUNET_CRYPTO_mpi_scan_unsigned (&big_y, fe->c.bits, GNUNET_CRYPTO_PAILLIER_BITS * 2 / 8);
1034   GNUNET_CRYPTO_mpi_scan_unsigned (&t2, fe->t2, GNUNET_CRYPTO_PAILLIER_BITS * 2 / 8);
1035   gcry_mpi_mul (n_sq, n, n);
1036
1037   // tmp1 = g^z
1038   gcry_mpi_powm (tmp1, elgamal_g, z, elgamal_p);
1039   // tmp2 = y^{-e}
1040   gcry_mpi_powm (tmp1, y, e, elgamal_p);
1041   gcry_mpi_invm (tmp1, tmp1, elgamal_p);
1042   // tmp1 = tmp1 * tmp2
1043   gcry_mpi_mulm (tmp1, tmp1, tmp2, elgamal_p);
1044
1045   if (0 == gcry_mpi_cmp (t1, tmp1))
1046   {
1047     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "fair encryption invalid (t1)\n");
1048     res = GNUNET_NO;
1049     goto cleanup;
1050   }
1051
1052   gcry_mpi_powm (big_y, big_y, e, n_sq);
1053   gcry_mpi_invm (big_y, big_y, n_sq);
1054
1055   gcry_mpi_add_ui (tmp1, n, 1);
1056   gcry_mpi_powm (tmp1, tmp1, z, n_sq);
1057
1058   gcry_mpi_powm (tmp2, w, n, n_sq);
1059
1060   gcry_mpi_mulm (tmp1, tmp1, tmp2, n_sq);
1061   gcry_mpi_mulm (tmp1, tmp1, big_y, n_sq);
1062
1063
1064   if (0 == gcry_mpi_cmp (t2, tmp1))
1065   {
1066     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "fair encryption invalid (t2)\n");
1067     res = GNUNET_NO;
1068     goto cleanup;
1069   }
1070
1071   res = GNUNET_YES;
1072
1073 cleanup:
1074
1075   gcry_mpi_release (n);
1076   gcry_mpi_release (n_sq);
1077   gcry_mpi_release (z);
1078   gcry_mpi_release (t1);
1079   gcry_mpi_release (t2);
1080   gcry_mpi_release (e);
1081   gcry_mpi_release (w);
1082   gcry_mpi_release (tmp1);
1083   gcry_mpi_release (tmp2);
1084   gcry_mpi_release (y);
1085   gcry_mpi_release (big_y);
1086   return res;
1087 }
1088
1089
1090 /**
1091  * Create a fair Paillier encryption of then given ciphertext.
1092  *
1093  * @param v the ciphertext
1094  * @param[out] fe the fair encryption
1095  */
1096 static void
1097 encrypt_fair (gcry_mpi_t v, const struct GNUNET_CRYPTO_PaillierPublicKey *ppub, struct GNUNET_SECRETSHARING_FairEncryption *fe)
1098 {
1099   gcry_mpi_t r;
1100   gcry_mpi_t s;
1101   gcry_mpi_t t1;
1102   gcry_mpi_t t2;
1103   gcry_mpi_t z;
1104   gcry_mpi_t w;
1105   gcry_mpi_t n;
1106   gcry_mpi_t e;
1107   gcry_mpi_t n_sq;
1108   gcry_mpi_t u;
1109   gcry_mpi_t Y;
1110   gcry_mpi_t G;
1111   gcry_mpi_t h;
1112   GNUNET_assert (NULL != (r = gcry_mpi_new (0)));
1113   GNUNET_assert (NULL != (s = gcry_mpi_new (0)));
1114   GNUNET_assert (NULL != (t1 = gcry_mpi_new (0)));
1115   GNUNET_assert (NULL != (t2 = gcry_mpi_new (0)));
1116   GNUNET_assert (NULL != (z = gcry_mpi_new (0)));
1117   GNUNET_assert (NULL != (w = gcry_mpi_new (0)));
1118   GNUNET_assert (NULL != (n_sq = gcry_mpi_new (0)));
1119   GNUNET_assert (NULL != (e = gcry_mpi_new (0)));
1120   GNUNET_assert (NULL != (u = gcry_mpi_new (0)));
1121   GNUNET_assert (NULL != (Y = gcry_mpi_new (0)));
1122   GNUNET_assert (NULL != (G = gcry_mpi_new (0)));
1123   GNUNET_assert (NULL != (h = gcry_mpi_new (0)));
1124
1125   GNUNET_CRYPTO_mpi_scan_unsigned (&n, ppub, sizeof (struct GNUNET_CRYPTO_PaillierPublicKey));
1126   gcry_mpi_mul (n_sq, n, n);
1127   gcry_mpi_add_ui (G, n, 1);
1128
1129   do {
1130     gcry_mpi_randomize (u, GNUNET_CRYPTO_PAILLIER_BITS, GCRY_WEAK_RANDOM);
1131   }
1132   while (gcry_mpi_cmp (u, n) >= 0);
1133
1134   gcry_mpi_powm (t1, G, v, n_sq);
1135   gcry_mpi_powm (t2, u, n, n_sq);
1136   gcry_mpi_mulm (Y, t1, t2, n_sq);
1137
1138   GNUNET_CRYPTO_mpi_print_unsigned (fe->c.bits,
1139                                     sizeof fe->c.bits,
1140                                     Y);
1141
1142
1143   gcry_mpi_randomize (r, 2048, GCRY_WEAK_RANDOM);
1144   do {
1145     gcry_mpi_randomize (s, GNUNET_CRYPTO_PAILLIER_BITS, GCRY_WEAK_RANDOM);
1146   }
1147   while (gcry_mpi_cmp (s, n) >= 0);
1148
1149   // compute t1
1150   gcry_mpi_mulm (t1, elgamal_g, r, elgamal_p);
1151   // compute t2 (use z and w as temp)
1152   gcry_mpi_powm (z, G, r, n_sq);
1153   gcry_mpi_powm (w, s, n, n_sq);
1154   gcry_mpi_mulm (t2, z, w, n_sq);
1155
1156
1157   gcry_mpi_powm (h, elgamal_g, v, elgamal_p);
1158
1159   GNUNET_CRYPTO_mpi_print_unsigned (fe->h,
1160                                     GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
1161                                     h);
1162
1163   GNUNET_CRYPTO_mpi_print_unsigned (fe->t1,
1164                                     GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
1165                                     t1);
1166
1167   GNUNET_CRYPTO_mpi_print_unsigned (fe->t2,
1168                                     GNUNET_CRYPTO_PAILLIER_BITS * 2 / 8,
1169                                     t2);
1170
1171
1172   get_fair_encryption_challenge (fe, e);
1173
1174   // compute z
1175   gcry_mpi_mul (z, e, v);
1176   gcry_mpi_addm (z, z, r, elgamal_q);
1177   // compute w
1178   gcry_mpi_powm (w, u, e, n);
1179   gcry_mpi_mulm (w, w, s, n);
1180
1181   GNUNET_CRYPTO_mpi_print_unsigned (fe->z,
1182                                     GNUNET_SECRETSHARING_ELGAMAL_BITS / 8,
1183                                     z);
1184
1185   GNUNET_CRYPTO_mpi_print_unsigned (fe->w,
1186                                     GNUNET_CRYPTO_PAILLIER_BITS / 8,
1187                                     w);
1188
1189   gcry_mpi_release (n);
1190   gcry_mpi_release (r);
1191   gcry_mpi_release (s);
1192   gcry_mpi_release (t1);
1193   gcry_mpi_release (t2);
1194   gcry_mpi_release (z);
1195   gcry_mpi_release (w);
1196   gcry_mpi_release (e);
1197   gcry_mpi_release (n_sq);
1198   gcry_mpi_release (u);
1199   gcry_mpi_release (Y);
1200   gcry_mpi_release (G);
1201   gcry_mpi_release (h);
1202 }
1203
1204
1205 /**
1206  * Insert round 2 element in the consensus, consisting of
1207  * (1) The exponentiated pre-share polynomial coefficients A_{i,l}=g^{a_{i,l}}
1208  * (2) The exponentiated pre-shares y_{i,j}=g^{s_{i,j}}
1209  * (3) The encrypted pre-shares Y_{i,j}
1210  * (4) The zero knowledge proof for fairness of
1211  *     the encryption
1212  *
1213  * @param ks session to use
1214  */
1215 static void
1216 insert_round2_element (struct KeygenSession *ks)
1217 {
1218   struct GNUNET_SET_Element *element;
1219   struct GNUNET_SECRETSHARING_KeygenRevealData *d;
1220   unsigned char *pos;
1221   unsigned char *last_pos;
1222   size_t element_size;
1223   unsigned int i;
1224   gcry_mpi_t idx;
1225   gcry_mpi_t v;
1226
1227   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "P%u: Inserting round2 element\n",
1228               ks->local_peer_idx);
1229
1230   GNUNET_assert (NULL != (v = gcry_mpi_new (GNUNET_SECRETSHARING_ELGAMAL_BITS)));
1231   GNUNET_assert (NULL != (idx = gcry_mpi_new (GNUNET_SECRETSHARING_ELGAMAL_BITS)));
1232
1233   element_size = (sizeof (struct GNUNET_SECRETSHARING_KeygenRevealData) +
1234                   sizeof (struct GNUNET_SECRETSHARING_FairEncryption) * ks->num_peers +
1235                   GNUNET_SECRETSHARING_ELGAMAL_BITS / 8 * ks->threshold);
1236
1237   element = GNUNET_malloc (sizeof (struct GNUNET_SET_Element) + element_size);
1238   element->size = element_size;
1239   element->data = (void *) &element[1];
1240
1241   d = (void *) element->data;
1242   d->peer = my_peer;
1243
1244   // start inserting vector elements
1245   // after the fixed part of the element's data
1246   pos = (void *) &d[1];
1247   last_pos = pos + element_size;
1248
1249   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "P%u: computed exp preshares\n",
1250               ks->local_peer_idx);
1251
1252   // encrypted pre-shares
1253   // and fair encryption proof
1254   {
1255     for (i = 0; i < ks->num_peers; i++)
1256     {
1257       ptrdiff_t remaining = last_pos - pos;
1258       struct GNUNET_SECRETSHARING_FairEncryption *fe = (void *) pos;
1259
1260       GNUNET_assert (remaining > 0);
1261       memset (fe, 0, sizeof *fe);
1262       if (GNUNET_YES == ks->info[i].round1_valid)
1263       {
1264         gcry_mpi_set_ui (idx, i + 1);
1265         // evaluate the polynomial
1266         horner_eval (v, ks->presecret_polynomial, ks->threshold, idx, elgamal_q);
1267         // encrypt the result
1268         encrypt_fair (v, &ks->info[i].paillier_public_key, fe);
1269       }
1270       pos += sizeof *fe;
1271     }
1272   }
1273
1274   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "P%u: computed enc preshares\n",
1275               ks->local_peer_idx);
1276
1277   // exponentiated coefficients
1278   for (i = 0; i < ks->threshold; i++)
1279   {
1280     ptrdiff_t remaining = last_pos - pos;
1281     GNUNET_assert (remaining > 0);
1282     gcry_mpi_powm (v, elgamal_g, ks->presecret_polynomial[i], elgamal_p);
1283     GNUNET_CRYPTO_mpi_print_unsigned (pos, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, v);
1284     pos += GNUNET_SECRETSHARING_ELGAMAL_BITS / 8;
1285   }
1286
1287   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "P%u: computed exp coefficients\n",
1288               ks->local_peer_idx);
1289
1290
1291   d->purpose.size = htonl (element_size - offsetof (struct GNUNET_SECRETSHARING_KeygenRevealData, purpose));
1292   d->purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG2);
1293   GNUNET_assert (GNUNET_OK ==
1294                  GNUNET_CRYPTO_eddsa_sign (my_peer_private_key,
1295                                            &d->purpose,
1296                                            &d->signature));
1297
1298   GNUNET_CONSENSUS_insert (ks->consensus, element, NULL, NULL);
1299   GNUNET_free (element); /* FIXME: maybe stack-allocate instead? */
1300
1301   gcry_mpi_release (v);
1302   gcry_mpi_release (idx);
1303 }
1304
1305
1306 static gcry_mpi_t
1307 keygen_reveal_get_exp_coeff (struct KeygenSession *ks,
1308                              const struct GNUNET_SECRETSHARING_KeygenRevealData *d,
1309                              unsigned int idx)
1310 {
1311   unsigned char *pos;
1312   gcry_mpi_t exp_coeff;
1313
1314   GNUNET_assert (idx < ks->threshold);
1315
1316   pos = (void *) &d[1];
1317   // skip encrypted pre-shares
1318   pos += sizeof (struct GNUNET_SECRETSHARING_FairEncryption) * ks->num_peers;
1319   // skip exp. coeffs we are not interested in
1320   pos += GNUNET_SECRETSHARING_ELGAMAL_BITS / 8 * idx;
1321   // the first exponentiated coefficient is the public key share
1322   GNUNET_CRYPTO_mpi_scan_unsigned (&exp_coeff, pos, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1323   return exp_coeff;
1324 }
1325
1326
1327 static struct GNUNET_SECRETSHARING_FairEncryption *
1328 keygen_reveal_get_enc_preshare (struct KeygenSession *ks,
1329                                 const struct GNUNET_SECRETSHARING_KeygenRevealData *d,
1330                                 unsigned int idx)
1331 {
1332   unsigned char *pos;
1333
1334   GNUNET_assert (idx < ks->num_peers);
1335
1336   pos = (void *) &d[1];
1337   // skip encrypted pre-shares we're not interested in
1338   pos += sizeof (struct GNUNET_SECRETSHARING_FairEncryption) * idx;
1339   return (struct GNUNET_SECRETSHARING_FairEncryption *) pos;
1340 }
1341
1342
1343 static gcry_mpi_t
1344 keygen_reveal_get_exp_preshare (struct KeygenSession *ks,
1345                                 const struct GNUNET_SECRETSHARING_KeygenRevealData *d,
1346                                 unsigned int idx)
1347 {
1348   gcry_mpi_t exp_preshare;
1349   struct GNUNET_SECRETSHARING_FairEncryption *fe;
1350
1351   GNUNET_assert (idx < ks->num_peers);
1352   fe = keygen_reveal_get_enc_preshare (ks, d, idx);
1353   GNUNET_CRYPTO_mpi_scan_unsigned (&exp_preshare, fe->h, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1354   return exp_preshare;
1355 }
1356
1357
1358 static void
1359 keygen_round2_new_element (void *cls,
1360                            const struct GNUNET_SET_Element *element)
1361 {
1362   struct KeygenSession *ks = cls;
1363   const struct GNUNET_SECRETSHARING_KeygenRevealData *d;
1364   struct KeygenPeerInfo *info;
1365   size_t expected_element_size;
1366   unsigned int j;
1367   int cmp_result;
1368   gcry_mpi_t tmp;
1369   gcry_mpi_t public_key_share;
1370   gcry_mpi_t preshare;
1371
1372   if (NULL == element)
1373   {
1374     GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "round2 consensus failed\n");
1375     return;
1376   }
1377
1378   expected_element_size = (sizeof (struct GNUNET_SECRETSHARING_KeygenRevealData) +
1379                   sizeof (struct GNUNET_SECRETSHARING_FairEncryption) * ks->num_peers +
1380                   GNUNET_SECRETSHARING_ELGAMAL_BITS / 8 * ks->threshold);
1381
1382   if (element->size != expected_element_size)
1383   {
1384     GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1385                 "keygen round2 data with wrong size (%u) in consensus, %u expected\n",
1386                 (unsigned int) element->size,
1387                 (unsigned int) expected_element_size);
1388     return;
1389   }
1390
1391   d = (const void *) element->data;
1392
1393   info = get_keygen_peer_info (ks, &d->peer);
1394
1395   if (NULL == info)
1396   {
1397     GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen commit data with wrong peer identity (%s) in consensus\n",
1398                 GNUNET_i2s (&d->peer));
1399     return;
1400   }
1401
1402   if (GNUNET_NO == info->round1_valid)
1403   {
1404     GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1405                 "ignoring round2 element from peer with invalid round1 element (%s)\n",
1406                 GNUNET_i2s (&d->peer));
1407     return;
1408   }
1409
1410   if (GNUNET_YES == info->round2_valid)
1411   {
1412     GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1413                 "ignoring duplicate round2 element (%s)\n",
1414                 GNUNET_i2s (&d->peer));
1415     return;
1416   }
1417
1418   GNUNET_log (GNUNET_ERROR_TYPE_INFO, "got round2 element\n");
1419
1420   if (ntohl (d->purpose.size) !=
1421       element->size - offsetof (struct GNUNET_SECRETSHARING_KeygenRevealData, purpose))
1422   {
1423     GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen reveal data with wrong signature purpose size in consensus\n");
1424     return;
1425   }
1426
1427   if (GNUNET_OK != GNUNET_CRYPTO_eddsa_verify (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG2,
1428                                                &d->purpose, &d->signature, &d->peer.public_key))
1429   {
1430     GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "keygen reveal data with invalid signature in consensus\n");
1431     return;
1432   }
1433
1434   public_key_share = keygen_reveal_get_exp_coeff (ks, d, 0);
1435   info->preshare_commitment = keygen_reveal_get_exp_preshare (ks, d, ks->local_peer_idx);
1436
1437   if (NULL == ks->public_key)
1438   {
1439     GNUNET_assert (NULL != (ks->public_key = gcry_mpi_new (0)));
1440     gcry_mpi_set_ui (ks->public_key, 1);
1441   }
1442   gcry_mpi_mulm (ks->public_key, ks->public_key, public_key_share, elgamal_p);
1443
1444   gcry_mpi_release (public_key_share);
1445   public_key_share = NULL;
1446
1447   {
1448     struct GNUNET_SECRETSHARING_FairEncryption *fe = keygen_reveal_get_enc_preshare (ks, d, ks->local_peer_idx);
1449     GNUNET_assert (NULL != (preshare = gcry_mpi_new (0)));
1450     GNUNET_CRYPTO_paillier_decrypt (&ks->paillier_private_key,
1451                                     &ks->info[ks->local_peer_idx].paillier_public_key,
1452                                     &fe->c,
1453                                     preshare);
1454
1455     // FIXME: not doing the restoration is less expensive
1456     restore_fair (&ks->info[ks->local_peer_idx].paillier_public_key,
1457                   fe,
1458                   preshare,
1459                   preshare);
1460   }
1461
1462   GNUNET_assert (NULL != (tmp = gcry_mpi_new (0)));
1463   gcry_mpi_powm (tmp, elgamal_g, preshare, elgamal_p);
1464
1465   cmp_result = gcry_mpi_cmp (tmp, info->preshare_commitment);
1466   gcry_mpi_release (tmp);
1467   tmp = NULL;
1468   if (0 != cmp_result)
1469   {
1470     GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "P%u: Got invalid presecret from P%u\n",
1471                 (unsigned int) ks->local_peer_idx, (unsigned int) (info - ks->info));
1472     return;
1473   }
1474
1475   if (NULL == ks->my_share)
1476   {
1477     GNUNET_assert (NULL != (ks->my_share = gcry_mpi_new (0)));
1478   }
1479   gcry_mpi_addm (ks->my_share, ks->my_share, preshare, elgamal_q);
1480
1481   for (j = 0; j < ks->num_peers; j++)
1482   {
1483     gcry_mpi_t presigma;
1484     if (NULL == ks->info[j].sigma)
1485     {
1486       GNUNET_assert (NULL != (ks->info[j].sigma = gcry_mpi_new (0)));
1487       gcry_mpi_set_ui (ks->info[j].sigma, 1);
1488     }
1489     presigma = keygen_reveal_get_exp_preshare (ks, d, j);
1490     gcry_mpi_mulm (ks->info[j].sigma, ks->info[j].sigma, presigma, elgamal_p);
1491     gcry_mpi_release (presigma);
1492   }
1493
1494   gcry_mpi_t prod;
1495   GNUNET_assert (NULL != (prod = gcry_mpi_new (0)));
1496   gcry_mpi_t j_to_k;
1497   GNUNET_assert (NULL != (j_to_k = gcry_mpi_new (0)));
1498   // validate that the polynomial sharing matches the additive sharing
1499   for (j = 0; j < ks->num_peers; j++)
1500   {
1501     unsigned int k;
1502     int cmp_result;
1503     gcry_mpi_t exp_preshare;
1504     gcry_mpi_set_ui (prod, 1);
1505     for (k = 0; k < ks->threshold; k++)
1506     {
1507       // Using pow(double,double) is a bit sketchy.
1508       // We count players from 1, but shares from 0.
1509       gcry_mpi_t tmp;
1510       gcry_mpi_set_ui (j_to_k, (unsigned int) pow(j+1, k));
1511       tmp = keygen_reveal_get_exp_coeff (ks, d, k);
1512       gcry_mpi_powm (tmp, tmp, j_to_k, elgamal_p);
1513       gcry_mpi_mulm (prod, prod, tmp, elgamal_p);
1514       gcry_mpi_release (tmp);
1515     }
1516     exp_preshare = keygen_reveal_get_exp_preshare (ks, d, j);
1517     gcry_mpi_mod (exp_preshare, exp_preshare, elgamal_p);
1518     cmp_result = gcry_mpi_cmp (prod, exp_preshare);
1519     gcry_mpi_release (exp_preshare);
1520     exp_preshare = NULL;
1521     if (0 != cmp_result)
1522     {
1523       GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "P%u: reveal data from P%u incorrect\n",
1524                   ks->local_peer_idx, j);
1525       /* no need for further verification, round2 stays invalid ... */
1526       return;
1527     }
1528   }
1529
1530   // TODO: verify proof of fair encryption (once implemented)
1531   for (j = 0; j < ks->num_peers; j++)
1532   {
1533     struct GNUNET_SECRETSHARING_FairEncryption *fe = keygen_reveal_get_enc_preshare (ks, d, j);
1534     if (GNUNET_YES != verify_fair (&ks->info[j].paillier_public_key, fe))
1535     {
1536       GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "P%u: reveal data from P%u incorrect (fair encryption)\n",
1537                   ks->local_peer_idx, j);
1538       return;
1539     }
1540
1541   }
1542
1543   info->round2_valid = GNUNET_YES;
1544
1545   gcry_mpi_release (preshare);
1546   gcry_mpi_release (prod);
1547   gcry_mpi_release (j_to_k);
1548 }
1549
1550
1551 /**
1552  * Called when the first consensus round has concluded.
1553  * Will initiate the second round.
1554  *
1555  * @param cls closure
1556  */
1557 static void
1558 keygen_round1_conclude (void *cls)
1559 {
1560   struct KeygenSession *ks = cls;
1561
1562   GNUNET_CONSENSUS_destroy (ks->consensus);
1563
1564   ks->consensus = GNUNET_CONSENSUS_create (cfg, ks->num_peers, ks->peers, &ks->session_id,
1565                                            time_between (ks->start_time, ks->deadline, 1, 2),
1566                                            ks->deadline,
1567                                            keygen_round2_new_element, ks);
1568
1569   insert_round2_element (ks);
1570
1571   GNUNET_CONSENSUS_conclude (ks->consensus,
1572                              keygen_round2_conclude,
1573                              ks);
1574 }
1575
1576
1577 /**
1578  * Insert the ephemeral key and the presecret commitment
1579  * of this peer in the consensus of the given session.
1580  *
1581  * @param ks session to use
1582  */
1583 static void
1584 insert_round1_element (struct KeygenSession *ks)
1585 {
1586   struct GNUNET_SET_Element *element;
1587   struct GNUNET_SECRETSHARING_KeygenCommitData *d;
1588   // g^a_{i,0}
1589   gcry_mpi_t v;
1590   // big-endian representation of 'v'
1591   unsigned char v_data[GNUNET_SECRETSHARING_ELGAMAL_BITS / 8];
1592
1593   element = GNUNET_malloc (sizeof *element + sizeof *d);
1594   d = (void *) &element[1];
1595   element->data = d;
1596   element->size = sizeof *d;
1597
1598   d->peer = my_peer;
1599
1600   GNUNET_assert (0 != (v = gcry_mpi_new (GNUNET_SECRETSHARING_ELGAMAL_BITS)));
1601
1602   gcry_mpi_powm (v, elgamal_g, ks->presecret_polynomial[0], elgamal_p);
1603
1604   GNUNET_CRYPTO_mpi_print_unsigned (v_data, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, v);
1605
1606   GNUNET_CRYPTO_hash (v_data, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, &d->commitment);
1607
1608   d->pubkey = ks->info[ks->local_peer_idx].paillier_public_key;
1609
1610   d->purpose.size = htonl ((sizeof *d) - offsetof (struct GNUNET_SECRETSHARING_KeygenCommitData, purpose));
1611   d->purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DKG1);
1612   GNUNET_assert (GNUNET_OK ==
1613                  GNUNET_CRYPTO_eddsa_sign (my_peer_private_key,
1614                                            &d->purpose,
1615                                            &d->signature));
1616
1617   GNUNET_CONSENSUS_insert (ks->consensus, element, NULL, NULL);
1618
1619   gcry_mpi_release (v);
1620   GNUNET_free (element);
1621 }
1622
1623
1624 /**
1625  * Check that @a msg is well-formed.
1626  *
1627  * @param cls identification of the client
1628  * @param msg the actual message
1629  * @return #GNUNET_OK if @a msg is well-formed
1630  */
1631 static int
1632 check_client_keygen (void *cls,
1633                      const struct GNUNET_SECRETSHARING_CreateMessage *msg)
1634 {
1635   unsigned int num_peers = ntohs (msg->num_peers);
1636
1637   if (ntohs (msg->header.size) - sizeof (*msg) !=
1638       num_peers * sizeof (struct GNUNET_PeerIdentity))
1639   {
1640     GNUNET_break (0);
1641     return GNUNET_SYSERR;
1642   }
1643   return GNUNET_OK;
1644 }
1645
1646
1647 /**
1648  * Functions with this signature are called whenever a message is
1649  * received.
1650  *
1651  * @param cls identification of the client
1652  * @param msg the actual message
1653  */
1654 static void
1655 handle_client_keygen (void *cls,
1656                       const struct GNUNET_SECRETSHARING_CreateMessage *msg)
1657 {
1658   struct ClientState *cs = cls;
1659   struct KeygenSession *ks;
1660
1661   GNUNET_log (GNUNET_ERROR_TYPE_INFO,
1662               "client requested key generation\n");
1663   if (NULL != cs->keygen_session)
1664   {
1665     GNUNET_break (0);
1666     GNUNET_SERVICE_client_drop (cs->client);
1667     return;
1668   }
1669   ks = GNUNET_new (struct KeygenSession);
1670   ks->cs = cs;
1671   cs->keygen_session = ks;
1672   ks->deadline = GNUNET_TIME_absolute_ntoh (msg->deadline);
1673   ks->threshold = ntohs (msg->threshold);
1674   ks->num_peers = ntohs (msg->num_peers);
1675
1676   ks->peers = normalize_peers ((struct GNUNET_PeerIdentity *) &msg[1],
1677                                ks->num_peers,
1678                                &ks->num_peers,
1679                                &ks->local_peer_idx);
1680
1681
1682   GNUNET_log (GNUNET_ERROR_TYPE_INFO,
1683               "first round of consensus with %u peers\n",
1684               ks->num_peers);
1685   ks->consensus = GNUNET_CONSENSUS_create (cfg,
1686                                            ks->num_peers,
1687                                            ks->peers,
1688                                            &msg->session_id,
1689                                            GNUNET_TIME_absolute_ntoh (msg->start),
1690                                            GNUNET_TIME_absolute_ntoh (msg->deadline),
1691                                            keygen_round1_new_element,
1692                                            ks);
1693
1694   ks->info = GNUNET_new_array (ks->num_peers,
1695                                struct KeygenPeerInfo);
1696
1697   for (unsigned int i = 0; i < ks->num_peers; i++)
1698     ks->info[i].peer = ks->peers[i];
1699
1700   GNUNET_CRYPTO_paillier_create (&ks->info[ks->local_peer_idx].paillier_public_key,
1701                                  &ks->paillier_private_key);
1702
1703   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1704               "P%u: Generated paillier key pair\n",
1705               ks->local_peer_idx);
1706   generate_presecret_polynomial (ks);
1707   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1708               "P%u: Generated presecret polynomial\n",
1709               ks->local_peer_idx);
1710   insert_round1_element (ks);
1711   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1712               "P%u: Concluding for round 1\n",
1713               ks->local_peer_idx);
1714   GNUNET_CONSENSUS_conclude (ks->consensus,
1715                              keygen_round1_conclude,
1716                              ks);
1717   GNUNET_SERVICE_client_continue (cs->client);
1718   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1719               "P%u: Waiting for round 1 elements ...\n",
1720               ks->local_peer_idx);
1721 }
1722
1723
1724 /**
1725  * Called when the partial decryption consensus concludes.
1726  */
1727 static void
1728 decrypt_conclude (void *cls)
1729 {
1730   struct DecryptSession *ds = cls;
1731   struct GNUNET_SECRETSHARING_DecryptResponseMessage *msg;
1732   struct GNUNET_MQ_Envelope *ev;
1733   gcry_mpi_t lagrange;
1734   gcry_mpi_t m;
1735   gcry_mpi_t tmp;
1736   gcry_mpi_t c_2;
1737   gcry_mpi_t prod;
1738   unsigned int *indices;
1739   unsigned int num;
1740   unsigned int i;
1741   unsigned int j;
1742
1743   GNUNET_CONSENSUS_destroy (ds->consensus);
1744   ds->consensus = NULL;
1745
1746   GNUNET_assert (0 != (lagrange = gcry_mpi_new (0)));
1747   GNUNET_assert (0 != (m = gcry_mpi_new (0)));
1748   GNUNET_assert (0 != (tmp = gcry_mpi_new (0)));
1749   GNUNET_assert (0 != (prod = gcry_mpi_new (0)));
1750
1751   num = 0;
1752   for (i = 0; i < ds->share->num_peers; i++)
1753     if (NULL != ds->info[i].partial_decryption)
1754       num++;
1755
1756   indices = GNUNET_new_array (num,
1757                               unsigned int);
1758   j = 0;
1759   for (i = 0; i < ds->share->num_peers; i++)
1760     if (NULL != ds->info[i].partial_decryption)
1761       indices[j++] = ds->info[i].original_index;
1762
1763   GNUNET_log (GNUNET_ERROR_TYPE_INFO,
1764               "P%u: decrypt conclude, with %u peers\n",
1765               ds->share->my_peer,
1766               num);
1767
1768   gcry_mpi_set_ui (prod, 1);
1769   for (i = 0; i < num; i++)
1770   {
1771
1772     GNUNET_log (GNUNET_ERROR_TYPE_INFO,
1773                 "P%u: index of %u: %u\n",
1774                 ds->share->my_peer, i, indices[i]);
1775     compute_lagrange_coefficient (lagrange, indices[i], indices, num);
1776     // w_i^{\lambda_i}
1777     gcry_mpi_powm (tmp, ds->info[indices[i]].partial_decryption, lagrange, elgamal_p);
1778
1779     // product of all exponentiated partiel decryptions ...
1780     gcry_mpi_mulm (prod, prod, tmp, elgamal_p);
1781   }
1782
1783   GNUNET_CRYPTO_mpi_scan_unsigned (&c_2, ds->ciphertext.c2_bits, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1784
1785   GNUNET_assert (0 != gcry_mpi_invm (prod, prod, elgamal_p));
1786   gcry_mpi_mulm (m, c_2, prod, elgamal_p);
1787   ev = GNUNET_MQ_msg (msg, GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_DECRYPT_DONE);
1788   GNUNET_CRYPTO_mpi_print_unsigned (&msg->plaintext, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, m);
1789   msg->success = htonl (1);
1790   GNUNET_MQ_send (ds->cs->mq,
1791                   ev);
1792
1793   GNUNET_log (GNUNET_ERROR_TYPE_INFO, "sent decrypt done to client\n");
1794
1795   GNUNET_free (indices);
1796
1797   gcry_mpi_release(lagrange);
1798   gcry_mpi_release(m);
1799   gcry_mpi_release(tmp);
1800   gcry_mpi_release(prod);
1801   gcry_mpi_release(c_2);
1802
1803   // FIXME: what if not enough peers participated?
1804 }
1805
1806
1807 /**
1808  * Get a string representation of an MPI.
1809  * The caller must free the returned string.
1810  *
1811  * @param mpi mpi to convert to a string
1812  * @return string representation of @a mpi, must be free'd by the caller
1813  */
1814 static char *
1815 mpi_to_str (gcry_mpi_t mpi)
1816 {
1817   unsigned char *buf;
1818
1819   GNUNET_assert (0 == gcry_mpi_aprint (GCRYMPI_FMT_HEX, &buf, NULL, mpi));
1820   return (char *) buf;
1821 }
1822
1823
1824 /**
1825  * Called when a new partial decryption arrives.
1826  */
1827 static void
1828 decrypt_new_element (void *cls,
1829                      const struct GNUNET_SET_Element *element)
1830 {
1831   struct DecryptSession *session = cls;
1832   const struct GNUNET_SECRETSHARING_DecryptData *d;
1833   struct DecryptPeerInfo *info;
1834   struct GNUNET_HashCode challenge_hash;
1835
1836   /* nizk response */
1837   gcry_mpi_t r;
1838   /* nizk challenge */
1839   gcry_mpi_t challenge;
1840   /* nizk commit1, g^\beta */
1841   gcry_mpi_t commit1;
1842   /* nizk commit2, c_1^\beta */
1843   gcry_mpi_t commit2;
1844   /* homomorphic commitment to the peer's share,
1845    * public key share */
1846   gcry_mpi_t sigma;
1847   /* partial decryption we received */
1848   gcry_mpi_t w;
1849   /* ciphertext component #1 */
1850   gcry_mpi_t c1;
1851   /* temporary variable (for comparision) #1 */
1852   gcry_mpi_t tmp1;
1853   /* temporary variable (for comparision) #2 */
1854   gcry_mpi_t tmp2;
1855
1856   if (NULL == element)
1857   {
1858     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "decryption failed\n");
1859     /* FIXME: destroy */
1860     return;
1861   }
1862
1863   if (element->size != sizeof *d)
1864   {
1865     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "element of wrong size in decrypt consensus\n");
1866     return;
1867   }
1868
1869   d = element->data;
1870
1871   info = get_decrypt_peer_info (session, &d->peer);
1872
1873   if (NULL == info)
1874   {
1875     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "decrypt element from invalid peer (%s)\n",
1876                 GNUNET_i2s (&d->peer));
1877     return;
1878   }
1879
1880   if (NULL != info->partial_decryption)
1881   {
1882     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "decrypt element duplicate\n");
1883     return;
1884   }
1885
1886   if (0 != memcmp (&d->ciphertext, &session->ciphertext, sizeof (struct GNUNET_SECRETSHARING_Ciphertext)))
1887   {
1888     GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "P%u: got decrypt element with non-matching ciphertext from P%u\n",
1889                 (unsigned int) session->share->my_peer, (unsigned int) (info - session->info));
1890
1891     return;
1892   }
1893
1894
1895   GNUNET_CRYPTO_hash (offsetof (struct GNUNET_SECRETSHARING_DecryptData, ciphertext) + (char *) d,
1896                       offsetof (struct GNUNET_SECRETSHARING_DecryptData, nizk_response) -
1897                           offsetof (struct GNUNET_SECRETSHARING_DecryptData, ciphertext),
1898                       &challenge_hash);
1899
1900   GNUNET_CRYPTO_mpi_scan_unsigned (&challenge, &challenge_hash,
1901                                    sizeof (struct GNUNET_HashCode));
1902
1903   GNUNET_CRYPTO_mpi_scan_unsigned (&sigma, &session->share->sigmas[info - session->info],
1904                                    sizeof (struct GNUNET_SECRETSHARING_FieldElement));
1905
1906   GNUNET_CRYPTO_mpi_scan_unsigned (&c1, session->ciphertext.c1_bits,
1907                                    sizeof (struct GNUNET_SECRETSHARING_FieldElement));
1908
1909   GNUNET_CRYPTO_mpi_scan_unsigned (&commit1, &d->nizk_commit1,
1910                                    sizeof (struct GNUNET_SECRETSHARING_FieldElement));
1911
1912   GNUNET_CRYPTO_mpi_scan_unsigned (&commit2, &d->nizk_commit2,
1913                                    sizeof (struct GNUNET_SECRETSHARING_FieldElement));
1914
1915   GNUNET_CRYPTO_mpi_scan_unsigned (&r, &d->nizk_response,
1916                                    sizeof (struct GNUNET_SECRETSHARING_FieldElement));
1917
1918   GNUNET_CRYPTO_mpi_scan_unsigned (&w, &d->partial_decryption,
1919                                    sizeof (struct GNUNET_SECRETSHARING_FieldElement));
1920
1921   GNUNET_assert (NULL != (tmp1 = gcry_mpi_new (0)));
1922   GNUNET_assert (NULL != (tmp2 = gcry_mpi_new (0)));
1923
1924   // tmp1 = g^r
1925   gcry_mpi_powm (tmp1, elgamal_g, r, elgamal_p);
1926
1927   // tmp2 = g^\beta * \sigma^challenge
1928   gcry_mpi_powm (tmp2, sigma, challenge, elgamal_p);
1929   gcry_mpi_mulm (tmp2, tmp2, commit1, elgamal_p);
1930
1931   if (0 != gcry_mpi_cmp (tmp1, tmp2))
1932   {
1933     char *tmp1_str;
1934     char *tmp2_str;
1935
1936     tmp1_str = mpi_to_str (tmp1);
1937     tmp2_str = mpi_to_str (tmp2);
1938     GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1939                 "P%u: Received invalid partial decryption from P%u (eqn 1), expected %s got %s\n",
1940                 session->share->my_peer,
1941                 (unsigned int) (info - session->info),
1942                 tmp1_str,
1943                 tmp2_str);
1944     GNUNET_free (tmp1_str);
1945     GNUNET_free (tmp2_str);
1946     goto cleanup;
1947   }
1948
1949
1950   gcry_mpi_powm (tmp1, c1, r, elgamal_p);
1951
1952   gcry_mpi_powm (tmp2, w, challenge, elgamal_p);
1953   gcry_mpi_mulm (tmp2, tmp2, commit2, elgamal_p);
1954
1955
1956   if (0 != gcry_mpi_cmp (tmp1, tmp2))
1957   {
1958     GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1959                 "P%u: Received invalid partial decryption from P%u (eqn 2)\n",
1960                 session->share->my_peer,
1961                 (unsigned int) (info - session->info));
1962     goto cleanup;
1963   }
1964
1965
1966   GNUNET_CRYPTO_mpi_scan_unsigned (&info->partial_decryption, &d->partial_decryption,
1967                                    GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
1968 cleanup:
1969   gcry_mpi_release (tmp1);
1970   gcry_mpi_release (tmp2);
1971   gcry_mpi_release (sigma);
1972   gcry_mpi_release (commit1);
1973   gcry_mpi_release (commit2);
1974   gcry_mpi_release (r);
1975   gcry_mpi_release (w);
1976   gcry_mpi_release (challenge);
1977   gcry_mpi_release (c1);
1978 }
1979
1980
1981 static void
1982 insert_decrypt_element (struct DecryptSession *ds)
1983 {
1984   struct GNUNET_SECRETSHARING_DecryptData d;
1985   struct GNUNET_SET_Element element;
1986   /* our share */
1987   gcry_mpi_t s;
1988   /* partial decryption with our share */
1989   gcry_mpi_t w;
1990   /* first component of the elgamal ciphertext */
1991   gcry_mpi_t c1;
1992   /* nonce for dlog zkp */
1993   gcry_mpi_t beta;
1994   gcry_mpi_t tmp;
1995   gcry_mpi_t challenge;
1996   gcry_mpi_t sigma;
1997   struct GNUNET_HashCode challenge_hash;
1998
1999   /* make vagrind happy until we implement the real deal ... */
2000   memset (&d, 0, sizeof d);
2001
2002   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "P%u: Inserting decrypt element\n",
2003               ds->share->my_peer);
2004
2005   GNUNET_assert (ds->share->my_peer < ds->share->num_peers);
2006
2007   GNUNET_CRYPTO_mpi_scan_unsigned (&c1, &ds->ciphertext.c1_bits,
2008                                    GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
2009   GNUNET_CRYPTO_mpi_scan_unsigned (&s, &ds->share->my_share,
2010                                    GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
2011   GNUNET_CRYPTO_mpi_scan_unsigned (&sigma, &ds->share->sigmas[ds->share->my_peer],
2012                                    GNUNET_SECRETSHARING_ELGAMAL_BITS / 8);
2013
2014   GNUNET_assert (NULL != (w = gcry_mpi_new (0)));
2015   GNUNET_assert (NULL != (beta = gcry_mpi_new (0)));
2016   GNUNET_assert (NULL != (tmp = gcry_mpi_new (0)));
2017
2018   // FIXME: unnecessary, remove once crypto works
2019   gcry_mpi_powm (tmp, elgamal_g, s, elgamal_p);
2020   if (0 != gcry_mpi_cmp (tmp, sigma))
2021   {
2022     char *sigma_str = mpi_to_str (sigma);
2023     char *tmp_str = mpi_to_str (tmp);
2024     char *s_str = mpi_to_str (s);
2025     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Share of P%u is invalid, ref sigma %s, "
2026                 "computed sigma %s, s %s\n",
2027                 ds->share->my_peer,
2028                 sigma_str, tmp_str, s_str);
2029     GNUNET_free (sigma_str);
2030     GNUNET_free (tmp_str);
2031     GNUNET_free (s_str);
2032   }
2033
2034   gcry_mpi_powm (w, c1, s, elgamal_p);
2035
2036   element.data = (void *) &d;
2037   element.size = sizeof (struct GNUNET_SECRETSHARING_DecryptData);
2038   element.element_type = 0;
2039
2040   d.ciphertext = ds->ciphertext;
2041   d.peer = my_peer;
2042   GNUNET_CRYPTO_mpi_print_unsigned (&d.partial_decryption, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, w);
2043
2044   // create the zero knowledge proof
2045   // randomly choose beta such that 0 < beta < q
2046   do
2047   {
2048     gcry_mpi_randomize (beta, GNUNET_SECRETSHARING_ELGAMAL_BITS - 1, GCRY_WEAK_RANDOM);
2049   } while ((gcry_mpi_cmp_ui (beta, 0) == 0) || (gcry_mpi_cmp (beta, elgamal_q) >= 0));
2050   // tmp = g^beta
2051   gcry_mpi_powm (tmp, elgamal_g, beta, elgamal_p);
2052   GNUNET_CRYPTO_mpi_print_unsigned (&d.nizk_commit1, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, tmp);
2053   // tmp = (c_1)^beta
2054   gcry_mpi_powm (tmp, c1, beta, elgamal_p);
2055   GNUNET_CRYPTO_mpi_print_unsigned (&d.nizk_commit2, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, tmp);
2056
2057   // the challenge is the hash of everything up to the response
2058   GNUNET_CRYPTO_hash (offsetof (struct GNUNET_SECRETSHARING_DecryptData, ciphertext) + (char *) &d,
2059                       offsetof (struct GNUNET_SECRETSHARING_DecryptData, nizk_response) -
2060                           offsetof (struct GNUNET_SECRETSHARING_DecryptData, ciphertext),
2061                       &challenge_hash);
2062
2063   GNUNET_CRYPTO_mpi_scan_unsigned (&challenge, &challenge_hash,
2064                                    sizeof (struct GNUNET_HashCode));
2065
2066   // compute the response in tmp,
2067   // tmp = (c * s + beta) mod q
2068   gcry_mpi_mulm (tmp, challenge, s, elgamal_q);
2069   gcry_mpi_addm (tmp, tmp, beta, elgamal_q);
2070
2071   GNUNET_CRYPTO_mpi_print_unsigned (&d.nizk_response, GNUNET_SECRETSHARING_ELGAMAL_BITS / 8, tmp);
2072
2073   d.purpose.size = htonl (element.size - offsetof (struct GNUNET_SECRETSHARING_DecryptData, purpose));
2074   d.purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_SECRETSHARING_DECRYPTION);
2075
2076   GNUNET_assert (GNUNET_OK ==
2077                  GNUNET_CRYPTO_eddsa_sign (my_peer_private_key,
2078                                            &d.purpose,
2079                                            &d.signature));
2080
2081   GNUNET_CONSENSUS_insert (ds->consensus, &element, NULL, NULL);
2082   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2083               "P%u: Inserting decrypt element done!\n",
2084               ds->share->my_peer);
2085
2086   gcry_mpi_release (s);
2087   gcry_mpi_release (w);
2088   gcry_mpi_release (c1);
2089   gcry_mpi_release (beta);
2090   gcry_mpi_release (tmp);
2091   gcry_mpi_release (challenge);
2092   gcry_mpi_release (sigma);
2093 }
2094
2095
2096 /**
2097  * Check that @a msg is well-formed.
2098  *
2099  * @param cls identification of the client
2100  * @param msg the actual message
2101  * @return #GNUNET_OK (check deferred a bit)
2102  */
2103 static int
2104 check_client_decrypt (void *cls,
2105                       const struct GNUNET_SECRETSHARING_DecryptRequestMessage *msg)
2106 {
2107   /* we check later, it's complicated */
2108   return GNUNET_OK;
2109 }
2110
2111
2112 /**
2113  * Functions with this signature are called whenever a message is
2114  * received.
2115  *
2116  * @param cls identification of the client
2117  * @param msg the actual message
2118  */
2119 static void
2120 handle_client_decrypt (void *cls,
2121                        const struct GNUNET_SECRETSHARING_DecryptRequestMessage *msg)
2122 {
2123   struct ClientState *cs = cls;
2124   struct DecryptSession *ds;
2125   struct GNUNET_HashCode session_id;
2126
2127   if (NULL != cs->decrypt_session)
2128   {
2129     GNUNET_break (0);
2130     GNUNET_SERVICE_client_drop (cs->client);
2131     return;
2132   }
2133   ds = GNUNET_new (struct DecryptSession);
2134   cs->decrypt_session = ds;
2135   ds->cs = cs;
2136   ds->start = GNUNET_TIME_absolute_ntoh (msg->start);
2137   ds->deadline = GNUNET_TIME_absolute_ntoh (msg->deadline);
2138   ds->ciphertext = msg->ciphertext;
2139
2140   ds->share = GNUNET_SECRETSHARING_share_read (&msg[1],
2141                                                ntohs (msg->header.size) - sizeof (*msg),
2142                                                NULL);
2143   if (NULL == ds->share)
2144   {
2145     GNUNET_break (0);
2146     GNUNET_SERVICE_client_drop (cs->client);
2147     return;
2148   }
2149
2150   /* FIXME: this is probably sufficient, but kdf/hash with all values would be nicer ... */
2151   GNUNET_CRYPTO_hash (&msg->ciphertext,
2152                       sizeof (struct GNUNET_SECRETSHARING_Ciphertext),
2153                       &session_id);
2154   ds->consensus = GNUNET_CONSENSUS_create (cfg,
2155                                            ds->share->num_peers,
2156                                            ds->share->peers,
2157                                            &session_id,
2158                                            ds->start,
2159                                            ds->deadline,
2160                                            &decrypt_new_element,
2161                                            ds);
2162
2163
2164   ds->info = GNUNET_new_array (ds->share->num_peers,
2165                                struct DecryptPeerInfo);
2166   for (unsigned int i = 0; i < ds->share->num_peers; i++)
2167   {
2168     ds->info[i].peer = ds->share->peers[i];
2169     ds->info[i].original_index = ds->share->original_indices[i];
2170   }
2171   insert_decrypt_element (ds);
2172   GNUNET_CONSENSUS_conclude (ds->consensus,
2173                              decrypt_conclude,
2174                              ds);
2175   GNUNET_SERVICE_client_continue (cs->client);
2176   GNUNET_log (GNUNET_ERROR_TYPE_INFO,
2177               "decrypting with %u peers\n",
2178               ds->share->num_peers);
2179 }
2180
2181
2182 static void
2183 init_crypto_constants (void)
2184 {
2185   GNUNET_assert (0 == gcry_mpi_scan (&elgamal_q, GCRYMPI_FMT_HEX,
2186                                      GNUNET_SECRETSHARING_ELGAMAL_Q_HEX, 0, NULL));
2187   GNUNET_assert (0 == gcry_mpi_scan (&elgamal_p, GCRYMPI_FMT_HEX,
2188                                      GNUNET_SECRETSHARING_ELGAMAL_P_HEX, 0, NULL));
2189   GNUNET_assert (0 == gcry_mpi_scan (&elgamal_g, GCRYMPI_FMT_HEX,
2190                                      GNUNET_SECRETSHARING_ELGAMAL_G_HEX, 0, NULL));
2191 }
2192
2193
2194 /**
2195  * Initialize secretsharing service.
2196  *
2197  * @param cls closure
2198  * @param c configuration to use
2199  * @param service the initialized service
2200  */
2201 static void
2202 run (void *cls,
2203      const struct GNUNET_CONFIGURATION_Handle *c,
2204      struct GNUNET_SERVICE_Handle *service)
2205 {
2206   cfg = c;
2207   my_peer_private_key = GNUNET_CRYPTO_eddsa_key_create_from_configuration (c);
2208   if (NULL == my_peer_private_key)
2209   {
2210     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2211                 "could not access host private key\n");
2212     GNUNET_break (0);
2213     GNUNET_SCHEDULER_shutdown ();
2214     return;
2215   }
2216   init_crypto_constants ();
2217   if (GNUNET_OK !=
2218       GNUNET_CRYPTO_get_peer_identity (cfg,
2219                                        &my_peer))
2220   {
2221     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2222                 "could not retrieve host identity\n");
2223     GNUNET_break (0);
2224     GNUNET_SCHEDULER_shutdown ();
2225     return;
2226   }
2227   GNUNET_SCHEDULER_add_shutdown (&cleanup_task,
2228                                  NULL);
2229 }
2230
2231
2232 /**
2233  * Callback called when a client connects to the service.
2234  *
2235  * @param cls closure for the service
2236  * @param c the new client that connected to the service
2237  * @param mq the message queue used to send messages to the client
2238  * @return @a c
2239  */
2240 static void *
2241 client_connect_cb (void *cls,
2242                    struct GNUNET_SERVICE_Client *c,
2243                    struct GNUNET_MQ_Handle *mq)
2244 {
2245   struct ClientState *cs = GNUNET_new (struct ClientState);;
2246
2247   cs->client = c;
2248   cs->mq = mq;
2249   return cs;
2250 }
2251
2252
2253 /**
2254  * Callback called when a client disconnected from the service
2255  *
2256  * @param cls closure for the service
2257  * @param c the client that disconnected
2258  * @param internal_cls should be equal to @a c
2259  */
2260 static void
2261 client_disconnect_cb (void *cls,
2262                       struct GNUNET_SERVICE_Client *c,
2263                       void *internal_cls)
2264 {
2265   struct ClientState *cs = internal_cls;
2266
2267   if (NULL != cs->keygen_session)
2268     keygen_session_destroy (cs->keygen_session);
2269
2270   if (NULL != cs->decrypt_session)
2271     decrypt_session_destroy (cs->decrypt_session);
2272   GNUNET_free (cs);
2273 }
2274
2275
2276 /**
2277  * Define "main" method using service macro.
2278  */
2279 GNUNET_SERVICE_MAIN
2280 ("secretsharing",
2281  GNUNET_SERVICE_OPTION_NONE,
2282  &run,
2283  &client_connect_cb,
2284  &client_disconnect_cb,
2285  NULL,
2286  GNUNET_MQ_hd_var_size (client_keygen,
2287                         GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_GENERATE,
2288                         struct GNUNET_SECRETSHARING_CreateMessage,
2289                         NULL),
2290  GNUNET_MQ_hd_var_size (client_decrypt,
2291                         GNUNET_MESSAGE_TYPE_SECRETSHARING_CLIENT_DECRYPT,
2292                         struct GNUNET_SECRETSHARING_DecryptRequestMessage,
2293                         NULL),
2294  GNUNET_MQ_handler_end ());