[zer0pts CTF 2022] ok

server.py

from Crypto.Util.number import isPrime, getPrime, getRandomRange, inverse
import os
import signal

signal.alarm(300)

flag = os.environ.get("FLAG", "0nepoint{GOLDEN SMILE & SILVER TEARS}")
flag = int(flag.encode().hex(), 16)

P = 2 ** 1000 - 1
while not isPrime(P): P -= 2

p = getPrime(512)
q = getPrime(512)
e = 65537
phi = (p-1)*(q-1)
d = inverse(e, phi)
n = p*q

key = getRandomRange(0, n)
ciphertext = pow(flag, e, P) ^ key

x1 = getRandomRange(0, n)
x2 = getRandomRange(0, n)

print("P = {}".format(P))
print("n = {}".format(n))
print("e = {}".format(e))
print("x1 = {}".format(x1))
print("x2 = {}".format(x2))

# pick a random number k and compute v = k**e + (x1|x2)
# if you add x1, you can get key = c1 - k mod n
# elif you add x2, you can get ciphertext = c2 - k mod n
v = int(input("v: "))

k1 = pow(v - x1, d, n)
k2 = pow(v - x2, d, n)

print("c1 = {}".format((k1 + key) % n))
print("c2 = {}".format((k2 + ciphertext) % n))

(We denote $\text{key}= K, \text{pow(flag,e,P)} = C$)

 

It is an oblivious transfer. OT is secure scheme but in this problem, there is an relation with two message $m_1 = K, m_2 = (C \oplus K)$.

 

When we set $v = (x_1 + x_2) / 2$, $c_1 + c_2 = m_1 + m_2 = K + (C \oplus K) \text{ mod } N$. We denote $M = K + (C \oplus K) \text{ mod } N$.

 

When we assume that $C$ is odd,  $K + (C \oplus K)$ must be odd. Therefore if $M$ is odd, $K + (C \oplus K) = M$. If $M$ is even, $K + (C \oplus K) = M + N$, which means that $\text{mod } N$ can be removed and the same goes for $C$ is even.

 

Now is time to recover each bits of $C$. If $bit(C, i)$ is 1, then $bit(K, i) + bit(C \oplus K, i) = 1$. $bit(M, i) = 0$(resp. $bit(M, i) = 1$) implies carry of $i+1$ bit is 1(resp. 0).

 

Therefore if $bit(C, i)$ is 1, $bit(M, i+1)$ must be consistent for $M \in \{M | bit(M, i) = 0\}$. If inconsitent, $bit(C, i)$ is 0.

 

solver.py

from Crypto.Util.number import *


datas = []


f = open('dd.txt', 'r') # it contains list of (n,c1,c2) tuple
lines = f.readlines()
for line in lines:
  datas.append(list(map(int, line.split())))


def bit(x, i):
  if x & (1<<i): return 1
  return 0

'''
def custom_data_gen():  
  P = 2**1000 - 1245
  #C = getRandomRange(0,P)
  #if C&1: C^=1
  C = 0b11001111110101
  print(C)
  for _ in range(1000):
    n=0
    while n%2==0:
      n = getRandomRange(1<<1022,1<<1024)
    K = getRandomRange(0, n)  
    datas.append([n,C^K,K])
    V = K + (C^K)    

custom_data_gen()
'''

# assume that C is odd
def recover_C_odd():
  Ms = []
  for n,c1,c2 in datas:
    # M = K + (C^K)
    #print(c1,c2)
    M = (c1+c2) % n
    #print(M)
    if M % 2 == 0:
      M += n
    Ms.append(M)

  cnt = [0]*1000
  C = 1
  for i in range(1,1000):
    M_bit0 = []
    M_bit1 = []    
    for M in Ms:
      if bit(M, i):
        M_bit1.append(M)
      else:
        M_bit0.append(M)
    # Trivial case
    if not M_bit0:
      # i-th bit is 1
      C ^= (1<<i)
      continue
    if not M_bit1:
      # i-th bit is 0
      continue

    # if i-th bit is 0, then bit(M, i+1) for M in M_bit0 is inconsitent
    s = set()
    for M in M_bit0:
      s.add(bit(M,i+1))
    # bit(M, i+1) for M in M_bit0 is consitent -> i-th bit is 1
    if len(s) == 1:
      C ^= (1<<i)
      continue
    else:
      continue
  P = 2**1000 - 1245
  e = 65537
  d = pow(e,-1,P-1)
  print(long_to_bytes(pow(C,d,P)))
  
        

# assume that C is even
def recover_C_even():
  pass

recover_C_odd()