DEV Community is a community of 665,273 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

picoCTF 2021 -Mind your Ps and Qs writeup-

Shitian Daxiang
Bio := struct {Identity, Undergrad, Research}{ "Ainu descendants", "π Data Science", "π¬ Privacy Preserving Data Mining"}

Description

In RSA, a small e value can be problematic, but what about N? Can you decrypt this?

Decrypt my super sick RSA:
c: 861270243527190895777142537838333832920579264010533029282104230006461420086153423
n: 1311097532562595991877980619849724606784164430105441327897358800116889057763413423
e: 65537

Solution

The RSA cryptosystem uses Euler's theorem, a theorem in number theory, and two prime numbers to implement the public key cryptosystem trick, and the difficulty of prime factorization of large numbers is the basis for its security.

Normally, it is better to implement the RSA cryptosystem and solve the problem, but in actual CTF, it is necessary to solve the problem as fast as possible, and in this article, we will use RsaCtfTool(https://github.com/Ganapati/RsaCtfTool
), which can solve the RSA cryptosystem quickly in CTF. In this article, we will use RsaCtfTool, which can solve RSA cryptosystem quickly by CTF. It is very simple to use, just give c, n, and e as optional arguments, and the plaintext will be returned.

``````\$  python3 /RsaCtfTool/RsaCtfTool.py -n 1311097532562595991877980619849724606784164430105441327897358800116889057763413423 -e 65537 --uncipher 861270243527190895777142537838333832920579264010533029282104230006461420086153423

private argument is not set, the private key will not be displayed, even if recovered.

[*] Testing key /var/folders/1c/vt_z3vzj2h9gnm0gqjtgyv8w0000gr/T/tmpsaz1c036.
[*] Performing pastctfprimes attack on /var/folders/1c/vt_z3vzj2h9gnm0gqjtgyv8w0000gr/T/tmpsaz1c036.
100%|βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ| 113/113 [00:00<00:00, 303818.17it/s]
[*] Performing system_primes_gcd attack on /var/folders/1c/vt_z3vzj2h9gnm0gqjtgyv8w0000gr/T/tmpsaz1c036.
100%|βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ| 6998/6998 [00:00<00:00, 490782.52it/s]
[*] Performing factordb attack on /var/folders/1c/vt_z3vzj2h9gnm0gqjtgyv8w0000gr/T/tmpsaz1c036.
[*] Attack success with factordb method !

Results for /var/folders/1c/vt_z3vzj2h9gnm0gqjtgyv8w0000gr/T/tmpsaz1c036:

Unciphered data :
HEX : 0x007069636f4354467b736d6131315f4e5f6e305f67306f645f31333638363637397d
INT (big endian) : 13016382529449106065927291425342535437996222135352905256639573959002849415739773
INT (little endian) : 3711971977671268622040852236510036125495501942684770673221105381148513202625671168
STR : b'\x00picoCTF{sma11_N_n0_g0od_13686679}'
``````

Conclusion

In the world of hackers, people who can't solve problems well without using tools made by others are called script kiddies. I honestly don't care, but I recommend you to implement RSA cryptography from scratch for the sake of learning.