2020 CISCN部分WP

2023-10-24 08:41:04

写在前面：菜鸡记录下自己做出来的几道题

(顺便试试CSDN发博客）

文章目录

写在前面：菜鸡记录下自己做出来的几道题

初赛

0x01 ctf_game

从文件里直接提取出flag字样即可（也可以写脚本

flag{65e02f26-0d6e-463f-bc63-2df733e47fbe}

0x02 bd

题目

from secret import flag
from Crypto.Util.number import *

m = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p-1) * (q-1)
while True:
    d = getRandomNBitInteger(200)
    if GCD(d, phi) == 1:
        e = inverse(d, phi)
        break

c = pow(m, e, N)

print(c, e, N, sep='\n')

# 37625098109081701774571613785279343908814425141123915351527903477451570893536663171806089364574293449414561630485312247061686191366669404389142347972565020570877175992098033759403318443705791866939363061966538210758611679849037990315161035649389943256526167843576617469134413191950908582922902210791377220066
# 46867417013414476511855705167486515292101865210840925173161828985833867821644239088991107524584028941183216735115986313719966458608881689802377181633111389920813814350964315420422257050287517851213109465823444767895817372377616723406116946259672358254060231210263961445286931270444042869857616609048537240249
# 86966590627372918010571457840724456774194080910694231109811773050866217415975647358784246153710824794652840306389428729923771431340699346354646708396564203957270393882105042714920060055401541794748437242707186192941546185666953574082803056612193004258064074902605834799171191314001030749992715155125694272289

题目给出了 n,e,c 发现 e 比较大，想到rsa-wiener-attack破解 d，尝试后成功，脚本如下:

from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import ContinuedFractions, Arithmetic
c=37625098109081701774571613785279343908814425141123915351527903477451570893536663171806089364574293449414561630485312247061686191366669404389142347972565020570877175992098033759403318443705791866939363061966538210758611679849037990315161035649389943256526167843576617469134413191950908582922902210791377220066
e=46867417013414476511855705167486515292101865210840925173161828985833867821644239088991107524584028941183216735115986313719966458608881689802377181633111389920813814350964315420422257050287517851213109465823444767895817372377616723406116946259672358254060231210263961445286931270444042869857616609048537240249
n=86966590627372918010571457840724456774194080910694231109811773050866217415975647358784246153710824794652840306389428729923771431340699346354646708396564203957270393882105042714920060055401541794748437242707186192941546185666953574082803056612193004258064074902605834799171191314001030749992715155125694272289
# firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !
def wiener_hack(e, n):
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    for (k, d) in convergents:
        if k != 0 and (e * d - 1) % k == 0:
            phi = (e * d - 1) // k
            s = n - phi + 1
            discr = s * s - 4 * n
            if (discr >= 0):
                t = Arithmetic.is_perfect_square(discr)
                if t != -1 and (s + t) % 2 == 0:
                    print("Hacked!")
                    return d
    return False
d = wiener_hack(e, n)
print(d)
m=pow(c,d,n)
flag=long_to_bytes(m)
print(flag)

flag{d3752538-90d0-c373-cfef-9247d3e16848}

0x03 lfsr

第一次接触这个题，查了下发现是线性反馈移位寄存器相关，本题将flag设为mask，即要求mask，原题目如下：

# -*- coding: cp936 -*-
import random

from secret import flag

N = 100
MASK = 2**(N+1) - 1

def lfsr(state, mask):
    feedback = state & mask
    feed_bit = bin(feedback)[2:].count("1") & 1 
    output_bit = state & 1 
    state = (state >> 1) | (feed_bit << (N-1)) 
    return state, output_bit

def main():
    assert flag.startswith("flag{")
    assert flag.endswith("}")

    mask = int(flag[5:-1]) #mask flag 100位
    assert mask.bit_length() == N
    
    state  = random.randint(0, MASK) 
    print(state)
    
    outputs = ''
    for _ in range(N**2):
        state, output_bit = lfsr(state, mask)
        outputs += str(output_bit)
    
    with open("output.txt", "w") as f:
        f.write(outputs)

main()

