常用编码和加密算法

1、CRC32（校验码）

• 循环冗余校验码，校验数据完整性。无法自动纠错。

• 逆向特征：

  • 0FFFFFFFFh
  • 0FFh
  • shr eax,8 xor eax,ebx
  • 256

    基本原理

• 在一个p位二进制数据序列之后附加一个r位二进制检验码(序列)，从而构成一个总长为n＝p＋r位的二进制序列；附加在数据序列之后的这个检验码与数据序列的内容之间存在着某种特定的关系。

• 一般用法：多项式模2运行（按位异或），当进行CRC检验时，需要事先约定一个除数，即生成多项式，一般记作G(x)。生成多项式比校验码多一位。生成多项式的最高位与最低位必须是1。当接收方收到数据后，用收到的数据对P（事先约定的）进行模2除法，若余数为0，则认为数据传输无差错；若余数不为0，则认为数据传输出现了错误
• 举例：CRC4
  • 需要发送的信息为M = 0011 1110，多项式对应的代码为P = 10011。在M后加4个0，然后对P做模2除法运算，得余数r(x)对应的代码：1110。故实际需要发送的数据是0011 1110 1110。

• 计算机计算
  • 可以假想出一个与生成项长度一致的“盒子”，取出一部分的数据出来若首位是1时就进行一次Xor，遇到0则左移到1为止，左移造成的右端的空缺用0补充。

• CRC数据表（驱动表法）

  • CRC4：2^4=16项（按4bit分解）
  • CRC32：2^8=256项（按8bit分解）
  • 通俗解释：想求一个数X = A xor B xor C xor D xor E xor F，但是这样一次一次xor多麻烦啊，如果你知道 Y = B xor C xor D xor E，就是其中的某一段，那么就可以直接xor啦，比如X = A xor Y xor F。CRC一次xor一位多麻烦啊，不如一次预先计算出8位也就是一个byte的xor结果，也就是256种，CRC的时候，你一看下面的8位是什么，直接去找事先计算好的就行啦。所以列表就好像是求出那个中间值Y，这样一次可以xor 8位。

    def calc_crc32(string): 
    return int(binascii.crc32(string) & 0xFFFFFFFF)

    算法逆向

• 开辟存放字符串的空间

  • GetWindowTextLengthA获取Name字符串的长度
• 进行CRC32计算

unsigned CRC32(char *c,int len){
        unsigned i,j;
        unsigned crc_i=0xFFFFFFFF;
        for(i=0;c!='\0';i++){
                j=(crc_i&0xFF) ^ (int)c;                
                crc_i=(crc_i>>8)^crc32_table[j%256];                
        }
        crc_i=crc_i^0xFFFFFFFF;
        printf("CRC32:%x,\n",crc_i);
        return crc_i;
}

2、MD5（散列算法 以64位二进制表示的填充前信息长度，512bit分组——>输出128bit）

• 逆向特点：

  • 四个幻数
  • 填充字符
  • 循环次数（64）
  • 查表（1～64）

    基本原理

    

• X[k],k=0…15

• T[i],i=0~63 查表
• 512bit经过4轮、每轮16步，每一步处理32bit

