对称加密算法&&Hash算法 文档

去年看对称加密算法写的一些文档，补了几个坑，剩下的坑有空再补（咕咕咕

对称加密算法

对称密钥算法（英语：Symmetric-key algorithm）又称为对称加密、私钥加密、共享密钥加密，是密码学中的一类加密算法。这类算法在加密和解密时使用相同的密钥，或是使用两个可以简单地相互推算的密钥。算法安全性依赖于加密算法强度以及密钥的保密。

常见的对称加密算法有DES、3DES、AES、SM4、Blowfish、IDEA、TEA、RC4、RC5、RC6。对称加密的速度比公钥加密快很多，在很多场合都需要对称加密。

DES、3DES

关于DES

DES(Data Encryption Standard)，是一种对称密钥块密码算法，分组大小为64位，密钥长度为56位（长度总共为64位，实际为56位，第8、16、24、32、40、48、56、64位是校验位）

3DES(Triple Data Encryption Algorithm)，相当于对每个数据块应用三次DES即（DES_encrypt(DES_decrypt(DES_encrypt(plainText)))

算法原理

IP表初始置换

64位明文通过IP初始置换表置换为L0（置换后的数据的前32位），R0（置换后的数据的后32位）

子密钥生成

通过PC1置换表将56位密钥置换位C0（置换后的数据的前28位），D0（置换后的数据的后32位）

将C0，D0分别循环位移（位移表固定{ 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1}）得到C1、D1

C1、D1合并，通过PC2置换表得到第一个子密钥K1

回到第二步继续循环，得到子密钥K2、K3、……、K16

迭代加密

f函数（16轮）

Ln = R(n - 1)；

Rn = L(n - 1)⊕f(Rn-1,kn-1)

其中涉及到E盒扩展、S盒压缩

Rn通过E盒由32位扩展到48位，而后与子密钥异或

异或得到的48位分为8个6位分组，分别进入S1——S8替换压缩，S盒有8个，每个64位，输入数据为6位，输出数据为4位，得到8个4位分组，即将48位数据通过S盒压缩成32位

S盒压缩得到的32位数据通过P盒置换得到新的32位数据

P盒置换得到的32位数据与Ln异或得到Rn+1

回到f函数继续迭代15轮（总共16轮）

将L16和R16整体互换位置（第16轮结束后）并且合并得到64位数据

输出

将得到的64位数据通过IP逆置换表置换得到64位数据并输出，这就是密文了

图解

图片来源于看雪会员Yangs的帖子，https://bbs.pediy.com/thread-90593.htm，我更正了少许错误

解密

解密过程与加密过程算法基本相同，唯一不同点的是子密钥要逆序使用，所以只要改变子密钥的顺序，逆序使用就可以得到明文了

DES加解密实现

C/C++实现

from https://cloud.tencent.com/developer/article/1016180

//from https://cloud.tencent.com/developer/article/1016180
#include <cstdio>
#include <cstring>

//  IP 初始置换表
const int IP_Init_Table[64] = {
    58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
    62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
    57, 49, 41, 33, 25, 17, 9,  1, 59, 51, 43, 35, 27, 19, 11, 3,
    61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7};

//  E 扩展表
const int E_Table[48] = {32, 1,  2,  3,  4,  5,  4,  5,  6,  7,  8,  9,
                         8,  9,  10, 11, 12, 13, 12, 13, 14, 15, 16, 17,
                         16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25,
                         24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1};

//  P 盒
const int P_Table[32] = {16, 7, 20, 21, 29, 12, 28, 17, 1,  15, 23,
                         26, 5, 18, 31, 10, 2,  8,  24, 14, 32, 27,
                         3,  9, 19, 13, 30, 6,  22, 11, 4,  25};

//  IP 逆置换表
const int IPR_Table[64] = {40, 8,  48, 16, 56, 24, 64, 32, 39, 7,  47, 15, 55,
                           23, 63, 31, 38, 6,  46, 14, 54, 22, 62, 30, 37, 5,
                           45, 13, 53, 21, 61, 29, 36, 4,  44, 12, 52, 20, 60,
                           28, 35, 3,  43, 11, 51, 19, 59, 27, 34, 2,  42, 10,
                           50, 18, 58, 26, 33, 1,  41, 9,  49, 17, 57, 25};

//  密钥第一次置换表
const int PC1_Table[56] = {
    57, 49, 41, 33, 25, 17, 9,  1,  58, 50, 42, 34, 26, 18, 10, 2,  59, 51, 43,
    35, 27, 19, 11, 3,  60, 52, 44, 36, 63, 55, 47, 39, 31, 23, 15, 7,  62, 54,
    46, 38, 30, 22, 14, 6,  61, 53, 45, 37, 29, 21, 13, 5,  28, 20, 12, 4};

//  密钥第二次置换表
const int PC2_Table[48] = {14, 17, 11, 24, 1,  5,  3,  28, 15, 6,  21, 10,
                           23, 19, 12, 4,  26, 8,  16, 7,  27, 20, 13, 2,
                           41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
                           44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32};

//  S 盒
const int S_Box[8][4][16] = {
    //  s1
    14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7, 0, 15, 7, 4, 14, 2,
    13, 1, 10, 6, 12, 11, 9, 5, 3, 8, 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7,
    3, 10, 5, 0, 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13,
    //  s2
    15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10, 3, 13, 4, 7, 15, 2, 8,
    14, 12, 0, 1, 10, 6, 9, 11, 5, 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9,
    3, 2, 15, 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9,
    //  s3
    10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8, 13, 7, 0, 9, 3, 4, 6,
    10, 2, 8, 5, 14, 12, 11, 15, 1, 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5,
    10, 14, 7, 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12,
    //  s4
    7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15, 13, 8, 11, 5, 6, 15,
    0, 3, 4, 7, 2, 12, 1, 10, 14, 9, 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14,
    5, 2, 8, 4, 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14,
    //  s5
    2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9, 14, 11, 2, 12, 4, 7,
    13, 1, 5, 0, 15, 10, 3, 9, 8, 6, 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6,
    3, 0, 14, 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3,
    //  s6
    12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11, 10, 15, 4, 2, 7, 12,
    9, 5, 6, 1, 13, 14, 0, 11, 3, 8, 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1,
    13, 11, 6, 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13,
    //  s7
    4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1, 13, 0, 11, 7, 4, 9, 1,
    10, 14, 3, 5, 12, 2, 15, 8, 6, 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0,
    5, 9, 2, 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12,
    //  s8
    13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7, 1, 15, 13, 8, 10, 3,
    7, 4, 12, 5, 6, 11, 0, 14, 9, 2, 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13,
    15, 3, 5, 8, 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11};

/*
 *  类型转换函数 I
 *  将 char 型转化为二进制形式
 *  8 * sizeof(char) = 8(位) 8 个字符 64 位
 */
void CharToBit(const char input[], int output[], int bits) {
  for (int j = 0; j < 8; j++) {
    for (int i = 0; i < 8; i++) {
      output[7 * (j + 1) - i + j] = (input[j] >> i) & 1;
    }
  }
}

/*
 *  类型转换函数 II
 *  将二进制形式转化为 char 型
 */
void BitToChar(const int intput[], char output[], int bits) {
  for (int j = 0; j < 8; j++) {
    for (int i = 0; i < 8; i++) {
      output[j] = output[j] * 2 + intput[i + 8 * j];
    }
  }
}

/*
 *  异或函数
 *  将数组 INA 和 INB 进行异或操作，并且保存在 INA 中
 */
void Xor(int* INA, int* INB, int len) {
  for (int i = 0; i < len; i++) {
    *(INA + i) = *(INA + i) ^ *(INB + i);
  }
}

/*
 *  IP 初始置换函数
 *  IP 根据 IP 初始置换表进行初始置换
 */
void IP_Init_Rep(const int input[64], int output[64], const int table[64]) {
  for (int i = 0; i < 64; i++) {
    output[i] = input[table[i] - 1];
  }
}

/*
 *  E 扩展置换函数
 *  根据 E 扩展表进行扩展
 */
void E_Extend(const int input[32], int output[48], const int table[48]) {
  for (int i = 0; i < 48; i++) {
    output[i] = input[table[i] - 1];
  }
}

/*
 *  P 置换函数
 *  根据 P 盒进行置换
 */
void P_Rep(const int input[32], int output[32], const int table[32]) {
  for (int i = 0; i < 32; i++) {
    output[i] = input[table[i] - 1];
  }
}

/*
 *  IP 逆置换函数
 *  IP 根据 IP 逆置换表进行置换
 */
void IP_Inv_Rep(const int input[64], int output[64], const int table[64]) {
  for (int i = 0; i < 64; i++) {
    output[i] = input[table[i] - 1];
  }
}

/*
 *  密匙第一次置换函数
 *  根据密匙第一次置换表进行置换
 */
void PC_1(const int input[64], int output[56], const int table[56]) {
  for (int i = 0; i < 56; i++) {
    output[i] = input[table[i] - 1];
  }
}

/*
 *  密匙第二次置换函数
 *  根据密匙第二次置换表进行置换
 */
void PC_2(const int input[56], int output[48], const int table[48]) {
  for (int i = 0; i < 48; i++) {
    output[i] = input[table[i] - 1];
  }
}

/*
 *  S 盒压缩函数
 *  根据 8 个 S 盒进行压缩
 */
void S_Comp(const int input[48], int output[32], const int table[8][4][16]) {
  int INT[8];
  for (int i = 0, j = 0; i < 48; i = i + 6) {
    INT[j] = table[j][(input[i] << 1) + (input[i + 5])]
                  [(input[i + 1] << 3) + (input[i + 2] << 2) +
                   (input[i + 3] << 1) + (input[i + 4])];
    j++;
  }
  for (int j = 0; j < 8; j++) {
    for (int i = 0; i < 4; i++) {
      output[3 * (j + 1) - i + j] = (INT[j] >> i) & 1;
    }
  }
}

/*
 *  轮迭代函数
 *  DES 核心迭代部分
 */
void F_func(const int input[32], int output[32], int subKey[48]) {
  int len = 48;
  int temp0[48] = {0};
  int temp1[32] = {0};
  E_Extend(input, temp0, E_Table);
  Xor(temp0, subKey, len);
  S_Comp(temp0, temp1, S_Box);
  P_Rep(temp1, output, P_Table);
}

/*
 *  密匙循环左移函数
 *  密匙在不同轮数都要进行不同的左移操作
 */
void RotateL(const int input[28], int output[28], int leftCount) {
  int len = 28;
  for (int i = 0; i < len; i++) {
    output[i] = input[(i + leftCount) % len];
  }
}

/*
 *  子密匙生成函数
 *  生成 subKey，在第 1、2、9、16 轮循环左移 1 位，其他轮循环左移 2 位
 */
void subKey_fun(const int input[64], int subKey[16][48]) {
  int loop0 = 1, loop1 = 2;
  int c[28], d[28];
  int pc_1[56] = {0};
  int pc_2[16][56] = {0};
  int rotatel_c[16][28] = {0};
  int rotatel_d[16][28] = {0};

  PC_1(input, pc_1, PC1_Table);
  for (int i = 0; i < 28; i++) {
    c[i] = pc_1[i];
    d[i] = pc_1[i + 28];
  }

  int leftCount = 0;
  for (int i = 1; i < 17; i++) {
    if (i == 1 || i == 2 || i == 9 || i == 16) {
      leftCount += loop0;
      RotateL(c, rotatel_c[i - 1], leftCount);
      RotateL(d, rotatel_d[i - 1], leftCount);
    } else {
      leftCount += loop1;
      RotateL(c, rotatel_c[i - 1], leftCount);
      RotateL(d, rotatel_d[i - 1], leftCount);
    }
  }

  for (int i = 0; i < 16; i++) {
    for (int j = 0; j < 28; j++) {
      pc_2[i][j] = rotatel_c[i][j];
      pc_2[i][j + 28] = rotatel_d[i][j];
    }
  }

  for (int i = 0; i < 16; i++) {
    PC_2(pc_2[i], subKey[i], PC2_Table);
  }
}

/*
 *  DES 加密函数
 *  传入明文 input 和密匙 inKey，获取 64 位二进制密文 output
 */
void DES_Efun(const char input[8], char inKey[8], char output[8]) {
  int ip[64] = {0};
  int output_1[64] = {0};
  int output_2[64] = {0};
  int subKeys[16][48];
  int chartobit[64] = {0};
  int key[64];
  int l[17][32], r[17][32];

  CharToBit(input, chartobit, 8);
  IP_Init_Rep(chartobit, ip, IP_Init_Table);
  CharToBit(inKey, key, 8);
  subKey_fun(key, subKeys);

  for (int i = 0; i < 32; i++) {
    l[0][i] = ip[i];
    r[0][i] = ip[32 + i];
  }
  for (int j = 1; j < 16; j++)  //  15 轮迭代
  {
    for (int k = 0; k < 32; k++) {
      l[j][k] = r[j - 1][k];
    }
    F_func(r[j - 1], r[j], subKeys[j - 1]);
    Xor(r[j], l[j - 1], 32);
  }

  int t = 0;
  for (t = 0; t < 32; t++)  //  第 16 轮迭代
  {
    r[16][t] = r[15][t];
  }
  F_func(r[15], l[16], subKeys[15]);
  Xor(l[16], l[15], 32);

  for (t = 0; t < 32; t++) {
    output_1[t] = l[16][t];
    output_1[32 + t] = r[16][t];
  }
  IP_Inv_Rep(output_1, output_2, IPR_Table);
  BitToChar(output_2, output, 8);
}

/*
 *  DES 解密函数
 *  传入 64 位二进制密文 input 和密匙 inKey 获取明文 output
 */
void DES_Dfun(char cipher[64], char inKey[8], char output[8]) {
  int ip[64] = {0};
  int output_1[64] = {0};
  int output_2[64] = {0};
  int subKeys[16][48];
  int key[64];
  int l[17][32], r[17][32];
  int input[64] = {0};
  CharToBit(cipher, input, 8);
  IP_Init_Rep(input, ip, IP_Init_Table);
  CharToBit(inKey, key, 8);
  subKey_fun(key, subKeys);
  for (int i = 0; i < 32; i++) {
    l[0][i] = ip[i];
    r[0][i] = ip[32 + i];
  }
  for (int j = 1; j < 16; j++)  //  15 轮迭代
  {
    for (int k = 0; k < 32; k++) {
      l[j][k] = r[j - 1][k];
    }
    F_func(r[j - 1], r[j], subKeys[16 - j]);
    Xor(r[j], l[j - 1], 32);
  }

  int t = 0;
  for (t = 0; t < 32; t++)  //  第 16 轮迭代
  {
    r[16][t] = r[15][t];
  }
  F_func(r[15], l[16], subKeys[0]);
  Xor(l[16], l[15], 32);

  for (t = 0; t < 32; t++) {
    output_1[t] = l[16][t];
    output_1[32 + t] = r[16][t];
  }
  IP_Inv_Rep(output_1, output_2, IPR_Table);
  BitToChar(output_2, output, 8);
}
//  DES_Efun(plain, key, cipher);
//  DES_Dfun(cipher, key, plain);
char plain[9] = {0};
char cipher[9] = {0x96, 0xd0, 0x02, 0x88, 0x78, 0xd5, 0x8c, 0x89};
char key[9] = "12345678";
int main() {
  char a = '0';

  puts("0.encrypt,1.decrypt");
  scanf("%c", &a);
  if (a == '0') {
    puts("input plain (8Bytes)");
    scanf("%s", plain);
    puts("input key (8Bytes)");
    scanf("%s", key);
    DES_Efun(plain, key, cipher);
    for (size_t i = 0; i < 8; i++) {
      printf("%.2x", (unsigned char)cipher[i]);
    }
    puts("");
    puts(cipher);
  } else if (a == '1') {
    puts("input cipher (8Bytes)");
    puts("such as 96 d0 02 88 78 d5 8c 89");
    //   scanf("%s",cipher);
    int cipherhex[8] = {0};
    for (size_t i = 0; i < 8; i++) {
      scanf("%x", &cipherhex[i]);
      cipher[i] = (char)cipherhex[i];
    }
    puts("input key (8Bytes)");
    scanf("%s", key);
    DES_Dfun(cipher, key, plain);
    for (size_t i = 0; i < 8; i++) {
      printf("%.2x", (unsigned char)plain[i]);
    }
    puts("");
    puts(plain);
  } else {
    // DES_Efun(plain, key, cipher);
    // puts("cipher:");
    // for (size_t i = 0; i < 8; i++) {
    //   printf("%.2x", (unsigned char)cipher[i]);
    // }
    // puts("");
    // puts(cipher);
    puts("plain:");
    DES_Dfun(cipher, key, plain);
    for (size_t i = 0; i < 8; i++) {
      printf("%.2x", (unsigned char)plain[i]);
    }
    puts("");
    puts(plain);
  }
  return 0;
}

DES的扩展3-DES

