RC4对称加密技术

编程入门行业动态更新时间:2024-10-25 14:34:14

RC4<a href=https://www.elefans.com/category/jswz/34/1763015.html style= 对称加密技术"/>

RC4对称加密技术

MD DocUmEnT: 3/14/2016 04:57:54 AM by Jimbowhy
PDF版下载：

背景资料

1987年，Ron Rivest 为他的公司 RSA Data Security, Inc. 发明了 RC4 加密系统，加密过程十分简洁明了，以致可以用大多数据语言重新编写。纳德·李维斯特 Ronald L. Rivest，就是 RSA 非对称加密算法的主要作者。和DES算法一样，RC4 是一种对称加密算法，也就是说使用同一个密钥来实现加密与解密，或者说对明文进行一次加密得到密文，对密文进行一次加密就可以得到明文。和DES不同于的是，RC4不是对明文进行分组处理，而是字节流的方式依次加密明文中的每一个字节，解密的时候也是依次对密文中的每一个字节进行解密。这种加密方式又称流式加密，RC4 是应用最广泛的流加密算法，应用在安全套接字层 SSL Security Socket layer 来保护网络上传输的数据，也应用于网络数据保护 WEP Wired Equivalent Privacy，而新的无线网络数据保护 WPA Wi-Fi Protected Access 已经取代了它在这方面的应用。

RC4官方名是“Rivest Cipher 4”，RC4是商业密码，是在94年9月份的时候，被人匿名公开在了Cypherpunks 邮件列表上，很快它就被发到了sci.crypt 新闻组上，随后从这儿传播到了互联网的许多站点。随之贴出的代码后来被证明是很有水平的，因为它的输出跟取得了RC4版权的私有软件的输出是完全的。由于算法已经公开，RC4也就不再是商业秘密了，只是它的名字“RC4”仍然是一个注册商标。RC4经常被称作是“ARCFOUR”或者”ARC4”，因为RSA从来没有官方公布这个算法，这样来避免商标使用的问题。

它的最大亮点是算法的简单性和快速处理，因此它可以很容易多种语言上实现。设有一个256字节的数组，用它来加密明文 plaintext，每使用一次，数组的就要交换其中两个字节。被交换的两个字节通过变量 i j 来指定，它们初始值为 0。计算 i 的新值时，直接加一，计算 j 的新值时，将 i 数值对应的数组字节值和密钥字节值相加得到。要得到密文 ciphertext，将明文和 i j 求和后指示的字节相异或 XOR，加密 encrypt 和解密 decrypt 的过程一样。然后交换 i j 指示的数组字节，所有操作都对256求模，数组使用前经过初始化，值依次为 0-255。密钥长度在 1-256字节，以下就是C语言实现的RC4算法：

