Dest0g3 520迎新赛&ctfshow dsb

​ 自己的编程能力确实偏弱，趁着实训学学golang和算法。这是之前做的题。

ezStream

在普通LCG上变异，在获得nextnumber的时候进行移位操作。

from gmpy2 import invert
from Crypto.Util.number import *

a = 3939333498
b = 3662432446
m = 2271373817
state1 = 17362
state2 = 20624
c = 600017039001091357643174067454938198067935635401496485588306838343558125283178792619821966678282131419050878
state1_ = state1 << 16


def next(seed):
    seed_new = (a * seed + b) % m
    return seed_new >> 16,seed_new

# 爆破低16位得到可能的state1的真实值
# for i in range(2**16):
#     t = state1_ + i
#     if (a * t + b) % m >> 16 == state2:
#         print(t)
t_list = [1137839988,1137855425,1137870862]
# 求出可能的seed
for i in t_list:
    seed = (i - b) * invert(a,m)%m
    print(seed)
seed_list = [1315807869,710396196,104984523]

c_bytes = long_to_bytes(c)
print(len(c_bytes))

key_list = []
seed = 104984523
for i in range(47):
    key,seed = next(seed)
    key_list.append(key%10)

for i in range(45):
    print(chr(key_list[i+2]^c_bytes[i]),end='')

# 这道题并不需要求seed，拿到t_list之后递推就可以了

Mr.Doctor

看到别的师傅解法用了copper，我这里是直接解同余方程求seed。后边爆破hash时间复杂度太高，所以先把hash值求出来存在字典里再进行遍历9次计算。这是用空间换时间的做法。

from Crypto.Util.number import *
from binascii import *
import string
from hashlib import *

table = string.ascii_lowercase+string.digits+string.ascii_uppercase +'_@^&!?+-*'
print(table)


a = 956366446278
r = 1061992537343
b = 636205571590
d = 18068433704538283397
c = 1920358673646340365826516899186299898354902389402251443712585240681673718967552394250439615271108958695077816395789102908554482423707690040360881719002797624203057223577713119411615697309430781610828105111854807558984242631896605944487456402584672441464316236703857236007195673926937583757881853655505218912262929700452404084
Ash = 1097363493609113
SliverAsh = 2051431344160327

for i in range(2**12):
    # 注意移加法优先于移位操作...
    t = (Ash << 12) + i
    if (a * t**2 + r * t + b) % d >> 12 == SliverAsh:
        print(t)

next1 = 4494800869822930172
# sage
# m = 18068433704538283397
# R.<p> = Zmod(m)[]
# a = 956366446278
# r = 1061992537343
# b = 636205571590
# next1 = 4494800869822930172
# f = a*p^2 + r*p + b - Ash
# f.roots()

seed = 626844643882

def next(s):
    s_new = (a*s**2 + r*s + b)%d
    return s_new >> 12 , s_new

c_bytes = long_to_bytes(c)
print(len(c_bytes))

key_list = []
s = seed
for i in range(11):
    key,s = next(s)
    key_list.append(key%100)

sha_list = []
for i in range(9):
    j = long_to_bytes(key_list[i + 2] ^ (seed**3))
    print(j)
    jj = b2a_hex(j).decode('ascii')
    print(jj)

tmp = []
for i in range(9):
    tmp.append(bytes_to_long(c_bytes[15*i:15*i+15])^key_list[i+2])

hash_list = {}
seeds = seed**3
for i in table:
    for j in table:
        for m in table:
            for n in table:
                hash_list.update({bytes_to_long(sha256((i + j + m + n).encode()).hexdigest().encode()) % seeds : i+j+m+n})


for p in range(9):
    for i in hash_list:
        if i == tmp[p]:
            print(hash_list[i],end='')
            # Dest0g3{d2a4d1af-8a80-8794-99ac-635f89494cac}

Bag

背包加密，这里做了一些变异，思路就是先用模运算求出真实的S序列，再用普通背包解密算法。

from gmpy2 import invert
from Crypto.Util.number import *

def decode(n,S,r):
    l = []
    for i in range(286):
        l.append('0')

    for i in range(n, 0, -1):
        if S >= r[i]:
            S -= r[i]
            l[i-1] = '1'
            #print(l)
            print(r[i])
    return ''.join(l)

m=372992427307339981616536686110115630075342113098010788080347982669869622759400031649792
w=274062421102700155372289583695782343443

h=m.bit_length()
j=int(h//2)
print(j)

Bag=[...]
e = sk[2]
f = sk[3]
d = invert(w,m)

# e=gmpy2.next_prime(sum(V))+2
# f=gmpy2.next_prime(sum(U))
# Vi的和是小于e的，Ui的和是小于f的

S_low = (c * invert(f,e)) % e
S = (S_low + (c * invert(e,f)) %f * 2**j) * d % m

flag = decode(286,S,Bag)[::-1] # 注意要倒序
print(flag)
print(len(flag))
print(long_to_bytes(int(flag,2)))

# Dest0g3{5090ea29-8cb6-4ad8-ab43-1e6f65cc8eeb}

ctfshowdsb-TooYoungRSA

春哥的题质量确实不戳。首先是求n的方法：

$$第一次提交m,得c1=m^e\mod n$$ $$第二次提交m^2,得c2=m^e\mod n$$

利用c2-c1，就能得到一个关于n的多项式。

同理再对不同的m做一次这样的操作，得到另一个多项式；然后gcd求出n。n比较小可分解为pq。

求e：

$$cp = 3660902843315450019，通过cp和p在群上求离散对数e$$

G =GF(14129883229625683549)
g = G(9)
h = G(3660902843315450019)
print(discrete_log(h,g))

完整exp：

from hashlib import *
from gmpy2 import *
from  Crypto.Util.number import *
from Crypto.Cipher import AES

c1 = [218317653878226290959562768676110488122,217554978178747863351384784206111663308]
c2 = [175923870763460273019767769376686022660,45459644707418729830733907632443475707]

n = gcd(c1[0]**2 - c2[0],c1[1]**2 - c2[1])
print(n)

p = 14129883229625683549
q = n // p
phi = (p-1)*(q-1)

cp = c1[0] % p
# cp = 3660902843315450019
# 通过cp和p在群上求离散对数e
e = 1043311
ck = 57106634108800010078279971407683538766
d = invert(e,phi)
k = pow(ck,d,n)
key = sha256(str(k).encode()).digest()

cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(long_to_bytes(0x499d097315136877de8010dbda1e2da14b1079e79bd783f0ebbc48bcf7eedc0599deb16c455e71d82a02b7db52e748ab))
print(flag)
# ctfshow{70004b8b-ee57-418e-ab44-69c69a1fa347}