# PBjar CTF 2021

Team. OAO
Point. 3094 (9/9 Crypto)
Rank. 95

## Convert

enc = 666c61677b6469735f69735f615f666c346767675f68317d

import binascii
from output import *

flag = binascii.unhexlify(enc)
print(flag)

:::success
flag{dis_is_a_fl4ggg_h1}
:::

## ReallynotSecureAlgorithm

:::spoiler **Source Code**

from Crypto.Util.number import *
with open('flag.txt','rb') as f:
    flag = f.read().strip()
e=65537
p=getPrime(128)
q=getPrime(128)
n=p*q
m=bytes_to_long(flag)
ct=pow(m,e,n)


print (p)
print (q)
print (e)
print (ct)

:::

Standard RSA :)

:::spoiler **Script**

from Crypto.Util.number import long_to_bytes
from output import *

pt = pow(c, pow(e, -1, (p-1)*(q-1)), p*q)

flag = long_to_bytes(pt)
print(flag)

:::

:::success
flag{n0t_to0_h4rd_rIt3_19290453}
:::

## Not_Baby

:::spoiler **Source Code**

from Crypto.Util.number import *

with open('flag.txt','rb') as g:
    flag = g.read().strip()

with open('nums.txt','r') as f:
	s=f.read().strip().split()
	a=int(s[0])
	b=int(s[1])
	c=int(s[2])


e=65537
n=a**3+b**3-34*c**3
m=bytes_to_long(flag)
ct=pow(m,e,n)


print ("n: ",n)
print ("e: ",e)
print ("ct: ",ct)

:::

One can factor the modulus $n$ using FactorDB API ...

:::spoiler **Script**

from pwn import *
from factordb.factordb import FactorDB
from output import *

f = FactorDB(n)
f.connect()

primes = f.get_factor_from_api()

phi = 1

for _ in primes:
	p = int(_[0])
	exp = _[1]

	phi *= (p ** (exp - 1)) * (p-1)

pt = pow(ct, pow(65537, -1, phi), n)

from Crypto.Util.number import long_to_bytes

flag = long_to_bytes(pt)
print(flag)	

:::

:::success
flag{f4ct0ring_s0000oo00000o00_h4rd}
:::

## Knapsack

:::spoiler **Source Code**

from Crypto.Util.number import getPrime
from sympy import nextprime
from random import randint

flag = open('./flag.txt', 'rb').read().strip()
flagbits = bin(int.from_bytes(flag, 'big'))[2:]

n, r = len(flagbits), getPrime(8)

w = [randint(1, 69)]
for i in range(1, n):
    w.append(randint(sum(w[:i]) + 1, w[-1] * r))

q = nextprime(r * w[-21])

b = [r * i % q for i in w]
c = sum((0 if i == '0' else 1) * j for i, j in zip(flagbits, b))

f = open('./output.txt', 'w')

print('b: ' + str(b), file = f)
print('c: ' + str(c), file = f)

f.close()

:::

