术→技巧, 法→原理, 研发, 算法实现

加密解密算法之RC4

钱魏Way · · 2,301 次浏览

RC4加密算法是一种对称加密算法。所谓对称加密算法,说得直白一点,就是加密与解密的过程一模一样。假设定义RC4的运算过程是rc4(key,data),那么,密文=rc4(key,明文),明文=rc4(key,密文)。所以,对一段数据迭代地做奇数次RC4运算,就得到密文,对这段数据迭代地做偶数次RC4运算,结果依旧是原来的那段数据。

这种对称性就是基于密钥流的加密算法的一个特征。RC4加密算法也是一种基于密钥流的加密算法。何为密钥流呢?假设要加密的数据长N个字节,那么我通过某种算法,也产生一串N字节的数据,然后把这两串N字节数据按位异或(XOR),就得到了密文。把密文与这串密钥流再XOR,就能重新得到明文。而这一串由某种算法产生的N字节,或者说8N位,就叫做密钥流,而该算法就叫做密钥流生成算法。所有基于密钥流的加密算法的区别就在于密钥流的生成方式的不同。只要生成了与数据等长的密钥流,那么加密、解密方式都是把数据与密钥流做异或运算。

RC4本质上就是一种密钥流生成算法。它的特点是算法简单、运算效率高,而且非线性度良好。算法简单的特点使得可以使用硬件来实现RC4,如同在很多旧的无线网卡中就是使用硬件来实现WEP加密的。运算效率高使得用软件实现RC4也很便捷、不会占用过多CPU。而非线性度良好,则是RC4广泛使用的重要原因。所谓非线性度好,就是指通过密码产生密钥流容易,而通过密钥流逆推出密码则很难。

RC4 算法的特点是算法简单,运行速度快,而且密钥长度是可变的,密钥长度范围为 1-256 字节。

RC4的算法原理

RC4算法主要包括两个部分:1)使用 key-scheduling algorithm (KSA) 算法根据用户输入的秘钥 key 生成 S 盒;2)使用 Pseudo-random generation algorithm (PRGA) 算法生成秘钥流用于加密数据。

利用Key生成S盒——The key-scheduling algorithm (KSA)

KSA算法初始化长度为 256 的 S 盒。第一个 for 循环将 0 到 255 的互不重复的元素装入 S 盒;第二个 for 循环根据密钥打乱 S 盒。

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 values of S[i] and S[j]
endfor

利用S盒生成密钥流——The pseudo-random generation algorithm(PRGA)

Pseudo-random generation algorithm (PRGA) 算法根据 S 盒生成与明文长度相同的秘钥流,使用秘钥流加密明文。秘钥流的生成如下图所示:

循环体中每收到一个字节,a 和 b 定位S盒中的一个元素,并与输入字节异或,得到密文 k;同时,c 还改变了 S 盒。由于异或运算的特性,使得加密与解密过程一致。如果输入的是明文,输出的就是密文;如果输入的是密文,输出的就是明文。

i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256  // a
    j := (j + S[i]) mod 256 // b
    swap values of S[i] and S[j]  // c
    K := inputByte ^ S[(S[i] + S[j]) mod 256] // d
    output K
endwhile

RC4算法的Python实现

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# author: @manojpandey

# Python 3 implementation for RC4 algorithm
# Brief: https://en.wikipedia.org/wiki/RC4

# Will use codecs, as 'str' object in Python 3 doesn't have any attribute 'decode'
import codecs

MOD = 256


def KSA(key):
    ''' Key Scheduling Algorithm (from wikipedia):
        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 values of S[i] and S[j]
        endfor
    '''
    key_length = len(key)
    # create the array "S"
    S = list(range(MOD))  # [0,1,2, ... , 255]
    j = 0
    for i in range(MOD):
        j = (j + S[i] + key[i % key_length]) % MOD
        S[i], S[j] = S[j], S[i]  # swap values

    return S


def PRGA(S):
    ''' Psudo Random Generation Algorithm (from wikipedia):
        i := 0
        j := 0
        while GeneratingOutput:
            i := (i + 1) mod 256
            j := (j + S[i]) mod 256
            swap values of S[i] and S[j]
            K := S[(S[i] + S[j]) mod 256]
            output K
        endwhile
    '''
    i = 0
    j = 0
    while True:
        i = (i + 1) % MOD
        j = (j + S[i]) % MOD

        S[i], S[j] = S[j], S[i]  # swap values
        K = S[(S[i] + S[j]) % MOD]
        yield K


