zer0pts CTF 2022 : Anti-Fermat

roaris commented 2 days ago

https://alpacahack.com/challenges/anti-fermat

roaris commented 2 days ago

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 < n
c = pow(m, e, n)

print('n = {}'.format(hex(n)))
print('c = {}'.format(hex(c)))

pip install gmpyしたら、エラーになった gmpyは古いらしいので https://stackoverflow.com/questions/77392893/cant-install-gmpy-on-windows 、from gmpyではなく、from gmpy2にして、pip install gmpy2したら動いた

roaris commented 2 days ago

$q$ を $p$ に基づいて決めていて $q$ を $p$ を使った式で表せれば、変数を1個消せる $p$ は1024bitなので $p \oplus (2^{1024} - 1) = 2^{1024} - 1 -p$ であるこれに $d$ を足して $q = 2^{1024} - 1 - p + d$ と表すことにする $d$ を0から10000まで全探索して $p * (2^{1024} - 1 - p + d) = n$ を $p$ の2次方程式として解けばよい(#73 と同様)

from math import isqrt
from Crypto.Util.number import long_to_bytes

n = 0x1ffc7dc6b9667b0dcd00d6ae92fb34ed0f3d84285364c73fbf6a572c9081931be0b0610464152de7e0468ca7452c738611656f1f9217a944e64ca2b3a89d889ffc06e6503cfec3ccb491e9b6176ec468687bf4763c6591f89e750bf1e4f9d6855752c19de4289d1a7cea33b077bdcda3c84f6f3762dc9d96d2853f94cc688b3c9d8e67386a147524a2b23b1092f0be1aa286f2aa13aafba62604435acbaa79f4e53dea93ae8a22655287f4d2fa95269877991c57da6fdeeb3d46270cd69b6bfa537bfd14c926cf39b94d0f06228313d21ec6be2311f526e6515069dbb1b06fe3cf1f62c0962da2bc98fa4808c201e4efe7a252f9f823e710d6ad2fb974949751
cipher = 0x60160bfed79384048d0d46b807322e65c037fa90fac9fd08b512a3931b6dca2a745443a9b90de2fa47aaf8a250287e34563e6b1a6761dc0ccb99cb9d67ae1c9f49699651eafb71a74b097fc0def77cf287010f1e7bd614dccfb411cdccbb84c60830e515c05481769bd95e656d839337d430db66abcd3a869c6348616b78d06eb903f8abd121c851696bd4cb2a1a40a07eea17c4e33c6a1beafb79d881d595472ab6ce3c61d6d62c4ef6fa8903149435c844a3fab9286d212da72b2548f087e37105f4657d5a946afd12b1822ceb99c3b407bb40e21163c1466d116d67c16a2a3a79e5cc9d1f6a1054d6be6731e3cd19abbd9e9b23309f87bfe51a822410a62
e = 65537

for d in range(10000):
    a = 1
    b = 1 - d - (1<<1024)
    c = n
    D = b*b - 4*a*c
    rD = isqrt(D)

    if D >= 0 and rD ** 2 == D and (-b+rD) % (2*a) == 0:
        p = (-b+rD) // (2*a)
        q = n // p
        phi = (p - 1) * (q - 1)
        d = pow(e, -1, phi)
        print(long_to_bytes(pow(cipher, d, n)).decode())

roaris commented 2 days ago

問題文でフェルマーの素因数分解について書かれていたので調べていたが、一切関係なかった一応、実装してみた

from math import isqrt

def fermat(n):
    assert n % 2 == 1
    x = 1 + isqrt(n - 1) # https://docs.python.org/ja/3/library/math.html#math.isqrt

    while True:
        y2 = x * x - n
        y = isqrt(y2)

        if y * y == y2:
            break

        x += 1

    return x + y, x - y

print(fermat(21)) # (7, 3)

roaris / ctf-log

zer0pts CTF 2022 : Anti-Fermat #90