[cryptography] Point compression prior art?
paul at ciphergoth.org
Tue May 3 12:27:12 EDT 2011
Is there a way of doing elliptic curve point compression for curves in
GF(p) which does not fall foul of patents? Of course point compression
in GF(p) is blindingly obvious, but as we know that doesn't always help.
This message, by Bodo Moeller in 2005, suggests there is:
> The idea to use one bit to
> compress a specific y-coordinate is newer -- it appears in Harper,
> Menezes, Vanstone, "Public-Key Cryptosystems with Very Small Key
> Lengths", EUROCRYPT '92 (LNCS 658). The technique for the GF(p) case
> is described here. The printed proceedings for this conference (held
> in May 1992) were published by Springer-Verlag in February 1993, so
> this case is quite clear.
> For the GF(2^m) case, however, I am not aware of prior art. Hence,
> point compression for binary curves is not available in standard
> compilations of OpenSSL.
The paper is here:
However, contrary to the above, AFAICT the paper describes point
compression for a GF(2^n) elliptic curve. Page 164 of the paper (the
first page is numbered 163) says "We will be concerned here with
elliptic curves over fields of characteristic 2", and gives the elliptic
curve equation in the form "y^2 + xy = x^3 + ax^2 + b" (1). It is this
equation which is then transformed on page 1 into equation (3) which is
designed for efficient point compression.
And indeed the OpenSSL sources now discuss that patent in a comment
above the GF(2^n) point compression implementation in ec2_smpl.c.
There's no similar comment above the GF(p) implementation in ecp_smpl.c.
Can anyone shed any light? Thanks!
\/ o\ Paul Crowley, paul at ciphergoth.org
More information about the cryptography