【密码学】流密码之RC4算法

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

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

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

算法过程

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

  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 以便下一次选取,选取的过程取决于索引 ij ,产生的密文为异或的结果,所以我们在这步就顺便产生密文。代码如下:

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()

参看

【Wikipedia】RC4

禁止商业用途,非商业分享转载请注明来源。
本文链接:http://comydream.github.io/2018/12/28/cryptography-rc4/