BUU刷题

发表于 更新于 分类于 ，

寒假刷题记录

1/16

[MRCTF2020]babyRSA

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import sympy
import random
from gmpy2 import gcd, invert
from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes
from z3 import *
flag = b"MRCTF{xxxx}"
base = 65537


def GCD(A):
    B = 1
    for i in range(1, len(A)):
        B = gcd(A[i-1], A[i])
    return B


def gen_p():
    P = [0 for i in range(17)]
    P[0] = getPrime(128)
    for i in range(1, 17):
        P[i] = sympy.nextprime(P[i-1])
    print("P_p :", P[9])
    n = 1
    for i in range(17):
        n *= P[i]
    p = getPrime(1024)
    factor = pow(p, base, n)
    print("P_factor :", factor)
    return sympy.nextprime(p)


def gen_q():
    sub_Q = getPrime(1024)
    Q_1 = getPrime(1024)
    Q_2 = getPrime(1024)
    Q = sub_Q ** Q_2 % Q_1
    print("Q_1: ", Q_1)
    print("Q_2: ", Q_2)
    print("sub_Q: ", sub_Q)
    return sympy.nextprime(Q)


if __name__ == "__main__":
    _E = base
    _P = gen_p()
    _Q = gen_q()
    assert (gcd(_E, (_P - 1) * (_Q - 1)) == 1)
    _M = bytes_to_long(flag)
    _C = pow(_M, _E, _P * _Q)
    print("Ciphertext = ", _C)
'''
P_p : 206027926847308612719677572554991143421
P_factor : 213671742765908980787116579976289600595864704574134469173111790965233629909513884704158446946409910475727584342641848597858942209151114627306286393390259700239698869487469080881267182803062488043469138252786381822646126962323295676431679988602406971858136496624861228526070581338082202663895710929460596143281673761666804565161435963957655012011051936180536581488499059517946308650135300428672486819645279969693519039407892941672784362868653243632727928279698588177694171797254644864554162848696210763681197279758130811723700154618280764123396312330032986093579531909363210692564988076206283296967165522152288770019720928264542910922693728918198338839
Q_1:  103766439849465588084625049495793857634556517064563488433148224524638105971161051763127718438062862548184814747601299494052813662851459740127499557785398714481909461631996020048315790167967699932967974484481209879664173009585231469785141628982021847883945871201430155071257803163523612863113967495969578605521
Q_2:  151010734276916939790591461278981486442548035032350797306496105136358723586953123484087860176438629843688462671681777513652947555325607414858514566053513243083627810686084890261120641161987614435114887565491866120507844566210561620503961205851409386041194326728437073995372322433035153519757017396063066469743
sub_Q:  168992529793593315757895995101430241994953638330919314800130536809801824971112039572562389449584350643924391984800978193707795909956472992631004290479273525116959461856227262232600089176950810729475058260332177626961286009876630340945093629959302803189668904123890991069113826241497783666995751391361028949651
Ciphertext =  1709187240516367141460862187749451047644094885791761673574674330840842792189795049968394122216854491757922647656430908587059997070488674220330847871811836724541907666983042376216411561826640060734307013458794925025684062804589439843027290282034999617915124231838524593607080377300985152179828199569474241678651559771763395596697140206072537688129790126472053987391538280007082203006348029125729650207661362371936196789562658458778312533505938858959644541233578654340925901963957980047639114170033936570060250438906130591377904182111622236567507022711176457301476543461600524993045300728432815672077399879668276471832
'''

题目中的def GCD()似乎是P用没有的 亏我研究半天

第一步解出p，是一串连续的质数并给出了其中的第10个（一共17个）只要用sympy的prevprime和nextprime可以很轻松的得到这17个质数然后算n，φ，d，解出p再nextprime

第二步解出q，已经给出了q的运算方法但是按照Q = sub_Q ** Q_2 % Q_1的方式是无法在短时间解出来的所以使用pow方法结果是一样的

随后直接解出flag 这么简单的题目就不要看本fw的脚本了吧

[网鼎杯 2020 青龙组]you_raise_me_up

是一道考察离散对数的题目（没错就是我不会）

题目本身没有难点所以就简述一下知识点：

​ 离散对数问题：已知g的x次方模p等于h，g h p已知求x，可以使用x=sympy.discrete_log(p,h,g)

[UTCTF2020]basic-crypto

是道ex人的古典密码但我还是写了

第一步二进制转十进制然后ASCII码转字符

第二步base64（无换表）

第三步维吉尼亚在线破解https://www.guballa.de/vigenere-solver

