6
$\begingroup$

The Bouncy Castle source code (Java edition) has a ECPoint.normalize() function. It seems to calculate the modular inverse of a coordinate of a point on the curve. Without it point compression - for instance - seems to fail.

It seems that usually this normalization is performed as part of Elliptic Curve calculations automatically when other libraries are concerned.

So I've got the following questions:

  1. After which operations is normalization required for elliptic curves?
  2. What's this normalization about, is it just calculating the coordinates with a "positive" Y value on the curve?
  3. Could leaving out the normalization of points trigger invalid calculations, or is this just about the representation of the point on the curve?

If there is any reference material available then I'd be interested to know about it.


For reference, the Java source code of Bouncy Castle:

/**
 * Normalization ensures that any projective coordinate is 1, and therefore that the x, y
 * coordinates reflect those of the equivalent point in an affine coordinate system.
 * 
 * @return a new ECPoint instance representing the same point, but with normalized coordinates
 */
public ECPoint normalize()
{
    if (this.isInfinity())
    {
        return this;
    }

    switch (this.getCurveCoordinateSystem())
    {
    case ECCurve.COORD_AFFINE:
    case ECCurve.COORD_LAMBDA_AFFINE:
    {
        return this;
    }
    default:
    {
        ECFieldElement Z1 = getZCoord(0);
        if (Z1.isOne())
        {
            return this;
        }

        return normalize(Z1.invert());
    }
    }
}

ECPoint normalize(ECFieldElement zInv)
{
    switch (this.getCurveCoordinateSystem())
    {
    case ECCurve.COORD_HOMOGENEOUS:
    case ECCurve.COORD_LAMBDA_PROJECTIVE:
    {
        return createScaledPoint(zInv, zInv);
    }
    case ECCurve.COORD_JACOBIAN:
    case ECCurve.COORD_JACOBIAN_CHUDNOVSKY:
    case ECCurve.COORD_JACOBIAN_MODIFIED:
    {
        ECFieldElement zInv2 = zInv.square(), zInv3 = zInv2.multiply(zInv);
        return createScaledPoint(zInv2, zInv3);
    }
    default:
    {
        throw new IllegalStateException("not a projective coordinate system");
    }
    }
}

protected ECPoint createScaledPoint(ECFieldElement sx, ECFieldElement sy)
{
    return this.getCurve().createRawPoint(getRawXCoord().multiply(sx), getRawYCoord().multiply(sy), this.withCompression);
}
$\endgroup$
  • $\begingroup$ I'm slightly humbled to ask this question as it clearly shows my missing math skills :| $\endgroup$ – Maarten Bodewes May 1 '17 at 16:24
  • 2
    $\begingroup$ OK, I think this handles conversion from internal projective point representation to affine representation for further exporting. But I'll wait with you for some more qualified explanation :) $\endgroup$ – SEJPM May 1 '17 at 18:05
  • $\begingroup$ I think you are right, but I'll do the same. I guess I will always have to perform the operation in that case, regardless of multiplication / addition etc. - when I export it as you indicated, not before. Waiting with anticipation. $\endgroup$ – Maarten Bodewes May 1 '17 at 18:15
  • 1
    $\begingroup$ I think @SEJPM is right, it's just taking the current coordinate representation and converting it to affine coordinates. Whereas operations on affine coordinates often require a field inversion this is not the case in other coordinates. So instead of (expensive) inversions per operation we just have to do an inversion once when converting back to affine coordinates from a representation that has more efficient group operations. This point is moot when we're working in a prime field since inversion is fast (due to Euler's Theorem). $\endgroup$ – puzzlepalace May 1 '17 at 19:10
2
$\begingroup$

This is just about the representation of the point on the curve.

In the affine form of elliptic curve points, $(x,y)$ is the representation of points. But in the projective coordination, points are in the form $(X:Y:Z)$. Let $K$ be a field, and let $c$ and $d$ be positive integers and $\lambda\in K^*$. In this representation $(X:Y:Z)\sim (\lambda ^cX:\lambda ^dY:\lambda Z) $. That is, any element of an equivalence class can serve as its representative. In particular, if $Z\ne 0$ then $(\frac{X}{\lambda ^c}:\frac{Y}{\lambda ^d}:1) $ is a representative of the projective point $(X:Y:Z)$, and in fact is the only representative with $Z$-coordinate equal to $1$. In this state, affine form of points is $(x,y)=(\frac{X}{Z ^c},\frac{Y}{Z ^d})=(X,Y)$.

For more details you can see page $86$ of "Guide to elliptic curve cryptography", Hankerson, ....

$\endgroup$
  • $\begingroup$ So to answer the first question, I presume I should normalize the ECPoint after any calculation, when communicating with external systems or when compressing / decompressing the point internally? Are there operations (multiplication / addition) where the compression can be skipped? For now I'll just always normalize after one or multiple sequential calculations within public methods (that may be called externally), assuming that normalization is fast - especially when nothing needs to be performed in the first place (Z=1). Thanks for the informative answer! $\endgroup$ – Maarten Bodewes May 2 '17 at 11:20
  • $\begingroup$ I've accepted the answer; I think this reflects whats in the code. If you can however answer Q1 (I've put numbers in front of the questions) I'd be very happy. $\endgroup$ – Maarten Bodewes May 2 '17 at 15:15
  • 1
    $\begingroup$ Huh, don't you mean after the computations? Your answer is quite clear, but that last comment is not. What I have in my head now is that Bouncy uses a projective coordination to speed things up, after which you need to perform normalization to get things back to affine form. Is this correct? $\endgroup$ – Maarten Bodewes May 2 '17 at 21:11
  • $\begingroup$ @MaartenBodewes, Yes, exactly. I delete my last comment. $\endgroup$ – Meysam Ghahramani May 3 '17 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.