RC4原理以及python实现

简介

RC4（来自Rivest Cipher 4的缩写）是一种流加密算法，密钥长度可变。它加解密使用相同的密钥，一个字节一个字节地加密。因此也属于对称加密算法。突出优点是在软件里面很容易实现。

加密流程

包含两个处理过程：一是秘钥调度算法(KSA)，用于之乱S盒的初始排列，另外一个是伪随机数生成算法(PRGA)，用来输出随机序列并修改S的当前顺序。

1. 根据秘钥生成S盒
2. 利用PRGA生成秘钥流
3. 秘钥与明文异或产生密文

单个点拿出来分析

根据秘钥生成S盒

初始化S盒

直接构造一个S[256]，遍历0_{255，然后创建临时T[256]，用于存储种子秘钥，长度不够循环填充直到T被填满，根据T[i]将S[i]与S中的另外一个字节对换，对S的操作仅仅是交换，唯一改变的是位置，但里面的元素是没变的还是0}255

    s_box = list(range(256)) #我这里没管秘钥小于256的情况，小于256不断重复填充即可
    j = 0
    for i in range(256):
        j = (j + s_box[i] + ord(key[i % len(key)])) % 256
        s_box[i], s_box[j] = s_box[j], s_box[i]
    #print(type(s_box)) #for_test
    return s_box

下图很好的解释了S盒被随机化的过程

利用PRGA生成秘钥流

从S盒选取一个元素输出，并置换S盒便于下一轮取出，选取过程取决于索引i和j，这也体现了在加密过程中S盒会变化。下面的是流程：

    res = []
    i = j =0
    for s in plain:
        i = (i + 1) %256
        j = (j + box[i]) %256
        box[i], box[j] = box[j], box[i]
        t = (box[i] + box[j])% 256
        k = box[t]
        res.append(chr(ord(s)^k))  #直接与每一个字节明文相异或

秘钥与明文异或产生密文

至于这一点就不用多说了，由于异或运算的对合性，RC4加密解密使用同一套算法。

python实现：

# -*- coding: utf-8 -*-
# Author:0verWatch

import base64

def get_message():
    print(\"输入你的信息：\")
    s = input()
    return s

def get_key():
    print(\"输入你的秘钥：\")
    key = input()
    if key == \'\':
        key = \'None_public_key\'
    return key

def init_box(key):
    \"\"\"
    S盒 
    \"\"\"
    s_box = list(range(256)) #我这里没管秘钥小于256的情况，小于256应该不断重复填充即可
    j = 0
    for i in range(256):
        j = (j + s_box[i] + ord(key[i % len(key)])) % 256
        s_box[i], s_box[j] = s_box[j], s_box[i]
    #print(type(s_box)) #for_test
    return s_box

def ex_encrypt(plain,box,mode):
    \"\"\"
    利用PRGA生成秘钥流并与密文字节异或，加解密同一个算法
    \"\"\"

    if mode == \'2\':
        while True:
            c_mode = input(\"输入你的解密模式:Base64 or ordinary\\n\")
            if c_mode == \'Base64\':
                plain = base64.b64decode(plain)
                plain = bytes.decode(plain)
                break
            elif c_mode == \'ordinary\':
                plain = plain
                break
            else:
                print(\"Something Wrong,请重新新输入\")
                continue

    res = []
    i = j =0
    for s in plain:
        i = (i + 1) %256
        j = (j + box[i]) %256
        box[i], box[j] = box[j], box[i]
        t = (box[i] + box[j])% 256
        k = box[t]
        res.append(chr(ord(s)^k))

    cipher = \"\".join(res)
    #print(cipher)
    if  mode == \'1\':
        # 化成可视字符需要编码
        print(\"加密后的输出(没经过任何编码):\")
        print(cipher)
        # base64的目的也是为了变成可见字符
        print(\"base64后的编码:\")
        print(str(base64.b64encode(cipher.encode(\'utf-8\')),\'utf-8\'))
    if mode == \'2\':
        print(\"解密后的密文：\")
        print(cipher)


def get_mode():
    print(\"请选择加密或者解密\")
    print(\"1. Encrypt\")
    print(\"2. Decode\")
    mode = input()
    if mode == \'1\':
        message = get_message()
        key = get_key()
        box = init_box(key)
        ex_encrypt(message,box,mode)
    elif mode == \'2\':
        message = get_message()
        key = get_key()
        box = init_box(key)
        ex_encrypt(message, box, mode)
    else:
        print(\"输入有误！\")





if __name__ == \'__main__\':
    while True:
        get_mode()

安全性

1. 由于RC4算法加密是采用的xor，所以，一旦子密钥序列出现了重复，密文就有可能被破解。所以必须对加密密钥进行测试，判断其是否为弱密钥。
2. 当然，现在RC4已经不安全了，可以参考这篇文章，破解RC4现在是具有很高效率的。