简析加密算法

加密算法

Tea

TEA是Tiny Encryption Algorithm的缩写，以加密解密速度快，实现简单著称。TEA算法每一次可以操作64bit(8byte)，采用128bit(16byte)作为key，算法采用迭代的形式，推荐的迭代轮数是64轮，最少32轮。为解决TEA算法密钥表攻击的问题，TEA算法先后经历了几次改进，从XTEA到BLOCK TEA，直至最新的XXTEA。XTEA也称做TEAN，它使用与TEA相同的简单运算，但四个子密钥采取不正规的方式进行混合以阻止密钥表攻击。Block TEA算法可以对32位的任意整数倍长度的变量块进行加解密的操作，该算法将XTEA轮循函数依次应用于块中的每个字，并且将它附加于被应用字的邻字。XXTEA使用跟Block TEA相似的结构，但在处理块中每个字时利用了相邻字，且用拥有两个输入量的MX函数代替了XTEA轮循函数。上面提到的相邻字其实就是数组中相邻的项。

TEA系列算法中均使用了一个DELTA常数，但DELTA的值对算法并无什么影响，只是为了避免不良的取值，推荐DELTA的值取为黄金分割数(5√-2) / 2与232的乘积，取整后的十六进制值为0x9e3779B9，用于保证每一轮加密都不相同。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<string>
#include<cstring>
#include<list>
#include<stdlib.h>
using namespace std;

void TEA(uint32_t *v, uint32_t *k) {
    uint32_t v0 = v[0], v1 = v[1], sum = 0xC6EF3720, i;  // 根据TEA算法，解密轮次的计算需要初始化sum
    uint32_t delta = 0x9e3779b9;
 	
    for (i = 0; i < 32; i++) {
        sum += delta;
        v0 += ((v1 << 4) + k[0]) ^ (v1 + sum) ^ ((v1 >> 5) + k[1]);
        v1 += ((v0 << 4) + k[2]) ^ (v0 + sum) ^ ((v0 >> 5) + k[3]);
    }
 
    v[0] = v0;
    v[1] = v1;
}

void tea_decrypt(uint32_t* v, uint32_t* k) {
    uint32_t v0 = v[0], v1 = v[1], sum = 0xC6EF3720, 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++) {
        v1 -= ((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3) ;
        v0 -= ((v1 << 4) + k0) ^ (v1 + sum) ^ ((v1 >> 5) + k1) ;
        sum -= delta;

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

}
int main()
{

    uint32_t key[] = { 0x67626463,0x696D616E,0x79645F65,0x6B696C69 };

    uint32_t data[] = {
      0x31363010,0xAD938623, 0x8492D4C5, 0x7567E366, 0xC786696B, 0xA0092E31, 0xDB695733, 0xDD13A893, 0x88D8A53E, 0x7E845437
    };
    
    //WATCH OUT!!
    for (int i = 0; i < 10; i += 2) {
    tea_decrypt(&data[i], key);
    }
    
    printf("%s", data);

}     

Python版

from ctypes import *

def encrypt(v, k):
    v0 = c_uint32(v[0])
    v1 = c_uint32(v[1])
    summ = c_uint32(0)
    delta = 0x9e3779b9

    k0, k1, k2, k3 = c_uint32(k[0]), c_uint32(k[1]), c_uint32(k[2]), c_uint32(k[3])
    
    print("%#x %#x" % (v0.value, v1.value))
    print("%#x %#x %#x %#x" % (k0.value, k1.value, k2.value, k3.value))

    w = [0,0]
    for i in range(32):
        summ.value += delta
        v0.value += ((v1.value << 4) + k0.value) ^ (v1.value + summ.value) ^ ((v1.value >> 5) + k1.value)
        v1.value += ((v0.value << 4) + k2.value) ^ (v0.value + summ.value) ^ ((v0.value >> 5) + k3.value)
    w[0], w[1] = v0, v1
    return w

def decrypt(v, k):
    v0 = c_uint32(v[0])
    v1 = c_uint32(v[1])
    summ = c_uint32(0xC6EF3720)
    delta = 0x9e3779b9

    k0, k1, k2, k3 = c_uint32(k[0]), c_uint32(k[1]), c_uint32(k[2]), c_uint32(k[3])
    
    print("%#x %#x" % (v0.value, v1.value))
    print("%#x %#x %#x %#x" % (k0.value, k1.value, k2.value, k3.value))

    w = [0,0]
    for i in range(32):
        v1.value -= ((v0.value << 4) + k2.value) ^ (v0.value + summ.value) ^ ((v0.value >> 5) + k3.value)
        v0.value -= ((v1.value << 4) + k0.value) ^ (v1.value + summ.value) ^ ((v1.value >> 5) + k1.value)
        summ.value -= delta
    w[0], w[1] = v0, v1
    return w


v = [1,2]
k = [1,2,3,4]
ret = encrypt(v,k)
print("%#x %#x" % (ret[0].value, ret[1].value))
enc = [0xf99e87a6, 0xa5b88bf3]
dec = decrypt(enc,k)
print("%#x %#x" % (dec[0].value, dec[1].value))

TEA算法是较为基础的算法，在此基础上还有xTEA和xxTEA。

出题方式

直接C语言算法
特殊：使用特殊大数计算函数（ADD，SUB，MUL，XOR，ROL，ROR等），模拟SSA风格的计算方式
改变加密轮数或delta的值，变体TEA
delta的值不直接给，而是先拆成两个数字，然后在异或后得到delta，来防止被FindCrypt直接检测到

识别方式

简单的直接FindCrypt直接发现
识别特征值

xTea

XTEA是TEA的扩展，也称做TEAN，它使用与TEA相同的简单运算，同样是一个64位块的Feistel密码，使用128位密钥，建议64轮, 但四个子密钥采取不正规的方式进行混合以阻止密钥表攻击

xTEA的加密轮函数为：

v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[(sum >> 11) & 3]);
v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[sum & 3]);

