I have read that Shamir's trick can protect RSA with CRT against fault attacks. However, it is not clear to me why the following equations $$ s_{p}^{*}=m^{d \bmod \varphi(p \cdot t)} \bmod p \cdot t \\ s_{q}^{*}=m^{d \bmod \varphi(q \cdot t)} \bmod q \cdot t $$ imply that: $$ s_{p}^{*} = s_{q}^{*} \bmod t $$
4
-
2$\begingroup$ That's not Shamir's trick as I know it, which computes $x^a\,y^b\bmod n$ at roughly 60% the cost of computing it as $(x^a\bmod n)\,y^b\bmod n$. OTOH Shamir surely has many tricks. Also, while the equation stated holds, that's not the standard countermeasure against fault attacks, which is to check $s^e\bmod n=m$. $\endgroup$– fgrieu ♦Commented Nov 4, 2021 at 17:26
-
1$\begingroup$ @fgrieu It is named Shamir's trick in Topics in Cryptology – CT-RSA 2009 and that's where I got the name from. $\endgroup$– Johny DowCommented Nov 4, 2021 at 19:36
-
1$\begingroup$ Yes, I now see it's in Matthieu Rivain, Securing RSA against Fault Analysis by Double Addition Chain Exponentiation (updated version), originally in proceedings of CT-RSA 2009. Still, this reference makes Shamir's Trick synonymous of Simultaneous Exponentiation. $\endgroup$– fgrieu ♦Commented Nov 4, 2021 at 20:27
-
$\begingroup$ Update: and that reference too, in it's note 1. $\endgroup$– fgrieu ♦Commented Feb 2, 2023 at 18:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
We have $\varphi(t)|\varphi(pt)$ and $\varphi(t)|\varphi(qt)$ so that if $d_1$ and $d_2$ are the exponents for $s_p^*$ and $s_q^*$ then $d=d_1+k_1\varphi(t)$ and $d=d_2+k_2\varphi(t)$ for some integers $k_1$ and $k_2$. It follows that $d_1=d_2+(k_2-k_1)\varphi(t)$ and hence $$d_1\equiv d_2\pmod{\varphi(t)}.$$
It follows that $m^{d_1}\equiv m^{d_2}\pmod t$ by Euler's theorem.
-
$\begingroup$ I just realized that I don't really understand why $d_1\equiv d_2\pmod{\phi(t)}$ could you explain this further? Thank you! $\endgroup$ Commented Nov 4, 2021 at 22:09