[git] GCRYPT - branch, master, updated. libgcrypt-1.5.0-335-gc630fd7
by Werner Koch
cvs at cvs.gnupg.org
Thu Oct 24 16:00:20 CEST 2013
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "The GNU crypto library".
The branch, master has been updated
via c630fd71b336eb9209e914d24dc1e26a34521882 (commit)
via 1cf5699b6febab1ef9d300531acc2ee33a7df739 (commit)
from 9ce54e5b512418ddf45ce18f2cbd48cdced779f5 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit c630fd71b336eb9209e914d24dc1e26a34521882
Author: Werner Koch <wk at gnupg.org>
Date: Thu Oct 24 13:59:29 2013 +0200
ecc: Change algorithm for Ed25519 x recovery.
* cipher/ecc-eddsa.c (scanval): Add as temporary hack.
(_gcry_ecc_eddsa_recover_x): Use the algorithm from page 15 of the
paper. Return an error code.
(_gcry_ecc_eddsa_decodepoint): Take care of the error code.
* mpi/mpi-mul.c (gcry_mpi_mulm): Use truncated division.
Signed-off-by: Werner Koch <wk at gnupg.org>
diff --git a/cipher/ecc-common.h b/cipher/ecc-common.h
index e451f8d..93fd449 100644
--- a/cipher/ecc-common.h
+++ b/cipher/ecc-common.h
@@ -97,8 +97,8 @@ gpg_err_code_t _gcry_ecc_ecdsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
gcry_mpi_t r, gcry_mpi_t s);
/*-- ecc-eddsa.c --*/
-void _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign,
- mpi_ec_t ec);
+gpg_err_code_t _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign,
+ mpi_ec_t ec);
gpg_err_code_t _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ctx,
gcry_mpi_t x, gcry_mpi_t y,
unsigned char **r_buffer,
diff --git a/cipher/ecc-eddsa.c b/cipher/ecc-eddsa.c
index 4a9fe0a..22f2702 100644
--- a/cipher/ecc-eddsa.c
+++ b/cipher/ecc-eddsa.c
@@ -46,6 +46,20 @@ reverse_buffer (unsigned char *buffer, unsigned int length)
}
+/* Helper to scan a hex string. */
+static gcry_mpi_t
+scanval (const char *string)
+{
+ gpg_error_t err;
+ gcry_mpi_t val;
+
+ err = gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
+ if (err)
+ log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (err));
+ return val;
+}
+
+
/* Encode MPI using the EdDSA scheme. MINLEN specifies the required
length of the buffer in bytes. On success 0 is returned an a
@@ -122,61 +136,82 @@ _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec,
}
-/* Recover X from Y and SIGN . */
-void
+/* Recover X from Y and SIGN (which actually is a parity bit). */
+gpg_err_code_t
_gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec)
{
- /* FIXME: This algorithm can be improved - see the paper.
- sqrt(-1) mod ed255519_p:
- 2B8324804FC1DF0B2B4D00993DFBD7A72F431806AD2FE478C4EE1B274A0EA0B0 */
- gcry_mpi_t yy, t, p1, p2, p3;
-
- /* t = (y^2-1) · ((b*y^2+1)^{p-2} mod p) */
- yy = mpi_new (0);
- mpi_mul (yy, y, y);
- t = mpi_copy (yy);
- mpi_mul (t, t, ec->b);
- mpi_add_ui (t, t, 1);
- p2 = mpi_copy (ec->p);
- mpi_sub_ui (p2, p2, 2);
- mpi_powm (t, t, p2, ec->p);
-
- mpi_sub_ui (yy, yy, 1);
- mpi_mul (t, yy, t);
-
- /* x = t^{(p+3)/8} mod p */
- p3 = mpi_copy (ec->p);
- mpi_add_ui (p3, p3, 3);
- mpi_fdiv_q (p3, p3, mpi_const (MPI_C_EIGHT));
- mpi_powm (x, t, p3, ec->p);
-
- /* (x^2 - t) % p != 0 ? x = (x*(2^{(p-1)/4} mod p)) % p */
- mpi_mul (yy, x, x);
- mpi_subm (yy, yy, t, ec->p);
- if (mpi_cmp_ui (yy, 0))
+ gpg_err_code_t rc = 0;
+ gcry_mpi_t u, v, v3, t;
+ static gcry_mpi_t p58, seven;
+
+ if (ec->dialect != ECC_DIALECT_ED25519)
+ return GPG_ERR_NOT_IMPLEMENTED;
+
+ if (!p58)
+ p58 = scanval ("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD");
+ if (!seven)
+ seven = mpi_set_ui (NULL, 7);
+
+ u = mpi_new (0);
+ v = mpi_new (0);
+ v3 = mpi_new (0);
+ t = mpi_new (0);
+
+ /* Compute u and v */
+ /* u = y^2 */
+ mpi_mulm (u, y, y, ec->p);
+ /* v = b*y^2 */
+ mpi_mulm (v, ec->b, u, ec->p);
+ /* u = y^2-1 */
+ mpi_sub_ui (u, u, 1);
+ /* v = b*y^2+1 */
+ mpi_add_ui (v, v, 1);
+
+ /* Compute sqrt(u/v) */
+ /* v3 = v^3 */
+ mpi_powm (v3, v, mpi_const (MPI_C_THREE), ec->p);
+ /* t = v3 * v3 * u * v = u * v^7 */
+ mpi_powm (t, v, seven, ec->p);
+ mpi_mulm (t, t, u, ec->p);
+ /* t = t^((p-5)/8) = (u * v^7)^((p-5)/8) */
+ mpi_powm (t, t, p58, ec->p);
+ /* x = t * u * v^3 = (u * v^3) * (u * v^7)^((p-5)/8) */
+ mpi_mulm (t, t, u, ec->p);
+ mpi_mulm (x, t, v3, ec->p);
+
+ /* Adjust if needed. */
+ /* t = v * x^2 */
+ mpi_mulm (t, x, x, ec->p);
+ mpi_mulm (t, t, v, ec->p);
+ /* -t == u ? x = x * sqrt(-1) */
+ gcry_mpi_neg (t, t);
+ if (!mpi_cmp (t, u))
{
- p1 = mpi_copy (ec->p);
- mpi_sub_ui (p1, p1, 1);
- mpi_fdiv_q (p1, p1, mpi_const (MPI_C_FOUR));
- mpi_powm (yy, mpi_const (MPI_C_TWO), p1, ec->p);
- mpi_mulm (x, x, yy, ec->p);
+ static gcry_mpi_t m1; /* Fixme: this is not thread-safe. */
+ if (!m1)
+ m1 = scanval ("2B8324804FC1DF0B2B4D00993DFBD7A7"
+ "2F431806AD2FE478C4EE1B274A0EA0B0");
+ mpi_mulm (x, x, m1, ec->p);
+ /* t = v * x^2 */
+ mpi_mulm (t, x, x, ec->p);
+ mpi_mulm (t, t, v, ec->p);
+ /* -t == u ? x = x * sqrt(-1) */
+ gcry_mpi_neg (t, t);
+ if (!mpi_cmp (t, u))
+ rc = GPG_ERR_INV_OBJ;
}
- else
- p1 = NULL;
- /* is_odd(x) ? x = p-x */
- if (mpi_test_bit (x, 0))
- mpi_sub (x, ec->p, x);
+ /* Choose the desired square root according to parity */
+ if (mpi_test_bit (x, 0) != !!sign)
+ gcry_mpi_neg (x, x);
- /* lowbit(x) != sign ? x = p-x */
- if (mpi_test_bit (x, 0) != sign)
- mpi_sub (x, ec->p, x);
+ mpi_free (t);
+ mpi_free (v3);
+ mpi_free (v);
+ mpi_free (u);
- gcry_mpi_release (yy);
- gcry_mpi_release (t);
- gcry_mpi_release (p3);
- gcry_mpi_release (p2);
- gcry_mpi_release (p1);
+ return rc;
}
@@ -278,10 +313,10 @@ _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
else
gcry_free (rawmpi);
- _gcry_ecc_eddsa_recover_x (result->x, result->y, sign, ctx);
+ rc = _gcry_ecc_eddsa_recover_x (result->x, result->y, sign, ctx);
mpi_set_ui (result->z, 1);
- return 0;
+ return rc;
}
diff --git a/mpi/mpi-mul.c b/mpi/mpi-mul.c
index ec6aea0..0a68711 100644
--- a/mpi/mpi-mul.c
+++ b/mpi/mpi-mul.c
@@ -208,5 +208,5 @@ void
gcry_mpi_mulm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, gcry_mpi_t m)
{
gcry_mpi_mul (w, u, v);
- _gcry_mpi_mod (w, w, m);
+ _gcry_mpi_tdiv_r (w, w, m);
}
diff --git a/tests/t-ed25519.c b/tests/t-ed25519.c
index 0a6ae14..be200fa 100644
--- a/tests/t-ed25519.c
+++ b/tests/t-ed25519.c
@@ -53,6 +53,7 @@ static int debug;
static int error_count;
static int sign_with_pk;
static int no_verify;
+static int custom_data_file;
static void
die (const char *format, ...)
@@ -405,9 +406,8 @@ one_test (int testno, const char *sk, const char *pk,
static void
-check_ed25519 (void)
+check_ed25519 (const char *fname)
{
- char *fname;
FILE *fp;
int lineno, ntests;
char *line;
@@ -416,7 +416,6 @@ check_ed25519 (void)
show ("Checking Ed25519.\n");
- fname = prepend_srcdir ("t-ed25519.inp");
fp = fopen (fname, "r");
if (!fp)
die ("error opening '%s': %s\n", fname, strerror (errno));
@@ -459,13 +458,12 @@ check_ed25519 (void)
xfree (msg);
xfree (sig);
- if (ntests != N_TESTS)
+ if (ntests != N_TESTS && !custom_data_file)
fail ("did %d tests but expected %d", ntests, N_TESTS);
else if ((ntests % 256))
show_note ("%d tests done\n", ntests);
fclose (fp);
- xfree (fname);
}
@@ -473,6 +471,7 @@ int
main (int argc, char **argv)
{
int last_argc = -1;
+ char *fname = NULL;
if (argc)
{ argc--; argv++; }
@@ -492,7 +491,8 @@ main (int argc, char **argv)
" --verbose print timings etc.\n"
" --debug flyswatter\n"
" --sign-with-pk also use the public key for signing\n"
- " --no-verify skip the verify test\n",
+ " --no-verify skip the verify test\n"
+ " --data FNAME take test data from file FNAME\n",
stdout);
exit (0);
}
@@ -517,11 +517,25 @@ main (int argc, char **argv)
no_verify = 1;
argc--; argv++;
}
+ else if (!strcmp (*argv, "--data"))
+ {
+ argc--; argv++;
+ if (argc)
+ {
+ xfree (fname);
+ fname = xstrdup (*argv);
+ argc--; argv++;
+ }
+ }
else if (!strncmp (*argv, "--", 2))
die ("unknown option '%s'", *argv);
}
+ if (!fname)
+ fname = prepend_srcdir ("t-ed25519.inp");
+ else
+ custom_data_file = 1;
gcry_control (GCRYCTL_DISABLE_SECMEM, 0);
if (!gcry_check_version (GCRYPT_VERSION))
@@ -532,9 +546,11 @@ main (int argc, char **argv)
gcry_control (GCRYCTL_INITIALIZATION_FINISHED, 0);
start_timer ();
- check_ed25519 ();
+ check_ed25519 (fname);
stop_timer ();
+ xfree (fname);
+
show ("All tests completed in %s. Errors: %d\n",
elapsed_time (), error_count);
return !!error_count;
commit 1cf5699b6febab1ef9d300531acc2ee33a7df739
Author: Werner Koch <wk at gnupg.org>
Date: Wed Oct 23 14:20:10 2013 +0200
ecc: Refactor _gcry_ecc_eddsa_decodepoint.
* cipher/ecc-eddsa.c (_gcry_ecc_eddsa_decodepoint): Factor some code
out to ..
(_gcry_ecc_eddsa_recover_x): new.
Signed-off-by: Werner Koch <wk at gnupg.org>
diff --git a/cipher/ecc-common.h b/cipher/ecc-common.h
index 0a95b95..e451f8d 100644
--- a/cipher/ecc-common.h
+++ b/cipher/ecc-common.h
@@ -97,6 +97,8 @@ gpg_err_code_t _gcry_ecc_ecdsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
gcry_mpi_t r, gcry_mpi_t s);
/*-- ecc-eddsa.c --*/
+void _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign,
+ mpi_ec_t ec);
gpg_err_code_t _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ctx,
gcry_mpi_t x, gcry_mpi_t y,
unsigned char **r_buffer,
diff --git a/cipher/ecc-eddsa.c b/cipher/ecc-eddsa.c
index 72103e9..4a9fe0a 100644
--- a/cipher/ecc-eddsa.c
+++ b/cipher/ecc-eddsa.c
@@ -122,6 +122,64 @@ _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec,
}
+/* Recover X from Y and SIGN . */
+void
+_gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec)
+{
+ /* FIXME: This algorithm can be improved - see the paper.
+ sqrt(-1) mod ed255519_p:
+ 2B8324804FC1DF0B2B4D00993DFBD7A72F431806AD2FE478C4EE1B274A0EA0B0 */
+ gcry_mpi_t yy, t, p1, p2, p3;
+
+ /* t = (y^2-1) · ((b*y^2+1)^{p-2} mod p) */
+ yy = mpi_new (0);
+ mpi_mul (yy, y, y);
+ t = mpi_copy (yy);
+ mpi_mul (t, t, ec->b);
+ mpi_add_ui (t, t, 1);
+ p2 = mpi_copy (ec->p);
+ mpi_sub_ui (p2, p2, 2);
+ mpi_powm (t, t, p2, ec->p);
+
+ mpi_sub_ui (yy, yy, 1);
+ mpi_mul (t, yy, t);
+
+ /* x = t^{(p+3)/8} mod p */
+ p3 = mpi_copy (ec->p);
+ mpi_add_ui (p3, p3, 3);
+ mpi_fdiv_q (p3, p3, mpi_const (MPI_C_EIGHT));
+ mpi_powm (x, t, p3, ec->p);
+
+ /* (x^2 - t) % p != 0 ? x = (x*(2^{(p-1)/4} mod p)) % p */
+ mpi_mul (yy, x, x);
+ mpi_subm (yy, yy, t, ec->p);
+ if (mpi_cmp_ui (yy, 0))
+ {
+ p1 = mpi_copy (ec->p);
+ mpi_sub_ui (p1, p1, 1);
+ mpi_fdiv_q (p1, p1, mpi_const (MPI_C_FOUR));
+ mpi_powm (yy, mpi_const (MPI_C_TWO), p1, ec->p);
+ mpi_mulm (x, x, yy, ec->p);
+ }
+ else
+ p1 = NULL;
+
+ /* is_odd(x) ? x = p-x */
+ if (mpi_test_bit (x, 0))
+ mpi_sub (x, ec->p, x);
+
+ /* lowbit(x) != sign ? x = p-x */
+ if (mpi_test_bit (x, 0) != sign)
+ mpi_sub (x, ec->p, x);
+
+ gcry_mpi_release (yy);
+ gcry_mpi_release (t);
+ gcry_mpi_release (p3);
+ gcry_mpi_release (p2);
+ gcry_mpi_release (p1);
+}
+
+
/* Decode the EdDSA style encoded PK and set it into RESULT. CTX is
the usual curve context. If R_ENCPK is not NULL, the encoded PK is
stored at that address; this is a new copy to be released by the
@@ -135,7 +193,6 @@ _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
gpg_err_code_t rc;
unsigned char *rawmpi;
unsigned int rawmpilen;
- gcry_mpi_t yy, t, x, p1, p2, p3;
int sign;
if (mpi_is_opaque (pk))
@@ -153,7 +210,7 @@ _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
first byte be 0x04. */
if (rawmpilen > 1 && buf[0] == 0x04 && (rawmpilen%2))
{
- gcry_mpi_t y;
+ gcry_mpi_t x, y;
rc = gcry_mpi_scan (&x, GCRYMPI_FMT_STD,
buf+1, (rawmpilen-1)/2, NULL);
@@ -221,59 +278,9 @@ _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
else
gcry_free (rawmpi);
- /* Now recover X. */
- /* t = (y^2-1) · ((b*y^2+1)^{p-2} mod p) */
- x = mpi_new (0);
- yy = mpi_new (0);
- mpi_mul (yy, result->y, result->y);
- t = mpi_copy (yy);
- mpi_mul (t, t, ctx->b);
- mpi_add_ui (t, t, 1);
- p2 = mpi_copy (ctx->p);
- mpi_sub_ui (p2, p2, 2);
- mpi_powm (t, t, p2, ctx->p);
-
- mpi_sub_ui (yy, yy, 1);
- mpi_mul (t, yy, t);
-
- /* x = t^{(p+3)/8} mod p */
- p3 = mpi_copy (ctx->p);
- mpi_add_ui (p3, p3, 3);
- mpi_fdiv_q (p3, p3, mpi_const (MPI_C_EIGHT));
- mpi_powm (x, t, p3, ctx->p);
-
- /* (x^2 - t) % p != 0 ? x = (x*(2^{(p-1)/4} mod p)) % p */
- mpi_mul (yy, x, x);
- mpi_subm (yy, yy, t, ctx->p);
- if (mpi_cmp_ui (yy, 0))
- {
- p1 = mpi_copy (ctx->p);
- mpi_sub_ui (p1, p1, 1);
- mpi_fdiv_q (p1, p1, mpi_const (MPI_C_FOUR));
- mpi_powm (yy, mpi_const (MPI_C_TWO), p1, ctx->p);
- mpi_mulm (x, x, yy, ctx->p);
- }
- else
- p1 = NULL;
-
- /* is_odd(x) ? x = p-x */
- if (mpi_test_bit (x, 0))
- mpi_sub (x, ctx->p, x);
-
- /* lowbit(x) != highbit(input) ? x = p-x */
- if (mpi_test_bit (x, 0) != sign)
- mpi_sub (x, ctx->p, x);
-
- mpi_set (result->x, x);
+ _gcry_ecc_eddsa_recover_x (result->x, result->y, sign, ctx);
mpi_set_ui (result->z, 1);
- gcry_mpi_release (x);
- gcry_mpi_release (yy);
- gcry_mpi_release (t);
- gcry_mpi_release (p3);
- gcry_mpi_release (p2);
- gcry_mpi_release (p1);
-
return 0;
}
-----------------------------------------------------------------------
Summary of changes:
cipher/ecc-common.h | 2 +
cipher/ecc-eddsa.c | 150 ++++++++++++++++++++++++++++++++-------------------
mpi/mpi-mul.c | 2 +-
tests/t-ed25519.c | 30 ++++++++---
4 files changed, 122 insertions(+), 62 deletions(-)
hooks/post-receive
--
The GNU crypto library
http://git.gnupg.org
_______________________________________________
Gnupg-commits mailing list
Gnupg-commits at gnupg.org
http://lists.gnupg.org/mailman/listinfo/gnupg-commits
More information about the Gcrypt-devel
mailing list