• 数据填充
  • 消息填充：在信息的后面填充一个1和无数个0，使其位长对512求余的结果等于448，并且填充必须进行，即使其位长对512求余的结果等于448。因此，信息的位长（Bits Length）将被扩展至N*512+448，N为一个非负整数，N可以是零。
  • 添加消息长度：在这个结果后面附加一个以64位二进制表示的填充前信息长度（单位为Bit），如果二进制表示的填充前信息长度超过64位，则取低64位。
  • 最终消息长度：N512+448+64=(N+1）512

• 初始化变量

  • MD5算法使用128bit长的缓冲区以存储中间结果和最终Hash值。缓冲区可初始化为4个32位长的幻数（A、B、C、D）

    A=0x67452301 B=0xefcdab89 C=0x98badcfe D=0x10325476

• 计算散列值（4轮）

  • 每一次循环都会让旧的ABCD产生新的ABCD
  • 假设处理后的原文长度是M，主循环次数 = M / 512，每个主循环中包含 （512 / 32） * 4 = 64 【4个步骤，每个步骤做16次，每次操作32bit输入】次 子循环（每次子循环如图）
  • 绿色F，代表非线性函数。官方MD5所用到的函数有四种。 在主循环下面64次子循环中，F、G、H、I 交替使用，第一个16次使用F，第二个16次使用G，第三个16次使用H，第四个16次使用I。（可以硬编码后查表）
    • F(X, Y, Z) =(X&Y) | ((~X) & Z)
    • G(X, Y, Z) =(X&Z) | (Y & (~Z))
    • H(X, Y, Z) =X^Y^Z
    • I(X, Y, Z)=Y^(X|(~Z))
  • 红色的田字代表相加
  • Mi是第一步处理后的原文。在第一步中，处理后原文的长度是512的整数倍。把原文的每512位再分成16等份，命名为M0~M15，每一等份长度32。在64次子循环中，每16次循环，都会交替用到M1~M16之一。
  • Ki一个常量，在64次子循环中，每一次用到的常量都是不同的。
  • 一次循环后结果
    • 新A = 原d
    • 新B = b+((a+F(b,c,d)+Mj+Ki)<<<s)
    • 新C = 原b
    • 新D = 原c

• 循环加工最终产生的A，B，C，D四个值拼接在一起，转换成字符串即可（128/4=32）

算法逆向

• 初始化：首先进行了一些初始化工作，初始化MD5中的A、B、C、D寄存器，并初始化一个变量赋值为0xC3D2E1F0，我们将其命名为E，这个值用于处理MD5后的数据。开辟64字节的缓冲区(64*8=512)

• 消息填充

• 计算每一轮散列值（4*16=64轮）

• 获得MD5

3、SHA1（散列算法 512位分组——>160bit）

• 逆向特点：
  • 五个幻数
  • 填充字符
  • 压缩函数执行（4）
  • FindCrypt插件识别出SHA-1常量

基本原理

• SHA-1也叫SHA-128，当消息长度小于2^64位时，使用SHA-1和SHA-256；当消息长度小于2^128位时，使用SHA-384和SHA-512。SHA-1的输出是160bit。与MD5不同的是SHA1的原始报文长度不能超过2的64次方，另外SHA1的明文长度从低位开始填充。
• 数据填充
  • 消息填充：和MD5的填充方法类似，填充后的消息长度为512*N-64
  • 消息长度填充：512N-64+64=512N，将消息按512bit分组，消息长度填入最后8字节中

• 初始化缓冲区

  • 使用160bit长的缓冲区存储中间结果和最终Hash值，缓冲区可初始化为5个32位长的幻数(5*32=160)

    A=0x67452301 B=0xEFCDAB89 C=0x98BADCFE D=0x10325476 E=0xC3D2E1F0

• 经过添加位数处理的明文，其长度正好为512位的整数倍，然后按512位的长度进行分组（block），可以划分成L份明文分组，我们用Y0，Y1，……YL-1表示这些明文分组。对于每一个明文分组，都要重复反复的处理，这些与MD5是相同的。

• 将512位的明文分组划分为16个子明文分组，每个子明文分组为32位。

• 16份子明文分组扩展为80份。扩充的方法如下。

  W t = M t , 当0≤t≤15
  W t = ( W t-3 ⊕ W t-8⊕ W t-14⊕ W t-16 )<<< 1, 当16≤t≤79

• 压缩函数处理：以分组为单位对消息进行处理，每一个分组都经过压缩函数处理，4轮，每一轮20步，第80步的迭代的输出再与第一轮的输入模2^32相加。

• sha2（8个幻数）

算法逆向

• 消息填充
  • 上图是MD5填充下图是SHA-1

• 初始化缓冲区

• 执行压缩函数（4个）

• 循环左移：rol == shl + shr
  • A<<<5=(A<<5)|(A>>0x1B) 【0x5+0x1B = 0x20 = 32】

• (X & Y) | ((~X) & Z)==((Z^Y)&X)^Z

• hashlib包可以进行爆破解密

4、Base64（编码算法）

• 逆向特征

  • 置换表：A-Z、a-z、0-9、+、/“ ，“=”（字母数字加除等）
  • 位运算操作

    基本原理

• 用6位表示一个可显示字符，使用含有65个字符的ASCII字符集：”A-Z、a-z、0-9、+、/“ ，“=”对字符串特殊处理。

• ASCII中一个字符8bit，而Base64用6bit表示一个可见字符，也就是说3个ASCII字节可以由4个Base64字符来表示。3个字节一组用于编码（3x8bit->4x6bit），6bit为一组作为索引。如果要编码的二进制数据不是3的倍数，Base64用\x00字节在末尾补足后，再在编码的末尾加上1个或2个=号，表示补了多少字节，解码的时候，会自动去掉。
• 首先我们需要将第一个字母G的二进制位从8位截取到6位，直接G>>2，前面自动补0则会得到00010001，也就是索引17，对应base64的表格得到字母R,第一个字母就替换完成了。编码的第二个值是由G的最后两个二进制位和u的前面四个二进制位拼接起来的，也就是说接下来应该将这两部分组合起来。如何得到第一个字母的最后两个字节呢，也是采用移位的方式：首先将第一个字母左移4位得到01110000，然后将01110000&0x30（十进制48，二进制00110000）得到。同样的，先将第二个字节右移四位以此得到需要拼接的部分。然后以类似的思路处理第三个字节。处理完毕将会得到新的四个字符。
• 一般用于在HTTP协议下传输二进制数据，由于HTTP协议是文本协议，所以在HTTP协议下传输二进制数据需要将二进制数据转换为字符数据，而且网络传输只能传输可打印字符

import base64
base64.b64encode()
base64.b64decode()

算法逆向

• 32bit数据
  • 32 bit 3 = 96 bit = 6bit 16 = 6bit4 4（每次处理24bit）

• 8bit数据

5、RSA（非对称加密，主流密钥长度【m】至少都是1024bits以上，0 < 明文长度 < m）

• 逆向特征

  • gmpy2（python包）：可以用来大素数生成
  • 能看到大整数n以及公钥e
  • 取模：idivq

    基本原理

• 用数论构造的、基于大合数因子分解困难性的公开密钥密码

• 乘法逆元(模反元素)：ab被n除的余数是1。这时，b就叫做a的乘法逆元(模反元素)。
• 欧拉函数：任意给定正整数n，计算小于n的正整数中与n互质的数的数目的方式就叫做欧拉函数，以φ(n)表示。如果n是质数，则 φ(n)=n-1 ，因为质数与小于它的每一个数，都构成互质关系。如果n可以分解成两个互质的整数之积，n = p1 × p2，则φ(n) =φ(p1p2) = φ(p1)φ(p2)=(p1-1)*(p2-1)。
• 欧拉定理：如果两个正整数a和n互质，则n的欧拉函数φ(n)可以让下面的等式成立：a^φ(n)=1 (mod n)
• 加解密算法描述
  • 生成密钥
    • 选两个保密的大素数p和q
    • 计算n=p*q，φ(n) =(p-1)(q-1)；
    • 选一整数e，满足1<e<φ(n)，且φ(n)与e互质；
    • 计算d，满足d*e=1 (mod φ(n))，即d是e在φ(n)下的乘法逆元，因e与φ(n)互素，由模运算可知，它的乘法逆元一定存在；
    • 以{e,n}为公钥，{d,n}为私钥；
  • 加密
    • 假设鲍勃要向爱丽丝发送加密信息m，他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意，m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。加密后把c发送给对方。

me ≡ c (mod n)

• 解密
  • cd ≡ m (mod n)

算法逆向

• 计算字符串长度（repne scas）

  • edi:存放字符串
  • al：存放字符x
  • repne scas byte ptr es:[edi] ：遍历字符串，每循环一次ecx-1，遇到字符x则停止

    cld
    xor eax，eax
    or ecx,-0x1     ;ecx=0xFFFFFFFF
    repne scas byte ptr es:[edi] ; [edi]=字符串
    not ecx
    dec ecx    ;计算出字符串长度

• me ≡ c (mod n)

6、DES（分组密码，对称加密，明文以64bit分组，密钥长64位，密钥事实上是56位参与DES运算【第8、16、24、32、40、48、56、64位是校验位】）

• 逆向特征

  • 各种查表（8个）
  • 组合（<<|）
  • 16轮

    基本原理

    

• 明文：L+R (32+32)

  • 高32bit：L = (uint32_t) (init_perm_res >> 32) & L64_MASK;//高32bit
  • 低32bit：R = (uint32_t) init_perm_res & L64_MASK;//低32bit

• IP置换（查表）：将输入的64位数据块按位重新组合，并把输出分为L0、R0两部分，每部分各长32位。

• 密钥置换（查表）：不考虑每个字节的第8位，DES的密钥由64位减至56位，每个字节的第8位作为奇偶校验位。产生的56位密钥查表生成。（打乱->移位->选择）

• 子密钥移位（查表）：在DES的每一轮中，从56位密钥产生出不同的48位子密钥，确定这些子密钥的方式如下：
  • 1) 将56位的密钥分成两部分，每部分28位。
  • 2) 根据轮数，这两部分分别循环左移1位或2位。每轮移动的位数查表。
