【新手向】在ctf逆向中，最基础也是最关键的一步就是逆加密算法，写解密算法，因为这往往是最后一步。虽然魔改算法很糖，因为纯耗费时间，但ctf喜欢出，没办法。

解密的常规思路

1.逆算法

逆算法的核心就是将加密算法倒过来，求逆运算。

这里求逆运算可以分两种情况：对单个运算求逆运算和对多个运算求逆运算

对单个运算求逆运算

比如现在我们有如下信息：明文m，密钥k

经过加密算法：

1 2	t=m+k c=t^k

此时我们得到信息：密文c，密钥k

解密思路也是显而易见，倒过来看加密算法

先是，c=t^k，异或的逆运算是异或，两边同时异或密钥k，得到c^k=t^k^k=t

所以t=c^k

这里就已经完成对异或单个运算求逆运算了，此时我们得到了中间变量t

然后是，t=m+k，加法逆运算是减法，两边同时减k，得到t-k=m+k-k，得到m=t-k

整体法

我们现在有如下信息：明文v1，v0，密钥k0，密钥k1，已知数sum，经过下面加密

1	v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);

现在我们得到信息为：加密后的v0，保持不变的明文v1，密钥k0，密钥k1，已知数sum

此时我们可以看到，在表达式右边的所有变量都未发生改变，假设令k=((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1)，则加密前后的k都保持不变。

可以重新看作

1
2
3

我们有如下信息：明文m，密钥k
经过加密算法：v0+=k
此时我们得到信息：加密后的v0，密钥k

因此解密只需要

1
2
3

v0-=k
即
v0-=((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);

对多个运算求逆运算

需要对多个运算求逆运算的情况在于，你对其中的单个运算求逆运算无法求出想要得到的数据。

比如base64：（如果对base64原理不了解，建议先看base64）

已知3个字节的m数组，经过base64加密得到4个字节的c数组

c[0] = base64table[((m[0] & 0xFC) >> 2)];
c[1] = base64table[(((m[0] & 0x03) << 4) | ((m[1] & 0xF0) >> 4))];
c[2] = base64table[(((m[1] & 0x0F) << 2) | ((m[2] & 0xC0) >> 6))];
c[3] = base64table[(m[2] & 0x3F)];

此时我们有c数组和base表，最后一步表达式是c[cPos + +] = base64table[(m[i + 2] & 0x3F)]

站在字节的角度你无法从c[3]里面还原出m[2]，因为加密过程中只用到了m[2]的低6位，你无法还原出其高2位

此时我们就要将最后两步表达式一起看

1 2	c[2] = base64table[(((m[1] & 0x0F) << 2) \| ((m[2] & 0xC0) >> 6))]; c[3] = base64table[(m[2] & 0x3F)];

不难看出m[2]的高两位位于c[2]的低两位，m[2]的低6位就是c[3]

所以需要同时通过c[2]和c[3]来求得m[3]，得到解密表达式为m[3]=((c[2]<<6)&0b11)|(c[3])

站在字节的角度来说，单独通过最后一步表达式可以求出m[2]的低6位，但是这样会比较麻烦，对多个运算求逆运算是一种解密的思路，用于简便解密过程和解密代码。当然有的情况下是无法求单步运算的逆，比如解方程。

2.爆破

主要思路有：暴力破解，递归爆破，测信道等

待更……

逆向中常见的加密算法

基础运算

加减乘

在有限域（在c中每一个类型都限制了bit位，可以看作有限域）内，如果加减乘得到的结果超过了有限域的范围，溢出的部分就会被截断。

例如下面代码中，unsigned char（8bit） a =0xff+6；

正常算的话：0xff+6 = 0x105

但是0x105显然超过了8个bit，超过8个bit的部分就必须舍弃，保留低8个bit，则：0x105&0xff = 0x5

#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[]) {
    unsigned char a = 0xff;
    a+=6;
    printf("%d",a);
}
//5

注意：和有无符号无关，unsigned char表示的数据范围为（0~~255），char表示的数据范围为（-128 ~ 127），但是他们在内存中都是用0~~0xff来表示的，只是解析的方式不同。而溢出是和bit大小有关的，他们都是8个bit，溢出时都是保留低8bit。

除法

主要用在解密中，有限域的除法跟平时肯定是不一样的

#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[]) {
    unsigned char a = 255;
    a*=3;
    printf("%d",a);
}
//253

直接拿253除以3肯定是得不到255的

