前言

GACTF算是新的XCTF分站赛，受北极星师傅邀请抽空打了这场比赛。最后团队总排名19名。很可惜这次比赛队友因故都没怎么认真做，不然是很有可能打进前十名的。星盟团队确实没有顶尖的密码手，因此这次比赛的crypto题目是相对简单的，这次本菜鸡也算是K了。

Writeup

da Vinci after rsa

题目首先给了一个貌似RSA算法的公钥和密文。N在factordb.com上可以完全分解。当我们兴冲冲地去求解d时，发现求不出e的逆元。那么这样也就是老的开根+CRT套路了，比较好的算法是A-M-M算法。但是在开源数学软件Sagemath中，已经实现了模域的开根算法，所以我们直接调用Sage中的roots()方法就行。解出以后，解一个简单的移位密码达芬奇密码就获得了flag，达芬奇密码简单地说就是将斐波那契序列作移位而形成。

Exp：

p = 9749
q = 11237753507624591
r = 9127680453986244150392840833873266696712898279308227257525736684312919750469261
n = 999999999999999999999999999999999999999999999999989999999999999999999999999999999999999999999999999
assert(p*q*r==n)
F.<x> = PolynomialRing(Zmod(p))
F1.<y> = PolynomialRing(Zmod(q))
F2.<z> = PolynomialRing(Zmod(r))
equation = "x^5-421363015174981309103786520626603807427915973516427836319727073378790974986429057810159449046489151"
equationy = "y^5-421363015174981309103786520626603807427915973516427836319727073378790974986429057810159449046489151"
equationz = "z^5-421363015174981309103786520626603807427915973516427836319727073378790974986429057810159449046489151"
rootp = F(equation).roots()
rootq = F1(equationy).roots()
rootr = F2(equationz).roots()
print(rootp[0][0])
print(rootq)
print(rootr)

rootq=[(9898464751509789, 1),
 (8415400986072042, 1),
 (6537111956662153, 1),
 (6139772527803903, 1),
 (2722510300825886, 1)]
rootp =7361
rootr=[(8499052407588078002885931765166137308397074232361087682974448633946350539292222,
  1),
 (5570877862584063114417410584640901580756179707042774516590562822938385811269597,
  1),
 (2816114411493328258682873357893989007684496552202823306045771363205185148674391,
  1),
 (1369135259891793292334345751773139388112378132927363770631732500241630990458667,
  1),
 (180966415225632465120208272366108475667934082405238808958048294287011243645,
  1)]
minn = n
for i in rootq:
    for j in rootr:
        if crt([rootp,i[0],j[0]],[p,q,r])< minn:
            minn = crt([rootp,i[0],j[0]],[p,q,r])
from Crypto.Util.number import *
print(long_to_bytes(minn))

elgaml_rsa

这个题一开始白给了secret，后来删了让你自己求……不过尽管让你自己求也是CTF-wiki上的原题……这个原题我暂时先不写了，有空以后再补上。这个RSA中e不是素数，所以还是得用那套开根算法。这次使用了nth_root()方法，功能比roots()更专精一些，所以速度更快。

Exp：

from Crypto.Util.number import *
c=255310806360822158306697936064463902328816816156848194779397173946813224291656351345682266227949792774097276485816149202739762582969208376195999403112665514848825884325279574067341653685838880693150001066940379902609411551128810484902428845412055387955258568610350610226605230048821754213270699317153844590496606931431733319116866235538921198147193538906156906954406577796507390570080177313707462469835954564824944706687157852157673146976402325057144745208116022973614795377968986322754779469798013426261911408914756488145211933799442123449261969392169406969410065018032795960230701484816708147958190769470879211953704222809883281592308316942052671516609231501663363123562942
e=4758
n = 232087313537^4*653551912583^15*42044128297^6*802576647765917^7*104280142799213^6*22138874396255995367093123412542835139147*13762465758315682081101120047311808273580676420732931921786988371226809960736779727880583811067*6516832825116557981350931*28079229001363^3
flag = long_to_bytes(min(mod(c,n).nth_root(e,all=True)))
print(flag)

what_r_the_noise

白给题，请求五百次数据然后求平均值就可以了。
Exp：

from pwn import *
rs = remote("124.71.145.165", 9999)

