zer0pts CTF 2022
Note : A JOURNEY TO GAIN KNOWLEDGE
#Anti-Fermat
source:
from Crypto.Util.number import isPrime, getStrongPrime
from gmpy import next_prime
from secret import flag
# Anti-Fermat Key Generation
p = getStrongPrime(1024)
q = next_prime(p ^ ((1<<1024)-1))
n = p * q
e = 65537
# Encryption
m = int.from_bytes(flag, 'big')
assert m < nbin
c = pow(m, e, n)
print('n = {}'.format(hex(n)))
print('c = {}'.format(hex(c)))
output:
Để ý:
q = next_prime(p ^ ((1<<1024)-1)) lúc này chính là giá trị prime kế tiếp của p xor pow(2,1024) -1
Điều thú vị ở đây pow(2,1024) -1 ở dạng binary chính là một dãy 0b1111...1111 khi xor với p chính là lật lại bit của p.
Ví dụ a=0b11110000 khi và b = 0b11111111 thì c = a xor b = 0b00001111 hay viết lại giá trị b = a+c
Ý tưởng khai thác:
Chi tiết trên ta có thể viết lại như sau: p + q'=(2**1024)-1 và p * q = n với q' lúc này là prime trước đó của q.
Khi thử mô phỏng lại mình thấy giá trị khoảng cách giữa q và q' không quá lớn => có thể brute force được .
Như vậy lúc này ta có: p * q = n và p + (q-i) = (2**1024)-1 với i là giá trị brute force từ đó tìm được p, q.
solve:
Good job! Here is the flag:\n+-----------------------------------------------------------+\n| zer0pts{F3rm4t,y0ur_m3th0d_n0_l0ng3r_w0rks.y0u_4r3_f1r3d} |\n+-----------------------------------------------------------+
Thanks for reading. Have a good day ❤️ !
Contact:
Last updated