（在师兄帮助下）找到 de1ctf 原题 https://ruanx.net/babylfsr/
只有左移和右移区别，state 需要逆序，数据取前 200 位修改脚本如下：

# -*- coding: utf-8 -*-
#sage脚本
#out = open('output.txt','r').read()
#f=out[:200]
f=01001100111011110111110110101001110010100101000011111101101111010111100111110100100101110111001101110110011000010100100111011010001101100000111110111100000101000010010000110010110110110110011111101011
print(f)
s=[int(x)for x in f]
M = matrix(GF(2), 100, 100)
T = vector(GF(2), 100)

for i in range(100):
    M[i] = (s[i : i + 100])[::-1] #state
    T[i] = s[i+100]
try:
    mask = M.inverse() * T
    print('flag{'+str(int(''.join(map(str, (mask))), base=2))+'}')
except Exception as e:
    print(e)
#flag{856137228707110492246853478448}
#sage cell server

在线sage脚本 https://sagecell.sagemath.org/

0x04 rsa

这道题没给什么条件，n也分解不出来…最后无解

n = 50142032499469550407421604706771611415193641755639270667473328045908799316205905505167271138079522738272643811917325451177986948493659090203974349370248583120022500722759239305447823602875823849366662503027591858371125301505134216095903796534740686834236150999
e = 65537
c = 45005399504992587510006608300548120810512973768886391125598523343330913326304417790989607300367232977960116381108873363343598357102136548218343380795022179607741940866191404186680657699739176842869814452906110393321567314747096161480003824583613027819960172221

11.9日更新

在整理博客时突然想到可能已经有人分解过了，在在线分解网站试了下，还真的成功了，是三个比较接近的素数相乘，分解出来就是常规的RSA求解了:

from Crypto.Util.number import *
from gmpy2 import *
n = 50142032499469550407421604706771611415193641755639270667473328045908799316205905505167271138079522738272643811917325451177986948493659090203974349370248583120022500722759239305447823602875823849366662503027591858371125301505134216095903796534740686834236150999
e = 65537
c = 45005399504992587510006608300548120810512973768886391125598523343330913326304417790989607300367232977960116381108873363343598357102136548218343380795022179607741940866191404186680657699739176842869814452906110393321567314747096161480003824583613027819960172221

p = 368751654879714877087975516875168751974879716873087714877516875971487715687516888458327
q = 368751654879714877087975516875168751974879716873087714877516875971487715687518277898523
r = 368751654879714877087975516875168751974879716873087714877516875971487715687518438089619
assert p*q*r == n
phi = (p-1)*(q-1)*(r-1)
d = invert(e,phi)
#print(d)
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)

flag{4e9f2a7f-bda9-4a46-af51-b29e0c61973e}

华南赛区晋级赛

ps.这次严格的要求需要队伍集中在统一环境，双机位监控等等，第一次这样体验回忆起宛如在家的期末考试；
师兄们拿了第一tql，不过自己也搞出了几题…

0X01 三年之期

一道偏脑洞题，源码如下：

import time as tm
import random as rd
from Crypto.Util.number import str2long
n = 20314136991489778708489418870071113306321126239354250215752297094907603867181
rd.seed(int(tm.time()))
e = rd.randint(12450, 1145141919810)
with open('flag.txt') as r:
    flag = r.readline()
c = pow(str2long(flag), e, n)
print(c)
'''
c = 9677463901939068132601817954384243432821268637875771855241656639633275682765
'''

开始研究了下，思路还算清晰，通过tm.time()函数获取了种子值，然后e其实就定了，即可求解；
一开始没懂time()函数的原理，通过给的附件提示就乱猜了下种子值，后来发现是根据本地时间获得值,具体解释是：

time() 是指返回自 Unix 纪元（January 1 1970 00:00:00 GMT）起的当前时间的秒数的函数，主要用来获取当前的系统时间。

于是反应过来附件提示是给出了一个时间点：2020年5月27日下午3时4分有余；因而修改系统时间，获取该时间点附近的种子值求得e值，脚本如下：

