国赛，算是我第一个打的久负盛名的比赛，但他用实际向我证明了有名气不等于题出的好的道理（流汗黄豆），一共3道题，比赛时战绩为1道，但实际上除了混进来的RE之外的题都挺常见，算是开阔眼见了。
ECDSA,挺标准的一道题
题干：
#!/usr/bin/env python3
from ecdsa import SigningKey, NIST521p
from hashlib import sha512
from Crypto.Util.number import long_to_bytes
import random
import binascii
import sys
digest_int = int.from_bytes(sha512(b"Welcome to this challenge!").digest(), "big")
curve_order = NIST521p.order
priv_int = digest_int % curve_order
priv_bytes = long_to_bytes(priv_int, 66)
sk = SigningKey.from_string(priv_bytes, curve=NIST521p)
vk = sk.verifying_key
f_pub = open("public.pem", "wb")
f_pub.write(vk.to_pem())
f_pub.close()
def nonce(i):
seed = sha512(b"bias" + bytes([i])).digest()
k = int.from_bytes(seed, "big")
return k
msgs = [b"message-" + bytes([i]) for i in range(60)]
sigs = []
for i, msg in enumerate(msgs):
k = nonce(i)
sig = sk.sign(msg, k=k)
sigs.append((binascii.hexlify(msg).decode(), binascii.hexlify(sig).decode()))
f_sig = open("signatures.txt", "w")
for m, s in sigs:
f_sig.write("%s:%s\n" % (m, s))
f_sig.close()-----BEGIN PUBLIC KEY-----
MIGbMBAGByqGSM49AgEGBSuBBAAjA4GGAAQBCmmiMNZTXuR44GdzljZErCUcNgf5
jpCcPTL31HYx8EUdoFh4JC+4kUBFxTn7VzuHxFUBLYmNGO1Jow6QqpDfLb0B+2d4
vs4wjNqvFZ1ET79VDt1AcgySGWX8KlAgizrmIGwXJmp1UfewMhv2f5EDbu3vVU9m
f1WeP2aRaDHmG4ryVkg=
-----END PUBLIC KEY-----
#省去数据pemWP:
1.已知d邪道：
from hashlib import sha512,md5
digest_int = int.from_bytes(sha512(b"Welcome to this challenge!").digest(), "big")
flag=md5(str(digest_int).encode()).hexdigest()
print(flag)2.常规思路：
#思路很简单，题上直接有k，是最简单的k已知
from hashlib import sha512,md5,sha1
from ecdsa import NIST521p,VerifyingKey
from Crypto.Util.number import *
import gmpy2
n=NIST521p.order#获取阶
with open("pub.pem","rb")as f:
vk=VerifyingKey.from_pem(f.read())#读取公钥。这一步实际上没必要
with open("signatures.txt","r")as f:
line=f.readline().strip()#读取第0条签名,readline只读第一行
m_hex,sig_hex=line.split(":")#按照：分成2段
msg=bytes.fromhex(m_hex)#这一步只是从hex()转化成了bytes
sig=bytes.fromhex(sig_hex)
r = int.from_bytes(sig[:66], "big")#这里用int转化成数字
s = int.from_bytes(sig[66:], "big")#读取签名，这里我才知道签名是写在一起没有间隔的
k = int.from_bytes(sha512(b"bias" + bytes([0])).digest(), "big") % n
e = int.from_bytes(sha1(msg).digest(), "big")
d = ((s * k - e) * gmpy2.invert(r, n)) % n#公式
flag = md5((str(d)).encode()).hexdigest()
print(flag)
属于常见的已知k的思路
Pollard P-1算法
题干：暗示得很明显
from Crypto.Util.number import *
from tqdm import tqdm
import os
flag=open("./flag.txt","rb").read()
flag=bytes_to_long(flag+os.urandom(2048//8-len(flag)))
e=65537
def get_smooth_prime(bits, smoothness, max_prime=None):
assert bits - 2 * smoothness > 0
p = 2
if max_prime!=None:
assert max_prime>smoothness
p*=max_prime
while p.bit_length() < bits - 2 * smoothness:
factor = getPrime(smoothness)
p *= factor
bitcnt = (bits - p.bit_length()) // 2
while True:
prime1 = getPrime(bitcnt)
prime2 = getPrime(bitcnt)
tmpp = p * prime1 * prime2
if tmpp.bit_length() < bits:
bitcnt += 1
continue
if tmpp.bit_length() > bits:
bitcnt -= 1
continue
if isPrime(tmpp + 1):
p = tmpp + 1
break
return p
p1=getPrime(512)
q1=getPrime(512)
r1=getPrime(512)
s1=getPrime(512)
n1=p1*q1*r1*s1
assert n1>flag
p=get_smooth_prime(1024,20,p1)
q=get_smooth_prime(1024,20,q1)
r=get_smooth_prime(1024,20,r1)
s=get_smooth_prime(1024,20,s1)
n=p*q*r*s
print(f"[+] inner RSA modulus = {n1}")
print(f"[+] outer RSA modulus = {n}")
print(f"[+] Ciphertext = {pow(flag,e,n1)}")
#省去数据流WP:
#理解了这道题后，得到p-1=2*max_prime*20_bytes素数n个*prime1*prime2,p是1024-bit
#除了max_prime,都是平滑的,a判断出要用p-1
#手上有(getPrime())512*512*512*512得到的n1;n=p*q*r*s,p-1,q-1,r-1,s-1,max_prime=前面的512
#得到p-1//P(getPrime)，有gcd(p-1,n1)=p,其他同理，得到所有的p,q,r,s得到n,计算m
#现在想怎么得到p.q.r.s现在有的就是n,就是p-1算法，详情看上面的p-1分解
#接下来就是有t的逐层剥离，说实话，我不太会这种有点抽象的程序实现
# solve_gmpy2.py
# Optimized for this challenge using gmpy2 (powmod/gcd/invert/is_prime)
import gmpy2
from gmpy2 import mpz#加速，转化成C语言的大数字计算，更快
from Crypto.Util.number import long_to_bytes
# -------------------- 题目输出（已填入） --------------------
n1 = mpz(16141229822582999941795528434053604024130834376743380417543848154510567941426284503974843508505293632858944676904777719167211264225017879544879766461905421764911145115313698529148118556481569662427943129906246669392285465962009760415398277861235401144473728421924300182818519451863668543279964773812681294700932779276119980976088388578080667457572761731749115242478798767995746571783659904107470270861418250270529189065684265364754871076595202944616294213418165898411332609375456093386942710433731450591144173543437880652898520275020008888364820928962186107055633582315448537508963579549702813766809204496344017389879)
n = mpz(484831124108275939341366810506193994531550055695853253298115538101629337644848848341479419438032232339003236906071864005366050185096955712484824249228197577223248353640366078747360090084446361275032026781246854700074896711976487694783856878403247312312487197243272330518861346981470353394149785086635163868023866817552387681890963052199983782800993485245670437818180617561464964987316161927118605512017355921555464359512280368738197370963036482455976503266489446554327046948670215814974461717020804892983665655107351050779151227099827044949961517305345415735355361979690945791766389892262659146088374064423340675969505766640604405056526597458482705651442368165084488267428304515239897907407899916127394598273176618290300112450670040922567688605072749116061905175316975711341960774150260004939250949738836358264952590189482518415728072191137713935386026127881564386427069721229262845412925923228235712893710368875996153516581760868562584742909664286792076869106489090142359608727406720798822550560161176676501888507397207863998129261472631954482761264406483807145805232317147769145985955267206369675711834485845321043623959730914679051434102698588945009836642922614296598336035078421463808774940679339890140690147375340294139027290793)
c = mpz(657984921229942454933933403447729006306657607710326864301226455143743298424203173231485254106370042482797921667656700155904329772383820736458855765136793243316671212869426397954684784861721375098512569633961083815312918123032774700110069081262242921985864796328969423527821139281310369981972743866271594590344539579191695406770264993187783060116166611986577690957583312376226071223036478908520539670631359415937784254986105845218988574365136837803183282535335170744088822352494742132919629693849729766426397683869482842748401000853783134170305075124230522253670782186531697976487673160305610021244587265868919495629)
e = mpz(65537)
# -------------------- 工具：筛 primes <= Bmax（Python int 即可） --------------------
#这个可以复用。用来扫描范围的素数
def primes_upto(Bmax: int):
sieve = bytearray(b"\x01") * (Bmax + 1)#建立一个布尔值的列表
sieve[0:2] = b"\x00\x00"
import math
for i in range(2, int(math.isqrt(Bmax)) + 1):
if sieve[i]:
step = i
start = i * i
sieve[start:Bmax+1:step] = b"\x00" * (((Bmax - start) // step) + 1)
return [i for i in range(2, Bmax + 1) if sieve[i]]
# -------------------- Stage1 核心：算 a^{lcm(1..B)} mod N（用 gmpy2.powmod） --------------------
#这个可以复用a**lcm(1..B)mod n,并且还有对应素数链
def pow_lcm(a: mpz, B: int, N: mpz, primes_list):
"""
返回 x = a^{lcm(1..B)} mod N
"""
x = a % N
for ell in primes_list:
if ell > B:
break
t = ell
while t * ell <= B:
t *= ell
x = gmpy2.powmod(x, t, N) # fast powmod
return x
# -------------------- 本题“补大因子”的命中函数（用 gmpy2.gcd / powmod） --------------------
#命中器复用，简称gcd，gcd(p-1,n)
def hit_outer_factor(N: mpz, n1_inner: mpz, B: int, primes_list, a_int: int):
"""
b = a^{lcm(1..B)} mod N
g = gcd(b^{n1}-1, N)
"""
a = mpz(a_int)
g0 = gmpy2.gcd(a, N)
if 1 < g0 < N:
return g0
b = pow_lcm(a, B, N, primes_list)
y = gmpy2.powmod(b, n1_inner, N)
g = gmpy2.gcd(y - 1, N)
if 1 < g < N:
return g
return None
# -------------------- 外层递归分解（允许 gcd 先吐出乘积因子） --------------------
#逐层剥离复用
def factor_outer(n_outer: mpz, n1_inner: mpz, primes_list):
# 更丰富一点的底数集合
a_list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
B0 = 1_048_576
coarse = list(range(B0, 860_000, -20_000))
fine_steps = [5000, 2000, 1000, 500]
def try_split_once(X: mpz):
if gmpy2.is_prime(X):
return None
# coarse scan
for B in coarse:
for a in a_list:
g = hit_outer_factor(X, n1_inner, B, primes_list, a)
if g is not None:
return (g, B, a)
# fine scan
for step in fine_steps:
for B in range(B0, 860_000, -step):
for a in a_list:
g = hit_outer_factor(X, n1_inner, B, primes_list, a)
if g is not None:
return (g, B, a)
return None
stack = [n_outer]
primes = []
while stack:
X = stack.pop()
if X == 1:
continue
if gmpy2.is_prime(X):
primes.append(X)
continue
res = try_split_once(X)
if res is None:
raise RuntimeError(
f"[!] Failed to split a composite of {int(gmpy2.bit_length(X))} bits. "
f"Try extending B scan range or adding more a values."
)
g, B_used, a_used = res
print(f"[+] split (bits={int(gmpy2.bit_length(X))}) using B={B_used}, a={a_used}, got g bits={int(gmpy2.bit_length(g))}")
stack.append(g)
stack.append(X // g)
primes.sort()
return primes
# -------------------- 从外层素数 P 抽内层素数：gcd(P-1, n1) --------------------
def recover_inner_primes(outer_primes, n1_inner: mpz):
rem = n1_inner
inner = []
for P in outer_primes:
g = gmpy2.gcd(P - 1, rem)
if 1 < g < rem:
inner.append(g)
rem //= g
if rem != 1 and rem != n1_inner:
inner.append(rem)
inner = sorted(set(inner))
return inner
# -------------------- 解密内层 RSA（用 gmpy2.invert / powmod） --------------------
def decrypt_inner(c: mpz, e: mpz, inner_primes, n1_inner: mpz):
if len(inner_primes) != 4:
raise ValueError(f"[!] need 4 inner primes, got {len(inner_primes)}: {inner_primes}")
phi = mpz(1)
for p in inner_primes:
phi *= (p - 1)
d = gmpy2.invert(e, phi)
if d == 0:
raise ValueError("[!] e is not invertible mod phi (unexpected in this challenge).")
m = gmpy2.powmod(c, d, n1_inner)
pt = long_to_bytes(int(m), 256)
return pt
def extract_flag(pt: bytes):
for prefix in [b"flag{", b"FLAG{", b"ctf{", b"CTF{"]:
if prefix in pt:
i = pt.index(prefix)
j = pt.find(b"}", i)
if j != -1:
return pt[i:j+1]
return pt
def main():
Bmax = 1_048_576
print("[*] sieving primes up to", Bmax)
primes_list = primes_upto(Bmax)
print("[*] primes count:", len(primes_list))
print("[*] factoring outer n ...")
outer_primes = factor_outer(n, n1, primes_list)
print("[+] outer primes found:", len(outer_primes))
for i, P in enumerate(outer_primes, 1):
print(f" P{i} bits={int(gmpy2.bit_length(P))}")
print("[*] recovering inner primes via gcd(P-1, n1):")
inner_primes = recover_inner_primes(outer_primes, n1)
print("[+] inner primes recovered:", len(inner_primes))
for i, p in enumerate(inner_primes, 1):
print(f" p{i} bits={int(gmpy2.bit_length(p))}")
print("[*] decrypting inner RSA ...")
pt = decrypt_inner(c, e, inner_primes, n1)
flag = extract_flag(pt)
print("[+] plaintext (first 80 bytes):", pt[:80])
print("[+] flag:", flag)
if __name__ == "__main__":
main()
#对于我这种代码低能，掌握代码摘要以便以后使用就可以了
#比如 lcm(..)代码复用属于常见的提示了光滑的RSA，难点是写代码
最大的启示是要夯实基础，落实代码，不过看到密码即使AK也只有150分还是挺难崩的，再不认真要被AI取代了（？？？）。。。
发表回复