祥云杯crypto-wp

0x01概况

为期2天的比赛，pwn题很多很难。re一坨屎。

0x02部分题解

tracing

gcd用的辗转相除法法，爆破无果。应该是从.out文件里的函数调用过程一步步恢复phi。
根据.out文件的 a = a - b a = rshift1(a) b = rshift1(b) a, b = b, a
写出对应的逆操作

import gmpy2
from Crypto.Util.number import long_to_bytes
n = 113793513490894881175568252406666081108916791207947545198428641792768110581083359318482355485724476407204679171578376741972958506284872470096498674038813765700336353715590069074081309886710425934960057225969468061891326946398492194812594219890553185043390915509200930203655022420444027841986189782168065174301
c = 64885875317556090558238994066256805052213864161514435285748891561779867972960805879348109302233463726130814478875296026610171472811894585459078460333131491392347346367422276701128380739598873156279173639691126814411752657279838804780550186863637510445720206103962994087507407296814662270605713097055799853102
e = 65537
with open('trace.out','rb') as f:
    data = f.readlines()
a = 1
b = 0
i = 0
for l in data[::-1]:
    # print(l)
    if 'a, b = b, a' in str(l).strip('\n'):
        a, b = b, a
        print(a,b)
    if 'a = rshift1(a)' in str(l).strip('\n'):
        a =a*2

    if 'b = rshift1(b)' in str(l).strip('\n'):
        b =b*2

    if 'a = a - b' in str(l).strip('\n'):
        i += 1
        a = a + b

print(i)
d = gmpy2.invert(e,a)
print(long_to_bytes(gmpy2.powmod(c,d,n)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

little little fermat

考察费马小定理的应用
114514 ** x % p == 1 可以得到 x = p-1

def obfuscate(p, k):
    nbit = p.bit_length()
    while True:
        l1 = [getRandomRange(-1, 1) for i in 'i' * k]
        l2 = [getRandomRange(100, nbit) for i in 'i' * k]
        l3 = [getRandomRange(10, nbit//4) for i in 'i' * k]
        l4 = [getRandomRange(2, 6) for i in 'i' *k]
        A = sum([l1[i] * 2 ** ((l2[i]+l3[i])//l4[i]) for i in range(0, k)])
        q = p + A
        if isPrime(q) * A != 0:
            return q
1
2
3
4
5
6
7
8
9
10
11

可以看出p,q生成接近
直接yafu分解即可。
exp.py

from Crypto.Util.number import *
import gmpy2
p = 11887853772894265642834649929578157180848240939084164222334476057487485972806971092902627112665734648016476153593841839977704512156756634066593725142934001
q = 11887853772894265642834649929578157180848240939084164222334476057487485972806971092902627112665734646483980612727952939084061619889139517526028673988305393
# 114514 ** x % p == 1

n = 141321067325716426375483506915224930097246865960474155069040176356860707435540270911081589751471783519639996589589495877214497196498978453005154272785048418715013714419926299248566038773669282170912502161620702945933984680880287757862837880474184004082619880793733517191297469980246315623924571332042031367393
c = 81368762831358980348757303940178994718818656679774450300533215016117959412236853310026456227434535301960147956843664862777300751319650636299943068620007067063945453310992828498083556205352025638600643137849563080996797888503027153527315524658003251767187427382796451974118362546507788854349086917112114926883
d = gmpy2.invert(65537,(p-1)*(q-1))
print(d)
m = gmpy2.powmod(c,d,n)
x = p-1
m = m^(x**2)
print(long_to_bytes(m))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

fill

阅读题
lcg + 背包密码
根据s[i] = (s[i-1]*m+c)%n; s[0], s[1], s[2] 求出m,c

from functools import reduce
from math import gcd
from Crypto.Util.number import *
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0]*multiplier) % modulus
    return modulus, multiplier, increment

def crack_unknown_multiplier(states, modulus):
    multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
    return crack_unknown_increment(states, modulus, multiplier)

print(crack_unknown_multiplier([562734112,859151551,741682801], 991125622))
# (991125622, 55365664, 8712091)
# n m c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

进一步得到s

def get_s_list():
    n = 991125622
    s = [0]*100
    s[0] = 562734112
    s[1],s[2] = 859151551,741682801
    m, c = 55365664, 8712091
    for i in range(1, 32):
        s[i] = (s[i - 1] * m + c) % n
    return s
1
2
3
4
5
6
7
8
9

解出M 把这个+改成-

for t in range(nbits):
    M[t] = M[t] + s[t]
print("M = ",M)


M = [19621141192340, 39617541681643, 3004946591889, 6231471734951, 3703341368174, 48859912097514, 4386411556216, 11028070476391, 18637548953150, 29985057892414, 20689980879644, 20060557946852, 46908191806199, 8849137870273, 28637782510640, 35930273563752, 20695924342882, 36660291028583, 10923264012354, 29810154308143, 4444597606142, 31802472725414, 23368528779283, 15179021971456, 34642073901253, 44824809996134, 31243873675161, 27159321498211, 2220647072602, 20255746235462, 24667528459211, 46916059974372]
s =[562734112, 859151551, 741682801, 14226897, 377702151, 628246015, 427012029, 408289189, 369763277, 24165751, 665728051, 402005955, 129351681, 886742445, 685428965, 26373789, 757015315, 693011303, 35961901, 114504751, 606049065, 739862995, 104041367, 338135467, 302333339, 338598601, 612797553, 721997467, 707613043, 657143655, 33698403, 941794625]
for i in range(32):
    M[i] -= s[i]
print(M)
1
2
3
4
5
6
7
8
9
10

背包:

M = [19620578458228, 39616682530092, 3004204909088, 6231457508054, 3702963666023, 48859283851499, 4385984544187, 11027662187202, 18637179189873, 29985033726663, 20689315151593, 20060155940897, 46908062454518, 8848251127828, 28637097081675, 35930247189963, 20695167327567, 36659598017280, 10923228050453, 29810039803392, 4443991557077, 31801732862419, 23368424737916, 15178683835989, 34641771567914, 44824471397533, 31243260877608, 27158599500744, 2219939459559, 20255089091807, 24667494760808, 46915118179747]

S = 492226042629702
# s = "110101111001111011101111011001000"
# s_ = list(s)
# sum = 0
# for i in range(len(M)):
#     sum += int(s_[i])*M[i]
#
# print(sum)



n = len(M)
L = matrix.zero(n + 1)

for row, x in enumerate(M):
    L[row, row] = 2
    L[row, -1] = x

L[-1, :] = 1
L[-1, -1] = S

res = L.LLL()
print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

exp.py

import hashlib

data = [-1,-1, 1,-1, 1,-1,-1,-1,-1, 1, 1,-1,-1,-1,-1, 1,-1,-1,-1,1,-1,-1,-1,-1 ,1,-1,-1 ,1, 1,-1 ,1, 1]

flag = []
for t in data:
    if t == -1:
        flag.append('1')
    else:
        flag.append('0')
print("".join(flag))

msg = int("11010111100111101110111101100100",2)
print(msg)
print("flag{" + hashlib.sha256(str(msg).encode()).hexdigest() + '}')

# flag{sha256(7235034824)}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

common_rsa

赛后可以直接在线分解…

leak_rsa

不会

DLP

是一个原题

0x03结尾

放下排名,全靠队友;坚持打卡，我不摸鱼。