Alpacahack Round 9 (Crypto) Writeup

,

Before all

Rank. 17
本來蠻期待這場，結果開打那天早上中午都在外面 + 打隔壁的 x3CTF 就沒好好打到，只摸了一題 qq
題目都好好玩，剩下兩題之後補 LOL，先過年

addprimes (13 solves)

server.sage 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import os
import signal
from sage.misc.banner import require_version
from Crypto.Util.number import getPrime, bytes_to_long

assert require_version(10), "This challenge requires SageMath version 10 or above"

signal.alarm(30)
FLAG = os.environ.get("FLAG", "Alpaca{*** FAKEFLAG ***}").encode()
assert FLAG.startswith(b"Alpaca{")

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 37

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

c = int(input("ciphertext: "))
assert 1 < c < n-1
pari.addprimes(p)
m = mod(c, n).nth_root(e)
print("plaintext:", m)

padded_flag = FLAG + os.urandom(127-len(FLAG))
print("encrypted flag:", pow(bytes_to_long(padded_flag), e, n))

一開始讓你輸入一個數字，找出他模n的e次方根吐回來給你，最後把加密後的 FLAG 給你。
值得注意的是這邊e特別小，它也沒檢查e跟$\varphi(p)$是不是互質，所以假設今天存在$x’^{37}\equiv input(mod\space n)$，而我們輸入時預想的值是x，並且 $gcd(e, p-1)=e$ 且 $gcd(e, q-1)=1$，那$gcd(x’-x, n)=p$就完成分解了，最後再用一次 nth_root 找根即可從其中一個還原flag
拿預設解 = 2 去爆的腳本：
brute.py 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
import math
from pwn import *

cnt=0

def hack():
    r=remote('34.170.146.252', 20209)
    data=r.recvline()
    r.recvuntil(b'ciphertext: ')
    r.sendline(b'137438953472') # 2**37
    cur=r.recvline()
    if cur!=b'plaintext: 2\n':
        #cnt+=1
        data+=cur
        data+=r.recv()
        print(data.decode())

while True:
    hack()

拿到解後：
solve.sage 

1
2
3
4
5
6
7
8
9
10
11
n=89218236468631916905164256824386437079014670813801107630734965136513026271851617158743215697397914500567099213886755035541869829452397010943597561887116786986639991581739611724846954353383645049572415301492611461971527044247851368316458384986569403845907648450121679868315385258283742818549140003425612379649
k=49505840533858192743060505510175263560448576040232584260767322896075426850358280259175614846974359386358663872904290926077778624258545580604549455513509065367298790604406300900168958377558892059156763085597455025162478526410187925853837344287020912049086445582464055894804306539643239049212376380801521238562
enc=78228026479944672264668907479870199428408390504364264011036277978839767881346677099362898917246714384321748883117807890002643802823189537295977145761877197939262555715469216087270870390510558796690055094325761693888407193009853092108944586063971421027700175663101087149979384905328813648460272207487982473406
p=gcd(k-2, n)
pari.addprimes(p)
a=mod(enc, n).nth_root(37, all=True)

for i in a:
    cur=long_to_bytes(i)
    if b'Alpaca{' in cur:
        print(cur)

RSAMPC (賽後解)

chall.py 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import os
from Crypto.Util.number import getRandomRange, getPrime, bytes_to_long

FLAG = os.environ.get("FLAG", "fakeflag").encode()

def additive_share(a):
    t0, t1 = getRandomRange(-2**512, 2**512), getRandomRange(-2**512, 2**512)
    t2 = a-t0-t1
    return t0, t1, t2

def replicated_share(a):
    t = additive_share(a)
    return [(t[i], t[(i+1)%3]) for i in range(3)]

def multiply_shares(sa, sb):
    def mul(t, u):
        return t[0]*u[0]+t[0]*u[1]+t[1]*u[0]
    r = additive_share(0)
    z = [mul(sa[i], sb[i])+r[i] for i in range(3)]
    w = [(z[i], z[(i+1)%3]) for i in range(3)]
    return w

def reconstruct(s):
    return s[0][0] + s[0][1] + s[1][1]

p = getPrime(512)
q = getPrime(512)

sp = replicated_share(p)
sq = replicated_share(q)
print("your share of p:", sp[0])
print("your share of q:", sq[0])

spq = multiply_shares(sp, sq)
print("your share of pq:", spq[0])

n = reconstruct(spq)
assert n == p*q
print("n:", n)

e = 0x10001
c = pow(bytes_to_long(FLAG + os.urandom(127-len(FLAG))), e, n)
print("e:", e)
print("c:", c)

一些有點複雜的算式， TL;DR 一下，總之推到最後會變成一個
$ap+bq+c=n$ 的方程，（a, b, n已知），注意到兩邊同乘$p$並把$cp$忽略(跟其他項次比起來它很小)，求解就可以拿到一個相近的$p’$，最後爆一下就好 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import *
tp=[-384164070196680113629973964276599320736606300184523772854135294036334447818682200607218877531386512793858125339877828582394197679795576991953411880314517, 178776721087372919385257940734429604253240493277094581482580652949038337321961407291832241379559936948198042043881180916670462219794291885959730598632423]
tq=[-10504102453855211730773548202462643334445368588122773952797120588540073173181223269420294976331168878842123082669069593895980908615299058089156709125348617, 3324659724832936014805633502878093035237335054058544453532695059432217891926271390882999445452501190449380595220556388508799059755133895886341486877191502]
spq=[880194945859095512548778390949753106113259354062743403885130575509194611686622871911550689148439940097472063798899034574466553154127726867674397008987477001207806315461004286936941315001029394217039765579529660629019466179402060549350587729722354909331590051509695082365313846996923469825646557408789955494, 40388351148875096689764230410867470980240794826105168292967479483809364773078955483003274901375600951153408618729650715655666480989756454152565386666760509805904377793675351489295406907138019316039841793386393194481700178651652081449097569147179108704523020190287922457859082133424057955783092523665228634328]
n=122269467950798077326822634108968850809243750508493781647505745002863843379348700424238562022365315227978807541070854658246091147872559714237246479088170538196473585543281713624525798244748333546435600544573727499127916535316599284592352755786055339638261774730837681190375466416924715653324305527245715836447
e=65537
c=100976267335628681910815317357700490412039872278731196009735781349258998302355802361980783540754919888894607253589239383351290237447746132667260747986281172840910605287343986031579879857474734142154881821962810929745626899955618676413832332521656625264015203959361696843594006345498340544121922011105950850715

tz0=spq[0]-tp[0]*tq[0]-tp[0]*tq[1]-tp[1]*tq[0]
spq.append(n-spq[0]-spq[1])

sum_tz1=spq[1]+tp[1]*tq[1]+tp[0]*tq[1]+tp[1]*tq[0]
P.<x>=PolynomialRing(RealField(10000))
f=tq[1]*(x**2)+tp[1]*n-sum_tz1*x
f=f.monic()
trial=f.roots()
for i in range(len(trial)):
	cur=int(trial[i][0])
	for j in range(cur-1000000, cur+1000000):
		if n%j==0:
			p=j
			break
q=n//p
d=inverse(e, (p-1)*(q-1))
print(long_to_bytes(int(pow(c, d, n))))