diff --git a/cipher/ecc-eddsa.c b/cipher/ecc-eddsa.c
index d4bedb0a..52a7cc9f 100644
--- a/cipher/ecc-eddsa.c
+++ b/cipher/ecc-eddsa.c
@@ -1,828 +1,828 @@
/* ecc-eddsa.c - Elliptic Curve EdDSA signatures
* Copyright (C) 2013, 2014 g10 Code GmbH
*
* This file is part of Libgcrypt.
*
* Libgcrypt is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as
* published by the Free Software Foundation; either version 2.1 of
* the License, or (at your option) any later version.
*
* Libgcrypt is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this program; if not, see .
*/
#include
#include
#include
#include
#include
#include "g10lib.h"
#include "mpi.h"
#include "cipher.h"
#include "context.h"
#include "ec-context.h"
#include "ecc-common.h"
void
reverse_buffer (unsigned char *buffer, unsigned int length)
{
unsigned int tmp, i;
for (i=0; i < length/2; i++)
{
tmp = buffer[i];
buffer[i] = buffer[length-1-i];
buffer[length-1-i] = tmp;
}
}
/* Helper to scan a hex string. */
static gcry_mpi_t
scanval (const char *string)
{
gpg_err_code_t rc;
gcry_mpi_t val;
rc = _gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
if (rc)
log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (rc));
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
malloced buffer with the encoded point is stored at R_BUFFER; the
length of this buffer is stored at R_BUFLEN. */
static gpg_err_code_t
eddsa_encodempi (gcry_mpi_t mpi, unsigned int minlen,
unsigned char **r_buffer, unsigned int *r_buflen)
{
unsigned char *rawmpi;
unsigned int rawmpilen;
rawmpi = _gcry_mpi_get_buffer (mpi, minlen, &rawmpilen, NULL);
if (!rawmpi)
return gpg_err_code_from_syserror ();
*r_buffer = rawmpi;
*r_buflen = rawmpilen;
return 0;
}
/* Encode (X,Y) using the EdDSA scheme. MINLEN is the required length
in bytes for the result. If WITH_PREFIX is set the returned buffer
is prefixed with a 0x40 byte. On success 0 is returned and a
malloced buffer with the encoded point is stored at R_BUFFER; the
length of this buffer is stored at R_BUFLEN. */
static gpg_err_code_t
eddsa_encode_x_y (gcry_mpi_t x, gcry_mpi_t y, unsigned int minlen,
int with_prefix,
unsigned char **r_buffer, unsigned int *r_buflen)
{
unsigned char *rawmpi;
unsigned int rawmpilen;
int off = with_prefix? 1:0;
rawmpi = _gcry_mpi_get_buffer_extra (y, minlen, off?-1:0, &rawmpilen, NULL);
if (!rawmpi)
return gpg_err_code_from_syserror ();
if (mpi_test_bit (x, 0) && rawmpilen)
rawmpi[off + rawmpilen - 1] |= 0x80; /* Set sign bit. */
if (off)
rawmpi[0] = 0x40;
*r_buffer = rawmpi;
*r_buflen = rawmpilen + off;
return 0;
}
/* Encode POINT using the EdDSA scheme. X and Y are either scratch
variables supplied by the caller or NULL. CTX is the usual
context. If WITH_PREFIX is set the returned buffer is prefixed
with a 0x40 byte. On success 0 is returned and a malloced buffer
with the encoded point is stored at R_BUFFER; the length of this
buffer is stored at R_BUFLEN. */
gpg_err_code_t
_gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec,
gcry_mpi_t x_in, gcry_mpi_t y_in,
int with_prefix,
unsigned char **r_buffer, unsigned int *r_buflen)
{
gpg_err_code_t rc;
gcry_mpi_t x, y;
x = x_in? x_in : mpi_new (0);
y = y_in? y_in : mpi_new (0);
if (_gcry_mpi_ec_get_affine (x, y, point, ec))
{
log_error ("eddsa_encodepoint: Failed to get affine coordinates\n");
rc = GPG_ERR_INTERNAL;
}
else
- rc = eddsa_encode_x_y (x, y, ec->nbits/8, with_prefix, r_buffer, r_buflen);
+ rc = eddsa_encode_x_y (x, y, (ec->nbits+7)/8, with_prefix, r_buffer, r_buflen);
if (!x_in)
mpi_free (x);
if (!y_in)
mpi_free (y);
return rc;
}
/* Make sure that the opaque MPI VALUE is in compact EdDSA format.
This function updates MPI if needed. */
gpg_err_code_t
_gcry_ecc_eddsa_ensure_compact (gcry_mpi_t value, unsigned int nbits)
{
gpg_err_code_t rc;
const unsigned char *buf;
unsigned int rawmpilen;
gcry_mpi_t x, y;
unsigned char *enc;
unsigned int enclen;
if (!mpi_is_opaque (value))
return GPG_ERR_INV_OBJ;
buf = mpi_get_opaque (value, &rawmpilen);
if (!buf)
return GPG_ERR_INV_OBJ;
rawmpilen = (rawmpilen + 7)/8;
if (rawmpilen > 1 && (rawmpilen%2))
{
if (buf[0] == 0x04)
{
/* Buffer is in SEC1 uncompressed format. Extract y and
compress. */
rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_USG,
buf+1, (rawmpilen-1)/2, NULL);
if (rc)
return rc;
rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_USG,
buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2, NULL);
if (rc)
{
mpi_free (x);
return rc;
}
rc = eddsa_encode_x_y (x, y, (nbits+7)/8, 0, &enc, &enclen);
mpi_free (x);
mpi_free (y);
if (rc)
return rc;
mpi_set_opaque (value, enc, 8*enclen);
}
else if (buf[0] == 0x40)
{
/* Buffer is compressed but with our SEC1 alike compression
indicator. Remove that byte. FIXME: We should write and
use a function to manipulate an opaque MPI in place. */
if (!_gcry_mpi_set_opaque_copy (value, buf + 1, (rawmpilen - 1)*8))
return gpg_err_code_from_syserror ();
}
}
return 0;
}
/* 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)
{
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) */
mpi_sub (t, ec->p, t);
if (!mpi_cmp (t, u))
{
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) */
mpi_sub (t, ec->p, t);
if (!mpi_cmp (t, u))
rc = GPG_ERR_INV_OBJ;
}
/* Choose the desired square root according to parity */
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);
return rc;
}
/* 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
caller. In contrast to the supplied PK, this is not an MPI and
thus guaranteed to be properly padded. R_ENCPKLEN receives the
length of that encoded key. */
gpg_err_code_t
_gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
unsigned char **r_encpk, unsigned int *r_encpklen)
{
gpg_err_code_t rc;
unsigned char *rawmpi;
unsigned int rawmpilen;
int sign;
if (mpi_is_opaque (pk))
{
const unsigned char *buf;
buf = mpi_get_opaque (pk, &rawmpilen);
if (!buf)
return GPG_ERR_INV_OBJ;
rawmpilen = (rawmpilen + 7)/8;
/* Handle compression prefixes. The size of the buffer will be
odd in this case. */
if (rawmpilen > 1 && (rawmpilen%2))
{
/* First check whether the public key has been given in
standard uncompressed format (SEC1). No need to recover
x in this case. */
if (buf[0] == 0x04)
{
gcry_mpi_t x, y;
rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_USG,
buf+1, (rawmpilen-1)/2, NULL);
if (rc)
return rc;
rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_USG,
buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2,NULL);
if (rc)
{
mpi_free (x);
return rc;
}
if (r_encpk)
{
- rc = eddsa_encode_x_y (x, y, ctx->nbits/8, 0,
+ rc = eddsa_encode_x_y (x, y, (ctx->nbits+7)/8, 0,
r_encpk, r_encpklen);
if (rc)
{
mpi_free (x);
mpi_free (y);
return rc;
}
}
mpi_snatch (result->x, x);
mpi_snatch (result->y, y);
mpi_set_ui (result->z, 1);
return 0;
}
/* Check whether the public key has been prefixed with a 0x40
byte to explicitly indicate compressed format using a SEC1
alike prefix byte. This is a Libgcrypt extension. */
if (buf[0] == 0x40)
{
rawmpilen--;
buf++;
}
}
/* EdDSA compressed point. */
rawmpi = xtrymalloc (rawmpilen? rawmpilen:1);
if (!rawmpi)
return gpg_err_code_from_syserror ();
memcpy (rawmpi, buf, rawmpilen);
reverse_buffer (rawmpi, rawmpilen);
}
else
{
/* Note: Without using an opaque MPI it is not reliable possible
to find out whether the public key has been given in
uncompressed format. Thus we expect native EdDSA format. */
- rawmpi = _gcry_mpi_get_buffer (pk, ctx->nbits/8, &rawmpilen, NULL);
+ rawmpi = _gcry_mpi_get_buffer (pk, (ctx->nbits+7)/8, &rawmpilen, NULL);
if (!rawmpi)
return gpg_err_code_from_syserror ();
}
if (rawmpilen)
{
sign = !!(rawmpi[0] & 0x80);
rawmpi[0] &= 0x7f;
}
else
sign = 0;
_gcry_mpi_set_buffer (result->y, rawmpi, rawmpilen, 0);
if (r_encpk)
{
/* Revert to little endian. */
if (sign && rawmpilen)
rawmpi[0] |= 0x80;
reverse_buffer (rawmpi, rawmpilen);
*r_encpk = rawmpi;
if (r_encpklen)
*r_encpklen = rawmpilen;
}
else
xfree (rawmpi);
rc = _gcry_ecc_eddsa_recover_x (result->x, result->y, sign, ctx);
mpi_set_ui (result->z, 1);
return rc;
}
/* Compute the A value as used by EdDSA. The caller needs to provide
the context EC and the actual secret D as an MPI. The function
returns a newly allocated 64 byte buffer at r_digest; the first 32
bytes represent the A value. NULL is returned on error and NULL
stored at R_DIGEST. */
gpg_err_code_t
_gcry_ecc_eddsa_compute_h_d (unsigned char **r_digest, mpi_ec_t ec)
{
gpg_err_code_t rc;
unsigned char *rawmpi = NULL;
unsigned int rawmpilen;
unsigned char *digest;
gcry_buffer_t hvec[2];
int hashalgo, b;
*r_digest = NULL;
hashalgo = GCRY_MD_SHA512;
if (hashalgo != GCRY_MD_SHA512)
return GPG_ERR_DIGEST_ALGO;
b = (ec->nbits+7)/8;
if (b != 256/8)
return GPG_ERR_INTERNAL; /* We only support 256 bit. */
/* Note that we clear DIGEST so we can use it as input to left pad
the key with zeroes for hashing. */
digest = xtrycalloc_secure (2, b);
if (!digest)
return gpg_err_code_from_syserror ();
memset (hvec, 0, sizeof hvec);
rawmpi = _gcry_mpi_get_buffer (ec->d, 0, &rawmpilen, NULL);
if (!rawmpi)
{
xfree (digest);
return gpg_err_code_from_syserror ();
}
hvec[0].data = digest;
hvec[0].off = 0;
hvec[0].len = b > rawmpilen? b - rawmpilen : 0;
hvec[1].data = rawmpi;
hvec[1].off = 0;
hvec[1].len = rawmpilen;
rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
xfree (rawmpi);
if (rc)
{
xfree (digest);
return rc;
}
/* Compute the A value. */
reverse_buffer (digest, 32); /* Only the first half of the hash. */
digest[0] = (digest[0] & 0x7f) | 0x40;
digest[31] &= 0xf8;
*r_digest = digest;
return 0;
}
/**
* _gcry_ecc_eddsa_genkey - EdDSA version of the key generation.
*
* @ec: Elliptic curve computation context.
* @flags: Flags controlling aspects of the creation.
*
* Return: An error code.
*
* The only @flags bit used by this function is %PUBKEY_FLAG_TRANSIENT
* to use a faster RNG.
*/
gpg_err_code_t
_gcry_ecc_eddsa_genkey (mpi_ec_t ec, int flags)
{
gpg_err_code_t rc;
int b = 256/8; /* The only size we currently support. */
gcry_mpi_t a, x, y;
mpi_point_struct Q;
gcry_random_level_t random_level;
char *dbuf;
size_t dlen;
gcry_buffer_t hvec[1];
unsigned char *hash_d = NULL;
point_init (&Q);
memset (hvec, 0, sizeof hvec);
if ((flags & PUBKEY_FLAG_TRANSIENT_KEY))
random_level = GCRY_STRONG_RANDOM;
else
random_level = GCRY_VERY_STRONG_RANDOM;
a = mpi_snew (0);
x = mpi_new (0);
y = mpi_new (0);
/* Generate a secret. */
hash_d = xtrymalloc_secure (2*b);
if (!hash_d)
{
rc = gpg_err_code_from_syserror ();
goto leave;
}
dlen = b;
dbuf = _gcry_random_bytes_secure (dlen, random_level);
/* Compute the A value. */
hvec[0].data = dbuf;
hvec[0].len = dlen;
rc = _gcry_md_hash_buffers (GCRY_MD_SHA512, 0, hash_d, hvec, 1);
if (rc)
goto leave;
ec->d = _gcry_mpi_set_opaque (NULL, dbuf, dlen*8);
dbuf = NULL;
reverse_buffer (hash_d, 32); /* Only the first half of the hash. */
hash_d[0] = (hash_d[0] & 0x7f) | 0x40;
hash_d[31] &= 0xf8;
_gcry_mpi_set_buffer (a, hash_d, 32, 0);
xfree (hash_d); hash_d = NULL;
/* log_printmpi ("ecgen a", a); */
/* Compute Q. */
_gcry_mpi_ec_mul_point (&Q, a, ec->G, ec);
if (DBG_CIPHER)
log_printpnt ("ecgen pk", &Q, ec);
ec->Q = mpi_point_snatch_set (NULL, Q.x, Q.y, Q.z);
Q.x = NULL;
Q.y = NULL;
Q.x = NULL;
leave:
_gcry_mpi_release (a);
_gcry_mpi_release (x);
_gcry_mpi_release (y);
xfree (hash_d);
return rc;
}
/* Compute an EdDSA signature. See:
* [ed25519] 23pp. (PDF) Daniel J. Bernstein, Niels Duif, Tanja
* Lange, Peter Schwabe, Bo-Yin Yang. High-speed high-security
* signatures. Journal of Cryptographic Engineering 2 (2012), 77-89.
* Document ID: a1a62a2f76d23f65d622484ddd09caf8.
* URL: http://cr.yp.to/papers.html#ed25519. Date: 2011.09.26.
*
* Despite that this function requires the specification of a hash
* algorithm, we only support what has been specified by the paper.
* This may change in the future. Note that we don't check the used
* curve; the user is responsible to use Ed25519.
*
* Return the signature struct (r,s) from the message hash. The caller
* must have allocated R_R and S.
*/
gpg_err_code_t
_gcry_ecc_eddsa_sign (gcry_mpi_t input, mpi_ec_t ec,
gcry_mpi_t r_r, gcry_mpi_t s, int hashalgo)
{
int rc;
int b;
unsigned int tmp;
unsigned char *digest = NULL;
gcry_buffer_t hvec[3];
const void *mbuf;
size_t mlen;
unsigned char *rawmpi = NULL;
unsigned int rawmpilen;
unsigned char *encpk = NULL; /* Encoded public key. */
unsigned int encpklen;
mpi_point_struct I; /* Intermediate value. */
gcry_mpi_t a, x, y, r;
memset (hvec, 0, sizeof hvec);
if (!mpi_is_opaque (input))
return GPG_ERR_INV_DATA;
/* Initialize some helpers. */
point_init (&I);
a = mpi_snew (0);
x = mpi_new (0);
y = mpi_new (0);
r = mpi_snew (0);
b = (ec->nbits+7)/8;
if (b != 256/8)
{
rc = GPG_ERR_INTERNAL; /* We only support 256 bit. */
goto leave;
}
rc = _gcry_ecc_eddsa_compute_h_d (&digest, ec);
if (rc)
goto leave;
_gcry_mpi_set_buffer (a, digest, 32, 0);
/* Compute the public key if it's not available (only secret part). */
if (ec->Q == NULL)
{
mpi_point_struct Q;
point_init (&Q);
_gcry_mpi_ec_mul_point (&Q, a, ec->G, ec);
ec->Q = mpi_point_snatch_set (NULL, Q.x, Q.y, Q.z);
}
rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, x, y, 0, &encpk, &encpklen);
if (rc)
goto leave;
if (DBG_CIPHER)
log_printhex (" e_pk", encpk, encpklen);
/* Compute R. */
mbuf = mpi_get_opaque (input, &tmp);
mlen = (tmp +7)/8;
if (DBG_CIPHER)
log_printhex (" m", mbuf, mlen);
hvec[0].data = digest;
hvec[0].off = 32;
hvec[0].len = 32;
hvec[1].data = (char*)mbuf;
hvec[1].len = mlen;
rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2);
if (rc)
goto leave;
reverse_buffer (digest, 64);
if (DBG_CIPHER)
log_printhex (" r", digest, 64);
_gcry_mpi_set_buffer (r, digest, 64, 0);
_gcry_mpi_ec_mul_point (&I, r, ec->G, ec);
if (DBG_CIPHER)
log_printpnt (" r", &I, ec);
/* Convert R into affine coordinates and apply encoding. */
rc = _gcry_ecc_eddsa_encodepoint (&I, ec, x, y, 0, &rawmpi, &rawmpilen);
if (rc)
goto leave;
if (DBG_CIPHER)
log_printhex (" e_r", rawmpi, rawmpilen);
/* S = r + a * H(encodepoint(R) + encodepoint(pk) + m) mod n */
hvec[0].data = rawmpi; /* (this is R) */
hvec[0].off = 0;
hvec[0].len = rawmpilen;
hvec[1].data = encpk;
hvec[1].off = 0;
hvec[1].len = encpklen;
hvec[2].data = (char*)mbuf;
hvec[2].off = 0;
hvec[2].len = mlen;
rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
if (rc)
goto leave;
/* No more need for RAWMPI thus we now transfer it to R_R. */
mpi_set_opaque (r_r, rawmpi, rawmpilen*8);
rawmpi = NULL;
reverse_buffer (digest, 64);
if (DBG_CIPHER)
log_printhex (" H(R+)", digest, 64);
_gcry_mpi_set_buffer (s, digest, 64, 0);
mpi_mulm (s, s, a, ec->n);
mpi_addm (s, s, r, ec->n);
rc = eddsa_encodempi (s, b, &rawmpi, &rawmpilen);
if (rc)
goto leave;
if (DBG_CIPHER)
log_printhex (" e_s", rawmpi, rawmpilen);
mpi_set_opaque (s, rawmpi, rawmpilen*8);
rawmpi = NULL;
rc = 0;
leave:
_gcry_mpi_release (a);
_gcry_mpi_release (x);
_gcry_mpi_release (y);
_gcry_mpi_release (r);
xfree (digest);
point_free (&I);
xfree (encpk);
xfree (rawmpi);
return rc;
}
/* Verify an EdDSA signature. See sign_eddsa for the reference.
* Check if R_IN and S_IN verifies INPUT.
*/
gpg_err_code_t
_gcry_ecc_eddsa_verify (gcry_mpi_t input, mpi_ec_t ec,
gcry_mpi_t r_in, gcry_mpi_t s_in, int hashalgo)
{
int rc;
int b;
unsigned int tmp;
unsigned char *encpk = NULL; /* Encoded public key. */
unsigned int encpklen;
const void *mbuf, *rbuf;
unsigned char *tbuf = NULL;
size_t mlen, rlen;
unsigned int tlen;
unsigned char digest[64];
gcry_buffer_t hvec[3];
gcry_mpi_t h, s;
mpi_point_struct Ia, Ib;
if (!mpi_is_opaque (input) || !mpi_is_opaque (r_in) || !mpi_is_opaque (s_in))
return GPG_ERR_INV_DATA;
if (hashalgo != GCRY_MD_SHA512)
return GPG_ERR_DIGEST_ALGO;
point_init (&Ia);
point_init (&Ib);
h = mpi_new (0);
s = mpi_new (0);
- b = ec->nbits/8;
+ b = (ec->nbits+7)/8;
if (b != 256/8)
{
rc = GPG_ERR_INTERNAL; /* We only support 256 bit. */
goto leave;
}
/* Encode and check the public key. */
rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL, 0,
&encpk, &encpklen);
if (rc)
goto leave;
if (!_gcry_mpi_ec_curve_point (ec->Q, ec))
{
rc = GPG_ERR_BROKEN_PUBKEY;
goto leave;
}
if (DBG_CIPHER)
log_printhex (" e_pk", encpk, encpklen);
if (encpklen != b)
{
rc = GPG_ERR_INV_LENGTH;
goto leave;
}
/* Convert the other input parameters. */
mbuf = mpi_get_opaque (input, &tmp);
mlen = (tmp +7)/8;
if (DBG_CIPHER)
log_printhex (" m", mbuf, mlen);
rbuf = mpi_get_opaque (r_in, &tmp);
rlen = (tmp +7)/8;
if (DBG_CIPHER)
log_printhex (" r", rbuf, rlen);
if (rlen != b)
{
rc = GPG_ERR_INV_LENGTH;
goto leave;
}
/* h = H(encodepoint(R) + encodepoint(pk) + m) */
hvec[0].data = (char*)rbuf;
hvec[0].off = 0;
hvec[0].len = rlen;
hvec[1].data = encpk;
hvec[1].off = 0;
hvec[1].len = encpklen;
hvec[2].data = (char*)mbuf;
hvec[2].off = 0;
hvec[2].len = mlen;
rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3);
if (rc)
goto leave;
reverse_buffer (digest, 64);
if (DBG_CIPHER)
log_printhex (" H(R+)", digest, 64);
_gcry_mpi_set_buffer (h, digest, 64, 0);
/* According to the paper the best way for verification is:
encodepoint(sG - h·Q) = encodepoint(r)
because we don't need to decode R. */
{
void *sbuf;
unsigned int slen;
sbuf = _gcry_mpi_get_opaque_copy (s_in, &tmp);
slen = (tmp +7)/8;
reverse_buffer (sbuf, slen);
if (DBG_CIPHER)
log_printhex (" s", sbuf, slen);
_gcry_mpi_set_buffer (s, sbuf, slen, 0);
xfree (sbuf);
if (slen != b)
{
rc = GPG_ERR_INV_LENGTH;
goto leave;
}
}
_gcry_mpi_ec_mul_point (&Ia, s, ec->G, ec);
_gcry_mpi_ec_mul_point (&Ib, h, ec->Q, ec);
_gcry_mpi_sub (Ib.x, ec->p, Ib.x);
_gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ec);
rc = _gcry_ecc_eddsa_encodepoint (&Ia, ec, s, h, 0, &tbuf, &tlen);
if (rc)
goto leave;
if (tlen != rlen || memcmp (tbuf, rbuf, tlen))
{
rc = GPG_ERR_BAD_SIGNATURE;
goto leave;
}
rc = 0;
leave:
xfree (encpk);
xfree (tbuf);
_gcry_mpi_release (s);
_gcry_mpi_release (h);
point_free (&Ia);
point_free (&Ib);
return rc;
}
diff --git a/mpi/ec.c b/mpi/ec.c
index d4c4f953..ba5c954d 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -1,2076 +1,2073 @@
/* ec.c - Elliptic Curve functions
* Copyright (C) 2007 Free Software Foundation, Inc.
* Copyright (C) 2013 g10 Code GmbH
*
* This file is part of Libgcrypt.
*
* Libgcrypt is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as
* published by the Free Software Foundation; either version 2.1 of
* the License, or (at your option) any later version.
*
* Libgcrypt is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this program; if not, see .
*/
#include
#include
#include
#include
#include "mpi-internal.h"
#include "longlong.h"
#include "g10lib.h"
#include "context.h"
#include "ec-context.h"
#include "ec-internal.h"
extern void reverse_buffer (unsigned char *buffer, unsigned int length);
#define point_init(a) _gcry_mpi_point_init ((a))
#define point_free(a) _gcry_mpi_point_free_parts ((a))
/* Print a point using the log functions. If CTX is not NULL affine
coordinates will be printed. */
void
_gcry_mpi_point_log (const char *name, mpi_point_t point, mpi_ec_t ctx)
{
gcry_mpi_t x, y;
char buf[100];
if (!point)
{
snprintf (buf, sizeof buf - 1, "%s.*", name);
log_mpidump (buf, NULL);
return;
}
snprintf (buf, sizeof buf - 1, "%s.X", name);
if (ctx)
{
x = mpi_new (0);
y = mpi_new (0);
}
if (!ctx || _gcry_mpi_ec_get_affine (x, y, point, ctx))
{
log_mpidump (buf, point->x);
buf[strlen(buf)-1] = 'Y';
log_mpidump (buf, point->y);
buf[strlen(buf)-1] = 'Z';
log_mpidump (buf, point->z);
}
else
{
buf[strlen(buf)-1] = 'x';
log_mpidump (buf, x);
buf[strlen(buf)-1] = 'y';
log_mpidump (buf, y);
}
if (ctx)
{
_gcry_mpi_release (x);
_gcry_mpi_release (y);
}
}
/* Create a new point option. NBITS gives the size in bits of one
coordinate; it is only used to pre-allocate some resources and
might also be passed as 0 to use a default value. */
mpi_point_t
_gcry_mpi_point_new (unsigned int nbits)
{
mpi_point_t p;
(void)nbits; /* Currently not used. */
p = xmalloc (sizeof *p);
_gcry_mpi_point_init (p);
return p;
}
/* Release the point object P. P may be NULL. */
void
_gcry_mpi_point_release (mpi_point_t p)
{
if (p)
{
_gcry_mpi_point_free_parts (p);
xfree (p);
}
}
/* Initialize the fields of a point object. gcry_mpi_point_free_parts
may be used to release the fields. */
void
_gcry_mpi_point_init (mpi_point_t p)
{
p->x = mpi_new (0);
p->y = mpi_new (0);
p->z = mpi_new (0);
}
/* Release the parts of a point object. */
void
_gcry_mpi_point_free_parts (mpi_point_t p)
{
mpi_free (p->x); p->x = NULL;
mpi_free (p->y); p->y = NULL;
mpi_free (p->z); p->z = NULL;
}
/* Set the value from S into D. */
static void
point_set (mpi_point_t d, mpi_point_t s)
{
mpi_set (d->x, s->x);
mpi_set (d->y, s->y);
mpi_set (d->z, s->z);
}
/* Return a copy of POINT. */
gcry_mpi_point_t
_gcry_mpi_point_copy (gcry_mpi_point_t point)
{
mpi_point_t newpoint;
newpoint = _gcry_mpi_point_new (0);
if (point)
point_set (newpoint, point);
return newpoint;
}
static void
point_resize (mpi_point_t p, mpi_ec_t ctx)
{
size_t nlimbs = ctx->p->nlimbs;
mpi_resize (p->x, nlimbs);
p->x->nlimbs = nlimbs;
mpi_resize (p->z, nlimbs);
p->z->nlimbs = nlimbs;
if (ctx->model != MPI_EC_MONTGOMERY)
{
mpi_resize (p->y, nlimbs);
p->y->nlimbs = nlimbs;
}
}
static void
point_swap_cond (mpi_point_t d, mpi_point_t s, unsigned long swap,
mpi_ec_t ctx)
{
mpi_swap_cond (d->x, s->x, swap);
if (ctx->model != MPI_EC_MONTGOMERY)
mpi_swap_cond (d->y, s->y, swap);
mpi_swap_cond (d->z, s->z, swap);
}
/* Set the projective coordinates from POINT into X, Y, and Z. If a
coordinate is not required, X, Y, or Z may be passed as NULL. */
void
_gcry_mpi_point_get (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z,
mpi_point_t point)
{
if (x)
mpi_set (x, point->x);
if (y)
mpi_set (y, point->y);
if (z)
mpi_set (z, point->z);
}
/* Set the projective coordinates from POINT into X, Y, and Z and
release POINT. If a coordinate is not required, X, Y, or Z may be
passed as NULL. */
void
_gcry_mpi_point_snatch_get (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z,
mpi_point_t point)
{
mpi_snatch (x, point->x);
mpi_snatch (y, point->y);
mpi_snatch (z, point->z);
xfree (point);
}
/* Set the projective coordinates from X, Y, and Z into POINT. If a
coordinate is given as NULL, the value 0 is stored into point. If
POINT is given as NULL a new point object is allocated. Returns
POINT or the newly allocated point object. */
mpi_point_t
_gcry_mpi_point_set (mpi_point_t point,
gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z)
{
if (!point)
point = mpi_point_new (0);
if (x)
mpi_set (point->x, x);
else
mpi_clear (point->x);
if (y)
mpi_set (point->y, y);
else
mpi_clear (point->y);
if (z)
mpi_set (point->z, z);
else
mpi_clear (point->z);
return point;
}
/* Set the projective coordinates from X, Y, and Z into POINT. If a
coordinate is given as NULL, the value 0 is stored into point. If
POINT is given as NULL a new point object is allocated. The
coordinates X, Y, and Z are released. Returns POINT or the newly
allocated point object. */
mpi_point_t
_gcry_mpi_point_snatch_set (mpi_point_t point,
gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z)
{
if (!point)
point = mpi_point_new (0);
if (x)
mpi_snatch (point->x, x);
else
mpi_clear (point->x);
if (y)
mpi_snatch (point->y, y);
else
mpi_clear (point->y);
if (z)
mpi_snatch (point->z, z);
else
mpi_clear (point->z);
return point;
}
/* W = W mod P. */
static void
ec_mod (gcry_mpi_t w, mpi_ec_t ec)
{
if (0 && ec->dialect == ECC_DIALECT_ED25519)
_gcry_mpi_ec_ed25519_mod (w);
else if (ec->t.p_barrett)
_gcry_mpi_mod_barrett (w, w, ec->t.p_barrett);
else
_gcry_mpi_mod (w, w, ec->p);
}
static void
ec_addm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
{
mpi_add (w, u, v);
ec_mod (w, ctx);
}
static void
ec_subm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ec)
{
mpi_sub (w, u, v);
while (w->sign)
mpi_add (w, w, ec->p);
/*ec_mod (w, ec);*/
}
static void
ec_mulm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
{
mpi_mul (w, u, v);
ec_mod (w, ctx);
}
/* W = 2 * U mod P. */
static void
ec_mul2 (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx)
{
mpi_lshift (w, u, 1);
ec_mod (w, ctx);
}
static void
ec_powm (gcry_mpi_t w, const gcry_mpi_t b, const gcry_mpi_t e,
mpi_ec_t ctx)
{
mpi_powm (w, b, e, ctx->p);
/* _gcry_mpi_abs (w); */
}
/* Shortcut for
ec_powm (B, B, mpi_const (MPI_C_TWO), ctx);
for easier optimization. */
static void
ec_pow2 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx)
{
/* Using mpi_mul is slightly faster (at least on amd64). */
/* mpi_powm (w, b, mpi_const (MPI_C_TWO), ctx->p); */
ec_mulm (w, b, b, ctx);
}
/* Shortcut for
ec_powm (B, B, mpi_const (MPI_C_THREE), ctx);
for easier optimization. */
static void
ec_pow3 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx)
{
mpi_powm (w, b, mpi_const (MPI_C_THREE), ctx->p);
}
static void
ec_invm (gcry_mpi_t x, gcry_mpi_t a, mpi_ec_t ctx)
{
if (!mpi_invm (x, a, ctx->p))
{
log_error ("ec_invm: inverse does not exist:\n");
log_mpidump (" a", a);
log_mpidump (" p", ctx->p);
}
}
static void
mpih_set_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, unsigned long set)
{
mpi_size_t i;
mpi_limb_t mask = ((mpi_limb_t)0) - set;
mpi_limb_t x;
for (i = 0; i < usize; i++)
{
x = mask & (wp[i] ^ up[i]);
wp[i] = wp[i] ^ x;
}
}
/* Routines for 2^255 - 19. */
#define LIMB_SIZE_25519 ((256+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB)
static void
ec_addm_25519 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
{
mpi_ptr_t wp, up, vp;
mpi_size_t wsize = LIMB_SIZE_25519;
mpi_limb_t n[LIMB_SIZE_25519];
mpi_limb_t borrow;
if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
log_bug ("addm_25519: different sizes\n");
memset (n, 0, sizeof n);
up = u->d;
vp = v->d;
wp = w->d;
_gcry_mpih_add_n (wp, up, vp, wsize);
borrow = _gcry_mpih_sub_n (wp, wp, ctx->p->d, wsize);
mpih_set_cond (n, ctx->p->d, wsize, (borrow != 0UL));
_gcry_mpih_add_n (wp, wp, n, wsize);
wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
}
static void
ec_subm_25519 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
{
mpi_ptr_t wp, up, vp;
mpi_size_t wsize = LIMB_SIZE_25519;
mpi_limb_t n[LIMB_SIZE_25519];
mpi_limb_t borrow;
if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
log_bug ("subm_25519: different sizes\n");
memset (n, 0, sizeof n);
up = u->d;
vp = v->d;
wp = w->d;
borrow = _gcry_mpih_sub_n (wp, up, vp, wsize);
mpih_set_cond (n, ctx->p->d, wsize, (borrow != 0UL));
_gcry_mpih_add_n (wp, wp, n, wsize);
wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
}
static void
ec_mulm_25519 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
{
mpi_ptr_t wp, up, vp;
mpi_size_t wsize = LIMB_SIZE_25519;
mpi_limb_t n[LIMB_SIZE_25519*2];
mpi_limb_t m[LIMB_SIZE_25519+1];
mpi_limb_t cy;
int msb;
(void)ctx;
if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
log_bug ("mulm_25519: different sizes\n");
up = u->d;
vp = v->d;
wp = w->d;
_gcry_mpih_mul_n (n, up, vp, wsize);
memcpy (wp, n, wsize * BYTES_PER_MPI_LIMB);
wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
memcpy (m, n+LIMB_SIZE_25519-1, (wsize+1) * BYTES_PER_MPI_LIMB);
_gcry_mpih_rshift (m, m, LIMB_SIZE_25519+1, (255 % BITS_PER_MPI_LIMB));
memcpy (n, m, wsize * BYTES_PER_MPI_LIMB);
cy = _gcry_mpih_lshift (m, m, LIMB_SIZE_25519, 4);
m[LIMB_SIZE_25519] = cy;
cy = _gcry_mpih_add_n (m, m, n, wsize);
m[LIMB_SIZE_25519] += cy;
cy = _gcry_mpih_add_n (m, m, n, wsize);
m[LIMB_SIZE_25519] += cy;
cy = _gcry_mpih_add_n (m, m, n, wsize);
m[LIMB_SIZE_25519] += cy;
cy = _gcry_mpih_add_n (wp, wp, m, wsize);
m[LIMB_SIZE_25519] += cy;
memset (m, 0, wsize * BYTES_PER_MPI_LIMB);
msb = (wp[LIMB_SIZE_25519-1] >> (255 % BITS_PER_MPI_LIMB));
m[0] = (m[LIMB_SIZE_25519] * 2 + msb) * 19;
wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB));
_gcry_mpih_add_n (wp, wp, m, wsize);
m[0] = 0;
cy = _gcry_mpih_sub_n (wp, wp, ctx->p->d, wsize);
mpih_set_cond (m, ctx->p->d, wsize, (cy != 0UL));
_gcry_mpih_add_n (wp, wp, m, wsize);
}
static void
ec_mul2_25519 (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx)
{
ec_addm_25519 (w, u, u, ctx);
}
static void
ec_pow2_25519 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx)
{
ec_mulm_25519 (w, b, b, ctx);
}
/* Routines for 2^448 - 2^224 - 1. */
#define LIMB_SIZE_448 ((448+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB)
#define LIMB_SIZE_HALF_448 ((LIMB_SIZE_448+1)/2)
static void
ec_addm_448 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
{
mpi_ptr_t wp, up, vp;
mpi_size_t wsize = LIMB_SIZE_448;
mpi_limb_t n[LIMB_SIZE_448];
mpi_limb_t cy;
if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
log_bug ("addm_448: different sizes\n");
memset (n, 0, sizeof n);
up = u->d;
vp = v->d;
wp = w->d;
cy = _gcry_mpih_add_n (wp, up, vp, wsize);
mpih_set_cond (n, ctx->p->d, wsize, (cy != 0UL));
_gcry_mpih_sub_n (wp, wp, n, wsize);
}
static void
ec_subm_448 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
{
mpi_ptr_t wp, up, vp;
mpi_size_t wsize = LIMB_SIZE_448;
mpi_limb_t n[LIMB_SIZE_448];
mpi_limb_t borrow;
if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
log_bug ("subm_448: different sizes\n");
memset (n, 0, sizeof n);
up = u->d;
vp = v->d;
wp = w->d;
borrow = _gcry_mpih_sub_n (wp, up, vp, wsize);
mpih_set_cond (n, ctx->p->d, wsize, (borrow != 0UL));
_gcry_mpih_add_n (wp, wp, n, wsize);
}
static void
ec_mulm_448 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
{
mpi_ptr_t wp, up, vp;
mpi_size_t wsize = LIMB_SIZE_448;
mpi_limb_t n[LIMB_SIZE_448*2];
mpi_limb_t a2[LIMB_SIZE_HALF_448];
mpi_limb_t a3[LIMB_SIZE_HALF_448];
mpi_limb_t b0[LIMB_SIZE_HALF_448];
mpi_limb_t b1[LIMB_SIZE_HALF_448];
mpi_limb_t cy;
int i;
#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
mpi_limb_t b1_rest, a3_rest;
#endif
if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
log_bug ("mulm_448: different sizes\n");
up = u->d;
vp = v->d;
wp = w->d;
_gcry_mpih_mul_n (n, up, vp, wsize);
for (i = 0; i < (wsize + 1)/ 2; i++)
{
b0[i] = n[i];
b1[i] = n[i+wsize/2];
a2[i] = n[i+wsize];
a3[i] = n[i+wsize+wsize/2];
}
#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
b0[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL<<32)-1;
a2[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL<<32)-1;
b1_rest = 0;
a3_rest = 0;
for (i = (wsize + 1)/ 2 -1; i >= 0; i--)
{
mpi_limb_t b1v, a3v;
b1v = b1[i];
a3v = a3[i];
b1[i] = (b1_rest<<32) | (b1v >> 32);
a3[i] = (a3_rest<<32) | (a3v >> 32);
b1_rest = b1v & (((mpi_limb_t)1UL <<32)-1);
a3_rest = a3v & (((mpi_limb_t)1UL <<32)-1);
}
#endif
cy = _gcry_mpih_add_n (b0, b0, a2, LIMB_SIZE_HALF_448);
cy += _gcry_mpih_add_n (b0, b0, a3, LIMB_SIZE_HALF_448);
for (i = 0; i < (wsize + 1)/ 2; i++)
wp[i] = b0[i];
#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
wp[LIMB_SIZE_HALF_448-1] &= (((mpi_limb_t)1UL <<32)-1);
#endif
#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
cy = b0[LIMB_SIZE_HALF_448-1] >> 32;
#endif
cy = _gcry_mpih_add_1 (b1, b1, LIMB_SIZE_HALF_448, cy);
cy += _gcry_mpih_add_n (b1, b1, a2, LIMB_SIZE_HALF_448);
cy += _gcry_mpih_add_n (b1, b1, a3, LIMB_SIZE_HALF_448);
cy += _gcry_mpih_add_n (b1, b1, a3, LIMB_SIZE_HALF_448);
#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
b1_rest = 0;
for (i = (wsize + 1)/ 2 -1; i >= 0; i--)
{
mpi_limb_t b1v = b1[i];
b1[i] = (b1_rest<<32) | (b1v >> 32);
b1_rest = b1v & (((mpi_limb_t)1UL <<32)-1);
}
wp[LIMB_SIZE_HALF_448-1] |= (b1_rest << 32);
#endif
for (i = 0; i < wsize / 2; i++)
wp[i+(wsize + 1) / 2] = b1[i];
#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
cy = b1[LIMB_SIZE_HALF_448-1];
#endif
memset (n, 0, wsize * BYTES_PER_MPI_LIMB);
#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2)
n[LIMB_SIZE_HALF_448-1] = cy << 32;
#else
n[LIMB_SIZE_HALF_448] = cy;
#endif
n[0] = cy;
_gcry_mpih_add_n (wp, wp, n, wsize);
memset (n, 0, wsize * BYTES_PER_MPI_LIMB);
cy = _gcry_mpih_sub_n (wp, wp, ctx->p->d, wsize);
mpih_set_cond (n, ctx->p->d, wsize, (cy != 0UL));
_gcry_mpih_add_n (wp, wp, n, wsize);
}
static void
ec_mul2_448 (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx)
{
ec_addm_448 (w, u, u, ctx);
}
static void
ec_pow2_448 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx)
{
ec_mulm_448 (w, b, b, ctx);
}
struct field_table {
const char *p;
/* computation routines for the field. */
void (* addm) (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx);
void (* subm) (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx);
void (* mulm) (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx);
void (* mul2) (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx);
void (* pow2) (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx);
};
static const struct field_table field_table[] = {
{
"0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED",
ec_addm_25519,
ec_subm_25519,
ec_mulm_25519,
ec_mul2_25519,
ec_pow2_25519
},
{
"0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE"
"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
ec_addm_448,
ec_subm_448,
ec_mulm_448,
ec_mul2_448,
ec_pow2_448
},
{ NULL, NULL, NULL, NULL, NULL, NULL },
};
/* Force recomputation of all helper variables. */
void
_gcry_mpi_ec_get_reset (mpi_ec_t ec)
{
ec->t.valid.a_is_pminus3 = 0;
ec->t.valid.two_inv_p = 0;
}
/* Accessor for helper variable. */
static int
ec_get_a_is_pminus3 (mpi_ec_t ec)
{
gcry_mpi_t tmp;
if (!ec->t.valid.a_is_pminus3)
{
ec->t.valid.a_is_pminus3 = 1;
tmp = mpi_alloc_like (ec->p);
mpi_sub_ui (tmp, ec->p, 3);
ec->t.a_is_pminus3 = !mpi_cmp (ec->a, tmp);
mpi_free (tmp);
}
return ec->t.a_is_pminus3;
}
/* Accessor for helper variable. */
static gcry_mpi_t
ec_get_two_inv_p (mpi_ec_t ec)
{
if (!ec->t.valid.two_inv_p)
{
ec->t.valid.two_inv_p = 1;
if (!ec->t.two_inv_p)
ec->t.two_inv_p = mpi_alloc (0);
ec_invm (ec->t.two_inv_p, mpi_const (MPI_C_TWO), ec);
}
return ec->t.two_inv_p;
}
static const char *const curve25519_bad_points[] = {
"0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed",
"0x0000000000000000000000000000000000000000000000000000000000000000",
"0x0000000000000000000000000000000000000000000000000000000000000001",
"0x00b8495f16056286fdb1329ceb8d09da6ac49ff1fae35616aeb8413b7c7aebe0",
"0x57119fd0dd4e22d8868e1c58c45c44045bef839c55b1d0b1248c50a3bc959c5f",
"0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec",
"0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffee",
NULL
};
static const char *const curve448_bad_points[] = {
"0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
"ffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
"0x00000000000000000000000000000000000000000000000000000000"
"00000000000000000000000000000000000000000000000000000000",
"0x00000000000000000000000000000000000000000000000000000000"
"00000000000000000000000000000000000000000000000000000001",
"0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
"fffffffffffffffffffffffffffffffffffffffffffffffffffffffe",
"0xffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
"00000000000000000000000000000000000000000000000000000000",
NULL
};
static const char *const *bad_points_table[] = {
curve25519_bad_points,
curve448_bad_points,
};
static gcry_mpi_t
scanval (const char *string)
{
gpg_err_code_t rc;
gcry_mpi_t val;
rc = _gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
if (rc)
log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (rc));
return val;
}
/* This function initialized a context for elliptic curve based on the
field GF(p). P is the prime specifying this field, A is the first
coefficient. CTX is expected to be zeroized. */
static void
ec_p_init (mpi_ec_t ctx, enum gcry_mpi_ec_models model,
enum ecc_dialects dialect,
int flags,
gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
{
int i;
static int use_barrett;
if (!use_barrett)
{
if (getenv ("GCRYPT_BARRETT"))
use_barrett = 1;
else
use_barrett = -1;
}
/* Fixme: Do we want to check some constraints? e.g. a < p */
ctx->model = model;
ctx->dialect = dialect;
ctx->flags = flags;
- if (dialect == ECC_DIALECT_ED25519)
- ctx->nbits = 256;
- else
- ctx->nbits = mpi_get_nbits (p);
+ ctx->nbits = mpi_get_nbits (p);
ctx->p = mpi_copy (p);
ctx->a = mpi_copy (a);
ctx->b = mpi_copy (b);
ctx->t.p_barrett = use_barrett > 0? _gcry_mpi_barrett_init (ctx->p, 0):NULL;
_gcry_mpi_ec_get_reset (ctx);
if (model == MPI_EC_MONTGOMERY)
{
for (i=0; i< DIM(bad_points_table); i++)
{
gcry_mpi_t p_candidate = scanval (bad_points_table[i][0]);
int match_p = !mpi_cmp (ctx->p, p_candidate);
int j;
mpi_free (p_candidate);
if (!match_p)
continue;
for (j=0; i< DIM(ctx->t.scratch) && bad_points_table[i][j]; j++)
ctx->t.scratch[j] = scanval (bad_points_table[i][j]);
}
}
else
{
/* Allocate scratch variables. */
for (i=0; i< DIM(ctx->t.scratch); i++)
ctx->t.scratch[i] = mpi_alloc_like (ctx->p);
}
ctx->addm = ec_addm;
ctx->subm = ec_subm;
ctx->mulm = ec_mulm;
ctx->mul2 = ec_mul2;
ctx->pow2 = ec_pow2;
for (i=0; field_table[i].p; i++)
{
gcry_mpi_t f_p;
gpg_err_code_t rc;
rc = _gcry_mpi_scan (&f_p, GCRYMPI_FMT_HEX, field_table[i].p, 0, NULL);
if (rc)
log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (rc));
if (!mpi_cmp (p, f_p))
{
ctx->addm = field_table[i].addm;
ctx->subm = field_table[i].subm;
ctx->mulm = field_table[i].mulm;
ctx->mul2 = field_table[i].mul2;
ctx->pow2 = field_table[i].pow2;
_gcry_mpi_release (f_p);
mpi_resize (ctx->a, ctx->p->nlimbs);
ctx->a->nlimbs = ctx->p->nlimbs;
mpi_resize (ctx->b, ctx->p->nlimbs);
ctx->b->nlimbs = ctx->p->nlimbs;
for (i=0; i< DIM(ctx->t.scratch) && ctx->t.scratch[i]; i++)
ctx->t.scratch[i]->nlimbs = ctx->p->nlimbs;
break;
}
_gcry_mpi_release (f_p);
}
/* Prepare for fast reduction. */
/* FIXME: need a test for NIST values. However it does not gain us
any real advantage, for 384 bits it is actually slower than using
mpi_mulm. */
/* ctx->nist_nbits = mpi_get_nbits (ctx->p); */
/* if (ctx->nist_nbits == 192) */
/* { */
/* for (i=0; i < 4; i++) */
/* ctx->s[i] = mpi_new (192); */
/* ctx->c = mpi_new (192*2); */
/* } */
/* else if (ctx->nist_nbits == 384) */
/* { */
/* for (i=0; i < 10; i++) */
/* ctx->s[i] = mpi_new (384); */
/* ctx->c = mpi_new (384*2); */
/* } */
}
static void
ec_deinit (void *opaque)
{
mpi_ec_t ctx = opaque;
int i;
_gcry_mpi_barrett_free (ctx->t.p_barrett);
/* Domain parameter. */
mpi_free (ctx->p);
mpi_free (ctx->a);
mpi_free (ctx->b);
_gcry_mpi_point_release (ctx->G);
mpi_free (ctx->n);
/* The key. */
_gcry_mpi_point_release (ctx->Q);
mpi_free (ctx->d);
/* Private data of ec.c. */
mpi_free (ctx->t.two_inv_p);
for (i=0; i< DIM(ctx->t.scratch); i++)
mpi_free (ctx->t.scratch[i]);
/* if (ctx->nist_nbits == 192) */
/* { */
/* for (i=0; i < 4; i++) */
/* mpi_free (ctx->s[i]); */
/* mpi_free (ctx->c); */
/* } */
/* else if (ctx->nist_nbits == 384) */
/* { */
/* for (i=0; i < 10; i++) */
/* mpi_free (ctx->s[i]); */
/* mpi_free (ctx->c); */
/* } */
}
/* This function returns a new context for elliptic curve based on the
field GF(p). P is the prime specifying this field, A is the first
coefficient, B is the second coefficient, and MODEL is the model
for the curve. This function is only used within Libgcrypt and not
part of the public API.
This context needs to be released using _gcry_mpi_ec_free. */
mpi_ec_t
_gcry_mpi_ec_p_internal_new (enum gcry_mpi_ec_models model,
enum ecc_dialects dialect,
int flags,
gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
{
mpi_ec_t ctx;
ctx = xcalloc (1, sizeof *ctx);
ec_p_init (ctx, model, dialect, flags, p, a, b);
return ctx;
}
/* This is a variant of _gcry_mpi_ec_p_internal_new which returns an
public context and does some error checking on the supplied
arguments. On success the new context is stored at R_CTX and 0 is
returned; on error NULL is stored at R_CTX and an error code is
returned.
The context needs to be released using gcry_ctx_release. */
gpg_err_code_t
_gcry_mpi_ec_p_new (gcry_ctx_t *r_ctx,
enum gcry_mpi_ec_models model,
enum ecc_dialects dialect,
int flags,
gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b)
{
gcry_ctx_t ctx;
mpi_ec_t ec;
*r_ctx = NULL;
if (!p || !a)
return GPG_ERR_EINVAL;
ctx = _gcry_ctx_alloc (CONTEXT_TYPE_EC, sizeof *ec, ec_deinit);
if (!ctx)
return gpg_err_code_from_syserror ();
ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
ec_p_init (ec, model, dialect, flags, p, a, b);
*r_ctx = ctx;
return 0;
}
void
_gcry_mpi_ec_free (mpi_ec_t ctx)
{
if (ctx)
{
ec_deinit (ctx);
xfree (ctx);
}
}
gcry_mpi_t
_gcry_mpi_ec_get_mpi (const char *name, gcry_ctx_t ctx, int copy)
{
mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
return _gcry_ecc_get_mpi (name, ec, copy);
}
gcry_mpi_point_t
_gcry_mpi_ec_get_point (const char *name, gcry_ctx_t ctx, int copy)
{
mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
(void)copy; /* Not used. */
return _gcry_ecc_get_point (name, ec);
}
gpg_err_code_t
_gcry_mpi_ec_set_mpi (const char *name, gcry_mpi_t newvalue,
gcry_ctx_t ctx)
{
mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
return _gcry_ecc_set_mpi (name, newvalue, ec);
}
gpg_err_code_t
_gcry_mpi_ec_set_point (const char *name, gcry_mpi_point_t newvalue,
gcry_ctx_t ctx)
{
mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC);
return _gcry_ecc_set_point (name, newvalue, ec);
}
/* Given an encoded point in the MPI VALUE and a context EC, decode
* the point according to the context and store it in RESULT. On
* error an error code is return but RESULT might have been changed.
* If no context is given the function tries to decode VALUE by
* assuming a 0x04 prefixed uncompressed encoding. */
gpg_err_code_t
_gcry_mpi_ec_decode_point (mpi_point_t result, gcry_mpi_t value, mpi_ec_t ec)
{
gcry_err_code_t rc;
if (ec && ec->dialect == ECC_DIALECT_ED25519)
rc = _gcry_ecc_eddsa_decodepoint (value, ec, result, NULL, NULL);
else if (ec && ec->model == MPI_EC_MONTGOMERY)
rc = _gcry_ecc_mont_decodepoint (value, ec, result);
else
rc = _gcry_ecc_os2ec (result, value);
return rc;
}
/* Compute the affine coordinates from the projective coordinates in
POINT. Set them into X and Y. If one coordinate is not required,
X or Y may be passed as NULL. CTX is the usual context. Returns: 0
on success or !0 if POINT is at infinity. */
int
_gcry_mpi_ec_get_affine (gcry_mpi_t x, gcry_mpi_t y, mpi_point_t point,
mpi_ec_t ctx)
{
if (!mpi_cmp_ui (point->z, 0))
return -1;
switch (ctx->model)
{
case MPI_EC_WEIERSTRASS: /* Using Jacobian coordinates. */
{
gcry_mpi_t z1, z2, z3;
z1 = mpi_new (0);
z2 = mpi_new (0);
ec_invm (z1, point->z, ctx); /* z1 = z^(-1) mod p */
ec_mulm (z2, z1, z1, ctx); /* z2 = z^(-2) mod p */
if (x)
ec_mulm (x, point->x, z2, ctx);
if (y)
{
z3 = mpi_new (0);
ec_mulm (z3, z2, z1, ctx); /* z3 = z^(-3) mod p */
ec_mulm (y, point->y, z3, ctx);
mpi_free (z3);
}
mpi_free (z2);
mpi_free (z1);
}
return 0;
case MPI_EC_MONTGOMERY:
{
if (x)
mpi_set (x, point->x);
if (y)
{
log_fatal ("%s: Getting Y-coordinate on %s is not supported\n",
"_gcry_mpi_ec_get_affine", "Montgomery");
return -1;
}
}
return 0;
case MPI_EC_EDWARDS:
{
gcry_mpi_t z;
z = mpi_new (0);
ec_invm (z, point->z, ctx);
mpi_resize (z, ctx->p->nlimbs);
z->nlimbs = ctx->p->nlimbs;
if (x)
{
mpi_resize (x, ctx->p->nlimbs);
x->nlimbs = ctx->p->nlimbs;
ctx->mulm (x, point->x, z, ctx);
}
if (y)
{
mpi_resize (y, ctx->p->nlimbs);
y->nlimbs = ctx->p->nlimbs;
ctx->mulm (y, point->y, z, ctx);
}
_gcry_mpi_release (z);
}
return 0;
default:
return -1;
}
}
/* RESULT = 2 * POINT (Weierstrass version). */
static void
dup_point_weierstrass (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
{
#define x3 (result->x)
#define y3 (result->y)
#define z3 (result->z)
#define t1 (ctx->t.scratch[0])
#define t2 (ctx->t.scratch[1])
#define t3 (ctx->t.scratch[2])
#define l1 (ctx->t.scratch[3])
#define l2 (ctx->t.scratch[4])
#define l3 (ctx->t.scratch[5])
if (!mpi_cmp_ui (point->y, 0) || !mpi_cmp_ui (point->z, 0))
{
/* P_y == 0 || P_z == 0 => [1:1:0] */
mpi_set_ui (x3, 1);
mpi_set_ui (y3, 1);
mpi_set_ui (z3, 0);
}
else
{
if (ec_get_a_is_pminus3 (ctx)) /* Use the faster case. */
{
/* L1 = 3(X - Z^2)(X + Z^2) */
/* T1: used for Z^2. */
/* T2: used for the right term. */
ec_pow2 (t1, point->z, ctx);
ec_subm (l1, point->x, t1, ctx);
ec_mulm (l1, l1, mpi_const (MPI_C_THREE), ctx);
ec_addm (t2, point->x, t1, ctx);
ec_mulm (l1, l1, t2, ctx);
}
else /* Standard case. */
{
/* L1 = 3X^2 + aZ^4 */
/* T1: used for aZ^4. */
ec_pow2 (l1, point->x, ctx);
ec_mulm (l1, l1, mpi_const (MPI_C_THREE), ctx);
ec_powm (t1, point->z, mpi_const (MPI_C_FOUR), ctx);
ec_mulm (t1, t1, ctx->a, ctx);
ec_addm (l1, l1, t1, ctx);
}
/* Z3 = 2YZ */
ec_mulm (z3, point->y, point->z, ctx);
ec_mul2 (z3, z3, ctx);
/* L2 = 4XY^2 */
/* T2: used for Y2; required later. */
ec_pow2 (t2, point->y, ctx);
ec_mulm (l2, t2, point->x, ctx);
ec_mulm (l2, l2, mpi_const (MPI_C_FOUR), ctx);
/* X3 = L1^2 - 2L2 */
/* T1: used for L2^2. */
ec_pow2 (x3, l1, ctx);
ec_mul2 (t1, l2, ctx);
ec_subm (x3, x3, t1, ctx);
/* L3 = 8Y^4 */
/* T2: taken from above. */
ec_pow2 (t2, t2, ctx);
ec_mulm (l3, t2, mpi_const (MPI_C_EIGHT), ctx);
/* Y3 = L1(L2 - X3) - L3 */
ec_subm (y3, l2, x3, ctx);
ec_mulm (y3, y3, l1, ctx);
ec_subm (y3, y3, l3, ctx);
}
#undef x3
#undef y3
#undef z3
#undef t1
#undef t2
#undef t3
#undef l1
#undef l2
#undef l3
}
/* RESULT = 2 * POINT (Montgomery version). */
static void
dup_point_montgomery (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
{
(void)result;
(void)point;
(void)ctx;
log_fatal ("%s: %s not yet supported\n",
"_gcry_mpi_ec_dup_point", "Montgomery");
}
/* RESULT = 2 * POINT (Twisted Edwards version). */
static void
dup_point_edwards (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
{
#define X1 (point->x)
#define Y1 (point->y)
#define Z1 (point->z)
#define X3 (result->x)
#define Y3 (result->y)
#define Z3 (result->z)
#define B (ctx->t.scratch[0])
#define C (ctx->t.scratch[1])
#define D (ctx->t.scratch[2])
#define E (ctx->t.scratch[3])
#define F (ctx->t.scratch[4])
#define H (ctx->t.scratch[5])
#define J (ctx->t.scratch[6])
/* Compute: (X_3 : Y_3 : Z_3) = 2( X_1 : Y_1 : Z_1 ) */
/* B = (X_1 + Y_1)^2 */
ctx->addm (B, X1, Y1, ctx);
ctx->pow2 (B, B, ctx);
/* C = X_1^2 */
/* D = Y_1^2 */
ctx->pow2 (C, X1, ctx);
ctx->pow2 (D, Y1, ctx);
/* E = aC */
if (ctx->dialect == ECC_DIALECT_ED25519)
ctx->subm (E, ctx->p, C, ctx);
else
ctx->mulm (E, ctx->a, C, ctx);
/* F = E + D */
ctx->addm (F, E, D, ctx);
/* H = Z_1^2 */
ctx->pow2 (H, Z1, ctx);
/* J = F - 2H */
ctx->mul2 (J, H, ctx);
ctx->subm (J, F, J, ctx);
/* X_3 = (B - C - D) · J */
ctx->subm (X3, B, C, ctx);
ctx->subm (X3, X3, D, ctx);
ctx->mulm (X3, X3, J, ctx);
/* Y_3 = F · (E - D) */
ctx->subm (Y3, E, D, ctx);
ctx->mulm (Y3, Y3, F, ctx);
/* Z_3 = F · J */
ctx->mulm (Z3, F, J, ctx);
#undef X1
#undef Y1
#undef Z1
#undef X3
#undef Y3
#undef Z3
#undef B
#undef C
#undef D
#undef E
#undef F
#undef H
#undef J
}
/* RESULT = 2 * POINT */
void
_gcry_mpi_ec_dup_point (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
{
switch (ctx->model)
{
case MPI_EC_WEIERSTRASS:
dup_point_weierstrass (result, point, ctx);
break;
case MPI_EC_MONTGOMERY:
dup_point_montgomery (result, point, ctx);
break;
case MPI_EC_EDWARDS:
dup_point_edwards (result, point, ctx);
break;
}
}
/* RESULT = P1 + P2 (Weierstrass version).*/
static void
add_points_weierstrass (mpi_point_t result,
mpi_point_t p1, mpi_point_t p2,
mpi_ec_t ctx)
{
#define x1 (p1->x )
#define y1 (p1->y )
#define z1 (p1->z )
#define x2 (p2->x )
#define y2 (p2->y )
#define z2 (p2->z )
#define x3 (result->x)
#define y3 (result->y)
#define z3 (result->z)
#define l1 (ctx->t.scratch[0])
#define l2 (ctx->t.scratch[1])
#define l3 (ctx->t.scratch[2])
#define l4 (ctx->t.scratch[3])
#define l5 (ctx->t.scratch[4])
#define l6 (ctx->t.scratch[5])
#define l7 (ctx->t.scratch[6])
#define l8 (ctx->t.scratch[7])
#define l9 (ctx->t.scratch[8])
#define t1 (ctx->t.scratch[9])
#define t2 (ctx->t.scratch[10])
if ( (!mpi_cmp (x1, x2)) && (!mpi_cmp (y1, y2)) && (!mpi_cmp (z1, z2)) )
{
/* Same point; need to call the duplicate function. */
_gcry_mpi_ec_dup_point (result, p1, ctx);
}
else if (!mpi_cmp_ui (z1, 0))
{
/* P1 is at infinity. */
mpi_set (x3, p2->x);
mpi_set (y3, p2->y);
mpi_set (z3, p2->z);
}
else if (!mpi_cmp_ui (z2, 0))
{
/* P2 is at infinity. */
mpi_set (x3, p1->x);
mpi_set (y3, p1->y);
mpi_set (z3, p1->z);
}
else
{
int z1_is_one = !mpi_cmp_ui (z1, 1);
int z2_is_one = !mpi_cmp_ui (z2, 1);
/* l1 = x1 z2^2 */
/* l2 = x2 z1^2 */
if (z2_is_one)
mpi_set (l1, x1);
else
{
ec_pow2 (l1, z2, ctx);
ec_mulm (l1, l1, x1, ctx);
}
if (z1_is_one)
mpi_set (l2, x2);
else
{
ec_pow2 (l2, z1, ctx);
ec_mulm (l2, l2, x2, ctx);
}
/* l3 = l1 - l2 */
ec_subm (l3, l1, l2, ctx);
/* l4 = y1 z2^3 */
ec_powm (l4, z2, mpi_const (MPI_C_THREE), ctx);
ec_mulm (l4, l4, y1, ctx);
/* l5 = y2 z1^3 */
ec_powm (l5, z1, mpi_const (MPI_C_THREE), ctx);
ec_mulm (l5, l5, y2, ctx);
/* l6 = l4 - l5 */
ec_subm (l6, l4, l5, ctx);
if (!mpi_cmp_ui (l3, 0))
{
if (!mpi_cmp_ui (l6, 0))
{
/* P1 and P2 are the same - use duplicate function. */
_gcry_mpi_ec_dup_point (result, p1, ctx);
}
else
{
/* P1 is the inverse of P2. */
mpi_set_ui (x3, 1);
mpi_set_ui (y3, 1);
mpi_set_ui (z3, 0);
}
}
else
{
/* l7 = l1 + l2 */
ec_addm (l7, l1, l2, ctx);
/* l8 = l4 + l5 */
ec_addm (l8, l4, l5, ctx);
/* z3 = z1 z2 l3 */
ec_mulm (z3, z1, z2, ctx);
ec_mulm (z3, z3, l3, ctx);
/* x3 = l6^2 - l7 l3^2 */
ec_pow2 (t1, l6, ctx);
ec_pow2 (t2, l3, ctx);
ec_mulm (t2, t2, l7, ctx);
ec_subm (x3, t1, t2, ctx);
/* l9 = l7 l3^2 - 2 x3 */
ec_mul2 (t1, x3, ctx);
ec_subm (l9, t2, t1, ctx);
/* y3 = (l9 l6 - l8 l3^3)/2 */
ec_mulm (l9, l9, l6, ctx);
ec_powm (t1, l3, mpi_const (MPI_C_THREE), ctx); /* fixme: Use saved value*/
ec_mulm (t1, t1, l8, ctx);
ec_subm (y3, l9, t1, ctx);
ec_mulm (y3, y3, ec_get_two_inv_p (ctx), ctx);
}
}
#undef x1
#undef y1
#undef z1
#undef x2
#undef y2
#undef z2
#undef x3
#undef y3
#undef z3
#undef l1
#undef l2
#undef l3
#undef l4
#undef l5
#undef l6
#undef l7
#undef l8
#undef l9
#undef t1
#undef t2
}
/* RESULT = P1 + P2 (Montgomery version).*/
static void
add_points_montgomery (mpi_point_t result,
mpi_point_t p1, mpi_point_t p2,
mpi_ec_t ctx)
{
(void)result;
(void)p1;
(void)p2;
(void)ctx;
log_fatal ("%s: %s not yet supported\n",
"_gcry_mpi_ec_add_points", "Montgomery");
}
/* RESULT = P1 + P2 (Twisted Edwards version).*/
static void
add_points_edwards (mpi_point_t result,
mpi_point_t p1, mpi_point_t p2,
mpi_ec_t ctx)
{
#define X1 (p1->x)
#define Y1 (p1->y)
#define Z1 (p1->z)
#define X2 (p2->x)
#define Y2 (p2->y)
#define Z2 (p2->z)
#define X3 (result->x)
#define Y3 (result->y)
#define Z3 (result->z)
#define A (ctx->t.scratch[0])
#define B (ctx->t.scratch[1])
#define C (ctx->t.scratch[2])
#define D (ctx->t.scratch[3])
#define E (ctx->t.scratch[4])
#define F (ctx->t.scratch[5])
#define G (ctx->t.scratch[6])
#define tmp (ctx->t.scratch[7])
point_resize (result, ctx);
/* Compute: (X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_3) */
/* A = Z1 · Z2 */
ctx->mulm (A, Z1, Z2, ctx);
/* B = A^2 */
ctx->pow2 (B, A, ctx);
/* C = X1 · X2 */
ctx->mulm (C, X1, X2, ctx);
/* D = Y1 · Y2 */
ctx->mulm (D, Y1, Y2, ctx);
/* E = d · C · D */
ctx->mulm (E, ctx->b, C, ctx);
ctx->mulm (E, E, D, ctx);
/* F = B - E */
ctx->subm (F, B, E, ctx);
/* G = B + E */
ctx->addm (G, B, E, ctx);
/* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */
ctx->addm (tmp, X1, Y1, ctx);
ctx->addm (X3, X2, Y2, ctx);
ctx->mulm (X3, X3, tmp, ctx);
ctx->subm (X3, X3, C, ctx);
ctx->subm (X3, X3, D, ctx);
ctx->mulm (X3, X3, F, ctx);
ctx->mulm (X3, X3, A, ctx);
/* Y_3 = A · G · (D - aC) */
if (ctx->dialect == ECC_DIALECT_ED25519)
{
ctx->addm (Y3, D, C, ctx);
}
else
{
ctx->mulm (Y3, ctx->a, C, ctx);
ctx->subm (Y3, D, Y3, ctx);
}
ctx->mulm (Y3, Y3, G, ctx);
ctx->mulm (Y3, Y3, A, ctx);
/* Z_3 = F · G */
ctx->mulm (Z3, F, G, ctx);
#undef X1
#undef Y1
#undef Z1
#undef X2
#undef Y2
#undef Z2
#undef X3
#undef Y3
#undef Z3
#undef A
#undef B
#undef C
#undef D
#undef E
#undef F
#undef G
#undef tmp
}
/* Compute a step of Montgomery Ladder (only use X and Z in the point).
Inputs: P1, P2, and x-coordinate of DIF = P1 - P1.
Outputs: PRD = 2 * P1 and SUM = P1 + P2. */
static void
montgomery_ladder (mpi_point_t prd, mpi_point_t sum,
mpi_point_t p1, mpi_point_t p2, gcry_mpi_t dif_x,
mpi_ec_t ctx)
{
ctx->addm (sum->x, p2->x, p2->z, ctx);
ctx->subm (p2->z, p2->x, p2->z, ctx);
ctx->addm (prd->x, p1->x, p1->z, ctx);
ctx->subm (p1->z, p1->x, p1->z, ctx);
ctx->mulm (p2->x, p1->z, sum->x, ctx);
ctx->mulm (p2->z, prd->x, p2->z, ctx);
ctx->pow2 (p1->x, prd->x, ctx);
ctx->pow2 (p1->z, p1->z, ctx);
ctx->addm (sum->x, p2->x, p2->z, ctx);
ctx->subm (p2->z, p2->x, p2->z, ctx);
ctx->mulm (prd->x, p1->x, p1->z, ctx);
ctx->subm (p1->z, p1->x, p1->z, ctx);
ctx->pow2 (sum->x, sum->x, ctx);
ctx->pow2 (sum->z, p2->z, ctx);
ctx->mulm (prd->z, p1->z, ctx->a, ctx); /* CTX->A: (a-2)/4 */
ctx->mulm (sum->z, sum->z, dif_x, ctx);
ctx->addm (prd->z, p1->x, prd->z, ctx);
ctx->mulm (prd->z, prd->z, p1->z, ctx);
}
/* RESULT = P1 + P2 */
void
_gcry_mpi_ec_add_points (mpi_point_t result,
mpi_point_t p1, mpi_point_t p2,
mpi_ec_t ctx)
{
switch (ctx->model)
{
case MPI_EC_WEIERSTRASS:
add_points_weierstrass (result, p1, p2, ctx);
break;
case MPI_EC_MONTGOMERY:
add_points_montgomery (result, p1, p2, ctx);
break;
case MPI_EC_EDWARDS:
add_points_edwards (result, p1, p2, ctx);
break;
}
}
/* RESULT = P1 - P2 (Weierstrass version).*/
static void
sub_points_weierstrass (mpi_point_t result,
mpi_point_t p1, mpi_point_t p2,
mpi_ec_t ctx)
{
(void)result;
(void)p1;
(void)p2;
(void)ctx;
log_fatal ("%s: %s not yet supported\n",
"_gcry_mpi_ec_sub_points", "Weierstrass");
}
/* RESULT = P1 - P2 (Montgomery version).*/
static void
sub_points_montgomery (mpi_point_t result,
mpi_point_t p1, mpi_point_t p2,
mpi_ec_t ctx)
{
(void)result;
(void)p1;
(void)p2;
(void)ctx;
log_fatal ("%s: %s not yet supported\n",
"_gcry_mpi_ec_sub_points", "Montgomery");
}
/* RESULT = P1 - P2 (Twisted Edwards version).*/
static void
sub_points_edwards (mpi_point_t result,
mpi_point_t p1, mpi_point_t p2,
mpi_ec_t ctx)
{
mpi_point_t p2i = _gcry_mpi_point_new (0);
point_set (p2i, p2);
ctx->subm (p2i->x, ctx->p, p2i->x, ctx);
add_points_edwards (result, p1, p2i, ctx);
_gcry_mpi_point_release (p2i);
}
/* RESULT = P1 - P2 */
void
_gcry_mpi_ec_sub_points (mpi_point_t result,
mpi_point_t p1, mpi_point_t p2,
mpi_ec_t ctx)
{
switch (ctx->model)
{
case MPI_EC_WEIERSTRASS:
sub_points_weierstrass (result, p1, p2, ctx);
break;
case MPI_EC_MONTGOMERY:
sub_points_montgomery (result, p1, p2, ctx);
break;
case MPI_EC_EDWARDS:
sub_points_edwards (result, p1, p2, ctx);
break;
}
}
/* Scalar point multiplication - the main function for ECC. If takes
an integer SCALAR and a POINT as well as the usual context CTX.
RESULT will be set to the resulting point. */
void
_gcry_mpi_ec_mul_point (mpi_point_t result,
gcry_mpi_t scalar, mpi_point_t point,
mpi_ec_t ctx)
{
gcry_mpi_t x1, y1, z1, k, h, yy;
unsigned int i, loops;
mpi_point_struct p1, p2, p1inv;
if (ctx->model == MPI_EC_EDWARDS
|| (ctx->model == MPI_EC_WEIERSTRASS
&& mpi_is_secure (scalar)))
{
/* Simple left to right binary method. Algorithm 3.27 from
* {author={Hankerson, Darrel and Menezes, Alfred J. and Vanstone, Scott},
* title = {Guide to Elliptic Curve Cryptography},
* year = {2003}, isbn = {038795273X},
* url = {http://www.cacr.math.uwaterloo.ca/ecc/},
* publisher = {Springer-Verlag New York, Inc.}} */
unsigned int nbits;
int j;
if (mpi_cmp (scalar, ctx->p) >= 0)
nbits = mpi_get_nbits (scalar);
else
nbits = mpi_get_nbits (ctx->p);
if (ctx->model == MPI_EC_WEIERSTRASS)
{
mpi_set_ui (result->x, 1);
mpi_set_ui (result->y, 1);
mpi_set_ui (result->z, 0);
}
else
{
mpi_set_ui (result->x, 0);
mpi_set_ui (result->y, 1);
mpi_set_ui (result->z, 1);
point_resize (point, ctx);
}
if (mpi_is_secure (scalar))
{
/* If SCALAR is in secure memory we assume that it is the
secret key we use constant time operation. */
mpi_point_struct tmppnt;
point_init (&tmppnt);
point_resize (result, ctx);
point_resize (&tmppnt, ctx);
for (j=nbits-1; j >= 0; j--)
{
_gcry_mpi_ec_dup_point (result, result, ctx);
_gcry_mpi_ec_add_points (&tmppnt, result, point, ctx);
point_swap_cond (result, &tmppnt, mpi_test_bit (scalar, j), ctx);
}
point_free (&tmppnt);
}
else
{
if (ctx->model == MPI_EC_EDWARDS)
{
point_resize (result, ctx);
point_resize (point, ctx);
}
for (j=nbits-1; j >= 0; j--)
{
_gcry_mpi_ec_dup_point (result, result, ctx);
if (mpi_test_bit (scalar, j))
_gcry_mpi_ec_add_points (result, result, point, ctx);
}
}
return;
}
else if (ctx->model == MPI_EC_MONTGOMERY)
{
unsigned int nbits;
int j;
mpi_point_struct p1_, p2_;
mpi_point_t q1, q2, prd, sum;
unsigned long sw;
mpi_size_t rsize;
int scalar_copied = 0;
/* Compute scalar point multiplication with Montgomery Ladder.
Note that we don't use Y-coordinate in the points at all.
RESULT->Y will be filled by zero. */
nbits = mpi_get_nbits (scalar);
point_init (&p1);
point_init (&p2);
point_init (&p1_);
point_init (&p2_);
mpi_set_ui (p1.x, 1);
mpi_free (p2.x);
p2.x = mpi_copy (point->x);
mpi_set_ui (p2.z, 1);
if (mpi_is_opaque (scalar))
{
const unsigned int pbits = ctx->nbits;
gcry_mpi_t a;
unsigned int n;
unsigned char *raw;
scalar_copied = 1;
raw = _gcry_mpi_get_opaque_copy (scalar, &n);
if ((n+7)/8 != (pbits+7)/8)
log_fatal ("scalar size (%d) != prime size (%d)\n",
(n+7)/8, (pbits+7)/8);
reverse_buffer (raw, (n+7)/8);
if ((pbits % 8))
raw[0] &= (1 << (pbits % 8)) - 1;
raw[0] |= (1 << ((pbits + 7) % 8));
raw[(pbits+7)/8 - 1] &= (256 - ctx->h);
a = mpi_is_secure (scalar) ? mpi_snew (pbits): mpi_new (pbits);
_gcry_mpi_set_buffer (a, raw, (n+7)/8, 0);
xfree (raw);
scalar = a;
}
point_resize (&p1, ctx);
point_resize (&p2, ctx);
point_resize (&p1_, ctx);
point_resize (&p2_, ctx);
mpi_resize (point->x, ctx->p->nlimbs);
point->x->nlimbs = ctx->p->nlimbs;
q1 = &p1;
q2 = &p2;
prd = &p1_;
sum = &p2_;
for (j=nbits-1; j >= 0; j--)
{
mpi_point_t t;
sw = mpi_test_bit (scalar, j);
point_swap_cond (q1, q2, sw, ctx);
montgomery_ladder (prd, sum, q1, q2, point->x, ctx);
point_swap_cond (prd, sum, sw, ctx);
t = q1; q1 = prd; prd = t;
t = q2; q2 = sum; sum = t;
}
mpi_clear (result->y);
sw = (nbits & 1);
point_swap_cond (&p1, &p1_, sw, ctx);
rsize = p1.z->nlimbs;
MPN_NORMALIZE (p1.z->d, rsize);
if (rsize == 0)
{
mpi_set_ui (result->x, 1);
mpi_set_ui (result->z, 0);
}
else
{
z1 = mpi_new (0);
ec_invm (z1, p1.z, ctx);
ec_mulm (result->x, p1.x, z1, ctx);
mpi_set_ui (result->z, 1);
mpi_free (z1);
}
point_free (&p1);
point_free (&p2);
point_free (&p1_);
point_free (&p2_);
if (scalar_copied)
_gcry_mpi_release (scalar);
return;
}
x1 = mpi_alloc_like (ctx->p);
y1 = mpi_alloc_like (ctx->p);
h = mpi_alloc_like (ctx->p);
k = mpi_copy (scalar);
yy = mpi_copy (point->y);
if ( mpi_has_sign (k) )
{
k->sign = 0;
ec_invm (yy, yy, ctx);
}
if (!mpi_cmp_ui (point->z, 1))
{
mpi_set (x1, point->x);
mpi_set (y1, yy);
}
else
{
gcry_mpi_t z2, z3;
z2 = mpi_alloc_like (ctx->p);
z3 = mpi_alloc_like (ctx->p);
ec_mulm (z2, point->z, point->z, ctx);
ec_mulm (z3, point->z, z2, ctx);
ec_invm (z2, z2, ctx);
ec_mulm (x1, point->x, z2, ctx);
ec_invm (z3, z3, ctx);
ec_mulm (y1, yy, z3, ctx);
mpi_free (z2);
mpi_free (z3);
}
z1 = mpi_copy (mpi_const (MPI_C_ONE));
mpi_mul (h, k, mpi_const (MPI_C_THREE)); /* h = 3k */
loops = mpi_get_nbits (h);
if (loops < 2)
{
/* If SCALAR is zero, the above mpi_mul sets H to zero and thus
LOOPs will be zero. To avoid an underflow of I in the main
loop we set LOOP to 2 and the result to (0,0,0). */
loops = 2;
mpi_clear (result->x);
mpi_clear (result->y);
mpi_clear (result->z);
}
else
{
mpi_set (result->x, point->x);
mpi_set (result->y, yy);
mpi_set (result->z, point->z);
}
mpi_free (yy); yy = NULL;
p1.x = x1; x1 = NULL;
p1.y = y1; y1 = NULL;
p1.z = z1; z1 = NULL;
point_init (&p2);
point_init (&p1inv);
/* Invert point: y = p - y mod p */
point_set (&p1inv, &p1);
ec_subm (p1inv.y, ctx->p, p1inv.y, ctx);
for (i=loops-2; i > 0; i--)
{
_gcry_mpi_ec_dup_point (result, result, ctx);
if (mpi_test_bit (h, i) == 1 && mpi_test_bit (k, i) == 0)
{
point_set (&p2, result);
_gcry_mpi_ec_add_points (result, &p2, &p1, ctx);
}
if (mpi_test_bit (h, i) == 0 && mpi_test_bit (k, i) == 1)
{
point_set (&p2, result);
_gcry_mpi_ec_add_points (result, &p2, &p1inv, ctx);
}
}
point_free (&p1);
point_free (&p2);
point_free (&p1inv);
mpi_free (h);
mpi_free (k);
}
/* Return true if POINT is on the curve described by CTX. */
int
_gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
{
int res = 0;
gcry_mpi_t x, y, w;
x = mpi_new (0);
y = mpi_new (0);
w = mpi_new (0);
/* Check that the point is in range. This needs to be done here and
* not after conversion to affine coordinates. */
if (mpi_cmpabs (point->x, ctx->p) >= 0)
goto leave;
if (mpi_cmpabs (point->y, ctx->p) >= 0)
goto leave;
if (mpi_cmpabs (point->z, ctx->p) >= 0)
goto leave;
switch (ctx->model)
{
case MPI_EC_WEIERSTRASS:
{
gcry_mpi_t xxx;
if (_gcry_mpi_ec_get_affine (x, y, point, ctx))
goto leave;
xxx = mpi_new (0);
/* y^2 == x^3 + a·x + b */
ec_pow2 (y, y, ctx);
ec_pow3 (xxx, x, ctx);
ec_mulm (w, ctx->a, x, ctx);
ec_addm (w, w, ctx->b, ctx);
ec_addm (w, w, xxx, ctx);
if (!mpi_cmp (y, w))
res = 1;
_gcry_mpi_release (xxx);
}
break;
case MPI_EC_MONTGOMERY:
{
#define xx y
/* With Montgomery curve, only X-coordinate is valid. */
if (_gcry_mpi_ec_get_affine (x, NULL, point, ctx))
goto leave;
/* The equation is: b * y^2 == x^3 + a · x^2 + x */
/* We check if right hand is quadratic residue or not by
Euler's criterion. */
/* CTX->A has (a-2)/4 and CTX->B has b^-1 */
ec_mulm (w, ctx->a, mpi_const (MPI_C_FOUR), ctx);
ec_addm (w, w, mpi_const (MPI_C_TWO), ctx);
ec_mulm (w, w, x, ctx);
ec_pow2 (xx, x, ctx);
ec_addm (w, w, xx, ctx);
ec_addm (w, w, mpi_const (MPI_C_ONE), ctx);
ec_mulm (w, w, x, ctx);
ec_mulm (w, w, ctx->b, ctx);
#undef xx
/* Compute Euler's criterion: w^(p-1)/2 */
#define p_minus1 y
ec_subm (p_minus1, ctx->p, mpi_const (MPI_C_ONE), ctx);
mpi_rshift (p_minus1, p_minus1, 1);
ec_powm (w, w, p_minus1, ctx);
res = !mpi_cmp_ui (w, 1);
#undef p_minus1
}
break;
case MPI_EC_EDWARDS:
{
if (_gcry_mpi_ec_get_affine (x, y, point, ctx))
goto leave;
mpi_resize (w, ctx->p->nlimbs);
w->nlimbs = ctx->p->nlimbs;
/* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */
ctx->pow2 (x, x, ctx);
ctx->pow2 (y, y, ctx);
if (ctx->dialect == ECC_DIALECT_ED25519)
ctx->subm (w, ctx->p, x, ctx);
else
ctx->mulm (w, ctx->a, x, ctx);
ctx->addm (w, w, y, ctx);
ctx->mulm (x, x, y, ctx);
ctx->mulm (x, x, ctx->b, ctx);
ctx->subm (w, w, x, ctx);
if (!mpi_cmp_ui (w, 1))
res = 1;
}
break;
}
leave:
_gcry_mpi_release (w);
_gcry_mpi_release (x);
_gcry_mpi_release (y);
return res;
}
int
_gcry_mpi_ec_bad_point (gcry_mpi_point_t point, mpi_ec_t ctx)
{
int i;
gcry_mpi_t x_bad;
for (i = 0; (x_bad = ctx->t.scratch[i]); i++)
if (!mpi_cmp (point->x, x_bad))
return 1;
return 0;
}