WKCTF

记录WKCTF——Crypto部分题解

fl@g

task.py

from Crypto.Util.number import *
from sympy import *
from tqdm import *
from secret import flag
from itertools import *
from math import factorial
import string

table = string.ascii_letters + string.digits + "@?!*"

def myprime():
    num = 0
    for i in tqdm(permutations(table) , total=factorial(len(table))):
        temp = "".join(list(i))
        if("flag" in temp or "FLAG" in temp or "f14G" in temp or "7!@9" in temp or "🚩" in temp):
            num += 1
    return nextprime(num)

m = bytes_to_long(flag)
n = myprime()*getPrime(300)
c = pow(m,65537,n)

print("n =",n)
print("c =",c)


'''
n = 10179374723747373757354331803486491859701644330006662145185130847839571647703918266478112837755004588085165750997749893646933873398734236153637724985137304539453062753420396973717
c = 1388132475577742501308652898326761622837921103707698682051295277382930035244575886211234081534946870195081797116999020335515058810721612290772127889245497723680133813796299680596
'''

排列组合问题，可以转换为:flag or FLAG or f14G or 7!@9 or 🚩在temp中出现的所有情况

先是考虑单个字符串出现的可能性，比如flag出现的可能性有$A_{62}^{62}\times 63$，先把flag抽出来，剩下62个字符排列，然后把flag往62个字符排好的队伍里插入，共有63个位置可以插入。

然后考虑重复出现的情况，这里只有4种可能，flag和FLAG，flag和7!@9，FLAG和7!@9，f14G和7!@9

两个字符串重复出现的可能性有$A_{58}^{58}\times 59\times 60$，先把两个字符串抽出来，剩下58个字符排列，再把字符串往里面插，第一个字符串插入的时候有59个空位，第二个字符串插入的时候有60个空位。

还要考虑flag FLAG 7!@9同时出现的情况，有$A_{54}^{54}\times 55 \times 56 \times 57$种可能，先把三个字符串抽出来，剩下的54个字符排列，再把字符串往里面插，第一个字符串插入的时候有55个空位，第二个字符串插入的时候有56个空位，第三个字符串插入的时候有57个空位。

然后把单个字符串出现的可能性相加，减去两个字符串重复出现的可能性，最后加上三个字符串重复出现的可能性。(卡了好久😭)

exp.py

from sympy import nextprime,factorial
from Crypto.Util.number import *

a = factorial(62) * 63 * 4 - factorial(58) * 59 * 60 * 4+ factorial(54) * 55 * 56 * 57

