# Why did Rabin use $x(x + b)$ instead of just $x^2$ in the original paper?

Encryption in the original Rabin scheme took a message $$x$$ and computed $$x(x + b) \bmod n$$, where $$0 \le b \lt n$$ and $$n$$ is the product of two secret primes $$p$$ and $$q$$. The private key is defined as $$(p,q)$$ and the public key as $$(b,n)$$. Modern Rabin encryption however is defined as computing $$x^2 \bmod n$$, which is equivalent to the original scheme with $$b = 0$$. Why is this? Why is the $$b$$ variable now ignored?

This question is based on a question which I found interesting but which was mysteriously self-deleted.

• Note: The original scheme was a signature scheme, not an encryption scheme. – Squeamish Ossifrage May 22 at 1:42
• Specifically, in the original scheme as described by Rabin in 1979, a public key is a pair of integers $(n, b)$ with $0 \leq b < n$, and a signature on a message $M$ is a pair $(x, U)$ of an integer $0 \leq x < n$ and a bit string $U$ such that $x(x + b) \equiv H(M, U) \pmod n$, where $H$ is a randomized hash function. The signer knows the secret factors $p$ and $q$ of $n$ by which they can solve for $x$ modulo $p$ and $q$ separately (if it exists, otherwise retry with another $U$). The paper uses the slightly confusing notation $C(MU)$, for ‘compressing function’, where I wrote $H(M, U)$. – Squeamish Ossifrage May 22 at 2:49
• The description on Wikipedia today is bad and misrepresents nearly all of the details from the original paper; obviously it was written by someone—or by a stumbling uncoordinated collective—who never bothered to actually read the paper and instead transcribed a secondhand game of telephone, as is mandated by the priests of Wikipedia who are apparently allergic to primary sources. – Squeamish Ossifrage May 22 at 3:05
• The factoring reduction, Theorems 1 and 2, applies to any square root algorithm, which can be derived, as the paper shows, from an $x(x+b)$ forger: to compute $\sqrt m$, find $x$ solving $x(x+b)=m-(b/2)^2$, since then $m=x^2+bx+(b/2)^2=(x+b/2)^2$ so that $x+b/2=\pm\sqrt m$. The algorithms for using the private key to solve $x(x+b)=c$ detailed in §2 are simpler if $b=0$: for $p\equiv3\pmod4$, compute $\pm(c+b^2/4)^{(p + 1)/4}-b/2$; for $p\equiv1\pmod4$, compute $$\gcd(x^{(p-1)/2}-1,(x+\delta)^2+b(x+\delta)-c)$$ for random $\delta$ until a factor $x+\delta-\alpha$ falls out and return $\alpha$. – Squeamish Ossifrage May 22 at 3:12
• You could try emailing Michael Rabin! – Squeamish Ossifrage May 22 at 3:13