Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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!

share|improve this question
    
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? –  fgrieu Jun 18 '13 at 5:16
    
I can not derive that equation...Can you help me? –  Kojo Jun 18 '13 at 8:29
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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