Python で RC4 暗号を実装する

この記事では、Python を使用して RC4 暗号を実装します。

Python のライブラリを使用すれば RC4 暗号なんて簡単に利用することができます。

しかし、RC4 暗号の中身を理解するという意味で、スクラッチで実装します。

RC4 概要

RC4 暗号の歴史などは、他の記事に譲ります。ここでは、RC4 の仕組みについてのみ着目します。RC4 はストリーム暗号の１種です。ストリーム暗号は、平文をビットもしくはバイト単位で暗号化・復号処理を行います。しかし、これらの処理は独立して行われるものではなく、例えばあるバイトの暗号化処理は、前のバイトの暗号化処理に依存します。

RC4 は秘密鍵（あるいは初期化ベクトル $IV$ など）から疑似乱数系列（キーストリーム）を生成し、それを暗号化・復号処理に使用します。RC4 の擬似乱数生成アルゴリズムは2つの段階に区別できます。

1つは、秘密鍵や初期化ベクトルを用いて擬似乱数生成器の内部状態を初期化します。この最初の処理を KSA (Key Scheduling Algorithm) と呼びます。もう1つは、内部状態を更新しながらキーストリームを生成します。これを PRGA (Pseudo-Random Generation Algorithm) と呼びます。

RC4 は 8~2048bit から秘密鍵の鍵長を選択することができます (128bit 以上が推奨されており、この記事では 128bit の鍵を用います)。また、RC4 の内部状態は $2^n$ 個の要素を持つ配列 $S$ と、2つのポインタで構成されています（$n$ は可変の値ですが、一般的には $n=8$ が使用されます）。

KSA (Key Scheduling Algorithm)

KSA のアルゴリズムを疑似コードで表すと以下のようになります。

// N = 256 (2^8: n=8 を採用)
// K = 秘密鍵
// l = K.length
procedure KSA
    // Initialize
    for i ← 0...N − 1 do
        S[i] ← i
    end for
    // Swap
    for i ← 0...N − 1 do
        j ← (j + S[i] + K[i mod l]) mod N
	Swap(S[i], S[j])
    end for
end procedure

最初の for 文で、内部状態を初期化しています。その後、内部状態をスワップさせることで攪拌させます。注意点としては、ポインタがリスト（配列）の外を指さないように剰余（mod）を使用することです。

これを Python で書くと以下のようになりました。

// 鍵長を 7bytes = 128bit とする
SECRETKEY_BYTE_LENGTH = 7

def ksa(K: bytes, n = 8) -> list[int]:
    N: int = 2 ** n
    S: list[int] = [0] * N
    for i in range(N):
        S[i] = i

    def swap(i: int, j: int) -> None:
        buffer: int = S[i]
        S[i] = S[j]
        S[j] = buffer

    j = 0
    for i in range(N):
        j = (j + S[i] + K[i % SECRETKEY_BYTE_LENGTH]) % N
        swap(i, j)
    
    return S

関数 ksa は、128bit の秘密鍵を入力とします。$n$ はデフォルトで $8$ にしています。返り値は初期化した内部状態 $S$ です。$S$ は int のリスト（配列）で表現しています。つまり、内部状態の各要素は 8bit で表せる整数値となっています。

PRGA (Pseudo-Random Generation Algorithm)

PRGA のアルゴリズムを疑似コードで表すと以下のようになります。

// N = 256 (2^8: n=8 を採用)
procedure PRGA
    i ← 0
    j ← 0
    loop
        i ← (i + 1) mod N
	j ← (j + S[i]) mod N
	Swap(S[i], S[j])
	k ← S[(S[i] + S[j]) mod N]
	Output(k)
    end loop
end procedure

KSA から得られた内部状態をもとに2つのポインタ $i$, $j$ の値を決定し、内部状態を攪拌（スワップ）します。攪拌後の内部状態から 1byte のキー (k) を求めます。この処理を、暗号化・復号するバイト数分だけループして繰り返し計算されます。最終的に一連のキー（キーストリーム）が計算されます。

これを Python で書くと以下のようになりました。

def prga(key: bytes, loop_length, n = 8) -> list[int]:
    i = 0
    j = 0
    N: int = 2 ** n
    S: list[int] = ksa(key)

    def swap(i: int, j: int) -> None:
        buffer: int = S[i]
        S[i] = S[j]
        S[j] = buffer

    output: list[int] = [0] * loop_length
    for l in range(loop_length):
        i = (i + 1) % N
        j = (j + S[i]) % N
        swap(i, j)
        output[l] = S[(S[i] + S[j]) % N]

    return output

関数 prga は、内部で関数 ksa を呼び出しています。そのため、入力として秘密鍵が必要になります。また、キーストリームの長さ（つまり、暗号化・復号する対象の長さ）を指定するために loop_length を整数型で受け取っています。返り値は、指定された長さのキーストリーム（int のリスト）です。

暗号化と復号

最後に、キーストリームを使用して暗号化・復号処理を行う部分を Python で書きます。

def byte_xor(bi1: bytes, bi2: list[int]) -> bytes:
    return bytes([a ^ b for a, b in zip(bi1, bi2)])


def encrypt(pText: str, S: list[int]) -> bytes:    
    bText = bytes(pText, "utf-8")
    return byte_xor(bText, S)


def decrypt(eText: bytes, S: list[int]) -> str:
    deText = byte_xor(eText, S)
    return deText.decode("utf-8")

今回は、文字列の暗号化・復号を前提にしています。暗号化処理は、平文である文字列と内部状態 $S$ を引数としています。関数 encrypt では、各引数を 1byte ずつ取り出して排他的論理和をとっています。

反対に復号処理は、バイト配列（bytes 型）と内部状態を引数としています。関数 decrypt も同様に、各引数を 1byte ずつ取り出して排他的論理和をとっています。

上記のプログラムの使用例を示します。

plainText = input("plainText > ")
secretKey: bytes = random.randbytes(SECRETKEY_BYTE_LENGTH)
print(f"secretKey: {bytes.hex(secretKey)}")
S: list[int] = prga(secretKey, len(bytes(plainText, "utf-8")))
// 内部状態を表示
print(len(S), S)
eText = encrypt(plainText, S)
print(f"encrypt: {bytes.hex(eText)}")
deText = decrypt(eText, S)
print(f"decrypt: {deText}")
 
fika:rc4 shuma$ pipenv run python rc4.py 
plainText > Hello
secretKey: c87486500f2497
5 [122, 147, 104, 244, 131]
encrypt: 32f60498ec
decrypt: Hello

Hello を暗号化して、復号したときにもとの文字列に戻ったので OK