diff options
Diffstat (limited to 'crypto.c')
| -rw-r--r-- | crypto.c | 340 |
1 files changed, 216 insertions, 124 deletions
@@ -157,19 +157,26 @@ ec_skey_create (gcry_mpi_t skey) /** - * ec_keypair_create + * ec_keypair_create creates a new keypair by creating a random secret key first + * and multipyling the base point with it to get the public key. * * @param[out] pkey where to store the generated public key - * @param[out] skey where to store the generated secret key + * @param[out] skey where to store the generated secret key. May be NULL if + * you're not interested in the secret key and just need a random point. */ void ec_keypair_create (gcry_mpi_point_t pkey, gcry_mpi_t skey) { + gcry_mpi_t sk; + brandt_assert (NULL != pkey); - brandt_assert (NULL != skey); + sk = (NULL == skey) ? gcry_mpi_new (0) : skey; - ec_skey_create (skey); - gcry_mpi_ec_mul (pkey, skey, ec_gen, ec_ctx); + ec_skey_create (sk); + gcry_mpi_ec_mul (pkey, sk, ec_gen, ec_ctx); + + if (NULL == skey) + gcry_mpi_release (sk); } @@ -244,19 +251,21 @@ mpi_serialize (struct ec_mpi *dst, gcry_mpi_t src) { size_t rsize = 0; unsigned int nbits; - const void *p; + const void *vp; + char *cp = (char *)dst; gcry_error_t rc; + if (gcry_mpi_get_flag (src, GCRYMPI_FLAG_OPAQUE)) { /* Store opaque MPIs left aligned into the buffer. Used by Ed25519 point * compression */ - p = gcry_mpi_get_opaque (src, &nbits); - brandt_assert (p); + vp = gcry_mpi_get_opaque (src, &nbits); + brandt_assert (vp); rsize = (nbits + 7) / 8; if (rsize > sizeof (struct ec_mpi)) rsize = sizeof (struct ec_mpi); - memcpy (dst, p, rsize); + memcpy (dst, vp, rsize); if (rsize < sizeof (struct ec_mpi)) memset (((char *)dst) + rsize, 0, sizeof (struct ec_mpi) - rsize); } @@ -270,7 +279,7 @@ mpi_serialize (struct ec_mpi *dst, gcry_mpi_t src) /* Shift the output to the right, if shorter than available space */ if (rsize && rsize < sizeof (struct ec_mpi)) { - memmove (&dst[sizeof (struct ec_mpi) - rsize], dst, rsize); + memmove (&cp[sizeof (struct ec_mpi) - rsize], dst, rsize); memset (dst, 0, sizeof (struct ec_mpi) - rsize); } } @@ -577,8 +586,8 @@ smc_encrypt_bid (struct AuctionData *ad, gcry_mpi_t r1, gcry_mpi_t r2) { - smc_zkp_0og (ad->alpha[ad->i][j], (j == ad->b ? ec_gen : ec_zero), ad->Y, - ad->beta[ad->i][j], a1, a2, b1, b2, d1, d2, r1, r2); +// smc_zkp_0og (ad->alpha[ad->i][j], j == ad->b, ad->Y, +// ad->beta[ad->i][j], a1, a2, b1, b2, d1, d2, r1, r2); } @@ -604,27 +613,28 @@ smc_compute_outcome (struct AuctionData *ad) /** - * smc_zkp_dl + * smc_zkp_dl creates a proof of knowledge of @a x with \f$v = xg\f$ where + * \f$g\f$ is the base point on Ed25519. * - * @param v \todo - * @param g \todo - * @param x \todo - * @param a \todo - * @param r \todo + * @param[in] v input point. Must be known to the verifier. + * @param[in] x private key. Knowledge of this number is certified in the proof + * @param[out] proof pointer where to save the output proof structure. Must be + * shared with the verifier. */ void smc_zkp_dl (const gcry_mpi_point_t v, - const gcry_mpi_point_t g, const gcry_mpi_t x, - const gcry_mpi_point_t a, - gcry_mpi_t r) + struct proof_dl *proof) { struct zkp_challenge_dl challenge; struct brandt_hash_code challhash; + gcry_mpi_point_t a = gcry_mpi_point_new (0); + gcry_mpi_t r = gcry_mpi_new (0); gcry_mpi_t c = gcry_mpi_new (0); gcry_mpi_t z = gcry_mpi_new (0); - ec_keypair_create_base (a, z, g); + /* a = zg */ + ec_keypair_create (a, z); /* compute challenge c */ ec_point_serialize (&challenge.g, ec_gen); @@ -634,36 +644,44 @@ smc_zkp_dl (const gcry_mpi_point_t v, mpi_parse (c, (struct ec_mpi *)&challhash); gcry_mpi_mod (c, c, ec_n); + /* r = z + cx */ gcry_mpi_mulm (r, c, x, ec_n); gcry_mpi_addm (r, r, z, ec_n); + ec_point_serialize (&proof->a, a); + mpi_serialize (&proof->r, r); + + gcry_mpi_point_release (a); + gcry_mpi_release (r); gcry_mpi_release (c); gcry_mpi_release (z); } /** - * smc_zkp_dl_check + * smc_zkp_dl_check verifies a proof of knowledge of \f$x = ECDL_g(v)\f$ where + * \f$g\f$ is the base point on Ed25519. * - * @param v \todo - * @param g \todo - * @param a \todo - * @param r \todo + * @param[in] v input point. Received from the prover. + * @param[in] proof pointer to the proof structure. Received from the prover. * @return 0 if the proof is correct, something else otherwise */ int smc_zkp_dl_check (const gcry_mpi_point_t v, - const gcry_mpi_point_t g, - const gcry_mpi_point_t a, - const gcry_mpi_t r) + const struct proof_dl *proof) { int ret; struct zkp_challenge_dl challenge; struct brandt_hash_code challhash; + gcry_mpi_point_t a = gcry_mpi_point_new (0); + gcry_mpi_t r = gcry_mpi_new (0); gcry_mpi_t c = gcry_mpi_new (0); gcry_mpi_point_t left = gcry_mpi_point_new (0); gcry_mpi_point_t right = gcry_mpi_point_new (0); + ec_point_parse (a, &proof->a); + mpi_parse (r, &proof->r); + /* compute challenge c */ ec_point_serialize (&challenge.g, ec_gen); ec_point_serialize (&challenge.v, v); @@ -672,11 +690,14 @@ smc_zkp_dl_check (const gcry_mpi_point_t v, mpi_parse (c, (struct ec_mpi *)&challhash); gcry_mpi_mod (c, c, ec_n); - gcry_mpi_ec_mul (left, r, g, ec_ctx); + /* rg =? a + cv */ + gcry_mpi_ec_mul (left, r, ec_gen, ec_ctx); gcry_mpi_ec_mul (right, c, v, ec_ctx); gcry_mpi_ec_add (right, a, right, ec_ctx); - ret = ec_point_cmp (left, right); + + gcry_mpi_point_release (a); + gcry_mpi_release (r); gcry_mpi_release (c); gcry_mpi_point_release (left); gcry_mpi_point_release (right); @@ -686,82 +707,116 @@ smc_zkp_dl_check (const gcry_mpi_point_t v, /** - * smc_zkp_2dle \todo + * smc_zkp_2dle creates a proof that two ECDLs are equal without revealing the + * ECDL. \f$v=xg_1, w=xg_2\f$ are calculated as well and can be returned to the + * caller if needed. * - * @param v TODO - * @param w TODO - * @param g1 TODO - * @param g2 TODO - * @param x TODO - * @param a TODO - * @param b TODO - * @param r TODO + * @param[out] v first output point. May be NULL if not needed by the caller. + * Must be known to the verifier. + * @param[out] w second output point. May be NULL if not needed by the caller. + * Must be known to the verifier. + * @param[in] g1 first base point. Must be known to the verifier. + * @param[in] g2 second base point. Must be known to the verifier. + * @param[in] x private number to prove knowledge of. + * @param[out] proof pointer where to save the output proof structure. Must be + * shared with the verifier. */ void -smc_zkp_2dle (const gcry_mpi_point_t v, - const gcry_mpi_point_t w, +smc_zkp_2dle (gcry_mpi_point_t v, + gcry_mpi_point_t w, const gcry_mpi_point_t g1, const gcry_mpi_point_t g2, const gcry_mpi_t x, - gcry_mpi_point_t a, - gcry_mpi_point_t b, - gcry_mpi_t r) + struct proof_2dle *proof) { struct zkp_challenge_2dle challenge; struct brandt_hash_code challhash; + gcry_mpi_point_t rv; + gcry_mpi_point_t rw; + gcry_mpi_point_t a = gcry_mpi_point_new (0); + gcry_mpi_point_t b = gcry_mpi_point_new (0); + gcry_mpi_t r = gcry_mpi_new (0); gcry_mpi_t c = gcry_mpi_new (0); gcry_mpi_t z = gcry_mpi_new (0); + rv = (NULL == v) ? rv = gcry_mpi_point_new (0) : v; + rw = (NULL == w) ? rw = gcry_mpi_point_new (0) : w; + + /* v = x*g1 */ + gcry_mpi_ec_mul (rv, x, g1, ec_ctx); + + /* w = x*g2 */ + gcry_mpi_ec_mul (rw, x, g2, ec_ctx); + + /* a = z*g1 */ ec_keypair_create_base (a, z, g1); + + /* b = z*g2 */ gcry_mpi_ec_mul (b, z, g2, ec_ctx); /* compute challenge c */ ec_point_serialize (&challenge.g1, g1); ec_point_serialize (&challenge.g2, g2); - ec_point_serialize (&challenge.v, v); - ec_point_serialize (&challenge.w, w); + ec_point_serialize (&challenge.v, rv); + ec_point_serialize (&challenge.w, rw); ec_point_serialize (&challenge.a, a); ec_point_serialize (&challenge.b, b); brandt_hash (&challenge, sizeof (struct zkp_challenge_dl), &challhash); mpi_parse (c, (struct ec_mpi *)&challhash); gcry_mpi_mod (c, c, ec_n); + /* r = z + cx */ gcry_mpi_mulm (r, c, x, ec_n); gcry_mpi_addm (r, r, z, ec_n); + mpi_serialize (&proof->r, r); + ec_point_serialize (&proof->a, a); + ec_point_serialize (&proof->b, b); + + if (NULL == v) + gcry_mpi_point_release (rv); + if (NULL == w) + gcry_mpi_point_release (rw); + gcry_mpi_point_release (a); + gcry_mpi_point_release (b); + gcry_mpi_release (r); gcry_mpi_release (c); gcry_mpi_release (z); } /** - * smc_zkp_2dle_check \todo + * smc_zkp_2dle_check verifies a proof of knowledge of \f$x\f$ with \f$v=xg_1\f$ + * and \f$w=xg_2\f$. * - * @param v TODO - * @param w TODO - * @param g1 TODO - * @param g2 TODO - * @param a TODO - * @param b TODO - * @param r TODO - * @return TODO + * @param[in] v first input point. + * @param[in] w second input point. + * @param[in] g1 first base point. + * @param[in] g2 second base point. + * @param[in] proof pointer to the proof structure. Received from the prover. + * @return 0 if the proof is correct, something else otherwise */ int -smc_zkp_2dle_check (const gcry_mpi_point_t v, - const gcry_mpi_point_t w, - const gcry_mpi_point_t g1, - const gcry_mpi_point_t g2, - const gcry_mpi_point_t a, - const gcry_mpi_point_t b, - const gcry_mpi_t r) +smc_zkp_2dle_check (const gcry_mpi_point_t v, + const gcry_mpi_point_t w, + const gcry_mpi_point_t g1, + const gcry_mpi_point_t g2, + const struct proof_2dle *proof) { int ret; struct zkp_challenge_2dle challenge; struct brandt_hash_code challhash; + gcry_mpi_point_t a = gcry_mpi_point_new (0); + gcry_mpi_point_t b = gcry_mpi_point_new (0); + gcry_mpi_t r = gcry_mpi_new (0); gcry_mpi_t c = gcry_mpi_new (0); gcry_mpi_point_t left = gcry_mpi_point_new (0); gcry_mpi_point_t right = gcry_mpi_point_new (0); + mpi_parse (r, &proof->r); + ec_point_parse (a, &proof->a); + ec_point_parse (b, &proof->b); + /* compute challenge c */ ec_point_serialize (&challenge.g1, g1); ec_point_serialize (&challenge.g2, g2); @@ -773,16 +828,21 @@ smc_zkp_2dle_check (const gcry_mpi_point_t v, mpi_parse (c, (struct ec_mpi *)&challhash); gcry_mpi_mod (c, c, ec_n); + /* r*g1 =? a + cv */ gcry_mpi_ec_mul (left, r, g1, ec_ctx); gcry_mpi_ec_mul (right, c, v, ec_ctx); gcry_mpi_ec_add (right, a, right, ec_ctx); ret = ec_point_cmp (left, right); + /* r*g2 =? b + cw */ gcry_mpi_ec_mul (left, r, g2, ec_ctx); gcry_mpi_ec_mul (right, c, w, ec_ctx); gcry_mpi_ec_add (right, b, right, ec_ctx); ret |= ec_point_cmp (left, right); + gcry_mpi_point_release (a); + gcry_mpi_point_release (b); + gcry_mpi_release (r); gcry_mpi_release (c); gcry_mpi_point_release (left); gcry_mpi_point_release (right); @@ -792,55 +852,57 @@ smc_zkp_2dle_check (const gcry_mpi_point_t v, /** - * smc_zkp_0og \todo + * smc_zkp_0og encrypts one of two values and creates a proof that the + * ciphertext decrypts to either one of those two values without revealing which + * one was encrypted. The two values are the zero point or the base point of the + * Ed25519 curve. Encryption is done via ElGamal: \f$(\alpha,\beta)=(m+ry,rg)\f$ + * where \f$m\f$ is the value to encrypt, \f$y\f$ is the public key and \f$g\f$ + * is the base point. The nonce \f$r\f$ is generated as well and can be returned + * to the caller if he needs it (e.g. for another proof). * - * @param alpha TODO - * @param m TODO - * @param y TODO - * @param beta TODO - * @param a1 TODO - * @param a2 TODO - * @param b1 TODO - * @param b2 TODO - * @param d1 TODO - * @param d2 TODO - * @param r1 TODO - * @param r2 TODO + * @param[in] m_is_gen if true, the base point is encrypted, else the zero point + * is encrypted. + * @param[in] y public key to use for encryption. + * @param[out] r random number used for encryption. May be NULL if caller + * doesn't need it. + * @param[out] alpha first part of the ciphertext output + * @param[out] beta second part of the ciphertext output + * @param[out] proof pointer where to save the output proof structure. Must be + * shared with the verifier. */ void -smc_zkp_0og (gcry_mpi_point_t alpha, - const gcry_mpi_point_t m, +smc_zkp_0og (int m_is_gen, const gcry_mpi_point_t y, + gcry_mpi_t r, + gcry_mpi_point_t alpha, gcry_mpi_point_t beta, - gcry_mpi_point_t a1, - gcry_mpi_point_t a2, - gcry_mpi_point_t b1, - gcry_mpi_point_t b2, - gcry_mpi_t d1, - gcry_mpi_t d2, - gcry_mpi_t r1, - gcry_mpi_t r2) + struct proof_0og *proof) { struct zkp_challenge_0og challenge; struct brandt_hash_code challhash; + gcry_mpi_point_t a1 = gcry_mpi_point_new (0); + gcry_mpi_point_t a2 = gcry_mpi_point_new (0); + gcry_mpi_point_t b1 = gcry_mpi_point_new (0); + gcry_mpi_point_t b2 = gcry_mpi_point_new (0); + gcry_mpi_t d1 = gcry_mpi_new (0); + gcry_mpi_t d2 = gcry_mpi_new (0); + gcry_mpi_t r1 = gcry_mpi_new (0); + gcry_mpi_t r2 = gcry_mpi_new (0); gcry_mpi_t c = gcry_mpi_new (0); - gcry_mpi_t r = gcry_mpi_new (0); + gcry_mpi_t rr; gcry_mpi_t w = gcry_mpi_new (0); - int eq0 = !ec_point_cmp (m, ec_zero); - int eqg = !ec_point_cmp (m, ec_gen); - if (!(eq0 ^ eqg)) - eprintf ("zero knowledge proof: m is neither 0 nor g"); + rr = (NULL == r) ? gcry_mpi_new (0) : r; /* beta = r*g */ - ec_keypair_create (beta, r); - gcry_mpi_mod (r, r, ec_n); + ec_keypair_create (beta, rr); + gcry_mpi_mod (rr, rr, ec_n); /* alpha = m + r*y */ - gcry_mpi_ec_mul (alpha, r, y, ec_ctx); - gcry_mpi_ec_add (alpha, m, alpha, ec_ctx); + gcry_mpi_ec_mul (alpha, rr, y, ec_ctx); + gcry_mpi_ec_add (alpha, m_is_gen ? ec_gen : ec_zero, alpha, ec_ctx); - if (eq0) + if (!m_is_gen) { /* m == 0 */ ec_keypair_create_base (a1, d1, beta); gcry_mpi_mod (d1, d1, ec_n); @@ -900,13 +962,13 @@ smc_zkp_0og (gcry_mpi_point_t alpha, mpi_parse (c, (struct ec_mpi *)&challhash); gcry_mpi_mod (c, c, ec_n); - if (eq0) + if (!m_is_gen) { /* m == 0 */ /* d2 = c - d1 */ gcry_mpi_subm (d2, c, d1, ec_n); /* r2 = w - r*d2 */ - gcry_mpi_mulm (r2, r, d2, ec_n); + gcry_mpi_mulm (r2, rr, d2, ec_n); gcry_mpi_subm (r2, w, r2, ec_n); } else @@ -915,53 +977,75 @@ smc_zkp_0og (gcry_mpi_point_t alpha, gcry_mpi_subm (d1, c, d2, ec_n); /* r1 = w - r*d1 */ - gcry_mpi_mulm (r1, r, d1, ec_n); + gcry_mpi_mulm (r1, rr, d1, ec_n); gcry_mpi_subm (r1, w, r1, ec_n); } + ec_point_serialize (&proof->a1, a1); + ec_point_serialize (&proof->a2, a2); + ec_point_serialize (&proof->b1, b1); + ec_point_serialize (&proof->b2, b2); + mpi_serialize (&proof->d1, d1); + mpi_serialize (&proof->d2, d2); + mpi_serialize (&proof->r1, r1); + mpi_serialize (&proof->r2, r2); + + gcry_mpi_point_release (a1); + gcry_mpi_point_release (a2); + gcry_mpi_point_release (b1); + gcry_mpi_point_release (b2); + gcry_mpi_release (d1); + gcry_mpi_release (d2); + gcry_mpi_release (r1); + gcry_mpi_release (r2); gcry_mpi_release (c); - gcry_mpi_release (r); + if (NULL == r) + gcry_mpi_release (rr); gcry_mpi_release (w); } /** - * smc_zkp_0og_check \todo + * smc_zkp_0og_check verifies a proof that \f$(\alpha,\beta\f$ decrypts either + * to the base point \f$g\f$ or the zero point. * - * @param alpha TODO - * @param y TODO - * @param beta TODO - * @param a1 TODO - * @param a2 TODO - * @param b1 TODO - * @param b2 TODO - * @param d1 TODO - * @param d2 TODO - * @param r1 TODO - * @param r2 TODO - * @return TODO + * @param[in] y the public key used for encryption + * @param[in] alpha first part of the ciphertext + * @param[in] beta second part of the ciphertext + * @param[in] proof pointer to the proof structure. Received from the prover. + * @return 0 if the proof is correct, something else otherwise */ int -smc_zkp_0og_check (const gcry_mpi_point_t alpha, - const gcry_mpi_point_t y, +smc_zkp_0og_check (const gcry_mpi_point_t y, + const gcry_mpi_point_t alpha, const gcry_mpi_point_t beta, - const gcry_mpi_point_t a1, - const gcry_mpi_point_t a2, - const gcry_mpi_point_t b1, - const gcry_mpi_point_t b2, - const gcry_mpi_t d1, - const gcry_mpi_t d2, - const gcry_mpi_t r1, - const gcry_mpi_t r2) + const struct proof_0og *proof) { int ret; struct zkp_challenge_0og challenge; struct brandt_hash_code challhash; + gcry_mpi_point_t a1 = gcry_mpi_point_new (0); + gcry_mpi_point_t a2 = gcry_mpi_point_new (0); + gcry_mpi_point_t b1 = gcry_mpi_point_new (0); + gcry_mpi_point_t b2 = gcry_mpi_point_new (0); + gcry_mpi_t d1 = gcry_mpi_new (0); + gcry_mpi_t d2 = gcry_mpi_new (0); + gcry_mpi_t r1 = gcry_mpi_new (0); + gcry_mpi_t r2 = gcry_mpi_new (0); gcry_mpi_t c = gcry_mpi_new (0); gcry_mpi_t sum = gcry_mpi_new (0); gcry_mpi_point_t right = gcry_mpi_point_new (0); gcry_mpi_point_t tmp = gcry_mpi_point_new (0); + ec_point_parse (a1, &proof->a1); + ec_point_parse (a2, &proof->a2); + ec_point_parse (b1, &proof->b1); + ec_point_parse (b2, &proof->b2); + mpi_parse (d1, &proof->d1); + mpi_parse (d2, &proof->d2); + mpi_parse (r1, &proof->r1); + mpi_parse (r2, &proof->r2); + /* compute challenge c */ ec_point_serialize (&challenge.g, ec_gen); ec_point_serialize (&challenge.alpha, alpha); @@ -1003,6 +1087,14 @@ smc_zkp_0og_check (const gcry_mpi_point_t alpha, gcry_mpi_ec_add (right, right, tmp, ec_ctx); ret |= ec_point_cmp (b2, right) << 4; + gcry_mpi_point_release (a1); + gcry_mpi_point_release (a2); + gcry_mpi_point_release (b1); + gcry_mpi_point_release (b2); + gcry_mpi_release (d1); + gcry_mpi_release (d2); + gcry_mpi_release (r1); + gcry_mpi_release (r2); gcry_mpi_release (c); gcry_mpi_release (sum); gcry_mpi_point_release (right); |