# Linear Related Message Attack on RSA

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!

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$.