-1
$\begingroup$

I've found an article that says how to add points in projective coordinates.But in my implementation these points don't form a group. Fields:

private final BigInteger x;

private final BigInteger y;

private final BigInteger z;

private final BigInteger a;

private final BigInteger b;

private final BigInteger n;

Constructor:

private EllipticCurveProjective(BigInteger x, BigInteger y, BigInteger z, BigInteger a, BigInteger b,
        BigInteger n) {
    super();
    this.x = x;
    this.y = y;
    this.z = z;
    this.a = a;
    this.b = b;
    this.n = n;
}

Random curve and point generator:

public static EllipticCurveProjective generateRandomCurve(BigInteger n) {
        BigInteger x = BigInteger.probablePrime(n.bitLength(), new 

    Random()).mod(n);
            BigInteger y = BigInteger.probablePrime(n.bitLength()-1, new Random()).mod(n);
            BigInteger a = BigInteger.probablePrime(n.bitLength()-1, new Random()).mod(n);
            //This b should fit Weierstrass equation y^2=x^3+ax+b, where b=y^2-x^3-ax
            BigInteger b = (y.modPow(TWO, n).subtract(x.modPow(THREE, n)).subtract(a.multiply(x))).mod(n);
            return new EllipticCurveProjective(x, y, BigInteger.ONE, a, b, n);
        }

Doubling and addition:

public EllipticCurveProjective doublePoint() {
        /*
         *  if (Y == 0) 
            return POINT_AT_INFINITY
         */
        if (y.equals(BigInteger.ZERO)) {
            return getInfinityPoint();
        }
        //W = a*Z^2 + 3*X^2
        BigInteger w = a.multiply(z.modPow(TWO, n)).add(THREE.multiply(x.modPow(TWO, n)));
        //S = Y*Z
        BigInteger s = y.multiply(z).mod(n);
        //B = X*Y*S
        BigInteger b = x.multiply(y).mod(n).multiply(s).mod(n);
        //H = W^2 - 8*B
        BigInteger h = w.modPow(TWO, n).subtract(EIGHT.multiply(b)).mod(n);
        //X' = 2*H*S
        BigInteger x3 = TWO.multiply(h).mod(n).multiply(s).mod(n);
        //Y' = W*(4*B - H) - 8*Y^2*S^2
        BigInteger y3 = w.multiply(FOUR.multiply(b).subtract(h).mod(n)).mod(n)
                .subtract(EIGHT.multiply(y.modPow(TWO, n)).multiply(s.modPow(TWO, n)).mod(n)).mod(n);
        //Z' = 8*S^3
        BigInteger z3 = EIGHT.multiply(s.modPow(THREE, n)).mod(n);
        return new EllipticCurveProjective(x3, y3, z3, a, this.b, n);
    }

    public EllipticCurveProjective addPoint(EllipticCurveProjective ec) {
        if (ec.equals(this)) {
            return this.doublePoint();
        }
        //U1 = Y2*Z1
        BigInteger u1 = ec.getY().multiply(z).mod(n);
        //U2 = Y1*Z2
        BigInteger u2 = y.multiply(ec.getZ()).mod(n);
        //V1 = X2*Z1
        BigInteger v1 = ec.getX().multiply(z).mod(n);
        //V2 = X1*Z2
        BigInteger v2 = x.multiply(ec.getZ()).mod(n);
        // if (V1 == V2)
        if (v1.equals(v2)) {
            //if (U1 != U2)
            if (!u1.equals(u2)) {
                return getInfinityPoint();
            } else {
                // return POINT_DOUBLE(X1, Y1, Z1)
                return this.doublePoint();
            }
        }
        //U = U1 - U2
        BigInteger u = u1.subtract(u2).mod(n);
        //V = V1 - V2
        BigInteger v = v1.subtract(v2).mod(n);
        //W = Z1*Z2
        BigInteger w = z.multiply(ec.getZ()).mod(n);
        //A = U^2*W - V^3 - 2*V^2*V2
        BigInteger A = u.modPow(TWO, n).multiply(w).mod(n).subtract(v.modPow(THREE, n)).mod(n)
                .subtract(TWO.multiply(v.modPow(TWO, n)).multiply(v2)).mod(n);
        //X3 = V*A
        BigInteger x3 = v.multiply(A).mod(n);
        //U*(V^2*V2 - A) - V^3*U2
        BigInteger y3 = u.multiply(v.modPow(TWO, n).multiply(v2).mod(n).subtract(A))
                .subtract(v.modPow(THREE, n).multiply(u2)).mod(n);
        //Z3 = V^3*W
        BigInteger z3 = v.modPow(THREE, n).multiply(w).mod(n);
        return new EllipticCurveProjective(x3, y3, z3, a, b, n);
    }

But if I do this:

BigInteger n = BigInteger.probablePrime(32, new Random());
        EllipticCurveProjective point = EllipticCurveProjective.generateRandomCurve(n);
        //p+p+p
        EllipticCurveProjective result1 = point.addPoint(point).addPoint(point);
        //p+(p+p)
        EllipticCurveProjective result2 = point.addPoint(point.addPoint(point));
        System.out.println(result1.equals(result2));

It will return false, meaning that p+p+p is not p+(p+p). Where is my mistake?

$\endgroup$

closed as off-topic by Maarten Bodewes, e-sushi Jan 23 '17 at 13:51

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Programming questions are off-topic even if you are writing or debugging cryptographic code. Unless your question is specifically about how the cryptographic algorithm or protocol works, you should look into asking on Stack Overflow instead." – Maarten Bodewes, e-sushi
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ This is more like a programming question... By the way how did you define equals ? Also your code is kinda hard to read. You should also provide a .java file (gist) so we could fiddle with it. While we get how you do this, if you provide also us the file, it will be easier for us to help you. :/ $\endgroup$ – Biv Jan 22 '17 at 21:46
3
$\begingroup$

I believe the implementation of is_equals (which you don't show) is likely to be the problem.

In projective coordinates, a triple $(x,y,z)$ corresponds to a solution $u=xz^{-1}, v=yz^{-1}$ to the equation $v^2 = u^3 + au + b$. Hence, two triples $(x,y,z), (x',y',z')$ with $xz^{-1} = x'z'^{-1}$ and $yz^{-1} = y'z'^{-1}$ are the same, because they both correspond to the same solution (also known as point). Two such triples are two different representations of the same point (in effect, different ways of spelling it); just like in Scientific Notation, $3 \times 10^2$ and $0.3 \times 10^3$ are really the same number.

With your addition routine, the addition $(A+B)+C$ will be the same point as $A+(B+C)$ but not necessarily the same representation of that point. Unless your is_equals function accounts for it, it would appear to break associativity.

$\endgroup$

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