3DES使用“密钥包”，其包含3个DES密钥，K1，K2和K3，均为56位（除去奇偶校验位）。加密算法为：

也就是说，使用K1为密钥进行DES加密，再用K2为密钥进行DES“解密”，最后以K3进行DES加密。

而解密则为其反过程：

即以K3解密，以K2“加密”，最后以K1解密。

每次加密操作都只处理64位数据，称为一块。

无论是加密还是解密，中间一步都是前后两步的逆。这种做法提高了使用密钥选项2时的算法强度，并在使用密钥选项3时与DES兼容。

• 密钥选项1：三个密钥是独立的。
• 密钥选项2：K1和K2是独立的，而K3=K1
• 密钥选项3：三个密钥均相等，即K1=K2=K3

AES

关于AES

AES（Advanced Encryption Standard），是一种对称密钥块密码算法，分组大小为128位，密钥长度为128，192或256位

算法原理

加解密实现

from https://github.com/dhuertas/AES

/*
 * Advanced Encryption Standard
 * @author Dani Huertas
 * @email huertas.dani@gmail.com
 *
 * Based on the document FIPS PUB 197
 */
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
*Addition in GF(2 ^ 8) *
    http :  // en.wikipedia.org/wiki/Finite_field_arithmetic
            * /
             * http://en.wikipedia.org/wiki/Finite_field_arithmetic
 */
uint8_t gadd(uint8_t a, uint8_t b) {
  return a ^ b;
}

/*
 * Subtraction in GF(2^8)
 * http://en.wikipedia.org/wiki/Finite_field_arithmetic
 */
uint8_t gsub(uint8_t a, uint8_t b) {
  return a ^ b;
}

/*
 * Multiplication in GF(2^8)
 * http://en.wikipedia.org/wiki/Finite_field_arithmetic
 * Irreducible polynomial m(x) = x8 + x4 + x3 + x + 1
 *
 * NOTE: This function can be easily replaced with a look up table for a speed
 *       boost, at the expense of an increase in memory size (around 65 KB).
 */
uint8_t gmult(uint8_t a, uint8_t b) {
  uint8_t p = 0, i = 0, hbs = 0;

  for (i = 0; i < 8; i++) {
    if (b & 1) {
      p ^= a;
    }

    hbs = a & 0x80;
    a <<= 1;
    if (hbs)
      a ^= 0x1b;  // 0000 0001 0001 1011
    b >>= 1;
  }

  return (uint8_t)p;
}

/*
 * Addition of 4 byte words
 * m(x) = x4+1
 */
void coef_add(uint8_t a[], uint8_t b[], uint8_t d[]) {
  d[0] = a[0] ^ b[0];
  d[1] = a[1] ^ b[1];
  d[2] = a[2] ^ b[2];
  d[3] = a[3] ^ b[3];
}

/*
 * Multiplication of 4 byte words
 * m(x) = x4+1
 */
void coef_mult(uint8_t* a, uint8_t* b, uint8_t* d) {
  d[0] = gmult(a[0], b[0]) ^ gmult(a[3], b[1]) ^ gmult(a[2], b[2]) ^
         gmult(a[1], b[3]);
  d[1] = gmult(a[1], b[0]) ^ gmult(a[0], b[1]) ^ gmult(a[3], b[2]) ^
         gmult(a[2], b[3]);
  d[2] = gmult(a[2], b[0]) ^ gmult(a[1], b[1]) ^ gmult(a[0], b[2]) ^
         gmult(a[3], b[3]);
  d[3] = gmult(a[3], b[0]) ^ gmult(a[2], b[1]) ^ gmult(a[1], b[2]) ^
         gmult(a[0], b[3]);
}

/*
 * The cipher Key.
 */
int K;

/*
 * Number of columns (32-bit words) comprising the State. For this
 * standard, Nb = 4.
 */
int Nb = 4;

/*
 * Number of 32-bit words comprising the Cipher Key. For this
 * standard, Nk = 4, 6, or 8.
 */
int Nk;

/*
 * Number of rounds, which is a function of  Nk  and  Nb (which is
 * fixed). For this standard, Nr = 10, 12, or 14.
 */
int Nr;

/*
 * S-box transformation table
 */
static uint8_t s_box[256] = {
    // 0     1     2     3     4     5     6     7     8     9     a     b     c
    // d     e     f
    0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5,
    0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,  // 0
    0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0,
    0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,  // 1
    0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc,
    0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,  // 2
    0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a,
    0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,  // 3
    0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0,
    0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,  // 4
    0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b,
    0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,  // 5
    0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85,
    0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,  // 6
    0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5,
    0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,  // 7
    0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17,
    0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,  // 8
    0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88,
    0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,  // 9
    0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c,
    0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,  // a
    0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9,
    0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,  // b
    0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6,
    0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,  // c
    0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e,
    0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,  // d
    0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94,
    0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,  // e
    0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68,
    0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16};  // f

/*
 * Inverse S-box transformation table
 */
static uint8_t inv_s_box[256] = {
    // 0     1     2     3     4     5     6     7     8     9     a     b     c
    // d     e     f
    0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38,
    0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb,  // 0
    0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87,
    0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb,  // 1
    0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d,
    0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e,  // 2
    0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2,
    0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25,  // 3
    0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16,
    0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92,  // 4
    0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda,
    0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84,  // 5
    0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a,
    0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06,  // 6
    0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02,
    0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b,  // 7
    0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea,
    0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73,  // 8
    0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85,
    0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e,  // 9
    0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89,
    0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b,  // a
    0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20,
    0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4,  // b
    0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31,
    0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f,  // c
    0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d,
    0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef,  // d
    0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0,
    0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61,  // e
    0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26,
    0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d};  // f

/*
 * Generates the round constant Rcon[i]
 */
uint8_t R[] = {0x02, 0x00, 0x00, 0x00};

uint8_t* Rcon(uint8_t i) {
  if (i == 1) {
    R[0] = 0x01;  // x^(1-1) = x^0 = 1
  } else if (i > 1) {
    R[0] = 0x02;
    i--;
    while (i - 1 > 0) {
      R[0] = gmult(R[0], 0x02);
      i--;
    }
  }

  return R;
}

/*
 * Transformation in the Cipher and Inverse Cipher in which a Round
 * Key is added to the State using an XOR operation. The length of a
 * Round Key equals the size of the State (i.e., for Nb = 4, the Round
 * Key length equals 128 bits/16 bytes).
 */
void add_round_key(uint8_t* state, uint8_t* w, uint8_t r) {
  uint8_t c;

  for (c = 0; c < Nb; c++) {
    state[Nb * 0 + c] =
        state[Nb * 0 + c] ^
        w[4 * Nb * r + 4 * c + 0];  // debug, so it works for Nb !=4
    state[Nb * 1 + c] = state[Nb * 1 + c] ^ w[4 * Nb * r + 4 * c + 1];
    state[Nb * 2 + c] = state[Nb * 2 + c] ^ w[4 * Nb * r + 4 * c + 2];
    state[Nb * 3 + c] = state[Nb * 3 + c] ^ w[4 * Nb * r + 4 * c + 3];
  }
}

/*
 * Transformation in the Cipher that takes all of the columns of the
 * State and mixes their data (independently of one another) to
 * produce new columns.
 */
void mix_columns(uint8_t* state) {
  uint8_t a[] = {0x02, 0x01, 0x01,
                 0x03};  // a(x) = {02} + {01}x + {01}x2 + {03}x3
  uint8_t i, j, col[4], res[4];

  for (j = 0; j < Nb; j++) {
    for (i = 0; i < 4; i++) {
      col[i] = state[Nb * i + j];
    }

    coef_mult(a, col, res);

    for (i = 0; i < 4; i++) {
      state[Nb * i + j] = res[i];
    }
  }
}

/*
 * Transformation in the Inverse Cipher that is the inverse of
 * MixColumns().
 */
void inv_mix_columns(uint8_t* state) {
  uint8_t a[] = {0x0e, 0x09, 0x0d,
                 0x0b};  // a(x) = {0e} + {09}x + {0d}x2 + {0b}x3
  uint8_t i, j, col[4], res[4];

  for (j = 0; j < Nb; j++) {
    for (i = 0; i < 4; i++) {
      col[i] = state[Nb * i + j];
    }

    coef_mult(a, col, res);

    for (i = 0; i < 4; i++) {
      state[Nb * i + j] = res[i];
    }
  }
}

/*
 * Transformation in the Cipher that processes the State by cyclically
 * shifting the last three rows of the State by different offsets.
 */
void shift_rows(uint8_t* state) {
  uint8_t i, k, s, tmp;

  for (i = 1; i < 4; i++) {
    // shift(1,4)=1; shift(2,4)=2; shift(3,4)=3
    // shift(r, 4) = r;
    s = 0;
    while (s < i) {
      tmp = state[Nb * i + 0];

      for (k = 1; k < Nb; k++) {
        state[Nb * i + k - 1] = state[Nb * i + k];
      }

      state[Nb * i + Nb - 1] = tmp;
      s++;
    }
  }
}

/*
 * Transformation in the Inverse Cipher that is the inverse of
 * ShiftRows().
 */
void inv_shift_rows(uint8_t* state) {
  uint8_t i, k, s, tmp;

  for (i = 1; i < 4; i++) {
    s = 0;
    while (s < i) {
      tmp = state[Nb * i + Nb - 1];

      for (k = Nb - 1; k > 0; k--) {
        state[Nb * i + k] = state[Nb * i + k - 1];
      }

      state[Nb * i + 0] = tmp;
      s++;
    }
  }
}

/*
 * Transformation in the Cipher that processes the State using a non­
 * linear byte substitution table (S-box) that operates on each of the
 * State bytes independently.
 */
void sub_bytes(uint8_t* state) {
  uint8_t i, j;
  uint8_t row, col;

  for (i = 0; i < 4; i++) {
    for (j = 0; j < Nb; j++) {
      row = (state[Nb * i + j] & 0xf0) >> 4;
      col = state[Nb * i + j] & 0x0f;
      state[Nb * i + j] = s_box[16 * row + col];
    }
  }
}

/*
 * Transformation in the Inverse Cipher that is the inverse of
 * SubBytes().
 */
void inv_sub_bytes(uint8_t* state) {
  uint8_t i, j;
  uint8_t row, col;

  for (i = 0; i < 4; i++) {
    for (j = 0; j < Nb; j++) {
      row = (state[Nb * i + j] & 0xf0) >> 4;
      col = state[Nb * i + j] & 0x0f;
      state[Nb * i + j] = inv_s_box[16 * row + col];
    }
  }
}

/*
 * Function used in the Key Expansion routine that takes a four-byte
 * input word and applies an S-box to each of the four bytes to
 * produce an output word.
 */
void sub_word(uint8_t* w) {
  uint8_t i;

  for (i = 0; i < 4; i++) {
    w[i] = s_box[16 * ((w[i] & 0xf0) >> 4) + (w[i] & 0x0f)];
  }
}

/*
 * Function used in the Key Expansion routine that takes a four-byte
 * word and performs a cyclic permutation.
 */
void rot_word(uint8_t* w) {
  uint8_t tmp;
  uint8_t i;

  tmp = w[0];

  for (i = 0; i < 3; i++) {
    w[i] = w[i + 1];
  }

  w[3] = tmp;
}

/*
 * Key Expansion
 */
void aes_key_expansion(uint8_t* key, uint8_t* w) {
  uint8_t tmp[4];
  uint8_t i, j;
  uint8_t len = Nb * (Nr + 1);

  for (i = 0; i < Nk; i++) {
    w[4 * i + 0] = key[4 * i + 0];
    w[4 * i + 1] = key[4 * i + 1];
    w[4 * i + 2] = key[4 * i + 2];
    w[4 * i + 3] = key[4 * i + 3];
  }

  for (i = Nk; i < len; i++) {
    tmp[0] = w[4 * (i - 1) + 0];
    tmp[1] = w[4 * (i - 1) + 1];
    tmp[2] = w[4 * (i - 1) + 2];
    tmp[3] = w[4 * (i - 1) + 3];

    if (i % Nk == 0) {
      rot_word(tmp);
      sub_word(tmp);
      coef_add(tmp, Rcon(i / Nk), tmp);

    } else if (Nk > 6 && i % Nk == 4) {
      sub_word(tmp);
    }

    w[4 * i + 0] = w[4 * (i - Nk) + 0] ^ tmp[0];
    w[4 * i + 1] = w[4 * (i - Nk) + 1] ^ tmp[1];
    w[4 * i + 2] = w[4 * (i - Nk) + 2] ^ tmp[2];
    w[4 * i + 3] = w[4 * (i - Nk) + 3] ^ tmp[3];
  }
}

/*
 * Initialize AES variables and allocate memory for expanded key
 */
uint8_t* aes_init(size_t key_size) {
  switch (key_size) {
    default:
    case 16:
      Nk = 4;
      Nr = 10;
      break;
    case 24:
      Nk = 6;
      Nr = 12;
      break;
    case 32:
      Nk = 8;
      Nr = 14;
      break;
  }

  return malloc(Nb * (Nr + 1) * 4);
}

/*
 * Performs the AES cipher operation
 */
void aes_cipher(uint8_t* in, uint8_t* out, uint8_t* w) {
  uint8_t state[4 * Nb];
  uint8_t r, i, j;

  for (i = 0; i < 4; i++) {
    for (j = 0; j < Nb; j++) {
      state[Nb * i + j] = in[i + 4 * j];
    }
  }

  add_round_key(state, w, 0);

  for (r = 1; r < Nr; r++) {
    sub_bytes(state);
    shift_rows(state);
    mix_columns(state);
    add_round_key(state, w, r);
  }

  sub_bytes(state);
  shift_rows(state);
  add_round_key(state, w, Nr);

  for (i = 0; i < 4; i++) {
    for (j = 0; j < Nb; j++) {
      out[i + 4 * j] = state[Nb * i + j];
    }
  }
}

/*
 * Performs the AES inverse cipher operation
 */
void aes_inv_cipher(uint8_t* in, uint8_t* out, uint8_t* w) {
  uint8_t state[4 * Nb];
  uint8_t r, i, j;

  for (i = 0; i < 4; i++) {
    for (j = 0; j < Nb; j++) {
      state[Nb * i + j] = in[i + 4 * j];
    }
  }

  add_round_key(state, w, Nr);

  for (r = Nr - 1; r >= 1; r--) {
    inv_shift_rows(state);
    inv_sub_bytes(state);
    add_round_key(state, w, r);
    inv_mix_columns(state);
  }

  inv_shift_rows(state);
  inv_sub_bytes(state);
  add_round_key(state, w, 0);

  for (i = 0; i < 4; i++) {
    for (j = 0; j < Nb; j++) {
      out[i + 4 * j] = state[Nb * i + j];
    }
  }
}

#include <stdio.h>
#include <stdlib.h>

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

  /*
   * Appendix A - Key Expansion Examples
   */

  /* 128 bits */
  /* uint8_t key[] = {
          0x2b, 0x7e, 0x15, 0x16,
          0x28, 0xae, 0xd2, 0xa6,
          0xab, 0xf7, 0x15, 0x88,
          0x09, 0xcf, 0x4f, 0x3c}; */

  /* 192 bits */
  /* uint8_t key[] = {
          0x8e, 0x73, 0xb0, 0xf7,
          0xda, 0x0e, 0x64, 0x52,
          0xc8, 0x10, 0xf3, 0x2b,
          0x80, 0x90, 0x79, 0xe5,
          0x62, 0xf8, 0xea, 0xd2,
          0x52, 0x2c, 0x6b, 0x7b}; */

  /* 256 bits */
  /* uint8_t key[] = {
          0x60, 0x3d, 0xeb, 0x10,
          0x15, 0xca, 0x71, 0xbe,
          0x2b, 0x73, 0xae, 0xf0,
          0x85, 0x7d, 0x77, 0x81,
          0x1f, 0x35, 0x2c, 0x07,
          0x3b, 0x61, 0x08, 0xd7,
          0x2d, 0x98, 0x10, 0xa3,
          0x09, 0x14, 0xdf, 0xf4};
  */

  /* uint8_t in[] = {
          0x32, 0x43, 0xf6, 0xa8,
          0x88, 0x5a, 0x30, 0x8d,
          0x31, 0x31, 0x98, 0xa2,
          0xe0, 0x37, 0x07, 0x34}; // 128
  */

  uint8_t key[] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77,
                   0x88, 0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee, 0xff};

  uint8_t in[] = {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77,
                  0x88, 0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee, 0xff};

  uint8_t out[16];  // 128

  uint8_t* w;  // expanded key

  w = aes_init(sizeof(key));

  aes_key_expansion(key, w);

  printf("Plaintext message:\n");
  for (i = 0; i < 4; i++) {
    printf("%x %x %x %x ", in[4 * i + 0], in[4 * i + 1], in[4 * i + 2],
           in[4 * i + 3]);
  }

  printf("\n");

  aes_cipher(in /* in */, out /* out */, w /* expanded key */);

  printf("Ciphered message:\n");
  for (i = 0; i < 4; i++) {
    printf("%x %x %x %x ", out[4 * i + 0], out[4 * i + 1], out[4 * i + 2],
           out[4 * i + 3]);
  }

  printf("\n");

  aes_inv_cipher(out, in, w);

  printf("Original message (after inv cipher):\n");
  for (i = 0; i < 4; i++) {
    printf("%x %x %x %x ", in[4 * i + 0], in[4 * i + 1], in[4 * i + 2],
           in[4 * i + 3]);
  }

  printf("\n");

  free(w);

  exit(0);
}

