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

Bignum: Implement fixed width modular negation #6021

Closed
yanesca opened this issue Jul 4, 2022 · 4 comments · Fixed by #6743
Closed

Bignum: Implement fixed width modular negation #6021

yanesca opened this issue Jul 4, 2022 · 4 comments · Fixed by #6743
Assignees
Labels
component-crypto Crypto primitives and low-level interfaces enhancement size-s Estimated task size: small (~2d)

Comments

@yanesca
Copy link
Contributor

yanesca commented Jul 4, 2022

Prerequisites: #6017

Implement and test mbedtls_mpi_mod_raw_neg(). The implementation should follow the prototype:
https://github.com/hanno-arm/mbedtls/blob/ecp_prototype/library/bignum_core.c#L436-L447

This function should take the modulus as a modulus struct instead of a raw pointer.

@yanesca yanesca added enhancement component-crypto Crypto primitives and low-level interfaces size-s Estimated task size: small (~2d) needs-info An issue or PR which needs further info from the reporter / author labels Jul 4, 2022
@yanesca yanesca removed the needs-info An issue or PR which needs further info from the reporter / author label Sep 15, 2022
@minosgalanakis minosgalanakis self-assigned this Nov 29, 2022
@tom-cosgrove-arm
Copy link
Contributor

Rather than 2 x sub + 1 x add-if, could we do something like this?

mbedtls_mpi_uint zero_check = 0;

/* The only representation of 0 is all-bits 0 in all limbs */
for( size_t i = 0; i < n; i++ )
    zero_check |= A[i];

/* We want X = N - A, except if A was 0, we want to return 0 */
mbedtls_mpi_core_sub( X, N, A, n );

/* mask is all-bits 0 if zero_check is 0, else all-bits 1 */
mbedtls_mpi_uint mask = mbedtls_ct_mpi_uint_mask( zero_check );

/* So if A was 0, we will clear it all out, else leave unchanged */
for( size_t i = 0; i < n; i++ )
        A[i] &= mask;

@gilles-peskine-arm
Copy link
Contributor

@tom-cosgrove-arm I think that's correct, and maybe marginally more efficient (because there's no carry to propagate, so the per-limb calculations can be pipelined more), but I don't think that's worth the extra complexity.

@minosgalanakis
Copy link
Contributor

@tom-cosgrove-arm I was wondering if there is a need for a constantime zero check method reglardless of the specific applicaton. It could be usefull if many inputs for bignum_mod have branching or invalid behavior when the input is zero, but I cannot think of many.

@gilles-peskine-arm
Copy link
Contributor

I was wondering if there is a need for a constantime zero check

This is going to be needed for inv_mod at least.

@minosgalanakis minosgalanakis linked a pull request Dec 7, 2022 that will close this issue
3 tasks
@tom-cosgrove-arm tom-cosgrove-arm changed the title Implement fixed width modular negation Bignum: Implement fixed width modular negation Dec 11, 2022
@mpg mpg closed this as completed in #6743 Dec 13, 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 size-s Estimated task size: small (~2d)
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants