长城杯2025crypto方向复现题解
Ezflagtask分析题目给了个64 位 Linux 动态链接可执行文件（PIE），目标机器不是 Windows。判断为re+密码 题，主要是没接触过逆向，逆出来的东西有点懵逼。我们可以知道程序的运行逻辑是输入密码，然后运行f函数，逐步输出flag。其中密码在逆出来的伪代码中可以直接得到。因为f函数的作用是计算斐波那契数列，如果按照程序里面的输入密码运行程序那么在有限时间内无法获取flag，我们
Ezflag
task
int __fastcall main(int argc, const char **argv, const char **envp)
{
__int64 v3; // rax
__int64 v4; // rax
_BYTE v6[32]; // [rsp+0h] [rbp-50h] BYREF
_BYTE v7[12]; // [rsp+20h] [rbp-30h] BYREF
int v8; // [rsp+2Ch] [rbp-24h] BYREF
char v9; // [rsp+33h] [rbp-1Dh]
int i; // [rsp+34h] [rbp-1Ch]
unsigned __int64 v11; // [rsp+38h] [rbp-18h]
std::string::basic_string(v6, argv, envp);
std::operator<<<std::char_traits<char>>(&std::cout, "Enter password: ");
std::getline<char,std::char_traits<char>,std::allocator<char>>(&std::cin, v6);
if ( (unsigned __int8)std::operator!=<char>(v6, "V3ryStr0ngp@ssw0rd") )
{
v3 = std::operator<<<std::char_traits<char>>(&std::cout, "Wrong password!");
std::ostream::operator<<(v3, &std::endl<char,std::char_traits<char>>);
}
else
{
std::operator<<<std::char_traits<char>>(&std::cout, "flag{");
std::ostream::flush((std::ostream *)&std::cout);
v11 = 1;
for ( i = 0; i <= 31; ++i )
{
v9 = f(v11);
std::operator<<<std::char_traits<char>>(&std::cout, (unsigned int)v9);
std::ostream::flush((std::ostream *)&std::cout);
if ( i == 7 || i == 12 || i == 17 || i == 22 )
{
std::operator<<<std::char_traits<char>>(&std::cout, "-");
std::ostream::flush((std::ostream *)&std::cout);
}
v11 *= 8LL;
v11 += i + 64;
v8 = 1;
std::chrono::duration<long,std::ratio<1l,1l>>::duration<int,void>(v7, &v8);
std::this_thread::sleep_for<long,std::ratio<1l,1l>>(v7);
}
v4 = std::operator<<<std::char_traits<char>>(&std::cout, "}");
std::ostream::operator<<(v4, &std::endl<char,std::char_traits<char>>);
}
std::string::~string(v6);
return 0;
}__int64 __fastcall f(unsigned __int64 a1)
{
__int64 v2; // [rsp+10h] [rbp-20h]
unsigned __int64 i; // [rsp+18h] [rbp-18h]
__int64 v4; // [rsp+20h] [rbp-10h]
__int64 v5; // [rsp+28h] [rbp-8h]
v5 = 0;
v4 = 1;
for ( i = 0; i < a1; ++i )
{
v2 = v4;
v4 = ((_BYTE)v5 + (_BYTE)v4) & 0xF;
v5 = v2;
}
return *(unsigned __int8 *)std::string::operator[](&K, v5);
}分析
题目给了个64 位 Linux 动态链接可执行文件（PIE），目标机器不是 Windows。
判断为re+密码 题，主要是没接触过逆向，逆出来的东西有点懵逼。
我们可以知道程序的运行逻辑是输入密码，然后运行f函数，逐步输出flag。其中密码在逆出来的伪代码中可以直接得到。
因为f函数的作用是计算斐波那契数列，如果按照程序里面的输入密码运行程序那么在有限时间内无法获取flag，我们真正需要的只是 fib(v) mod 16，不是整个斐波那契数列。而在模 16 下，斐波那契序列是周期的 —— 这个周期叫 Pisano 周期，所以通过数学分析其实一下子就能得到flag。
其中生成flag的字符集为
由这个字符集得到的斐波那契模 16 的周期如下：
0 1 1 2 3 5 8 13 5 2 7 9 0 9 9 2 11 13 8 5 13 2 15 1
接下来对比索引即可得到答案，然后可以通过简短得运行程序来验证答案。
结果为
flag{10632674-1d219-09f29-14769-f60219a24}RSA_NestingDoll
task
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): #1024 20
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)}")
[+] inner RSA modulus = 16141229822582999941795528434053604024130834376743380417543848154510567941426284503974843508505293632858944676904777719167211264225017879544879766461905421764911145115313698529148118556481569662427943129906246669392285465962009760415398277861235401144473728421924300182818519451863668543279964773812681294700932779276119980976088388578080667457572761731749115242478798767995746571783659904107470270861418250270529189065684265364754871076595202944616294213418165898411332609375456093386942710433731450591144173543437880652898520275020008888364820928962186107055633582315448537508963579549702813766809204496344017389879
[+] outer RSA modulus = 484831124108275939341366810506193994531550055695853253298115538101629337644848848341479419438032232339003236906071864005366050185096955712484824249228197577223248353640366078747360090084446361275032026781246854700074896711976487694783856878403247312312487197243272330518861346981470353394149785086635163868023866817552387681890963052199983782800993485245670437818180617561464964987316161927118605512017355921555464359512280368738197370963036482455976503266489446554327046948670215814974461717020804892983665655107351050779151227099827044949961517305345415735355361979690945791766389892262659146088374064423340675969505766640604405056526597458482705651442368165084488267428304515239897907407899916127394598273176618290300112450670040922567688605072749116061905175316975711341960774150260004939250949738836358264952590189482518415728072191137713935386026127881564386427069721229262845412925923228235712893710368875996153516581760868562584742909664286792076869106489090142359608727406720798822550560161176676501888507397207863998129261472631954482761264406483807145805232317147769145985955267206369675711834485845321043623959730914679051434102698588945009836642922614296598336035078421463808774940679339890140690147375340294139027290793
[+] Ciphertext = 657984921229942454933933403447729006306657607710326864301226455143743298424203173231485254106370042482797921667656700155904329772383820736458855765136793243316671212869426397954684784861721375098512569633961083815312918123032774700110069081262242921985864796328969423527821139281310369981972743866271594590344539579191695406770264993187783060116166611986577690957583312376226071223036478908520539670631359415937784254986105845218988574365136837803183282535335170744088822352494742132919629693849729766426397683869482842748401000853783134170305075124230522253670782186531697976487673160305610021244587265868919495629分析
先来看参数生成逻辑，out 提供了加密的公钥 n1 和 e，以及加密后的密文 c，还有本题的关键信息，由生成 n1 的各因子再派生出的 n。
观察 get_smooth 函数我们可以得知 p1,q1,r1,s1 的生成逻辑如下：
很明显的 p-1 光滑攻击，但是这里直接用板子的话时间会爆炸，因为上界来到了 512 位的大小。
解决方法就是将我们已知的 n1 当作已构造的光滑数，再去爆破其他的小素数，这样速度就能得到很好的改善。因为 n1 中已经包含了素因子 pqrs，而多出来的数其实不会影响结果：
exp
import random
import sys
import time
from gmpy2 import gcd, is_prime, mpz, powmod
from Crypto.Util.number import *
def split(m):
a=1
for attempt in range(40):
a =a+1
t0 = time.time()
x = powmod(a, n1, m) # 第一步：乘 n1，消掉 512 位大因子
x = powmod(x, L, m) # 第二步：乘光滑部分
for g in (gcd(x - 1, m), gcd(x + 1, m)):
if 1 < g < m:
return int(g)
return None
def factor(m, out):
"""递归分解。指数 L 不变、模数逐层变小，所以耗时递减。"""
if is_prime(mpz(m)):
out.append(m)
return
g = split(mpz(m))
factor(g, out) #这里递归调用是为了防止第一次分解出合数，所以重复调用知道分解出素数为止
factor(m // g, out)
def primes_below(hi): #埃氏筛，返回 [2, hi) 内全部素数
sieve = bytearray([1]) * hi
sieve[0:2] = b"\x00\x00"
for i in range(2, int(hi ** 0.5) + 1):
if sieve[i]:
sieve[i * i::i] = bytearray(len(range(i * i, hi, i)))
return [i for i in range(2, hi) if sieve[i]]
n1 = mpz(16141229822582999941795528434053604024130834376743380417543848154510567941426284503974843508505293632858944676904777719167211264225017879544879766461905421764911145115313698529148118556481569662427943129906246669392285465962009760415398277861235401144473728421924300182818519451863668543279964773812681294700932779276119980976088388578080667457572761731749115242478798767995746571783659904107470270861418250270529189065684265364754871076595202944616294213418165898411332609375456093386942710433731450591144173543437880652898520275020008888364820928962186107055633582315448537508963579549702813766809204496344017389879)
n = mpz(484831124108275939341366810506193994531550055695853253298115538101629337644848848341479419438032232339003236906071864005366050185096955712484824249228197577223248353640366078747360090084446361275032026781246854700074896711976487694783856878403247312312487197243272330518861346981470353394149785086635163868023866817552387681890963052199983782800993485245670437818180617561464964987316161927118605512017355921555464359512280368738197370963036482455976503266489446554327046948670215814974461717020804892983665655107351050779151227099827044949961517305345415735355361979690945791766389892262659146088374064423340675969505766640604405056526597458482705651442368165084488267428304515239897907407899916127394598273176618290300112450670040922567688605072749116061905175316975711341960774150260004939250949738836358264952590189482518415728072191137713935386026127881564386427069721229262845412925923228235712893710368875996153516581760868562584742909664286792076869106489090142359608727406720798822550560161176676501888507397207863998129261472631954482761264406483807145805232317147769145985955267206369675711834485845321043623959730914679051434102698588945009836642922614296598336035078421463808774940679339890140690147375340294139027290793)
c = mpz(657984921229942454933933403447729006306657607710326864301226455143743298424203173231485254106370042482797921667656700155904329772383820736458855765136793243316671212869426397954684784861721375098512569633961083815312918123032774700110069081262242921985864796328969423527821139281310369981972743866271594590344539579191695406770264993187783060116166611986577690957583312376226071223036478908520539670631359415937784254986105845218988574365136837803183282535335170744088822352494742132919629693849729766426397683869482842748401000853783134170305075124230522253670782186531697976487673160305610021244587265868919495629)
e = mpz(65537)
L=1
for i in primes_below(1 << 20):
if i >= (1 << 9):
L=L*i
outer = []
factor(n, outer)
inner = [int(gcd(mpz(p) - 1, n1)) for p in outer]
phi = 1
for f in inner:
phi *= f - 1
d = powmod(e, -1, phi)
m = int(powmod(c, d, n1))
print("FLAG =", long_to_bytes(m))结果如下:
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
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())) #转16进制
f_sig = open("signatures.txt", "w")
for m, s in sigs:
f_sig.write("%s:%s\n" % (m, s))
f_sig.close()分析
本题给了很多的混淆信息？又是pem文件又是签名前后的结果，但是题目只要求拿到私钥，并且私钥的生成非常的清晰，都摆在源码里面了，只能说这题是在吓唬不懂ecdsa的人hhh。
运行逻辑为通过指定字符串的sha512和NIST521p曲线的阶来生成私钥，然后用私钥创建信息，提取公钥，依次从不知道拿来的 bytes列表中提取元素加密，最后写入文件，后面其实都没必要看。
因为字符串已经写在源码，且NIST521p曲线的阶也能查到，所以简单计算一下就行了。exp都没必要写
总结
……
END