RC4ストリーム暗号 in Python

はじめに

RC4は1987年にRon Rivestによって作られました。1994年にアルゴリズムがリークされ、WEPやWPA（WI-FIで見たことありませんか？）で使われています。この暗号はとっても短いコードで書くことがでるので、誰でも簡単なRC4のおもちゃが作れると思います。ここでは、RC4をpythonで簡単に作ってみたいと思います。

RC4のしくみ

RC4は2つのパートKSA(Key-scheduling algorithm)とPRGA(Pseudo-random generation algorithm)から構成されています。KSAはランダムな鍵(40～256bit)で\(S = [0, 1, ..., N - 1]\)を初期化し、PRGAはそのSを使って疑似乱数を生成します。この生成された疑似乱数と平文のxorを取っていくことで暗号化をします。以下に疑似コードを書いておきます。

KSA(K)
Initialization:
        For i = 0 ... N - 1
                swap S[i] = i
        j = 0
Scrambling:
        For i = 0 ... N - 1
                j = j + S[i] + K[i mod l]
                Swap(S[i], S[j])

PRGA(S)
Initialization:
        i = 0
        j = 0
Generation loop:
        i = i + 1
        j = j + S[i]
        Swap(S[i], S[j])
        Output z = S[S[i] + S[j]]

上の疑似コードをPythonにしてRC4を作ります。

def KSA(key):
    l = len(key)
    S = list(range(256))
    j = 0
    for i in range(256):
        j = (j + S[i] + key[i % l]) % 256
        S[i], S[j] = S[j], S[i]
    return S

KSAはb'key'のようなbytesオブジェクトが入ることを想定しています。そしてリストSを返します。

def PRGA(S):
    i, j = 0, 0
    while True:
        i = (i + 1) % 256
        j = (j + S[i]) % 256
        S[i], S[j] = S[j], S[i]
        K = S[(S[i] + S[j]) % 256]
        yield K

PRGAはKSAの返り値Sを入れて疑似乱数を生成するジェエネレータです。

最後に'message'のような文字列を暗号化する関数を以下のように作ります。

def rc4(m, key):
    keystream = PRGA(KSA(key))
    return bytes(i ^ j for i, j in zip(m, keystream))

参考文献

S. Flisher, I. Mantin, and A. Shamir, Weaknesses in the key shcheduling algorithm of RC4, Proc. SAC2001, LNCS 2259, pp.q-24, Springer-verlag, 2001.