From 1a5fdede16498c6306b02f4ab8c81af4ccf7c289 Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Thu, 22 Jan 2015 21:25:25 +0100 Subject: Add reduced-bitlength scalar multiplication --- include/libuecc/ecc.h | 3 +++ src/ec25519.c | 33 ++++++++++++++++++++++++++++++--- 2 files changed, 33 insertions(+), 3 deletions(-) diff --git a/include/libuecc/ecc.h b/include/libuecc/ecc.h index c456ac3..46cfaa9 100644 --- a/include/libuecc/ecc.h +++ b/include/libuecc/ecc.h @@ -64,7 +64,10 @@ void ecc_25519_store_packed(ecc_int256_t *out, const ecc_25519_work_t *in); int ecc_25519_is_identity(const ecc_25519_work_t *in); void ecc_25519_double(ecc_25519_work_t *out, const ecc_25519_work_t *in); void ecc_25519_add(ecc_25519_work_t *out, const ecc_25519_work_t *in1, const ecc_25519_work_t *in2); + +void ecc_25519_scalarmult_bits(ecc_25519_work_t *out, const ecc_int256_t *n, const ecc_25519_work_t *base, unsigned bits); void ecc_25519_scalarmult(ecc_25519_work_t *out, const ecc_int256_t *n, const ecc_25519_work_t *base); +void ecc_25519_scalarmult_base_bits(ecc_25519_work_t *out, const ecc_int256_t *n, unsigned bits); void ecc_25519_scalarmult_base(ecc_25519_work_t *out, const ecc_int256_t *n); /**@}*/ diff --git a/src/ec25519.c b/src/ec25519.c index d21bb8a..9f66d6f 100644 --- a/src/ec25519.c +++ b/src/ec25519.c @@ -548,16 +548,23 @@ void ecc_25519_add(ecc_25519_work_t *out, const ecc_25519_work_t *in1, const ecc } /** - * Does a scalar multiplication of a point of the Elliptic Curve with an integer + * Does a scalar multiplication of a point of the Elliptic Curve with an integer of a given bit length + * + * To speed up scalar multiplication when it is known that not the whole 256 bits of the scalar + * are used. The bit length should always be a constant and not computed at runtime to ensure + * that no timing attacks are possible. * * The same pointers may be used for input and output. **/ -void ecc_25519_scalarmult(ecc_25519_work_t *out, const ecc_int256_t *n, const ecc_25519_work_t *base) { +void ecc_25519_scalarmult_bits(ecc_25519_work_t *out, const ecc_int256_t *n, const ecc_25519_work_t *base, unsigned bits) { ecc_25519_work_t Q2, Q2p; ecc_25519_work_t cur = id; int b, pos; - for (pos = 255; pos >= 0; --pos) { + if (bits > 256) + bits = 256; + + for (pos = bits - 1; pos >= 0; --pos) { b = n->p[pos / 8] >> (pos & 7); b &= 1; @@ -569,6 +576,15 @@ void ecc_25519_scalarmult(ecc_25519_work_t *out, const ecc_int256_t *n, const ec *out = cur; } +/** + * Does a scalar multiplication of a point of the Elliptic Curve with an integer + * + * The same pointers may be used for input and output. + **/ +void ecc_25519_scalarmult(ecc_25519_work_t *out, const ecc_int256_t *n, const ecc_25519_work_t *base) { + ecc_25519_scalarmult_bits(out, n, base, 256); +} + /** The ec25519 default base */ static const ecc_25519_work_t default_base = { {0xd4, 0x6b, 0xfe, 0x7f, 0x39, 0xfa, 0x8c, 0x22, @@ -586,6 +602,17 @@ static const ecc_25519_work_t default_base = { 0x47, 0x4b, 0x4c, 0x81, 0xa6, 0x02, 0xfd, 0x29} }; +/** + * Does a scalar multiplication of the default base point (generator element) of the Elliptic Curve with an integer of a given bit length + * + * The order of the base point is \f$ 2^{252} + 27742317777372353535851937790883648493 \f$. + * + * See the notes about \ref ecc_25519_scalarmult_bits before using this function. + */ +void ecc_25519_scalarmult_base_bits(ecc_25519_work_t *out, const ecc_int256_t *n, unsigned bits) { + ecc_25519_scalarmult_bits(out, n, &default_base, bits); +} + /** * Does a scalar multiplication of the default base point (generator element) of the Elliptic Curve with an integer * -- cgit v1.2.3