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