第十九届全国大学生信息安全竞赛 Crypto WriteUp

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()

非预期解，题目中直接给出了私钥的生成方式，直接运行就能得到私钥，逆天

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)

题目需要交的flag是私钥的MD5值，需要注意的是这里要交的是md5(priv_int)而非md5(priv_bytes)

from hashlib import sha512,md5
from ecdsa import NIST521p

# 1. 根据代码中的逻辑计算摘要
digest_bytes = sha512(b"Welcome to this challenge!").digest()
digest_int = int.from_bytes(digest_bytes, "big")

# 2. 获取曲线阶数
curve_order = NIST521p.order

# 3. 计算私钥
priv_int = digest_int % curve_order

print(f"私钥 (十进制): {priv_int}")
print(f"私钥 (十六进制): {hex(priv_int)}")

# 4. 计算私钥的MD5值
md5_hash = md5(str(priv_int).encode()).hexdigest()

# 输出flag格式
print(f"flag{{{md5_hash}}}")

只能说浪费了一个小时看nonce函数和加密过程，我服了

EzFlag

int __cdecl main(int argc, const char **argv, const char **envp)
{
  __int64 v3; // rax
  __int64 v4; // rax
  char v6[32]; // [rsp+0h] [rbp-50h] BYREF
  char 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>>(&_bss_start, "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>>(&_bss_start, "Wrong password!");
    std::ostream::operator<<(v3, &std::endl<char,std::char_traits<char>>);
  }
  else
  {
    std::operator<<<std::char_traits<char>>(&_bss_start, "flag{");
    std::ostream::flush((std::ostream *)&_bss_start);
    v11 = 1LL;
    for ( i = 0; i <= 31; ++i )
    {
      v9 = f(v11);
      std::operator<<<std::char_traits<char>>(&_bss_start, (unsigned int)v9);
      std::ostream::flush((std::ostream *)&_bss_start);
      if ( i == 7 || i == 12 || i == 17 || i == 22 )
      {
        std::operator<<<std::char_traits<char>>(&_bss_start, "-");
        std::ostream::flush((std::ostream *)&_bss_start);
      }
      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>>(&_bss_start, "}");
    std::ostream::operator<<(v4, &std::endl<char,std::char_traits<char>>);
  }
  std::string::~string(v6);
  return 0;
}

上面这个是main函数，其中关键是v9 = f(v11)处理，下面是f函数，实现的是一个模16的斐波那契数列，而模上的斐波那契数列是有周期性的。可以找到K的值为012ab9c3478d56ef

__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 = 0LL;
  v4 = 1LL;
  for ( i = 0LL; i < a1; ++i )
  {
    v2 = v4;
    v4 = ((_BYTE)v5 + (_BYTE)v4) & 0xF;
    v5 = v2;
  }
  return *(unsigned __int8 *)std::string::operator[](&K, v5);
}

代码逻辑很简单，直接写解题脚本

#include <iostream>
#include <string>
#include <cstdint>

// 全局变量 K，对应反编译代码中的 K
std::string K = "012ab9c3478d56ef";

// 斐波那契数列模 16 的周期表 (周期为 24)
// Fib(n) % 16 的值
const int fib_mod_16[24] = {
    0, 1, 1, 2, 3, 5, 8, 13, 
    5, 2, 7, 9, 0, 9, 9, 2, 
    11, 13, 8, 5, 13, 2, 15, 1
};

// 模拟 f 函数
// 反编译代码中的循环 for(i=0; i<a1; ++i) 在 a1 极大时不可行，
// 这里利用数学性质 (周期性) 进行了优化，结果等价。
char f(uint64_t a1) {
    // 计算索引
    int index = fib_mod_16[a1 % 24];
    // 返回 K 中对应的字符
    return K[index];
}

