Why does Shamir's Trick for RSA Work

Johny Dow

3/4/23, 4:47 PM

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

172

0 + 0

rsa

public-key

modular-arithmetic

fgrieu

3/4/23, 5:26 PM

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

Johny Dow

3/4/23, 7:36 PM

@fgrieu It is named Shamir's trick in [Topics in Cryptology – CT-RSA 2009](https://link.springer.com/book/10.1007/978-3-642-00862-7) and that's where I got the name from.

fgrieu

3/4/23, 8:27 PM

Yes, I now see it's in Matthieu Rivain, [Securing RSA against Fault Analysis by Double Addition Chain Exponentiation](https://eprint.iacr.org/2009/165.pdf) (updated version), originally [in proceedings of CT-RSA 2009](https://doi.org/10.1007/978-3-642-00862-7_31). Still, [this reference](https://doi.org/10.1007/978-1-4419-5906-5_1157) makes _Shamir's Trick_ synonymous of [_Simultaneous Exponentiation_](https://doi.org/10.1007/978-1-4419-5906-5_45).

fgrieu

2/2/24, 6:14 PM

Update: and [that reference too](https://doi.org/10.1007/3-540-44647-8_11), in [it's note 1](https://link.springer.com/content/pdf/10.1007/3-540-44647-8_11.pdf#Hfootnote.1).

Score:2

Crypto

Daniel S

3/4/23, 4:56 PM

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.

0 + 0

Johny Dow

3/4/23, 10:09 PM

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!

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Why does Shamir's Trick for RSA Work

TH: ทำไมเคล็ดลับของ Shamir สำหรับ RSA จึงใช้งานได้

RO: De ce funcționează trucul lui Shamir pentru RSA

RU: Почему прием Шамира для RSA работает

VI: Tại sao Thủ thuật của Shamir cho RSA hoạt động

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.