RC 4生成一个伪随机流(pseduorandom stream of bits) 来同 明文 进行 按位异或(bit-wise exclusive-or) 来 实现加密和解密
KSA(key-scheduling algorithm)
初始化数组S. 键长 1 ≤ keylength ≤ 256, 典型值为 5～ 16， 也就是 40bits ~ 128bits
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(&S[i],&S[j])
endfor
PRGA
使用上一步生成的S 数组来生成 伪随机流
i := 0
j := 0
while GeneratingOutput:
i := (i + 1) mod 256
j := (j + S[i]) mod 256
swap(&S[i],&S[j])
output S[(S[i] + S[j]) mod 256]
endwhile
一个C实现
unsigned char S[256];
unsigned int i, j;
void swap(unsigned char *s, unsigned int i, unsigned int j) {
unsigned char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
/* KSA */
void rc4_init(unsigned char *key, unsigned int key_length) {
for (i = 0; i < 256; i++)
S[i] = i;
for (i = j = 0; i < 256; i++) {
j = (j + key[i % key_length] + S[i]) & 255;
swap(S, i, j);
}
i = j = 0;
}
/* PRGA */
unsigned char rc4_output() {
i = (i + 1) & 255;
j = (j + S[i]) & 255;
swap(S, i, j);
return S[(S[i] + S[j]) & 255];
}
#include < stdio.h >
#include < string.h >
#include < stdlib.h >
#define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))
int main() {
unsigned char *test_vectors[][2] =
{
{"Key", "Plaintext"},
{"Wiki", "pedia"},
{"Secret", "Attack at dawn"}
};
int x;
for (x = 0; x < ARRAY_SIZE(test_vectors); x++) {
int y;
rc4_init(test_vectors[x][0], strlen((char*)test_vectors[x][0]));
for (y = 0; y < strlen((char*)test_vectors[x][1]); y++)
printf("%02X", test_vectors[x][1][y] ^ rc4_output());
printf("n");
}
return 0;
}
Python实现
def initialize(key):
"""Produce a 256-entry list based on `key` (a sequence of numbers)
as the first step in RC4.
Note: indices in key greater than 255 will be ignored.
"""
k = range(256)
j = 0
for i in range(256):
j = (j + k[i] + key[i % len(key)]) % 256
k[i], k[j] = k[j], k[i]
return k
def gen_random_bytes(k):
"""Yield a pseudo-random stream of bytes based on 256-byte array `k`."""
i = 0
j = 0
while True:
i = (i + 1) % 256
j = (j + k[i]) % 256
k[i], k[j] = k[j], k[i]
yield k[(k[i] + k[j]) % 256]
def run_rc4(k, text):
cipher_chars = []
random_byte_gen = gen_random_bytes(k)
for char in text:
byte = ord(char)
cipher_byte = byte ^ random_byte_gen.next()
cipher_chars.append(chr(cipher_byte))
return ''.join(cipher_chars)
以上是一种实现方式， run_rc4(k, text) 输入 key 和 待加密的 text, 返回 已经加密的串
class RC4:
def __init__(self, key = ""):
if key:
self._rc4_init(key)
def _rc4_init(self, key):
(self.x,self.y) = (0,0)
key_len = len(key)
if key_len > 256 or key_len < 1:
raise IndexError, 'Invalid key length' + key_len
self.state_array = [i for i in xrange(0,256)] #self.stat_array = range(0,256)
for i in xrange(0,256):
self.x = ((ord(key[i%key_len]) & 0xff) + self.state_array[i] + self.x) & 0xff
self.state_array[i], self.state_array[self.x] = self.state_array[self.x], self.state_array[i]
self.x = 0
def engine_crypt(self, input):
self.out = []
for i in xrange(0,len(input)):
self.x = (self.x + 1) & 0xff
self.y = (self.state_array[self.x] + self.y) & 0xff
self.state_array[self.x], self.state_array[self.y] = self.state_array[self.y], self.state_array[self.x]
self.out.append(chr((ord(input[i]) ^ self.state_array[(self.state_array[self.x] + self.state_array[self.y]) & 0xff])))
return "".join(self.out)
以上是第2种实现，使用了class
使用方法 RC4(key).engine_crypt(text) ，返回的是加密后的串
def rc4crypt(data, key):
x = 0
box = range(256)
for i in range(256):
x = (x + box[i] + ord(key[i % len(key)])) % 256
box[i], box[x] = box[x], box[i]
x = 0
y = 0
out = []
for char in data:
x = (x + 1) % 256
y = (y + box[x]) % 256
box[x], box[y] = box[y], box[x]
out.append(chr(ord(char) ^ box[(box[x] + box[y]) % 256]))
return ''.join(out)
Python3版本
def rc4crypt(data: bytes, key: bytes) -> bytes:
x = 0
box = list(range(256))
for i in range(256):
x = (x + box[i] + key[i % len(key)]) % 256
box[i], box[x] = box[x], box[i]
x = y = 0
out = []
for char in data:
x = (x + 1) % 256
y = (y + box[x]) % 256
box[x], box[y] = box[y], box[x]
out.append((char ^ box[(box[x] + box[y]) % 256]))
return bytes(out)
mykey = b'softs.im!'
mydata = b'android/telephony/TelephonyManager'
x = rc4crypt(mydata, mykey)
import binascii
print(x)
print(binascii.hexlify(x))
y = rc4crypt(x, mykey)
print(y)
print(binascii.hexlify(y))
以上是一个单个函数形式的实现
PHP实现
function Encrypt($key, $pt) {
$s = array();
for ($i=0; $i<256; $i++) {
$s[$i] = $i;
}
$j = 0;
$key_len = strlen($key);
for ($i=0; $i<256; $i++) {
$j = ($j + $s[$i] + ord($key[$i % $key_len])) % 256;
//swap
$x = $s[$i];
$s[$i] = $s[$j];
$s[$j] = $x;
}
$i = 0;
$j = 0;
$ct = '';
$data_len = strlen($pt);
for ($y=0; $y< $data_len; $y++) {
$i = ($i + 1) % 256;
$j = ($j + $s[$i]) % 256;
//swap
$x = $s[$i];
$s[$i] = $s[$j];
$s[$j] = $x;
$ct .= $pt[$y] ^ chr($s[($s[$i] + $s[$j]) % 256]);
}
return $ct;
}
Java也可以实现
private static byte[] rc4_encrypt(byte[] key, byte[] plaintext) {
byte[] S = new byte[256];
byte[] T = new byte[256];
int keylen = key.length;
for (int i = 0; i < 256; i++) {
S[i] = (byte) i;
T[i] = key[i % keylen];
}
int j = 0;
for (int i = 0; i < 256; i++) {
j = (j + S[i] + T[i]) & 0xFF;
S[i] ^= S[j];
S[j] ^= S[i];
S[i] ^= S[j];
}
byte[] ciphertext = new byte[plaintext.length];
int i = 0, k, t;
j = 0;
for (int counter = 0; counter < plaintext.length; counter++) {
i = (i + 1) & 0xFF;
j = (j + S[i]) & 0xFF;
S[i] ^= S[j];
S[j] ^= S[i];
S[i] ^= S[j];
t = (S[i] + S[j]) & 0xFF;
k = S[t];
ciphertext[counter] = (byte) (plaintext[counter] ^ k);
}
return ciphertext;
}