5
$\begingroup$

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.

|improve this question
$\endgroup$
  • 2
    $\begingroup$ Note: The original scheme was a signature scheme, not an encryption scheme. $\endgroup$ – Squeamish Ossifrage May 22 at 1:42
  • $\begingroup$ 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)$. $\endgroup$ – Squeamish Ossifrage May 22 at 2:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage May 22 at 3:05
  • $\begingroup$ 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$. $\endgroup$ – Squeamish Ossifrage May 22 at 3:12
  • 1
    $\begingroup$ You could try emailing Michael Rabin! $\endgroup$ – Squeamish Ossifrage May 22 at 3:13

Your Answer

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

Browse other questions tagged or ask your own question.