这种情况下我们需要求3在有限域下的逆元

1
2
3

import gmpy2
print(gmpy2.invert(3,256))
#171

假如你会离散数学：这里(3*255)&0xff 也可以表示成 (3*255)%256。常规思想用253除以3，其实就是用253乘以3的倒数。而在有限域内倒数就是逆元，倒数的定义大家都知道，a*(1/a)=1，这里用（171*3）%256得到的是1，所以逆元就相当于倒数这样的一个存在，而171就是在8bit有限域内3的倒数

所以用(171*253)&0xff解出255

假如不会离散数学：那不会也可以，记得这么操作就行，或者简单自学一下

异或

将两个数逐bit比较，相同为0，不同为1

最重要的性质：若c=a^b，我们知道a，b，c任意两个数，都能异或得到另外一个数。

自行研究

与

与或非的运算自学就行

主要讲”与”作为mask的用法

data & mask 会保留 data 中与 mask 中 1 对应的位，其余位会被置为 0。

1
2
3

unsigned char data = 0xAB; // 二进制: 10101011
unsigned char mask = 0x0F; // 二进制: 00001111
unsigned char result = data & mask; // 结果: 00001011 (0x0B)

所以在溢出的时候，如果用的是python脚本，可以用&0xff限制保留低8位，同样对于uint32_t，在python中可以用&0xffffffff来限制

RC4

rc4主要加密过程分为两步，初始化函数+加密明文

初始化函数生成s盒，加密密文的时候利用s盒对明文进行加密

 
/*初始化函数*/
void rc4_init(unsigned char *s, unsigned char *key, unsigned long Len) {
    int i = 0, j = 0;
    char k[256] = {0};
    unsigned char tmp = 0;
    for (i = 0; i < 256; i++) {
        s[i] = i;
        k[i] = key[i % Len];
    }
    for (i = 0; i < 256; i++) {
        j = (j + s[i] + k[i]) % 256;
        tmp = s[i];
        s[i] = s[j]; // 交换s[i]和s[j]
        s[j] = tmp;
    }
}
 
/*加解密*/
void rc4_crypt(unsigned char *s, unsigned char *Data, unsigned long Len) {
    int i = 0, j = 0, t = 0;
    unsigned long k = 0;
    unsigned char tmp;
    for (k = 0; k < Len; k++) {
        i = (i + 1) % 256;
        j = (j + s[i]) % 256;
        tmp = s[i];
        s[i] = s[j]; // 交换s[x]和s[y]
        s[j] = tmp;
        t = (s[i] + s[j]) % 256;
        Data[k] ^= s[t];
    }
}

我更加倾向将rc4分为下面这样的两步：生成密钥流，加密明文。

这样我们可以看到rc4实际上是将明文和一个由key生成的密钥流进行异或。如果在知道key的情况下，我们就等于知道了密钥流。

那么rc4就可以看成明文和一个固定数组进行异或。因为异或的逆运算是其本身，解密的话也只需要将密文和密钥流进行异或即可。

 void rc4_init(unsigned char *s, unsigned char *key, unsigned long Len) {
    int i = 0, j = 0;
    char k[256] = {0};
    unsigned char tmp = 0;
    for (i = 0; i < 256; i++) {
        s[i] = i;
        k[i] = key[i % Len];
    }
    for (i = 0; i < 256; i++) {
        j = (j + s[i] + k[i]) % 256;
        tmp = s[i];
        s[i] = s[j]; // 交换s[i]和s[j]
        s[j] = tmp;
    }
}
 void rc4_crypt(unsigned char *s, unsigned char *Data, unsigned long Len) {
    int i = 0, j = 0, t = 0;
    unsigned long k = 0;
    unsigned char tmp;
    unsigned char keystream[Len];
    for (k = 0; k < Len; k++) {
        i = (i + 1) % 256;
        j = (j + s[i]) % 256;
        tmp = s[i];
        s[i] = s[j]; // 交换s[x]和s[y]
        s[j] = tmp;
        t = (s[i] + s[j]) % 256;
        keystream[k]=s[t];
    }
     
     
     //上面是生成密钥流keystream，下面是加密
     for (k = 0; k < Len; k++) {
        Data[i]^=keystream[i];
    }
     
}

如何解密

rc4解密方式太多，根据情况选择合适的解法

1.复现算法

将反编译器中的生成密钥流的算法复现出来，然后通过key运行算法生成密钥流，然后用密钥流和密文异或，可以自己敲一遍rc4的代码，敲完就会了

