RC4算法简介.pdf

§2.1 RC4 算法 1987 年, Ron Rivest 为 RSA 公司开发了一个可以快速软件实现的新的序列密码算法 −−RC4 算法, 并申请了专利. RC4 算法因其算法简洁, 安全性高, 易于软件实现, 被广泛地 应用于各种商业密码产品中, 它还是许多重要的加密协议和标准的一部分, 如WEP, WPA, SSL, TLS 等. 2.1.1 算法描述 RC4 算法主要基于n 比特数的置换, 密钥的扩展和系统状态的更新通过一系列数组置 换来实现. 通常n 8, 即考虑256 个字节间的置换. RC4 算法选用 40−256 比特可变长的密钥, 产生以字节为单位的密钥流序列, 得到的 密钥流序列再与明文序列或者密文序列异或得到密文序列或者明文序列. 其中间状态包括 如下两部分: (1) 256 个字节间的置换S, 其中各分量S[i]均为字节, 0≤i ≤ 255. (2) 两个8-bit 指针: i 和j , 初值为0. 系统总的状态变量约为1684 比特. 置换（数组）S 先经密钥设置算法初始化, 再通过密钥生成算法得到需要的密钥序列. 其密钥设置算法和密钥生成算法如下: • 密钥设置算法 记keylength 为密钥字节数, 通常5 ≤ keylength ≤32, 即密钥长度为40∼256 比特, key[j ]. 40 ≤j ≤ 128. 密钥设置算法中S-盒初始化分三步: Step1. 线性填充, 即S 为恒等置换. Step2. 密钥扩展, 即K [i] K [i mod keylength], keylength ≤i ≤ 255. Step3. 类似于下面的密钥生成算法, 密钥参与j 的递归, 系统迭代256 次, 更新S 盒. 其伪码表示为: for i from 0 to 255 S[i] i endfor j 0 for i from 0 to 255 j (j + S[i] + key[i mod keylength]) mod 256 swap(S[i],S[j ]) endfor 注2.1.1 在WEP 应用中, 会话密钥和IV 级联作为RC4 的种子密钥, 而在SSL 应用中, 会话密钥和IV 的hash 值作为RC4 的种子密钥. WEP 协议中会话密钥和IV 简单级联使用 的方式也是容易对其攻击的原因之一. • 密钥生成算法 初始化算法结束后, 系统按下面的密钥生成算法输出需要的密钥序列. Initialization: i 0 j 0 Generation loop: i (i + 1) mod 256 j (j + S[i]) mod 256 Swap(S[i], S[j ]) j ]) mod 256] Output K S[(S[i] + S[ 每次迭代, 系统内部状态更新一次, 并输出一个字节K, 经过256 次迭代后, S 盒中每个值 至少交换了一次. 参考文献 [1] A. Roos. A class of weak keys in the RC4 stream cipher. In: Two posts in sci.crypt. (1995), http://marcel.wanda.ch/Archive/WeakKeys. [2] S. R.