owned this note
owned this note
Published
Linked with GitHub
# PBjar CTF 2021
Team. OAO
Point. 3094 (9/9 Crypto)
Rank. 95
## Convert
enc = 666c61677b6469735f69735f615f666c346767675f68317d
```python=
import binascii
from output import *
flag = binascii.unhexlify(enc)
print(flag)
```
:::success
flag{dis_is_a_fl4ggg_h1}
:::
## ReallynotSecureAlgorithm
:::spoiler **Source Code**
```python=
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**
```python=
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**
```python=
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**
```python=
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**
```python=
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**
```python=
# 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**
```python=
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**
```python=
# 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**
```python=
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**
```python=
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**
```python=
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*} $$
```python=
# Sage
P.<x,y> = PolynomialRing(ZZ)
f = 3375*x^6 - 918*x^3*y^3 + 343*y^6
f.factor()
```
:::spoiler **Script**
```python=
# 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**
```python=
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.
```python=
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**
```python=
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**
```python=
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**
```python=
# 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}
:::
Sign in with Wallet