2.trace获取密钥流

// rc4.c
// gcc .\rc4.c -o rc4.exe
#include <stdio.h>
#include <string.h>

/* 初始化函数 */
void rc4_init(unsigned char *s, unsigned char *key, unsigned long Len) {
    int i = 0, j = 0;
    char k[256] = {0};
    unsigned char tmp = 0;
    for (i = 0; i < 256; i++) {
        s[i] = i;
        k[i] = key[i % Len];
    }
    for (i = 0; i < 256; i++) {
        j = (j + s[i] + k[i]) % 256;
        tmp = s[i];
        s[i] = s[j]; // 交换s[i]和s[j]
        s[j] = tmp;
    }
}

/* 加解密函数 */
void rc4_crypt(unsigned char *s, unsigned char *Data, unsigned long Len) {
    int i = 0, j = 0, t = 0;
    unsigned long k = 0;
    unsigned char tmp;
    for (k = 0; k < Len; k++) {
        i = (i + 1) % 256;
        j = (j + s[i]) % 256;
        tmp = s[i];
        s[i] = s[j]; // 交换s[x]和s[y]
        s[j] = tmp;
        t = (s[i] + s[j]) % 256;
        Data[k] ^= s[t];
    }
}

int main() {
    unsigned char s[256]; // S盒
    unsigned char key[] = "key123"; // 固定密钥
    unsigned char enc[]={0xfd,0xeb,0xd9,0x97,0x78,0x79,0x9d,0x2c,0x96,0xce};
    unsigned char plaintext[256]; // 明文
    unsigned long len;

    // 用户输入明文
    printf("input flag: ");
    scanf("%s", plaintext);

    // 计算明文长度
    len = strlen((char *)plaintext);
    if(len!=10){
        return 0;
    };

    // 初始化S盒
    rc4_init(s, key, strlen((char *)key));

    // 加密明文
    rc4_crypt(s, (unsigned char *)plaintext, len);
    for (int i = 0; i < len; i++) {
        if(plaintext[i]!=enc[i]){
            return 0;
        }
    }
    printf("yes");

    return 0;
}

编译出exe后用ida64打开，在rc4_crypt处找到异或

按tab转成汇编，找到汇编的xor

f2下断点，右键选择编辑断点，打印寄存器的值

1 2	import idc print(hex(get_reg_value("ecx")),end=",")

点击运行后，输入任意10个字节的字符串，可以看到在output中输出了密钥流，用密钥流和密文异或即可解密

3.测试明文和测试密文进行异或

用户随意输入的数据为测试明文，经过加密得到测试密文

断在加密后面，运行上面rc4.exe，输入任意10字节字符串，这里我输入的测试明文为”1111111111”

断下来后点进str，找到测试密文

因为testc = testm ^k，两边都异或testm得到testc^testm=testm^k^testm=k

所以k=testc^testm

异或得到密钥流，用密钥流和密文进行异或可以解密

testm=[ord(i) for i in "1111111111"]
testc=[ 0xAA, 0xB6, 0x89, 0xC1, 0x32, 0x3C, 0xC9, 0x6E, 0xD3, 0x82]
keystream=[]
for i in range(len(testm)):
    keystream.append(testm[i]^testc[i])
print(",".join(map(hex,keystream)))

4.输入patch成密文

因为rc4算法即是加密，又是解密，可以直接利用程序解密

但是密文可能是不可打印字符，所以使用idapython进行patch，然后到解密处拿到flag

from ida_bytes import *
c=[]                #密文
addr=0x0            #输入字符串存放的起始地址
patch_bytes(addr,bytes(c))

断在输入后面

输入任意10个字节字符串

点进v6拿到密文（shift+8，选择长度10，转化为长度为10的数组，shift+e提取）

点进str找到输入

然后点run，再×掉，能看到输入变成了密文

运行到加密（解密完成）

点进str，可以看到已经完成了解密

魔改

在原算法上做一些改动，如果对加密解密非常了解的话，都是手撕算法，不需要硬记下面内容。

1.魔改密钥流生成

比如修改s盒大小，但是没啥影响，除了复现算法的时候要注意别写错了，2，3，4的解密方法依然适用

 
/*初始化函数*/
void rc4_init(unsigned char *s, unsigned char *key, unsigned long Len) {
    int i = 0, j = 0;
    char k[128] = {0};
    unsigned char tmp = 0;
    for (i = 0; i < 128; i++) {
        s[i] = i;
        k[i] = key[i % Len];
    }
    for (i = 0; i < 128; i++) {
        j = (j + s[i] + k[i]) % 128;
        tmp = s[i];
        s[i] = s[j]; // 交换s[i]和s[j]
        s[j] = tmp;
    }
}
 
