Designing an Efficicient Public-Key Cryptosystem: Rabin-p vs. RSA

After completing this semester of studies at my university, I found myself continuing to ponder the material discussed in my Number Theory course, particularly regarding the unit of cryptography, which dove into various public-key cryptosystems, like Diffie-Hellman, ElGamal, and RSA. I remember one lecture in particular where we briefly discussed the Discrete Logarithm Problem and how it single-handedly forms the backbone of several cryptosystems. At a high level, most of the widely-used encryption schemes today rely on the computational difficulty of solving certain mathematical problems, like factoring large integers or computing discrete logarithms, as the problem name suggests. This piqued my interest, and I decided to explore further the computational efficiency of these systems and how they compare to one another. This post may be a bit more math-heavy than my usual fare, but my goal is to make the ideas concrete and intuitive, especially where performance and design tradeoffs matter.

RSA Overview

We begin with a brief overview of the RSA cryptosystem. Suppose you want to send me a message, encoded as an integer, over a public channel, securely. How can we go about this? We could, in theory, send the message directly or use a simple cipher, but an eavesdropper could easily intercept and decode it. So, the problem becomes: how can we ensure that only you can read the message, even if someone intercepts it? This is the essence of the study of public-key cryptography, and where RSA comes into play. In short, we need to provide just enough information to allow you to encrypt/decrypt messages, but not enough for an eavesdropper to do the same. To do so, we perform the following procedure. Suppose you wish to send me a message over a public channel:

I choose two large primes $p$ and $q$ , and compute $n = pq$ .
I compute $\varphi(n) = (p-1)(q-1)$ . This value helps us generate an exponent $e$ , chosen such that $\gcd(e, \varphi(n)) = 1$ .
I compute $d = e^{-1} \pmod{\varphi(n)}$ using the Extended Euclidean Algorithm. This value acts as my private key.
I publish the public key $(n, e)$ .
You encode your message $m$ as $M = m^e \pmod n$ and send me the ciphertext $M$ .
I decrypt the message by computing
$M^d \equiv m^{ed} \equiv m^{1 + k\varphi(n)} \equiv m \cdot m^{k\varphi(n)} \equiv m \pmod n.$

Aside: What on earth is that?

What I just outlined may seem like complete nonsense. Here are a few notes to hopefully clarify some of the madness.

We use large prime numbers for $p$ and $q$ since factoring $n$ into its original primes is believed to be computationally hard when the primes are sufficiently large.
$\varphi$ is Euler's Totient Function. For $n = pq$ , $\varphi(n)$ counts the number of integers less than $n$ that share no common divisors with $n$ . For these numbers, exponentiation $\bmod \, n$ behaves in cycles, and $\varphi(n)$ tells us how long it takes to return to where we started.
We require $\gcd(e, \varphi(n)) = 1$ so that a modular inverse $d$ exists. This is what allows the decryption step to undo encryption. Notably, this permits us to perform the second simplification in the above equation.
We only share $n$ and $e$ over the public channel. Without knowledge of $d$ , an eavesdropper will have a hard time decrypting the message.

This procedure and variants of it are widely used in modern encryption systems. But, can we improve upon this at all? While RSA is elegant and robust, modular exponentiation on a large scale can be computationally expensive. Although encryption is typically fast since the exponent $e$ is usually chosen to be small, commonly being $2^{16} + 1$ , decryption requires computing $M^d \pmod n$ where $d$ is a large integer of size comparable to $n$ . Even though some strategies like binary exponentiation reduce the number of operations, the cost of decryption grows with the number of bits in $d$ , resulting in many large-integer multiplications and modular reductions.

This raises a natural question: can we design a public-key cryptosystem with similar security guarantees, but with a cheaper decryption step? One promising direction comes from Rabin-style cryptosystems, which replace exponentiation with squaring: an operation that is significantly faster in practice. The tradeoff, however, is that decryption in the textbook Rabin cryptosystem leads to four possible plaintext results since, for $n = pq$ , calculating $\sqrt{M} \pmod p$ and $\sqrt{M} \pmod q$ yields two solutions each, much like how a positive number has two square roots over the integers. These results then combine to create four distinct square roots modulo $n$ (Chinese Remainder Theorem).

The Rabin-p Cryptosystem

This limitation is one of the primary reasons Rabin-style systems are rarely used. However, while exploring this design space, I came across a refinement known as the Rabin-p cryptosystem that resolves this ambiguity while preserving the efficiency benefits of squaring-based decryption. I will again step through the associated algorithms for encoding and decoding messages, following the Rabin-p cryptosystem as presented in Asbullah and Ariffin (2016). Suppose you wish to send me a message over a public channel:

