参考文章：

RC5

RC5 分组密钥算法 C语言实现

背景与历史

RC5是Ron Rivest开发的对称密钥块加密算法。RC5的主要特性是很快，只是用基本的计算机运算（加、异或、移位等），轮数可变，密钥位数可变，从而大大增加灵活性。需要不同安全性的应用程序可以相应设置这些值。RC5的另一个重要特性是执行所需的内存更少。

RC5工作的基本原理

RC5的字长（即输入明文块的长度）、轮数和密钥8位字节数都是可变的。一旦确认之后，这些值在执行特定的加密算法时保持不变。这些变量在执行特定的RC5实例之前是可变的，可以从取值范围中选择。而DES的块长只能是64位，密钥长度只能是56位；IDEA的块长只能是64位，密钥长度只能是128位。下表列出了RC5一些参数的取值范围：

（1）明文块长可以是32、64或者128位（使用2个块）

（2）密钥长度为0~2040位（指定了8位密钥的取值）

RC5的输出是密文，与输入明文具有相同的参数。由于RC5算法的三个参数可以改变数值，因此RC5算法的特定实例记作RC5-w/r/b，其中w为字长（位），r为轮数，b为密钥的8位字节数。这样，RC5-32/16/16表示为RC5的块长为64位（注：RC5使用两个字块）、16轮加密和16字节密钥。Ron Rivest推荐的最低安全版本为RC5-32/16/16。

RC5 算法流程概述

  • 分组大小：两个 w-bit（32-bit）字 = 一共64位
  • 输入：两个32-bit字 (A,B)
  • 密钥扩展：生成 2r+2 个32-bit子密钥
  • 加密轮数：r轮

每一轮：

  1. A = ((A ⊕ B) <<< B) + S[2i]
  2. B = ((B ⊕ A) <<< A) + S[2i+1]

解密就是逆过程。

操作原理(这边以RC5-32/12/16为例)

由于使用上述记法，RC5初看起来比较复杂。首先介绍RC5的工作原理，为了便于理解RC5算法，假设输入明文块的长度为64位，其他块长的操作原理是一样的。

在一次性初始操作中，输入明文块分成两个32位块A和B，前两个子密钥（稍后会介绍如何生成）S[0]和S[1]分别加进A和B，分别产生C和D，表示一次性操作结束。

然后开始各轮，每一轮完成系列操作：

（1）位异或运算；

（2）循环左移；

（3）对C和D增加下一个子密钥，先是加法运算，然后将结果用2的w次方求模（由于这里w=32，因此为2的32次方）。

RC5 的工作原理，如下图所示：

从上图可以看出，初始操作有两步，然后是几轮操作，轮数可以取0~255。也可以从中看出，一个块的输出是另一个块的输入，是整个逻辑很难破译。

加密代码如下：

1
2
3
//循环位移操作
#define ROTL(x, y) (((x) << ((y) & (w - 1))) | ((x) >> (w - ((y) & (w - 1)))))
#define ROTR(x, y) (((x) >> ((y) & (w - 1))) | ((x) << (w - ((y) & (w - 1)))))
1
2
3
4
5
6
7
8
uint32_t A = in[0] + S[0];
uint32_t B = in[1] + S[1];
for (int i = 1; i <= r; i++) {
    A = ROTL(A ^ B, B) + S[2 * i];
    B = ROTL(B ^ A, A) + S[2 * i + 1];
}
//in[2]是明文被分为2个块
//ROTL是循环位移

扩展密钥

子密钥生成

这一步使用两个常量P和Q。生成的子密钥数组称为S，第一个子密钥为S[0]用P值初始化。

每个后续子密钥（S[1]，S[2]，…）根据前面的子密钥和常量Q求出，用2的32次方

求模。这个过程要进行2(r+1)-1次，其中r位轮数。下图显示了子密钥生成的数学形式：

这个过程把主密钥 K 扩展为 S[0..25] 子密钥。

分步讲解：

1
void generateSubkeys(uint8_t* K, uint32_t* S)

将字节数组 K 转换成 4个32位整数 L[0..3]

1
2
3
4
5
6
  uint32_t L[c] = { 0 };

// 将密钥转换为小端序的32位字
  for (int i = 0; i < b; i++) {
  L[i / 4] |= ((uint32_t)K[i]) << (8 * (i % 4));
  }

示意：

1
2
K[0..15] --> L[0..3]
每4字节组合成一个32位整数

例如：

1
2
K[0]=0xAA K[1]=0xBB K[2]=0xCC K[3]=0xDD
L[0]=0xDDCCBBAA

初始化子密钥数组 S[0..25]

1
2
3
4
S[0] = 0xB7E15163;
for (int i = 1; i < t; i++) {
    S[i] = S[i-1] + 0x9E3779B9;
}

这里用两个“幻数”：

  • PW = 0xB7E15163 （2^w * (e - 2)）
  • QW = 0x9E3779B9 （2^w * (Golden Ratio - 1)） 这是RC5官方定义。

这一部分按照原理来说的话应该是(S[i-1] + 0x9E3779B9)% (1<<32)

（% (1<<32)就是取2的32次方的mod）

但这个代码里面没有，为什么呢？

因为我用的是uint32_t类型

  • 在 C 语言里 uint32_t 类型是无符号32位整数。

  • 当超过 2^32 时，会自动溢出并回绕到模 2^32 的余数。