/*加解密*/
void rc4_crypt(unsigned char *s, unsigned char *Data, unsigned long Len) {
    int i = 0, j = 0, t = 0;
    unsigned long k = 0;
    unsigned char tmp;
    for (k = 0; k < Len; k++) {
        i = (i + 1) % 128;
        j = (j + s[i]) % 128;
        tmp = s[i];
        s[i] = s[j]; // 交换s[x]和s[y]
        s[j] = tmp;
        t = (s[i] + s[j]) % 128;
        Data[k] ^= s[t];
    }
}

2.魔改加密

例如将最后的Data[k]^=s[t]改成Data[k]-=s[t]

此时对于1解法来说，只需要将解密改成Data[k]+=s[t]。（注意，如果是c的话，得用unsigned char，否则就得&0xff防止溢出，其他语言最好都&0xff，加减法都会导致溢出问题）

对于方法2和方法3照样用，最后Data[k]+=keystream[k]即可，同样得注意溢出

方法4不可用，因为加密是减法的话，解密就是加法，解密!=加密

tea系列

tea，xtea

//tea
#include <stdint.h>
 
void encrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i < 32; i++) {                       /* basic cycle start */
        sum += delta;
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);  
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}
 
void decrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i;  /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i<32; i++) {                         /* basic cycle start */
        v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
        v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        sum -= delta;
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}



//xtea
#include <stdint.h>
 
/* take 64 bits of data in v[0] and v[1] and 128 bits of key[0] - key[3] */
 
void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
    for (i=0; i < num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}
 
void decipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], delta=0x9E3779B9, sum=delta*num_rounds;
    for (i=0; i < num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}

tea和xtea是分组密码，将明文封装成uint32_t （4字节）类型数组，通常为小端序；（建议自行查询关于小端序的内容）

、

我们输入flag111111111111，得到转化出来的数组，

主要看第一个元素，0x67616c66，其中0x67是”g”的ascii，0x61是”a”，0x6c是”l”，0x66是”f”，可以看到是倒过来的，这就是小端序，大端序的话就是正的。

tea和xtea会对数组中的元素两个一组进行Feistel 结构加密，除了在表达式上有些区别，基本一样。（有关Feistel 可以自行查阅，不查也没事，不重要）

在encrypt(&data[0], key)中

v0 = v[0], v1 = v[1]

即v0 = data[0], v1 = data[1] （主要补充说明一下两个一组）

下面是源码，可以编译成ctf例题，标准tea，看看逻辑即可。

//tea.c
//gcc .\tea.c -o tea.exe
#include <stdio.h>
#include <stdint.h>
#include <string.h>