XTEA算法在TEA算法的基础上进行了改进，主要改进有以下几点：

增加了迭代轮数：TEA算法迭代轮数为32轮，XTEA算法增加到了64轮，加强了加密强度。
改进了密钥扩展算法：XTEA算法的密钥扩展算法相对于TEA算法更为复杂和高效。
加入了反向迭代：XTEA算法加入了反向迭代，即加密和解密的过程完全相同。
可变的块大小：XTEA算法的块大小可变，可以是64位、128位等多种长度，提供了更加灵活的加密选项。
增加了数据完整性保护：XTEA算法可以通过增加MAC（Message Authentication Code）来保护数据完整性，防止数据在传输过程中被篡改。

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

//加密函数
void encrypt(unsigned int num_rounds, uint32_t v[2], uint32_t key[4]){
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9e3779b9;

    for(int 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]);
        //printf("%#x %#x\n",v0,v1);
    }
    v[0] = v0;
    v[1] = v1;
}

//解密函数
void decrypt(unsigned int num_rounds, uint32_t v[2], uint32_t key[4]){
    uint32_t v0=v[0], v1=v[1], delta=0x9e3779b9, sum=delta*num_rounds;
    for(int 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;
}


int main(void){
    uint32_t v[2]={1,2};
    uint32_t k[4]={1,2,3,4};
    unsigned int r=32;//加密轮数建议取值为32
    // v为要加密的数据是两个32位无符号整数
    // k为加密解密密钥，为4个32位无符号整数，即密钥长度为128位
    printf("%#x %#x\n",v[0],v[1]);
    encrypt(r, v, k);
    printf("%#x %#x\n",v[0],v[1]);
    decrypt(r, v, k);
    printf("%#x %#x\n",v[0],v[1]);
    return 0;
}

Python版

import sys
import os
from ctypes import *

def encrypt(num_rounds, v, key):
    v0, v1 = c_uint32(v[0]), c_uint32(v[1])
    summ = c_uint32(0)
    delta = 0x9e3779b9

    #print("%#10x %#10x" % (v0.value, v1.value))
    #print("%#10x" % (summ.value))

    for i in range(num_rounds):
        v0.value += (((v1.value << 4) ^ (v1.value >> 5)) + v1.value) ^ (summ.value + key[summ.value & 3])
        summ.value += delta
        v1.value += (((v0.value << 4) ^ (v0.value >> 5)) + v0.value) ^ (summ.value + key[(summ.value>>11) & 3])
        #print("%#10x %#10x" % (v0.value, v1.value))
    w = [v0.value, v1.value]
    return w

def decrypt(num_rounds, v, key):
    v0, v1 = c_uint32(v[0]), c_uint32(v[1])
    delta = 0x9e3779b9
    summ = c_uint32(delta*num_rounds)

    print("%#10x %#10x" % (v0.value, v1.value))

    for i in range(num_rounds):
        v1.value -= (((v0.value << 4) ^ (v0.value >> 5)) + v0.value) ^ (summ.value + key[(summ.value>>11)&3])
        summ.value -= delta
        v0.value -= (((v1.value << 4) ^ (v1.value >> 5)) + v1.value) ^ (summ.value + key[summ.value & 3])

    w = [v0.value, v1.value]
    return w

v = [1,2]
k = [1,2,3,4]

ret = encrypt(32,v,k)
print("%#x %#x" % (ret[0], ret[1]))
enc = [0xf4420bdd, 0xd58bca18]
dec = decrypt(32,enc,k)
print("%#x %#x" % (dec[0], dec[1]))

xxTea

XXTEA是一个非平衡Feistel网络分组密码，在可变长度块上运行，这些块是32位大小的任意倍数（最小64位），使用128位密钥, 是目前TEA系列中最安全的算法，但性能较上两种有所降低。

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#define DELTA 0x9e3779b9
#define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z)))
 
void btea(uint32_t *v, int n, uint32_t const key[4]){
    uint32_t y, z, sum;
    unsigned p, rounds, e;

    /* Coding Part */
    if (n > 1) {
        rounds = 6 + 52/n;
        sum = 0;
        z = v[n-1];
        do{
            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;
        }
        while (--rounds);
    }
    else if (n < -1)/* Decoding Part */{
        n = -n;
        rounds = 6 + 52/n;
        sum = rounds*DELTA;
        y = v[0];
        do{
            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;
        }
        while (--rounds);
    }
}
 
int main()
{
    uint32_t v[2]= {1,2};
    uint32_t const k[4]= {2,2,3,4};
    int n= 2; //n的绝对值表示v的长度，取正表示加密，取负表示解密
    // v为要加密的数据是两个32位无符号整数
    // k为加密解密密钥，为4个32位无符号整数，即密钥长度为128位
    
    /*方法1*/
    printf("%#10x %#10x\n",v[0],v[1]);
    btea(v, n, k);
    printf("%#10x %#10x\n",v[0],v[1]);
    btea(v, -n, k);
    printf("%#10x %#10x\n",v[0],v[1]);
    
    /*方法2*/
    int n1=abs(n);
    for (int i = 0; i < n1; i++)
    {
        //printf("0x%x ",v[i]);
		printf("%c%c%c%c",*((unsigned char*)&v[i] + 0) & 0xff ,*((unsigned char*)&v[i] + 1) & 0xff, *((unsigned char*)&v[i] + 2) & 0xff, *((unsigned char*)&v[i] + 3)&0xff);
    }
    
    return 0;
}

Python版

可以直接pip安装模块

pip install xxtea-py

使用–>

python2

import xxtea
text = "Hello World! 你好，中国！"
key = "1234567890"
encrypt_data = xxtea.encrypt(text, key)
decrypt_data = xxtea.decrypt(encrypt_data, key)
print(text == decrypt_data);

python3

import xxtea
text = "Hello World! 你好，中国！"
key = "1234567890"
encrypt_data = xxtea.encrypt(text, key)
decrypt_data = xxtea.decrypt_utf8(encrypt_data, key)
print(text == decrypt_data);

直接使用模块分析的话如果魔改了逻辑或者delta值被修改那么就不能用了，还是推荐使用cpp脚本修改方便

RC4

RC4是一种流密码算法，由Ron Rivest于1987年设计。RC4的名字源于它是“Rivest Cipher 4”的缩写。

RC4算法使用变量长度的密钥来生成伪随机比特流，该比特流可以与明文进行异或运算得到密文。RC4算法的特点是简单高效，适用于低带宽的网络通信。

RC4算法的核心是密钥调度算法（Key Scheduling Algorithm，KSA）和伪随机生成算法（Pseudo-Random Generation Algorithm，PRGA）。密钥调度算法将密钥按字节分成256个元素的S盒，然后对S盒进行混淆和置换，生成256个随机排列的字节，即密钥调度表。伪随机生成算法则使用密钥调度表和一个计数器来生成伪随机比特流。

RC4算法的加密过程如下：

初始化：创建一个256字节的S盒，使用密钥调度算法生成密钥调度表，并初始化计数器。
生成伪随机比特流：使用密钥调度表和计数器生成伪随机比特流。
明文加密：将明文与伪随机比特流进行异或运算得到密文。
重复步骤2和3：使用相同的密钥和初始化向量对每个数据块重复执行步骤2和3。

RC4算法的 解密过程与加密过程 相同，因为异或运算是可逆的。

需要注意的是，RC4算法的密钥长度不应太短，否则容易受到攻击。通常建议使用长度为128位或以上的密钥。此外，RC4算法在初始化时需要避免使用相同的密钥和初始化向量，否则会导致生成的伪随机比特流重复，从而降低加密强度。

加密步骤：

1.初始化s盒与t盒

 int Len = strlen(key);
 for(i=0;i<256;i++) {
        s[i]=i;
        T[i]=key[i%Len];
    }

2.初始化排列s盒

 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;
    }