子密钥混合

子密钥混合阶段将子密钥S[]，S[]，…与原密钥L[]，L[]，…混合。其数学形式如下图所示：

如上图所示，首先初始化i，j，A和B；其次将子密钥与A和B相加，并左移3位，赋给A和该子密钥，将原密钥与A和B相加，并左移A加B位，赋给B和该原密钥；最后，将i加1，并用2(r+1)求模，将j加1，并用c求模，循环3×n次结束。

注：c是原密钥中最后一个子密钥部分，<<<表示循环左移。

代码实现

1
2
3
4
5
6
7
8
uint32_t A = 0, B = 0;
int i = 0, j = 0;
for (int k = 0; k < 3 * t; k++) {
    A = S[i] = ROTL(S[i] + A + B, 3);
    B = L[j] = ROTL(L[j] + A + B, A + B);
    i = (i + 1) % t;
    j = (j + 1) % c;
}

整体加解密代码实现（以RC5-32/12/16为例）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <stdint.h>
#include <math.h>

// RC5 parameters
#define w 32            // 字长
#define r 12            // 加密轮数
#define b 16            // 密钥长度
#define t (2 * r + 2)   // 子密钥数
#define c (b * 8 / w)   // 主密钥分租数

// 循环位移
#define ROTL(x, y) (((x) << ((y) & (w - 1))) | ((x) >> (w - ((y) & (w - 1)))))
#define ROTR(x, y) (((x) >> ((y) & (w - 1))) | ((x) << (w - ((y) & (w - 1)))))

// 密钥扩展
void generateSubkeys(uint8_t* K, uint32_t* S)
{
    uint32_t L[c] = { 0 };

  // 将密钥转换为小端序的32位字
    for (int i = 0; i < b; i++) {
    L[i / 4] |= ((uint32_t)K[i]) << (8 * (i % 4));
    }

    // 子密钥生成
    S[0] = 0xB7E15163;//常量Q，0x9E3779B9就是常量p
    for (int i = 1; i < t; i++) {
        S[i] = S[i - 1] + 0x9E3779B9;
    }

    // 主子密钥混合
    uint32_t A = 0, B = 0;
    int i = 0, j = 0;
    for (int k = 0; k < 3 * t; k++) {
        A = S[i] = ROTL(S[i] + A + B, 3);
        B = L[j] = ROTL(L[j] + A + B, A + B);
        i = (i + 1) % t;
        j = (j + 1) % c;
    }
}

// 加密函数
void Encrypt(uint32_t* in, uint32_t* out, uint32_t* S)
{
    uint32_t A = in[0] + S[0];
    uint32_t B = in[1] + S[1];
    for (int i = 1; i <= r; i++) {
        A = ROTL(A ^ B, B) + S[2 * i];
        B = ROTL(B ^ A, A) + S[2 * i + 1];
    }
    out[0] = A;
    out[1] = B;
}

// 解密函数
void Decrypt(uint32_t* in, uint32_t* out, uint32_t* S)
{
    uint32_t A = in[0];
    uint32_t B = in[1];
    for (int i = r; i >= 1; i--) {
        B = ROTR(B - S[2 * i + 1], A) ^ A;
        A = ROTR(A - S[2 * i], B) ^ B;
    }
    out[0] = A - S[0];
    out[1] = B - S[1];
}

int main()
{
    // define arrays
    uint8_t K[b] = { 'c','l','e','W','t','e','m','o','H','3','L','o','!','F','T','C' };
    uint32_t S[t];
    uint32_t plaintext[2] = { 0x12345678, 0x9ABCDEF0 };
    uint8_t cipher_bytes[32] = {
     0x1B, 0xBB, 0xA1, 0xF2, 0xE9, 0x7C, 0x87, 0x21,
     0x8A, 0x37, 0xFD, 0x0A, 0x94, 0x1A, 0x81, 0xBC,
     0x40, 0x1E, 0xE3, 0xAA, 0x73, 0x2E, 0xD8, 0x3F,
     0x84, 0xB8, 0x71, 0x42, 0xCC, 0x35, 0x8B, 0x39
    };
    uint32_t decrypted[2];
    uint32_t ciphertext[8];
    // 将字节序列转换为小端序的32位字
    for (int i = 0; i < 8; i++) {
        ciphertext[i] =
            (cipher_bytes[4 * i + 3] << 24) |
            (cipher_bytes[4 * i + 2] << 16) |
            (cipher_bytes[4 * i + 1] << 8) |
            cipher_bytes[4 * i];
    }
    // 密钥扩展
    generateSubkeys(K, S);
    //加密
    for(int i =0;i<4;i++)
    Encrypt(&ciphertext[i*2], &decrypted[i*2], S);
    for(int j = 0;j<8;j+=2)
    printf("Decrypted:   %08X %08X\n", decrypted[j], decrypted[j+1]);
    printf("\n\n");
    printf("%s", decrypted);
    //解密
    for(int i =0;i<4;i++)
    Decrypt(&ciphertext[i*2], &decrypted[i*2], S);
    for(int j = 0;j<8;j+=2)
    printf("Decrypted:   %08X %08X\n", decrypted[j], decrypted[j+1]);
    printf("\n\n");
    printf("%s", decrypted);
    return 0;
}