int main() {
    // v11 必须是 unsigned long long (64位无符号)，以确保发生溢出
    unsigned long long v11 = 1;
    
    std::string flag = "flag{";

    for (int i = 0; i < 32; ++i) {
        // 1. 调用 f 计算字符
        char c = f(v11);
        flag += c;

        // 2. 插入连字符
        if (i == 7 || i == 12 || i == 17 || i == 22) {
            flag += "-";
        }

        // 3. 更新 v11 状态
        // 注意：这里 v11 * 8 会触发 64 位整数溢出，正是溢出导致了后半部分 flag 的不同
        v11 = v11 * 8 + i + 64;
    }

    flag += "}";

    // 输出最终结果
    std::cout << flag << std::endl;

    return 0;
}

这里有个大坑，用Python默认的高精度整数掩盖了溢出，而 C++ 的 uint64_t 自然产生的溢出改变了 v11 % 24 的结果。所以如果没考虑到溢出的问题，Python跑出的答案后半段是错误。

RSA_NestingDoll

scr.py文件

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)}")

output.txt

[+] inner RSA modulus = 16141229822582999941795528434053604024130834376743380417543848154510567941426284503974843508505293632858944676904777719167211264225017879544879766461905421764911145115313698529148118556481569662427943129906246669392285465962009760415398277861235401144473728421924300182818519451863668543279964773812681294700932779276119980976088388578080667457572761731749115242478798767995746571783659904107470270861418250270529189065684265364754871076595202944616294213418165898411332609375456093386942710433731450591144173543437880652898520275020008888364820928962186107055633582315448537508963579549702813766809204496344017389879
[+] outer RSA modulus = 484831124108275939341366810506193994531550055695853253298115538101629337644848848341479419438032232339003236906071864005366050185096955712484824249228197577223248353640366078747360090084446361275032026781246854700074896711976487694783856878403247312312487197243272330518861346981470353394149785086635163868023866817552387681890963052199983782800993485245670437818180617561464964987316161927118605512017355921555464359512280368738197370963036482455976503266489446554327046948670215814974461717020804892983665655107351050779151227099827044949961517305345415735355361979690945791766389892262659146088374064423340675969505766640604405056526597458482705651442368165084488267428304515239897907407899916127394598273176618290300112450670040922567688605072749116061905175316975711341960774150260004939250949738836358264952590189482518415728072191137713935386026127881564386427069721229262845412925923228235712893710368875996153516581760868562584742909664286792076869106489090142359608727406720798822550560161176676501888507397207863998129261472631954482761264406483807145805232317147769145985955267206369675711834485845321043623959730914679051434102698588945009836642922614296598336035078421463808774940679339890140690147375340294139027290793
[+] Ciphertext = 657984921229942454933933403447729006306657607710326864301226455143743298424203173231485254106370042482797921667656700155904329772383820736458855765136793243316671212869426397954684784861721375098512569633961083815312918123032774700110069081262242921985864796328969423527821139281310369981972743866271594590344539579191695406770264993187783060116166611986577690957583312376226071223036478908520539670631359415937784254986105845218988574365136837803183282535335170744088822352494742132919629693849729766426397683869482842748401000853783134170305075124230522253670782186531697976487673160305610021244587265868919495629

GPT-5.2直接一把出，只能说国内大模型还是差一点

import math
import random
import time
from math import gcd
from sympy import mod_inverse  # 使用sympy的模逆函数

def long_to_bytes(n, block_size):
    """
    将大整数转换为字节，不足block_size则在前面补零
    """
    b = []
    while n > 0:
        b.append(n & 0xff)
        n >>= 8
    # 补零到block_size
    b.extend([0] * (block_size - len(b)))
    return bytes(reversed(b))

def read_output(filename):
    """
    读取output.txt，提取内模n1、外模n、密文c
    """
    with open(filename, 'r') as f:
        lines = f.read().strip().splitlines()
    # 假设输出格式如下：
    # [+] inner RSA modulus = ...
    # [+] outer RSA modulus = ...
    # [+] Ciphertext = ...
    n1 = int(lines[0].split('=')[1].strip())
    n = int(lines[1].split('=')[1].strip())
    c = int(lines[2].split('=')[1].strip())
    return n1, n, c

