Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve Montgomery multiplication strategy #5666

Open
hanno-becker opened this issue Mar 28, 2022 · 0 comments
Open

Improve Montgomery multiplication strategy #5666

hanno-becker opened this issue Mar 28, 2022 · 0 comments
Labels
component-crypto Crypto primitives and low-level interfaces enhancement

Comments

@hanno-becker
Copy link

hanno-becker commented Mar 28, 2022

In the language of https://ieeexplore.ieee.org/document/502403, Mbed TLS' Montgomery Multiplication implements "Coarsely Integrated Operand Scanning" (CIOS): In each step of the Montgomery multiplication loop, we perform two separate big x small multiplications to compute first T -> T + u0*B and then T -> T + u0*B + u1*N where u1 = (T + u0*B)_0 * Pinv_0: https://github.com/ARMmbed/mbedtls/blob/e44d8e7eea886a472684bb830295a0ac1c283007/library/bignum.c#L1931-L1938

Those loops should be merged together to compute T + u0*B + u1*N in one loop, introducing a basic primitive mpi_mul_dbl_hlp() (or similar) which performs two multiply-accumulates. This results in what the above paper calls "Finely Integrated Operand Scanning".

The impact is particularly large for M-Profile CPUs which implement the DSP extension and thus feature the UMAAL instruction. With this instruction, the bottleneck of the entire Montgomery multiplication are memory accesses. We have already reported on one optimization #5360 reducing the CC for a 2048-bit Montgomery multiplication from 37kC to 25kC by pairing loads and stores. Passing from CIOS to FIOS will further reduce the cycle count to around 20kC since a load/store pair for the accumulator T is removed.

@hanno-becker hanno-becker added enhancement component-crypto Crypto primitives and low-level interfaces labels Mar 28, 2022
@hanno-becker hanno-becker changed the title Montgomery multiplication strategy Improve Montgomery multiplication strategy Mar 28, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
component-crypto Crypto primitives and low-level interfaces enhancement
Projects
None yet
Development

No branches or pull requests

1 participant