CTF question with hint "Quadratic method to solve ifp problem"

shanzhuer

10/29/23, 12:41 PM

I totally have no idea about this Rabin decrypt problem. source code:

https://github.com/shanzhuer/myctf/blob/main/crypto/rabin.py

Inside there were $2^{21}$ times of encryption and decryption of Rabin-cryptosystem, with 126 bytes plaintext, 1024-bit public key $N$(unknown 512-bit $p$ and $q$ when $p*q=N$)

the output log is $\dfrac{140}{2^{21}}$ decrypt failure because $2$ small root of ciphertext(less than 126 bytes) exists

and the hint is "Quadratic method to solve if p problem"

I was trying several days to find out how to use the Quadratic method to factor $N$ in this question but didn't work

Can anyone help?

131

0 + 8

rabin-cryptosystem

factoring

kelalaka

10/29/23, 2:32 PM

@kodlu https://crypto.meta.stackexchange.com/q/1106/18298 Well, you might [not spoil the flag with a hash commitment as I did](https://crypto.stackexchange.com/a/89563/18298)

shanzhuer

10/30/23, 2:06 AM

i think there is probably some kind of relationship between ciphertext has 2 small roots and factors of N. but i tried many times and didn't work out. if the program print out the values of 2 small roots then i can calculate p from gcd(root1-root2,N). but the program only print out one of the two small roots.

ddddavidee

10/30/23, 11:01 AM

@shanzhuer did you read about the Quadratic Sieve as a factorization method? (https://en.wikipedia.org/wiki/Quadratic_sieve)

shanzhuer

10/30/23, 12:16 PM

@ddddavidee yes i did but it's very hard to find out two different x!=y when x^2=y^2 mod n in this question

ddddavidee

10/30/23, 1:41 PM

@shanzhuer, try to understand *why* the decryption failed. The Rabin cryptosystem maps 4 plaintexts into the same ciphertext. So when you decrypt and fine the 4 square roots, you need to decide which one is the correct to keep. If you have two different square roots... can you do something?

shanzhuer

10/30/23, 2:34 PM

@ddddavidee i already know gcd(root1-root2,N) is factor for N. but now i just have one of the two small roots. so sad

ddddavidee

10/31/23, 7:42 AM

Could you please link to the original CTF?

shanzhuer

10/31/23, 9:21 AM

@ddddavidee it's just an internal competition and only one anonymous team solves.

Elon Musk

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

EN: CTF question with hint "Quadratic method to solve ifp problem"

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.