• 子密钥压缩置换（查表）
  • 移动后，从56位查表中取出48位。

• E扩展置换（查表）：IP置换后获得的右半部分R0，将32位输入查表扩展为48位(分为4位×8组)输出。
• S盒代换（查表）：将48位的密钥盒扩展后的R0异或，将结果送入S盒进行替代运算。8个S盒，每个S盒输入6位，输出4位，6位中高低两位为行号，中间四位为列号，在S盒中查找对应数据替换。最终得到32bit输出
• P盒置换（查表）：按照映射表重新排列输入的32bit数据

• IP^-1置换（查表）：左右两部分合并作为输出，查表重新排列。

算法逆向

• 循环移位：

  for()
  {
    C = (0x0fffffff & (C << 1)) | (0x00000001 & (C >> 27));//循环移位
  }

• 高28bit和低28bit组合：permuted_choice_2 = (((uint64_t) C) << 28) | (uint64_t) D ;//C+D

• 查表置换：

  //count:表中项数（变换后的比特数）
  //count2:变换前的bit数
  #define L64_MASK 0x00000000ffffffff
  for (i = 0; i < count; i++) 
  {
    after <<= 1;//按位置换（按照IP置换后新生成的count bit）
    after |= (input >> (count2-table[i])) & LB64_MASK;//取出第IP[i]位放到第i位上，每次 & LB64_MASK，让这个位的0或1扩充到64bit
  }

