STM32 PKA RSA Montgomery Parameter

[Thomas Roell]

The PKA peripheral can precompte the montgomery parameter, which is documented as "R2 mod n". If I compute this offline with R being the normal (2 ^ b) [b the numbers of bits in the modulus n], I am getting a different result than what PKA computes.

I did see there was a "computeR2.exe" for BlueNRG-LPS (also with PKA peripheral), but no source.

Is there anywhere documentation or source code of how to precompute the "Montgomery Parameter" used by the PKA peripheral ?

[Tesla DeLorean]

@Jocelyn RICARD @ALABSTM 

https://www.st.com/resource/en/product_training/STM32WB-Security-PublicKeyAccelerator-HW-Accelerator-PKA.pdf

https://www.st.com/content/ccc/resource/training/technical/product_training/group1/b8/bc/a1/3e/75/66/46/00/STM32L5-Security-PublicKeyAccelerator_HW_Accelerator_PKA/files/STM32L5-Security-PublicKeyAccelerator_HW_Accelerator_PKA.pdf/_jcr_content/translations/en.STM32L5-Security-PublicKeyAccelerator_HW...

https://community.st.com/t5/stm32-mcus-security/stm32u585-pka-ecc-scalar-multiplication-undocumented-errors/td-p/124728

https://github.com/STMicroelectronics/STM32CubeWB/issues/1#issuecomment-558167521

[Thomas Roell]

None of that is relevant.

The official documentation does not specify what format the montgomery parameter gets stored in. Yes, it says that you can compute the montgomery parameter directly using PKA. But that is not what I am asking for. I do want to precompute this "r2modn" offline, rather than online via the PKA periperal.

This here is some code using the OpenSSL bignum APIs. I use this for a software implementation to verify a rsa2048 signature. Fairly simple stuff, lifted off some 2013 google code. Code is crosschecked with OpenSSL's RSA code, so I know it works:

    N = BN_dup(rsa2048_modulus);
    Big2 = BN_new();
    Big32 = BN_new();
    R = BN_new();
    RR = BN_new();
    RRTemp = BN_new();
    NnumBits = BN_new();
    rr = BN_new();
    BN_set_word(Big2, 2L);
    BN_set_word(Big32, 32L);
    B = BN_new();
    BN_exp(B, Big2, Big32, bn_ctx); /* B = 2^32 */

    /* Calculate R = 2^(# of key bits) */
    BN_set_word(NnumBits, BN_num_bits(N));
    BN_exp(R, Big2, NnumBits, bn_ctx);
    /* Calculate RR = R^2 mod N */
    BN_copy(RR, R);
    BN_mul(RRTemp, RR, R, bn_ctx);
    BN_mod(RR, RRTemp, N, bn_ctx);
    /* Write R^2 as little endian array of integers. */
    for (i = 0; i < nwords; ++i) {
        uint32_t rrout;
        BN_mod(rr, RR, B, bn_ctx); /* rr = RR mod B */
        rrout = BN_get_word(rr);
        printf("%08x\n", rrout);
        BN_rshift(RR, RR, 32); /* RR = RR/B */
    }

However the value produced here does not match the one that PKA computes as the montgomery parameter. No byte/halfbyte swapping, nor other common reordering works. N.b. that I am using the same logic to emit the modulus "n" in the proper order, which works just fine with the PKA peripheral. 

So either the PKA peripheral does not use the classic R^2 mod n, or it's stored in some other fashion.

[Tesla DeLorean]

Perhaps one of the ST staff can provide the details you are looking for, or you can ping them via GitHub / LinkedIn, etc

@Le Corre Pierre 

Kind of on the wrong side of the pond, and Friday, to get a quick answer from Europe.

[Tesla DeLorean]

>> However the value produced here does not match the one that PKA computes as the montgomery parameter. No byte/halfbyte swapping, nor other common reordering works. ... or it's stored in some other fashion.

Well I can certainly subscribe to that, had my own battles with SECP192R1 libraries and assorted byte/endian differences between them, and that was with only permutations of 12 bytes.. especially with the light-weight library I was able to get to build cleanly on the STM32 and MSVC

[UgoIannu]

Hello Thomas,

could you please specify which is the target MCU on which you are working on?

[Thomas Roell]

Ugolannu,

this is for STM32WB55 and STM32WL55.

[UgoIannu · Accepted solution]

Hello Thomas,

for both targets, you should be able to generate a valid value of R2 using the following python function:

def generateR2(n):
    n = int(n)
    k = n.bit_length()
    w = int(math.ceil(k/32))
    R = 2**(32*w)
    r2adj = 2**(w*32-k)
    Z = R - n*r2adj
    for i in range(0, w+2):
        Z = Z << 32
        MSW = (Z >> w*32) & (2**32-1)
        while (MSW != 0):
            Z = Z - (n * MSW * r2adj)
            MSW = (Z >> w*32) & (2**32-1)
    return (Z)

In the snippet, n is the modulus, and the output Z is the desired related R2 Montgomery parameter.

Please, let me know if it solves the issue or you need further support.

[Thomas Roell]

Ugolannu,

thanx for the response. That fixed my issue. Now, I asked for WL/WB5. Does this also apply to any of the 32 bit word PKA peripherals (WB0, WBA, U5) ?

- Thomas

[UgoIannu]

Yes, it should be ok for all the 32 bit PKAs