3.产生密钥流

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;
}

完整加密解密函数

#include<stdio.h>
#include<string.h>
typedef unsigned longULONG;
 
/*初始化函数*/
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] = { 0 }, s2[256] = { 0 };//S-box
    char key[256] = { "justfortest" };
    char pData[512] = "这是一个用来加密的数据Data";
    unsigned long len = strlen(pData);
    int i;
 
    printf("pData=%s\n", pData);
    printf("key=%s,length=%d\n\n", key, strlen(key));
    rc4_init(s, (unsigned char*)key, strlen(key));//已经完成了初始化
    printf("完成对S[i]的初始化，如下：\n\n");
    for (i = 0; i<256; i++)
    {
        printf("%02X", s[i]);
        if (i && (i + 1) % 16 == 0)putchar('\n');
    }
    printf("\n\n");
    for (i = 0; i<256; i++)//用s2[i]暂时保留经过初始化的s[i]，很重要的！！！
    {
        s2[i] = s[i];
    }
    printf("已经初始化，现在加密:\n\n");
    rc4_crypt(s, (unsigned char*)pData, len);//加密
    printf("pData=%s\n\n", pData);
    printf("已经加密，现在解密:\n\n");
    //rc4_init(s,(unsignedchar*)key,strlen(key));//初始化密钥
    rc4_crypt(s2, (unsigned char*)pData, len);//解密
    printf("pData=%s\n\n", pData);
    return 0;
}

RC4 是由 KSA 和 PRGA 组成的算法，每次使用相同密钥加密会使生成的伪随机比特流相同，我们可以调试出执行完RC4的伪随机比特流，直接将密文和伪随机比特流进行异或直接得到明文

以下是分析伪随机比特流与密文进行异或的脚本

def ksa(key):
    key_length = len(key)
    S = list(range(256))
    j = 0
    for i in range(256):
        j = (j + S[i] + key[i % key_length]) % 256
        S[i], S[j] = S[j], S[i]
    return S

def prga(S):
    i = 0
    j = 0
    while True:
        i = (i + 1) % 256
        j = (j + S[i]) % 256
        S[i], S[j] = S[j], S[i]
        K = S[(S[i] + S[j]) % 256]
        yield K

def get_key_stream(key, length):
    S = ksa([ord(c) for c in key])
    key_stream_gen = prga(S)
    return bytes([next(key_stream_gen) for i in range(length)])

def xor_encrypt_decrypt(data, key_stream):
    result = bytearray(len(data))  # 创建一个与 data 长度相同的 bytearray
    for i in range(len(data)):
        result[i] = data[i] ^ key_stream[i]  # 逐字节进行 XOR 运算
    return bytes(result)

# 示例用法
key = "testkey"
plaintext = "flag{flag_for_test}"

# 密文转bytes
plaintext_bytes = plaintext.encode()