IDEA

关于IDEA

国际数据加密算法（IDEA）是来学嘉与James Massey联合提出的。这种算法是在DES算法的基础上发展出来的，类似于三重DES。分组长度为64位，密钥长度为128位，算法使用3种不同代数群操作。

算法原理

子密钥生成

IDEA密钥长度为128位，子密钥长度为16位共52个

a.128位密钥分为8个16位分组，直接作为前八个子密钥

b.128位密钥循环左移25位，生成的128位密钥分为8个16位分组，作为接下来的8个子密钥

c.继续执行步骤b，直至52个子密钥全部生成完毕

IDEA加密

64为明文被分成4个16位分组。每一轮加密都需要6个子密钥，最后的输出变换只需要4个子密钥，所以共需8*6+4=52个子密钥。一轮加密中，4个16位子密钥分别通过2个模2^16+1（65537）乘法和2个模2^16(65536)加法运算与明文混合，并用2个16位子密钥按位异或对结果进行处理，前一轮加密结果作为后一轮加密的输入。总共进行8轮加密，最后用4个子密钥变换输出最终的密文。

IDEA解密

解密过程同加密过程，唯一不同的是子密钥不同。

解密所需的52个子密钥是加密子密钥相对于不同操作运输的逆元，且解密时子密钥使用顺序相反。（乘法逆元可以通过扩展欧几里得算法求出）

加解密实现

// https://github.com/razvanalex/IDEA-encryption-algorithm
#include <stdio.h>
#include <string.h>

typedef __uint32_t uint32_t;
typedef __int32_t int32_t;
typedef __uint16_t uint16_t;
typedef void (*idea_gen_key)(uint16_t[52], uint16_t[8]);

uint16_t mulMod65537(uint16_t a, uint16_t b) {
  uint32_t c;
  uint16_t hi, lo;

  if (a == 0)
    return -b + 1;
  if (b == 0)
    return -a + 1;

  c = (uint32_t)a * (uint32_t)b;
  hi = c >> 16;
  lo = c;

  if (lo > hi)
    return lo - hi;
  return lo - hi + 1;
}

int modInverse(int a, int m) {
  int m0 = m, t, q;
  int x0 = 0, x1 = 1;

  if (m == 1)
    return 0;

  while (a > 1) {
    // q is quotient
    q = a / m;
    t = m;

    // m is remainder now, process same as
    // Euclid's algo
    m = a % m;
    a = t;

    t = x0;
    x0 = x1 - q * x0;
    x1 = t;
  }

  // Make x1 positive
  if (x1 < 0)
    x1 += m0;

  return x1;
}

void encrypt(uint16_t subKey[52], uint16_t key[8]) {
  int i;

  // Generate encryption keys
  for (i = 0; i < 52; i++) {
    if (i < 8)
      subKey[i] = key[i];
    else if (i % 8 == 6)
      subKey[i] = (subKey[i - 7] << 9) | (subKey[i - 14] >> 7);
    else if (i % 8 == 7)
      subKey[i] = (subKey[i - 15] << 9) | (subKey[i - 14] >> 7);
    else
      subKey[i] = (subKey[i - 7] << 9) | (subKey[i - 6] >> 7);
  }
}

void decrypt(uint16_t subKey[52], uint16_t key[8]) {
  int i;
  uint16_t K[52];

  // Compute encryption keys
  encrypt(K, key);

  // Generate dencryption keys
  subKey[0] = modInverse(K[48], 65537);
  subKey[1] = -K[49];
  subKey[2] = -K[50];
  subKey[3] = modInverse(K[51], 65537);

  printf("Keys: %04X %04X %04X %04X\n", subKey[0], subKey[1], subKey[2],
         subKey[3]);

  for (i = 4; i < 52; i += 6) {
    subKey[i + 0] = K[52 - i - 2];
    subKey[i + 1] = K[52 - i - 1];

    subKey[i + 2] = modInverse(K[52 - i - 6], 65537);
    if (i == 46) {
      subKey[i + 3] = -K[52 - i - 5];
      subKey[i + 4] = -K[52 - i - 4];
    } else {
      subKey[i + 3] = -K[52 - i - 4];
      subKey[i + 4] = -K[52 - i - 5];
    }
    subKey[i + 5] = modInverse(K[52 - i - 3], 65537);

    printf("Keys: %04X %04X %04X %04X %04X %04X\n", subKey[i], subKey[i + 1],
           subKey[i + 2], subKey[i + 3], subKey[i + 4], subKey[i + 5]);
  }
}

void IDEA(uint16_t data[4], uint16_t key[8], idea_gen_key func) {
  int i;
  uint16_t subKey[52];

  // Generate keys
  func(subKey, key);

  uint16_t X0 = data[0];
  uint16_t X1 = data[1];
  uint16_t X2 = data[2];
  uint16_t X3 = data[3];
  uint16_t tmp1, tmp2;

  // Apply 8 rounds
  for (i = 0; i < 8; i++) {
    printf("%d:   %04X %04X %04X %04X\n", i, X0, X1, X2, X3);

    X0 = mulMod65537(X0, subKey[6 * i + 0]);  // Step 1
    X1 += subKey[6 * i + 1];                  // Step 2
    X2 += subKey[6 * i + 2];                  // Step 3
    X3 = mulMod65537(X3, subKey[6 * i + 3]);  // Step 4

    tmp1 = X0 ^ X2;  // Step 5
    tmp2 = X1 ^ X3;  // Step 6

    tmp1 = mulMod65537(tmp1, subKey[6 * i + 4]);  // Step 7
    tmp2 += tmp1;                                 // Step 8
    tmp2 = mulMod65537(tmp2, subKey[6 * i + 5]);  // Step 9
    tmp1 += tmp2;                                 // Step 10

    X0 ^= tmp2;
    X1 ^= tmp1;
    X2 ^= tmp2;
    X3 ^= tmp1;

    // Swap X1 and X2
    tmp1 = X1;
    X1 = X2;
    X2 = tmp1;
  }

  tmp1 = X1;
  tmp2 = X2;

  // Apply the half round
  data[0] = mulMod65537(X0, subKey[6 * i + 0]);
  data[1] = tmp2 + subKey[6 * i + 1];
  data[2] = tmp1 + subKey[6 * i + 2];
  data[3] = mulMod65537(X3, subKey[6 * i + 3]);
}

uint16_t binToInt(char* str) {
  int i;
  uint16_t size = strlen(str);
  uint16_t result = 0;
  uint16_t pow = 1;

  for (i = size - 1; i >= 0; i--) {
    if (str[i] == '1')
      result += pow;
    pow *= 2;
  }

  return result;
}

void convertStringToBin(char* str, uint16_t* data, uint16_t size) {
  int i, j = 0;
  int sizeBlock = sizeof(uint16_t) * 8;
  char block[sizeBlock + 1];

  for (i = 0; i < strlen(str) && i < size * sizeof(uint16_t);
       i += sizeof(uint16_t)) {
    strncpy(block, str, sizeBlock);
    block[sizeBlock] = '\0';

    data[j++] = binToInt(block);
    str += sizeBlock;
  }
}

int main() {
  char Data[64] =
      "0000010100110010000010100110010000010100110010000001100111111010";
  char Key[128] =
      "000000000110010000000000110010000000000100101100000000011001000000000001"
      "11110100000000100101100000000010101111000000001100100000";

  uint16_t data[4];
  uint16_t key[8];

  convertStringToBin(Data, data, 4);
  convertStringToBin(Key, key, 8);

  // Print initial data
  printf("Initial data:   %04X %04X %04X %04X\n", data[0], data[1], data[2],
         data[3]);

  // Encrypt data
  IDEA(data, key, encrypt);
  printf("Encrypted data: %04X %04X %04X %04X\n", data[0], data[1], data[2],
         data[3]);

  // Decrypt data
  IDEA(data, key, decrypt);
  printf("Decrypted data: %04X %04X %04X %04X\n", data[0], data[1], data[2],
         data[3]);

  return 0;
}

SM4

关于SM4

SM4是一个具有128块大小和128位密钥的分组密码算法。加密算法和密钥扩展算法采用32轮线性非迭代结构，S盒输入为8bits，输出也为8bits。

算法原理

参考文档

前置知识

F函数

F(X0, X1, X2, X3, rk) = X0 ⊕ T(X1 ⊕ X2 ⊕ X3 ⊕ rk)

合成置换T

由非线性变换τ 和线性变换L复合合成 T(x)=L(τ(x))

非线性变换τ

τ由四个并行的S-box组成（S-box为16*16 * 8bits，输入8bits，输出8bits）

若输出为A(A0, A1, A2, A3)，输出为B(B0, B1, B2, B3)