I choose two large primes, $p$ and $q$ , satisfying $p \equiv 3 \pmod 4$ , $q \equiv 3 \pmod 4$ , as well as $2^k < p,q < 2^{k+1}$ for some integer $k$ . I then compute $n = p^2q$ . This is the public key that I publish.
You encode your message $m$ as $M = m^2 \pmod n$ , ensuring $\gcd(m, n) = 1$ before doing so. You send me the ciphertext $M$ .
To decrypt the ciphertext, I first reduce it modulo $p$ by computing $w \equiv M \pmod p$ .
Since $p \equiv 3 \pmod 4$ , I can efficiently compute a square root of $w$ modulo $p$ via $m_p \equiv w^{\frac{p+1}{4}} \pmod p$ . This is a result of Euler's Criterion that gives a value satisfying $m_p^2 \equiv M \pmod p$ .
At this point, $m_p$ is a square root modulo $p$ , but not necessarily modulo $p^2$ . To quantify exactly how far $m_p^2$ is from $M$ when the modulus is raised from $p$ to $p^2$ , I compute
$i = \frac{M - m_p^2}{p}.$
To lift the square root from modulo $p$ to modulo $p^2$ , I consider a small correction of the form $m_1 = m_p + jp$ and expand $(m_p + jp)^2$ . Matching the resulting expression to $M$ modulo $p^2$ forces the congruence $2m_p j \equiv i \pmod p$ , which I solve by computing $j \equiv i \cdot (2m_p)^{-1} \pmod p$ .
Using the correction term, I construct a square root modulo $p^2$ via $m_1 = m_p + jp$ . This value is the unique lift of $m_p$ modulo $p^2$ that satisfies $m_1^2 \equiv M \pmod{p^2}$ .
As with any square root modulo an odd modulus, exactly two roots modulo $p^2$ exist, differing by a sign. This ambiguity is combated by enforcing a message size constraint at encryption time. Exactly one of $m_1$ or $p^2 - m_1$ lies in the valid range $[0, 2^{2k-1})$ for $k$ as defined above. The decrypted message is $m = m_1$ if $m_1 < 2^{2k-1}$ , and $m = p^2 - m_1$ otherwise.

Aside: Notes on Rabin-p

By restricting $p \equiv 3 \pmod 4$ , we can ensure that square roots modulo $p$ can be computed efficiently using a single exponentiation $w^ {(p + 1) / 4} \pmod p$ . This avoids the need for square root algorithms.
The value $m_p$ computed in this way satisfies $m_p^2 \equiv M \pmod p$ , but this congruence alone does not constitute a solution modulo $p^2$ . The goal of the remaining steps is to lift this solution from modulo $p$ to modulo $p^2$ without introducing ambiguity.
The quantity $i = \frac{(M - m_p) ^ 2} {p}$ measures the exact discrepancy between $m_p^2$ and $M$ at the next power of $p$ . This division is well-defined because $m_p^2 \equiv M \pmod p$ by construction.
The correction step $m_1 = m_p + jp$ is an instance of
Hensel’s Lemma
applied to the polynomial $f(x) = x^2 - M$ . Writing a lifted candidate as $x = m_p + jp$ and expanding $(m_p + jp)^2 = m_p^2 + 2m_pjp + j^2p^2 \equiv m_p^2 + 2m_pjp \pmod{p ^ 2}$ and matching terms modulo $p^2$ results in the linear congruence $2m_p j \equiv i \pmod p$ . A full proof of this equivalence can be found in Lemma 3.3 in
Asbullah and Ariffin (2016)
, as cited above.
The inverse $(2m_p)^{-1} \pmod p$ always exists because $p$ is odd and because $m_p$ and $p$ are coprime ( $\gcd(m_p, p) = 1$ ) by construction of $M$ since $M$ is also guaranteed to be coprime with $p$ . This guarantees a unique solution $j \pmod p$ and, consequently, a unique lift $m_1 \pmod{p ^ 2}$ .

A full proof of correctness of the decryption algorithm can be found in the paper cited above.

Complexity Comparison

In terms of complexity, however, how does Rabin-p compare to RSA? At a high level, both schemes spend most of their time doing arithmetic on large integers. But how many multiplications and modular reductions do we need to perform encryption and decryption in both schemes? First, we notice that encryption is the simplest operation in both schemes, being $O(lg \; e)$ modular multiplications for RSA but only a single modular squaring in Rabin-p.

For decryption, the naive view is that RSA performs a single modular exponentiation $M^d \pmod{n}$ , with the exponent $d$ comparable in bit length to $n$ . On the other hand, Rabin-p performs a single exponentiation modulo $p$ , followed by a constant number of operations to perform the lift and extract the correct plaintext. Instead of doing work modulo $n$ , Rabin-p does work modulo $p$ .

However, this comparison is somewhat misleading. In practice, RSA decryption does not need to compute $M^d \pmod{n}$ directly. Instead, using the Chinese Remainder Theorem, one computes $d_1 = e^{-1} \pmod{p-1}$ and $d_2 = e^{-1} \pmod{q-1}$ , then evaluates $M^{d_1} \pmod{p}$ and $M^{d_2} \pmod{q}$ separately, and combines the results via CRT to recover $M^d \pmod{n}$ . Since each exponentiation now operates on numbers with roughly half the bit length of $n$ , each one is significantly cheaper. The tradeoff is that two exponentiations are required instead of one, but the reduction in operand size more than compensates in practice.

With this optimization in mind, the gap between RSA and Rabin-p narrows considerably. Both schemes ultimately perform their heavy arithmetic modulo factors of $n$ rather than modulo $n$ itself. Rabin-p still avoids full modular exponentiation in favor of a single exponentiation modulo $p$ plus a constant-cost Hensel lift, but RSA with CRT-based decryption is far more competitive than the naive comparison suggests. Each system makes a distinct tradeoff between efficiency, generality, and implementation complexity, and understanding these nuances is what makes the comparison worthwhile.

Edited April 9, 2026