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


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?

  • $\begingroup$ @kodlu crypto.meta.stackexchange.com/q/1106/18298 Well, you might not spoil the flag with a hash commitment as I did $\endgroup$
    – kelalaka
    Commented Oct 29, 2022 at 14:32
  • $\begingroup$ 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. $\endgroup$
    – shanzhuer
    Commented Oct 30, 2022 at 2:06
  • $\begingroup$ @shanzhuer did you read about the Quadratic Sieve as a factorization method? (en.wikipedia.org/wiki/Quadratic_sieve) $\endgroup$
    – ddddavidee
    Commented Oct 30, 2022 at 11:01
  • $\begingroup$ @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 $\endgroup$
    – shanzhuer
    Commented Oct 30, 2022 at 12:16
  • $\begingroup$ @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? $\endgroup$
    – ddddavidee
    Commented Oct 30, 2022 at 13:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.