• 没有符号文件的情况下，通过string定位main函数

• 确定key和明文（这里key和每一轮输入相同：v0+v1）

  
  
  
  

• IP

  
  
  
  
  
  

• 16轮生成子密钥

  • 置换选择PC1

• 将56bit的密钥分成两部分

• 移位（x16）

• 置换选择PC2（x16）

• f函数
  • E盒

• Si盒

• P盒

• 初始逆置换

  
  
  

7、3DES

• 3DES加密过程为：C=Ek3(Dk2(Ek1(P)))

3DES解密过程为：P=Dk1((EK2(Dk3(C)))
K1、K2、K3决定了算法的安全性，若三个密钥互不相同，本质上就相当于用一个长为168位的密钥进行加密。多年来，它在对付强力攻击时是比较安全的。若数据对安全性要求不那么高，K1可以等于K3。在这种情况下，密钥的有效长度为112位。

7、AES（分组密码，对称加密，分组大小128位，密钥长度也为128位）

• 逆向特征
  • 密钥
  • AES-128 经历10次轮询 / AES-192 经历12次轮询 / AES-256 经历14次轮询

    基本原理

    

• 轮密钥加（Add Round Key)
  • 明文和子密钥k[0]（两个输入都是128位）按字节异或操作

• 字节代换层(SubByte)
  • 通过S_box表完成从一个字节到另一个字节的映射，S_box表是一个拥有256个字节元素的数组，读取S_box数据的方法就是要将输入数据的每个字节的高四位作为第一个下标，第四位作为第二个下标