则B(B0, B1, B2, B3) = τ(A) = (S-box(A0), S-box(A1), S-box(A2), S-box(A3)

线性变换L

线性变换L的输入是非线性变换τ的输出

输出C = L(B) = B ⊕ (B <<< 2) ⊕ (B <<< 10) ⊕ (B <<< 18) ⊕ (B <<< 24)

T’变换

T’(x)=L’(τ(x))

L’变换

C = L(B) = B ⊕ (B <<< 13) ⊕ (B <<< 23)

反序变换R(A0, A1, A2, A3) = (A3, A2, A1, A0)

密钥扩展算法

加密密钥128位为 MK(MK0, MK1, MK2, MK3)

子密钥128位，共32个为rk0, rk1 , … , rk31

系统参数FKi取值为FK[4] = {0xa3b1bac6, 0x56aa3350, 0x677d9197, 0xb27022dc}

固定参数CKi取值为 CK[32] = {

​ 0x00070e15, 0x1c232a31, 0x383f464d, 0x545b6269, 0x70777e85, 0x8c939aa1,

​ 0xa8afb6bd, 0xc4cbd2d9, 0xe0e7eef5, 0xfc030a11, 0x181f262d, 0x343b4249,

​ 0x50575e65, 0x6c737a81, 0x888f969d, 0xa4abb2b9, 0xc0c7ced5, 0xdce3eaf1,

​ 0xf8ff060d, 0x141b2229, 0x30373e45, 0x4c535a61, 0x686f767d, 0x848b9299,

​ 0xa0a7aeb5, 0xbcc3cad1, 0xd8dfe6ed, 0xf4fb0209, 0x10171e25, 0x2c333a41,

​ 0x484f565d, 0x646b7279};

子密钥生成算法如下

(K0,K1,K2,K3)=(MK0 ⊕ FK0, MK1⊕FK1, MK2⊕FK2, MK3⊕FK3)

rki = K(i+4) = Ki ⊕ T’(K(i+1) ⊕ K(i+2) ⊕ K(i+3) ⊕ CKi) (i = 0 ,1 , … , 31)

加密算法

明文输入为X(X0, X1, X2, X3)，密文输出为Y(Y0, Y1, Y2, Y3)

Xi+4 = F(Xi, Xi+1, Xi+2, Xi+3, rki) = Xi ⊕ T(Xi+1 ⊕ Xi+2 ⊕ Xi+3 ⊕ rki) (i = 0 ,1 , … , 31)

Y(Y0, Y1, Y2, Y3) = R(X32, X33, X34, X35) = (X35, X34, X33, X32)

解密算法

解密算法和加密算法相同，唯一区别是密钥使用顺序要逆序使用

加解密实现

from https://zhuanlan.zhihu.com/p/43951432

sm4.c

/*************************************************************************
       > File Name: run_sm4.c
       > Author:yangkefeng
       > E-mail:muyidixin2006@126.com
       > Created Time: Thu July 13 23:55:50 2018
************************************************************************/

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

#include "sm4.h"

int main(int argc, char** argv) {
  int mode = 0, flag = 1, format_res;
  unsigned char iv[16] = {0x0, 0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7,
                          0x8, 0x9, 0xa, 0xb, 0xc, 0xd, 0xe, 0xf};
  unsigned char output[16];
  long i;
  // SM4 mode:SM4_ECB 0,SM4_CBC 1,SM4_CFB 2,SM4_OFB 3,SM4_CTR 4
  // SM4 flag:encrypt=1/decrypt=0
  unsigned char input[16] = {0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef,
                             0xfe, 0xdc, 0xba, 0x98, 0x76, 0x54, 0x32, 0x10};
  unsigned char key[16] = {0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef,
                           0xfe, 0xdc, 0xba, 0x98, 0x76, 0x54, 0x32, 0x10};
  flag = 1;
  mode = 0;

  sm4(key, mode, flag, 16, iv, input, output);
  // SM4 输出
  for (i = 0; i < 16; i++)
    printf("%02x", output[i]);
  printf("\n");
  return 0;

  // int mode = 0, flag = 1, format_res;
  // unsigned char key[16];
  // unsigned char iv[16] = {0x0, 0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7,
  //                         0x8, 0x9, 0xa, 0xb, 0xc, 0xd, 0xe, 0xf};
  // unsigned char input[16];
  // unsigned char output[16];
  // long i;
  // // SM4 input 读取
  // format_res = format_park_input(argv[1], input);
  // if (format_res == 0) {
  //   printf("明文/密文必须是32位16进制的数(0-F)\n");
  //   return 0;
  // }
  // // SM4 key 读取
  // format_res = format_park_input(argv[2], key);
  // if (format_res == 0) {
  //   printf("密钥必须是32位16进制的数(0-F)\n");
  //   return 0;
  // }
  // // SM4 mode:SM4_ECB 0,SM4_CBC 1,SM4_CFB 2,SM4_OFB 3,SM4_CTR 4
  // mode = atoi(argv[3]);
  // // SM4 flag:encrypt=1/decrypt=0
  // flag = atoi(argv[4]);
  // sm4(key, mode, flag, 16, iv, input, output);
  // // SM4 输出
  // for (i = 0; i < 16; i++)
  //   printf("%02x", output[i]);
  // printf("\n");
  // return 0;
}

sm4.h

/*************************************************************************
       > File Name: run_sm4.c
       > Author:yangkefeng
       > E-mail:muyidixin2006@126.com
       > Created Time: Thu July 13 23:55:50 2018
************************************************************************/

#ifndef XYSSL_SM4_H
#define XYSSL_SM4_H

/***
 *sm4 select encrypt/decrypt by flag
 ***/
#define SM4_ENCRYPT 1
#define SM4_DECRYPT 0

/***
 *sm4 select mode by mode
 ***/
#define SM4_ECB 0
#define SM4_CBC 1
#define SM4_CFB 2
#define SM4_OFB 3
#define SM4_CTR 4

/**
 * \brief          SM4 context structure
 */
typedef struct {
  int mode;             /*!<  encrypt/decrypt   */
  unsigned long sk[32]; /*!<  SM4 subkeys       */
} sm4_context;

#ifdef __cplusplus
extern "C" {
#endif

/**
 * \brief          SM4 key schedule (128-bit, encryption)
 *
 * \param ctx      SM4 context to be initialized
 * \param key      16-byte secret key
 */
void sm4_setkey_enc(sm4_context* ctx, unsigned char key[16]);

/**
 * \brief          SM4 key schedule (128-bit, decryption)
 *
 * \param ctx      SM4 context to be initialized
 * \param key      16-byte secret key
 */
void sm4_setkey_dec(sm4_context* ctx, unsigned char key[16]);

/**
 * \brief          SM4-ECB block encryption/decryption
 * \param ctx      SM4 context
 * \param flag     SM4_ENCRYPT or SM4_DECRYPT
 * \param length   length of the input data
 * \param input    input block
 * \param output   output block
 */
void sm4_crypt_ecb(sm4_context* ctx,
                   int flag,
                   int length,
                   unsigned char* input,
                   unsigned char* output);

/**
 * \brief          SM4-CBC buffer encryption/decryption
 * \param ctx      SM4 context
 * \param flag     SM4_ENCRYPT or SM4_DECRYPT
 * \param length   length of the input data
 * \param iv       initialization vector (updated after use)
 * \param input    buffer holding the input data
 * \param output   buffer holding the output data
 */
void sm4_crypt_cbc(sm4_context* ctx,
                   int flag,
                   int length,
                   unsigned char iv[16],
                   unsigned char* input,
                   unsigned char* output);

/**
 * \brief          SM4-CFB encryption/decryption
 * \param ctx      SM4 context
 * \param flag     SM4_ENCRYPT or SM4_DECRYPT
 * \param length   length of the input data
 * \param iv       initialization vector (updated after use)
 * \param input    buffer holding the input data
 * \param output   buffer holding the output data
 */
void sm4_crypt_cfb(sm4_context* ctx,
                   int flag,
                   int length,
                   unsigned char iv[16],
                   unsigned char* input,
                   unsigned char* output);

/**
 * \brief          SM4-OFB encryption/decryption
 * \param ctx      SM4 context
 * \param flag     SM4_ENCRYPT or SM4_DECRYPT
 * \param length   length of the input data
 * \param iv       initialization vector (updated after use)
 * \param input    buffer holding the input data
 * \param output   buffer holding the output data
 */
void sm4_crypt_ofb(sm4_context* ctx,
                   int flag,
                   int length,
                   unsigned char iv[16],
                   unsigned char* input,
                   unsigned char* output);

/**
 * \brief          SM4-CTR encryption/decryption
 * \param ctx      SM4 context
 * \param flag     SM4_ENCRYPT or SM4_DECRYPT
 * \param length   length of the input data
 * \param iv       initialization vector (updated after use)
 * \param input    buffer holding the input data
 * \param output   buffer holding the output data
 */
void sm4_crypt_ctr(sm4_context* ctx,
                   int flag,
                   int length,
                   unsigned char iv[16],
                   unsigned char* input,
                   unsigned char* output);

/**
 * \brief          SM4 encryption/decryption
 * \param key      SM4 key
 * \param flag     SM4_ENCRYPT or SM4_DECRYPT
 * \param length   length of the input data
 * \param iv       initialization vector (updated after use)
 * \param input    buffer holding the input data
 * \param output   buffer holding the output data
 */
void sm4(unsigned char key[16],
         int mode,
         int flag,
         int length,
         unsigned char iv[16],
         unsigned char* input,
         unsigned char* output);

/**
 * \brief          SM4 parameter format hex
 * \param input    buffer holding the input data
 * \param output   buffer holding the output data
 */
int format_park_input(char* input, unsigned char* output);

#ifdef __cplusplus
}
#endif

#endif /* sm4.h */

sm4_code.c

/*************************************************************************
       > File Name: run_sm4.c
       > Author:yangkefeng
       > E-mail:muyidixin2006@126.com
       > Created Time: Thu July 13 23:55:50 2018
************************************************************************/

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

/*
 * 32-bit integer manipulation macros (big endian)
 */
#ifndef GET_ULONG_BE
#define GET_ULONG_BE(n, b, i)                                                 \
  {                                                                           \
    (n) = ((unsigned long)(b)[(i)] << 24) |                                   \
          ((unsigned long)(b)[(i) + 1] << 16) |                               \
          ((unsigned long)(b)[(i) + 2] << 8) | ((unsigned long)(b)[(i) + 3]); \
  }
#endif

#ifndef PUT_ULONG_BE
#define PUT_ULONG_BE(n, b, i)                  \
  {                                            \
    (b)[(i)] = (unsigned char)((n) >> 24);     \
    (b)[(i) + 1] = (unsigned char)((n) >> 16); \
    (b)[(i) + 2] = (unsigned char)((n) >> 8);  \
    (b)[(i) + 3] = (unsigned char)((n));       \
  }
#endif

/*
 *rotate shift left marco definition
 *
 */
#define SHL(x, n) (((x)&0xFFFFFFFF) << n)
#define ROTL(x, n) (SHL((x), n) | ((x) >> (32 - n)))

#define SWAP(a, b)       \
  {                      \
    unsigned long t = a; \
    a = b;               \
    b = t;               \
    t = 0;               \
  }

/*
 * Expanded SM4 S-boxes
 /* Sbox table: 8bits input convert to 8 bits output*/

static const unsigned char SboxTable[16][16] = {
    {0xd6, 0x90, 0xe9, 0xfe, 0xcc, 0xe1, 0x3d, 0xb7, 0x16, 0xb6, 0x14, 0xc2,
     0x28, 0xfb, 0x2c, 0x05},
    {0x2b, 0x67, 0x9a, 0x76, 0x2a, 0xbe, 0x04, 0xc3, 0xaa, 0x44, 0x13, 0x26,
     0x49, 0x86, 0x06, 0x99},
    {0x9c, 0x42, 0x50, 0xf4, 0x91, 0xef, 0x98, 0x7a, 0x33, 0x54, 0x0b, 0x43,
     0xed, 0xcf, 0xac, 0x62},
    {0xe4, 0xb3, 0x1c, 0xa9, 0xc9, 0x08, 0xe8, 0x95, 0x80, 0xdf, 0x94, 0xfa,
     0x75, 0x8f, 0x3f, 0xa6},
    {0x47, 0x07, 0xa7, 0xfc, 0xf3, 0x73, 0x17, 0xba, 0x83, 0x59, 0x3c, 0x19,
     0xe6, 0x85, 0x4f, 0xa8},
    {0x68, 0x6b, 0x81, 0xb2, 0x71, 0x64, 0xda, 0x8b, 0xf8, 0xeb, 0x0f, 0x4b,
     0x70, 0x56, 0x9d, 0x35},
    {0x1e, 0x24, 0x0e, 0x5e, 0x63, 0x58, 0xd1, 0xa2, 0x25, 0x22, 0x7c, 0x3b,
     0x01, 0x21, 0x78, 0x87},
    {0xd4, 0x00, 0x46, 0x57, 0x9f, 0xd3, 0x27, 0x52, 0x4c, 0x36, 0x02, 0xe7,
     0xa0, 0xc4, 0xc8, 0x9e},
    {0xea, 0xbf, 0x8a, 0xd2, 0x40, 0xc7, 0x38, 0xb5, 0xa3, 0xf7, 0xf2, 0xce,
     0xf9, 0x61, 0x15, 0xa1},
    {0xe0, 0xae, 0x5d, 0xa4, 0x9b, 0x34, 0x1a, 0x55, 0xad, 0x93, 0x32, 0x30,
     0xf5, 0x8c, 0xb1, 0xe3},
    {0x1d, 0xf6, 0xe2, 0x2e, 0x82, 0x66, 0xca, 0x60, 0xc0, 0x29, 0x23, 0xab,
     0x0d, 0x53, 0x4e, 0x6f},
    {0xd5, 0xdb, 0x37, 0x45, 0xde, 0xfd, 0x8e, 0x2f, 0x03, 0xff, 0x6a, 0x72,
     0x6d, 0x6c, 0x5b, 0x51},
    {0x8d, 0x1b, 0xaf, 0x92, 0xbb, 0xdd, 0xbc, 0x7f, 0x11, 0xd9, 0x5c, 0x41,
     0x1f, 0x10, 0x5a, 0xd8},
    {0x0a, 0xc1, 0x31, 0x88, 0xa5, 0xcd, 0x7b, 0xbd, 0x2d, 0x74, 0xd0, 0x12,
     0xb8, 0xe5, 0xb4, 0xb0},
    {0x89, 0x69, 0x97, 0x4a, 0x0c, 0x96, 0x77, 0x7e, 0x65, 0xb9, 0xf1, 0x09,
     0xc5, 0x6e, 0xc6, 0x84},
    {0x18, 0xf0, 0x7d, 0xec, 0x3a, 0xdc, 0x4d, 0x20, 0x79, 0xee, 0x5f, 0x3e,
     0xd7, 0xcb, 0x39, 0x48}};

/* System parameter */
static const unsigned long FK[4] = {0xa3b1bac6, 0x56aa3350, 0x677d9197,
                                    0xb27022dc};

/* fixed parameter */
static const unsigned long CK[32] = {
    0x00070e15, 0x1c232a31, 0x383f464d, 0x545b6269, 0x70777e85, 0x8c939aa1,
    0xa8afb6bd, 0xc4cbd2d9, 0xe0e7eef5, 0xfc030a11, 0x181f262d, 0x343b4249,
    0x50575e65, 0x6c737a81, 0x888f969d, 0xa4abb2b9, 0xc0c7ced5, 0xdce3eaf1,
    0xf8ff060d, 0x141b2229, 0x30373e45, 0x4c535a61, 0x686f767d, 0x848b9299,
    0xa0a7aeb5, 0xbcc3cad1, 0xd8dfe6ed, 0xf4fb0209, 0x10171e25, 0x2c333a41,
    0x484f565d, 0x646b7279};

/*
 * private function:
 * look up in SboxTable and get the related value.
 * args:    [in] inch: 0x00~0xFF (8 bits unsigned value).
 */
static unsigned char sm4Sbox(unsigned char inch) {
  unsigned char* pTable = (unsigned char*)SboxTable;
  unsigned char retVal = (unsigned char)(pTable[inch]);
  return retVal;
}

/*
 * private F(Lt) function:
 * "T algorithm" == "L algorithm" + "t algorithm".
 * args:    [in] a: a is a 32 bits unsigned value;
 * return: c: c is calculated with line algorithm "L" and nonline algorithm "t"
 */
static unsigned long sm4Lt(unsigned long ka) {
  unsigned long bb = 0;
  unsigned long c = 0;
  unsigned char a[4];
  unsigned char b[4];
  PUT_ULONG_BE(ka, a, 0)
  b[0] = sm4Sbox(a[0]);
  b[1] = sm4Sbox(a[1]);
  b[2] = sm4Sbox(a[2]);
  b[3] = sm4Sbox(a[3]);
  GET_ULONG_BE(bb, b, 0)
  c = bb ^ (ROTL(bb, 2)) ^ (ROTL(bb, 10)) ^ (ROTL(bb, 18)) ^ (ROTL(bb, 24));
  return c;
}

/*
 * private F function:
 * Calculating and getting encryption/decryption contents.
 * args:    [in] x0: original contents;
 * args:    [in] x1: original contents;
 * args:    [in] x2: original contents;
 * args:    [in] x3: original contents;
 * args:    [in] rk: encryption/decryption key;
 * return the contents of encryption/decryption contents.
 */
static unsigned long sm4F(unsigned long x0,
                          unsigned long x1,
                          unsigned long x2,
                          unsigned long x3,
                          unsigned long rk) {
  return (x0 ^ sm4Lt(x1 ^ x2 ^ x3 ^ rk));
}

/* private function:
 * Calculating round encryption key.
 * args:    [in] a: a is a 32 bits unsigned value;
 * return: sk[i]: i{0,1,2,3,...31}.
 */
static unsigned long sm4CalciRK(unsigned long ka) {
  unsigned long bb = 0;
  unsigned long rk = 0;
  unsigned char a[4];
  unsigned char b[4];
  PUT_ULONG_BE(ka, a, 0)
  b[0] = sm4Sbox(a[0]);
  b[1] = sm4Sbox(a[1]);
  b[2] = sm4Sbox(a[2]);
  b[3] = sm4Sbox(a[3]);
  GET_ULONG_BE(bb, b, 0)
  rk = bb ^ (ROTL(bb, 13)) ^ (ROTL(bb, 23));
  return rk;
}

static void sm4_setkey(unsigned long SK[32], unsigned char key[16]) {
  unsigned long MK[4];
  unsigned long k[36];
  unsigned long i = 0;

  GET_ULONG_BE(MK[0], key, 0);
  GET_ULONG_BE(MK[1], key, 4);
  GET_ULONG_BE(MK[2], key, 8);
  GET_ULONG_BE(MK[3], key, 12);
  k[0] = MK[0] ^ FK[0];
  k[1] = MK[1] ^ FK[1];
  k[2] = MK[2] ^ FK[2];
  k[3] = MK[3] ^ FK[3];
  for (; i < 32; i++) {
    k[i + 4] = k[i] ^ (sm4CalciRK(k[i + 1] ^ k[i + 2] ^ k[i + 3] ^ CK[i]));
    SK[i] = k[i + 4];
  }
}

/*
 * SM4 standard one round processing
 *
 */
static void sm4_one_round(unsigned long sk[32],
                          unsigned char input[16],
                          unsigned char output[16]) {
  unsigned long i = 0;
  unsigned long ulbuf[36];
  memset(ulbuf, 0, sizeof(ulbuf));
  GET_ULONG_BE(ulbuf[0], input, 0)
  GET_ULONG_BE(ulbuf[1], input, 4)
  GET_ULONG_BE(ulbuf[2], input, 8)
  GET_ULONG_BE(ulbuf[3], input, 12)
  while (i < 32) {
    ulbuf[i + 4] =
        sm4F(ulbuf[i], ulbuf[i + 1], ulbuf[i + 2], ulbuf[i + 3], sk[i]);
    // #ifdef _DEBUG
    //        	printf("rk(%02d) = 0x%08x,  X(%02d) = 0x%08x \n",i,sk[i], i,
    //        ulbuf[i+4] );
    // #endif
    i++;
  }
  PUT_ULONG_BE(ulbuf[35], output, 0);
  PUT_ULONG_BE(ulbuf[34], output, 4);
  PUT_ULONG_BE(ulbuf[33], output, 8);
  PUT_ULONG_BE(ulbuf[32], output, 12);
}

/*
 * SM4 key schedule (128-bit, encryption)
 */
void sm4_setkey_enc(sm4_context* ctx, unsigned char key[16]) {
  ctx->mode = SM4_ENCRYPT;
  sm4_setkey(ctx->sk, key);
}

/*
 * SM4 key schedule (128-bit, decryption)
 */
void sm4_setkey_dec(sm4_context* ctx, unsigned char key[16]) {
  int i;
  ctx->mode = SM4_DECRYPT;
  sm4_setkey(ctx->sk, key);
  for (i = 0; i < 16; i++) {
    SWAP(ctx->sk[i], ctx->sk[31 - i]);
  }
}

/*
 * SM4 key schedule (128-bit, decryption)
 */
static int is_hex(char* input) {
  int i, len, isHex = 1;
  len = strlen(input);
  for (i = 0; i < len; i += 1) {
    if (isxdigit(input[i]) == 0) {
      isHex = 0;
      break;
    }
  }
  return isHex;
}

/*
 * SM4 key schedule (128-bit, decryption)
 */
static int hex2ds(char* s)  // 16进制转10进制
{
  int i, m, temp = 0, n;
  m = strlen(s);  //十六进制是按字符串传进来的，所以要获得他的长度
  for (i = 0; i < m; i++) {
    if (s[i] >= 'A' &&
        s[i] <= 'F')  //十六进制还要判断他是不是在A-F或者a-f之间a=10。{
    {
      n = s[i] - 'A' + 10;
    } else if (s[i] >= 'a' && s[i] <= 'f') {
      n = s[i] - 'a' + 10;
    } else {
      n = s[i] - '0';
    }
    temp = temp * 16 + n;
  }
  return temp;
}

/*
 * 2位为单位处理转换成ASCII后再输出为字符保存在output
 */
static void char2hex(unsigned char* input, unsigned char* output, int len) {
  int i;
  unsigned char a[3];
  unsigned char res;
  for (i = 0; i < len; i += 2) {
    a[0] = input[i];
    a[1] = input[i + 1];
    a[2] = 0;
    res = hex2ds(a);
    output[i / 2] = res;
  }
  output[len / 2] = 0;
}

int format_park_input(char* input, unsigned char* output) {
  int len = 0;
  len = strlen(input);
  if (len != 32 || is_hex(input) == 0)  //判断是否为双数位
  {
    return 0;
  } else {
    char2hex(input, output, len);
    return 1;
  }
}

/*
 * SM4-ECB block encryption/decryption
 */
void sm4_crypt_ecb(sm4_context* ctx,
                   int flag,
                   int length,
                   unsigned char* input,
                   unsigned char* output) {
  while (length > 0) {
    sm4_one_round(ctx->sk, input, output);
    input += 16;
    output += 16;
    length -= 16;
  }
}

/*
 * SM4-CBC buffer encryption/decryption
 */
void sm4_crypt_cbc(sm4_context* ctx,
                   int flag,
                   int length,
                   unsigned char iv[16],
                   unsigned char* input,
                   unsigned char* output) {
  int i;
  unsigned char temp[16];

  if (flag == SM4_ENCRYPT) {
    while (length > 0) {
      for (i = 0; i < 16; i++)
        output[i] = (unsigned char)(input[i] ^ iv[i]);

      sm4_one_round(ctx->sk, output, output);
      memcpy(iv, output, 16);

      input += 16;
      output += 16;
      length -= 16;
    }
  } else /* SM4_DECRYPT */
  {
    while (length > 0) {
      memcpy(temp, input, 16);
      sm4_one_round(ctx->sk, input, output);

      for (i = 0; i < 16; i++)
        output[i] = (unsigned char)(output[i] ^ iv[i]);

      memcpy(iv, temp, 16);

      input += 16;
      output += 16;
      length -= 16;
    }
  }
}

/*
 * SM4 cfb mode
 */
void sm4_crypt_cfb(sm4_context* ctx,
                   int flag,
                   int length,
                   unsigned char iv[16],
                   unsigned char* input,
                   unsigned char* output) {
  int i;
  unsigned char temp[16];

  if (flag == SM4_ENCRYPT) {
    while (length > 0) {
      sm4_one_round(ctx->sk, iv, temp);

      for (i = 0; i < 16; i++)
        output[i] = (unsigned char)(temp[i] ^ input[i]);
      memcpy(iv, output, 16);

      input += 16;
      output += 16;
      length -= 16;
    }
  } else /* SM4_DECRYPT */
  {
    while (length > 0) {
      sm4_one_round(ctx->sk, iv, temp);
      memcpy(iv, input, 16);

      for (i = 0; i < 16; i++)
        output[i] = (unsigned char)(temp[i] ^ input[i]);

      input += 16;
      output += 16;
      length -= 16;
    }
  }
}

/*
 * SM4 ofb mode
 */
void sm4_crypt_ofb(sm4_context* ctx,
                   int flag,
                   int length,
                   unsigned char iv[16],
                   unsigned char* input,
                   unsigned char* output) {
  int i;
  unsigned char temp[16];

  if (flag == SM4_ENCRYPT) {
    while (length > 0) {
      sm4_one_round(ctx->sk, iv, temp);

      for (i = 0; i < 16; i++)
        output[i] = (unsigned char)(temp[i] ^ input[i]);

      for (i = 0; i < 16; i++) {
        iv[i]++;
        if (iv[i] != 0)
          break;
      }

      input += 16;
      output += 16;
      length -= 16;
    }
  } else /* SM4_DECRYPT */
  {
    while (length > 0) {
      sm4_one_round(ctx->sk, iv, temp);

      for (i = 0; i < 16; i++)
        output[i] = (unsigned char)(temp[i] ^ input[i]);

      for (i = 0; i < 16; i++) {
        iv[i]++;
        if (iv[i] != 0)
          break;
      }

      input += 16;
      output += 16;
      length -= 16;
    }
  }
}

/*
 * SM4 ctr mode
 */
void sm4_crypt_ctr(sm4_context* ctx,
                   int flag,
                   int length,
                   unsigned char iv[16],
                   unsigned char* input,
                   unsigned char* output) {
  int i;
  unsigned char temp[16];

  if (flag == SM4_ENCRYPT) {
    while (length > 0) {
      for (i = 0; i < 16; i++)
        output[i] = (unsigned char)(input[i] ^ iv[i]);

      sm4_one_round(ctx->sk, output, output);
      memcpy(iv, output, 16);

      input += 16;
      output += 16;
      length -= 16;
    }
  } else /* SM4_DECRYPT */
  {
    while (length > 0) {
      memcpy(temp, input, 16);
      sm4_one_round(ctx->sk, input, output);

      for (i = 0; i < 16; i++)
        output[i] = (unsigned char)(output[i] ^ iv[i]);

      memcpy(iv, temp, 16);

      input += 16;
      output += 16;
      length -= 16;
    }
  }
}

void sm4(unsigned char key[16],
         int mode,
         int flag,
         int length,
         unsigned char iv[16],
         unsigned char* input,
         unsigned char* output) {
  sm4_context ctx;
  if (flag == SM4_ENCRYPT) {
    sm4_setkey_enc(&ctx, key);
  } else {
    sm4_setkey_dec(&ctx, key);
  }
  switch (mode) {
    case 0:
      sm4_crypt_ecb(&ctx, flag, length, input, output);
      break;
    case 1:
      sm4_crypt_cbc(&ctx, flag, length, iv, input, output);
      break;
    case 2:
      sm4_crypt_cfb(&ctx, flag, length, iv, input, output);
      break;
    case 3:
      sm4_crypt_ofb(&ctx, flag, length, iv, input, output);
      break;
    case 4:
      sm4_crypt_ctr(&ctx, flag, length, iv, input, output);
      break;
    default:
      sm4_crypt_ecb(&ctx, flag, length, input, output);
  }
}

BlowFish

关于BlowFish算法

BlowFish是一个具有64位块大小和可变密钥长度（32位到448位）的分组密码算法。它是一个16轮Feistel密码，使用大型密钥相关的S盒。

算法原理

子密钥生成

子密钥生成使用了由18个32位字组成的P数组

4个8*32的包含1024个32位字的S-box

uint32_t P[18];
uint32_t S[4][256];

步骤：

1.按顺序使用常数Π的小数部分初始化P数组和S-box

2.对P数组和密钥进行逐位异或，必要时重用密钥

3.使用当前的P数组和S-box对全0的64位分组使用BlowFish算法进行加密，用输出代替P[1]、P[2]

4.重复以上步骤使用当前的P数组和S-box对上一步输出进行加密，并用输出代替P[3]、P[4]，直到按顺序替代所有的P数组和S-box中的元素为止

加密

f函数输入是一个32位双字，共4个字节，分别作为4个S-box的索引，取出相应的S-box的值然后进行模2^32加运算

F(x) = F(a, b, c, d) = ((S1[a] + S2[b]) ^ S3[c]) + S4[d]
// x = a << 24 + b << 16 + c << 8 + d

加密是由16轮的Feistel网络组成

void encrypt (uint32_t & L, uint32_t & R) {
   for (int i=0 ; i<16 ; i += 2) {
      L ^= P[i];
      R ^= f(L);
      R ^= P[i+1];
      L ^= f(R);
   }
   L ^= P[16];
   R ^= P[17];
   swap (L, R);
}

解密

解密方法与加密方法相同，只是P数组要逆序使用

void decrypt (uint32_t & L, uint32_t & R) {
   for (int i=16 ; i > 0 ; i -= 2) {
      L ^= P[i+1];
      R ^= f(L);
      R ^= P[i];
      L ^= f(R);
   }
   L ^= P[1];
   R ^= P[0];
   swap (L, R);
}

加解密实现

// create by feng on August 1, 2019
// This is a simple encryption and decryption program for Blowfish 
#include <stdio.h>
// P array
unsigned int P[18] = {0x243F6A88L, 0x85A308D3L, 0x13198A2EL, 0x03707344L,
                      0xA4093822L, 0x299F31D0L, 0x082EFA98L, 0xEC4E6C89L,
                      0x452821E6L, 0x38D01377L, 0xBE5466CFL, 0x34E90C6CL,
                      0xC0AC29B7L, 0xC97C50DDL, 0x3F84D5B5L, 0xB5470917L,
                      0x9216D5D9L, 0x8979FB1BL};
// S-box
unsigned int S[4][256] = {
    {0xD1310BA6L, 0x98DFB5ACL, 0x2FFD72DBL, 0xD01ADFB7L, 0xB8E1AFEDL,
     0x6A267E96L, 0xBA7C9045L, 0xF12C7F99L, 0x24A19947L, 0xB3916CF7L,
     0x0801F2E2L, 0x858EFC16L, 0x636920D8L, 0x71574E69L, 0xA458FEA3L,
     0xF4933D7EL, 0x0D95748FL, 0x728EB658L, 0x718BCD58L, 0x82154AEEL,
     0x7B54A41DL, 0xC25A59B5L, 0x9C30D539L, 0x2AF26013L, 0xC5D1B023L,
     0x286085F0L, 0xCA417918L, 0xB8DB38EFL, 0x8E79DCB0L, 0x603A180EL,
     0x6C9E0E8BL, 0xB01E8A3EL, 0xD71577C1L, 0xBD314B27L, 0x78AF2FDAL,
     0x55605C60L, 0xE65525F3L, 0xAA55AB94L, 0x57489862L, 0x63E81440L,
     0x55CA396AL, 0x2AAB10B6L, 0xB4CC5C34L, 0x1141E8CEL, 0xA15486AFL,
     0x7C72E993L, 0xB3EE1411L, 0x636FBC2AL, 0x2BA9C55DL, 0x741831F6L,
     0xCE5C3E16L, 0x9B87931EL, 0xAFD6BA33L, 0x6C24CF5CL, 0x7A325381L,
     0x28958677L, 0x3B8F4898L, 0x6B4BB9AFL, 0xC4BFE81BL, 0x66282193L,
     0x61D809CCL, 0xFB21A991L, 0x487CAC60L, 0x5DEC8032L, 0xEF845D5DL,
     0xE98575B1L, 0xDC262302L, 0xEB651B88L, 0x23893E81L, 0xD396ACC5L,
     0x0F6D6FF3L, 0x83F44239L, 0x2E0B4482L, 0xA4842004L, 0x69C8F04AL,
     0x9E1F9B5EL, 0x21C66842L, 0xF6E96C9AL, 0x670C9C61L, 0xABD388F0L,
     0x6A51A0D2L, 0xD8542F68L, 0x960FA728L, 0xAB5133A3L, 0x6EEF0B6CL,
     0x137A3BE4L, 0xBA3BF050L, 0x7EFB2A98L, 0xA1F1651DL, 0x39AF0176L,
     0x66CA593EL, 0x82430E88L, 0x8CEE8619L, 0x456F9FB4L, 0x7D84A5C3L,
     0x3B8B5EBEL, 0xE06F75D8L, 0x85C12073L, 0x401A449FL, 0x56C16AA6L,
     0x4ED3AA62L, 0x363F7706L, 0x1BFEDF72L, 0x429B023DL, 0x37D0D724L,
     0xD00A1248L, 0xDB0FEAD3L, 0x49F1C09BL, 0x075372C9L, 0x80991B7BL,
     0x25D479D8L, 0xF6E8DEF7L, 0xE3FE501AL, 0xB6794C3BL, 0x976CE0BDL,
     0x04C006BAL, 0xC1A94FB6L, 0x409F60C4L, 0x5E5C9EC2L, 0x196A2463L,
     0x68FB6FAFL, 0x3E6C53B5L, 0x1339B2EBL, 0x3B52EC6FL, 0x6DFC511FL,
     0x9B30952CL, 0xCC814544L, 0xAF5EBD09L, 0xBEE3D004L, 0xDE334AFDL,
     0x660F2807L, 0x192E4BB3L, 0xC0CBA857L, 0x45C8740FL, 0xD20B5F39L,
     0xB9D3FBDBL, 0x5579C0BDL, 0x1A60320AL, 0xD6A100C6L, 0x402C7279L,
     0x679F25FEL, 0xFB1FA3CCL, 0x8EA5E9F8L, 0xDB3222F8L, 0x3C7516DFL,
     0xFD616B15L, 0x2F501EC8L, 0xAD0552ABL, 0x323DB5FAL, 0xFD238760L,
     0x53317B48L, 0x3E00DF82L, 0x9E5C57BBL, 0xCA6F8CA0L, 0x1A87562EL,
     0xDF1769DBL, 0xD542A8F6L, 0x287EFFC3L, 0xAC6732C6L, 0x8C4F5573L,
     0x695B27B0L, 0xBBCA58C8L, 0xE1FFA35DL, 0xB8F011A0L, 0x10FA3D98L,
     0xFD2183B8L, 0x4AFCB56CL, 0x2DD1D35BL, 0x9A53E479L, 0xB6F84565L,
     0xD28E49BCL, 0x4BFB9790L, 0xE1DDF2DAL, 0xA4CB7E33L, 0x62FB1341L,
     0xCEE4C6E8L, 0xEF20CADAL, 0x36774C01L, 0xD07E9EFEL, 0x2BF11FB4L,
     0x95DBDA4DL, 0xAE909198L, 0xEAAD8E71L, 0x6B93D5A0L, 0xD08ED1D0L,
     0xAFC725E0L, 0x8E3C5B2FL, 0x8E7594B7L, 0x8FF6E2FBL, 0xF2122B64L,
     0x8888B812L, 0x900DF01CL, 0x4FAD5EA0L, 0x688FC31CL, 0xD1CFF191L,
     0xB3A8C1ADL, 0x2F2F2218L, 0xBE0E1777L, 0xEA752DFEL, 0x8B021FA1L,
     0xE5A0CC0FL, 0xB56F74E8L, 0x18ACF3D6L, 0xCE89E299L, 0xB4A84FE0L,
     0xFD13E0B7L, 0x7CC43B81L, 0xD2ADA8D9L, 0x165FA266L, 0x80957705L,
     0x93CC7314L, 0x211A1477L, 0xE6AD2065L, 0x77B5FA86L, 0xC75442F5L,
     0xFB9D35CFL, 0xEBCDAF0CL, 0x7B3E89A0L, 0xD6411BD3L, 0xAE1E7E49L,
     0x00250E2DL, 0x2071B35EL, 0x226800BBL, 0x57B8E0AFL, 0x2464369BL,
     0xF009B91EL, 0x5563911DL, 0x59DFA6AAL, 0x78C14389L, 0xD95A537FL,
     0x207D5BA2L, 0x02E5B9C5L, 0x83260376L, 0x6295CFA9L, 0x11C81968L,
     0x4E734A41L, 0xB3472DCAL, 0x7B14A94AL, 0x1B510052L, 0x9A532915L,
     0xD60F573FL, 0xBC9BC6E4L, 0x2B60A476L, 0x81E67400L, 0x08BA6FB5L,
     0x571BE91FL, 0xF296EC6BL, 0x2A0DD915L, 0xB6636521L, 0xE7B9F9B6L,
     0xFF34052EL, 0xC5855664L, 0x53B02D5DL, 0xA99F8FA1L, 0x08BA4799L,
     0x6E85076AL},
    {0x4B7A70E9L, 0xB5B32944L, 0xDB75092EL, 0xC4192623L, 0xAD6EA6B0L,
     0x49A7DF7DL, 0x9CEE60B8L, 0x8FEDB266L, 0xECAA8C71L, 0x699A17FFL,
     0x5664526CL, 0xC2B19EE1L, 0x193602A5L, 0x75094C29L, 0xA0591340L,
     0xE4183A3EL, 0x3F54989AL, 0x5B429D65L, 0x6B8FE4D6L, 0x99F73FD6L,
     0xA1D29C07L, 0xEFE830F5L, 0x4D2D38E6L, 0xF0255DC1L, 0x4CDD2086L,
     0x8470EB26L, 0x6382E9C6L, 0x021ECC5EL, 0x09686B3FL, 0x3EBAEFC9L,
     0x3C971814L, 0x6B6A70A1L, 0x687F3584L, 0x52A0E286L, 0xB79C5305L,
     0xAA500737L, 0x3E07841CL, 0x7FDEAE5CL, 0x8E7D44ECL, 0x5716F2B8L,
     0xB03ADA37L, 0xF0500C0DL, 0xF01C1F04L, 0x0200B3FFL, 0xAE0CF51AL,
     0x3CB574B2L, 0x25837A58L, 0xDC0921BDL, 0xD19113F9L, 0x7CA92FF6L,
     0x94324773L, 0x22F54701L, 0x3AE5E581L, 0x37C2DADCL, 0xC8B57634L,
     0x9AF3DDA7L, 0xA9446146L, 0x0FD0030EL, 0xECC8C73EL, 0xA4751E41L,
     0xE238CD99L, 0x3BEA0E2FL, 0x3280BBA1L, 0x183EB331L, 0x4E548B38L,
     0x4F6DB908L, 0x6F420D03L, 0xF60A04BFL, 0x2CB81290L, 0x24977C79L,
     0x5679B072L, 0xBCAF89AFL, 0xDE9A771FL, 0xD9930810L, 0xB38BAE12L,
     0xDCCF3F2EL, 0x5512721FL, 0x2E6B7124L, 0x501ADDE6L, 0x9F84CD87L,
     0x7A584718L, 0x7408DA17L, 0xBC9F9ABCL, 0xE94B7D8CL, 0xEC7AEC3AL,
     0xDB851DFAL, 0x63094366L, 0xC464C3D2L, 0xEF1C1847L, 0x3215D908L,
     0xDD433B37L, 0x24C2BA16L, 0x12A14D43L, 0x2A65C451L, 0x50940002L,
     0x133AE4DDL, 0x71DFF89EL, 0x10314E55L, 0x81AC77D6L, 0x5F11199BL,
     0x043556F1L, 0xD7A3C76BL, 0x3C11183BL, 0x5924A509L, 0xF28FE6EDL,
     0x97F1FBFAL, 0x9EBABF2CL, 0x1E153C6EL, 0x86E34570L, 0xEAE96FB1L,
     0x860E5E0AL, 0x5A3E2AB3L, 0x771FE71CL, 0x4E3D06FAL, 0x2965DCB9L,
     0x99E71D0FL, 0x803E89D6L, 0x5266C825L, 0x2E4CC978L, 0x9C10B36AL,
     0xC6150EBAL, 0x94E2EA78L, 0xA5FC3C53L, 0x1E0A2DF4L, 0xF2F74EA7L,
     0x361D2B3DL, 0x1939260FL, 0x19C27960L, 0x5223A708L, 0xF71312B6L,
     0xEBADFE6EL, 0xEAC31F66L, 0xE3BC4595L, 0xA67BC883L, 0xB17F37D1L,
     0x018CFF28L, 0xC332DDEFL, 0xBE6C5AA5L, 0x65582185L, 0x68AB9802L,
     0xEECEA50FL, 0xDB2F953BL, 0x2AEF7DADL, 0x5B6E2F84L, 0x1521B628L,
     0x29076170L, 0xECDD4775L, 0x619F1510L, 0x13CCA830L, 0xEB61BD96L,
     0x0334FE1EL, 0xAA0363CFL, 0xB5735C90L, 0x4C70A239L, 0xD59E9E0BL,
     0xCBAADE14L, 0xEECC86BCL, 0x60622CA7L, 0x9CAB5CABL, 0xB2F3846EL,
     0x648B1EAFL, 0x19BDF0CAL, 0xA02369B9L, 0x655ABB50L, 0x40685A32L,
     0x3C2AB4B3L, 0x319EE9D5L, 0xC021B8F7L, 0x9B540B19L, 0x875FA099L,
     0x95F7997EL, 0x623D7DA8L, 0xF837889AL, 0x97E32D77L, 0x11ED935FL,
     0x16681281L, 0x0E358829L, 0xC7E61FD6L, 0x96DEDFA1L, 0x7858BA99L,
     0x57F584A5L, 0x1B227263L, 0x9B83C3FFL, 0x1AC24696L, 0xCDB30AEBL,
     0x532E3054L, 0x8FD948E4L, 0x6DBC3128L, 0x58EBF2EFL, 0x34C6FFEAL,
     0xFE28ED61L, 0xEE7C3C73L, 0x5D4A14D9L, 0xE864B7E3L, 0x42105D14L,
     0x203E13E0L, 0x45EEE2B6L, 0xA3AAABEAL, 0xDB6C4F15L, 0xFACB4FD0L,
     0xC742F442L, 0xEF6ABBB5L, 0x654F3B1DL, 0x41CD2105L, 0xD81E799EL,
     0x86854DC7L, 0xE44B476AL, 0x3D816250L, 0xCF62A1F2L, 0x5B8D2646L,
     0xFC8883A0L, 0xC1C7B6A3L, 0x7F1524C3L, 0x69CB7492L, 0x47848A0BL,
     0x5692B285L, 0x095BBF00L, 0xAD19489DL, 0x1462B174L, 0x23820E00L,
     0x58428D2AL, 0x0C55F5EAL, 0x1DADF43EL, 0x233F7061L, 0x3372F092L,
     0x8D937E41L, 0xD65FECF1L, 0x6C223BDBL, 0x7CDE3759L, 0xCBEE7460L,
     0x4085F2A7L, 0xCE77326EL, 0xA6078084L, 0x19F8509EL, 0xE8EFD855L,
     0x61D99735L, 0xA969A7AAL, 0xC50C06C2L, 0x5A04ABFCL, 0x800BCADCL,
     0x9E447A2EL, 0xC3453484L, 0xFDD56705L, 0x0E1E9EC9L, 0xDB73DBD3L,
     0x105588CDL, 0x675FDA79L, 0xE3674340L, 0xC5C43465L, 0x713E38D8L,
     0x3D28F89EL, 0xF16DFF20L, 0x153E21E7L, 0x8FB03D4AL, 0xE6E39F2BL,
     0xDB83ADF7L},
    {0xE93D5A68L, 0x948140F7L, 0xF64C261CL, 0x94692934L, 0x411520F7L,
     0x7602D4F7L, 0xBCF46B2EL, 0xD4A20068L, 0xD4082471L, 0x3320F46AL,
     0x43B7D4B7L, 0x500061AFL, 0x1E39F62EL, 0x97244546L, 0x14214F74L,
     0xBF8B8840L, 0x4D95FC1DL, 0x96B591AFL, 0x70F4DDD3L, 0x66A02F45L,
     0xBFBC09ECL, 0x03BD9785L, 0x7FAC6DD0L, 0x31CB8504L, 0x96EB27B3L,
     0x55FD3941L, 0xDA2547E6L, 0xABCA0A9AL, 0x28507825L, 0x530429F4L,
     0x0A2C86DAL, 0xE9B66DFBL, 0x68DC1462L, 0xD7486900L, 0x680EC0A4L,
     0x27A18DEEL, 0x4F3FFEA2L, 0xE887AD8CL, 0xB58CE006L, 0x7AF4D6B6L,
     0xAACE1E7CL, 0xD3375FECL, 0xCE78A399L, 0x406B2A42L, 0x20FE9E35L,
     0xD9F385B9L, 0xEE39D7ABL, 0x3B124E8BL, 0x1DC9FAF7L, 0x4B6D1856L,
     0x26A36631L, 0xEAE397B2L, 0x3A6EFA74L, 0xDD5B4332L, 0x6841E7F7L,
     0xCA7820FBL, 0xFB0AF54EL, 0xD8FEB397L, 0x454056ACL, 0xBA489527L,
     0x55533A3AL, 0x20838D87L, 0xFE6BA9B7L, 0xD096954BL, 0x55A867BCL,
     0xA1159A58L, 0xCCA92963L, 0x99E1DB33L, 0xA62A4A56L, 0x3F3125F9L,
     0x5EF47E1CL, 0x9029317CL, 0xFDF8E802L, 0x04272F70L, 0x80BB155CL,
     0x05282CE3L, 0x95C11548L, 0xE4C66D22L, 0x48C1133FL, 0xC70F86DCL,
     0x07F9C9EEL, 0x41041F0FL, 0x404779A4L, 0x5D886E17L, 0x325F51EBL,
     0xD59BC0D1L, 0xF2BCC18FL, 0x41113564L, 0x257B7834L, 0x602A9C60L,
     0xDFF8E8A3L, 0x1F636C1BL, 0x0E12B4C2L, 0x02E1329EL, 0xAF664FD1L,
     0xCAD18115L, 0x6B2395E0L, 0x333E92E1L, 0x3B240B62L, 0xEEBEB922L,
     0x85B2A20EL, 0xE6BA0D99L, 0xDE720C8CL, 0x2DA2F728L, 0xD0127845L,
     0x95B794FDL, 0x647D0862L, 0xE7CCF5F0L, 0x5449A36FL, 0x877D48FAL,
     0xC39DFD27L, 0xF33E8D1EL, 0x0A476341L, 0x992EFF74L, 0x3A6F6EABL,
     0xF4F8FD37L, 0xA812DC60L, 0xA1EBDDF8L, 0x991BE14CL, 0xDB6E6B0DL,
     0xC67B5510L, 0x6D672C37L, 0x2765D43BL, 0xDCD0E804L, 0xF1290DC7L,
     0xCC00FFA3L, 0xB5390F92L, 0x690FED0BL, 0x667B9FFBL, 0xCEDB7D9CL,
     0xA091CF0BL, 0xD9155EA3L, 0xBB132F88L, 0x515BAD24L, 0x7B9479BFL,
     0x763BD6EBL, 0x37392EB3L, 0xCC115979L, 0x8026E297L, 0xF42E312DL,
     0x6842ADA7L, 0xC66A2B3BL, 0x12754CCCL, 0x782EF11CL, 0x6A124237L,
     0xB79251E7L, 0x06A1BBE6L, 0x4BFB6350L, 0x1A6B1018L, 0x11CAEDFAL,
     0x3D25BDD8L, 0xE2E1C3C9L, 0x44421659L, 0x0A121386L, 0xD90CEC6EL,
     0xD5ABEA2AL, 0x64AF674EL, 0xDA86A85FL, 0xBEBFE988L, 0x64E4C3FEL,
     0x9DBC8057L, 0xF0F7C086L, 0x60787BF8L, 0x6003604DL, 0xD1FD8346L,
     0xF6381FB0L, 0x7745AE04L, 0xD736FCCCL, 0x83426B33L, 0xF01EAB71L,
     0xB0804187L, 0x3C005E5FL, 0x77A057BEL, 0xBDE8AE24L, 0x55464299L,
     0xBF582E61L, 0x4E58F48FL, 0xF2DDFDA2L, 0xF474EF38L, 0x8789BDC2L,
     0x5366F9C3L, 0xC8B38E74L, 0xB475F255L, 0x46FCD9B9L, 0x7AEB2661L,
     0x8B1DDF84L, 0x846A0E79L, 0x915F95E2L, 0x466E598EL, 0x20B45770L,
     0x8CD55591L, 0xC902DE4CL, 0xB90BACE1L, 0xBB8205D0L, 0x11A86248L,
     0x7574A99EL, 0xB77F19B6L, 0xE0A9DC09L, 0x662D09A1L, 0xC4324633L,
     0xE85A1F02L, 0x09F0BE8CL, 0x4A99A025L, 0x1D6EFE10L, 0x1AB93D1DL,
     0x0BA5A4DFL, 0xA186F20FL, 0x2868F169L, 0xDCB7DA83L, 0x573906FEL,
     0xA1E2CE9BL, 0x4FCD7F52L, 0x50115E01L, 0xA70683FAL, 0xA002B5C4L,
     0x0DE6D027L, 0x9AF88C27L, 0x773F8641L, 0xC3604C06L, 0x61A806B5L,
     0xF0177A28L, 0xC0F586E0L, 0x006058AAL, 0x30DC7D62L, 0x11E69ED7L,
     0x2338EA63L, 0x53C2DD94L, 0xC2C21634L, 0xBBCBEE56L, 0x90BCB6DEL,
     0xEBFC7DA1L, 0xCE591D76L, 0x6F05E409L, 0x4B7C0188L, 0x39720A3DL,
     0x7C927C24L, 0x86E3725FL, 0x724D9DB9L, 0x1AC15BB4L, 0xD39EB8FCL,
     0xED545578L, 0x08FCA5B5L, 0xD83D7CD3L, 0x4DAD0FC4L, 0x1E50EF5EL,
     0xB161E6F8L, 0xA28514D9L, 0x6C51133CL, 0x6FD5C7E7L, 0x56E14EC4L,
     0x362ABFCEL, 0xDDC6C837L, 0xD79A3234L, 0x92638212L, 0x670EFA8EL,
     0x406000E0L},
    {0x3A39CE37L, 0xD3FAF5CFL, 0xABC27737L, 0x5AC52D1BL, 0x5CB0679EL,
     0x4FA33742L, 0xD3822740L, 0x99BC9BBEL, 0xD5118E9DL, 0xBF0F7315L,
     0xD62D1C7EL, 0xC700C47BL, 0xB78C1B6BL, 0x21A19045L, 0xB26EB1BEL,
     0x6A366EB4L, 0x5748AB2FL, 0xBC946E79L, 0xC6A376D2L, 0x6549C2C8L,
     0x530FF8EEL, 0x468DDE7DL, 0xD5730A1DL, 0x4CD04DC6L, 0x2939BBDBL,
     0xA9BA4650L, 0xAC9526E8L, 0xBE5EE304L, 0xA1FAD5F0L, 0x6A2D519AL,
     0x63EF8CE2L, 0x9A86EE22L, 0xC089C2B8L, 0x43242EF6L, 0xA51E03AAL,
     0x9CF2D0A4L, 0x83C061BAL, 0x9BE96A4DL, 0x8FE51550L, 0xBA645BD6L,
     0x2826A2F9L, 0xA73A3AE1L, 0x4BA99586L, 0xEF5562E9L, 0xC72FEFD3L,
     0xF752F7DAL, 0x3F046F69L, 0x77FA0A59L, 0x80E4A915L, 0x87B08601L,
     0x9B09E6ADL, 0x3B3EE593L, 0xE990FD5AL, 0x9E34D797L, 0x2CF0B7D9L,
     0x022B8B51L, 0x96D5AC3AL, 0x017DA67DL, 0xD1CF3ED6L, 0x7C7D2D28L,
     0x1F9F25CFL, 0xADF2B89BL, 0x5AD6B472L, 0x5A88F54CL, 0xE029AC71L,
     0xE019A5E6L, 0x47B0ACFDL, 0xED93FA9BL, 0xE8D3C48DL, 0x283B57CCL,
     0xF8D56629L, 0x79132E28L, 0x785F0191L, 0xED756055L, 0xF7960E44L,
     0xE3D35E8CL, 0x15056DD4L, 0x88F46DBAL, 0x03A16125L, 0x0564F0BDL,
     0xC3EB9E15L, 0x3C9057A2L, 0x97271AECL, 0xA93A072AL, 0x1B3F6D9BL,
     0x1E6321F5L, 0xF59C66FBL, 0x26DCF319L, 0x7533D928L, 0xB155FDF5L,
     0x03563482L, 0x8ABA3CBBL, 0x28517711L, 0xC20AD9F8L, 0xABCC5167L,
     0xCCAD925FL, 0x4DE81751L, 0x3830DC8EL, 0x379D5862L, 0x9320F991L,
     0xEA7A90C2L, 0xFB3E7BCEL, 0x5121CE64L, 0x774FBE32L, 0xA8B6E37EL,
     0xC3293D46L, 0x48DE5369L, 0x6413E680L, 0xA2AE0810L, 0xDD6DB224L,
     0x69852DFDL, 0x09072166L, 0xB39A460AL, 0x6445C0DDL, 0x586CDECFL,
     0x1C20C8AEL, 0x5BBEF7DDL, 0x1B588D40L, 0xCCD2017FL, 0x6BB4E3BBL,
     0xDDA26A7EL, 0x3A59FF45L, 0x3E350A44L, 0xBCB4CDD5L, 0x72EACEA8L,
     0xFA6484BBL, 0x8D6612AEL, 0xBF3C6F47L, 0xD29BE463L, 0x542F5D9EL,
     0xAEC2771BL, 0xF64E6370L, 0x740E0D8DL, 0xE75B1357L, 0xF8721671L,
     0xAF537D5DL, 0x4040CB08L, 0x4EB4E2CCL, 0x34D2466AL, 0x0115AF84L,
     0xE1B00428L, 0x95983A1DL, 0x06B89FB4L, 0xCE6EA048L, 0x6F3F3B82L,
     0x3520AB82L, 0x011A1D4BL, 0x277227F8L, 0x611560B1L, 0xE7933FDCL,
     0xBB3A792BL, 0x344525BDL, 0xA08839E1L, 0x51CE794BL, 0x2F32C9B7L,
     0xA01FBAC9L, 0xE01CC87EL, 0xBCC7D1F6L, 0xCF0111C3L, 0xA1E8AAC7L,
     0x1A908749L, 0xD44FBD9AL, 0xD0DADECBL, 0xD50ADA38L, 0x0339C32AL,
     0xC6913667L, 0x8DF9317CL, 0xE0B12B4FL, 0xF79E59B7L, 0x43F5BB3AL,
     0xF2D519FFL, 0x27D9459CL, 0xBF97222CL, 0x15E6FC2AL, 0x0F91FC71L,
     0x9B941525L, 0xFAE59361L, 0xCEB69CEBL, 0xC2A86459L, 0x12BAA8D1L,
     0xB6C1075EL, 0xE3056A0CL, 0x10D25065L, 0xCB03A442L, 0xE0EC6E0EL,
     0x1698DB3BL, 0x4C98A0BEL, 0x3278E964L, 0x9F1F9532L, 0xE0D392DFL,
     0xD3A0342BL, 0x8971F21EL, 0x1B0A7441L, 0x4BA3348CL, 0xC5BE7120L,
     0xC37632D8L, 0xDF359F8DL, 0x9B992F2EL, 0xE60B6F47L, 0x0FE3F11DL,
     0xE54CDA54L, 0x1EDAD891L, 0xCE6279CFL, 0xCD3E7E6FL, 0x1618B166L,
     0xFD2C1D05L, 0x848FD2C5L, 0xF6FB2299L, 0xF523F357L, 0xA6327623L,
     0x93A83531L, 0x56CCCD02L, 0xACF08162L, 0x5A75EBB5L, 0x6E163697L,
     0x88D273CCL, 0xDE966292L, 0x81B949D0L, 0x4C50901BL, 0x71C65614L,
     0xE6C6C7BDL, 0x327A140AL, 0x45E1D006L, 0xC3F27B9AL, 0xC9AA53FDL,
     0x62A80F00L, 0xBB25BFE2L, 0x35BDD2F6L, 0x71126905L, 0xB2040222L,
     0xB6CBCF7CL, 0xCD769C2BL, 0x53113EC0L, 0x1640E3D3L, 0x38ABBD60L,
     0x2547ADF0L, 0xBA38209CL, 0xF746CE76L, 0x77AFA1C5L, 0x20756060L,
     0x85CBFE4EL, 0x8AE88DD8L, 0x7AAAF9B0L, 0x4CF9AA7EL, 0x1948C25CL,
     0x02FB8A8CL, 0x01C36AE4L, 0xD6EBE1F9L, 0x90D4F869L, 0xA65CDEA0L,
     0x3F09252DL, 0xC208E69FL, 0xB74E6132L, 0xCE77E25BL, 0x578FDFE3L,
     0x3AC372E6L}};

// f函数
unsigned int f(unsigned int x) {
  unsigned int res;
  res = S[0][(x >> 24) & 0xff];
  res += S[1][(x >> 16) & 0xff];
  res ^= S[2][(x >> 8) & 0xff];
  res += S[3][x & 0xff];
  return res;
}

void encrypt(unsigned int* L, unsigned int* R) {
  for (size_t i = 0; i < 16; i += 2) {
    *L ^= P[i];
    *R ^= f(*L);
    *R ^= P[i + 1];
    *L ^= f(*R);
  }
  *L ^= P[16];
  *R ^= P[17];
  unsigned int temp = *L;
  *L = *R;
  *R = temp;
}

void decrypt(unsigned int* L, unsigned int* R) {
  for (size_t i = 16; i > 0; i -= 2) {
    *L ^= P[i + 1];
    *R ^= f(*L);
    *R ^= P[i];
    *L ^= f(*R);
  }
  *L ^= P[1];
  *R ^= P[0];
  unsigned int temp = *L;
  *L = *R;
  *R = temp;
}

void init(unsigned char* key, int keylen) {
  unsigned int l = 0, r = 0, data = 0;
  int index = 0;
  //对P数组和密钥进行逐位异或，必要时重用密钥
  for (size_t i = 0; i < 18; i++) {
    data = 0;
    for (size_t j = 0; j < 4; j++) {
      data <<= 8;
      data |= key[index];
      index++;
      if (index == keylen) {
        index = 0;
      }
    }
    P[i] ^= data;
  }
  // 使用当前的P数组和S-box对全0的64位分组使用BlowFish算法进行加密，用输出代替P[1]、P[2]
  // 重复以上步骤使用当前的P数组和S-box对上一步输出进行加密，并用输出代替P[3]、P[4]，
  //   直到按顺序替代所有的P数组和S-box中的元素为止
  for (size_t i = 0; i < 18; i += 2) {
    encrypt(&l, &r);
    P[i] = l;
    P[i + 1] = r;
  }
  for (size_t i = 0; i < 4; i++) {
    for (size_t j = 0; j < 256; j += 2) {
      encrypt(&l, &r);
      S[i][j] = l;
      S[i][j + 1] = r;
    }
  }
}

int main(int argc, char const* argv[]) {
  unsigned int l = 1;
  unsigned int r = 2;
  unsigned char* key = "ASimpleKey";
  init(key, 10);//init subkey
  encrypt(&l, &r);//encrypt
  printf("%x,%x\n", l, r);
  return 0;
}

TEA、XTEA、XXTEA

关于TEA系列算法

微型加密算法（Tiny Encryption Algorithm，TEA）是一种易于描述和执行的块密码，通常只需要很少的代码就可实现。其设计者是David Wheeler、Roger Needham

TEA的分组长度为64位，密钥长度为128位，采用Feistel网络，建议32次循环加密即64轮

XTEA是TEA的扩展，同样是一个64位块的Feistel密码，使用128位密钥，建议64轮

XXTEA是一个非平衡Feistel网络分组密码，在可变长度块上运行，这些块是32位大小的任意倍数（最小64位），使用128位密钥

TEA系列算法典型特征是采用密钥调度常数0x9e3779b9

加解密实现

TEA加解密实现

#include <stdio.h>
void encrypt(unsigned int* v, unsigned int* key) {
  unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
  for (size_t i = 0; i < 32; i++) {
    sum += delta;
    l += ((r << 4) + key[0]) ^ (r + sum) ^ ((r >> 5) + key[1]);
    r += ((l << 4) + key[2]) ^ (l + sum) ^ ((l >> 5) + key[3]);
  }
  v[0] = l;
  v[1] = r;
}

void decrypt(unsigned int* v, unsigned int* key) {
  unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
  sum = delta *32;
  for (size_t i = 0; i < 32; i++) {
    r -= ((l << 4) + key[2]) ^ (l + sum) ^ ((l >> 5) + key[3]);
    l -= ((r << 4) + key[0]) ^ (r + sum) ^ ((r >> 5) + key[1]);
    sum -= delta;
  }
  v[0] = l;
  v[1] = r;
}

int main(int argc, char const *argv[])
{
    //test
    unsigned int v[2]={1,2},key[4]={1,2,3,4};
    printf("%u,%u\n",v[0],v[1]);
    encrypt(v,key);
    printf("%u,%u\n",v[0],v[1]);
    decrypt(v,key);
    printf("%u,%u\n",v[0],v[1]);
    return 0;
}

XTEA加解密实现

#include <stdio.h>
void encrypt(unsigned int* v, unsigned int* key) {
  unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
  for (size_t i = 0; i < 32; i++) {
    l += (((r << 4) ^ (r >> 5)) + r) ^ (sum + key[sum & 3]);
    sum += delta;
    r += (((l << 4) ^ (l >> 5)) + l) ^ (sum + key[(sum >> 11) & 3]);
  }
  v[0] = l;
  v[1] = r;
}

void decrypt(unsigned int* v, unsigned int* key) {
  unsigned int l = v[0], r = v[1], sum = 0, delta = 0x9e3779b9;
  sum = delta * 32;
  for (size_t i = 0; i < 32; i++) {
    r -= (((l << 4) ^ (l >> 5)) + l) ^ (sum + key[(sum >> 11) & 3]);
    sum -= delta;
    l -= (((r << 4) ^ (r >> 5)) + r) ^ (sum + key[sum & 3]);
  }
  v[0] = l;
  v[1] = r;
}

int main(int argc, char const *argv[])
{
    //test
    unsigned int v[2]={1,2},key[4]={1,2,3,4};
    printf("%u,%u\n",v[0],v[1]);
    encrypt(v,key);
    printf("%u,%u\n",v[0],v[1]);
    decrypt(v,key);
    printf("%u,%u\n",v[0],v[1]);
    return 0;
}

XXTEA加解密实现

#include <stdbool.h>
#include <stdio.h>
#define MX \
  ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z))
