# How to handle modular arithmetic with regard to two's-complement negative numbers?

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).

• 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$. – fgrieu Feb 14 at 14:23
• @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. – DannyNiu Feb 14 at 14:26
• @fgrieu I've edited the question so that you can solidify your arguments into an answer. – DannyNiu Feb 14 at 15:48

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, 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.

• 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! – DannyNiu Feb 15 at 2:34

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;
}

• 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 ]. – fgrieu Feb 14 at 16:41
• @fgrieu Thanks for spotting the mistake! I was at bed in my timezone for the past few hours. – DannyNiu Feb 15 at 2:50
• @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. – DannyNiu Feb 15 at 3:53
• 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. – fgrieu Feb 15 at 8:36
• 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. – fgrieu Feb 15 at 11:05