def get_keystream(key):
    ''' Takes the encryption key to get the keystream using PRGA
        return object is a generator
    '''
    S = KSA(key)
    return PRGA(S)


def encrypt_logic(key, text):
    ''' :key -> encryption key used for encrypting, as hex string
        :text -> array of unicode values/ byte string to encrpyt/decrypt
    '''
    # For plaintext key, use this
    key = [ord(c) for c in key]
    # If key is in hex:
    # key = codecs.decode(key, 'hex_codec')
    # key = [c for c in key]
    keystream = get_keystream(key)

    res = []
    for c in text:
        val = ("%02X" % (c ^ next(keystream)))  # XOR and taking hex
        res.append(val)
    return ''.join(res)


def encrypt(key, plaintext):
    ''' :key -> encryption key used for encrypting, as hex string
        :plaintext -> plaintext string to encrpyt
    '''
    plaintext = [ord(c) for c in plaintext]
    return encrypt_logic(key, plaintext)


def decrypt(key, ciphertext):
    ''' :key -> encryption key used for encrypting, as hex string
        :ciphertext -> hex encoded ciphered text using RC4
    '''
    ciphertext = codecs.decode(ciphertext, 'hex_codec')
    res = encrypt_logic(key, ciphertext)
    return codecs.decode(res, 'hex_codec').decode('utf-8')


def main():

    key = 'not-so-random-key'  # plaintext
    plaintext = 'Good work! Your implementation is correct'  # plaintext
    # encrypt the plaintext, using key and RC4 algorithm
    ciphertext = encrypt(key, plaintext)
    print('plaintext:', plaintext)
    print('ciphertext:', ciphertext)
    # ..
    # Let's check the implementation
    # ..
    ciphertext = '2D7FEE79FFCE80B7DDB7BDA5A7F878CE298615'\
        '476F86F3B890FD4746BE2D8F741395F884B4A35CE979'
    # change ciphertext to string again
    decrypted = decrypt(key, ciphertext)
    print('decrypted:', decrypted)

    if plaintext == decrypted:
        print('\nCongrats ! You made it.')
    else:
        print('Shit! You pooped your pants ! .-.')

    # until next time folks !


def test():

    # Test case 1
    # key = '4B6579' # 'Key' in hex
    # key = 'Key'
    # plaintext = 'Plaintext'
    # ciphertext = 'BBF316E8D940AF0AD3'
    assert(encrypt('Key', 'Plaintext')) == 'BBF316E8D940AF0AD3'
    assert(decrypt('Key', 'BBF316E8D940AF0AD3')) == 'Plaintext'

    # Test case 2
    # key = 'Wiki' # '57696b69'in hex
    # plaintext = 'pedia'
    # ciphertext should be 1021BF0420
    assert(encrypt('Wiki', 'pedia')) == '1021BF0420'
    assert(decrypt('Wiki', '1021BF0420')) == 'pedia'

    # Test case 3
    # key = 'Secret' # '536563726574' in hex
    # plaintext = 'Attack at dawn'
    # ciphertext should be 45A01F645FC35B383552544B9BF5
    assert(encrypt('Secret',
                   'Attack at dawn')) == '45A01F645FC35B383552544B9BF5'
    assert(decrypt('Secret',
                   '45A01F645FC35B383552544B9BF5')) == 'Attack at dawn'

if __name__ == '__main__':
    main()

参考链接:https://github.com/manojpandey/rc4

使用pyCrypto进行RC4加密解密

RC4最初是一个商业秘密,但是在1994年9月被泄漏。因为名称“RC4”是商标,因此RC4通常被称为“ARCFOUR”或“ARC4”,以避免商标问题。

from Crypto.Cipher import ARC4

def encrypt(message, key):
    des = ARC4.new(key)
    cipher_text = des.encrypt(message)
    return cipher_text

def decrypt(cipher_text, key):
    des3 = ARC4.new(key)
    message = des3.decrypt(cipher_text)
    return message

if __name__ == "__main__":
    key = "0123456789abcdef"
    message = "www.biaodianfu.com"
    cipher_text = encrypt(message, key)
    print(cipher_text.hex().upper())
    message = decrypt(cipher_text, key)
print(message.decode("utf-8"))

参考链接:

One Reply to “加密解密算法之RC4”

  1. 非常好的宝藏文. 希望能继续深入浅出的谈谈所有密码学原理和应用!非常感谢!

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注