RC5加密

发表于 2019-03-28 更新于 2021-11-17 分类于密码学本文字数： 1.5k 阅读时长 ≈ 1 分钟

背景

RC5全称Rivest Cipher5，,是1994年Ron Rivest设计的（原始论文）。AES的候选算法之一RC6就是基于RC5开发的。这种算法具有块可变，秘钥长度可变，加密轮数可变的特点，非常灵活。并且，操作简单，仅需加法、移位、异或即可完成，而且内存占用极少

基本原理

首先加密前要确定块长，轮数和秘钥长度，确定后不可改变。其中块长可选16,32或64位。轮数介于1-255之间，秘钥长度介于0-255字节。为了便于记忆，我们定义RC5-w/r/b表示一个实例，w/r/b分别表示一个字的长度（算法以两个字位一单位），轮数和秘钥长。推荐的最低安全标准为RC5-32/16/16

加密时都先将明文块分两部分，用这两部分开始若干轮计算，每轮都涉及相加、移位和异或，最后输出密文

详细流程

初始化操作

首相将明文分为A,B两部分。然后A与子秘钥S[0]相加，B与子秘钥S[1]相加，结果分别用2^w求模，得到C,D

每一轮细节

C和D异或得E
E循环左移D位
E与子秘钥S[2i]相加得F。同样也要模2^w，i表示第几轮
D与F异或得G
G循环左移F位
G与子秘钥S[2i+1]相加得H。同样也要模2^w，i表示第几轮
若还有轮数则C=F，D=H

基本可以写成下列形式

A = A + S[0]
B = B + S[1]
for i = 1 to r:
    A = ((A XOR B) <<< B) + S[2i]
    B = ((B XOR A) <<< A) + S[2i+1]

秘钥计算

子秘钥生成

首先取两个常亮P、Q。P与Q在不同的w也就是字长下有不同值：

W	P	Q
16	0xB7E1	0x9E37
32	0xB7E15163	0x9E3779B9
64	0xB7E151628AED2A6B	0x9E3779B97F4A7C15

P、Q计算公式分别如下：

第一个公式中的e表示自然常数，即2.71828… 第二个公式中的φ表示黄金比例，即1.618….。odd表示取最接近给定输入的奇数。P、Q都是魔法数字，没有任何来源根据.

得到两个常数后，令S[0] = P，从i=1开始循环，i每个循环递增1，每次循环计算A = S[i-1]+Q，B = A mod 2^w，S[i] = B。一直循环2(r+1)-1次。表示如下

s[0] = P
for i = 1 to 2(r+1)-1:
    s[i] = (s[i-1]+Q) mod 2^w

子秘钥混合

该阶段将子秘钥S与秘钥L进行混合

i = j = 0
A = B = 0
do 3 * max(2(r+1), (b*8)/w) times:
    A = S[i] = (S[i] + A + B) <<< 3
    B = L[j] = (L[j] + A + B) <<< (A + B)
    i = (i + 1) mod 2(r+1)
    j = (j + 1) mod (b*8)/w

解密

解密就是将加密过程颠倒

for i = r to 1:
    A = ((B - S[2i+1])>>>A) XOR A
    B = ((A - S[2i])>>>B) XOR B

B = B - S[1]
A = A - S[0]

安全性

12轮RC5(64位块)容易受到使用了2^44的选定的明文的差分攻击。18–20轮加密则被认为可以提供足够的保护。更大的安全性可以通过增加轮数获得，其代价是减少密码的吞吐量。

实现

论文附录中作者给出了详细实现，这里不再列出。

题图来自unsplash：https://unsplash.com/photos/WhRsHmFtFXQ