Incorrect serialization of elliptic curve point whose X = 0

[guidovranken]

Zig Version

zig-linux-x86_64-0.11.0-dev.3395+1e7dcaa3a

Steps to Reproduce and Observed Behavior

const std = @import("std");
const P256 = std.crypto.ecc.P256;

pub fn main() !void {
    var ax: [32]u8 = [32]u8{
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    };
    var ay: [32]u8 = [32]u8{
    0x99, 0xB7, 0xA3, 0x86, 0xF1, 0xD0, 0x7C, 0x29, 0xDB, 0xCC, 0x42, 0xA2, 0x7B, 0x5F, 0x94, 0x49,
    0xAB, 0xE3, 0xD5, 0x0D, 0xE2, 0x51, 0x78, 0xE8, 0xD7, 0x40, 0x7A, 0x95, 0xE8, 0xB0, 0x6C, 0x0B,
    };
    var bx: [32]u8 = [32]u8{
    0xC2, 0x24, 0x2B, 0xE3, 0x59, 0x87, 0x9E, 0xCF, 0x8A, 0x92, 0xB8, 0xD9, 0x79, 0xC6, 0xDC, 0x96,
    0xD9, 0x00, 0x5A, 0x00, 0x23, 0x6B, 0xA2, 0x0E, 0x7E, 0xB2, 0x46, 0x5F, 0xE7, 0x68, 0x29, 0xB4,
    };
    var by: [32]u8 = [32]u8{
    0x43, 0x20, 0x84, 0x08, 0x5D, 0x73, 0xE7, 0xBF, 0x62, 0x48, 0x25, 0x88, 0x0C, 0x59, 0x08, 0xA4,
    0x49, 0x08, 0x59, 0x76, 0x42, 0xFD, 0xE9, 0xE4, 0x40, 0xB3, 0xB8, 0x36, 0xA1, 0xB9, 0x05, 0xA6,
    };
    var a = P256.fromSerializedAffineCoordinates(ax, ay, .Big) catch return;
    var b = P256.fromSerializedAffineCoordinates(bx, by, .Big) catch return;
    var r = a.add(b).toUncompressedSec1();
    var i: u32 = 0;
    while (i < 65): (i+=1) {
        std.debug.print("0x{x} ", .{r[i]});
    }
    std.debug.print("\n", .{});
}

Output:

0x4 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x1

E.g. point (0, 1)

Expected Behavior

0x4 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x66 0x48 0x5c 0x78 0x0e 0x2f 0x83 0xd7 0x24 0x33 0xbd 0x5d 0x84 0xa0 0x6b 0xb6 0x54 0x1c 0x2a 0xf3 0x1d 0xae 0x87 0x17 0x28 0xbf 0x85 0x6a 0x17 0x4f 0x93 0xf4

E.g. point (0, 46263761741508638697010950048709651021688891777877937875096931459006746039284)

[guidovranken]

@jedisct1

[guidovranken]

Also calling .neg() on a returns (0, 1) (it shouldn't)

[jedisct1]

Thanks Guido! I'm gonna take a look at this shortly.

My intuition is that the issue is in the conversion to affine coordinates. The computations themselves are fine. Here's a simpler way to highlight the problem.

const std = @import("std");
const P256 = std.crypto.ecc.P256;

pub fn main() !void {
    var ax: [32]u8 = [32]u8{
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    };
    var ay: [32]u8 = [32]u8{
        0x99, 0xB7, 0xA3, 0x86, 0xF1, 0xD0, 0x7C, 0x29, 0xDB, 0xCC, 0x42, 0xA2, 0x7B, 0x5F, 0x94, 0x49,
        0xAB, 0xE3, 0xD5, 0x0D, 0xE2, 0x51, 0x78, 0xE8, 0xD7, 0x40, 0x7A, 0x95, 0xE8, 0xB0, 0x6C, 0x0B,
    };
    var a = P256.fromSerializedAffineCoordinates(ax, ay, .Big) catch return;
    std.debug.print(" a.x={s}\n", .{std.fmt.bytesToHex(a.x.toBytes(.Big), .lower)});
    std.debug.print(" a.y={s}\n", .{std.fmt.bytesToHex(a.y.toBytes(.Big), .lower)});
    std.debug.print(" a.z={s}\n", .{std.fmt.bytesToHex(a.z.toBytes(.Big), .lower)});
    std.debug.print(" a.Z={s}\n", .{std.fmt.bytesToHex(a.z.invert().toBytes(.Big), .lower)});

    const af = a.affineCoordinates();
    std.debug.print("af.x={s}\n", .{std.fmt.bytesToHex(af.x.toBytes(.Big), .lower)});
    std.debug.print("af.y={s}\n", .{std.fmt.bytesToHex(af.y.toBytes(.Big), .lower)});
}

With Z = 1/z = 1, coordinates shouldn't change.

[jedisct1]

When serializing, we were assuming that when the X coordinate was 0, it represented the point at infinity. Which is not the case if Z != 0. The PR above fixes it. Thanks!

[guidovranken]

Thanks. Changed the title for posterity.