void encrypt(uint32_t* v, uint32_t* k) {
    uint32_t v0 = v[0], v1 = v[1], sum = 0, i;
    uint32_t delta = 0x9e3779b9;
    uint32_t k0 = k[0], k1 = k[1], k2 = k[2], k3 = k[3];

    for (i = 0; i < 32; i++) {
        sum += delta;
        v0 += ((v1 << 4) + k0) ^ (v1 + sum) ^ ((v1 >> 5) + k1);
        v1 += ((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3);
    }

    v[0] = v0;
    v[1] = v1;
}

int main() {
    uint32_t key[4] = {0x12345678, 0x9abcdef0, 0xdeadbeef, 0x11223344};  // 128-bit 密钥
    unsigned char input[16] = {0};  // 16 字节输入
    uint32_t enc[4] = {0x2d179ba6,0xf8e07778,0x5a96e915,0xb7ea15af};
    uint32_t data[4] = {0};  // 16 字节转换为 4 个 uint32_t 进行加密

    printf("input flag: ");
    fgets((char*)input, 17, stdin);  // 读取 16 字节数据（多读 1 个字节用于防止缓冲区溢出）
    
    // 如果输入少于 16 字节，补 0
    size_t len = strlen((char*)input);
    if (len < 16) {
        memset(input + len, 0, 16 - len);
    }

    // 将 16 字节转换为 4 个 uint32_t
    for (int i = 0; i < 4; i++) {
        data[i] = (input[i * 4] ) | (input[i * 4 + 1] << 8) | 
                  (input[i * 4 + 2] << 16) | (input[i * 4 + 3]<<24);
    }
    for(int i=0;i<4;i++){
        printf("%x,",data[i]);
    }

    // 8 字节一组加密，即两个uint32_t
    encrypt(&data[0], key);
    encrypt(&data[2], key);
    for (int i = 0; i < 4; i++) {
        if(data[i]!=enc[i]){
            return 0;
        }
    }
    printf("yes");

    return 0;
}

如何解密

用tea举例，我们可以看到下面三句关键加密代码，并且加密了32次，或者说32轮，其中delta是常量，k0~k3是密钥。

假如下面是第32轮，也就是最后一轮的加密，那么我们可以得到哪些信息？

题目肯定给定了密文，v0’（加密后的v0，这里的加密指的是在第32轮被加密）和v1‘（加密后的v1），sum’=32*delta（因为sum += delta累加了32次，注意uint32_t sum，小心溢出），k0~k3

1
2
3

sum’ = sum + delta;
v0’ = v0 + ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
v1’ = v1 + ((v0’<<4) + k2) ^ (v0’ + sum) ^ ((v0’>>5) + k3);

现在我们要解密出在第32轮加密之前的v0，v1

参考解密的常规思路对单个运算求逆运算整体法中的内容

对于

1	v1’ = v1 + ((v0’<<4) + k2) ^ (v0’ + sum) ^ ((v0’>>5) + k3);

因为 v0’，v1‘，sum，k0~k3已知，移项得到

1	v1 = v1’ - ((v0’<<4) + k2) ^ (v0’ + sum) ^ ((v0’>>5) + k3);

此时， v0’，v1，sum，k0~k3已知，所以对第二个表达式移项得到

1 2	v0 = v0’ - ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1); sum = sum’ - delta;

此时我们就求出了第32轮加密前的v0，v1，sum，还有已知的delta，k0~k3

然后v0，v1，sum分别作为第31轮的v0’，v1‘，sum’，参与第31轮的解密，以此类推，得到解密算法

for (i=32-1; i>=0; i--) {                        
        v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
        v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        sum -= delta;
}

为什么这里写的for (i=32-1; i>=0; i++) ，前面写的for (i = 0; i < 32; i++) ？

实际上在这都一样，因为每一轮的加密都是一样的，每一轮的解密也是一样

如果是如下这样的魔改tea的话，每一轮异或的i是不一样的，因此每一轮的加密和解密都是不一样的，则必须是for (i=32-1; i>=0; i++)