• 行位移层(Shift Rows)
  • 扩散

• 列混淆层(Mix Column)

  • 扩散
  • 列混合变换是通过矩阵相乘来实现的，经行移位后的状态矩阵与固定的矩阵相乘，得到混淆后的状态矩阵

• 密钥生成

  • 以列为单位进行的，一列是32Bit，四列组成子密钥共128Bit。生成子密钥的数量比AES算法的轮数多一个，因为第一个密钥加法层进行密钥漂白时也需要子密钥。密钥漂白是指在AES的输入和输出中都使用的子密钥的XOR加法。子密钥在图中都存储在W[0]、W[1]、…、W[43]的扩展密钥数组之中。

算法逆向

• 读入密钥（128位）

• 初始化AES加密子密钥生成的循环部分，首先拷贝用于密钥扩展的轮常量Rcon，该轮常量也可以用来识别该算法。

• subbyte

• AddRoundKey

• MixColumns

8、RC4（流密码，对称加密）

• 逆向特征

  • 逐字节加密
  • 初始密钥
  • KSA PRGA

    基本原理

• 依次加密明文中的每一个字节，解密的时候也是依次对密文中的每一个字节进行解密

• 初始化秘钥：根据输入的秘钥key，使用密钥调度算法（KSA）生成一个256字节的sbox。

  • KSA：根据密钥打乱 S 盒

    j = 0
    for i in range(256):
    j = (j+S[i]+ord(T[i]))%256
    S[i],S[j] = S[j],S[i]

• 再通过伪随机数生成算法（PRGA）得到密钥流（keystream）

  i = j = 0
  ans = ""
  for x in text:
    i = (i+1)%256
    j = (j+S[i])%256
    S[i],S[j] = S[j],S[i]
    t = (S[i]+S[j])%256
    k = S[t]
    ans += chr(ord(x)^k)

• 加密：密钥流与明文进行异或运算得到密文

• 解密：秘文与密钥流进行异或运算得到明文

算法逆向

• 定义加密密钥

• 初始化S盒

• 循环加密数据（每次取出一位）

9、LZW压缩算法

• 原先ASCII每个字符占1byte（8bit），想办法将字节压缩到少于8位
• 原理：将多个字符联合表示
• 编码举例：
  • 输入字符串：TOBEORNOTTOBEORTOBERORNOT
  • 初始字典

• 将经常出现的字符组合编写到字典中（字符串和数字的映射关系）

• 解码举例（输入code）
  • 倒推dictionary

10、TEA算法（密钥长度128bit，明文分组64bit）

• 特征识别：魔数特征 - 0xC6EF3720
• 对称加密，块密码
• 加密使用的数据为2个32位无符号整数，密钥为4个32位无符号整数即密钥长度为128位
• 采用与DES算法类似的Feistel结构，迭代的每次循环使用加法和移位操作，对明文和密钥进行扩散和混乱，实现明文的非线性变换。

块加密工作模式

EBC（电码本模式）

• 优点：简单、利于并行计算、无错误传播
• 缺点：不抗统计分析攻击
• 应用：单个数据、短数据

CBC（密文分组链接模式）

• 优点：安全性好，适合传输长报文
• 缺点：不利于并行计算、存在密文错误传播

CFB（密文反馈模式）

OFB（输出反馈模式）