2
$\begingroup$

The reason for asking, is that this occurs in real life with CRT calculation of RSA decryption/signing. In CRT RSA, there's the need to calculate subtraction, and it's known negative numbers could occur, especially with multi-prime cases.

While RSA would eventually phase out when moderately-sized quantum computers are available, before QCs can reach that scale, scaling RSA parameters (especially towards using more primes) may be more feasible than rushing to adopt post-quantum schemes in the short term, therefore, it's still a bit relevant.

While it's easy to to do modular arithmetic in variable-time, it seems very difficult do it in constant-time and with limited space for holding working variables.

Q1: Is there a way to implement efficient constant-time modular arithmetic for signed two's-comlement integers in constant time?

Additional Q2 for refuting the use of such implementation: Is there alternative methods for computing CRT RSA decryption/signing that uses no more (or even less) number of working variables? (these "working variables" are big integers).

$\endgroup$
3
  • $\begingroup$ Anything wrong with: ensure $p$ and $q$ are the same bit size, $v\gets(c\bmod q)^{d_q}\bmod q$, $m\gets(((((c\bmod p)^{d_p}\bmod p)+2p-v)\bmod p)\,q_{inv}\bmod p)\,q+v$ ? Nothing can get negative. If $p\ge q$, we can even get away with $p$ rather than $2p$. $\endgroup$
    – fgrieu
    Feb 14, 2021 at 14:23
  • 2
    $\begingroup$ @fgrieu The problem is significant with multi-prime RSA, where $m = m + R \cdot h$ and $h = (m_i - m) \cdot t_i \pmod{r_i}$ where $m$ is larger than $m_i$ by an order of magnitude. $\endgroup$
    – DannyNiu
    Feb 14, 2021 at 14:26
  • $\begingroup$ @fgrieu I've edited the question so that you can solidify your arguments into an answer. $\endgroup$
    – DannyNiu
    Feb 14, 2021 at 15:48

2 Answers 2

3
$\begingroup$

Using that $\forall x\in\mathbb Z$, it holds $x\bmod p\,=\,p-1-((-x-1)\bmod p)$, and that in so-called two's-complement arithmetic $-x-1$ is the bitwise complement of $x$, the other answer's code simplifies to:

uint32_t imod(uint32_t x, uint32_t p) {
    uint32_t s = -(x>>31);          // 0 or -1, with the later iff x<0
    x = x ^ s;                      // conditionally complement x, so that x >= 0
    x = x % p;                      // unsigned modular reduction in constant time
    x = x ^ (((p-1 - x) ^ x) & s);  // conditionally change x to p-1 - x
    return x;
}

This also has the advantage that the code computing x % p is now assured that $x<2^{31}$ on input, instead of having to properly handle $x=2^{31}$ when imod is passed x = 0x80000000 in order to compute $(-2^{31})\bmod p$.


In cryptography, an alternative to signed arithmetic is to avoid negative values entirely. For example, in RSA-CRT with $p>q$, the private-key computation $x\gets y^d\bmod(p\,q)$ can go (with the first three steps performed just once at key generation) $$\begin{align} d_p&\gets d\bmod(p-1)\\ d_q&\gets d\bmod(q-1)\\ q_\text{inv}&\gets q^{-1}\bmod p\\ x&\gets(y\bmod q)^{d_q}\bmod q\\ x&\gets x+q\cdot((p-x+((y\bmod p)^{d_p}\bmod p))\cdot q_\text{inv}\bmod p) \end{align}$$ which involves no negative value, since $p>q\implies p-x>1$ before the last expression. If we don't know that $p>q$ but know that $p$ and $q$ have the same bit size (as is the case for a FIPS 186‑4 key), we can change $p-x$ to $2p-x$.

