[2018 X-MAS CTF] Hanukkah

from Crypto.Util.number import isPrime
from random import getrandbits

def genKey(k):

    while True:
        r=getrandbits(k)
        while(r%2):
            r=getrandbits(k)

        p =  3 * r**2 +  2 * r + 7331
        q = 17 * r**2 + 18 * r + 1339
        n = p * q

        if(isPrime(p) and isPrime(q)):
            return (p,q) , n

def encrypt(m,pubkey):

    c=m**2 % pubkey
    return c

privkey,pubkey = genKey(256)

flag = open('flag.txt').read().strip()
while(len(flag)<125):
    flag+='X'
flag = int(flag.encode('hex'),16),

ct=encrypt(flag,pubkey)

with open('flag.enc','w') as f:
    f.write('ct = ' + str(ct))

with open('pubkey.txt','w') as f:
    f.write('pubkey = ' + str(pubkey))

with open('privkey.txt','w') as f:
    f.write('privkey = ' + str(privkey))

문제의 코드는 위와 같습니다.

$R$이 256bit이기 때문에 $P$와 $Q$는 512bit의 소수이고, $N(=PQ)$가 공개키이나 이를 소인수분해하는건 불가능에 가깝습니다. 하지만 $N$은 굉장히 쉽게 소인수분해를 해낼 수 있는데, 바로 $N$이 어떤 자연수 $r$에 대한 4차식으로 표현된다는 점 때문입니다. 이 점을 이용해 $r$을 binary search로 찾을 수 있습니다.

이렇게 $P$와 $Q$를 찾고 나면 $m$을 $P$로 나눈 나머지와 $m$을 $Q$로 나눈 나머지를 이차합동식을 해결함으로서 알아낼 수 있습니다.($P$와 $Q$가 $4k+3$ 꼴이기 때문에 $x^2=a \, mod \, P$의 해는 $ x=\pm a ^ {\frac{P+1}{4} }$ 로 계산할 수 있습니다.)

이후에 4가지 가능성에 대해 중국인의 나머지 정리로 m을 복원하면 됩니다.

코드

import binascii
def gcd(a, b):
  if a == 0: return b
  return gcd(b%a, a)

def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  g, y, x = egcd(b%a,a)
  return (g, x - (b//a) * y, y)

def inv(a, m):
  g, x, y = egcd(a, m)
  if g != 1:
    raise Exception('No modular inverse')
  return x%m

# x**2 = a (mod m), m is prime
def quad_congruence_equation(a, m):
  assert((m+1)%4 == 0)
  return pow(a, (m+1)//4, m)
# m must satisfies pairwise relatively prime
def crt(a, m):
  n = len(m)
  ret = a[0]
  mod = m[0]
  for i in range(1,n):
    m1 = mod
    mod *= m[i]
    m2inv = inv(m[i],m1)
    m1inv = inv(m1,m[i])
    ret = (ret*m[i]*m2inv+a[i]*m1*m1inv)%mod
  return ret

def f(r):
  return 51*r**4 + 88*r**3 + 128680*r**2 + 134636*r + 9816209

# 0x6161 -> 'AA'
def hexint2str(x):
  s = hex(x)[2:]
  if len(s) % 2 == 1: s = '0'+s
  return binascii.unhexlify(s).decode()

n = 577080346122592746450960451960811644036616146551114466727848435471345510503600476295033089858879506008659314011731832530327234404538741244932419600335200164601269385608667547863884257092161720382751699219503255979447796158029804610763137212345011761551677964560842758022253563721669200186956359020683979540809
c = 66888784942083126019153811303159234927089875142104191133776750131159613684832139811204509826271372659492496969532819836891353636503721323922652625216288408158698171649305982910480306402937468863367546112783793370786163668258764837887181566893024918981141432949849964495587061024927468880779183895047695332465
#### Recover p, q by binary search ####
st = 1
en = 2**256
while st < en:
  mid = (st+en)//2
  val = f(mid)
  if val > n: en = mid-1
  elif val == n: st,en = mid,mid
  else: st = mid+1

r = st
assert(f(r)==n)
p = 3 * r**2 +  2 * r + 7331
q = 17 * r**2 + 18 * r + 1339
########################################

#### Recover m mod p (=mp), m mod q (=mq) ####
ap = c % p
aq = c % q
mp = quad_congruence_equation(ap,p)
mq = q-quad_congruence_equation(aq,q) # two possibilities
assert((mp*mp - ap) % p==0)
assert((mq*mq - aq) % q==0)

###############################################

#### Recover m ####
m = crt([mp,mq],[p,q])
assert(m*m % n == c)
print(hexint2str(m))