加密算法分析

字符对称加密有求模运算

如果遇到这种加密,有密文的情况下(当然),可以直接爆破,并且不是把所有的组合都显示出来,直接判断是否和密文相等即可.

例题-BUUCTF-SimpleRev

解密脚本:

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
67
68
69
70
71
72
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
char *__fastcall join(const char *a1, const char *a2) {
    size_t v2; // rbx
    size_t v3; // rax
    char *dest; // [rsp+18h] [rbp-18h]

    v2 = strlen(a1);
    v3 = strlen(a2);
    dest = (char *)malloc(v2 + v3 + 1);
    if ( !dest )
        exit(1);
    strcpy(dest, a1);
    strcat(dest, a2);
    return dest;
}
int main() {
    // char str2[100] = {0};
    // char key[100];
    // char *text;
    // char key1[100] = "ADSFK";
    // char key3[100] = "kills";
    // char chr; // [rsp+Fh] [rbp-51h]
    // int v2; // [rsp+10h] [rbp-50h]
    // int v3; // [rsp+14h] [rbp-4Ch]
    // int i; // [rsp+18h] [rbp-48h]
    // int v5; // [rsp+1Ch] [rbp-44h]
    // char src[8]; // [rsp+20h] [rbp-40h] BYREF
    // __int64 v7; // [rsp+28h] [rbp-38h]
    // int v8; // [rsp+30h] [rbp-30h]
    // __int64 v9[2]; // [rsp+40h] [rbp-20h] BYREF
    // int v10; // [rsp+50h] [rbp-10h]
    // unsigned __int64 v11; // [rsp+58h] [rbp-8h]

    // *(long long *)src = 0x534C43444ELL;
    // v7 = 0LL;
    // v8 = 0;
    // v9[0] = 0x776F646168LL;
    // v9[1] = 0LL;
    // v10 = 0;
    // text = (char *)join(key3, (char*)v9);
    // strcpy(key, key1);
    // strcat(key, src);
    // v2 = 0;
    // v3 = 0;
    // v5 = strlen(key);
    // for ( i = 0; i < v5; ++i ) {
    //     if ( key[v3 % v5] > 64 && key[v3 % v5] <= 90 )
    //         key[i] = key[v3 % v5] + 32;
    //     ++v3;
    // }
    // printf("v3=%d v5=%d key=%s\n", v3, v5, key);
    // printf("text=%s\n",text);

	printf("flag{");
    int v3 = 10;
    int v5 = 10;
    char key[] = "adsfkndcls"; //上面的处理脚本求出的key
    char text[] = "killshadow"; //上面的处理脚本求出的text
    for (int i = 0; i < strlen(key); ++i) {
        for (int chr = 'A'; chr <= 'Z'; ++chr) {
            if ((chr - 39 - key[v3 % v5] + 97) % 26 + 97 == text[i]) {
                v3++;
                putchar(chr);
                break;
            }
        }
    }
    printf("}");
    return 0;
}

RSA的判断

见[SUCTF2019]SignIn

image-20230922170839398

根据第20行的求幂并取模,和65537这个数,直接看出是RSA加密,调用python相关库进行求解

同时结果转换成十六进制数,使用binascii.unhexlify()方法将其转换为字符串

WP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 解密脚本
import gmpy2
import binascii

# 已知公私钥
n = 103461035900816914121390101299049044413950405173712170434161686539878160984549
p = 282164587459512124844245113950593348271
q = 366669102002966856876605669837014229419
e = 65537
c = 0xad939ff59f6e70bcbfad406f2494993757eee98b91bc244184a377520d06fc35
# c = input('请输入密文')
n = p * q
phi_n = (p - 1) * (q - 1)  # 对n取欧拉函数,p,q均为素数
d = gmpy2.invert(e, phi_n)  # 即e*d mod phi_n = 1 (求逆元)
m = gmpy2.powmod(c, d, n)  # 即m = c^d mod n (求大整数c的d次幂模n取余)
flag = str(hex(m))[2:]
print(binascii.unhexlify(flag).decode())

数学基础考察

求模逆运算

例题:NSSCTF-[SWPUCTF 2021 新生赛]fakebase

题目:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
flag = 'xxxxxxxxxxxxxxxxxxx'

s_box = 'qwertyuiopasdfghjkzxcvb123456#$'
tmp = ''
for i in flag:
    tmp += str(bin(ord(i)))[2:].zfill(8)
b1 = int(tmp,2)
s = ''
while b1//31 != 0:
    s += s_box[b1%31]
    b1 = b1//31

print(s)

# s = u#k4ggia61egegzjuqz12jhfspfkay

题目考查了取模的逆运算，假设c=a%b已知，c和b，那么a可以得到算式：a=k*b+c。其中k是需要爆破的.

1.加密时,将flag的每一个字符的8位ASCII码拼接起来,生成一个整数b1,

然后对b1循环,每次将b1%31作为下标从s_box中找到转换的字符,并拼接到s中,然后b1整除31,以此类推,直到b1为0(?).

2.解密时,先令b1=0,然后将s逆序,对每一个字符从s_box中找到其下标,依次加入到b1中,然后b1*=31.

最后能逆向求出前面的b1,然后使用对应的方法转换为字符串即可.

但是这里有一个问题,那就是flag的第一个字符需要爆破—由于对31求模的运算,我们不知道这个求模究竟减掉了多少个31,也就是说k*31中,我们不知道k的值.

3.爆破方法:

因为每次处理的字符都是其ASCII码,不超过128,那么128//31==4,所以爆破范围不超过5,我们直接在外面套一个循环,让b1最开始就等于这个数,内层的循环中的b1 = b1 * 31 + s_box.index(i)第一次执行就会将其乘上k,然后正常处理,输出这次的flag.

循环5次后,从爆破出来字符串中找到正确的flag(其他的大概率乱码).

关键在于,第一个字符直接影响到最终的b1的高位(?),进而直接影响到整个flag的解码,而不是仅仅影响第一个字符的解码.

解密脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
s = 'u#k4ggia61egegzjuqz12jhfspfkay'
s_box = 'qwertyuiopasdfghjkzxcvb123456#$'
flag = ''
for k in range(5):
    flag = ''
    b1 = k
    for i in reversed(s):
        b1 = b1 * 31 + s_box.index(i)
    b1 = str(bin(b1))[2:]
    # print(b1)
    if len(b1) % 8 != 0:
        b1 = b1.zfill((len(b1) // 8 + 1) * 8)

    for i in range(0, len(b1), 8):
        flag += chr(int(b1[i:i + 8], 2))
    print(flag)

输出结果:

1
2
3
4
5
6
7
8
9
E:\devtools\CTF\Scripts\python.exe D:\Data\CTF\do\test.py 
@ô㻆qrMñáSø&xغ
ñ¾v^™PÌbk¬MÁ;a û
5¢ˆÜÙoæ«Q¼åwGŠPJi<
NSSCTF{WHAt_BASe31}
;zù¾

进程已结束，退出代码为 0