# 生成与密文同长度的密钥流
key_stream = get_key_stream(key, len(plaintext_bytes))
print("密钥流:",key_stream)
# 加密明文
ciphertext = xor_encrypt_decrypt(plaintext_bytes, key_stream)
print("密文:", ciphertext)

# 生成相同密钥流解密
key_stream = get_key_stream(key, len(ciphertext))

# 解密密文
decrypted_plaintext_bytes = xor_encrypt_decrypt(ciphertext, key_stream)
decrypted_plaintext = decrypted_plaintext_bytes.decode()
print("解密明文:", decrypted_plaintext)

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

void ksa(const unsigned char *key, int key_length, unsigned char *S) {
    int j = 0;
    for (int i = 0; i < 256; i++) {
        S[i] = i;
    }
    for (int i = 0; i < 256; i++) {
        j = (j + S[i] + key[i % key_length]) % 256;
        unsigned char temp = S[i];
        S[i] = S[j];
        S[j] = temp;
    }
}

void prga(unsigned char *S, unsigned char *key_stream, int length) {
    int i = 0, j = 0;
    for (int n = 0; n < length; n++) {
        i = (i + 1) % 256;
        j = (j + S[i]) % 256;
        unsigned char temp = S[i];
        S[i] = S[j];
        S[j] = temp;
        key_stream[n] = S[(S[i] + S[j]) % 256];
        printf("0x%02x,",key_stream[n]);
    }
}

void rc4(const unsigned char *key, int key_length, const unsigned char *input, unsigned char *output, int length) {
    unsigned char S[256];
    unsigned char key_stream[length];

    ksa(key, key_length, S);
    prga(S, key_stream, length);
    for (int i = 0; i < length; i++) {
        output[i] = input[i] ^ key_stream[i];
    }

}

int main() {
    const char *key = "testkey";
    const char *plaintext = "flag{flag_for_test}";
    int length = strlen(plaintext);

    unsigned char ciphertext[length];
    unsigned char decrypted_plaintext[length + 1]; // +1 for null terminator

    // 加密
    rc4( (unsigned char *)key , strlen(key) , (unsigned char *)plaintext , ciphertext, length);

    printf("密文: ");
    for (int i = 0; i < length; i++) {
        printf("0x%02X,", ciphertext[i]);
    }
    printf("\n");

    // 解密
    rc4( (unsigned char *)key , strlen(key) , ciphertext , decrypted_plaintext , length);
    decrypted_plaintext[length] = '\0'; // 添加 null terminator

    printf("解密明文: %s\n", decrypted_plaintext);

    return 0;
}

例如：

tmp = [0xEB, 0x0D, 0x61, 0x29, 0xBF, 0x9B, 0x05, 0x22, 0xF3, 0x32,
  0x28, 0x97, 0xE3, 0x86, 0x4D, 0x2D, 0x5A, 0x2A, 0xA3, 0x55,
  0xAA, 0xD5, 0xB4, 0x6C, 0x8B, 0x51, 0xB1]

key = [141,97,0,78,196,210,90,110,195,100,109,200,132,227,35,94,50,27,205,10,227,184,196,88,232,37,204]
for i in range(len(tmp)):
    print(chr(tmp[i] ^ key[i]),end='')   
# flag{I_L0VE_gensh1n_Imp4ct}

BASE

Base64原理 用一句话来说明Base64编码的原理：“把3个字节变成4个字节”。

这么说吧，3个字节一共24个bit，把这24个bit依次分成4个组，每个组6个bit，再把这6个bit塞到一个字节中去(最高位补两个0就变成8个bit)，就会变成4个字节。没了。

因为6个bit最多能表示2^6=64，也就是说Base64编码出来的字符种类只有64个，这也是Base64名字的由来。

那我们就要从ASCII中0x20 ~ 0x7E是可打印字符选出64个普通的ASCII字符

换表

import base64
import string
 
str1 = "AMHo7dLxUEabf6Z3PdWr6cOy75i4fdfeUzL17kaV7rG=" #待解秘字符串
 
string1 = "qaCpwYM2tO/RP0XeSZv8kLd6nfA7UHJ1No4gF5zr3VsBQbl9juhEGymc+WTxIiDK" #新表
string2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
 
print (base64.b64decode(str1.translate(str.maketrans(string1,string2))))

Rot

rot密码其实可以看作是凯撒密码的一种变式

本质都是移位运算

rot密码按种类大致分为以下几类

rot5：只将字符串中的数字进行加密，步数为5，同时在0-9十个数字进行循环，如1在rot5加密后为6，而6在rot5加密后为1

rot13：只将字符串中的字母进行加密，步数为13，加密方式上最接近凯撒密码，分别在A-Z或a-z之间循环，如A在rot13加密后为N,Z在rot13加密后为M

rot18:字面意思(5+13=18) 即将上述两种加密方式结合，分别对数字和字母进行相应的操作

rot47:由于无论是rot5、rot13或rot18都只能对数字和字母进行相应的加密，而对“！@#￥%&”之类的符号却缺少加密，因此在此基础上引入ASCII码

如果理解了上面的rot5、rot13、rot18，那么rot47也相当好理解了，只是将步数改为47而已（同样存在循环）

对数字、字母、常用符号进行编码，按照它们的ASCII值进行位置替换，用当前字符ASCII值往前数的第47位对应字符替换当前字符，例如当前为小写字母z，编码后变成大写字母K，当前为数字0，编码后变成符号_。

注意：用于ROT47编码的字符其ASCII值范围是33－126（原因是由于0-32以及127与字符表示无关！！）

