Failing to implement HAL_PKA_ECCCompleteAddition correctly

[MaartenMJR]

Hi,

I am struggling to get `HAL_PKA_ECCCompleteAddition` implemented correctly, that is, if I'm comparing the projective coordinates with a reference implementation, the results don't match. Same goes for converting the projective coordinates back to affine coordinates using `HAL_PKA_ECCProjective2Affine`. 

I am using a STM32u585vi microprocessor, and was able to use `HAL_PKA_ECCMul` properly already.

See below the function that shows incorrect results. Could you please provide help to proceed here?

ps. In its current form, the projective X coordinate produces equal results as a C# BountyCastle reference implementation. 

bool ecc_secp256r1_add_points_projective(const generator_point_t* p1, const generator_point_t* p2, generator_point_t* pOut) {
    const uint8_t Z_projective_input[prime256v1_Prime_len] = {[0] = 0, [31] = 1};

    uint8_t X[prime256v1_Prime_len];
    uint8_t Y[prime256v1_Prime_len];
    uint8_t Z[prime256v1_Prime_len];

    PKA_ECCCompleteAdditionInTypeDef eccAddInput = {
        .modulusSize = prime256v1_Prime_len,
        .modulus = prime256v1_Prime,    // Curve prime
        .coefA = prime256v1_absA,       /* PKA operation need abs(a) */
        .coefSign = prime256v1_A_sign,  // Coefficient sign
        .basePointX1 = p1->x,
        .basePointY1 = p1->y,
        .basePointZ1 = Z_projective_input,
        .basePointX2 = p2->x,
        .basePointY2 = p2->y,
        .basePointZ2 = Z_projective_input,
    };

    if (HAL_PKA_ECCCompleteAddition(&hpka, &eccAddInput, HAL_MAX_DELAY) != HAL_OK) {
        return false;
    }

    PKA_ECCCompleteAdditionOutTypeDef eccAddOutput = {
        .ptX = X,
        .ptY = Y,
        .ptZ = Z,
    };
    HAL_PKA_ECCCompleteAddition_GetResult(&hpka, &eccAddOutput);

    // This is an effort to convert the coordinates manually, which failed, and I want to use the hardware acceleration
    // if (ecc_convert_to_affine(X, Y, Z, pOut->x, pOut->y) == false) {
    //     return false;
    // }

    {
        PKA_MontgomeryParamInTypeDef montgomeryParamIn = {
            .size = prime256v1_Prime_len,
            .pOp1 = prime256v1_Prime,
        };

        if (HAL_PKA_MontgomeryParam(&hpka, &montgomeryParamIn, HAL_MAX_DELAY) != HAL_OK) {
            return false;
        }
    }

    uint32_t montgomeryparam[8] = {0};

    HAL_PKA_MontgomeryParam_GetResult(&hpka, montgomeryparam);

    /**
    After performing the ECC addition or other operations, we need to normalize the resulting point from
    projective coordinates to affine coordinates.
    */

    {
        PKA_ECCProjective2AffineInTypeDef eccNormalizeInput = {
            .modulusSize = prime256v1_Prime_len,
            .modulus = prime256v1_Prime,          /*!< pointer to curve modulus value p */
            .basePointX = X,                      /*!< pointer to curve base point coordinate x */
            .basePointY = Y,                      /*!< pointer to curve base point coordinate y */
            .basePointZ = Z,                      /*!< pointer to curve base point coordinate z */
            .pMontgomeryParam = montgomeryparam,  // secp256r1_R2_mod_p,
        };

        HAL_PKA_ECCProjective2Affine(&hpka, &eccNormalizeInput, HAL_MAX_DELAY);

        PKA_ECCProjective2AffineOutTypeDef eccNormalizeOutput = {
            .ptX = pOut->x,
            .ptY = pOut->y,
        };

        HAL_PKA_ECCProjective2Affine_GetResult(&hpka, &eccNormalizeOutput);
        return true;
    }
}

[STea]

Hello @MaartenMJR ,

After a quick look to the code you are providing and I'm wondering if X Y Z buffers to output results should be based as addresses as the .ptX and .ptY should get a pointer as parameter.

Can you check the implementation of STM32CubeU5/Projects/B-U585I-IOT02A/Examples/PKA/PKA_ECCProjective2Affine at main · STMicroelectronics/STM32CubeU5
as a reference for your implementation?
Also, could you provide the source of test vectors you are using to test this function?
Regards

[MaartenMJR]

Thanks for your response, and the (Montgomery) implementation reference (see below about that).

For a reference I use 2x multiplication of the generator base point, see below snippet. `double_origin_expected` gives the same results as in a python implementation. However, the `ecc_secp256r1_add_points_projective` does not give the same results.

// Multiply generator base point with 2, and compare with (base point + base point)

generator_point_t double_origin_expected;
const uint8_t scalar_2[prime256v1_Order_len] = {[31] = 2};

assert(ecc_secp256r1_multiply_base((buffer_view_t){.buffer = scalar_2, .size = sizeof(scalar_2)},
&double_origin_expected) == true);

const generator_point_t* const generator_origin = (generator_point_t*)&prime256v1_Generator[1];
generator_point_t double_origin;

//assert(ecc_secp256r1_add_points_affine(generator_origin, generator_origin, &double_origin) == true);
assert(ecc_secp256r1_add_points_projective(generator_origin, generator_origin, &double_origin) == true);

assert(memcmp(double_origin_expected.x, double_origin.x, sizeof(double_origin.x)) == 0);
assert(memcmp(double_origin_expected.y, double_origin.y, sizeof(double_origin.y)) == 0);

With the provided reference I'm able to verify that the computation of the MontgomeryParameter is correct:

{
const uint32_t input1_1PKA_ECC_ConvToAffine_IN_MONTGOMERY_PARAM[] = {0x00000001, 0x00000000, 0x00000002,
0x00000000, 0x00000002, 0x00000000};

const uint8_t prime192v1[] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff};

// Test montgomery param
{
PKA_MontgomeryParamInTypeDef montgomeryParamIn = {
.size = sizeof(prime192v1),
.pOp1 = prime192v1,
};

assert(HAL_PKA_MontgomeryParam(&hpka, &montgomeryParamIn, HAL_MAX_DELAY) == HAL_OK);
}

uint32_t montgomeryparam[sizeof(input1_1PKA_ECC_ConvToAffine_IN_MONTGOMERY_PARAM) / sizeof(uint32_t)] = {0};

HAL_PKA_MontgomeryParam_GetResult(&hpka, montgomeryparam);

assert(memcmp(montgomeryparam, input1_1PKA_ECC_ConvToAffine_IN_MONTGOMERY_PARAM, sizeof(montgomeryparam)) == 0);
}

Still I can't figure out why the `ecc_secp256r1_add_points_projective` computation remains faulty. Any ideas?

[MaartenMJR]

Note: In this example, the `Y` coordinate in ecc_secp256r1_add_points_projective is correct, but the `X` and `Z` coordinates not, and of course the affine result is then also incorrect.