#context.log_level = 'debug'
database = []
T = 500
final = []
for i in range(47):
    final.append(0)
for i in range(T):
    log.success(str(i))
    #rs.recvuntil(":")
    rs.sendline("2")
    ans = rs.recvline().strip()[1:-1].split(',')
    database.append(ans)
log.success(database)
for i in database:
    try:
        for j in range(47):
            final[j] += float(i[j])
    except:
        pass

for j in range(47):
    final[j] = chr(int(round(final[j]/T)+1))
flag = "".join(final)
#log.success(final)
log.success(flag)

ezAES

又是个白给题。题目给了key的前14位，爆破2位，就能获得key，复杂度仅为O(128*128)。题目给了最后一个分组的完整密文，爆破成功后，又能根据最后一个分组的密文，根据CBC模式的特点依次推算出之前所有分块的密文。这样解出所有的密文为a884ed307a7af7b003e81c46b928b1a9233f21c19790307c1f0b551b296401114765763869a74c4d22538ad4489c6e094eea629633f4d9589791ac584817cdb1c70b38bbd268a32c412a3e7474e584cd72481dab9dd83141706925d92bdd39e4，然后根据第一个分组求解IV。

Exp：

from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor
import binascii, sys
import hashlib
import string
KEYSIZE=16
def pad(message):
    p = (KEYSIZE - len(message) % KEYSIZE) * chr(KEYSIZE - len(message) % KEYSIZE)
    return message + p
message = 'AES CBC Mode is commonly used in data encryption. What do you know about it?'
key = 'T0EyZaLRzQmNe2pd'
cipher = 'a884ed307a7af7b003e81c46b928b1a9'.decode('hex')
aes = AES.new(key, AES.MODE_ECB)
middle = aes.decrypt(cipher)
pl = pad(message)[:16]
print(pl)
iv = strxor(pl, middle)
print(iv.encode('hex'))
print(iv)

square

这题考点是佩尔方程。题目给了一个奇怪的等式，用平方和公式化简后得到2y2+3y+1=6x22y^2+3y+1 = 6x^2。经过一通神奇的配方变换，等式化为(4y+3)2−48x2=1(4y+3)^2 - 48x^2 = 1，即标准的pell方程形式。然后换元使用pell方程的递推求解式子求解，注意最后换元回最先的xx和yy时要注意y≡3(mod4)y \equiv 3 \pmod 4。

佩尔方程递推式：

xk=xk−1x1+nyk−1y1x_k = x_{k-1}x_1 + ny_{k-1}y_1

yk=xk−1y1+yk−1x1y_k = x_{k-1}y_1 + y_{k-1}x_1

Exp：

from pwnlib.util.iters import mbruteforce
from pwn import *
import string
from hashlib import *
solvex = [7]
solvey = [1]
n = 48
def proof_of_work(p):
    p.recvuntil("md5(str + ")
    suffix = p.recv(4).decode("utf8")
    p.recvuntil("== ")
    cipher = p.recvline().strip().decode("utf8")
    assert(len(cipher)==5)
    proof = mbruteforce(lambda x: md5((x + suffix).encode()).hexdigest()[0:5] ==  cipher, string.ascii_letters + string.digits, length=5, method='fixed')
    p.sendlineafter("Give me xxxxx:", proof)

def valid(n):
    return n % 4==3

for i in xrange(1,200):
    xk=solvex[-1]*solvex[0]+n*solvey[-1]*solvey[0]
    yk=solvex[-1]*solvey[0]+solvey[-1]*solvex[0]
    solvex.append(xk)
    solvey.append(yk)
ansx = []
ansy = []
for i in range(len(solvex)):
    if (valid(solvex[i])):
        ansx.append(solvey[i])
        ansy.append((solvex[i]-3)//4)
for i in range(len(ansx)):
    assert(6*ansx[i]**2==2*ansy[i]**2+3*ansy[i]+1)
print(len(ansx))
rs = remote("124.71.158.89",8888)
proof_of_work(rs)
for i in range(100):
    rs.recvuntil('[>] x:')
    rs.sendline(str(ansx[i]))
    rs.recvuntil('[>] y:')
    rs.sendline(str(ansy[i]))
rs.interactive()

babycrypto

一个原题，爱德华兹曲线。我个人的理解以后有空再补。