breaking RSA with linear padding using Hastads attack with e>=11

rozi

1/14/23, 6:13 PM

I have been playing around with Hastad's broadcast attack on RSA with linear padding. Using the implementation and the test function from here: https://github.com/0n5/CTF-Crypto/blob/master/RSA/hastads.sage

The test function and the attack work perfectly well with e=3,5,7. However, with e>=11 the attack does not find a solution. I tried playing around with the values of eps and modifying the attack to use more inputs (which shouldn't be needed), but the attack still fails.

Is there any reason for why the attack fails with a slightly larger e?

596

0 + 0

rsa

attack

Score:5

Crypto

Samuel Neves

1/14/23, 11:27 PM

The Coppersmith method, as usually stated with the $\epsilon$ factor, finds a root of a polynomial $f(x)$ of degree $d$ modulo $n$ of size $x \le n^{\frac{1}{d} - \epsilon}$, $0 < \epsilon \le 1/7$.

The Håstad attack with $e = 11$ is fundamentally an application of the Coppersmith method with $f(x)$ of degree $11$ modulo $n_0\cdot n_1 \cdot \dots n_{e-1}$. If $\epsilon = 1/8$, then the above bound is useless, seeing that $\left( n_0\cdot n_1 \cdot \dots n_{e-1} \right)^{1/11 - 1/8} < 1$. This is also why it worked without modification up to $e = 7$: $\left(2^{2048\cdot 7}\right)^{1/7 - 1/8} \approx 2^{256}$.

However, decreasing $\epsilon$ does work: setting $\epsilon = 1/13$ we will already find all roots below $\left(2^{2048\cdot 11}\right)^{1/11 - 1/13} \approx 2^{315}$, which is enough to recover this flag.

0 + 0

Elon Musk

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

EN: breaking RSA with linear padding using Hastads attack with e>=11

TH: breaking RSA with linear padding using Hastads attack with e>=11

RO: breaking RSA with linear padding using Hastads attack with e>=11

RU: breaking RSA with linear padding using Hastads attack with e>=11

VI: breaking RSA with linear padding using Hastads attack with e>=11

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.