SpaceHeroesCTF NSSCTF MidnightSunCTF UMassCTF2022

2022-04-04

4月初有很多比赛，每个比赛都做了一些题，难题大多是hash师傅教的。

SpaceHeroesCTF

Easy Crypto Challenge

y^2 = x^3 + ax + b
a = 3820149076078175358
b = 1296618846080155687
modulus = 11648516937377897327
G = (4612592634107804164, 6359529245154327104)
PubKey = (9140537108692473465, 10130615023776320406)
k*G = (7657281011886994152, 10408646581210897023)
C = (5414448462522866853, 5822639685215517063)
What's the message?

用hellman算法可以解出私钥na，明文为C - na*KG：

M = 11648516937377897327
A = 3820149076078175358
B = 1296618846080155687
P = (4612592634107804164, 6359529245154327104)
Q = (9140537108692473465, 10130615023776320406)
C = (5414448462522866853, 5822639685215517063)
C1 = (7657281011886994152, 10408646581210897023)
F = FiniteField(M)
E = EllipticCurve(F,[A,B])
P = E.point(P)
Q = E.point(Q)
C = E.point(C)
C1 = E.point(C1)
P_order = P.order()
print(P_order) #计算生成元的阶
print(factor(P_order))
dlog = discrete_log(Q,P,operation="+")
print(dlog) #这是私钥na
m = C - dlog * C1
print(m)

NSSCTF Round#1 Basic

number_by_number

import hashlib
from Crypto.Util.number import *
from gmpy2 import *
FLAG = b'******************'
assert FLAG.startswith(b'NSSCTF{') and FLAG.endswith(b'}')
FLAG = FLAG[7:-1]

def sign(msg, pub, pri, k):
    (p,q,g,y) = pub
    x = pri
    r = int(pow(g, k, p) % q)
    h = int(hashlib.sha256(msg).digest().hex(),16)
    s = int((h + x * r) * invert(k, q) % q)
    return (r, s)

p = 12521300600879647215212622604478307167614802603722694432672492518732844280050451647647783544918670551333939947202324314036106883627652934658092246151569719841172139651756731975948641752941369320985906043813128667949407263418091261521078015038472125264708315959943830171678415621896727622381651264882655845219115471323352719455064712014904581019529062436850895982568432772820884304927292484611574315452532539622439874476205201585972439739033662281856954069390915294301650596122027017512657387126870291348326594014789938826560641601265413964203409968207292456857314148848395645091850604205535043035332961436498283695843
q = 89333150710898097819726085329049525002843220030438497258487456281988064920981
g = 4659169190462665152432024005060362819268084070474399613244522271693166269703240438309526888954293382169994621221386886590606442329876391429681914154130453072540079426475110538234340272617964838185872575922598867083747162403217264242469640383596415974818773608247780785279490355462362699968367544837511541267300331418420849521244364899679912282991493675152166261501255315036943693486335864565853496499243373834189894710718862409646613179068080762011713847012853815796678705445232715083564615906424779193638984542271665075749327914765645357163924702265124479067028868769369414557728443665123548337757950887923116453268
x = bytes_to_long(FLAG)
y = powmod(g, x, p)

pub = (p,q,g,y)
pri = x

nonce = getPrime(64)
print('y =', y)
print(sign(b'nssctfround#1', pub, pri, nonce))
print(sign(b'nssctfround#1', pub, pri, 12345*nonce + 67890))

'''
y = 516079379252376231001717898324355848864109868582016554029703521946402522000955354396295307046881971504216991061930299508521161039333927590076006514531946316725453062373440451679354041777376121961468715242703413529070177041819221792817124111175287475946526246377103779752133378942603534385789689950337366490082828044596711426514502752548887337695502949798115745655734033592905036846835127551577851715558217775334831352232997052342694255476534837857477388530834954919414905007702912216496977764789386913244009912368937860550222726279524193115767983754873150853915852619223039800432272818237552774389220137762595332280
(81900716895065212453759953296615257914462909922962929287345063257120550453427, 45144894416226080526306932143570511284754744855790908537643986192724824691890)
(60471460394555700734359895323450929800168788093422384886037011624642263106556, 74754852228035293908666429128869604520827363733944834534730568060790683199921)
'''