bool btea(unsigned int* v, int n, unsigned int* k) {
  unsigned int z = v[n - 1], y = v[0], sum = 0, e, DELTA = 0x9e3779b9;
  unsigned int 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;
}

int main(int argc, char const* argv[]) {
  // test
  unsigned int v[2] = {1, 2}, key[4] = {1, 2, 3, 4};
  printf("%u,%u\n", v[0], v[1]);
  btea(v, 2, key);
  printf("%u,%u\n", v[0], v[1]);
  btea(v, -2, key);
  printf("%u,%u\n", v[0], v[1]);
  return 0;
}

XXTEA逆向分析

文件来源：2019RCTF babyre

该题大致为输入一个16位字符串经过多次变换最终输出Bingo! 即可，由于题目的原因出现多解，故还需满足md5(rctf{flag})==5f8243a662cf71bf31d2b2602638dc1d，此处不作解释，由于主要是讲解XXTEA的逆向分析，其他过程暂且不细说，我们看到其中最关键的加密函数sub_55A0DF892CE0。

signed __int64 __fastcall sub_55A0DF892CE0(int *a1, signed int a2, __int64 a3)
{
  v3 = a3;
  v4 = a2;
  v5 = *a1;
  v43 = a2;
  if ( a2 > 1 )
  {
    v6 = a2 - 1;
    v7 = &a1[a2 - 1];
    v8 = 0;
    v9 = *v7;
    v10 = ((a2 - 4) & 0xFFFFFFFE) + 2;
    v45 = 0x9E3779B9 * (52 / a2) - 0x4AB325AA;
    do
    {
      v8 -= 0x61C88647;
      v11 = v8 >> 2;
      if ( v43 <= 3 )
      {
        v14 = 0;
      }
      else
      {
        v12 = *a1;
        v13 = a1;
        v14 = 0;
        do
        {
          v15 = v13[1];
          v13 += 2;
          v16 = (v9 ^ *(_DWORD *)(v3 + 4LL * (((unsigned __int8)v14 ^ (unsigned __int8)v11) & 3))) + (v15 ^ v8);
          v17 = v14 + 1;
          v14 += 2;
          v18 = v12 + ((((v9 >> 5) ^ 4 * v15) + ((v15 >> 3) ^ 16 * v9)) ^ v16);
          v12 = *v13;
          *(v13 - 2) = v18;
          v9 = v15
             + (((4 * v12 ^ (v18 >> 5)) + (16 * v18 ^ (v12 >> 3))) ^ ((v12 ^ v8)
                                                                    + (v18 ^ *(_DWORD *)(v3
                                                                                       + 4LL
                                                                                       * (((unsigned __int8)v11 ^ v17) & 3)))));
          *(v13 - 1) = v9;
        }
        while ( v10 != v14 );
      }
      v19 = &a1[v14];
      do
      {
        v20 = v19[1];
        v21 = v11 ^ v14++;
        ++v19;
        v22 = *(v19 - 1)
            + (((v9 ^ *(_DWORD *)(v3 + 4LL * (v21 & 3))) + (v20 ^ v8)) ^ ((16 * v9 ^ (v20 >> 3)) + ((v9 >> 5) ^ 4 * v20)));
        *(v19 - 1) = v22;
        v9 = v22;
      }
      while ( v6 > v14 );
      v9 = *v7
         + (((v22 ^ *(_DWORD *)(v3 + 4LL * (((unsigned __int8)v6 ^ (unsigned __int8)v11) & 3))) + (*a1 ^ v8)) ^ ((4 * *a1 ^ (v22 >> 5)) + (16 * v22 ^ ((unsigned int)*a1 >> 3))));
      *v7 = v9;
    }
    while ( v8 != v45 );
    return 0LL;
  }
  result = 1LL;
  if ( a2 < -1 )
  {
    v24 = -a2;
    v25 = 0x9E3779B9 * (52 / v24 + 6);
    if ( v25 )
    {
      v26 = &a1[v24 - 1];
      v27 = ~v4;
      v44 = &a1[~v4];
      v28 = ~v4 - 2 - ((~v4 - 3) & 0xFFFFFFFE);
      do
      {
        v29 = v25 >> 2;
        if ( v27 <= 2 )
        {
          v31 = v27;
        }
        else
        {
          v30 = v44;
          v31 = v27;
          v32 = *v44;
          do
          {
            v33 = *(v30 - 1);
            v30 -= 2;
            v34 = v32;
            v32 = *v30;
            v35 = ((v5 ^ v25) + (v33 ^ *(_DWORD *)(v3 + 4LL * (((unsigned __int8)v31 ^ (unsigned __int8)v29) & 3)))) ^ ((4 * v5 ^ (v33 >> 5)) + ((v5 >> 3) ^ 16 * v33));
            v36 = v31 - 1;
            v31 -= 2;
            v37 = v34 - v35;
            v38 = *v30;
            v30[2] = v37;
            v5 = v33
               - (((16 * v38 ^ (v37 >> 3)) + ((v32 >> 5) ^ 4 * v37)) ^ ((v32 ^ *(_DWORD *)(v3
                                                                                         + 4LL
                                                                                         * (((unsigned __int8)v29 ^ v36) & 3)))
                                                                      + (v25 ^ v37)));
            v30[1] = v5;
          }
          while ( v28 != v31 );
        }
        v39 = &a1[v31];
        do
        {
          v40 = *(v39 - 1);
          --v39;
          v5 = v39[1]
             - (((v5 ^ v25) + (v40 ^ *(_DWORD *)(v3 + 4LL * (((unsigned __int8)v29 ^ (unsigned __int8)v31) & 3)))) ^ (((v5 >> 3) ^ 16 * v40) + ((v40 >> 5) ^ 4 * v5)));
          v39[1] = v5;
          --v31;
        }
        while ( v31 );
        v41 = *a1
            - (((((unsigned int)*v26 >> 5) ^ 4 * v5) + (16 * *v26 ^ (v5 >> 3))) ^ ((*(_DWORD *)(v3 + 4LL * (v29 & 3)) ^ *v26)
                                                                                 + (v25 ^ v5)));
        v42 = v25 == 0x9E3779B9;
        v25 += 0x61C88647;
        v5 = v41;
        *a1 = v41;
      }
      while ( !v42 );
    }
    return 0LL;
  }
  return result;
}