Rot5

def rot5_encrypt(plaintext):
    ciphertext = ""
    for c in plaintext:
        if c.isdigit():
            new_digit = (int(c) + 5) % 10
            ciphertext += str(new_digit)
        else:
            ciphertext += c
    return ciphertext

def rot5_decrypt(ciphertext):
    plaintext = ""
    for c in ciphertext:
        if c.isdigit():
            new_digit = (int(c) - 5) % 10
            plaintext += str(new_digit)
        else:
            plaintext += c
    return plaintext

Rot13

def rot13_encrypt(plaintext: str) -> str:
    ciphertext = ""
    for c in plaintext:
        if c.isalpha():
            if c.isupper():
                new_ascii = (ord(c) - 65 + 13) % 26 + 65
            else:
                new_ascii = (ord(c) - 97 + 13) % 26 + 97
            ciphertext += chr(new_ascii)
        else:
            ciphertext += c
    return ciphertext


def rot13_decrypt(ciphertext: str) -> str:
    plaintext = ""
    for c in ciphertext:
        if c.isalpha():
            if c.isupper():
                new_ascii = (ord(c) - 65 - 13) % 26 + 65
            else:
                new_ascii = (ord(c) - 97 - 13) % 26 + 97
            plaintext += chr(new_ascii)
        else:
            plaintext += c
    return plaintext

Rot18

def rot18_encrypt(plaintext: str) -> str:
    ciphertext = ""
    for c in plaintext:
        if c.isalpha():
            if c.isupper():
                new_ascii = (ord(c) - 65 + 18) % 26 + 65
            else:
                new_ascii = (ord(c) - 97 + 18) % 26 + 97
            ciphertext += chr(new_ascii)
        else:
            ciphertext += c
    return rot5_encrypt(rot13_encrypt(plaintext))


def rot18_decrypt(ciphertext: str) -> str:
    plaintext = ""
    for c in ciphertext:
        if c.isalpha():
            if c.isupper():
                new_ascii = (ord(c) - 65 - 18) % 26 + 65
            else:
                new_ascii = (ord(c) - 97 - 18) % 26 + 97
            plaintext += chr(new_ascii)
        else:
            plaintext += c
    return rot5_decrypt(rot13_decrypt(ciphertext))

Rot47

# rot-47 解密
s = "nihao"
x = []
for i in range(len(s)):
    j = ord(s[i])  # 字符在ASCII中的序号
    if j >= 33 and j <= 126:  # 用于ROT47编码的字符其ASCII值范围是33－126
        x.append(chr(33 + ((j + 14) % 94)))
    else:
        x.append(s[i])
 
a = "".join(x)
print(a)

Z3 Solve

Z3 是一个微软出品的开源约束求解器，能够解决很多种情况下的给定部分约束条件寻求一组满足条件的解的问题功能强大且易于使用。

这个Z3可以用pip直接安装

pip install z3-solver

z3中有3种类型的变量，分别是整型(Int)，实型(Real)和向量(BitVec)。

对于整数类型数据，基本API：

Int(name, ctx=None)，创建一个整数变量，name是名字
Ints (names, ctx=None)，创建多个整数变量，names是空格分隔名字
IntVal (val, ctx=None)，创建一个整数常量，有初始值，没名字。

对于实数类型的API与整数类型一致，向量(BitVec)则稍有区别：

Bitvec(name,bv,ctx=None)，创建一个位向量，name是他的名字，bv表示大小
BitVecs(name,bv,ctx=None)，创建一个有多变量的位向量，name是名字，bv表示大小
BitVecVal(val,bv,ctx=None)，创建一个位向量，有初始值，没名字。

simplify(表达式)，对可以简化的表达式进行简化。

完整的API使用可以参考：完整API文档可参考：https://z3prover.github.io/api/html/namespacez3py.html

求解

二元一次方程

比如使用z3解二元一次方程：

$x-y = 3$

$3x-8y=4$

solve直接求解：

from z3 import *

x, y = Reals('x y')
solve(x-y == 3, 3*x-8*y == 4)

#[y = 1, x = 4]

如果需要取出指定变量的结果，可以使用Solver求解器：

s=solver()，创建一个解的对象。
s.add(条件)，为解增加一个限制条件
s.check()，检查解是否存在，如果存在，会返回”sat”
modul()，输出解得结果

x, y = Reals('x y')
solver = Solver()
qs = [x-y == 3, 3*x-8*y == 4]
for q in qs:
    solver.add(q)
if solver.check() == sat:
    result = solver.model()
print(result)
print("x =", result[x], ", y =", result[y])

#[y = 1, x = 4]
#x = 4 , y = 1

⚠️注意：没有push过的约束条件时直接pop会导致报出Z3Exception: b'index out of bounds'错误。

线性多项式约束

约束条件为：

x>2y<10x+2*y=7

上述约束x和y都是整数，我们需要找到其中一个可行解：

x, y = Ints('x y')
solve([x > 2, y < 10, x + 2*y == 7])

结果：

[y = 0, x = 7]

当然，实际可行的解不止这一个，z3只能找到其中一个可行的解。

非线性多项式约束

约束条件为：

$ x^2 + y^2 > 3 $

$ x^3 + y < 5 $

上述约束x和y都是实数，我们需要找到其中一个可行解：

x, y = Reals('x y')
solve(x**2 + y**2 > 3, x**3 + y < 5)

结果：

[y = 2, x = 1/8]

很快就计算出了一个可行解。

ChaCha20

