Problems with field arithmetic about rfc7748_precomputed

[armfazh]

With respect to the fp25519 arithmetic this was already solved in 42953.
You can verify whether the new code computes correctly the arith operations in fp25519.
Thanks for pointing this bug.

[armfazh]

I only briefly checked fp448_x64 for comparison, but I believe add_EltFp448_1w_x64 and sub_EltFp448_1w_x64 also have similar errors, probably even less likely to be detected by random inputs.

More tests are needed for the case of fp448.

[peterdettman]

A simple change that will reveal more failures is e.g.:

void random_EltFp25519_1w_x64(uint64_t *A)
{
        random_bytes((uint8_t*)A,SIZE_ELEMENT_BYTES);
        for (int i = 0; i < 4; ++i) {
                A[i] = -(A[i] & 1);    // <- Each limb becomes either all 0 bits or all 1 bits
        }
        A[3] &= ((uint64_t)1<<63)-1;    // <- Also comment this out for more failures
}

A similar change will reveal errors for fp448 also.

Assuming that add_EltFp25519_1w_x64 is supposed to work correctly for all 256-bit values (i.e. there are no tighter bounds on expected inputs), then I believe you need yet another carry (*38) from r11 to r8. Presumably needed in sub_ also.

[armfazh]

Assuming that add_EltFp25519_1w_x64 is supposed to work correctly for all 256-bit values (i.e. there are no tighter bounds on expected inputs), then I believe you need yet another carry (*38) from r11 to r8. Presumably needed in sub_ also.

Thanks for pinpointing this issue. In fact, the pull request merged in c79ca5e6 now handles addition and subtraction for any value of 256 bits.

[armfazh]

A similar change will reveal errors for fp448 also.

This part of the library still requires more analysis. I will open an issue for this particular part.

@peterdettman Please, let me know if you found more issues in the arithmetic and DH implementation of X25519.