一文读懂RC4加密算法

这次再来重新回顾下RC4加密算法，虽然说之前的文章写过有关RC4的算法，感觉那一篇文章写的比较简陋，所以这一篇文章是一个重制篇，这次呢，再来重新梳理一下RC4算法的结构，在这次介绍算法的过程中呢，我尽量的给出变换的图示，来辅助读者们理解。

算法概览

首先来说，这是一个流密码体系，核心在于生成随机的字节序列，因此对于算法的重点就在于随机序列的生成之上，流密码的好处是加密和解密是完全相同的一套流程，不同余分组密码，加密和解密的流程要发生一些变化，用于实现加密和解密的一致性。对于完整的RC4流程的图如下。

初始化S-Box

具体过程如下图所示，其实就是从0~255填充满大小为256的数组。

KSA过程

上面我们有了最初的S-Box，那么对于KSA的核心作用呢，实际上是通过密钥来置乱初始的向量，这个初始向量是一个固定值，从0~255来填充满S-Box。

初始化密钥

这一步呢其实在编码过程当中是可有可无的，如果我们不生成T-Box，可以在编码过程当中模KeyLen来实现，如果使用T-Box，那么我们在编码过程当中需要模256了，这里展示使用T-Box的情况，和文章最开头的流程图保持一致。对于T-Box来说，其实就是密钥循环复制m次，使得循环之后充满256长度的数组，从这里可以直观的看出，对于RC4来说，它的密钥长度大小最大是256。

置乱过程(KSA)

对于这一步呢，其实是根据S-Box和T-Box来获取一个索引j，然后交换i和j的对应元素的位置。

PRNG过程

这个过程是整个RC4算法的核心，通过这个过程生成我们需要的PRNG序列，具体过程如下图所示。

这里简单的来描述下这个过程，如果读者看图能看得懂，我这段啰嗦的描述就可以先不看了蛤，具体过程呢，首先根据i和S-Box生成j的位置索引，然后交换S-Box当中i和j元素的位置，之后呢，通过S[i],S[j]最终获取到输出序列的索引，最终在S-Box当中获取到最终的输出序列。

编码实现

这里编码实现呢，我在中间打印出来了中间的变量，读者们可以直接运行代码来更改输入和输出来看具体的算法的运行过程，还是老样子，这个代码仅供「学习」使用，使用到生产环境建议采用「标准库」或者「使用人数较多」的代码，由于个人水平有限，这次还是只给出Rust的实现吧。

Rust

use std::iter::repeat;

pub struct RC4 {
    i: u8,
    j: u8,
    s_box: [u8; 256],
    t_box: [u8; 256],
}

impl RC4 {
    pub fn init(key: &[u8]) -> RC4 {
        // 初始化S-Box
        let mut rc4 = RC4 { i: 0, j: 0, s_box: [0; 256], t_box: [0; 256] };
        for (i, x) in rc4.s_box.iter_mut().enumerate() {
            *x = i as u8;
        }
        println!("S-Box: {:?}", rc4.s_box);
        let key_len = key.len();
        for i in 0..256 {
            rc4.t_box[i] = key[i % key_len];
        }
        println!("T-Box: {:?}", rc4.t_box);
        // ksa 过程
        let mut j = 0u8;
        for i in 0..256 {
            // j = (j + S[i] + T[i]) mod 256
            j = j.wrapping_add(rc4.s_box[i]).wrapping_add(rc4.t_box[i]);
            // swap S[i] S[j]
            rc4.s_box.swap(i, j as usize);
        }
        println!("KSA result: {:?}", rc4.s_box);
        return rc4;
    }

    fn prng(&mut self) -> u8 {
        println!("===== prng start =====");
        self.i = self.i.wrapping_add(1);
        println!("i = {}", self.i);
        self.j = self.j.wrapping_add(self.s_box[self.i as usize]);
        println!("j = (j + S[i]) mod 256 = {}", self.j);
        self.s_box.swap(self.i as usize, self.j as usize);
        let out = self.s_box[(self.s_box[self.i as usize].wrapping_add(self.s_box[self.j as usize])) as usize];
        println!("out =  S[(S[i] + S[j]) mod 256] = {}", out);
        println!("===== prng end =====");
        out
    }

    fn crypt(&mut self, input: &[u8], output: &mut [u8]) {
        for (i, j) in input.iter().zip(output.iter_mut()) {
            let steam = self.prng();
            *j = *i ^ steam;
            println!("加密结果: 明文^PRNG序列 = {} ^ {} = {}", *i, steam, *j);
        }
    }
}

fn main() {
    let mut rc4 = RC4::init("key".as_bytes());
    let plaintext = "plaintext";
    let mut result: Vec<u8> = repeat(0).take(plaintext.len()).collect();
    rc4.crypt(plaintext.as_bytes(), &mut result);
    println!("{:?}", result);
}

总结

本文呢，我们简单描述了一下RC4算法的过程，本文实际上属于一个重制篇，这次通过更多的图来描述了RC4算法的过程，希望读者可以喜欢，最后一如既往的皮一下吧，学累了读一首诗来放松一下。

❝

富家不用买良田，书中自有千钟粟。安居不用架高堂，书中自有黄金屋。—劝学诗【宋】赵恒

❞

参考资料

• https://en.wikipedia.org/wiki/RC4^[1]

Reference