Standard Knapsack cryptosystem, just perform [LDA attack](https://eprint.iacr.org/2007/066.pdf)

:::spoiler **Script**

# Sage
from output import *

n = len(Public_key)

L = Matrix(ZZ, n+1, n+1)
N = ceil(n^0.5 / 2)
        
for i in range(n + 1):
    for j in range(n + 1):
        if j == n and i < n:
            L[i, j] = 2 * N * Public_key[i]
        elif j == n:
            L[i, j] = 2 * N * enc_Flag
        elif i == j:
            L[i, j] = 2
        elif i == n:
            L[i, j] = 1
        else:
            L[i, j] = 0

B = L.LLL()

for i in range(n + 1):
    if B[i, n] != 0:
        continue

    if all(v == -1 or v == 1 for v in B[i][:n]):
        ans = [ (-B[i, j] + 1) // 2 for j in range(n)]
        calc_sum = sum(map(lambda x: x[0] * x[1], zip(Public_key, ans)))
        
        if calc_sum == enc_Flag:
            binary_Flag = ""
            for _ in range(n):
                binary_Flag += str(ans[_])
                Flag = int(binary_Flag, 2)
            print(Flag)

:::

:::success
flag{b4d_r_4nd_q_1s_sc4ry}
:::

## MRSA

:::spoiler **Source Code**

from Crypto.Util.number import *


with open('flag.txt','rb') as f:
    flag = f.read().strip()

e=65537
p=getPrime(256)
q=getPrime(128)
n=p*q
m=bytes_to_long(flag)
ct=pow(m,e,n)

print ('n:',n)
print ('e:',e)
print ('ct:',ct)

def enc(msg):
    print (p%msg)
try:
    br="#"
    print (br*70)
    print ("Now here's the More part!!!")
    print ("Enter some number, and I will encrypt it for you")
    print ("But you gotta follow the condition that your number gotta be less than q (and like legitamite)")
    print (br*70)
    s=int(input("Enter: ").strip())
    assert(s>0 and s<q)        
    enc(s)
except:
    print ("Bruh why you be like this")
    exit()

:::

We can ask for the residue of $n$ divided by our input $k$. A straightforward solution is:
1. Send $k = 2^{127}$ to the server and get the last $127$-bits of $p$
2. Perform partial $p$ exposure attack (Modify [script](https://github.com/mimoo/RSA-and-LLL-attacks) from mimoo)

:::spoiler **Script**

# Sage

from __future__ import print_function
import time

debug = False

# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print(a)

def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
    #
    # init
    #
    dd = pol.degree()
    nn = dd * mm + tt

    #
    # Coppersmith revisited algo for univariate
    #

    # change ring of pol and x
    polZ = pol.change_ring(ZZ)
    x = polZ.parent().gen()

    # compute polynomials
    gg = []
    for ii in range(mm):
        for jj in range(dd):
            gg.append((x * XX)**jj * modulus**(mm - ii) * polZ(x * XX)**ii)
    for ii in range(tt):
        gg.append((x * XX)**ii * polZ(x * XX)**mm)
    
    # construct lattice B
    BB = Matrix(ZZ, nn)

    for ii in range(nn):
        for jj in range(ii+1):
            BB[ii, jj] = gg[ii][jj]

    # display basis matrix
    if debug:
        matrix_overview(BB, modulus^mm)

    # LLL
    BB = BB.LLL()

    # transform shortest vector in polynomial    
    new_pol = 0
    for ii in range(nn):
        new_pol += x**ii * BB[0, ii] / XX**ii

    # factor polynomial
    potential_roots = new_pol.roots()
    # print("potential roots:", potential_roots)

    # test roots
    roots = []
    for root in potential_roots:
        if root[0].is_integer():
            result = polZ(ZZ(root[0]))
            if gcd(modulus, result) >= modulus^beta:
                roots.append(ZZ(root[0]))

    # 
    return roots
   
N = 22462929226230698839733727530532826254264355600156744007766926652422587544315761736758772358470826527492517915601901
p_low = 123816289112636220809301414050217986899 

F.<x> = PolynomialRing(Zmod(N), implementation='NTL'); 
pol = 2^127 * x + p_low
pol = pol.monic()
dd = pol.degree()

# PLAY WITH THOSE:
beta = 0.6                             # we should have q >= N^beta
epsilon = beta / 7                     # <= beta/7
mm = ceil(beta**2 / (dd * epsilon))    # optimized
tt = floor(dd * mm * ((1/beta) - 1))   # optimized
XX = ceil(N**((beta**2/dd) - epsilon)) # we should have |diff| < X

# Coppersmith
start_time = time.time()
roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)

# output
print("\n# Solutions")
print("we found:", roots)
print(("in: %s seconds " % (time.time() - start_time)))

p = 2^127 * roots[0] + p_low
q = N // p

e = 65537
ct = 783513924331267748616897862708377643116691425522576921126356389765414000280824908377536276625570472081680799255651

pt = pow(ct, pow(e, -1, (p-1)*(q-1)), N)

from Crypto.Util.number import long_to_bytes

flag = long_to_bytes(pt)
print(flag)

:::

:::success
flag{1dk_what_to_wr1te_h3re_s0_hii_ig}
:::

## leftovers

:::spoiler **Source Code**

from random import *

def gen():
  mod=randint(10**9,10**10)
  while (mod%2==0):
    mod=randint(10**9,10**10)
  return mod

mod=gen()
small=mod
while True:
  for i in range(2,int((mod+5)**(1/2))):
    if mod%i==0:
      small=i
      break
  if small!=mod:
    mod*=small
    break
  mod=gen()

lst=[]
for i in range(small-1):
  lst.append(1)
r=randint(min(10,small-1),small*3)
for i in range(r):
  lst.append(0)
  
shuffle(lst)
print ("Alright, I will send you a string, where each char contains either 0 or 1.")
print ("Then you will send me a list of integers back with the same size, separated by spaces.")
print ("Now for each number in your list, a, if it satisfies a to the power of "+str(small)+" is congruent to 1 mod "+str(mod)+" it will encode to 1.")
print ("Otherwise, your number will encode to 0. Now I will concattenate all of your encoded numbers into a string.")
print ("If this string equals the original string I sent you, then you will get the flag :yayy:.")
print ("One final caveat: all your numbers must be unique and positive integers greater than 1 and less than "+str(mod)+".")
string=""
for i in lst:
  string+=str(i)
print (string)

s=input("Enter: ").strip().split()
s=[int(i) for i in s]
check=True
for i in s:
  if i>=mod or i<=1:
    check=False
    break
check=check & (len(s)==len(lst))
check=check & (len(s)==len(set(s)))

cs=""
for i in s:
  if pow(i,small,mod)==1:
    cs+="1"
  else:
    cs+="0"
check=check & (cs==string)

if check:
  with open('flag.txt','rb') as f:
      flag = f.read().strip()
  print (flag)
else:
  print ("Better luck next time!")

:::

The server chooses a random number $n$ around $10^{10}$ and its smallest prime divisor $p$. Our goal is to find $p-1$ different non-trivial elements $a_1, \dots, a_{p-1}$ in $\mathbb{Z}/n\mathbb{Z}$ such that $$a_{i}^p \equiv 1 \pmod{n}, \quad \forall i = 1, \dots, p-1$$

and different $k$ different elements $b_1, \dots, b_k$ in $\mathbb{Z}/n\mathbb{Z}$ such that $$b_{i}^p \not\equiv 1 \pmod{n}, \quad \forall i = 1, \dots, k$$

* **Lazy.** Use solve_mod function :)
* **Non-Lazy.** Factorize $n$ and brute-force all roots for each prime power. Apply CRT to get $p$-th roots of $n$

:::spoiler **Script**

mod = 13373207811
small = 3

lst = "0110"

x = var('x')
roots = solve_mod([x^small == 1], mod)

print(roots)
cnt1, cnt2 = 0, 1

ans = []

for _ in range(len(lst)):
    c = lst[_]
    if c == "0":
        ans += [str(cnt1 + 2)]
        cnt1 += 1
    else:
        ans += [str(roots[cnt2][0])]
        cnt2 += 1

payload = ' '.join(ans)
print(payload)

:::

:::success
flag{pr1mes_r_pr3tty_sp3c14lll}
:::

## Not_Baby_Fixed

:::spoiler **Source Code**

from Crypto.Util.number import *

with open('flag.txt','rb') as g:
    flag = g.read().strip()

with open('nums.txt','r') as f:
	s=f.read().strip().split()
	a=int(s[0])
	b=int(s[1])
	c=int(s[2])


e=65537
n=a**3+b**3-34*c**3
m=bytes_to_long(flag)
ct=pow(m,e,n)


print ('n:',n)
print ('e:',e)
print ('ct:',ct)

:::

It turns out the numbers $a,b,c$ satisfying $$ a = 15x^2, \quad b = 7y^2, \quad c = 3xy$$ where $$ \begin{align*} x & = 321329349024937022728435772726127082487 \\ y & = 302518462040600437690188095770599287567 \end{align*} $$

Then, we may factor $n$ by Sage $$ \begin{align*} n & = a^3+b^3-34c^3 \\ & = 3375x^6+343y^6-918x^3y^3 \\ & = (15x^2+3xy+7y^2)(225x^4-45x^3y-96x^2y^2-21xy^3+49y^4) \end{align*} $$

# Sage
P.<x,y> = PolynomialRing(ZZ)

f = 3375*x^6 - 918*x^3*y^3 + 343*y^6

f.factor()

:::spoiler **Script**

# Sage
x = 321329349024937022728435772726127082487
y = 302518462040600437690188095770599287567

a = 15*x^2 + 3*x*y + 7*y^2
b = 225*x^4 - 45*x^3*y - 96*x^2*y^2 - 21*x*y^3 + 49*y^4

phi = 1

factors, exponents = zip(*factor(a))

for f, e in zip(factors, exponents):
    phi *= f ** (e-1) * (f-1)

factors, exponents = zip(*factor(b))

for f, e in zip(factors, exponents):
    phi *= f ** (e-1) * (f-1)

e = 65537
ct = 1918452064660929090686220330495385310745803950329608928110672560978679963497394969369363585721389729566306519544561789659164639271919010791127784820214512488663422537225906608133719652453804000168907004058397487865279113133220466050285

pt = pow(ct, pow(e, -1, phi), a*b)

from Crypto.Util.number import long_to_bytes

flag = long_to_bytes(pt)
print(flag)

:::

:::success
flag{plz_n0_guess_sum_of_a_b_c_d1vides_n}
:::

## ILoveYou3000

:::spoiler **Source Code**

import random
from Crypto.Util.number import *

def newflag(oldflag):
	s=list(b"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPWRSTUVWXYYZ")
	for i in range(random.randint(1,10)):
		oldflag=long_to_bytes(random.choice(s))+oldflag
	for i in range(random.randint(1,10)):
		oldflag=oldflag+long_to_bytes(random.choice(s))
	return oldflag

flag = b"flag{testing_flag}"
flag=newflag(flag)

m=bytes_to_long(flag)

def cooooolerRandom(x,y):
	base=random.randint(2,5)
	e=base

	operation=random.choice([-1,1]) #subtraction or addition

	_range=random.randint(1,6) #rolling some dice
	change=sum([random.randint(-_range,_range) for i in range(random.randint(1,100))]) #chillllly am I right?
	e*=(x+operation*change)

	operation2=random.choice([-1,1]) #subtraction or addition

	_range=random.randint(1,6) #rolling some more dice
	change2=sum([random.randint(-_range,_range) for i in range(random.randint(1,100))]) #someone get me a blanket pleasee
	
	e*=(y+operation2*change2)
	return e+base,base

example_count=int(input("How many examples do you want?: "))

for i in range(example_count):
	p=getPrime(256)
	q=getPrime(256)
	n=p*q
	assert(m<n)
	e,b=cooooolerRandom(p,q)
	ct=pow(m,e,n)
	print("Ciphertext: ", ct)
	print("Modulus: ", n)
	print("Base: ", b)

:::

In one connection, the server generates $3000$ modulus $n_i=p_iq_i$ and encrypts the padding flag as follows $$ ct_{i} \equiv m^{b_i(p+r_{i_1})(q+r_{i_2})+b_i} \pmod{n_i} $$ It only gives us $ct, b$ and $n_i$. According to Euler, $$m^{(p-1)(q-1)} \equiv 1 \pmod{n_i} $$ We hope that $r_{i_1}, r_{i_2}$ are $-1$ and thus, $ct_{i} \equiv m^{b_{i}} \pmod{n_{i}}$.

In fact, the probability of $r_{i_1} = r_{i_2} = -1$ is big. We may run a simple simulation locally. One could, in average, find such a sample in $600$ samples.

import random

def test():

	operation=random.choice([-1,1]) #subtraction or addition

	_range=random.randint(1,6) #rolling some dice
	change=sum([random.randint(-_range,_range) for i in range(random.randint(1,100))]) #chillllly am I right?

	operation2=random.choice([-1,1]) #subtraction or addition

	_range=random.randint(1,6) #rolling some more dice
	change2=sum([random.randint(-_range,_range) for i in range(random.randint(1,100))]) #someone get me a blanket pleasee

	if operation * change == -1 and operation2 * change2 == -1:
		return True
	else:
		return False

cnt = 0

for _ in range(300000):
	if test():
		cnt += 1
		print(_)

print(cnt)

Since $m$ may be much larger than $\sqrt[b_{i}]{n_{i}}$, we cannot simply take ${i}$-th root of $ct_{i}$. But we can apply Hastad broadcast attack!

In average, we get $750$ samples with $b_{i} = 2$. We can expect to find $2$ nice samples with $b_{i} = 2$.

:::spoiler **Script**

from pwn import *
from Crypto.Util.number import long_to_bytes
from decimal import *

getcontext().prec = 400

def conn(local):

	if local == 1:
		r = remote("143.198.127.103", 42010)
	else:
		r = process("source.py")
	
	return r

def get_sample(r):

	r.recvuntil("Ciphertext: ")
	ct = int(r.recvline().strip())

	r.recvuntil("Modulus: ")
	n = int(r.recvline().strip())

	r.recvuntil("Base: ")
	b = int(r.recvline().strip())

	return ct, n, b

def lucky(r):

	samples = 3000

	r.recvuntil("How many examples do you want?: ")
	r.sendline(str(samples))

	ct2, mod = [], []

	for _ in range(samples):
		ct, n, b = get_sample(r)

		if b == 2:
			ct2 += [ct]
			mod += [n]
	
	for i in range(len(ct2)):
		for j in range(len(ct2)):
			if j == i:
				continue
			
			CRT = (ct2[i] * mod[j] * pow(mod[j], -1, mod[i]) + \
				ct2[j] * mod[i] * pow(mod[i], -1, mod[j])) % (mod[i] * mod[j])

			m = int(Decimal(CRT) ** (Decimal(1) / Decimal(2)))
		
			flag = long_to_bytes(m)
			if b"flag" in flag:
				return flag

	return None

while True:

	r = conn(1)
	res = lucky(r, ct2, mod)
	r.close()
	
	if res:
		print(res)
		break

:::

## MRSA2

:::spoiler **Source Code**

from Crypto.Util.number import *


with open('flag.txt','rb') as f:
    flag = f.read().strip()

e=65537
p=getPrime(256)
q=getPrime(256)
n=p*q
phi=(p-1)*(q-1)
m=bytes_to_long(flag)
d=pow(e,-1,phi)
ct=pow(m,e,n)

print ('n:',n)
print ('e:',e)
print ('ct:',ct)

def enc(msg):
    print (d%msg)
try:
    br="#"
    print (br*70)
    print ("Now here's the More part!!!")
    print ("Enter some number, and I will encrypt it for you")
    print ("But you gotta follow the condition that your number gotta be less than 2^140 (and like legitamite)")
    print (br*70)
    s=int(input("Enter: ").strip())
    assert(s>0 and s<2**140)
    enc(s)
except:
    print ("Bruh why you be like this")
    exit()

:::

We can ask for the residue of $d$ divided by our input $k$. A straightforward solution is:

1. Send $k = 2^{138}$ to the server and get the last $138$-bits of $d$, say $d_{0}$
2. Notice that $$ed = 1 + c\phi{(n)} \quad \text{where} \quad c < e$$ It follows that $$ed_0 \equiv 1 + c(n-p-\frac{n}{p}+1) \pmod{2^{138}}$$ So we can get all possibilities of least $138$-bits of $p$
2. Perform again partial $p$ exposure attack (Modify [script](https://github.com/mimoo/RSA-and-LLL-attacks) from mimoo)

:::spoiler **Script**

# Sage
from __future__ import print_function
import time

# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print(a)

def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
    
    dd = pol.degree()
    nn = dd * mm + tt

    # change ring of pol and x
    polZ = pol.change_ring(ZZ)
    x = polZ.parent().gen()

    # compute polynomials
    gg = []
    for ii in range(mm):
        for jj in range(dd):
            gg.append((x * XX)**jj * modulus**(mm - ii) * polZ(x * XX)**ii)
    for ii in range(tt):
        gg.append((x * XX)**ii * polZ(x * XX)**mm)
    
    # construct lattice B
    BB = Matrix(ZZ, nn)

    for ii in range(nn):
        for jj in range(ii+1):
            BB[ii, jj] = gg[ii][jj]

    # LLL
    BB = BB.LLL()

    # transform shortest vector in polynomial    
    new_pol = 0
    for ii in range(nn):
        new_pol += x**ii * BB[0, ii] / XX**ii

    # factor polynomial
    potential_roots = new_pol.roots()
    # print("potential roots:", potential_roots)

    # test roots
    roots = []
    for root in potential_roots:
        if root[0].is_integer():
            roots.append(root[0])

    return roots

import multiprocessing

n = 6538906996876211622159813771898634542490427964432296104602802174964246398504084361075456100475447139001712152771117230602533691744124398724816978553787959
kbits = 138
d0 = 215828658855119428266805137903011920281601
e = 257
ct = 3561636066096712802219233065256334728039796982298930748171850418458732632647463402398904825272481505558815292669878999929431185631673938890831438880807053

def partial_p(p0):

    F.<x> = PolynomialRing(Zmod(n), implementation='NTL'); 
    pol = 2^kbits * x + p0
    pol = pol.monic()
    dd = pol.degree()

    # PLAY WITH THOSE:
    beta = 0.5                             # we should have q >= N^beta
    epsilon = beta^2 - 119 / 512                   # <= beta/7
    mm = ceil(beta**2 / (dd * epsilon))    # optimized
    tt = floor(dd * mm * ((1/beta) - 1))   # optimized
    XX = ceil(n**((beta**2/dd) - epsilon)) # we should have |diff| < X

    # Coppersmith
    start_time = time.time()
    roots = coppersmith_howgrave_univariate(pol, n, beta, mm, tt, XX)
   
    for r in roots:
        p = 2^kbits * r + p0
        if n % p == 0 and p < n:
            print(p)
            return p
     
    return None

def solve(ks):

    X = var('X')
    
    for k in ks:
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            
            p = partial_p(p0)
            if p:
                return p
        
        print(k)
    return None
    
if __name__ == '__main__':
    solve(range(1, e))

:::

:::success
flag{0ops_m4yb3_4_b1t_t000o000oo00o0_much_rsa}
:::