分析签名参数，有：

$nounce = h(m)s1^-1 + rxs1^-1 \mod q$ $a*nounce+b =h(m)s^-1+r2xs2^-1 \mod q$

高斯消元消去nounce以后求逆解出x（flag）：

import hashlib
from Crypto.Util.number import *
from gmpy2 import *

msg = b'nssctfround#1'
h = int(hashlib.sha256(msg).digest().hex(),16)

p = 12521300600879647215212622604478307167614802603722694432672492518732844280050451647647783544918670551333939947202324314036106883627652934658092246151569719841172139651756731975948641752941369320985906043813128667949407263418091261521078015038472125264708315959943830171678415621896727622381651264882655845219115471323352719455064712014904581019529062436850895982568432772820884304927292484611574315452532539622439874476205201585972439739033662281856954069390915294301650596122027017512657387126870291348326594014789938826560641601265413964203409968207292456857314148848395645091850604205535043035332961436498283695843
q = 89333150710898097819726085329049525002843220030438497258487456281988064920981
g = 4659169190462665152432024005060362819268084070474399613244522271693166269703240438309526888954293382169994621221386886590606442329876391429681914154130453072540079426475110538234340272617964838185872575922598867083747162403217264242469640383596415974818773608247780785279490355462362699968367544837511541267300331418420849521244364899679912282991493675152166261501255315036943693486335864565853496499243373834189894710718862409646613179068080762011713847012853815796678705445232715083564615906424779193638984542271665075749327914765645357163924702265124479067028868769369414557728443665123548337757950887923116453268

sign1 = (81900716895065212453759953296615257914462909922962929287345063257120550453427, 45144894416226080526306932143570511284754744855790908537643986192724824691890)
sign2 = (60471460394555700734359895323450929800168788093422384886037011624642263106556, 74754852228035293908666429128869604520827363733944834534730568060790683199921)
r1 = sign1[0]
r2 = sign2[0]
s1 = sign1[1]
s2 = sign2[1]
s1_ = invert(s1,q)
s2_ = invert(s2,q)
a = 12345
b = 67890

bb = (-a * h * s1_ - b + h * s2_)%q
kk = a * r1 * s1_ - r2 * s2_
flag = (invert(kk,q) * bb)%q
print(long_to_bytes(flag))
# b'43fe-bd64-68b4bc1c4845'

MidnightSunCTF

pelles_rotor_supported_arithmetic

#!/usr/bin/python3
from sys import stdin, stdout, exit
from flag import FLAG
from secrets import randbelow
from gmpy import next_prime

p = int(next_prime(randbelow(2**512)))
q = int(next_prime(randbelow(2**512)))
n = p * q
e = 65537

phi = (p - 1)*(q - 1)
d = int(pow(e, -1, phi))
d_len = len(str(d))

print("encrypted flag", pow(FLAG, 3331646268016923629, n))
stdout.flush()

ctr = 0
def oracle(c, i):
    global ctr
    if ctr > 10 * d_len // 9:
        print("Come on, that was already way too generous...")
        return
    ctr += 1
    rotor = lambda d, i: int(str(d)[i % d_len:] + str(d)[:i % d_len]) #对d循环移位，利用这个关键求n和恢复d
    return int(pow(c, rotor(d, i), n))

banner = lambda: stdout.write("""
Pelle's Rotor Supported Arithmetic Oracle
1) Query the oracle with a ciphertext and rotation value.
2) Exit.
""")

banner()
stdout.flush()

choices = {
    1: oracle,
    2: exit
}

while True:
    try:
        choice = stdin.readline()
        print("c:")
        stdout.flush()
        cipher = stdin.readline()
        print("rot:")
        stdout.flush()
        rotation = stdin.readline()
        print(choices.get(int(choice))(int(cipher), int(rotation)))
        stdout.flush()
    except Exception as e:
        stdout.write("%s\n" % e)
        stdout.flush()
        exit()

