Hello, This patch adds ECC support using the GnuTLS libtomcrypt adaptation.
regards, Nikos
btw. I had issues building the cvs version. The compilation was failing: nettle-hash.o: In function `list_algorithms': /home/nmav/cvs/lsh/nettle/tools/nettle-hash.c:49: undefined reference to `nettle_hashes'
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
This patch adds ECC support using the GnuTLS libtomcrypt adaptation.
Nice! Needs some more work to really fit with nettle. Some initial comments based on the header file:
+/* assume curve is y^2 = x^3 - 3x + b
- instead of the generic y^2 = x^3 + ax + b
- (XXX: the generic case has been tested only
- with the SECG curves.)
- */
Maybe the naming in the itnerface should reflect that it's a special case.
+/* ---- ECC Routines ---- */ +/* size of our temp buffers for exported keys */ +#define ECC_BUF_SIZE 512
+/* max private key size */ +#define ECC_MAXSIZE 66
Where do these maximums come from?
+/** Structure defines a NIST GF(p) curve */ +typedef struct {
- /** The size of the curve in octets */
- int size;
- /** name of curve */
- const char *name;
- /** curve's OID */
- const char *oid;
- /** The prime that defines the field the curve is in (encoded in hex) */
- const char *prime;
- /** The fields A param (hex) */
- const char *A;
- /** The fields B param (hex) */
- const char *B;
- /** The order of the curve (hex) */
- const char *order;
- /** The x co-ordinate of the base point on the curve (hex) */
- const char *Gx;
- /** The y co-ordinate of the base point on the curve (hex) */
- const char *Gy;
+} ecc_set_type;
Avoid using typedef for plain structs.
I'm not sure I like using hex strings for the constants. Depends a bit on usage, of course. E.g., it's a bit difficult to define a constant mpz_t.
+/** An ECC key */ +typedef struct {
- /** Type of key, PK_PRIVATE or PK_PUBLIC */
- int type;
- mpz_t prime;
- mpz_t order;
- mpz_t A;
- mpz_t Gx;
- mpz_t Gy;
- /** The public key */
- ecc_point pubkey;
- /** The private key */
- mpz_t k;
+} ecc_key;
I'd follow nettle's DSA interface with separate structs for the public and private parameters, and eliminate the PK_PRIVATE and PK_PUBLIC constants. I think it would also make sense to move out the curve parameters to it's own struct (typed as mpz_t, then, unlike ecc_set_tyep above).
+/* Key generation */ +int ecc_make_key(void *random_ctx, nettle_random_func random, ecc_key *key, const ecc_set_type *dp); +int ecc_make_key_ex(void *random_ctx, nettle_random_func random, ecc_key *key, mpz_t prime, mpz_t order, mpz_t A, mpz_t Gx, mpz_t Gy); +void ecc_free(ecc_key *key);
I haven't figured out exactly what these do, but naming should most likele be _init and _clear, for consistency with the rest of nettle and with gmp.
+/* EC-Diffie-Hellman */ +int ecc_shared_secret(ecc_key *private_key, ecc_key *public_key,
unsigned char *out, unsigned long *outlen);
Haven't looked at this; for diffie-hellman over the normal ring one would just use gmp's powm function. I think the corresponding ecc function should also be public (maybe it already is?).
+/* ECDSA */ +int ecc_sign_hash(const unsigned char *in, unsigned long inlen,
struct dsa_signature *signature,void *random_ctx, nettle_random_func random, ecc_key *key);+int ecc_verify_hash(struct dsa_signature * signature,
const unsigned char *hash, unsigned long hashlen,int *stat, ecc_key *key);
Do these correspond to the _sign_digest and _verify_digest functions for dsa and rsa?
+/* (Internal) low level functions */ +ecc_point *ecc_new_point(void); +void ecc_del_point(ecc_point *p);
It's more nettle style to let the caller allocate the structs. ecc_point_init and ecc_point_clear would be more appropriate.
+/* point ops (mp == montgomery digit) */ +/* R = 2P */ +int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mpz_t a, mpz_t modulus);
+/* R = P + Q */ +int ecc_projective_add_point(ecc_point *P, ecc_point *Q, ecc_point *R, mpz_t A, mpz_t modulus);
Is it customary jargon and notation to think about the the ecc group operation as addition rather than multiplication? (Choice is arbitrary).
+/* R = kG */ +int ecc_mulmod(mpz_t k, ecc_point *G, ecc_point *R, mpz_t a, mpz_t modulus, int map);
I'd call the it ecc_scalar_mul or something like that, rather than mulmod. Algebraically, any (cummutative?) group is a module over Z or over Z/(group order) or something like that (sorry, I don't recall the fine details since I studied algebra), and that's the type of multiplication we're doing: Z x G -> G.
+int mp_init_multi(mpz_t *a, ...); +void mp_clear_multi(mpz_t *a, ...);
Not sure I like these.
+#define mp_isodd(a) (mpz_size(a) > 0 ? (mpz_getlimbn(a, 0) & 1 ? 1 : 0) : 0)
Just use mpz_odd_p.
+#define MP_DIGIT_BIT (sizeof(mp_limb_t) * 8 - GMP_NAIL_BITS)
Same as GMP_NUMB_BITS.
/nisse
On 08/14/2011 07:43 PM, Niels Möller wrote:
+/* assume curve is y^2 = x^3 - 3x + b
- instead of the generic y^2 = x^3 + ax + b
- (XXX: the generic case has been tested only
- with the SECG curves.)
- */
Maybe the naming in the itnerface should reflect that it's a special case.
You can use the generic code by keeping ecc_projective_add_point.c instead of ecc_projective_add_point_3.c. I have not tested the generic code though with other curves than the SECP that use a = -3. The improvement from the special case is not that significant.
+/* ---- ECC Routines ---- */ +/* size of our temp buffers for exported keys */ +#define ECC_BUF_SIZE 512 +/* max private key size */ +#define ECC_MAXSIZE 66
Where do these maximums come from?
From the sizes of the supported groups.
+/* Key generation */ +int ecc_make_key(void *random_ctx, nettle_random_func random, ecc_key *key, const ecc_set_type *dp); +int ecc_make_key_ex(void *random_ctx, nettle_random_func random, ecc_key *key, mpz_t prime, mpz_t order, mpz_t A, mpz_t Gx, mpz_t Gy); +void ecc_free(ecc_key *key);
I haven't figured out exactly what these do, but naming should most likele be _init and _clear, for consistency with the rest of nettle and with gmp.
make_key is actually _init and _generate in one.
+/* EC-Diffie-Hellman */ +int ecc_shared_secret(ecc_key *private_key, ecc_key *public_key,
unsigned char *out, unsigned long *outlen);Haven't looked at this; for diffie-hellman over the normal ring one would just use gmp's powm function. I think the corresponding ecc function should also be public (maybe it already is?).
Could be. This is a convenience function.
+/* ECDSA */ +int ecc_sign_hash(const unsigned char *in, unsigned long inlen,
struct dsa_signature *signature,void *random_ctx, nettle_random_func random, ecc_key *key);+int ecc_verify_hash(struct dsa_signature * signature,
const unsigned char *hash, unsigned long hashlen,int *stat, ecc_key *key);Do these correspond to the _sign_digest and _verify_digest functions for dsa and rsa?
Indeed but they are not limited to a particular digest. Any hash can be used.
+/* point ops (mp == montgomery digit) */ +/* R = 2P */ +int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mpz_t a, mpz_t modulus);
+/* R = P + Q */ +int ecc_projective_add_point(ecc_point *P, ecc_point *Q, ecc_point *R, mpz_t A, mpz_t modulus);
Is it customary jargon and notation to think about the the ecc group operation as addition rather than multiplication? (Choice is arbitrary).
I've never seen multiplication being used to describe this operation (either in cryptography or pure mathematics).
+int mp_init_multi(mpz_t *a, ...); +void mp_clear_multi(mpz_t *a, ...);
Not sure I like these.
They simplify code utilizing multiple mpz_ts significantly.
regards, Nikos
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
Indeed but they are not limited to a particular digest. Any hash can be used.
And the hash algorithm is not encoded into the signature process (copmare to rsa pkcs#1 signatures)? I have to read up on how these ecc signatures are done. I think a comment said that it was analogous to dsa, but dsa is tied quite hard to a particular hash function (and the digest size should also match the size of the subgroup where the group operations take place).
I've never seen multiplication being used to describe this operation (either in cryptography or pure mathematics).
I think the group operation of an arbitrary group is usually written as a multiplication in abstract algebra textbooks. E.g., Herstein's Topics in Algebra. Maybe the reason for this tradition is that it is natural when group elements are functions (in particular, permutations), and the group operation is composition (but then Herstein has an unusual convention for the argument order of compositions...).
Do I understand you correctly that the group operations is usually written as an addition in the context of elliptic curves?
Regards, /Niels
On 08/14/2011 10:06 PM, Niels Möller wrote:
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
Indeed but they are not limited to a particular digest. Any hash can be used.
And the hash algorithm is not encoded into the signature process (copmare to rsa pkcs#1 signatures)? I have to read up on how these ecc signatures are done. I think a comment said that it was analogous to dsa, but dsa is tied quite hard to a particular hash function (and the digest size should also match the size of the subgroup where the group operations take place).
ECDSA is very similar to DSA. Specific hash functions are used for specific curves, but it always depends on the profile. E.g. rfc5480 has a table with the allowed combinations and a table with the recommended combinations.
Unfortunately DSA (and ECDSA) require a profile, or are practically unimplementable.
I've never seen multiplication being used to describe this operation (either in cryptography or pure mathematics).
I think the group operation of an arbitrary group is usually written as a multiplication in abstract algebra textbooks. E.g., Herstein's Topics in Algebra. Maybe the reason for this tradition is that it is natural when group elements are functions (in particular, permutations), and the group operation is composition (but then Herstein has an unusual convention for the argument order of compositions...). Do I understand you correctly that the group operations is usually written as an addition in the context of elliptic curves?
You always can avoid the term addition by using the generic term group operation or so. I've also seen the dot notation to describe operations in a group, but I've rarely seen the actual term multiplication. Note however that here you also have the "scalar multiplication", so if you use this term, addition would be the appropriate for the group operation.
regards, Nikos
Nikos Mavrogiannopoulos nmav@gnutls.org writes:
I've also seen the dot notation to describe operations in a group, but I've rarely seen the actual term multiplication.
I'm referring to the notation, which somehow determines how how one thinks about the operation.
Note however that here you also have the "scalar multiplication", so if you use this term, addition would be the appropriate for the group operation.
Sure. If one chooses to use multiplicative notation for the group operation, this operation would be called an exponentiation, not a multiplication.
Regards, /nisse
nettle-bugs@lists.lysator.liu.se
-
Nikos Mavrogiannopoulos -
nisse＠lysator.liu.se