Paper 2025/1157 Original: eprint.iacr.org/2025/1157 ↗

General Multi-Prime Multi-Power RSA - A Generalization of RSA and CRT-RSA to Regular Integers Modulo $n$

Abstract

We present a multi-prime multi-power generalization of RSA for arbitrary integer moduli $n>1$ and messages $m<n$ which are regular modulo $n$, meaning that they have a John-von-Neumann pseudoinverse modulo $n$. We prove that our RSA generalization is correct in the sense that it works for all regular messages modulo $n$, and complete in the sense that it works for no other message. Our correctness and completeness result, which implies the original RSA correctness theorem, is proved in a rigorous way based on a new sharpening of Charmichael's theorem established in this paper. As for CRT-RSA, decryption can be accelerated by Chinese remaindering, which results in a multi-prime multi-power generalization of CRT-RSA. We show that the restriction to regular messages modulo $n$ is negligible by proving that under reasonable assumptions almost all messages are regular modulo $n$. More precisely, we give a probabilistic argument that for $k$-bit primes $p_1,\dots,p_r$ the probability that a random message fails to be regular modulo $n=p_1^{e_1}\dots p_r^{e_r}$ is at most $r/{2^{k-1}}$, which quickly tends to $0$ as $k\rightarrow \infty$, and which shows that our general scheme can be used even with primes of moderate length.