9
$\begingroup$

Every information I found on internet about RSA-CRT encryption/decryption uses only two primes. I'm interested in my project in doing that using multiple (up to 8) primes.

The general idea is to calculate $d_p = d\bmod(p-1)$, $d_q = d\bmod(q-1)$, and $q_\text{inv} = q^{-1}\bmod p$, where $p$ and $q$ are primes.

Encryption and decryption is based on "logical relations" between $p$ and $q$ and I'm unable to expand it to more than two primes.

Any help appreciated.

$\endgroup$
9
$\begingroup$

The RSA private-key operation (used for decryption and signature generation) amounts to solving for $x$ the equation $y\equiv x^e\pmod N$, knowing $y$, the factorization of the public modulus $N$ into $k\ge2$ distinct primes $N=r_1\dots r_k$, public exponent $e$ such that $\gcd(e,r_i-1)\ne1$, and that $0\le x<N$.

For an efficient implementation, we can solve this equation modulo each of the $r_i$; then use the CRT to combine solutions between products of moduli for which we already have a solution, until reaching a solution modulo $N$. The common way, implicit in PKCS#1v2.2, is:

  • precompute the following quantities $d_i$ (the CRT exponents) and $t_i$ (the CRT inverses/coefficients), e.g. at key generation time, including the results in the private key:
    • for $i\in\{1,\dots,k\}$
      • $d_i\gets e^{-1}\bmod(r_i-1)$, or equivalently $d_i\gets d\bmod(r_i-1)$
    • $m\gets r_1$
    • for $i$ from $2$ to $k$
      • $t_i\gets m^{-1}\bmod r_i$
      • $m\gets m\cdot r_i$
  • when needing to use the private key and solve $y\equiv x^e\pmod N$
    • for $i\in\{1,\dots,k\}$ [note: should be parallelized if possible]
      • $x_i\gets(y\bmod r_i)^{d_i}\bmod r_i$
    • $x\gets x_1$, $m\gets r_1$
    • for $i$ from $2$ to $k$ [loop invariant: $0\le x<m$, $y\equiv x^e\pmod m$ ]
      • $x\gets x+m\cdot((x_i-x\bmod r_i)\cdot t_i\bmod r_i)$
      • $m\gets m\cdot r_i$

Correctness follows from the loop invariant. See this question for attribution. See this other one for how the bitsize of $N$ relates to a maximum reasonable number of primes.

Artificially small example with 3 primes:

e=5
r1=931164518537359 r2=944727352543879 r3=982273258722607
N=864102436520313334659779717201860718296307527
d1=558698711122415 d2=566836411526327 d3=785818606978085
                   t2=360227672914825 t3=882117903741868
y=529481440313141057262802385309623737292746309
x1=436496882968258 x2=903092574358267 x3=806961802724
x=710532117316769399313215266414 (when i=2)
x=111222333444555666777888999000000000000000042

The effort saved compared to a standard (non-CRT) implementation is by a factor at most (and near) $k^2$, if modular multiplication has cost $\mathcal O(n^2)$ for arguments of $n$ bits. The time saved can be higher, up to a factor at most (and near) $k^3$ if parallelization is used on $k$ independent modexp units.

It is critical to make a final check that $y\equiv x^e\pmod N$, and not disclose $x$ otherwise. If this precaution was not taken, the implementation would be vulnerable to the cardinal "Bellcore" fault attack: D. Boneh, R. A. DeMillo, R. Lipton; On the Importance of Eliminating Errors in Cryptographic Computations (in Journal of Cryptology 14(2), 2001; or there).

Implementations should be adequately protected from a variety of other attacks, including timing, power analysis, and other side-channel attacks.


The question also mentions encryption, where only the public key $(N,e)$ is known, not the factorization of $N$. Hence, for that RSA public-key operation (also used for signature verification), there is no similar shortcut applying to the computation $y\gets x^e\bmod N$. However, typically, that remains of low cost compared to the RSA private-key operation, because $e$ is small.

$\endgroup$
  • $\begingroup$ Thank you for detailed answer, I'm going to sink into that, check if I can get it running and mark it as corect answer :) $\endgroup$ – tomQrsd Dec 8 '15 at 6:02
  • 2
    $\begingroup$ Tiny nit: multiprime is in v2.2 (as linked) and v2.1, but not v2.0. $\endgroup$ – dave_thompson_085 Jan 24 '18 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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