第四步字符替换在线破解quipqiup - cryptoquip and cryptogram solver

下次一定直接跳（

[HDCTF2019]together

这是一道简单的共模攻击的题目但是本fw还是花了好长时间才完成

因为公钥文件私钥文件flagenc啥的实在是太为难我了（bushi

下面是一些openssl的东西

1
2
3
4
5
提取公钥文件信息：openssl rsa -pubin -text -modulus -in warmup -in pubkey.pem

生成私钥文件：python rsatool.py -o private.pem -e xxx-p xxx -q xxx

用private.pem文件 解密 flag.enc文件：openssl rsautl -decrypt -in flag.enc -inkey private.pem

但这不是这道题目搞我心态的地方（因为起码知道在哪找

搞我心态的是我竟然对一个base64加密之后的flag文件束手无策（正文开始

打开myflag1可以看到里面是明显的base64编码

bytes_to_long(base64.b64decode(s))得到10进制的或者base64.b64decode(s).hex()得到16进制的

我纯纯nt

1.17

[WUSTCTF2020]情书

过于简单，略

坏蛋是雷宾

rabin算法是rsa的一种衍生算法，其 p,q % 4 == 3, \(c = pow(m, 2, n)\)

解密过程如下，会得到四个明文，如果没有其他信息无法确定哪个是正确的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2  

c = 162853095  # 密文 c  
p = 49123             # 分解后的素数 p  
q = 10663             # 分解后的素数 q  
n = p*q                                                 # 公钥 N  