import time as tm
import random as rd
from Crypto.Util.number import *
from gmpy2 import *
n = 20314136991489778708489418870071113306321126239354250215752297094907603867181
c = 9677463901939068132601817954384243432821268637875771855241656639633275682765
p = 91878423570644433705107636207019552241
q = 221098014115037952387250830957848633341
phi =(p-1)*(q-1)
for i in range(1590563000,1590563100):
    rd.seed(i)
    e = rd.randint(12450, 1145141919810)
    #e=1142573861267
    if(gcd(e,phi)==1):
        d = invert(e,phi)
        m = pow(c,d,n)
        flag=long_to_bytes(m)
        if(flag[:4]=='flag'):
            print("i="+str(i))
            print("e="+str(e))
            print(long_to_bytes(m))

flag{fake_crypto_real_time}

0x02 paillier

通过题目描述可以获得提示，是同态加密相关,首先分解n获得p,q，再写解密脚本获得flag (其实是DASCTF原题
https://www.anquanke.com/post/id/204720 这个写的挺好的

from Crypto.Util.number import *
c=3808740243451829078210724960912929301578515217667342177748504822876637487457955515274108053834689975926677363518389793704175328503134131135222019673109070160582400165248020145405704970220361687652902588280756668081550609197401147259204898810928417434170277979905559815094009996366760441244275219995751156342
n=10999687930887680707038926445934606154952916940968581490041059775550485116500433363190163190149269018664612556276327671880157597616757778207737495630969441
p=104879397075344024438671231239628115011303349344697797964879592144922079001013
q=104879397075344024438671231239628115011303349344697797964879592144922079000957
phi=(p-1)*(q-1)
print(p*q==n)
tmp=inverse(phi,n*n)
def L(x,n):
    return (x-1)/n
m=(L(pow(c,phi,n**2),n)*tmp)% n
flag=long_to_bytes(m)
print(flag)

flag{p4ill1er_1s_simp13_6ut_fun0y}

0x03 easyRSA2

通过观察发现R值在一定范围内随机生成且有限定条件，通过脚本爆破出R值再生成p,q满足p*q==N即可（爆破需要点技巧，也有点运气）

from Crypto.Util.number import *
from gmpy2 import *
from random import randint
def lfsr(R, mask):
    out = (R << 1) & 0xffffff
    bit = (R & mask) & 0xffffff
    out_bit = 0
    while bit != 0:
        out_bit ^= (bit & 1)
        bit = bit >> 1
    out ^= out_bit
    return out, out_bit
def genPrime(R, mask, bit):
    count = 0
    while True:
        prime = 0
        for i in range(bit):
            (R, out) = lfsr(R, mask)
            prime = (prime << 1) ^ out
        if isPrime(prime):
            yield prime
c = 6684964915220118582967779339778281191480721331277264008727956905412522191891577318496811103479236535162902002849402158576209369365216871215970298759907612506858782907695363640961486949954737422674241319324005824608432362870601503195732749418913837430005734723713418265367674478034958636210553558710255343852430555289083769122915746460520527901281000640322695067600645854331373546357250717419234641975207055438310902263460786023264083276241993777033019403958870974651300443284267874897661821470295678104777173473067115481628462826806003468946251426791453198705124293359121586511241439875401814776017696707984182021387
N = 20810957009276106793407213910378661196121487687823746048122155641218542460826730219110656287101260168946938791461059505814922118515467109509837349680754090608255504526134410351463656255691783971444571054522453022800126929469043167030391678846170049623981035076358138786501749472609158363456145355371459844126461090570363853528625626105278328302124774326540071764723428549101629873760220706844175555426584061941559726039964237456357385035695064652549354921445248608377193556548812135468913090861015290434175512233678163185595303365514323264097974212600785941588676627766702571648150080528511340232845880170920561238451
e = 16069787
mask = 0b101011000100100100000100 
'''
for R in range(0x80dfee, 0xffffff):#(0xb00000, 0xdddddd)
    if(R.bit_length() == 24):
        generator_24 = genPrime(R, mask, 24)
        e1 = generator_24.next()
        if(e1==e):
            print("R=",R)
'''
R=12045632
#print(hex(R))
generator_24 = genPrime(R, mask, 24)
e1 = generator_24.next()
#print(e1==e)
generator_1024 = genPrime(R, mask, 1024)
p = generator_1024.next()
q = generator_1024.next()
assert N==p*q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m=pow(c,d,N)
flag=long_to_bytes(m)
print(flag)

flag{cf51fa40dbe7cb83b5169f3313a4ea7e}

0x04 strange_rsa

这题因为卡在pyc文件反编译失败就挺可惜的，提示说的是python花指令，但也是没接触过没明白怎么修改，后来要了下wp才知道了一定原理。
首先拿到的是一个something.pcapng与加密压缩包,wireshark打开后直接过滤http协议，找到post方法显示是个png，点开后能够发现文件名是password.png，提取出16进制的代码还原图片

扫出来密码：Ss@qA!mm_
解压压缩包是一个pyc文件和输出的结果txt文件
但是pyc文件无法被 uncompyle6 反编译，原来是因为加入了一些多余的指令影响了反编译，参考pyc文件结构分析和防止反编译pyc文件，使用winhex打开文件后分析结果如下：

把71 04 00 64 71 08 00 00 去掉，再修改长度0x17为0x09就可以成功反编译
命令：uncompyle6 rsa_random.pyc > rsa_random.py
uncompyle直接pip安装就行，命令行就可以运行

终于看到了我们的题目代码：

# uncompyle6 version 3.7.4
# Python bytecode 2.7 (62211)
# Decompiled from: Python 2.7.13 (v2.7.13:a06454b1afa1, Dec 17 2016, 20:53:40) [MSC v.1500 64 bit (AMD64)]
# Embedded file name: ./python/rsa_random.py
# Compiled at: 2020-08-26 12:02:23
from Crypto.Util.number import *
import random

def main():
    flag = '**********'
    m = bytes_to_long(flag)
    p = getPrime(512)
    q = getPrime(512)
    e, n = 65537, p * q
    r = random.randint(50, 100)
    r1 = random.randint(5, r)
    r2 = random.randint(5, r)
    s = random.randint(1, min(p, q))
    t = random.randint(1, min(p, q))
    t_p = pow(s * p + r1, r, n)
    t_q = pow(t * q + r2, r, n)
    print 'n =', n
    print 't_p =', t_p
    print 't_q =', t_q
    print 'c =', pow(m, e, n)

main()
# okay decompiling rsa_random.pyc

r1 和 r 的随机范围不大可以爆破p
脚本如下：

from Crypto.Util.number import *
from gmpy2 import *
n = 106167987315458499845087542773749962995469243694635569829220420774849062833049760575518693059870630167239436735955264071653383506679652091045638741618504839584505361315933220909020046425848421545346559422019079643132131785046095049850931132463890947581870728502289320378392990348902513082529129376441145994323
t_p = 86191458332734793845711497945714858434638883031851134115636850463320763256565925316902861348795456765010953918047697708710031908677801221376679279014384189140352237592188052577541702005248235273960616498903480686442689933478323574292060151002175686324302922992554727339951548209119698126175978976116191668845
t_q = 49023282194184073130589088330027960511865709311590683281062620530681231536657641049225088203402381903290925322585102155461400792022533183187279351938764033055626670741881146630950258168552905391489757411210980567577440197443188598960091296683944678101675224274474737678890392686476446860809205525039445086142
c = 104498813539119630676178442611185869706877295539994211928418886093624460250606159685360064791018901082052090400832909428730136676600461331523802285428055114328521472522725362959019727527700610124983289687658202563483492274334268321759564440244724340188750046983025378483244471763496149402122413634144274462179
e = 65537
for r in range(50,101):
    for r1 in range(5,r+1):
        tmp=gcd((t_p-r1**r),n)
        if (tmp) !=1:
            p=tmp
            break
q=n//p
print "p=" + str(p)
print "q=" + str(q)
phi=(p-1)*(q-1)
d=invert(e,phi)
m=pow(c,d,n)
flag=long_to_bytes(m)
print(flag)

flag{086288c0-34a2-4c17-b419-114a4890791b}

码农公寓