我们可以看到反编译的伪代码也是十分清晰的，纵观整个函数，整个函数过程都围绕着0x9E3779B9这个魔数，相信很多人都有似曾相识的感觉，没错！该函数与上文的XXTEA加解密实现结构基本相同，实现了XXTEA加解密。接下来我们看到函数的调用

sub_55A0DF892CE0(v, -(v10 >> 2), key);  // stea(v,-2,key)

结合其他有关信息可以简单看出函数参数v为两个32位无符号数， -(v10 >> 2)的值为-2，key为128位密钥，它们是0xE0C7E0C7, 0xC6F1D3D7, 0xC6D3C6D3, 0xC4D0D2CE，此处调用了XXTEAdecode对两个32位无符号数进行解密，解密结果与之后的常量异或后比较判断

整个题目的核心算法就是XXTEA，只要识别出该算法，那么逆向将变得非常简单，逻辑无非就是输入一个16进制字符串之后hexencode，得到一个64位无符号数（即2个32位无符号数），然后将之2个32位无符号数xxteadecrypt得到新的64位无符号数，此处要求最后一个字节的值小于0x4，并将第（8-最后一个字节的值+1）字节的值置为00，而后将之经下一个函数进行一些位操作验证结果是否等于0x69e2,这一步并不改变原有值无视之，最终验证按字节与0x17异或出来结果是否为Bingo!，结合上面猜测第7字节的值为00，最后一个字节值为0x02，且md5(rctf{flag})==5f8243a662cf71bf31d2b2602638dc1d，由此可以确定最终解密后的64位无符号数的值为0x02XX367870797e55(小端序)，直接写脚本就可以爆破次高8位即可，依次就可以得到该题的flag了

