[Botan-devel] ECC internals

Jack Lloyd lloyd at randombit.net
Tue Dec 28 14:48:36 EST 2010


Internally PointGFp uses Jacobian coordinates. ECC point addition uses
the formula [1] and doubling uses [2]. There are more efficient
formulas that can be used, though some of them rely on special
cases. Point multiplication is defined using a double-and-add
technique analogous to a square-and-multiply exponentiation in Z_p.

The underlying GF(p) operations are Montgomery reduction,
Karatsuba multiplication, and extended Euclidean for inverses.

I personally do not have any interest in ECC in GF(2^n) as the patent
situation seems much murkier than for fields over GF(p), and the
primary efficiency gains vs GF(p) seem to be for hardware
implementations. As far as I know nobody has really looked into adding
this to botan at any point.

As to the debug library; certainly there is no reason it can't be
done, but I really don't have time right now. I _might_ be able to
build and upload one sometime next month since admittedly this would
be useful, but you should not expect it. If you need debug symbols I'd
really suggest building a local copy with VC and passing
--enable-debug during the build rather than waiting for me.

-Jack

[1] http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
[2] http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc

On Tue, Dec 28, 2010 at 08:50:52PM +0200, Eugene N wrote:
> Hi,
> 
> I would like to know more about botan EC intrenals
> 
> 1) what algorithms are used for reduction, inversion, multiplication in
> GF(P)
> 2) what coordinates are used in EC point operation
> 3) what algo is used for scalar multilication?
> 4) why no binary fields?
> 
> PS: i wonder is it possible to get s debug compiled DLL for windows of botan
> 1.9?
> 
> Thanks and happy new year!

> _______________________________________________
> botan-devel mailing list
> botan-devel at randombit.net
> http://lists.randombit.net/mailman/listinfo/botan-devel




More information about the botan-devel mailing list