4
$\begingroup$

I have a question about this attack: Oded Yacobi and Yacov Yacobi, A New Related Message Attack on RSA (in proceedings of PKCS2005).

Given $e$ linear related messages encrypted with RSA: $c_i = ({x_i}^e \bmod N)$

where, $x_i = a_i*x + b_i$,

the author claims that given the $a_i$'s and $b_i$'s values, it is possible to obtain the original message $m$. He shows that for the case of $x_i = x + b$, but I can't see how is the general form to apply this attack for messages $x_i = a_i*x + b_i$.

More specifically, I'm having difficulties in calculating the $p_k$ values presented in section 2.2.

Thanks!

$\endgroup$
5
$\begingroup$

The ability to recover $x$ in the latter case is a direct consequence of RSA's homomorphic property and the ability to recover $x$ in the former case.

Suppose you are given the equations (with $c_i,a_i,b_i$ known):

$$c_i=(a_i\cdot x+b_i)^e\bmod N$$ $$\iff c_i=(a_i\cdot x+a_i\cdot b_i\cdot a_i^{-1})^e\bmod N$$ $$\iff c_i=a^e_i(x+b_i\cdot a_i^{-1})^e\bmod N$$ $$\iff c_i\cdot a^{-e}_i =(x+b_i\cdot a_i^{-1})^e\bmod N$$ $$\iff c_i' =(x+b'_i)^e\bmod N$$

With $b_i':=b_i\cdot a_i^{-1}$ and $c_i':=c_i\cdot a^{-e}_i$ which both only depend on known quantities, as you can always find multiplicative inverse $\bmod N$ (or if you can't in one instance, you can factor $N$) and you know $e,c_i,a_i,b_i$.

So you can use the ability to recover $y$ from $g_i=(y+f_i)^e\bmod N$ to recover (using the above equations) $x$ from $c_i=(a_i\cdot x+b_i)^e\bmod N$.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ That is right. Thank you. I wonder if there is a way to compute that when the public keys have the same exponent but different modulo (e, Ni). $\endgroup$ – Pedro Barbosa Apr 22 '17 at 18:01

Your Answer

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

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