exp：

from pwn import *
import gmpy2
from tqdm import tqdm

p = remote('pelle-01.hfsc.tf', 4591)

p.recvuntil(b'encrypted flag ')

enc = int(p.recvline()[:-1])

p.recvuntil(b'Exit.\n')
p.sendline(b'1')
p.recvuntil(b'c:\n')
p.sendline(b'-1')
p.recvuntil(b'rot:\n')
p.sendline(b'0')
n = int(p.recvline()[:-1]) + 1 #-1 mod n就是n-1

t = []
for i in tqdm(range(len(str(n)) + 1)):#因为e比较小，所以猜测d和n十进制位数一样
    p.sendline(b'1')
    p.recvuntil(b'c:\n')
    p.sendline(b'2')
    p.recvuntil(b'rot:\n')
    p.sendline(str(i).encode())
    temp = int(p.recvline()[:-1])
    t.append(temp)

d = ''
for i in range(len(str(n))):
    t1 = t[i]
    t2 = t[i + 1]
    t1 = pow(t1, 10, n)
    s = t1 * gmpy2.invert(t2, n) % n
    for j in range(10):
        if pow(2, j * (10 ** len(str(n)) - 1), n) == s:
            d += str(j)

print(d)

e1 = 65537
e2 = 3331646268016923629
d = int(d, 10)
kphi = e1 * d - 1
dd = gmpy2.invert(e2, kphi)
m = pow(enc, dd, n)
print(m)

from Crypto.Util.number import *
print(long_to_bytes(m))

UMassCTF

Web1

考察jwt，因为web学的很少所以第一次见到jwt就顺便学习了一波。

关于jwt：https://blog.csdn.net/weixin_45070175/article/details/118559272

首先题目给了签名接口的git项目地址，去访问发现隐藏了代码，去看提交的history找到所有代码；分析代码找到关键点：

即post的数据会通过该接口签名生成完整的jwt。

第二步，请求get_flag，bp抓包看jwt，base64解码发现user字段是anonymous，要获取flag需要把这个改为admin，但这样之后签名值sign发生改变，所以需要把改为admin之后的header和data base64加密以后和在一起并去掉原来的签名post到服务器让服务器再签一次名（重放），然后拿到之后再把token修改一下提交给服务器获得flag。

quickmath

交互题，计算1000次服务器发送的加减乘除，pwntool直接自动化处理：

from pwn import *
# 做1000次加减乘除运算
def quickmath(a,n1,n2):
    if a == '+' or a == "+ ":
        return n1+n2
    elif a == "-" or a == "- ":
        return n1-n2
    elif a == "*" or a == "* ":
        return n1*n2
    else:
        return n1//n2


oi=remote('34.148.103.218',1228)
oi.recvuntil(b"!")
r1 = oi.recv(15)[3:]
r1 = str(r1)
print(r1)

start = r1.find("'")
space = r1.find(" ")
n1 = int(r1[start+1:space])
a = r1[space+1:space+3]
n2 = int(r1[space+3:].replace("n","").replace("\\",'').replace("'",'').strip())
print(a,n1,n2)
an1 = quickmath(a,n1,n2)
#有bug，第一次接收的不能是除法
print(an1)
oi.sendline(str(an1).encode())
for i in range(999):
    print(i)
    print(oi.recvuntil(b"!"))
    r2 = oi.recv(15)[1:]
    r2 = str(r2)
    print(r2)
    start1 = r2.find("'")
    space1 = r2.find(" ")
    n3 = int(r2[start1+1:space1])
    a_ = r2[space1+1:space1+3]
    n4 = int(r2[space1+3:].replace("n","").replace("\\",'').replace("'",'').strip())
    an2 = quickmath(a_,n3,n4)
    print(an2)
    oi.sendline(str(an2).encode())
flag = str(oi.recv(1000))
print(flag)