#include <openssl/md5.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
// -lcrypto
string MD5(const string& src) {
  MD5_CTX ctx;

  string md5_string;
  unsigned char md[16] = {0};
  char tmp[33] = {0};

  MD5_Init(&ctx);
  MD5_Update(&ctx, src.c_str(), src.size());
  MD5_Final(md, &ctx);

  for (int i = 0; i < 16; ++i) {
    memset(tmp, 0x00, sizeof(tmp));
    sprintf(tmp, "%02X", md[i]);
    md5_string += tmp;
  }
  return md5_string;
}

string aaa(unsigned int* v) {
  string str;
  for (size_t i = 0; i < 2; i++) {
    for (size_t j = 0; j < 8; j += 2) {
      unsigned char cur = v[i] & 0xff;
      str += ((cur & 0xf0) >> 4) < 10 ? (((cur & 0xf0) >> 4) + 0x30)
                                      : (((cur & 0xf0) >> 4) + 0x57);
      str += (cur & 0x0f) < 10 ? ((cur & 0x0f) + 0x30) : ((cur & 0x0f) + 0x57);
      v[i] >>= 8;
    }
  }
  return str;
}

#define MX \
  ((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z))
bool btea(unsigned int* v, int n, unsigned int* k) {
  unsigned int z = v[n - 1], y = v[0], sum = 0, e, DELTA = 0x9e3779b9;
  unsigned int 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;
}

int main() {
  // 55 7e 79 70 78 36 xx 02
  unsigned int t[2] = {0x70797e55, 0x02003678};
  unsigned int v[2] = {0, 0};
  unsigned int key[4] = {0xE0C7E0C7, 0xC6F1D3D7, 0xC6D3C6D3, 0xC4D0D2CE};
  string flagmd5 = "5F8243A662CF71BF31D2B2602638DC1D";

  for (unsigned long long i = 0x0; i <= 0xff; i += 0x1) {
    v[0] = t[0];
    v[1] = t[1] | (i << 16);
    string flag = "";
    flag += "rctf{";
    btea(v, 2, key);
    flag += aaa(v);
    flag += "}";
    cout << flag << endl;
    if (MD5(flag) == flagmd5) {
      cout << "success!" << endl;
      cout << flag << endl;
      return 0;
    }
  }
  return 0;
}

TX TEA魔改算法

TX 将TEA算法魔改成16轮（TEA保密的最低要求）并且广泛应用

相关内容可以看这里腾讯TEA加密算法

主要就是将加密轮次改为16轮，并且采用改进的CBC模式加密

总结

对于TEA系列算法的识别只要依据常数0x9e3779b9并且其相关加密结构就可以很容易判断是TEA、XTEA亦或XXTEA，之后只要找到其密文以及加密密钥辅以以上加解密实现代码就可以很快解密了，TEA算法在逆向分析中，IDA反编译以后一般都是比较清晰的，只要有一定的了解就能轻而易举的识别出对应算法，而后动态调试验证即可，至于findcrypto3插件识别也是依据常数识别的，所以只要知道这个特征即可。

附件

TEA系列算法源码

2019RCTF babyre

参考文献

Tiny Encryption Algorithm

XTEA

XXTEA

TEA、XTEA、XXTEA加密解密算法

RC4

关于RC4算法

RC4（Rivest Cipher 4）是一种流加密算法，密钥长度可变。加解密使用相同的密钥，美国密码学家Ronald Rivest在1987年设计的。

RC4由伪随机数生成器和异或运算组成。密钥长度可变，范围是[1,255]。RC4一个字节一个字节地加解密。给定一个密钥，伪随机数生成器接受密钥并产生一个S盒。S盒用来加密数据，而且在加密过程中S盒会变化。