In multiprime RSA, this needs adaptation. The corresponding part of the calculation (detailed there) involves computing $$x\gets x+m\cdot(((x_i-x)\bmod r_i)\cdot t_i\bmod r_i)$$ where $x_i\ll x$ (typically). Using that $0\le x_i<r_i$, we can rearrange this to either one of $$\begin{align} x&\gets x+m\cdot((r_i-(x\bmod r_i)+x_i)\cdot t_i\bmod r_i)\\ x&\gets x+m\cdot(((r_i-(x\bmod r_i)+x_i)\bmod r_i)\cdot t_i\bmod r_i) \end{align}$$ which involves no negative value, and is asymptotically as efficient as the original.

$\endgroup$
1
  • $\begingroup$ Great work simplifying the code! Although I'd like to point out that it'll require additional variables if applied to big integers. Apart from that, the code itself definitely very useful! $\endgroup$
    – DannyNiu
    Feb 15, 2021 at 2:34
2
$\begingroup$

This answer answers Q1, as there may be merit other than just for calculating CRT RSA (e.g. the extended Euclidean algorithm).


Let's build it step-by-step.

First let's assume you've implemented the % operator for unsigned modular arithmetic in constant time, when you encounter a negative number x, we have the following:

x === -(-x)

Introducing the modulus p, and we have:

x (mod p) === p - (-x) (mod p)

Hence, the algorithm for negative numbers (in pseudo-code, not constant-time yet):

imod(x):
    x = -x
    x = x % p
    if x > 0: x = p - x
    return x

Now, we want to generalize it to apply to also positive numbers, here's the full code in C (constant-time this time):

uint32_t imod(uint32_t x, uint32_t p)
{
    uint32_t neg = -(x >> 31);
    uint32_t z;

    // conditionally negate x.
    x ^= neg;
    x += neg & 1;
    x = x % p;

    // test for 0.
    z = x;

    // Per suggestion by @fgrieu
    // The following code fragment involves:
    // 2 shifts, 4 bit-ops, and 2 additive ops.
    z |= z >> 16;
    z &= 0xffffU;
    z = -(1 ^ ((z ^ (z - 1)) >> 31));

    // In comparison, the following requires:
    // 5 shifts, 6 bit-ops, and 1 additive ops.
    /* z |= z >> 16;
     * z |= z >> 8;
     * z |= z >> 4;
     * z |= z >> 2;
     * z |= z >> 1;
     * z = -(z & 1);
     */

    neg &= z;

    // conditionally compute p - x.
    x = ((~neg & x) | (neg & p)) - (neg & x);
    return x;
}
$\endgroup$
5
  • 1
    $\begingroup$ Computing z from x can be z = -((x^(x-1))>>31). See my preferred solution overall in this answer. [obsolete: the answer formerly used an undefined u ]. $\endgroup$
    – fgrieu
    Feb 14, 2021 at 16:41
  • $\begingroup$ @fgrieu Thanks for spotting the mistake! I was at bed in my timezone for the past few hours. $\endgroup$
    – DannyNiu
    Feb 15, 2021 at 2:50
  • 1
    $\begingroup$ @fgrieu Your formula for z has the edge case of 0x80000000, which can be easily solved in combination with my codes. I'll implement that. $\endgroup$
    – DannyNiu
    Feb 15, 2021 at 3:53
  • $\begingroup$ Right, I had missed that special case for z. Update: OTOH, on third analysis, if $p$ is expressed using signed arithmetic, and since it holds 0 <= xand x < p where z is computed, the edge case x = 0x8000000won't happen. $\endgroup$
    – fgrieu
    Feb 15, 2021 at 8:36
  • $\begingroup$ About the extended Euclidean algorithm (now mentioned in the answer): when it's done for the purpose of computing a modular inverse, as is the case in RSA, it's more efficient (less variables to compute and store) to use the half-extended Euclidean algorithm. It's less well-known there's a simple variant of that which involves no negative. Really, it's easy to avoid any negative in an implementation of RSA, except temporarily in an efficient modular reduction. $\endgroup$
    – fgrieu
    Feb 15, 2021 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.