Chacha20流密码经常和Poly1305消息认证码结合使用，被称为ChaCha20-Poly1305,由Google公司率先在Andriod移动平台中的Chrome中代替RC4使用

ChaCha20加密的初始状态包括了包括了

1、一个128位常量(Constant)

常量的内容为 0x61707865,0x3320646e,0x79622d32,0x6b206574

2、一个256位密钥(Key)

3、一个64位计数(Counter)

4、一个64位随机数(Nonce)

一共64字节其排列成4 * 4的32位字矩阵如下所示：（实际运算为小端

1/4轮操作

在ChaCha20算法当中, 一个基础的操作即为1/4轮运算, 它主要操作4个32位的无符号整数，具体操作如下:

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

块函数

(ChaCha20 Block Function)

这个块函数输入是之前所生成的状态矩阵, 最终输出64bit的”随机化”的字节, 具体操作如下所示:

static void chacha20_block(uint32_t in[16], uint8_t out[64], int num_rounds) { // num_rounds 一般为20 
    int i;
    uint32_t x[16];

    memcpy(x, in, sizeof(uint32_t) * 16);

    for (i = num_rounds; i > 0; i -= 2) {
        //odd round  // 奇数行变换
        chacha20_quarterround(x, 0, 4,  8, 12);
        chacha20_quarterround(x, 1, 5,  9, 13);
        chacha20_quarterround(x, 2, 6, 10, 14);
        chacha20_quarterround(x, 3, 7, 11, 15);
        //even round    // 偶数列变换
        chacha20_quarterround(x, 0, 5, 10, 15);
        chacha20_quarterround(x, 1, 6, 11, 12);
        chacha20_quarterround(x, 2, 7,  8, 13);
        chacha20_quarterround(x, 3, 4,  9, 14);
    }

    for (i = 0; i < 16; i++) {
        x[i] += in[i];
    }

    chacha20_serialize(x, out);
}

到这里, ChaCha20的基本原理就结束了, 整个密码结构并不是很复杂, 整体思路也比较清晰。

ChaCha20代码实现

Rust版本：

// https://datatracker.ietf.org/doc/html/rfc8439
pub struct ChaCha20 {
    state: [u32; 16],
}
fn quarter_round(state: &mut [u32; 16], a: usize, b: usize, c: usize, d: usize) {
    state[a] = state[a].wrapping_add(state[b]);
    state[d] = (state[d] ^ state[a]).rotate_left(16);
    state[c] = state[c].wrapping_add(state[d]);
    state[b] = (state[b] ^ state[c]).rotate_left(12);
    state[a] = state[a].wrapping_add(state[b]);
    state[d] = (state[d] ^ state[a]).rotate_left(8);
    state[c] = state[c].wrapping_add(state[d]);
    state[b] = (state[b] ^ state[c]).rotate_left(7);
}
impl ChaCha20 {
    pub fn new(key: [u32; 8], counter: u32, nonce: [u32; 3]) -> ChaCha20 {
        return ChaCha20 {
            state: [
                0x61707865, 0x3320646e, 0x79622d32, 0x6b206574,
                key[0], key[1], key[2], key[3],
                key[4], key[5], key[6], key[7],
                counter, nonce[0], nonce[1], nonce[2],
            ]
        };
    }
    fn chacha20_block(&mut self) -> Vec<u8> {
        let mut key_stream = vec![];
        let mut initial_state = self.state;
        for _ in 1..=10 {
            quarter_round(&mut initial_state, 0, 4, 8, 12);
            quarter_round(&mut initial_state, 1, 5, 9, 13);
            quarter_round(&mut initial_state, 2, 6, 10, 14);
            quarter_round(&mut initial_state, 3, 7, 11, 15);
            quarter_round(&mut initial_state, 0, 5, 10, 15);
            quarter_round(&mut initial_state, 1, 6, 11, 12);
            quarter_round(&mut initial_state, 2, 7, 8, 13);
            quarter_round(&mut initial_state, 3, 4, 9, 14);
        }
        for (index, value) in initial_state.iter().enumerate() {
            let new_value = self.state[index].wrapping_add(*value);
            for &x in new_value.to_le_bytes().iter() {
                key_stream.push(x);
            }
        }
        key_stream
    }
    pub fn encrypt(&mut self, message: &[u8]) -> Vec<u8> {
        let mut result = vec![];
        for chunk in message.chunks(64) {
            for (&key, value) in chunk.iter().zip(self.chacha20_block()) {
                result.push(key ^ value);
            }
            self.state[12] += 1;
        }
        return result;
    }
}
#[cfg(test)]
mod test {
    use crate::chacha20::ChaCha20;
    #[test]
    fn test() {
        let key = [0u32; 8];
        let nonce = [0x0u32; 3];
        let mut cc20 = ChaCha20::new(key, 1, nonce);
        let result = cc20.encrypt("1234".as_bytes());
        println!("{:?}", result);
    }
}

C语言：

#include <stdint.h>
#include <string.h>
#include "chacha20.h"

static inline void u32t8le(uint32_t v, uint8_t p[4]) {
    p[0] = v & 0xff;
    p[1] = (v >> 8) & 0xff;
    p[2] = (v >> 16) & 0xff;
    p[3] = (v >> 24) & 0xff;
}

static inline uint32_t u8t32le(uint8_t p[4]) {
    uint32_t value = p[3];

    value = (value << 8) | p[2];
    value = (value << 8) | p[1];
    value = (value << 8) | p[0];

    return value;
}

static inline uint32_t rotl32(uint32_t x, int n) {
    // http://blog.regehr.org/archives/1063
    return x << n | (x >> (-n & 31));
}