由于异或运算的对合性，RC4加密解密使用同一套算法。

加解密实现

伪代码

KSA(the Key-Scheduling Algorithm)

通过密钥调度算法（KSA）初始化长度为256的S盒。第一个for循环将0到255的互不重复的元素装入S盒。第二个for循环根据密钥打乱S盒。

for i from 0 to 255
    S[i] := i
endfor
j := 0
for( i=0 ; i<256 ; i++)
    j := (j + S[i] + key[i mod keylength]) % 256
    swap values of S[i] and S[j]
endfor

PGRA(the Pseudo-Random Generation Algorithm)

下面i,j是两个指针。每收到一个字节，就进行while循环。通过一定的算法（(a),(b)）定位S盒中的一个元素，并与输入字节异或，得到k。循环中还改变了S盒（(c)）。如果输入的是明文，输出的就是密文；如果输入的是密文，输出的就是明文。

i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256   //a
    j := (j + S[i]) mod 256 //b
    swap values of S[i] and S[j]  //c
    k := inputByte ^ S[(S[i] + S[j]) % 256]
    output K
endwhile

C语言实现

#include <stdio.h>
#include <string.h>
void RC4_init(unsigned char* Sbox, unsigned char* key, int keylen) {
  for (size_t i = 0; i < 256; i++) {
    Sbox[i] = i;
  }
  size_t j = 0;
  for (size_t i = 0; i < 256; i++) {
    j = (j + Sbox[i] + key[i % keylen]) % 256;
    char temp = Sbox[i];
    Sbox[i] = Sbox[j];
    Sbox[j] = temp;
  }
}

void RC4(unsigned char* Sbox,
         unsigned char* data,
         unsigned char* key,
         int datalen,
         int keylen) {
  RC4_init(Sbox, key, keylen);
  size_t i = 0, j = 0;
  for (size_t k = 0; k < datalen; k++) {
    i = (i + 1) % 256;
    j = (j + Sbox[i]) % 256;
    char temp = Sbox[i];
    Sbox[i] = Sbox[j];
    Sbox[j] = temp;
    data[k] ^= Sbox[(Sbox[i] + Sbox[j]) % 256];
  }
}

int main(int argc, char const* argv[]) {
  //   test
  unsigned char Sbox[256] = {0};
  unsigned char data[] = "helloworld";
  unsigned char key[] = "1234";
  RC4(Sbox, data, key, strlen(data), strlen(key));
  printf("%s\n", data);
  RC4(Sbox, data, key, strlen(data), strlen(key));
  printf("%s\n", data);
  puts("-----------------------------");
  unsigned char datahex[] = {0x68, 0x65, 0x6c, 0x6c, 0x6f, 0x77,
                             0x6f, 0x72, 0x6c, 0x64, '\0'};
  unsigned char keyhex[] = {0x31, 0x32, 0x33, 0x34, '\0'};
  //   strlen(key)函数求的是字符串的实际长度，它求得方法是从开始到遇到第一个'\0'
  RC4(Sbox, datahex, keyhex, strlen(datahex), strlen(keyhex));
  printf("%s\n", datahex);
  for (size_t i = 0; i < strlen(datahex); i++)
    printf("%.2x", (int)datahex[i]);
  puts("");
  RC4(Sbox, datahex, keyhex, strlen(datahex), strlen(keyhex));
  printf("%s\n", datahex);
  for (size_t i = 0; i < strlen(datahex); i++)
    printf("%.2x", (int)datahex[i]);
  puts("");
  return 0;
}

逆向分析

RC4反汇编/反编译之后一般有两个函数，一个就是用key初始Sbox，另外一个就是按字节加密字符串，以下两个函数是RC4加密反编译的结果

unsigned __int64 __fastcall RC4_init(__int64 a1, __int64 a2, int a3)
{
  unsigned __int64 result; // rax
  unsigned __int8 v4; // ST1F_1
  unsigned __int64 i; // [rsp+1Ch] [rbp-18h]
  __int64 v6; // [rsp+24h] [rbp-10h]
  unsigned __int64 j; // [rsp+2Ch] [rbp-8h]

  for ( i = 0LL; i <= 0xFF; ++i )
  {
    result = a1 + i;
    *(_BYTE *)(a1 + i) = i;
  }
  LOBYTE(v6) = 0;
  for ( j = 0LL; j <= 0xFF; ++j )
  {
    v6 = (unsigned __int8)(*(_BYTE *)(a1 + j) + v6 + *(_BYTE *)(j % a3 + a2));
    v4 = *(_BYTE *)(a1 + j);
    *(_BYTE *)(j + a1) = *(_BYTE *)(a1 + v6);
    result = v4;
    *(_BYTE *)(v6 + a1) = v4;
  }
  return result;
}

__int64 __fastcall RC4(__int64 a1, __int64 a2, __int64 a3, int a4, int a5)
{
  char v5; // ST27_1
  __int64 result; // rax
  int v7; // [rsp+4h] [rbp-3Ch]
  __int64 v8; // [rsp+28h] [rbp-18h]
  __int64 v9; // [rsp+30h] [rbp-10h]
  unsigned __int64 i; // [rsp+38h] [rbp-8h]

  v7 = a4;
  RC4_init(a1, a3, a5);
  LOBYTE(v8) = 0;
  LOBYTE(v9) = 0;
  for ( i = 0LL; ; ++i )
  {
    result = v7;
    if ( v7 <= i )
      break;
    v8 = (unsigned __int8)(v8 + 1);
    v9 = (unsigned __int8)(*(_BYTE *)(a1 + v8) + v9);
    v5 = *(_BYTE *)(a1 + v8);
    *(_BYTE *)(v8 + a1) = *(_BYTE *)(a1 + v9);
    *(_BYTE *)(v9 + a1) = v5;
    *(_BYTE *)(a2 + i) ^= *(_BYTE *)((unsigned __int8)(*(_BYTE *)(a1 + v8) + *(_BYTE *)(a1 + v9)) + a1);
  }
  return result;
}

用伪随机数数列初始化Sbox是其最大的特征，另外一个特征就是无论是初始化Sbox还是加密过程都大量用到unsigned __int8也就是加密过程中的mod256，有一些可执行文件反编译之后就直接是mod256，这更好判断，一般RC4题型都是结合base64encode等其他编码方法出题的，解密只要找到key和加密后的字符串利用以上代码解密即可

hash算法

MD5

关于MD5

MD5消息摘要算法，一种被广泛使用的密码散列函数，可以产生出一个128位（16字节）的散列值（hash value），用于确保信息传输完整一致。

算法原理

数据填充

填充消息使其长度与448模512同余，即使长度满足要求也需填充，填充方法是：附加一个1在消息后面，然后用0填充，直到消息长度与448模512同余，至少填充1位，至多填充512位

添加长度

在第一步的结果之后附加上64位的消息长度，若消息长度大于2^64则只记录其低64位，附加之后消息长度正好是512的倍数

初始化变量

A=0X67452301L，B=0XEFCDAB89L，C=0X98BADCFEL，D=0X10325476L

4.处理分组数据并输出

以512位一一个分组由类似的64次循环构成，分成4组16次。F 一个非线性函数；一个函数运算一次。Mi 表示一个 32-bits 的输入数据，Ki表示一个 32-bits 常数，用来完成每次不同的计算。

四个非线性函数为

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) )

待到所有分组处理完毕后输出一个128bit的散列结果

伪代码(from wiki)

//Note: All variables are unsigned 32 bits and wrap modulo 2^32 when calculating
var int[64] r, k

//r specifies the per-round shift amounts
r[ 0..15]：= {7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22} 
r[16..31]：= {5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20}
r[32..47]：= {4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23}
r[48..63]：= {6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21}

//Use binary integer part of the sines of integers as constants:
for i from 0 to 63
    k[i] := floor(abs(sin(i + 1)) × 2^32)

//Initialize variables:
var int h0 := 0x67452301
var int h1 := 0xEFCDAB89
var int h2 := 0x98BADCFE
var int h3 := 0x10325476

//Pre-processing:
append "1" bit to message
append "0" bits until message length in bits ≡ 448 (mod 512)
append bit length of message as 64-bit little-endian integer to message

//Process the message in successive 512-bit chunks:
for each 512-bit chunk of message
    break chunk into sixteen 32-bit little-endian words w[i], 0 ≤ i ≤ 15

    //Initialize hash value for this chunk:
    var int a := h0
    var int b := h1
    var int c := h2
    var int d := h3

    //Main loop:
    for i from 0 to 63
        if 0 ≤ i ≤ 15 then
            f := (b and c) or ((not b) and d)
            g := i
        else if 16 ≤ i ≤ 31
            f := (d and b) or ((not d) and c)
            g := (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47
            f := b xor c xor d
            g := (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63
            f := c xor (b or (not d))
            g := (7×i) mod 16
 
        temp := d
        d := c
        c := b
        b := leftrotate((a + f + k[i] + w[g]),r[i]) + b
        a := temp
    Next i
    //Add this chunk's hash to result so far:
    h0 := h0 + a
    h1 := h1 + b 
    h2 := h2 + c
    h3 := h3 + d
End ForEach
var int digest := h0 append h1 append h2 append h3 //(expressed as little-endian)

C语言实现

from https://github.com/pod32g/MD5

// from https://github.com/pod32g/MD5
/*
 * Simple MD5 implementation
 *
 * Compile with: gcc -o md5 md5.c
 */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Constants are the integer part of the sines of integers (in radians) * 2^32.
const uint32_t k[64] = {
    0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a,
    0xa8304613, 0xfd469501, 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
    0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821, 0xf61e2562, 0xc040b340,
    0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
    0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8,
    0x676f02d9, 0x8d2a4c8a, 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
    0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70, 0x289b7ec6, 0xeaa127fa,
    0xd4ef3085, 0x04881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
    0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92,
    0xffeff47d, 0x85845dd1, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
    0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391};

// r specifies the per-round shift amounts
const uint32_t r[] = {7,  12, 17, 22, 7,  12, 17, 22, 7,  12, 17, 22, 7,
                      12, 17, 22, 5,  9,  14, 20, 5,  9,  14, 20, 5,  9,
                      14, 20, 5,  9,  14, 20, 4,  11, 16, 23, 4,  11, 16,
                      23, 4,  11, 16, 23, 4,  11, 16, 23, 6,  10, 15, 21,
                      6,  10, 15, 21, 6,  10, 15, 21, 6,  10, 15, 21};

// leftrotate function definition
#define LEFTROTATE(x, c) (((x) << (c)) | ((x) >> (32 - (c))))

void to_bytes(uint32_t val, uint8_t* bytes) {
  bytes[0] = (uint8_t)val;
  bytes[1] = (uint8_t)(val >> 8);
  bytes[2] = (uint8_t)(val >> 16);
  bytes[3] = (uint8_t)(val >> 24);
}

uint32_t to_int32(const uint8_t* bytes) {
  return (uint32_t)bytes[0] | ((uint32_t)bytes[1] << 8) |
         ((uint32_t)bytes[2] << 16) | ((uint32_t)bytes[3] << 24);
}

void md5(const uint8_t* initial_msg, size_t initial_len, uint8_t* digest) {
  // These vars will contain the hash
  uint32_t h0, h1, h2, h3;

  // Message (to prepare)
  uint8_t* msg = NULL;

  size_t new_len, offset;
  uint32_t w[16];
  uint32_t a, b, c, d, i, f, g, temp;

  // Initialize variables - simple count in nibbles:
  h0 = 0x67452301;
  h1 = 0xefcdab89;
  h2 = 0x98badcfe;
  h3 = 0x10325476;

  // Pre-processing:
  // append "1" bit to message
  // append "0" bits until message length in bits ≡ 448 (mod 512)
  // append length mod (2^64) to message

  for (new_len = initial_len + 1; new_len % (512 / 8) != 448 / 8; new_len++)
    ;

  msg = (uint8_t*)malloc(new_len + 8);
  memcpy(msg, initial_msg, initial_len);
  msg[initial_len] =
      0x80;  // append the "1" bit; most significant bit is "first"
  for (offset = initial_len + 1; offset < new_len; offset++)
    msg[offset] = 0;  // append "0" bits

  // append the len in bits at the end of the buffer.
  to_bytes(initial_len * 8, msg + new_len);
  // initial_len>>29 == initial_len*8>>32, but avoids overflow.
  to_bytes(initial_len >> 29, msg + new_len + 4);

  // Process the message in successive 512-bit chunks:
  // for each 512-bit chunk of message:
  for (offset = 0; offset < new_len; offset += (512 / 8)) {
    // break chunk into sixteen 32-bit words w[j], 0 ≤ j ≤ 15
    for (i = 0; i < 16; i++)
      w[i] = to_int32(msg + offset + i * 4);

    // Initialize hash value for this chunk:
    a = h0;
    b = h1;
    c = h2;
    d = h3;

    // Main loop:
    for (i = 0; i < 64; i++) {
      if (i < 16) {
        f = (b & c) | ((~b) & d);
        g = i;
      } else if (i < 32) {
        f = (d & b) | ((~d) & c);
        g = (5 * i + 1) % 16;
      } else if (i < 48) {
        f = b ^ c ^ d;
        g = (3 * i + 5) % 16;
      } else {
        f = c ^ (b | (~d));
        g = (7 * i) % 16;
      }

      temp = d;
      d = c;
      c = b;
      b = b + LEFTROTATE((a + f + k[i] + w[g]), r[i]);
      a = temp;
    }

    // Add this chunk's hash to result so far:
    h0 += a;
    h1 += b;
    h2 += c;
    h3 += d;
  }

  // cleanup
  free(msg);

  // var char digest[16] := h0 append h1 append h2 append h3 //(Output is in
  // little-endian)
  to_bytes(h0, digest);
  to_bytes(h1, digest + 4);
  to_bytes(h2, digest + 8);
  to_bytes(h3, digest + 12);
}

int main(int argc, char** argv) {
  char* msg;
  size_t len;
  int i;
  uint8_t result[16];

  if (argc < 2) {
    printf("usage: %s 'string'\n", argv[0]);
    return 1;
  }
  msg = argv[1];

  len = strlen(msg);

  md5((uint8_t*)msg, len, result);

  // display result
  for (i = 0; i < 16; i++)
    printf("%2.2x", result[i]);
  puts("");

  return 0;
}

md5逆向分析

逆向分析中如果软件采用openssl等加密库载入od、ida显而易见就可知是md5加密，而对于一些原生的c、c++等语言实现的md5加密算法，也可以通过md5初始化变量这个特征来实现，下面是一个md5加密过程反汇编的结果

push    ebp
mov     ebp, esp
sub     esp, 98h
mov     [ebp+var_40], 0
mov     [ebp+var_C], 67452301h
mov     [ebp+var_10], 0EFCDAB89h
mov     [ebp+var_14], 98BADCFEh
mov     [ebp+var_18], 10325476h
mov     eax, [ebp+arg_4]
add     eax, 1
mov     [ebp+var_1C], eax
jmp     short loc_4015B5

显而易见程序初始化了4个变量，恰好是A=0X67452301L，B=0XEFCDAB89L，C=0X98BADCFEL，D=0X10325476L，据此可以初步识别为md5算法，继续向下追踪明文填充、分组处理进而可以判断加密过程是否为md5算法。

对于 md5(input) == 常量一般只能通过诸如爆破的方法求出input，而更多的软件一般都是采用 md5(input) == sn对此破解即变得相当简单，简单分析是否为md5变种亦或是对sn还采取了其他算法加密、编码，就可以依此来编写注册机。

md5穷举

md5算法本身不可逆，解密都是基于彩虹表(cmd5)、暴力破解工具(hashcat)、以及字典

cmd5(cmd5实时查询已收录11位及11位以下数字，8位小写字母，7位小写字母加数字，1-6位大小写字母+数字+特殊字符)

hashcat

hashcat 用法

md5碰撞

2004年，王小云教授提出了非常高效的MD5碰撞方法。

2009年，冯登国、谢涛利用差分攻击，将MD5的碰撞算法复杂度进一步降低。

以下是一个md5碰撞的例子

文件a二进制为

4DC968FF0EE35C209572D4777B721587D36FA7B21BDC56B74A3DC0783E7B9518AFBFA200A8284BF36E8E4B55B35F427593D849676DA0D1555D8360FB5F07FEA2

文件b二进制为

4DC968FF0EE35C209572D4777B721587D36FA7B21BDC56B74A3DC0783E7B9518AFBFA202A8284BF36E8E4B55B35F427593D849676DA0D1D55D8360FB5F07FEA2

两个文件都具有共同的md5值008ee33a9d58b51cfeb425b0959121c9

总结

MD5算法已经不具备安全性，不应将之运用于密码存储、软件加解密等应用上，当然在当前，MD5算法因其普遍、稳定、快速的特点，仍广泛应用于普通数据的错误检查领域。

附件

MD5encrypt 加密源码及可执行文件

MD5碰撞例子