从RFC2040中理解RC5算法.md

一、RC5算法概述

作为同样是由Rivest推出的算法，RC5算法与RC4算法是完全不同的，一个明显的特征是RC5采用的是基于Feistel对称结构的分组加密算法

和许多加密方法不同，RC5支持可变的块大小(32、64或128比特)，密钥长度（0至2040位）和加密轮数（0～255）。最初建议选择的参数是64位的块大小，128位的密钥和12轮加密

RC5的一个关键特征是使用基于数据的置换。RC5的其中一个目标是促进对于这类作为原始密码的操作的研究和评估。RC5也包括一些的取模加法和逻辑异或(XOR)运算。加密结构是基于Feistel来完成的，虽然结构简单，但密钥的生成算法更复杂。密钥扩展使用了e和黄金比例代入一个单向函数，将所得值作为“袖子里是空的”数字（即无任何来源依据的魔法数字）。算法的诱人的简洁性和基于数据的置换的特性，让RC5吸引了众多密码研究人员将其作为研究对象。 RC5通常被记为RC5-w/r/b，w=字的大小（以bit为单位），r=加密轮数，b=密钥的字节数。这样，RC5-32/16/16表示为RC5的块长为64位（注：RC5使用两个字块）、16轮加密和16字节密钥。Ron Rivest推荐的最低安全版本为RC5-32/16/16

二、RC5算法框架

为了便于理解RC5算法，假设输入明文块的长度为64位，其他块长的操作原理是一样的

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

接着进行各轮计算，每轮完成以下操作：

1. 位异或运算
2. 循环左移
3. 对C和D增加下一个子密钥，先是加法运算，然后将结果用2^32求模

1 初始化操作

第一步的初始化计算可以看成是RC4融合了DES的做法，融合了RC4的密钥计算和DES的Feistel的一个对称结构运用

首先会将明文分为两个等长的A和B，接着是第一个子密钥S[0]与A相加，第二个子密钥S[1]与B相加

2 子密钥的计算

子密钥的计算可以分成生成和混合两步，预计要产生2r+2个子密钥，每个密钥长度为w位

• 生成

  这一步使用两个常量P和Q。生成的子密钥数组称为S，第一个子密钥为S[0]用P值初始化。每个后续子密钥（S[1]，S[2]，…）根据前面的子密钥和常量Q求出，用2^32求模，这个过程要进行2(r+1)-1次，其中r位轮数

  // Set magic constants
  rc5_p = 0xb7e15163;
  rc5_q = 0x9e3779b9;
  
  // Cleaning user key
  for(int i=0; i<RC5_B; i++)
  rc5_key[i]=0;
  
  for(rc5_s[0]=rc5_p,i=1; i<RC5_T; i++) 
      rc5_s[i] = rc5_s[i-1]+rc5_q;
  
  for(i=RC5_B-1, l[RC5_C-1]=0; i!=-1; i--)
      l[i/u] = (l[i/u]<<8)+key[i];

• 混合

  // 3*t > 3*c
  for(a=b=i=j=k=0; k<3*RC5_T; k++, i=(i+1)%RC5_T, j=(j+1)%RC5_C)   
   { 
     a = rc5_s[i] = RC5_ROTL(rc5_s[i]+(a+b),3);  
     b = l[j] = RC5_ROTL(l[j]+(a+b),(a+b)); 
   } 

混合之后得到了新的长度为(2 * r) + 2的密钥组，需要注意的是，代码中提到了P和Q两个变量，其实是根据以下的公式而得来的

Pw = Odd((e-2)*2^32)
Qw = Odd((Φ-2)*2^32)

e表示自然对数的底 Φ表示黄金分割比率 Odd(x)表示最接近x的奇整数

3 轮计算

RC5_TWORD i; 
RC5_TWORD a=pt[0]+rc5_s[0];
RC5_TWORD b=pt[1]+rc5_s[1];

for(i=1; i<=RC5_R; i++)
{ 
    a = RC5_ROTL(a^b, b)+rc5_s[2*i]; 
    b = RC5_ROTL(b^a, a)+rc5_s[2*i+1]; 
}

ct[0] = a; 
ct[1] = b; 

三、理解