RC4加密算法

  在密码学领域，RC4（ 又名ARC4 或者ARCFOUR ）是应用最广泛的流加密算法，应用在安全套接字层（SSL）（用来保护网络上传输的数据）和WEP（无线网络数据保护）上。虽然它的最大亮点是算法的简单性和运行速度，但是因为它存在的弱点，在新的系统中使用时是有所争论的。the beginning of the output keystream  is not discarded（使用起始的输出keystream），使用非随机的或者相关性的keys，一个keysteream连续两次使用，这些使用方法都能使RC4加密方法显得特别脆弱，比如在WEP中RC4的一些使用方式就导致了非常不安全的情况。

1. 历史
2. 描述
   1. The key-scheduling algorithm (KSA)
   2. 伪随机生成算法（PRGA）
3. 实现

历史

---

RC4是由RSA Security的Ron Rivest 在1987年开发出来的，虽然它的官方名是“Rivest Cipher 4”，但是首字母缩写RC也可以理解为Ron's Code。RC4开始时是商业密码，没有公开发表出来，但是在94年9月份的时候，它被人匿名公开在了Cypherpunks 邮件列表上，很快它就被发到了sci.crypt 新闻组上，随后从这儿传播到了互联网的许多站点。随之贴出的代码后来被证明是很有水平的，因为它的输出跟取得了RC4版权的私有软件的输出是完全的。由于算法已经公开，rc4也就不再是商业秘密了，只是它的名字“RC4”仍然是一个注册商标。RC4经常被称作是“ARCFOUR”或者"ARC4"（A lleged  RC4，所谓的RC4,因为RSA从来没有官方公布这个算法），这样来避免商标使用的问题。它已经成为一些广泛使用的协议和标准的一部分，比如，包括WEP和WPA的无线网卡和TLS。

让它如此广泛分布和使用的主要因素是它不可思议的简单和速度，不管是软件还是硬件，实现起来都十分容易。

描述

---

RC4产生一个伪随机比特流（a keystream），加密的时候，把它跟明文进行比特级别的异或处理，解密时进行一样的步骤（因为异或操作是对称的）。（这个类似于Vernam cipher ，只不过后者不使用伪随机比特流而直接使用随机比特流）。为了产生keystream，本密码算法使用时需要两个数据的私有空间来保存内部状态：

  1. 总共256个字节的序列（下面用“S"代替）

   2.   两个8比特的索引指针（下面用“i”和“j”代替）

比特流序列的初始化是根据key的长度（key的长度通常在40到256比特之间），使用key-scheduling 算法来进行的（KSA)，一旦完成了初始化,比特流就可以根据伪随机生成算法(PRGA)来产生。

The key-scheduling algorithm (KSA)

key-scheduling 算法用来初始化数组“S”中的字节序列，“keylength”定义了key的字节长度，可能的范围是[1, 256]， 典型的值是5到16之间，相应的key 长度就是40-128比特。首先，数组“S”被初始化成identity permutation（身份鉴别的序列），随后在PRGA的算法中进行256为周期的循环列举出来，每次处理的方式都是一样的，是联合key的字节进行的 。

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

伪随机生成算法（PRGA）

对于尽可能多的每个列举过程，PRGA算法修改内部的状态并输出keystream的一个字节。在每次循环中，PRGA把i加一，并把i所指向的S值加到j上去，然后交换S[i]和S[j]的值，最后输出S[i]和S[j]的和(取256的模)对应的S值。至多经过256次，S每个位置上的值都被交换一次。

i := 0 j := 0 

while   GeneratingOutput:

    i := (i + 1) mod 256

    j := (j + S[i]) mod 256

    swap(&S[i],&S[j])

    output S[(S[i] + S[j]) mod 256] 

endwhile

实现

---

  许多流加密算法都是基于Linear feedback shift register（LFSRs, 寄存器线性反馈移位）, 虽然在硬件上有效率但是在软件实现上却可能比较慢。RC4的设计避免了LFSRs的使用，对于软件实现是相当理想的，它只需字节操作，使用了256字节的状态数组（从S[0]到S[255]）, k字节的key内存（从key[0]到key[k-1]），整数i,j和k。 进行256的取模操作可以用255的字节AND来进行（在有些平台上，只需简单地进行字节相加，忽略掉溢出即可）。下面是一个简单的C实现：

unsigned char S[256];

unsigned int i, j;

 

void swap(unsigned char *s, unsigned int i, unsigned int j) {

    unsigned char temp = s[i];

    s[i] = s[j];

    s[j] = temp;

}

 

/* KSA */

void rc4_init(unsigned char *key, unsigned int key_length) {

    for (i = 0; i < 256; i++)

        S[i] = i;

 

    for (i = j = 0; i < 256; i++) {

        j = (j + key[i % key_length] + S[i]) & 255;

        swap(S, i, j);

    }

 

    i = j = 0;

}

 

/* PRGA */

unsigned char rc4_output() {

    i = (i + 1) & 255;

    j = (j + S[i]) & 255;

 

    swap(S, i, j);

 

    return S[(S[i] + S[j]) & 255];

}

 

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

 

#define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))

 

int main() {

    unsigned char *test_vectors[][2] = 

    {

        {"Key", "Plaintext"},

        {"Wiki", "pedia"},

        {"Secret", "Attack at dawn"}

    };

 

    int x;

    for (x = 0; x < ARRAY_SIZE(test_vectors); x++) {

        int y;

        rc4_init(test_vectors[x][0], strlen((char*)test_vectors[x][0]));

 

        for (y = 0; y < strlen((char*)test_vectors[x][1]); y++)

            printf("%02X", test_vectors[x][1][y] ^ rc4_output());

        printf("\n");

    }

    return 0;

}