def primes_upto(n):
    """
    使用筛法生成小于等于n的素数列表
    """
    sieve = bytearray(b'\x01') * (n + 1)
    sieve[0:2] = b'\x00\x00'
    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:
            step = i
            start = i * i
            sieve[start:n+1:step] = b'\x00' * ((n - start) // step + 1)
    return [i for i in range(n + 1) if sieve[i]]

def pollard_pm1_with_multiplier(n, mult, B=1<<20, a=2, primes=None, check_every=1):
    """
    Pollard's p-1算法（第一阶段）
    返回非平凡因子或None
    """
    if primes is None:
        primes = primes_upto(B)
    b = pow(a, mult, n)
    for idx, p in enumerate(primes):
        pk = p
        while pk * p <= B:
            pk *= p
        b = pow(b, pk, n)
        g = gcd(b-1, n)
        if 1 < g < n:
            return g, idx, p, pk
    return None, None, None, None

def pollard_sequence_factor(n, multiplier, primes_list, a=2, seed=123):
    """
    使用Pollard's p-1算法序列分解n
    尝试返回n的因子列表，如果完全分解则返回素因子列表，否则可能返回部分因子
    """
    rng = random.Random(seed)
    plist = primes_list[:]
    rng.shuffle(plist)
    
    factors = []
    N = n
    b = pow(a, multiplier, N)
    
    for p in plist:
        b = pow(b, p, N)
        g = gcd(b-1, N)
        if 1 < g < N:
            factors.append(g)
            N //= g
            if N == 1:
                return factors
            b %= N
            # 继续寻找剩余因子
            while True:
                g2 = gcd(b-1, N)
                if 1 < g2 < N:
                    factors.append(g2); N //= g2
                    if N == 1:
                        return factors
                    b %= N
                else:
                    break
    if N != 1:
        factors.append(N)
    return factors

def main():
    # 1. 读取数据
    n1, n, c = read_output('output.txt')
    
    # 2. 生成素数列表：小素数（<=65536）和大素数（>=2^19）
    B = 1 << 20
    small_max = 1 << 16  # 65536
    low_high = 1 << 19
    
    primes_all = primes_upto(B)
    small_primes = [p for p in primes_all if p <= small_max]
    high_primes = [p for p in primes_all if p >= low_high]
    primes_list = small_primes + high_primes
    
    # 3. 使用Pollard's p-1算法序列分解外模n
    # 使用种子7，参考信息中成功分解的种子
    start_time = time.time()
    outer_factors = pollard_sequence_factor(n, n1, primes_list, a=2, seed=7)
    elapsed = time.time() - start_time
    print(f"Outer factors found in {elapsed:.2f} seconds: {[f.bit_length() for f in outer_factors]}")
    
    # 4. 对每个外模因子P，计算gcd(P-1, n1)得到内模素因子
    inner_primes = []
    for P in outer_factors:
        g = gcd(P-1, n1)
        inner_primes.append(g)
    print(f"Inner primes (bit lengths): {[p.bit_length() for p in inner_primes]}")
    
    # 5. 验证内模素因子的乘积是否等于n1
    from functools import reduce
    from operator import mul
    assert reduce(mul, inner_primes, 1) == n1, "Inner primes product not equal to n1"
    
    # 6. 计算phi
    phi = 1
    for p in inner_primes:
        phi *= (p-1)
    
    # 7. 计算d
    e = 65537
    d = mod_inverse(e, phi)
    
    # 8. 解密
    m = pow(c, d, n1)
    
    # 9. 转换为字节，寻找flag
    pt = long_to_bytes(m, 256)
    start = pt.find(b'flag{')
    end = pt.find(b'}', start)
    if start != -1 and end != -1:
        flag = pt[start:end+1]
        print(f"Flag: {flag}")
    else:
        print("Flag not found in plaintext")
        print(f"Plaintext: {pt}")

if __name__ == '__main__':
    main()