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