// https://tools.ietf.org/html/rfc7539#section-2.1
static void chacha20_quarterround(uint32_t *x, int a, int b, int c, int d) {
    x[a] += x[b]; x[d] = rotl32(x[d] ^ x[a], 16);
    x[c] += x[d]; x[b] = rotl32(x[b] ^ x[c], 12);
    x[a] += x[b]; x[d] = rotl32(x[d] ^ x[a],  8);
    x[c] += x[d]; x[b] = rotl32(x[b] ^ x[c],  7);
}

static void chacha20_serialize(uint32_t in[16], uint8_t output[64]) {
    int i;
    for (i = 0; i < 16; i++) {
        u32t8le(in[i], output + (i << 2));
    }
}

static void chacha20_block(uint32_t in[16], uint8_t out[64], int num_rounds) { // num_rounds 一般为20 
    int i;
    uint32_t x[16];

    memcpy(x, in, sizeof(uint32_t) * 16);

    for (i = num_rounds; i > 0; i -= 2) {    
        //odd round
        chacha20_quarterround(x, 0, 4,  8, 12);
        chacha20_quarterround(x, 1, 5,  9, 13);
        chacha20_quarterround(x, 2, 6, 10, 14);
        chacha20_quarterround(x, 3, 7, 11, 15);
        //even round 
        chacha20_quarterround(x, 0, 5, 10, 15);
        chacha20_quarterround(x, 1, 6, 11, 12);
        chacha20_quarterround(x, 2, 7,  8, 13);
        chacha20_quarterround(x, 3, 4,  9, 14);
    }

    for (i = 0; i < 16; i++) {
        x[i] += in[i];
    }

    chacha20_serialize(x, out);
}

// https://tools.ietf.org/html/rfc7539#section-2.3
static void chacha20_init_state(uint32_t s[16], uint8_t key[32], uint32_t counter, uint8_t nonce[12]) {
    int i;

    // refer: https://dxr.mozilla.org/mozilla-beta/source/security/nss/lib/freebl/chacha20.c
    // convert magic number to string: "expand 32-byte k"
    s[0] = 0x61707865;
    s[1] = 0x3320646e;
    s[2] = 0x79622d32;
    s[3] = 0x6b206574;

    for (i = 0; i < 8; i++) {
        s[4 + i] = u8t32le(key + i * 4);
    }

    s[12] = counter;

    for (i = 0; i < 3; i++) {
        s[13 + i] = u8t32le(nonce + i * 4);
    }
}

void ChaCha20XOR(uint8_t key[32], uint32_t counter, uint8_t nonce[12], uint8_t *in, uint8_t *out, int inlen) {
    int i, j;

    uint32_t s[16];
    uint8_t block[64];

    chacha20_init_state(s, key, counter, nonce);

    for (i = 0; i < inlen; i += 64) {
        chacha20_block(s, block, 20);
        s[12]++;

        for (j = i; j < i + 64; j++) {
            if (j >= inlen) {
                break;
            }
            out[j] = in[j] ^ block[j - i];
        }
    }
}

chacha20.h

#ifndef __CHACHA20_H
#define __CHACHA20_H
#include <stdint.h>

void ChaCha20XOR(uint8_t key[32], uint32_t counter, uint8_t nonce[12], uint8_t *input, uint8_t *output, int inputlen);

#endif

main.cpp

#include <stdio.h>
#include "chacha20.h"

int main(int argc, char **argv) {
    int i;

    uint8_t key[] = {
        0x00, 0x01, 0x02, 0x03,
        0x04, 0x05, 0x06, 0x07,
        0x08, 0x09, 0x0a, 0x0b,
        0x0c, 0x0d, 0x0e, 0x0f,
        0x10, 0x11, 0x12, 0x13,
        0x14, 0x15, 0x16, 0x17,
        0x18, 0x19, 0x1a, 0x1b,
        0x1c, 0x1d, 0x1e, 0x1f
    };

    uint8_t nonce[] = {                // 随机数 
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x4a, 0x00, 0x00, 0x00, 0x00
    };

    uint8_t input[114] = {
        0x4c, 0x61, 0x64, 0x69, 0x65, 0x73, 0x20, 0x61, 0x6e, 0x64, 0x20, 0x47, 0x65, 0x6e, 0x74, 0x6c,
        0x65, 0x6d, 0x65, 0x6e, 0x20, 0x6f, 0x66, 0x20, 0x74, 0x68, 0x65, 0x20, 0x63, 0x6c, 0x61, 0x73,
        0x73, 0x20, 0x6f, 0x66, 0x20, 0x27, 0x39, 0x39, 0x3a, 0x20, 0x49, 0x66, 0x20, 0x49, 0x20, 0x63,
        0x6f, 0x75, 0x6c, 0x64, 0x20, 0x6f, 0x66, 0x66, 0x65, 0x72, 0x20, 0x79, 0x6f, 0x75, 0x20, 0x6f,
        0x6e, 0x6c, 0x79, 0x20, 0x6f, 0x6e, 0x65, 0x20, 0x74, 0x69, 0x70, 0x20, 0x66, 0x6f, 0x72, 0x20,
        0x74, 0x68, 0x65, 0x20, 0x66, 0x75, 0x74, 0x75, 0x72, 0x65, 0x2c, 0x20, 0x73, 0x75, 0x6e, 0x73,
        0x63, 0x72, 0x65, 0x65, 0x6e, 0x20, 0x77, 0x6f, 0x75, 0x6c, 0x64, 0x20, 0x62, 0x65, 0x20, 0x69,
        0x74, 0x2e
    };

    uint8_t encrypt[114];
    uint8_t decrypt[114];

    ChaCha20XOR(key, 1, nonce, input, encrypt, 114);                //1 就是conter 
    ChaCha20XOR(key, 1, nonce, encrypt, decrypt, 114);

    printf("\nkey:");
    for (i = 0; i < 32; i++) {
        if (!(i % 16)) {
            printf("\n");
        }
        printf("%02x ", key[i]);
    }

    printf("\n\nnonce:\n");
    for (i = 0; i < 12; i++) {
        printf("%02x ", nonce[i]);
    }

    printf("\n\nplaintext:");
    for (i = 0; i < 114; i++) {
        if (!(i % 16)) {
            printf("\n");
        }
        printf("%02x ", input[i]);
    }

    printf("\n\nencrypted:");
    for (i = 0; i < 114; i++) {
        if (!(i % 16)) {
            printf("\n");
        }
        printf("%02x ", encrypt[i]);
    }

    printf("\n\ndecrypted:");
    for (i = 0; i < 114; i++) {
        if (!(i % 16)) {
            printf("\n");
        }
        printf("%02x ", decrypt[i]);
    }

    printf("\n");
    return 0;
}

