ECC curve k224 is broken

Hej,

the point multiplication on the ECC curve k224 (secp224k1 in OpenSSL) returns points that do not lie on the curve. Thus curve k224 is unusable right now. All other ECC curves, especially k192 and k224, are not affected by this problem.

Since other curves are not affected I've looked for some special properties of the k224 curve and found two things:

The order of k224's G (parameter r of the ECC curve constructor) starts with a leading zero.
The order of k224's G is longer (in bits) than the x and y values of G (parameters x & y of the ECC curve constructor).

I've checked the parameters with the official SEC definition and they seem to be correct, but they may be the root of the problem anyway...

Apart from that some tests revealed that the point conversion from Jacobian coordinates back to the affine form changes the point itself:

sjcl.ecc.curves.k224.G.toJac().toAffine() != sjcl.ecc.curves.k224.G;

I digged a bit deeper and found out that the fullReduce method for pseudo Mersenne primes changes the value of the prime. I don't think that this is expected behaviour. The this.addM(this.modulus) lines within fullReduce seem to cause the change, but commenting them out didn't fix point multiplication on the k224 curve.

The fact that adding this.modulus causes problems lead me to the conclusion that the modulus calculation itself might be the problem. However, I only have little knowledge about EC mathematics, so I wasn't able to proove that.

I've created a fix-k224-curve branch in my SJCL fork, which contains some tests for the k224 curve that might be helpful for debugging. Once the branch has been cloned, they can be run with the following lines:

./configure --without-all --with-ecc --compress=none
make test

bitwiseshiftleft / sjcl

ECC curve k224 is broken #262