[cryptography] Point compression prior art?

Paul Crowley 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
/\__/ http://www.ciphergoth.org/

More information about the cryptography mailing list