Python版：

def main():
    runtests()

def chacha20_decrypt(key, counter, nonce, ciphertext):
    return chacha20_encrypt(key, counter, nonce, ciphertext)

def chacha20_encrypt(key, counter, nonce, plaintext):
    byte_length = len(plaintext)
    full_blocks = byte_length//64
    remainder_bytes = byte_length % 64
    encrypted_message = b''

    for i in range(full_blocks):
        key_stream = serialize(chacha20_block(key, counter + i, nonce))
        plaintext_block = plaintext[i*64:i*64+64]
        encrypted_block = [plaintext_block[j] ^ key_stream[j] for j in range(64)]
        encrypted_message += bytes(encrypted_block)
    if remainder_bytes != 0:
        key_stream = serialize(chacha20_block(key, counter + full_blocks, nonce))
        plaintext_block = plaintext[full_blocks*64:byte_length]
        encrypted_block = [plaintext_block[j] ^ key_stream[j] for j in range(remainder_bytes)]
        encrypted_message += bytes(encrypted_block)

    return encrypted_message

# returns a list of 16 32-bit unsigned integers
def chacha20_block(key, counter, nonce):
    BLOCK_CONSTANTS = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574]
    init_state = BLOCK_CONSTANTS + key + [counter] + nonce
    current_state = init_state[:]
    for i in range(10):
        inner_block(current_state)
    for i in range(16):
        current_state[i] = add_32(current_state[i], init_state[i])

    return current_state

def inner_block(state):
    # columns
    quarterround(state, 0, 4, 8, 12)
    quarterround(state, 1, 5, 9, 13)
    quarterround(state, 2, 6, 10, 14)
    quarterround(state, 3, 7, 11, 15)
    # diagonals
    quarterround(state, 0, 5, 10, 15)
    quarterround(state, 1, 6, 11, 12)
    quarterround(state, 2, 7, 8, 13)
    quarterround(state, 3, 4, 9, 14)

def xor_32(x, y):
    return (x ^ y) & 0xffffffff

def add_32(x, y):
    return (x + y) & 0xffffffff

def rot_l32(x, n):
    return ((x << n) | (x >> (32 - n))) & 0xffffffff

def quarterround(state, i1, i2, i3, i4):
    a = state[i1]
    b = state[i2]
    c = state[i3]
    d = state[i4]

    a = add_32(a, b); d = xor_32(d, a); d = rot_l32(d, 16)
    c = add_32(c, d); b = xor_32(b, c); b = rot_l32(b, 12)
    a = add_32(a, b); d = xor_32(d, a); d = rot_l32(d, 8)
    c = add_32(c, d); b = xor_32(b, c); b = rot_l32(b, 7)

    state[i1] = a
    state[i2] = b
    state[i3] = c
    state[i4] = d

def serialize(block):
    return b''.join([(word).to_bytes(4, 'little') for word in block])

# Test Vectors from RFC 8439
def runtests():

    key = [0x2519EB0A, 0x909CE82E, 0xD6C085EC, 0x545ACF07, 0x24124049, 0x1E1353E7, 0x14AD4F2F, 0xE98FF6DE] 
    plaintext = b"\x8e\x91\x9e\xbe\x6a\x6c\x64\xc1\x02\x02\xf8\xda\xc4\xc8\xd6\x14\xa0\xa3\x9c\x0e\x62\x64\x70\x6d\x02\x02\x0c\x9d\xd2\xd6\xc6\xa8"
    nonce = [0x7369C667, 0xEC4AFF51, 0xABBACD29]
    init_counter = 0x00000001
    ciphertext = chacha20_encrypt(key, init_counter, nonce, plaintext)
    for i in range(len(ciphertext)):
        print(hex(ciphertext[i])[2:],end = " ")
    assert(chacha20_decrypt(key, init_counter, nonce, ciphertext) == plaintext)

    print("All tests passed!")

main();

对CTF中的加密算法做一个简单总结

加密算法

Tea

xTea

xxTea

RC4

BASE

换表

Rot

Rot5

Rot13

Rot18

Rot47

Z3 Solve

求解

二元一次方程

线性多项式约束

非线性多项式约束

ChaCha20

1/4轮操作

块函数

ChaCha20代码实现

CATALOG

FEATURED TAGS

FRIENDS