Score:1

Crypto

Specific RSA challenge

darkside

10/18/23, 9:45 PM

It was a challenge from CTF (ended), but I didn't solve it.

p, q = keygen(512)
n = p * q
flag = bytes_to_long(flag)
enc = pow(n + 1, flag, n**3)

So we have module and encrypted flag. We don't know module's factors (p,q). I have tried some ways, search another writeups and read many topics, but I didn't find any information how solve it.

435

1 + 8

number-theory

Lev

10/19/23, 12:29 AM

I'm assuming pow() is the standard python function? In that case this is quite different from RSA. You are actually solving a discrete logarithm in $\mathbb{Z}_{n^3}$. You know $x$ and are trying to solve for $y$ where $x = (n+1)^y \mod n^3$

Lev

10/19/23, 12:42 AM

I think I have a solution. Hint: use the binomial theorem to expand $(n+1)^y$.

Lev

10/19/23, 12:58 AM

There might be a overflow issue depending on the size of the flag, but if it is less than 512 bits it works.

kelalaka

10/19/23, 6:55 AM

This was asked before, and given hint as use of binomial theorem. The post seems deleted and I couldn't find even by searching the deleted posts, sights!

darkside

10/19/23, 7:20 AM

@kelalaka yes I asked about it, but still don't solve =(

kelalaka

10/19/23, 7:28 AM

Haven't you tried the binomial theorem? It was easy to do after that hint. I would prefer that you wrote down what you had tried with the hint and where you failed. This was better for you learning curve...

Lev

10/19/23, 9:39 PM

@darkside if you're still stuck you can add your working so far, otherwise feel free to accept the answer below.

darkside

10/20/23, 10:16 PM

@Lev Solve it ! Thanks :))

Score:2

Crypto

Lev

10/19/23, 1:18 AM

To elaborate on my comment, let $y$ be the flag. You are trying to solve for y, given x and n:

$x = (n+1)^y \mod n^3$

If you take the binomial expansion of $(n+1)^y$, you will notice that the higher order terms will be 0 mod n^3. I.e. terms of the polynomial which are divisible by n^3. If you consider the remaining terms, there is one last trick to obtain y (reducing the value of $x$ mod a particular number).

+ 0

Elon Musk

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

EN: Specific RSA challenge

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.