/** RC4 encryption by Jimbowhy* @key : password whin 256 bytes* @p   : plaintext/chipher to encrypt/decrypt, MODIFIED*/
string RC4(string key, string &p){unsigned int k = 0, lk = key.length(), lp = p.length(), mod = 256;unsigned char *sbox = (unsigned char *)malloc(mod);unsigned char i = 0, j = 0;for(i=0; i<mod; i++){sbox[i] = i;if(i==255) break;}for(i=0; i<mod; i++){j += key[i%lk] + sbox[i];sbox[i] = sbox[i] ^ sbox[j]; // a = a + bsbox[j] = sbox[i] ^ sbox[j]; // b = a - bsbox[i] = sbox[i] ^ sbox[j]; // a = a - bif(i==255) break;}i = j = k = 0;while(k<lp){j += sbox[++i];sbox[i] = sbox[i] ^ sbox[j]; /***/sbox[j] = sbox[i] ^ sbox[j]; /***/sbox[i] = sbox[i] ^ sbox[j]; /***/p[k] = p[k] ^ sbox[(sbox[i] + sbox[j]) % mod];k++;}delete sbox;return p;
}

代码中的 sbox 指 Substitution Box，直译为密码置换盒，这是常见的用于增强保密性的原始密码处理过程。程序的基本过程：

初始化255字节的密钥置换盒；
根据密钥扰乱置换盒的状态；
重围变量 i j;
对输入字节流进行异或运算；
完成输出。

测试程序：

char k[] = {0x61, 0x8A, 0x63, 0xD2, 0xFB};
char p[] = {0x2C, 0xF9, 0x4C, 0xEE, 0xDC};
string ps(p, sizeof(p));
string ks(k, sizeof(k));
cout << "plaintext to encrypt: " << toHex(ps) << endl;
cout << "          key to hex: " << toHex(ks) << endl;
cout << "   ciphertext to hex: " << toHex( RC4(ks, ps) ) << endl;
cout << "    decrypted to hex: " << toHex( RC4(ks, ps) ) << endl << endl;plaintext to encrypt: 0x2c 0xf9 0x4c 0xee 0xdc  key to hex: 0x61 0x8a 0x63 0xd2 0xfb  ciphertext to hex: 0x01 0x2f 0x29 0xde 0x2e  decrypted to hex: 0x2c 0xf9 0x4c 0xee 0xdc

安全性增强

在上面的代码中，可以看到RC4的流式加密过程中，编码是以字节为单位的，也就是说每个字节就是一个编码块，而且各个字节间相互独立，这样编码方法就称为电码本模式 ECB Electronic Codebook，ECB 模式是分组密码的一种最基本的工作模式。在该模式下，待处理信息被分为大小合适的分组，然后分别对每一分组独立进行加密或解密处理。流程看起来就如下图一样：

            +---------------+ plaintext  | | | | | | | | | +-------+-------+ |         
+------+     +------+-------+ 
| key  |---->| block cipher | 
+------+     |  encryption  | +------+-------+ |         +-------+-------+ 
ciphertext  | | | | | | | | | +---------------+

为了理解这种模式有什么安全性缺点，这里引用FC的超级玛丽游戏上的一幅图片，左侧的图像是正常的，中间的图片则是对每个像素进行加密后得到的，是不是发现加密几乎完全失败了，因为图像的内容还可以辨识。通过加密图片像素可以得出ECB加密的随机性是不够的，尽管图片的上边几乎是认不出内容的，但是越往下的随机性越差。因此，如果将上面的RC4算法用于文本的加密还是可行的，但是用于图像这类靠大量数据传递的信息却不是那有效果。当然，如果加密算法中 while 循环中的密钥转换盒的操作去掉，即注解/*/几行代码去掉也可以让图片的内容识别不出来，再增加密钥长度就可以提高随机性，最右侧的图片就是使用2048-bit密钥加密的结果：

在测试中发现，有些长度不大的密钥也能产生很强的随机性，比如这几个8-bit、80-bit长度不等的密钥：

99 25 34 FB 99 78 86 10  93 67
62 E3 A4 07 83 B6 3D 38  E7 
C0 CB 96 94 2A 33 21 
56 4B 65 3E F1 CF AB 
52 EF EF 7F AA 
A1 A4 35 BD DA 
E9 72 91 C3 C2 
2F

而有些很长的密钥随机性反而不是特别好，比如这个2048-bit密钥：

C4 20 85 9F 9A 81 84 D3  B1 BF DB 57 F2 37 A3 FE
BD 65 EE 2F A5 5D AB 44  AC DF 09 88 40 BF 46 45
8C 81 23 EB 0A 6E A4 4D  8A 64 DA 6F 09 ED BB 7D
FA 69 0D F7 9C A8 F6 E1  CC 24 EF 3D CD 0C EF 96
95 ED 26 F1 D2 77 E4 B7  2C 70 D6 DF DF 7C 20 8C
30 6F 79 75 E0 9C B9 E7  E6 E6 82 99 60 13 FB E3
85 40 A4 3C 15 9D 85 40  EE 72 82 70 F3 26 16 36
8F C8 E8 88 ED 45 32 2C  79 FD 4D 08 34 4C 73 3A
E9 70 0A 12 B1 8F F0 C4  87 A0 38 0B D1 53 DA D2
A0 46 68 C9 82 BB BC 1B  C9 83 96 1B 86 4F D3 34
BB 8D A2 2B 6B 17 02 DF  08 E0 1C 25 F5 72 8A 99
A2 50 F1 71 CB 94 BF 9F  16 EC 3C F0 8E E7 41 D9
24 ED 6C 7A 8A C6 1A DA  F5 5D 9C 6B 17 9B 38 17
A4 58 A2 DB 36 A1 A1 EC  A1 0A 63 25 CD 2B 87 D3
2D 4C EF C6 40 05 A5 57  2B B8 B2 B1 FE F5 40 C3
B8 56 F9 05 6A 90 4C 0C  3D B3 14 F2 0C 9F 4B 5A

因为RC4算法具有实现简单，加密速度快，对硬件资源耗费低等优点，于轻量级加密算法的行列中确属优秀的算法。但是另一方面，其简单的算法结构也容易遭到破解攻击，RC4算法的加密强度完全取决于密钥，即伪随机序列生成，而真正的随机序列是不可能实现，只能实现伪随机。这就不可避免出现密钥的重复，而加密解密过程都进行了异或运算，这就意味着，一旦子密钥序列出现了重复，密文就极有可能被破解。

具体破解过程如下：若明文、密钥是任意长的字节，可以用重合码计数法(counting coincidence)找出密钥长度。把密文进行各种字节的位移，并与原密文进行异或运算，统计那些相同的字节。如果位移是密钥长度的倍数，那么超过60%的字节将是相同的；如果不是，则至多只有0.4%的字节是相同的，这叫做重合指数(index of coincidence)。找出密钥长度倍数的最小位移，按此长度移到密文，并且和自身异或。由于明文每字节有1.3位的实际信息，因此有足够的冗余度去确定位移的解密。对所有的密钥，输出密钥流的前几个字节不是随机的，因此极有可能会泄露密钥的信息。如果一个长期使用的密钥与一个随机数串联产生RC4算法密钥，那么可以通过分析大量由该密钥加密的密文得到这个长期使用的密钥。

为了得到以上图片，需要使用 Mathematica 来简单处理一下图像，将图像的像素导出到一个数据文件，然后通过加密程序来处理数据，再将加密处理后的数据导入重新生成图像：

tux = "C:\\writing\\VirtualNes\\MARIO.jpg";
df = "C:\\writing\\MARIO.txt";
im = Import[tux];
ib = ImageData[im, "Byte"];
Export[df, ib, "Byte"];
SetDirectory["C:\\c\\src\\base_struct\\"];
pw = RandomInteger[{0, 255}, 256];
Export["pw.dat", pw, "Byte"]
<< "!rc4.exe pw.dat C:\\writing\\MARIO.txt"
ib = Import[df, "Byte"];
ib = Partition[ib, 3];
ib = Partition[ib, 256];
<< "!rc4.exe pw.dat  C:\\writing\\MARIO.txt"
im = Import[df, "Byte"];
im = Partition[im, 3];
im = Partition[im, 256];
{Image[im, "Byte"], Image[ib, "Byte"]}

为了得到 rc4.exe，需要编译以下代码和 RC4 的算法函数：

#include <iostream>
#include <fstream>
#include <cstdlib>using namespace std;void putStream(string p, string d){ofstream fo( p.data(), ios::binary|ios::out );fo.write( d.data(), d.length() );fo.close();
}
string getStream(string p){int len;char *buf; ifstream fi( p.data(), ios::binary|ifstream::in );//fi.open( p.data(), ios::binary|ios::in );if( !fi.is_open() || fi.fail() ) return string();fi.seekg( 0,ios::end );len = fi.tellg();fi.seekg( 0,ios::beg );buf = new char[len];fi.read ( buf,len );fi.close();string *r = new string(buf, len);delete buf;return *r;
}int main(int argc, char *args[]){if(argc==3){string fk = getStream(args[1]);string fs = getStream(fp);if( !(fs.length() && fk.length()) ){cout << "check key length: " << fk.length() << " data length: " << fs.length();return 1;}putStream( fp+".log",fs );RC4(fk, fs);putStream( fp,fs );cout << "\"file encrypted, length:" << fs.length() << "\"";return 0;}
}

1994年 Ronald L. Rivest 在他的 RC4 升级版 RC5 中引入了分组密码算法 CBC Cipher Block Chaining。CBC模式下，数据块在加密前会先与前一个已加密数据块的异或运算然后再用加密器加密。第一个明文块与一个叫初始化向量 Initialization vector 的数据块异或。相比ECB，CBC模式有更高的保密性，但由于对每个数据块的加密依赖与前一个数据块的加密所以加密无法并行。以下为几种主要的加密编码模式：

Electronic Codebook (ECB)
Cipher Block Chaining (CBC)
Propagating Cipher Block Chaining (PCBC)
Cipher Feedback (CFB)
Output Feedback (OFB)
Counter (CTR)

密文反馈模式 CFB Cipher feedback，与ECB和CBC模式只能够加密块数据不同，CFB能够将密文块 Block Cipher 转换为密文流 Stream Cipher。

输出反馈模式 OFB Output feedback, OFB是先用块加密器生成密钥流（Keystream），然后再将密钥流与明文流异或得到密文流，解密是先用块加密器生成密钥流，再将密钥流与密文流异或得到明文，由于异或操作的对称性所以加密和解密的流程是完全一样的。

计数模式 CTR Counter 也称为 ICM Integer counter mode 或 SIC Segmented integer counter 模式，和 OFB 模式类似地，计数模式可以将密文块转换成密文流，它通过引入一个连续的计数值来生成密码流，因此各个密文数据块的关系并不像 CBC 和 CFB 那样具有前后依赖。

图片来源WIKI