p = nextprime(a)
n = 10179374723747373757354331803486491859701644330006662145185130847839571647703918266478112837755004588085165750997749893646933873398734236153637724985137304539453062753420396973717
c = 1388132475577742501308652898326761622837921103707698682051295277382930035244575886211234081534946870195081797116999020335515058810721612290772127889245497723680133813796299680596
print(p.bit_length())
print(n % p)
q = n // p
d = inverse(65537,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
# WKCTF{How_long_does_it_take_to_run_directly?}

easy_random

task.py

import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

flag = b'WKCTF{}'
pad_flag = pad(flag,16)
key = random.randbytes(16)
cipher = AES.new(key,AES.MODE_ECB)
print(cipher.encrypt(pad_flag))
# b'a\x93\xdc\xc3\x90\x0cK\xfa\xfb\x1c\x05$y\x16:\xfc\xf3+\xf8+%\xfe\xf9\x86\xa3\x17i+ab\xca\xb6\xcd\r\xa5\x94\xeaVM\xdeo\xa7\xdf\xa9D\n\x02\xa3'
with open('random.txt','w') as f:
    for i in range(2496):
        f.write(str(random.getrandbits(8))+'\n')

思路倒是挺清晰的。

通过给出的随机数，回推key，再解AES

具体原理参考这篇文章的 2020 pwnhub CoinFlip2，文章里那道题目是随机数的高1位泄露，一共泄露了19968bit(无论泄露多少位，只要凑出19968bit就可以恢复state)

稍微改动一下文章的exp，我们就可以得到这道题产生随机数的state。(原理是不懂的，只会套板子😭)

main.py

from sage.all import *
from random import Random
from tqdm import *

prng = Random()
length = 19968

def myState():
    state = [0]*624
    i = 0
    while i < length:
        ind = i // 32
        expont = i % 32
        state[ind] = 1 << (31 - expont)
        s = (3,tuple(state + [0]),None)
        yield s
        state[ind] = 0
        i += 1

def getRow():
    rng = Random()
    gs = myState()
    for i in range(length):
        s = next(gs)
        rng.setstate(s)
        data=[]
        for i in range(length // 8):
            data.extend(list(bin(rng.getrandbits(8))[2:].zfill(8)))
        data = [int(i) for i in data] # 只有1行，还是length长度
        row = vector(GF(2),data)
        yield row

def buildBox():
    b = matrix(GF(2),length,length)
    rg = getRow()
    for i in tqdm(range(length)):
        b[i] = next(rg)
    return b # length * length

def test():
    prng = Random()
    originState = prng.getstate()
    # 这里都是用的MSB,如果采用不同的二进制位(如LSB)最后的矩阵T 也会不同
    leak = []
    for i in range(length // 8):
        leak.extend(list(bin(prng.getrandbits(8))[2:].zfill(8)))
    leak = [int(i) for i in leak]
    leak = vector(GF(2),leak) # leak 长度为 length
    T = buildBox()
    with open("Matirx","w") as f:
        for i in trange(T.nrows()):
            for j in range(T.ncols()):
                f.write(str(T[i,j])+'n')
    x = T.solve_left(leak)
    x = ''.join([str(i) for i in x.list()])
    state = []
    for i in range(624):
        tmp = int(x[i*32:(i+1)*32],2)
        state.append(tmp)
    prng.setstate(originState)
    prng.getrandbits(8)
    originState = [x for x in prng.getstate()[1][:-1]]
    print(originState[1:] == state[1:])
#     print(state)
    return state,T

def buildMatrix():
    with open("Matrix","r") as f:
        data = [int(x) for x in f.read().split('n')]
    m = matrix(GF(2),length,length,data)
    return m

# X = Z*(T^-1)
def recoverState(T,leak):
    x = T.solve_left(leak)
    x = ''.join([str(i) for i in x.list()])
    state = []
    for i in range(624):
        tmp = int(x[i * 32:(i + 1) * 32], 2)
        state.append(tmp)
    return state


# 根据题型2,还原state,有两种可能,这时候可以用暴破
def backfirst(state):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908b0df
    tmp = state[623] ^ state[396]
    if tmp & high == high:
        tmp ^= mask
        tmp <<= 1
        tmp |= 1
    else:
        tmp <<= 1
    return (1 << 32 - 1) | tmp & low, tmp & low

def main():
    _, T = test()
    print('构建完成')
    print("T完成")
    prng = Random()
    originState = prng.getstate()
    # 题目给的数据
    leak = []
    
    leak1 = [int(j) for j in "".join([bin(i)[2:].zfill(8) for i in leak[:19968 // 8]])]
    leak1 = matrix(GF(2), leak1)
    # 恢复state
    state = recoverState(T,leak1)
    print("state恢复完成")
    # 两种可能
    guess1, guess2 = backfirst(state)
    print(f"两种可能分别为{guess1}, {guess2}")
    state[0] = guess1
    s = state
    prng.setstate((3, tuple(s + [0]), None))
    if True:
        print("尝试第一种可能")
        prng.setstate((3, tuple(s + [0]), None))
        now =  [prng.getrandbits(8) for i in range(2496)]
        if now == leak:
            print("第一个可能尝试成功")
            print(f"state = {state}")
            return
    state[0] = guess2
    s = state
    prng.setstate((3, tuple(s + [0]), None))
    if True:
        print("尝试第二种可能")
        prng.setstate((3, tuple(s + [0]), None))
        now =  [prng.getrandbits(8) for i in range(2496)]
        if now == leak:
            print("第二个可能尝试成功")
            print(f"state = {state}")
            return
main()

得到的state如下

state = [2922114156, 2886276701, 1168768544, 2339187170, 3551087255, 117510054, 4232565172, 1076139110, 3366831833, 1734453078, 4105913658, 1066792668, 2395352043, 785096749, 3707690263, 2430171307, 2064716469, 1119720065, 1112222395, 2136656989, 2232844740, 388978998, 1363102788, 67899517, 457789137, 3527002829, 1187847099, 1188611575, 3830294635, 3760337941, 297081839, 3230408812, 2906355860, 279725084, 3056220997, 1053068885, 3252084646, 2818726015, 3615795115, 2751222655, 74688614, 1452880497, 426221319, 1680367484, 4211465923, 908441837, 2290937869, 526329269, 3225608663, 350552485, 885538125, 3496826412, 3347875222, 2730243675, 1823616219, 1474037291, 2474670592, 1175091387, 1527449390, 2024565653, 2185945759, 902338428, 3571876882, 632524934, 1235569406, 3612682285, 2727233684, 2085380963, 1570339017, 3839696585, 1482742582, 646051896, 3804319832, 2113555238, 4150326517, 2606046640, 1454130831, 1919843931, 1018624146, 1956310311, 1162868231, 1118548906, 974692065, 3020424226, 2996838388, 1724936385, 1668410782, 3044755338, 3710133971, 1043581839, 362583150, 3880481779, 114234888, 1724135673, 1280834309, 2958310395, 3502226151, 620064160, 3244210820, 3839287479, 2283659292, 405764632, 29535149, 2759062778, 1662916252, 2374319319, 3359789079, 1896011543, 1991740933, 2041947596, 3393060496, 996086198, 193135800, 1184463268, 819767446, 410330102, 569788256, 3880255000, 340523190, 885031563, 2752345656, 4116368372, 1738848623, 1895472503, 85502529, 334873925, 3543996685, 3082948803, 3195880838, 1458851187, 2843458392, 20236078, 3136689072, 2121777470, 3543587943, 3590933177, 4057799526, 1241162800, 1014541188, 1031410742, 267989518, 92604561, 2190353015, 87786611, 435741463, 3800398555, 1860727248, 2608606593, 287619193, 768990059, 1686137462, 3255556540, 3234299857, 2087562050, 1575350832, 1982640551, 1476745138, 2757668599, 108958643, 337813164, 273001595, 3515727084, 2976758889, 2674818924, 2133197017, 3709052669, 1992118633, 2421927781, 174599786, 3608298365, 1708985493, 3925831183, 3063611093, 3852984733, 540242111, 1623482619, 1874921843, 1317809124, 2774735715, 3828180102, 1997343223, 1516869708, 941992323, 307089973, 368181535, 163007409, 596938343, 1686397275, 52708329, 230996593, 3597201983, 378926364, 3618422671, 2062721049, 3659976071, 546629459, 3976307656, 1509609055, 3677736141, 1613243397, 1378877471, 531534610, 2602178644, 4099876535, 1394187732, 1706260244, 1842911215, 3381571710, 456693813, 1667668257, 792813840, 4044011316, 1391972141, 1677638507, 1467741933, 2542725716, 3261642613, 1122181516, 1726857655, 2765884383, 2563231823, 1890137479, 3462591813, 290505918, 3480784421, 4146013364, 906268950, 1460571462, 625398701, 1868955581, 2562420879, 3524561573, 2480663847, 424010572, 3760440358, 506451740, 2616205788, 3835513223, 2698078113, 933669512, 2259175222, 1766445936, 3062774434, 3383207496, 165724374, 717679250, 872303977, 1054921507, 1640987195, 2398705310, 744526846, 2142916476, 3769314780, 3643489144, 906983325, 1001096018, 1522376663, 3516789445, 425379249, 1807654888, 1584889396, 996500676, 2138028000, 1877118731, 2780715755, 56317932, 994780643, 231703463, 1590924826, 449553992, 1970334362, 3631415563, 2378887069, 2645995105, 604040985, 766274135, 2897107084, 3122401328, 604584226, 3514594183, 3159592392, 539086862, 1966827756, 1548312674, 2223920152, 4193868755, 2604831097, 2301554299, 2919432501, 3445772747, 221908018, 1919849944, 1707243688, 1311680342, 1132835813, 824121832, 2623654824, 4245764621, 1669541543, 793028119, 1400611299, 2330555992, 1295319061, 2376883177, 3054784982, 1534527889, 3381065612, 431181624, 2520679460, 1612115175, 3417053178, 3202101207, 4112825474, 209873225, 3982289256, 3175605361, 1007754107, 1533969733, 3657972615, 1233249703, 1775877579, 2812100730, 3215107528, 1781386145, 3025989255, 3066346118, 3283795978, 1197222174, 2936543382, 3503535134, 2892598771, 2621962168, 931511531, 2231087188, 4146539078, 4002087507, 2491835423, 4060649251, 4048333160, 2444738719, 2691519303, 1556526141, 3615497232, 4050826531, 500299044, 717467546, 2206683369, 861398548, 3151369905, 4029791836, 3416545629, 4120104600, 1465267912, 483234533, 3035820989, 3832933168, 3568690105, 96174302, 2545526712, 1102861924, 1074783639, 4182941480, 1533353222, 1488829617, 1503690984, 185887778, 4211993208, 2290188486, 1146083769, 2041769341, 2684027677, 3176900642, 1387338494, 946259368, 1066487432, 795876682, 3861793354, 1668825820, 216618949, 2896083408, 3851619025, 442276681, 206355214, 270139248, 347366931, 1910792165, 3953458832, 2734158556, 2811136264, 1920172269, 1837836373, 3778467275, 3779230355, 3897121172, 2344011383, 1146522764, 2190434845, 609244986, 2013714652, 560173192, 2402932255, 1072869170, 1770725561, 952360909, 1412825165, 3696544236, 2306376326, 2830983153, 207976619, 4155556879, 3728896627, 2654370117, 3334033001, 1365410137, 1493856098, 1253593280, 1631830970, 5803336, 3918597809, 86127041, 333464839, 3604499396, 149662371, 2129288705, 1461710188, 3760680120, 3729872359, 2100765881, 3535556758, 444301423, 2716178967, 1126522126, 4087265377, 129975151, 3676574817, 946781552, 1144144314, 4160587561, 3992786314, 45372372, 2839307265, 3121990915, 2417091275, 2394722122, 2336989436, 3126674182, 3231554964, 3785353831, 3066121066, 4059908701, 3257600631, 3304564137, 976977941, 2994176851, 3509885563, 436168092, 2194926470, 572263581, 2964578564, 2577729800, 4257414592, 1074783671, 2629434251, 42822614, 1475322010, 3068645543, 3694724738, 3480058324, 4204711804, 3168448984, 2767935672, 3016152818, 4134435775, 2141315517, 2182008981, 2871864678, 2294299758, 1409773258, 3418660825, 3090287076, 3241139267, 2315623533, 2157788904, 334169841, 2062298350, 4075844652, 1672438569, 2994084656, 2204498767, 2430183901, 4179388667, 317027997, 2894184457, 3635887387, 1307832846, 3358657065, 734371454, 610520453, 3421706671, 3240587498, 3690351924, 935152653, 2737123774, 203357945, 1027962332, 3777141639, 743025036, 4046422672, 1085389282, 110265143, 320421926, 1931570193, 936595461, 2927488848, 2265674314, 3444945553, 786566925, 4133145648, 2879270131, 4165751769, 3985446237, 1971125873, 3724681025, 2661325531, 2441664181, 3290805620, 2459158763, 2102811157, 2881160687, 1153639082, 827213914, 3028527431, 2205345684, 3556675715, 1279123065, 4253124398, 3483559979, 4068430995, 4141206587, 2571521727, 2944439402, 443124686, 2268164570, 2235451426, 3679071975, 3129207272, 2516367556, 1468462786, 1881517367, 3491042253, 2913831047, 3164481275, 202602034, 3150723817, 1533130707, 1912730441, 2090267514, 3558123575, 1133228007, 3421482977, 2553693497, 3421969717, 2520271965, 2067324870, 1223636150, 2714495378, 3773685424, 2961634881, 88882886, 408668635, 904339271, 3187997208, 2883270961, 1911371885, 1111177434, 3677904221, 1424566197, 456428662, 3160502725, 2571618126, 1931038165, 1229862345, 885692642, 928907436, 281108918, 2025639202, 4098934983, 245166619, 3978368942, 2335134348, 2663736265, 3483476476, 1019177183, 1076843627, 2150626843, 3549898506, 497411044, 2948681730, 1293862520, 3364439483, 200913955, 876046583, 2810673955, 2828391839, 1905062360, 3783182365, 2472665728, 1439731349, 2736703148, 3316496080, 2996051367, 448455111, 3808598160, 2313472828, 1619655346, 1198200314, 3744504057, 1680713197, 2474661491, 3214410863, 1662774943, 3537885099, 3365412658, 3583677483]

因为我会用的随机数预测的板子来自这篇文章

所以我利用下面这个代码，把19968bit，拆分成了624个32bit的值

from random import Random
prng = Random()
state = []

prng.setstate((3, tuple(state + [0]), None))
D = [prng.getrandbits(32) for _ in range(624)]
print(D)
"""
[3086615663, 3771906507, 1933791567, 874400704, 4000928288, 1101512046, 3757205682, 895930285, 2975657910, 1590250704, 227397937, 3163700038, 1702493296, 86408336, 1317214060, 355017934, 4281601498, 2958424486, 3248821687, 1977038961, 75767861, 1848107476, 1201089736, 1669521311, 3079560731, 753259725, 2783047520, 1792692953, 1335325755, 4118154638, 221587457, 3931660158, 2105971738, 205787269, 3306213190, 3047766446, 757659831, 70863674, 2054184739, 418281550, 2654142751, 3195128907, 3920550815, 273337573, 856860348, 2332777112, 1144893468, 4097373151, 2348453877, 3391728911, 1909111864, 1167657184, 1690201897, 3037596190, 2683689827, 2591985588, 483396539, 583852871, 4213595783, 3297463098, 3940471284, 3167491933, 3836764654, 385184073, 4089593895, 2435556034, 2689611721, 3009515703, 2557788155, 742759035, 2911234764, 2747466359, 1658388676, 77325257, 1282826102, 833518584, 258773596, 1252680510, 2161330425, 1505524757, 1106189058, 2479195181, 4059279758, 4087261637, 2802856115, 215936888, 385734300, 3976823712, 2155716808, 166878602, 2958581226, 2153643018, 3459229793, 166654981, 1135752470, 2999716815, 102870168, 3592405002, 143561712, 3332529987, 3320611547, 176304087, 3809410875, 956905158, 3283895217, 1267764884, 1781613649, 2648889013, 4023857409, 2805378741, 2649655508, 2608225929, 2196639843, 2844902511, 1947381383, 133311662, 3189375534, 3360781939, 2598704112, 449730728, 1660136746, 2120362421, 4282918442, 553031705, 2359175283, 1820194402, 3326941501, 2079373053, 3848840564, 674418166, 2099289575, 3503720323, 71654499, 1153326313, 560391397, 987219237, 3519108661, 343772283, 2206155982, 1710469128, 4284016382, 1099544658, 2385903806, 435889661, 1754514095, 1654595795, 2611465271, 2924309399, 3849122741, 2771388572, 132443906, 639488960, 1702455392, 1197499823, 3431742381, 1162507747, 1956793904, 2882150352, 1024607141, 573195509, 4026654414, 2622992078, 3350586931, 3799382718, 189653578, 2030853706, 2360599919, 1447670146, 3029293260, 449492231, 794537698, 2013929440, 2521582617, 3662902133, 2988382934, 1101429406, 2204422539, 2884223003, 4160719615, 378925199, 321253023, 713869660, 1722066591, 4190495614, 3241838993, 3156104799, 3976107465, 690141471, 2565083608, 629627271, 3367902606, 3025623735, 1771459709, 2325207656, 29331249, 1631496960, 1272596234, 677116176, 36223230, 1894006200, 1868323656, 147662067, 3018282350, 847618418, 473803624, 303813116, 1222076488, 2857631548, 1620440323, 3028453586, 3771115277, 974948581, 2805463577, 3012869721, 1677541868, 873746956, 3206333732, 3540196648, 4222297189, 3955666095, 3723668809, 3383181896, 1572023031, 3593767211, 4139994756, 2493637240, 1055398974, 3491895839, 2158774748, 4074778554, 2265454243, 3123246270, 3737495019, 3584208536, 505004504, 711346815, 2265659930, 44813444, 762261590, 2345302575, 3635851795, 2255282129, 3598634106, 921749760, 1418440684, 3784150188, 2393915660, 2720478000, 1612782044, 4147046015, 2561634247, 586916363, 1606384598, 1299844033, 4047608483, 3431257347, 781242816, 3127114595, 1484369015, 483654543, 678493767, 2757899632, 3276695749, 1363370762, 1578035875, 555054787, 3093962781, 2222987767, 2130200534, 2053306276, 3948690640, 3249023873, 2343777324, 2833997966, 44199340, 1950451402, 1448991312, 1055067146, 3980624341, 1812874122, 2512418377, 3541037815, 714180005, 987816438, 3414079245, 1619142872, 4122595525, 3638144912, 3337941608, 2664929972, 1577036940, 206102296, 2850863132, 3729200403, 644729416, 844182047, 2261919397, 1040614315, 1776485562, 677708826, 223842114, 2591956969, 3141458682, 4271489476, 4253854271, 3973860423, 2805984925, 2908508806, 2328769351, 3865140, 4170270812, 1373888554, 1702101960, 3761095439, 3848481069, 812779025, 2073985983, 239315333, 1585392927, 2233774162, 2308108952, 3393306946, 2891660426, 1059096016, 2448311649, 2662483261, 422228248, 2356192519, 4004741305, 432651290, 2419877069, 3136967672, 329338548, 510605497, 2753410852, 2256462380, 3602678268, 2558451886, 324326056, 3822050324, 944965241, 4107093336, 1023337388, 564298141, 2977064774, 1802025909, 2329346614, 1460784428, 2510641562, 593994802, 4034614216, 4154528137, 3061249939, 487067285, 2856327155, 1909407614, 1782934804, 947220403, 2311402749, 3528590202, 2841893555, 3179384475, 3485733076, 87074890, 753396673, 790057962, 378850528, 3789224576, 3983502105, 1166116, 1854075229, 965611444, 3399039227, 3301304385, 3499808775, 1553588463, 2562124078, 3702675704, 1456114141, 768418804, 2227423616, 3711148950, 2738970313, 4033988307, 1184409529, 3461105405, 2986057969, 2112332635, 615658869, 2858394250, 2819269426, 499315937, 1714425168, 3816439521, 4188657733, 1226314395, 773286132, 1257824142, 2439511774, 1412431345, 451028253, 102711904, 3272107935, 1915128127, 674941443, 1907183006, 4205826365, 2592631544, 2001660887, 1793337902, 336832953, 1676534641, 439197643, 2175306211, 1969440247, 4084563735, 564896680, 1293717918, 1136684128, 4289259757, 2368216261, 3167549822, 1998645278, 2908859410, 2014400533, 1482521794, 3082876093, 2742987778, 3273667028, 1654313273, 3551772744, 1923315597, 1063687791, 1907747434, 3323400678, 3445870975, 316314436, 3905619499, 853586576, 456263058, 3213830894, 3603099146, 1478599807, 344267130, 1085971878, 2416474796, 247701271, 2926294528, 1981779524, 3809025846, 2106937971, 1596271124, 1289668306, 1824884242, 543613169, 2698011204, 1632632104, 179981234, 1091171130, 608067622, 4034608897, 2707671187, 2261524231, 2177175178, 1649366013, 733151281, 2783115482, 389580085, 495962438, 512715565, 1917819840, 1993385884, 2910358830, 3223741704, 3302008571, 857474180, 143995596, 3194737469, 2792999636, 111369357, 2665449999, 3481184513, 21965724, 172308864, 3373225896, 3941204120, 1487487599, 2697473345, 4173199839, 1988623177, 3567610975, 2393053467, 2231132558, 3798877543, 4275987399, 3626515970, 3957758644, 3196139612, 1577858639, 4145376193, 3982712357, 1316354617, 2476570111, 2796635786, 3673095113, 317782376, 38302891, 2729549772, 3124741082, 779634809, 480059945, 1764557943, 1905762442, 2439926326, 3398546304, 1275206055, 3578388510, 4286589961, 2284154687, 1547652572, 211218778, 4019993609, 1035325551, 47385212, 1413260320, 1895132671, 2144191841, 976730195, 880818479, 2944522030, 3051883625, 941172532, 1956827360, 604038865, 1490554868, 2014326554, 3585424155, 1705580179, 1484996770, 3145161387, 2410763156, 1196196268, 4125882510, 1569631240, 3635487118, 3743075539, 53348120, 3549050110, 2179975673, 1455493727, 909517499, 2034744814, 1815931219, 2625466993, 2328144852, 3083176966, 4185591290, 4232725936, 233807337, 987553443, 25498384, 1577858645, 3349985471, 222166290, 1566719496, 4025597331, 454410574, 4172717618, 3397690720, 1563985388, 1294197484, 454917824, 250364909, 1076318659, 3751354075, 3324840413, 2834288682, 1309780963, 3789459740, 1605544538, 1448439145, 1158482892, 407656226, 3589982226, 2670402128, 2795218845, 4079499284, 2736737218, 468906864, 347349067, 3541605667, 1532233501, 1192558327, 3650037602, 1570092544, 3596826230, 2768927258, 1775543901, 1324819997, 3401066173, 4078892370, 3373389918, 3360817112, 3261261117, 2443241006, 847292772, 3862028592, 4086319712, 1837673494, 3577160747, 2636413549, 4021668342, 573747407, 3546255858, 2787607684, 403421850, 3477281082, 4133820736, 332805644, 3663845239, 80993494, 344033777, 1187319040, 1547969768]
"""

然后就可以回推随机数，此时需要注意random.randbytes()的产生方式:

def randbytes(self, n):
    """Generate n random bytes."""
    return self.getrandbits(n * 8).to_bytes(n, 'little')

接下来，我们只需要回推一个16 * 8bit的随机数，再转为字节即可

exp.py

from Crypto.Cipher import AES
from extend_mt19937_predictor import ExtendMT19937Predictor

predictor = ExtendMT19937Predictor()

D = []

for _ in range(624):
    predictor.setrandbits(D[_], 32)

for i in range(624):
    predictor.backtrack_getrandbits(32)

key = predictor.backtrack_getrandbits(16 * 8).to_bytes(16, 'little')
cipher = AES.new(key,AES.MODE_ECB)
c =  b'a\x93\xdc\xc3\x90\x0cK\xfa\xfb\x1c\x05$y\x16:\xfc\xf3+\xf8+%\xfe\xf9\x86\xa3\x17i+ab\xca\xb6\xcd\r\xa5\x94\xeaVM\xdeo\xa7\xdf\xa9D\n\x02\xa3'
flag = cipher.decrypt(c)
print(flag)
# WKCTF{3f2af637b773613c18d27694f20d98fd}

Meet me in the summer——复现

task.py

from random import choice, randint
from Crypto.Util.number import isPrime, sieve_base as primes, getPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5

flag = b'WKCTF{}'
flag = pad(flag,16)
def myPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

def encrypt(key, message):
    return pow(65537, message, key)

p = myPrime(512)
q = getPrime(512)
N = p * q
m = [getPrime(512) for i in range(1024)]
enc = [encrypt(N, _) for _ in m]

a = [randint(1,2 ** 50) for i in range(70)]
b = [randint(1,2 ** 50) for i in range(50)]
secret = randint(2**119, 2**120)

ra = 1
rb = 1
for i in range(120):
    if(i < 70):
        if (secret >> i) & 1:
            ra *= a[i]
            ra %= p
    else:
        if (secret >> i) & 1:
            rb *= b[i-70]
            rb %= q


key = md5(str(secret).encode()).hexdigest()[16:].encode()
cipher = AES.new(key,AES.MODE_ECB)

with open("output.txt","w") as f:
    f.write(f'c = {cipher.encrypt(flag).hex()}\n')
    f.write(f'm = {m}\n')
    f.write(f'enc = {enc}\n')
    f.write(f'a = {a}\n')
    f.write(f'b = {b}\n')
    f.write(f'ra = {ra}\n')
    f.write(f'rb = {rb}\n')

求N

先求N
$$
\because enc_i \equiv 65537^{m_i} \mod N
$$
我们可以尝试寻找一组$a_1,a_2,…,a_n$，使得$a_1m_1 + a_2m_2 + …+a_nm_n = 0$

则$\prod_{i=1}^{n}enc_i^{a_i} = 65537^{a_1m_1 + a_2m_2 +…+.a_nm_n} \equiv 65537^0 \mod N$

找出两组这样的$a_1,a_2,…,a_n$再求公因数就可以得到N

接下来就是造格找出这样的向量
$$
\begin{pmatrix}
a_1 & a_2 & … & a_n
\end{pmatrix}
\begin{pmatrix}
1 & 0 & … & 0 & m_1\\
0 & 1 & … & 0 & m_2\\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & … & 1 & m_n
\end{pmatrix}
=
\begin{pmatrix}
a_1 & a_2 & … & a_n & 0
\end{pmatrix}
$$

f = open("output.txt",'r').readlines()
m = eval(f[1].strip().split("=")[-1])
enc = eval(f[2].strip().split("=")[-1])

m = m[:100]
enc = enc[:100]
# 感觉不需要全部数据，随便取点数据试试能不能出

n = len(m)
Ge = Matrix(ZZ,n,n+1)
K = 2^200
for i in range(n):
    Ge[i,i] = 1
    Ge[i,-1] = K*m[i]

L = Ge.LLL()
xx = product([ZZ(y) ^ x for x, y in zip(L[0][:-1], enc)])
yy = product([ZZ(y) ^ x for x, y in zip(L[1][:-1], enc)])
N = gcd(xx.numer() - xx.denom(), yy.numer() - yy.denom())
print(N)

求出N之后，因为p-1光滑，很容易分解出p,q

import gmpy2 

N = 3365950545896839807600753681439061096312578337873460615427103468443333055935222147455641892341798604350037357999848711970084367398055755047567367304166808830853176966914407772226194410114093800191521813038405295729046243670270181161836427221727870133145321390846488824416000038564306005700271206427983462394735137
def smooth(N):
    a = 2
    n = 2
    while True:
        a = pow(a, n, N)
        res = gmpy2.gcd(a - 1, N)
        if res != 1 and res != N:
            return res
        n += 1

p = smooth(N)
q = N // p
print(f"p = {p}")
print(f"q = {q}")
"""
p = 266239931579101788237217833822346198682539336616234011732898866661722928035386747695230192006141430294833011494452114878744414084025005167432139516382471637567
q = 12642545864299817932696528548195775137854645688987690739317393212595731628016420449974358672452504599152386464349500792607469701592216257829464295238775711

"""

接下来我们把secret分为两段，第一段是低70位，第二段是高50位

求secret的低位

先处理第一段，有
$$
ra\equiv a_0k_{70}\times a_1k_{69} \times …\times a_{69}k_1 \mod p
$$
$k_i$表示第一段的第i位，需要注意的是当$k_i = 0$的时候是不需要乘进来的，这里只是写成这样。

因为$p-1$光滑，我们考虑把这个式子变成一个求解离散对数的问题，这样才能利用上$p-1$光滑

我们随便取一个生成元g，然后对等式两边取对数，要注意的是，取对数之后模数应该变成p-1
$$
\log_{g}{ra} \equiv \log_{g}{a_0k_{70}} + \log_{g}{a_1k_{69}} + … + \log_{g}{a_{69}k_1} \mod p - 1
$$
对于这个式子，当$k_i = 1$的时候，$log_g^{a_ik_i} = log_g^{a_i}$，刚刚前面说了$k_i =0$的时候是不需要乘进来的，那这个取离散对数后的式子里面只包括了$k_i = 1$的情况。

因此我们有
$$
\log_{g}{ra} \equiv \log_{g}{a_0} + \log_{g}{a_1} + … + \log_{g}{a_{69}} \mod p - 1
$$
这样就可以写为加法背包了

造格
$$
\begin{pmatrix}
k_{70} & k_{69} & … & k_{1} & 1 & l
\end{pmatrix}
\begin{pmatrix}
1 & 0 & … & 0 & 0 & \log_{g}{a_0}\\
0 & 1 & … & 0 & 0 & \log_{g}{a_1}\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & … & 1 & 0 & \log_{g}{a_{69}}\\
0 & 0 & … & 0 & 1 & \log_{g}{ra}\\
0 & 0 & … & 0 & 0 & p - 1
\end{pmatrix}
=
\begin{pmatrix}
k_{70} & k_{69} & … & k_1 & 1 & 0
\end{pmatrix}
$$

这个格没出，进行优化，造下面这个格
$$
\begin{pmatrix}
k_{70} & k_{69} & … & k_{1} & l & -1
\end{pmatrix}
\begin{pmatrix}
2 & 0 & … & 0 & 0 & \log_{g}{a_0}\\
0 & 2 & … & 0 & 0 & \log_{g}{a_1}\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & … & 2 & 0 & \log_{g}{a_{69}}\\
0 & 0 & … & 0 & 1 & p - 1\\
1 & 1 & … & 1 & 1 & \log_{g}{ra}
\end{pmatrix}
=
\begin{pmatrix}
k_{70}-1 & k_{69}-1 & … & k_1-1 & l-1 & 0
\end{pmatrix}
$$

a = [810922431519561, 446272766988725, 167807402211751, 137130339017755, 214986582563833, 141074297736993, 1116944910925939, 827779449967114, 887541522977945, 698795918391810, 180874459256817, 42309568567278, 148563974468327, 43541894027392, 369461465628947, 226728238060977, 902554563386031, 369980733296039, 495826170604031, 202556971656774, 1124261777691439, 533425503636189, 393536945515725, 242107802161603, 506637008093239, 846292038115984, 686372167052341, 923093823276073, 557898577262848, 719859369760663, 51513645433906, 946714837276014, 24336055796632, 302053499607130, 970564601798660, 1082742759743394, 499339281736843, 13407991387893, 667336471542364, 38809146657917, 29069472887681, 420834834946561, 1044601747029985, 854268790341671, 918316968972873, 737863884666895, 1036231016223653, 792781009835942, 142149344663288, 828341073371968, 186470549619656, 279923049419811, 487848895651491, 737257307326881, 1065005635075133, 628186519179693, 554767859759026, 606623194910240, 497855707815081, 88176594691403, 278020899501967, 440746393631841, 921270589876795, 800698974218498, 437669423813782, 717945417305277, 191204872168085, 791101652791845, 772875127585562, 174750251898037]
ra = 215843182933318975496532456029939484729806294336845406882490936458079210569046120528327121994744424727894554328344229010979127024288283698486557728305231262446
p = 266239931579101788237217833822346198682539336616234011732898866661722928035386747695230192006141430294833011494452114878744414084025005167432139516382471637567

g = 5
tmp = discrete_log(mod(ra,p),mod(g,p))

n = len(a)
A = [discrete_log(mod(a[i],p),mod(g,p)) for i in range(n)]

d = n / log(max(A), 2)
print(CDF(d))

Ge = Matrix(ZZ,n+2,n+2)
for i in range(n):
    Ge[i,i] = 2
    Ge[i,-1] = A[i]
    Ge[-1,i] = 1
    
Ge[-2,-2] = 1
Ge[-2,-1] = p - 1
Ge[-1,-1] = tmp
Ge[-1,-2] = 1
Ge[:,-1] *= 2^200

for line in Ge.BKZ(block_size = 26):
    if line[-1] == 0:
        t = ""
        for i in line[:-2]:
            if i == 1:
                t += "0"        # or 1
            if i == -1:
                t += "1"        # or 0 这两个来回换一下即可
    if len(t) == 70:
        print(t[::-1])
        break
        # 1100100011000011000001010101000010111110000001000010101010100100011011

此时得到secret的低位为1100100011000011000001010101000010111110000001000010101010100100011011

求secret的高位

处理第二段，有
$$
\because rb \equiv b_0k_{50}\times b_1k_{49}\times …\times b_{49}k_1 \mod q
$$
$k_i$表示第二段的第i位，接下来我们采用中间相遇攻击

记$t_1 \equiv b_0k_{50}\times b_1k_{49}\times …\times b_{24}k_{26}\mod q$

记$t_2 \equiv b_{25}k_{25}\times b_{26}k_{24}\times …\times b_{49}k_{50} \mod q$

那么此时$rb \equiv t_1\times t_2 \mod q$

我们计算$rb \times t_2^{-1}$，看它是否满足$rb \times t_2^{-1} \equiv t_1 \mod q$

from tqdm import *
from Crypto.Util.number import *

q = 12642545864299817932696528548195775137854645688987690739317393212595731628016420449974358672452504599152386464349500792607469701592216257829464295238775711
rb = 3498090364718786308911989083689617571932166777012900779070629523727655934582351599924963383902292211754876835801399401170701861988033911802302715724060488
b = [919042075929804, 731196114348957, 780418394368709, 3413259132589, 766847233992470, 297211103941610, 500281126810865, 849501916345269, 117720599611510, 551153334471840, 1072866601658568, 829727438821072, 179087882377496, 934984220634910, 670865352770561, 153859069714096, 600663927005680, 540242857915696, 553340712407662, 1113968197194611, 272342861356660, 1117828067970844, 796048575670909, 454054034318932, 654225458148223, 183717820875099, 1064983259059879, 737236143792316, 565414872646761, 550812923748544, 467970413493147, 764197477914194, 572611266860917, 74578187275404, 462057895458922, 594841925406302, 178813973628003, 607180532395162, 455598995678785, 227757559710253, 178207804255926, 982118016357442, 286821935441865, 947088152152874, 592190023483880, 686189038585889, 701809424042029, 610206451919836, 189925081438758, 108664403267133]

dict = {}
for tmp in trange(2**24,2**25):
    t1 = 1
    for i in range(25):
        if (tmp >> i) & 1:
            t1 *= b[i]
            t1 %= q
    dict[t1] = tmp
    
for tmp in trange(2**24,2**25):
    t2 = 1
    for i in range(25):
        if (tmp >> i) & 1:
            t2 *= b[i + 25]
            t2 %= q
    t = rb * inverse(t2,q) % q
    if t in dict.keys():
        print(f"低25位是:{bin(dict[t])[2:]}")
        print(f"高25位是:{bin(tmp)[2:]}")
        break
        # 1011111010011011011100010
        # 1100010001001011111001111
        # 11000100010010111110011111011111010011011011100010

此时我们得到了secret的高50位为11000100010010111110011111011111010011011011100010

解AES

最后拼接即可

from Crypto.Cipher import AES
from hashlib import md5

high = "11000100010010111110011111011111010011011011100010"
low = "1100100011000011000001010101000010111110000001000010101010100100011011"
secret = int(high + low,2)
print(secret)

c = "dc6ba0123102f13a60ec4488d917a53a3c9b61372f39b977e93027fcb735eac38ceea2c0a7d5d6baf3570eea05200ce0"
key = md5(str(secret).encode()).hexdigest()[16:].encode()
cipher = AES.new(key,AES.MODE_ECB)
flag = cipher.decrypt(bytes.fromhex(c))

print(flag)
# WKCTF{Hell0_CTFer_Th1s_the_5ignin_fl4g.}

FaaS——Unsolved

task.py

from Crypto.Util.number import *

flag = b''
p = getPrime(256)
q = getPrime(256)
n = p*q
e = 0x10001
# print(p,q)
print(n)
print(pow(bytes_to_long(flag), e, n))

'''
6307087428677736357497034459737970959152896262793715778296915427469297166787112126441383726582076126245773277476143478349256813717514008533538716513810511
5311161002667378270287698542067235931405307317925963294522517859778084164120335331513838215353575415471218414362372788855224259598970138214133452539914210
'''

用yafu挂了半天没结果，猜测应该是基于某篇论文，或者真的用超算？