【密码学】序列密码之 RC4 算法

Author Avatar
source. 12月 28, 2018
  • 在其它设备中阅读本文章

RC4 是序列密码的一种，突出优点是在软件中容易实现。它可能是世界上使用最广泛的序列密码。

看到这个 R ，你会想到什么，如果你想到 RSA 中的 Revest ，那么你跟我想的一样。没错，这种密码算法又是由 MIT 的 Revest 设计开发的， RC4 是 Rivest Cipher 4 的缩写。

序列密码也叫流密码（stream cipher）。因为计算起来简单，它的效率大概是分组密码的3~5倍。

加密过程是明文和密钥逐比特异或，故序列密码的关键是如何生成足够安全的密钥。

算法过程

该算法包括两个处理过程：

  1. 密钥调度算法（ KSA, Key-Scheduling Algorithm ）：置乱 S 盒的初始排列
  2. 伪随机生成算法（ PRGA, Pseudo Random-Generation Algorithm ）：输出随机序列并修改 S 的当前排列顺序

S 盒初始排列 及 临时数组向量 T[i]

T[i] 用于解决输入的 Key 的长度小于 256 字节的情况，这种情况下联想古典密码中的 Vigenere 密码，不断重复直至填满。代码实现：

## 将0到255的互不重复的元素装入S盒。
lk = len(key)
S = list(range(256))
T = [key[i%lk] for i in range(256)]

KSA

根据密钥打乱 S 盒。代码如下：

## 根据密钥打乱S盒
j = 0
for i in range(256):
    j = (j+S[i]+ord(T[i]))%256
    S[i],S[j] = S[j],S[i]

PRGA

从 S 中随机抽取一个元素输出，并置换 S 以便下一次选取，选取的过程取决于索引 i 和 j ，产生的密文为异或的结果，所以我们在这步就顺便产生密文。代码如下：

i = j = 0
ans = ""
for x in text:
    i = (i+1)%256
    j = (j+S[i])%256
    S[i],S[j] = S[j],S[i]
    t = (S[i]+S[j])%256
    k = S[t]
    ans += chr(ord(x)^k)

解密过程与加密过程相同。密文对应的 8 bit 可能无法对应 ASCII 中的字符或可打印字符，那么一般做法是对加密的结果 base64 编码。那么，在解密过程我们就可以对它先进行 base64 解码再运行算法。

正确性

验证：

完整代码

#-*- coding:utf-8 -*-
#Stream Cipher: RC4
import base64

# RC4算法
def RC4(text,key):
    ## 将0到255的互不重复的元素装入S盒。
    lk = len(key)
    S = list(range(256))
    T = [key[i%lk] for i in range(256)]
    ## 根据密钥打乱S盒
    j = 0
    for i in range(256):
        j = (j+S[i]+ord(T[i]))%256
        S[i],S[j] = S[j],S[i]
    ## 生成伪随机数，构造密文
    i = j = 0
    ans = ""
    for x in text:
        i = (i+1)%256
        j = (j+S[i])%256
        S[i],S[j] = S[j],S[i]
        t = (S[i]+S[j])%256
        k = S[t]
        ans += chr(ord(x)^k)
    # print(" ".join(str(ord(x)) for x in ans))
    return ans

# RC4加密: 明文转成base64编码的密文
def RC4Encrypt(message,key):
    return base64.b64encode(RC4(message,key))

# RC4解密: base64编码的密文转成明文
def RC4Decrypt(cipher,key):
    return RC4(base64.b64decode(cipher),key)

# 对字符串的加密解密
def main1():
    # s = raw_input("Please input the plaintext: ")
    # k = raw_input("Please input the key: ")
    s = "QAQ"
    k = "MengMengDa"
    print 8*"*"+" Encryption "+8*"*"
    Encryption = RC4Encrypt(s,k)
    print "The Ciphertext is "+Encryption

    print 8*"*"+" Decryption "+8*"*"
    print "The Plaintext is "+RC4Decrypt(Encryption,k)

# 对文件的加密解密
def main2():
    ## 加密
    fin = open("d:/Plaintext.txt")
    fout = open("d:/Ciphertext2.txt","w")
    s = fin.read()
    k = "MengMengDa"
    fout.write(RC4Encrypt(s,k))
    fin.close()
    fout.close()
    ## 解密
    fin = open("d:/Ciphertext2.txt")
    fout = open("d:/Plaintext_output.txt","w")
    s = fin.read()
    k = "MengMengDa"
    fout.write(RC4Decrypt(s,k))
    fin.close()
    fout.close()

if __name__ == '__main__':
    main1()

安全性分析

无效初始置换

由初始置换算法：

j = 0
for i in range(256):
    j = (j + S[i] + T[i]) % 256
    s[i], s[j] = s[j], s[i]

当$T[i]=[0,0,255,254,\dots,3,2]$时，S盒在初始置换前后不变。

参看

【Wikipedia】RC4

本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 ComyDream 。
本文链接：http://comydream.github.io/2018/12/28/cryptography-rc4/

Powered by Hexo
Theme - Material