# 根据中国剩余定理求解相应明文  
r = pow(c,(p+1)//4,p)  
s = pow(c,(q+1)//4,q)  
a = gmpy2.invert(p,q)  
b = gmpy2.invert(q,p)  
x =(a*p*s+b*q*r)%n  
y =(a*p*s-b*q*r)%n  

# 打印明文  
print(x%n)  
print((-x)%n)  
print(y%n)  
print((-y)%n)

在本题中找到二进制符合题目的解10010011100100100101010110001然后去掉最后6个校验位再转成十进制md5

[WUSTCTF2020]dp_leaking_1s_very_d@angerous

一道基础的dp泄露攻击 （终于可以把一篇远古时期写的不知道往哪里贴的放上来了）

\(dp=d mod (p-1)\)

\(dp*e=ed mod (p-1)\)

\(ed = k1(p-1) +dp *e\)

\(ed ≡1 mod (p-1)(q-1)\)

\(k1(p-1) + dp*e = 1 mod (p-1)(q-1)\)

\(k1(p-1) + dp*e = k2(p-1)(q-1) + 1\)

\(dp*e = k2[(q-1)-k1] * (p-1) + 1\)

令\(x = k2[(q-1)-k1]\)

\(dp * e = x * (p-1) + 1\)

因为\(dp<(p-1)\), 所以\(x<e\)

遍历\(x\)从 \(1\) 到 \(e\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import*
e = 
n = 
dp = 
c = 
for i in range(1,65538):
    if (dp*e-1)%i == 0:
        if n%(((dp*e-1)//i)+1)==0:
            p=((dp*e-1)//i)+1
            q=n//(((dp*e-1)//i)+1)
            phi = (p-1)*(q-1)
            d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

ps：这个题目名字好像就是flag捏（

[BJDCTF2020]Polybius

好像是道古典密码捏

题目名字就是这个密码然后懒狗直接找了wp（

emmm没啥好说的不是很难就写个脚本列举出aeiou排列顺序和替换i/j然后找出有意义的序列

[NPUCTF2020]EzRSA

一道神奇的题目（

先看题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from gmpy2 import lcm , powmod , invert , gcd , mpz
from Crypto.Util.number import getPrime
from sympy import nextprime
from random import randint
p = getPrime(1024)
q = getPrime(1024)
n = p * q
gift = lcm(p - 1 , q - 1)
e = 54722
flag = b'NPUCTF{******************}'
m = int.from_bytes(flag , 'big')
c = powmod(m , e , n)
print('n: ' , n)
print('gift: ' , gift)
print('c: ' , c)
#输出略（

\(gift\)为\((p-1)\)和\((q-1)\)的最小公倍数，其比特位为2045

而$ φ \(的比特位应为2048位，所以应有\)φ = gift * i\(其中\) i ∈ ( 4 , 8 ) $

爆破一下\(i\)就好了,但是开始算的时候发现\(e\)不是一个质数，\(e = 27361 * 2\)

那么就按\(e = 27361\)计算之后再对m开方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import*
import gmpy2
'''
n=
gift=
c=
'''
e=54722//2
for i in range(4,9):
	phi=gift*i
	d=inverse(e,phi)
	m=pow(c,d,n)
	m,_=gmpy2.iroot(m,2)
	m=long_to_bytes(m)
	print(m)

这时候奇妙的事情增加了，我发现这5次都输出了相同的值（也就是flag

于是我把\(i\)设定为\(1\)也就是直接把\(gift\)当成\(φ\)用居然也得到了相同的答案。最后我发现无论\(i\)为何数都可以得到相同的明文（\(d\)不相同）

由于对rsa的原理并没有理解的非常透彻，本fw决定放弃解释并向huangx求助

实际上\(lcm(p-1, q-1)\)是\(φ\)的最简形式（但是我不知道怎么证明）

至于为什么i取任意值都可以达到呢

借这个机会先重新再整理一遍rsa解密推导过程 \[ c^d\ ≡\ m(mod\ n)\ \ >>\ \ (m^e-kn)^d≡m(mod\ n)\ \ >>\ \ m^{ed}≡m(mod\ n) \]

\[ >>\ \ m^{hφ(n)+1}≡m\ (mod\ n)\ \ >>\ \ m^{hφ(n)}≡1\ (mod\ n) \]

根据欧拉定理我们可以知道上式是成立的

那么对于i取任意值的情况，下式也成立 \[ m^{kiφ(n)}≡1 \]

[AFCTF2018]BASE

一整个无语住

什么都好说，就是这个文件实在是太大了，基本思路先16进制转文本（可以用winhex）然后basecrack一条龙，但是问题就是这个文件实在是太大了

八说了，逃

[BJDCTF2020]编码与调制

根据图片的内容找到曼彻斯特编码，略

[NPUCTF2020]Classical Cipher

古典密码（逃

[ACTF新生赛2020]crypto-classic1

古典（逃

坑爹之处在于：BUU给的题目是错的捏并且解完还要你给他变成小写才能过捏

原题为SRLU{OWSI_S_RDPKHARSA_NXYTFTJT}

四面八方

古典（逃

1.18

[MRCTF2020]Easy_RSA

先看题目

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import sympy
from gmpy2 import gcd, invert
from random import randint
from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes
import base64

from zlib import *
flag = b"MRCTF{XXXX}"
base = 65537

def gen_prime(N):
    A = 0
    while 1:
        A = getPrime(N)
        if A % 8 == 5:
            break
    return A

def gen_p():
    p = getPrime(1024)
    q = getPrime(1024)
    assert (p < q)
    n = p * q
    print("P_n = ", n)
    F_n = (p - 1) * (q - 1)
    print("P_F_n = ", F_n)
    factor2 = 2021 * p + 2020 * q
    if factor2 < 0:
        factor2 = (-1) * factor2
    return sympy.nextprime(factor2)


def gen_q():
    p = getPrime(1024)
    q = getPrime(1024)
    assert (p < q)
    n = p * q
    print("Q_n = ", n)
    e = getRandomNBitInteger(53)
    F_n = (p - 1) * (q - 1)
    while gcd(e, F_n) != 1:
        e = getRandomNBitInteger(53)
    d = invert(e, F_n)
    print("Q_E_D = ", e * d)
    factor2 = 2021 * p - 2020 * q
    if factor2 < 0:
        factor2 = (-1) * factor2
    return sympy.nextprime(factor2)


if __name__ == "__main__":
    _E = base
    _P = gen_p()
    _Q = gen_q()
    assert (gcd(_E, (_P - 1) * (_Q - 1)) == 1)
    _M = bytes_to_long(flag)
    _C = pow(_M, _E, _P * _Q)
    print("Ciphertext = ", _C)
'''
P_n =  略
P_F_n =  
Q_n =  
Q_E_D =  
Ciphertext =  
'''

求\(p\)，直接sage解方程

求\(q\)，先计算\(phi=(e*d-1)//(((e*d-1)//n)+1)\),随后和计算p一样，sage解出方程

随后正常rsa解出flag

EasyProgram

看到与flag有关的运算只有最后一句异或

先把伪代码转换成python（虽然没什么用只是看着舒服

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
key = "whoami"
flag = "flag{********************************}"
s = []
t = []
f = ""
j = 0
for i in range(256):
	s.append(i)
	t.append(key[i%len(key)])
for i in range(256):
	j = (j+s[i]+ord(t[i]))%256
	s[i],s[j]=s[j],s[i]
for m in range(38):
	i = (i+1)%256
	j = (j+s[i])%256
	s[i], s[j] = s[j], s[i]
	x = (s[i]+(s[j]%256))%256
	f += chr(ord(flag[m])^s[x])
print(f)

那么直接逆运算回去，由于只有一个和flag有关的运算，所以代码改动不是很大

看一眼file文件是乱码用winhex读16进制刚好38位于是手敲进去（我是菜狗）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
key = "whoami"
flag = [0x00,0xBA,0x8F,0x11,0x2B,0x22,0x9F,0x51,0xA1,0x2F,0xAB,0xB7,0x4B,0xD7,0x3F,0xEF,0xE1,0xB5,0x13,0xBE,0xC4,0xD4,0x5D,0x03,0xD9,0x00,0x7A,0xCA,0x1D,0x51,0xA4,0x73,0xB5,0xEF,0x3D,0x9B,0x31,0xB3]
s = []
t = []
f = ""
j = 0
for i in range(256):
	s.append(i)
	t.append(key[i%len(key)])
for i in range(256):
	j = (j+s[i]+ord(t[i]))%256
	s[i], s[j] = s[j], s[i]
i,j = 0,0
for m in range(38):
	i = (i+1)%256
	j = (j+s[i])%256
	s[i], s[j] = s[j], s[i]
	x = (s[i]+(s[j]%256))%256
	f += chr(flag[m] ^ s[x])
print(f)

[INSHack2017]rsa16m

一打开看着挺哈人的但是我们知道当n>>e的时候存在可能对c直接开e次方就能得到密文或者m^e = k*n+c中的k很小使得我们可以通过爆破得到

本题中直接开e次方就完事了（好烦这么大的txt虚拟机都打不开）

1
2
3
4
5
6
7
c = #略
e = 0x10001
import gmpy2
from Crypto.Util.number import*
m,_=gmpy2.iroot(c,e)
m=long_to_bytes(m)
print(m)

[AFCTF2018]你听过一次一密么？

一眼懵，先查一次一密，然后继续懵，然后看官方wp原来是Many-Time-Pad还是不会

继续查，翻到一篇写的比较好的wp于是懂了 （顺便嫖了代码） Many-Time-Pad 攻击

转述：

已知\(C_i⊕key=M_i\)

根据异或运算的性质， \[ C_1⊕C_2=(M_1⊕key)⊕(M_2⊕key)=M_1⊕M_2 \] 也就是说两个密文的异或就相当于对应明文的异或，此外我们还会发现 空格⊕大写字母=相应小写字母。所以如果x⊕y得到的是一个字母，那么x，y中就很可能有一个为空格。

将每条密文两两异或，得到相应列中，英文字母最多的，那么就假定该行明文的该列处为空格，如此可以恢复出该列的所有明文。

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
29
30
31
32
33
34
35
36
37
import Crypto.Util.strxor as xo
import libnum, codecs, numpy as np

def isChr(x):
    if ord('a') <= x and x <= ord('z'): return True
    if ord('A') <= x and x <= ord('Z'): return True
    return False

def infer(index, pos):
    if msg[index, pos] != 0:
        return
    msg[index, pos] = ord(' ')
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(' ')

dat = []

def getSpace():
    for index, x in enumerate(c):
        res = [xo.strxor(x, y) for y in c if x!=y]
        f = lambda pos: len(list(filter(isChr, [s[pos] for s in res])))
        cnt = [f(pos) for pos in range(len(x))]
        for pos in range(len(x)):
            dat.append((f(pos), index, pos))

c = [codecs.decode(x.strip().encode(), 'hex') for x in open('Problem.txt', 'r').readlines()]

msg = np.zeros([len(c), len(c[0])], dtype=int)

getSpace()

dat = sorted(dat)[::-1]
for w, index, pos in dat:
    infer(index, pos)

print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))

执行代码之后可以发现我们已经恢复出了大部分的明文（这里遇到一个小问题，直接执行这个代码是报错了，问题在于最后一行密文少了最后两位，补上两个0就可以了）

虽然还不是最终结果，但已经可以猜测出相应出错位置的字母了

1
2
3
4
5
6
7
8
9
10
def know(index, pos, ch):
    msg[index, pos] = ord(ch)
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(ch)

know(10, 21, 'y')
know(8, 14, 'n')

print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))

加上这一串代码就可以通过确定的字母恢复出相应出错列的明文

最后用\(C_1⊕M_1\)得到\(key\)：

1
2
key = xo.strxor(c[0], ''.join([chr(c) for c in msg[0]]).encode())
print(key)

大佬写的代码太好了555