for (i = 0; i < 32; i++) {
        sum += delta;
        v0 += ((v1 << 4) + k0) ^ (v1 + sum) ^ ((v1 >> 5) + k1)^i;
        v1 += ((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3)^i;
}

在解密的时候，我们要将加密算法倒过来解，而加密的最后一轮是第32轮，也就是i=31的那一轮，而i会影响当前轮的加密，所以解密的时候也要先解第32轮，i=31，然后一直解第31轮（i=30），解第30轮（i=29）……

魔改

1.魔改常量

例如：

魔改delta

解密直接将delta换了就行

魔改sum初始值（默认都是0）

解密的时候直接sum=初始值+轮数*delta

魔改加密轮数

解密的时候sum=初始值+轮数*delta，同时也要解密同样的轮数

2.魔改加密表达式

例如

魔改表达式顺序

1
2
3

v1 += ((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3);
sum += delta;
v0 += ((v1 << 4) + k0) ^ (v1 + sum) ^ ((v1 >> 5) + k1);

解密倒着来就行

1
2
3

v0 -= ((v1 << 4) + k0) ^ (v1 + sum) ^ ((v1 >> 5) + k1);
sum -= delta;
v1 -= ((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3);

魔改表达式运算

1
2
3

v1 += ((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3);
sum -= delta;
v0 ^= ((v1 << 4) + k0) ^ (v1 + sum) ^ ((v1 >> 5) + k1);

替换成相应的逆运算

1
2
3

v0 ^= ((v1 << 4) + k0) ^ (v1 + sum) ^ ((v1 >> 5) + k1);
sum += delta;
v1 -= ((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3);

xxtea（btea）

xxtea不再是两个一组，而是整个uint32_t 数组传到第一个参数v，n表示数组长度，k作为密钥

#define DELTA 0x9e3779b9
#define MX ((z>>5^y<<2) + (y>>3^z<<4) ^ (sum^y) + (k[p&3^e]^z))
 
long btea(long* v, long n, long* k) {
  unsigned long z=v[n-1], y=v[0], sum=0, e;
  long p, q ;
  if (n > 1) {          /* Coding Part */
    q = 6 + 52/n;
    while (q-- > 0) {
      sum += DELTA;
      e = (sum >> 2) & 3;
      for (p=0; p<n-1; p++) y = v[p+1], z = v[p] += MX;
      y = v[0];
      z = v[n-1] += MX;
    }
    return 0 ; 
  } else if (n < -1) {  /* Decoding Part */
    n = -n;
    q = 6 + 52/n;
    sum = q*DELTA ;
    while (sum != 0) {
      e = (sum >> 2) & 3;
      for (p=n-1; p>0; p--) z = v[p-1], y = v[p] -= MX;
      z = v[n-1];
      y = v[0] -= MX;
      sum -= DELTA;
    }
    return 0;
  }
  return 1;
}

主要看下面加密部分，然后我将它稍微变得好看了一点

  #define DELTA 0x9e3779b9
 
  long btea(long* v, long n, long* k) {
    unsigned long pre=v[n-1], next=v[0], sum=0, e;
    long p, q ;
    q = 6 + 52/n;
    while (q-- > 0) {         //q轮加密
        sum += DELTA;
        for (p=0; p<n-1; p++) {
            next = v[p+1];
            v[p] += ((pre>>5^next<<2) + (next>>3^pre<<4) ^ (sum^next) + (k[p&3^((sum >> 2) & 3)]^pre));
            pre = v[p]
        }
	
        next = v[0];
        pre = v[n-1] += ((pre>>5^next<<2) + (next>>3^pre<<4) ^ (sum^next) + (k[p&3^((sum >> 2) & 3)]^pre));
    }
    return 0 ; 
}

for (p=0; p<n-1; p++) p遍历0~n-2

对v[p]+=((pre>>5^next<<2) + (next>>3^pre<<4) ^ (sum^next) + (k[p&3^((sum >> 2) & 3)]^pre));

其中pre不难看出为v[p-1]，即前一个元素；

如果是第0个元素，则前一个元素就是最后一个元素，相当于循环链表了

next是v[p+1]，即后一个元素；

如果是最后一个元素，则后一个元素就是第0个元素

因此我们还可以化简加密代码为

  #define DELTA 0x9e3779b9
 
  long btea(long* v, long n, long* k) {
    unsigned long sum=0;
    long p, q ;
    q = 6 + 52/n;
    while (q-- > 0) { 
        sum += DELTA;
        for (p=0; p<n; p++) {
            v[p] += ((v[(p-1)%n]>>5^v[(p+1)%n]<<2) + (v[(p+1)%n]>>3^v[(p-1)%n]<<4) ^ (sum^v[(p+1)%n]) + (k[p&3^((sum >> 2) & 3)]^v[(p-1)%n]));
        }
    }
    return 0 ; 
}

其中k=((v[(p-1)%n]>>5^v[(p+1)%n]<<2) + (v[(p+1)%n]>>3^v[(p-1)%n]<<4) ^ (sum^v[(p+1)%n]) + (k[p&3^((sum >> 2) & 3)]^v[(p-1)%n]))

显然所有变量都是已知的

同样的思路解密，用v[p]-=k即可

  #define DELTA 0x9e3779b9
 
  long btea(long* v, long n, long* k) {
    unsigned long sum=0;
    long p, q ;
    q = 6 + 52/n;
    while (q-- > 0) { 
        sum += DELTA;
        for (p=n-1; p>=0; p--) {
            v[p] -= ((v[(p-1)%n]>>5^v[(p+1)%n]<<2) + (v[(p+1)%n]>>3^v[(p-1)%n]<<4) ^ (sum^v[(p+1)%n]) + (k[p&3^((sum >> 2) & 3)]^v[(p-1)%n]));
        }
    }
    return 0 ; 
}

BASE64

char m[3];
char c[4];
char base64table="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
c[0] = base64table[(m[0] >> 2)];
c[1] = base64table[(((m[0] & 0x03) << 4) | (m[1] >> 4))];
c[2] = base64table[(((m[1] & 0x0F) << 2) | (m[2] >> 6))];
c[3] = base64table[(m[2] & 0x3F)];

直观来看，假如m=”fla”;

将其转化成二进制形式就是011001100110110001100001

每6位取一次

011001

100110

110001

100001

对应的ascii码分别是，25，38，49，33，用其作为base64table的下标，依次取值得到密文c=”Zmxh”

因为用6个bit位作为table的下标，所以table长度为2**6=64，所以叫base64

如何解密

显然你可以直接利用base64table找到密文c中所有字符对应的索引，然后转化成二进制一拼，再转化成字符串就能解密。但这里更希望新手能从bit位的角度出发来解密，因为上面做法无法处理一些魔改。

将index单独拎出来，解密的时候很显然。

1 2	base64table="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/" idx=[base64table.index(i) for i in c]

idx[0] = (m[0] >> 2);

低2位丢了，保留高6位。所以index[0]就是m[0]的高6位

idx[1] = (((m[0] & 0x03) << 4) | (m[1] >> 4));

0x3=0b11，m[0]& 0x03取了m[0]低2位，右移4后，m[0]低2位成为了idx[1]的高2位（因为c只有6位，右移4位，肯定就是高2位了）

m[1] >> 4，丢掉了低4位，保留了高4位，m[1]高4位作为idx[1]低4位

idx[2] = (((m[1] & 0x0F) << 2) | (m[2] >> 6));

0x0F=0b1111，m[1] & 0x0F取了m[1]低4位，右移2后，m[1]低4位成了idx[2]高4位

m[2] >> 6，丢掉了低6位，保留了高2位，m[2]高2位作为idx[2]低2位

idx[3] = (m[2] & 0x3F);

idx[3]位m[2]第6位

所以我们可以得到

//可以自行研究一下解密算法位运算的实现，和加密差不多
//m[0]的高6位就是idx[0],m[0]的低2位就是idx[1]的高2位
m[0]=(idx[1]>>4)|(idx[0]<<2)
//m[1]的高4位就是idx[1]的低4位,m[1]的低4位就是idx[2]的高4位
m[1]=(idx[2]>>2)|((idx[1]&0b1111)<<4)
//m[2]的高2位就是idx[2]的低2位,m[2]的低6位就是idx[3]
m[2]=(idx[3])|((idx[2]&0b11)<<6)

魔改

1.魔改base表

给base表换成别的，显然只影响最后的映射，解密直接套下来就行

2.魔改加密过程

m总共3*8等于24个bit，可以将其随意拼接成4*6的index

此时我们就得找到加密算法中中m的bit位分别到了idx的哪

例如下面算法：可以自己看看加密逻辑，谢谢解密算法

base64table="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
m=[ord(i) for i in "fla"]
c=""
for i in range(4):
    idx=0
    for j in range(3):
        idx|=(m[j]>>(4*i))&0b11
    c+=base64table[idx]
print(c)

CRC64

#include <stdio.h>
#include <stdint.h>
#include <string.h>

// CRC64 多项式
#define CRC64_POLY 0xF2F0E1EBA9EA3693ULL

// 初始化CRC64表
uint64_t crc64_table[256];

// 生成CRC64表
void generate_crc64_table() {
    uint64_t crc;
    for (int i = 0; i < 256; i++) {
        crc = i;
        for (int j = 0; j < 8; j++) {
            if (crc & 1)
                crc = (crc >> 1) ^ CRC64_POLY;
            else
                crc >>= 1;
        }
        crc64_table[i] = crc;
    }
}

// 计算CRC64值
uint64_t crc64(const void *data, size_t length) {
    uint64_t crc = 0xFFFFFFFFFFFFFFFFULL;
    const uint8_t *buf = (const uint8_t *)data;

    for (size_t i = 0; i < length; i++) {
        crc = crc64_table[(crc ^ buf[i]) & 0xFF] ^ (crc >> 8);
    }

    return crc ^ 0xFFFFFFFFFFFFFFFFULL;
}

可以看出crc64是校验算法而不是加密算法，在ctf中，通常利用生成CRC64表这步作为加密算法进行加密数据

uint64_t crc = m;            //8个字节
for (int j = 0; j < 8; j++) { //每一轮加密与j无关，所以每一轮加密都是一样的，单独拎出来一轮来看就行
    if (crc & 1)             //取最低位，判断是否为1，不管是否为1，下面crc都右移1，如果是1则额外异或0x42F0E1EBA9EA3693
        crc = (crc >> 1) ^ 0xF2F0E1EBA9EA3693;
    else
        crc >>= 1;
}
c = crc;

如何解密

if (crc & 1)             
    crc' = (crc >> 1) ^ 0xF2F0E1EBA9EA3693;
else
    crc' = crc >> 1;
c=crc';

加密后，我们有密文c，k=0xF2F0E1EBA9EA3693

显然需要先判断加密过程中走的哪条分支，即判断是否异或了k，分支是由crc&1得到的。但是，无论是哪一个分支，crc都右移了一位，低1位都没了，如何判断？

这里当时想了我很久，因为我当时不知道这是crc64。crc右移一位，最低位没了，但是最高位必定是0（区分一下循环移位，循环右移的化会将溢出的低位循环移到高位）。而0xF2F0E1EBA9EA3693的最高位是1，(crc >> 1) 最高位是0，如果异或了0xF2F0E1EBA9EA3693，那么其最高位就会变成1，而没有异或的话最高位还是0。

所以，通过最高位来判断是否异或了k，因此解密算法为

crc=c;
if (crc > 63)             
    crc = ((crc ^ 0xF2F0E1EBA9EA3693) << 1) | 1;     //最高位是1，说明原数据最低位是1，并且包含异或0xF2F0E1EBA9EA3693这一步
else
    crc = (crc << 1) | 0;           //最高位是0，最低位是0，并且不包含异或

魔改

给出了一些魔改版本的crc64加密算法，不说明解密过程了，思路和上面完全一样，可以自行思考。

魔改1

uint64_t crc = m;
for (int j = 0; j < 10; j++) {         //魔改轮数，解密轮数改成一样的就行
    if (crc > 63)                      //高低位逻辑交换了一下，解密用最低位判断分支
        crc = (crc << 1) ^ 0xF2F0E1EBA9EA3693;
    else
        crc <<= 1;
}
c = crc;

魔改2

uint64_t crc = m;
uint64_t key=[0xF2F0E1EBA9EA3691,0xF2F0E1EBA9EA3690,0xF2F0E1EBA9EA3693,0xF2F0E1EBA9EA3692]
for (int j = 0; j < 8; j++) {
    int index=crc>>62;            //加密利用高2位来取key；key中的低2位显然都是不一样的，解密的时候用低2位来判断
    crc=(crc<<2)^key[index];
}
c = crc;

SM4

sm4核心加密算法就

只需要通过

Xi=X(i+4)^T(X(i+1) ^ X(i+2) ^ X(i+3) ^ rki)

就能还原

待更……

AES

待更……

DES

待更……

逆向中如何手撕算法

主要分为四步

复现算法

通过输入测试明文，动态调试跟伪代码或者汇编，一句一句复现出对应的算法，调试器步进一步，写出对应的代码，然后看看代码运行出来的结果是否和调试器中的结果一致，一直复现完所有加密流程。用自己擅长或者适合的语言即可。

校验算法

更改测试明文，测试加密算法正确性

写出解密算法

解密算法基本参照前面逆算法的思路都能解密，除了对多个运算求逆，可能需要用到z3求解方程或者递归爆破等思路。

为啥要复现一遍算法写解密算法而不是对着解密？

1.复现算法便于你对加密算法的理解

2.防止伪代码错误，或者溢出等（溢出的话只要是跟汇编基本可以规避）导致的一些坑

3.写解密算法的时候出现错误，可以用写好的加密算法打印一些数据，解密算法也打印一些数据，定位错误代码

例如：

v1 += ((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3);

你可以将加密前的v1，打印出来，再将解密后的v1打印出来，如果解密后的v1==加密前的v1，那么这一句你的解密算法写的就没错，反之解密算法错了。

验证解密算法

能解开测试密文基本就没问题，然后带入密文解密出明文

ctf逆向-加密与解密

解密的常规思路

1.逆算法

对单个运算求逆运算

整体法

对多个运算求逆运算

2.爆破

逆向中常见的加密算法

基础运算

加减乘

除法

异或

与

RC4

如何解密

1.复现算法

2.trace获取密钥流

3.测试明文和测试密文进行异或

4.输入patch成密文

魔改

1.魔改密钥流生成

2.魔改加密

tea系列

tea，xtea

如何解密

魔改

1.魔改常量

魔改delta

魔改sum初始值（默认都是0）

魔改加密轮数

2.魔改加密表达式

魔改表达式顺序

魔改表达式运算

xxtea（btea）

BASE64

如何解密

魔改

1.魔改base表

2.魔改加密过程

CRC64

如何解密

魔改

魔改1

魔改2

SM4

AES

DES

逆向中如何手撕算法

复现算法

校验算法

写出解密算法

验证解密算法