I have questions from http://link.springer.com/chapter/10.1007%2F3-540-68339-9_1

Suppose we have 2 messages $m_1$ and $m_2$ related by a known relation $m_2=m_1+1$. Suppose further the messages are encrypted under RSA with an exponent of $3$ using a single public modulus $N$. $c_i=m_i^3$ mod$N$, $i=1,2$

Then from $c_1,c_2,N$ we can calculate the secrete messages $m_i$ algebraically as follows: $\frac{c_2+2c_1-1}{c_2-c_1+2}=\frac{3m_1^3+3m_1^2+3m_1}{3m_1^2+3m_1+3}=m_1$ mod$N$.

When the exponent is 5, setting $c_1=m^5$ mod$N$ and $c_2=(m+1)^5$ mod$N$, we can find some $P(m)$ s.t. $\frac{mP(m)}{P(m)}$. (there is explicit $P(m)$ in the above paper.)

For an arbitrary exponent $e$, the author says it will always be possible to write down an equation analogous to them.

My question is: How can I find such equations? Even, I don't know the exponent 3 case. Please help!

  • $\begingroup$ You say: "I don't know the exponent 3 case". What's your issue with that? For $e=3$, given numerical values of $N$, $c_1$ and $c_2$, do you understand how to compute $m_1$ from $\frac{c_2+2c_1-1}{c_2-c_1+2}=m_1\pmod N$? Or do you "only" have difficulty deriving that equation? $\endgroup$
    – fgrieu
    Commented Jun 18, 2013 at 5:16
  • $\begingroup$ I can not derive that equation...Can you help me? $\endgroup$
    – Kojo
    Commented Jun 18, 2013 at 8:29

1 Answer 1


Following the notation in Low-Exponent RSA with Related Messages and with $\alpha=\beta=1$ for simplification, we'll assume $e$, $N$, $c_1=m^e\bmod N$ and $c_2=(m+1)^e\bmod N$ are known; we are trying to derive $m$, in range $[0…N-1]$.

For $e=3$, a little inspiration is enough. We get

$c_2-c_1≡(m+1)^3-m^3≡3⋅m^2+3⋅m+1\pmod N$ thus
$c_2-c_1+2≡3⋅(m^2+m+1)\pmod N$

$c_2+2⋅c_1≡(m+1)^3+2⋅m^3≡3⋅m^3+3⋅m^2+3⋅m+1\pmod N$ thus
$c_2+2⋅c_1-1≡3⋅m⋅(m^2+m+1)\pmod N$

Then $m⋅(c_2-c_1+2)≡c_2+2c_1-1\pmod N$.

From which it follows that $m=(c_2-c_1+2)^{-1}⋅(c_2+2⋅c_1-1)\bmod N$ when $\gcd(c_2-c_1+2,N)=1$ (which is likely).

Updated: after fixing serious mistakes, and restructuring, I hope the following explicitly constructs an expression $m=P(c_1,c_2)^{-1}⋅Q(c_1,c_2)\bmod N$ using $\mathcal{O}(e^2)$ terms, with the expressions $P$ and $Q$ dependent on the value of $e$ but independent of the value of $N$, $c_1$, $c_2$, and allowing to compute $m$ explicitly with high odds.

Our $P(c_1,c_2)$ and $Q(c_1,c_2)$ will be of the form $$P(c_1,c_2)=\sum_{i=0}^f\sum_{j=0}^{f-i}p_{i,j}⋅c_1^i⋅c_2^j$$ $$Q(c_1,c_2)=\sum_{i=0}^f\sum_{j=0}^{f-i}q_{i,j}⋅c_1^i⋅c_2^j$$ with integer coefficients $p_{i,j}$, $q_{i,j}$, the indexes $i$, $j$ in $[0…f]$ for some $f$ to be determined, and such that $m⋅P(m^e,(m+1)^e)-Q(m^e,(m+1)^e)$ is the null polynomial in $m$.

We can develop $m⋅P(m^e,(m+1)^e)-Q(m^e,(m+1)^e)$ into a polynomial in $m$ of degree $e⋅f+1$, with each of its $e⋅f+2$ coefficients a linear combination (dependent only on the value of $e$ and $f$) of the $p_{i,j}$ and $q_{i,j}$. Asserting that this is the null polynomial is equivalent to a system of $e⋅f+2$ linear equations in $\mathbb Z$ for the $(f+1)⋅(f+2)$ unknowns $p_{i,j}$ and $q_{i,j}$. This system has a trivial solution: $p_{i,j}=q_{i,j}=0$.

When $f=e-2$ and $e\ge3$, our linear system of equations in $\mathbb Z$ has more unknowns than equations (precisely: $e-2$ more). It thus has solutions beyond the trivial one. We can find such non-trivial solution by mere linear algebra (further, we can fix any $e-3$ for our unknowns to $0$). That gives us the desired expressions for $P(c_1,c_2)$ and $Q(c_1,c_2)$. Note that the solution can't have all the $p_{i,j}=0$ (as that would imply all the $q_{i,j}=0$); thus $\gcd(P(c_1,c_2),N)=1$ is likely.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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