ECC improvements

[karel-m]

Hi,

I would like to propose a set of changes to ECC part of libtomcrypt. I have already implemented all proposed changes in my something-like-fork of libtomcrypt which is available https://github.com/DCIT/perl-CryptX/tree/master/src/ltc

1/ Support for curves y^2 = x^3 + a*x + b

Currently libtomcrypt supports only y^2 = x^3 - 3*x + b.

Support for general case required changes to ltc_ecc_projective_dbl_point(), ltc_ecc_projective_add_point() and ltc_ecc_is_point() as you can see in my repo (please note that I have moved is_point function into a separate file ltc_ecc_is_point.c). Extending ltc_ecc_set_type + other small changes were also necessary.

2/ Support for compressed public keys

Already existing function ecc_ansi_x963_export() allows you to export EC public key in a format defined by X9.63 but only supports 'uncompressed' form.

I have added support for exporting compressed EC public keys (which was easy) as well as for import. The import part was a bit tricky as it was necessary to add mp_sqrtmod_prime to libtommath.

As I wanted to keep old interface I have created new functions:

• https://github.com/DCIT/perl-CryptX/blob/master/src/ltc/pk/ecc/ecc_export_raw.c
• https://github.com/DCIT/perl-CryptX/blob/master/src/ltc/pk/ecc/ecc_import_raw.c

NOTE: The new functions ecc_import_raw() / ecc_export_raw() also support import/export of private key (raw octects)

My implementation of mp_sqrtmod_prime (based on Tonelli–Shanks algorithm) is available here:

• https://github.com/DCIT/perl-CryptX/blob/master/src/ltm/bn_mp_sqrtmod_prime.c

3/ DER format compatible with openssl

To support importing/exporting keys in DER format compatible with openssl we need to support the following:

• private key format: http://tools.ietf.org/html/rfc5915
• public key format: http://tools.ietf.org/html/rfc5480

Again, I wanted to keep old interface so I have created new functions:

• https://github.com/DCIT/perl-CryptX/blob/master/src/ltc/pk/ecc/ecc_import_full.c
• https://github.com/DCIT/perl-CryptX/blob/master/src/ltc/pk/ecc/ecc_export_full.c

A small trouble was with adding support for OPTIONAL items in ASN.1 sequences. A big trouble was with private keys which uses ASN.1 context specific tags which are not supported by current libtomcrypt. This part is more a hack/workaround than a systematic support but fully follow ASN.1 specification is not easy.

See the changes at https://github.com/DCIT/perl-CryptX/commits/master/src/ltc/pk/asn1

As my changes to libtomcrypt + libtommath are are quite huge I am not sending them as a pull request. However if you find it worth to be included in upstream libtomcrypt I can fork develop branch a port my changes (I mean those you will agree with) into it.

Any feedback welcome.

Karel

[karel-m]

I have synced https://github.com/DCIT/perl-CryptX/tree/master/src/ltc with latest changes in develop branch. If you checkout my version and do a simple diff it'll show you my ECC related changes.

[karel-m]

Hi,

I have rebased all proposed changes on top of the current develep and pushed them into a new branch for review

• branch - https://github.com/libtom/libtomcrypt/tree/miko-ecc-enhancements
• changes - 9a4a138b96

Keep in mind that the new features require libtommath with a new function mp_sqrtmod_prime as I have proposed here libtom/libtommath#33

[tomstdenis]

IIRC point compression is subjected to patents. I'd highly recommend leaving that disabled by default.

[sjaeckel]

I don't know if this is the patent you are thinking of, or if there are others, but at least one patent targeting point compression is expired:
http://cr.yp.to/patents/us/6141420.html

[sjaeckel]

@karel-m can you please create a PR from that branch?

[sjaeckel]

mh, travis won't be able to build as it requires new functionality in ltm

btw. would you mind creating an implementation of mp_sqrtmod_prime() for tfm? and is that functionality available in gmp?

[tomstdenis]

I didn't have a specific # in mind but we never implemented it originally (nor in my private work) because of noise surrounding it (and quite frankly it rarely comes up with customers).