Re: ECC point compression trick

Tom St Denis <tomstdenis@xxxxxxxxx>:
Paul Rubin wrote:
"Tom St Denis" <tomstdenis@xxxxxxxxx> writes:

You still have to compute the root to find y but now you don't even
send the one bit. You just send x.

You can already do that. See:

http://cr.yp.to/patents/us/6141420.html

IIRC he's dealing with a OEF curve and as such is using a montgomery
ladder algorithm which only uses the x-coord. I don't know if you can
do the same for the GF(p) curves that NIST specifies.

I can't see how this relates to the relevant quote from Victor
Miller's CRYPTO '85 paper, which is as follows:

Finally, it should be remarked, that even though we have phrased
everything in terms of points on an elliptic curve, that, for the
key exchange protocol (and other uses as one-way functions), that
only the x-coordinate needs to be transmitted. The formulas for
multiples of a point cited in the first section make it clear that
the x-coordinate of a multiple depends only on the x-coordinate of
the original point.

This applies to elliptic-curve Diffie-Hellman when you discard the
y-coordinate of the ECDH result after computing a B where a is
your secret multiplier and B is a point chosen by the other party:

If you only have the x-coordinate of point B, x_B, then you can
compute y_B, y'_B such that either B = (x_B, y_B) and -B = (x, y'),
or B = (x_B, y_B') and -B = (x_B, y_B). You know this -- often
you have a point-compression bit that helps you decide whether to
keep y_B or y'_B to obtain B. But consider what you'll get when
computing a B and a (-B). The latter is -(a B), so if
a B = (x, y), then a (-B) = (x, y'), which has the same
x-coordinate as a B, since inverting a point only changes the
y-coordinate.

Thus you can obtain the x-coordinate of a B without knowing which
one of y_B and y'_B is the original y-coordinate of B. Your
implementation may not run deterministically, but still it can compute
a deterministic result.

So you don't need to provide the specific y-coordinate to do
Diffie-Hellman over an elliptic curve. However, this trick does not
apply to ECDSA, since in signature verification for ECDSA you have
to compute a linear combination r P + s Q of points, and if you
end up computing r P - s Q instead, this is not of much use.
For ECDSA, the appropriate idea to get rid of explicit compression
bits is the one that you brought up here, namely to decide upon
a fixed compression bit. (Your wording was different, but the
essential idea is to define some point compression scheme and declare
that the compression bit is standardized to be 0 under said scheme,
ruling out those keys for which it would be 1.)
.

Relevant Pages

  • plotting a parabola
    ... My book states that to find the base point from a quadratic ... we have the Axis of symmetry and x-Coordinate of the Vertex ... along with the y-Coordinate of the vertex respectively. ... us the sum of all interior angles of a general polygon? ...
    (sci.math)
  • Re: How to get the infomation of position where the mouse point is in the screen?
    ... > The information of position means x-coordinate, y-coordinate in the ... > I don't know how to access these coordinates from kernel. ... Prev by Date: ...
    (comp.os.linux.development.system)
  • Re: plotting RGB colors
    ... column 1: X-coordinate ... column 2: Y-coordinate ... column 3: Z-coordinate ...
    (comp.soft-sys.matlab)
  • plotting RGB colors
    ... I have an Nx6 matrix in which: ... column 1: X-coordinate ... column 2: Y-coordinate ... column 3: Z-coordinate ...
    (comp.soft-sys.matlab)