RC4加密算法学习记录

博主： Richard
发布时间：2019 年 10 月 08 日
845 次浏览
暂无评论
4194字数
分类：数据结构与算法 Crypto

RC4于1987年提出，和DES算法一样，是一种对称加密算法，也就是说使用的密钥为单钥（或称为私钥）。但不同于DES的是，RC4不是对明文进行分组处理，而是字节流的方式依次加密明文中的每一个字节，解密的时候也是依次对密文中的每一个字节进行解密。

## 算法特点
RC4算法的特点是算法简单，运行速度快，而且密钥长度是可变的，可变范围为1-256字节(8-2048比特)，在如今技术支持的前提下，当密钥长度为128比特时，用暴力法搜索密钥已经不太可行，所以可以预见RC4的密钥范围任然可以在今后相当长的时间里抵御暴力搜索密钥的攻击。

## 算法原理
转载一张图片([图片来源](https://www.cnblogs.com/block2016/p/5601925.html)): 
![RC4.jpg](https://blog.domineto.top/usr/uploads/2019/10/3445645282.jpg)
### 前提
在讲 RC4 的算法之前，先看几个里面的关键变量：

1. **密钥流**：
RC4算法的关键是根据明文和密钥生成相应的密钥流，密钥流的长度和明文的长度是对应的;

2. **状态向量S**：
长度为256，S[0],S[1]....S[255]。每个单元都是一个字节，算法运行的任何时候，S都包括0-255的8比特数的排列组合，只不过值的位置发生了变换;

3. **临时向量T**：
长度也为256，每个单元也是一个字节。如果密钥的长度是256字节，就直接把密钥的值赋给T，否则，循环将密钥的每个字节赋给T;

4. **密钥K**：
长度为1-256字节，注意密钥的长度与明文长度、密钥流的长度没有必然关系，通常密钥的长度取16字节（128比特）。

### 原理
RC4 的原理分为三步:

#### 1. 初始化 S 和 T
伪代码如下: 
```cpp
for i=0 to 255 do

S[i]=i;

T[i]=K[ i mod key_len ];
```

#### 2. 初始化排列 S
伪代码如下: 
```cpp
j=0;

for i=0 to 255 do

j= ( j + S[i] + T[i])mod256;

swap(S[i], S[j]);
```

#### 3. 产生密钥流
伪代码如下: 
```cpp
i, j=0;

for r=0 to len do  //r为明文长度，r字节

i=(i + 1) mod 256;

j=(j + S[i])mod 256;

swap(S[i], S[j]);

t=(S[i] + S[j]) mod 256;

k[r] = S[t];
```

## C++ 实现
> RC4.h

```cpp
#pragma once

#include <fstream>
#include <string>
#include <vector>

using std::string;
using std::vector;

class RC4
{
private:
	string key; // 可变长度密钥
	string key_stream; // 密钥流

unsigned char S[256]; // 状态向量 S
	unsigned char T[256]; // 临时向量 T

void initial(); // 初始化
	void rangeS(); // S 的初始置换
	void key_stream_generate(int len);

public:
	RC4();
	~RC4();
	RC4(const string& k);

bool set_key(const string& k);

string encrypt(const string& plain);
	string decrypt(const string& cipher);

void encrypt(string plain_path, string cipher_path);
	void decrypt(string cipher_path, string plain_path);
};

/**
 * \brief 工具函数, string 转换为 hex
 */
string string2hex(string in)
{
	string res;

for (auto i : in)
	{
		int tmp = static_cast<int>(i);

int high = (tmp & 0xf0) >> 4;
		int low = (tmp & 0x0f);

res += (high < 10 ? '0' + high : 'a' + high - 10);
		res += (low < 10 ? '0' + low : 'a' + low - 10);
	}

return res;
}
```

> RC4.cpp

```cpp
#include "RC4.h"

/**
 * \brief 初始化状态向量S和临时向量T
 */
void RC4::initial()
{
	// 清空密钥流
	key_stream.clear();
	
	for (auto i = 0; i < 256; i++)
	{
		S[i] = i;
		T[i] = key[i % key.length()];
	}
}

/**
 * \brief 初始排列状态向量S
 */
void RC4::rangeS()
{
	auto j = 0;

for (auto i = 0; i < 256; i++)
	{
		j = (j + S[i] + T[i]) % 256;

std::swap(S[i], S[j]);
	}
}

/**
 * \brief 生成密钥流
 * \param len 明文长度
 */
void RC4::key_stream_generate(int len)
{
	initial();
	rangeS();

auto i = 0, j = 0;

while (len--)
	{
		i = (i + 1) % 256;
		j = (j + S[i]) % 256;

std::swap(S[i], S[j]);

const auto t = (S[i] + S[j]) % 256;

key_stream.push_back(S[t]);
	}
}

RC4::RC4()
= default;

RC4::~RC4()
= default;

RC4::RC4(const string& k)
{
	key = k;
}

bool RC4::set_key(const string& k)
{
	key = k;
	
	return true;
}

string RC4::encrypt(const string& plain)
{
	string cipher = plain;
	
	// 生成密钥流
	key_stream_generate(plain.length());

// 将原文与密钥流异或
	for (auto i = 0; i < plain.length(); i++)
		cipher[i] ^= key_stream[i];

return cipher;
}

string RC4::decrypt(const string& cipher)
{
	string plain = cipher;

// 生成密钥流
	key_stream_generate(cipher.length());

// 将密文与密钥流异或
	for (auto i = 0; i < cipher.length(); i++)
		plain[i] ^= key_stream[i];

return plain;
}

void RC4::encrypt(string plain_path, string cipher_path)
{
	std::ifstream in;
	std::ofstream out;

// 打开输入输出文件以及相应的异常处理
	in.open(plain_path, std::ios::binary);

if (!in.is_open())
		throw "Input file open error!";

out.open(cipher_path, std::ios::binary);

if (!out.is_open())
		throw "Output file open error!";

// 获取文件流的长度
	in.seekg(0, std::ios::end);
	auto file_len = in.tellg();
	in.seekg(0, std::ios::beg);
	
	// 读入整个文件
	string plain((std::istreambuf_iterator<char>(in)), std::istreambuf_iterator<char>());

// 加密并写入文件
	for (auto i = 0; i < file_len; i++)
		out << static_cast<unsigned char>(plain[i] ^ key_stream[i]);
}

void RC4::decrypt(string cipher_path, string plain_path)
{
	std::ifstream in;
	std::ofstream out;

// 打开输入输出文件以及相应的异常处理
	in.open(cipher_path, std::ios::binary);

if (!in.is_open())
		throw "Input file open error!";

out.open(plain_path, std::ios::binary);

if (!out.is_open())
		throw "Output file open error!";

// 获取文件流的长度
	in.seekg(0, std::ios::end);
	auto file_len = in.tellg();
	in.seekg(0, std::ios::beg);

// 读入整个文件
	string plain((std::istreambuf_iterator<char>(in)), std::istreambuf_iterator<char>());

// 解密并写入文件
	for (auto i = 0; i < file_len; i++)
		out << static_cast<unsigned char>(plain[i] ^ key_stream[i]);
}
```

> main.cpp

```cpp
#include <iostream>
#include <chrono>
#include "RC4.h"
using namespace std;

RC4 rc4;
string k;
string plain_path;
string cipher_path;

int main()
{
	ifstream file;
	ofstream out;
	char cmd;

CHANGE_KEY:
	cout << "请输入你的密钥" << endl;
	cin >> k;

rc4.set_key(k);

system("cls");

while (true)
	{
		cout << "你的密钥为: " << k << endl;
		cout << "1. 加密\n2. 解密\n3. 修改密钥\n4. 退出" << endl;
		cin >> cmd;

switch (cmd)
		{
		case '1':
		{
			cout << "输入明文所在文件的绝对路径" << endl;
			cin.get();
			getline(cin, plain_path);

file.open(plain_path, ios::binary);

if (!file.is_open())
			{
				cout << "打开明文文件时发生错误!" << endl;
				break;
			}

cout << "输入密文输出文件的绝对路径" << endl;
			getline(cin, cipher_path);

out.open(cipher_path, ios::binary);

if (!out.is_open())
			{
				cout << "打开输出文件时发生错误!" << endl;
				break;
			}

// 一次读入整个文件，之后再分组加密
			string plain((istreambuf_iterator<char>(file)), istreambuf_iterator<char>());

auto begin = std::chrono::system_clock::now();

string cipher;

cipher = rc4.encrypt(plain);

auto end = std::chrono::system_clock::now();
			auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - begin);

out.write(cipher.c_str(), cipher.length());

file.clear();
			file.close();
			out.clear();
			out.close();

cout << "加密成功!" << endl;
			cout << "一共花费了" << double(duration.count()) * \
				std::chrono::microseconds::period::num / std::chrono::microseconds::period::den \
				<< "秒" << endl;

break;
		}
		case '2':
		{
			cout << "输入密文所在文件的绝对路径" << endl;
			cin.get();
			getline(cin, cipher_path);

file.open(cipher_path, ios::binary);

if (!file.is_open())
			{
				cout << "打开明文文件时发生错误!" << endl;
				break;
			}

cout << "输入明文输出文件的绝对路径" << endl;
			getline(cin, plain_path);

out.open(plain_path, ios::binary);

if (!out.is_open())
			{
				cout << "打开输出文件时发生错误!" << endl;
				break;
			}

string cipher((istreambuf_iterator<char>(file)), istreambuf_iterator<char>());

auto begin = std::chrono::system_clock::now();

string plain;

plain = rc4.decrypt(cipher);

auto end = std::chrono::system_clock::now();
			auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - begin);

out.write(plain.c_str(), plain.length());

file.clear();
			file.close();
			out.clear();
			out.close();

cout << "解密成功!" << endl;
			cout << "一共花费了" << double(duration.count()) * \
				std::chrono::microseconds::period::num / std::chrono::microseconds::period::den \
				<< "秒" << endl;

break;
		}
		case '3': goto CHANGE_KEY;
		case '4': return 0;
		default: cout << "不要瞎按!" << endl; break;
		}

system("pause");
		system("cls");
	}

return 0;
}
```

最后修改：2019 年 11 月 18 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

[每日一题] 216.组合总和III - Richardの小小杂货铺
[...]};时间复杂度 $O(M \times 2^M)$ ...
fa
最新的版本无法登陆，能否指导一下。多谢
rantrism
您好～我是腾讯云开发者社区运营，关注了您分享的技术文章，觉得内...
examine
Richard什么时候带我
https://telegra.ph/Technology-A-linchpin-To-Maintain-Businesses-Handle-Remote-Workforce-Amid-Pandemic---Technology-02-16
You actually expressed this ade...

RC4加密算法学习记录

Richard • 2019 年 10 月 08 日

1. **密钥流**：
RC4算法的关键是根据明文和密钥生成相应的密钥流，密钥流的长度和明文的长度是对应的;

3. **临时向量T**：
长度也为256，每个单元也是一个字节。如果密钥的长度是256字节，就直接把密钥的值赋给T，否则，循环将密钥的每个字节赋给T;

4. **密钥K**：
长度为1-256字节，注意密钥的长度与明文长度、密钥流的长度没有必然关系，通常密钥的长度取16字节（128比特）。

### 原理
RC4 的原理分为三步:

#### 1. 初始化 S 和 T
伪代码如下: 
```cpp
for i=0 to 255 do

S[i]=i;

T[i]=K[ i mod key_len ];
```

#### 2. 初始化排列 S
伪代码如下: 
```cpp
j=0;

for i=0 to 255 do

j= ( j + S[i] + T[i])mod256;

swap(S[i], S[j]);
```

#### 3. 产生密钥流
伪代码如下: 
```cpp
i, j=0;

for r=0 to len do  //r为明文长度，r字节

i=(i + 1) mod 256;

j=(j + S[i])mod 256;

swap(S[i], S[j]);

t=(S[i] + S[j]) mod 256;

k[r] = S[t];
```

## C++ 实现
> RC4.h

```cpp
#pragma once

#include <fstream>
#include <string>
#include <vector>

using std::string;
using std::vector;

class RC4
{
private:
	string key; // 可变长度密钥
	string key_stream; // 密钥流

unsigned char S[256]; // 状态向量 S
	unsigned char T[256]; // 临时向量 T

void initial(); // 初始化
	void rangeS(); // S 的初始置换
	void key_stream_generate(int len);

public:
	RC4();
	~RC4();
	RC4(const string& k);

bool set_key(const string& k);

string encrypt(const string& plain);
	string decrypt(const string& cipher);

void encrypt(string plain_path, string cipher_path);
	void decrypt(string cipher_path, string plain_path);
};

/**
 * \brief 工具函数, string 转换为 hex
 */
string string2hex(string in)
{
	string res;

for (auto i : in)
	{
		int tmp = static_cast<int>(i);

int high = (tmp & 0xf0) >> 4;
		int low = (tmp & 0x0f);

res += (high < 10 ? '0' + high : 'a' + high - 10);
		res += (low < 10 ? '0' + low : 'a' + low - 10);
	}

return res;
}
```

> RC4.cpp

```cpp
#include "RC4.h"

/**
 * \brief 初始排列状态向量S
 */
void RC4::rangeS()
{
	auto j = 0;

for (auto i = 0; i < 256; i++)
	{
		j = (j + S[i] + T[i]) % 256;

std::swap(S[i], S[j]);
	}
}

/**
 * \brief 生成密钥流
 * \param len 明文长度
 */
void RC4::key_stream_generate(int len)
{
	initial();
	rangeS();

auto i = 0, j = 0;

while (len--)
	{
		i = (i + 1) % 256;
		j = (j + S[i]) % 256;

std::swap(S[i], S[j]);

const auto t = (S[i] + S[j]) % 256;

key_stream.push_back(S[t]);
	}
}

RC4::RC4()
= default;

RC4::~RC4()
= default;

RC4::RC4(const string& k)
{
	key = k;
}

bool RC4::set_key(const string& k)
{
	key = k;
	
	return true;
}

string RC4::encrypt(const string& plain)
{
	string cipher = plain;
	
	// 生成密钥流
	key_stream_generate(plain.length());

// 将原文与密钥流异或
	for (auto i = 0; i < plain.length(); i++)
		cipher[i] ^= key_stream[i];

return cipher;
}

string RC4::decrypt(const string& cipher)
{
	string plain = cipher;

// 生成密钥流
	key_stream_generate(cipher.length());

// 将密文与密钥流异或
	for (auto i = 0; i < cipher.length(); i++)
		plain[i] ^= key_stream[i];

return plain;
}

void RC4::encrypt(string plain_path, string cipher_path)
{
	std::ifstream in;
	std::ofstream out;

// 打开输入输出文件以及相应的异常处理
	in.open(plain_path, std::ios::binary);

if (!in.is_open())
		throw "Input file open error!";

out.open(cipher_path, std::ios::binary);

if (!out.is_open())
		throw "Output file open error!";

// 加密并写入文件
	for (auto i = 0; i < file_len; i++)
		out << static_cast<unsigned char>(plain[i] ^ key_stream[i]);
}

void RC4::decrypt(string cipher_path, string plain_path)
{
	std::ifstream in;
	std::ofstream out;

// 打开输入输出文件以及相应的异常处理
	in.open(cipher_path, std::ios::binary);

if (!in.is_open())
		throw "Input file open error!";

out.open(plain_path, std::ios::binary);

if (!out.is_open())
		throw "Output file open error!";

// 获取文件流的长度
	in.seekg(0, std::ios::end);
	auto file_len = in.tellg();
	in.seekg(0, std::ios::beg);

// 读入整个文件
	string plain((std::istreambuf_iterator<char>(in)), std::istreambuf_iterator<char>());

// 解密并写入文件
	for (auto i = 0; i < file_len; i++)
		out << static_cast<unsigned char>(plain[i] ^ key_stream[i]);
}
```

> main.cpp

```cpp
#include <iostream>
#include <chrono>
#include "RC4.h"
using namespace std;

RC4 rc4;
string k;
string plain_path;
string cipher_path;

int main()
{
	ifstream file;
	ofstream out;
	char cmd;

CHANGE_KEY:
	cout << "请输入你的密钥" << endl;
	cin >> k;

rc4.set_key(k);

system("cls");

while (true)
	{
		cout << "你的密钥为: " << k << endl;
		cout << "1. 加密\n2. 解密\n3. 修改密钥\n4. 退出" << endl;
		cin >> cmd;

switch (cmd)
		{
		case '1':
		{
			cout << "输入明文所在文件的绝对路径" << endl;
			cin.get();
			getline(cin, plain_path);

file.open(plain_path, ios::binary);

if (!file.is_open())
			{
				cout << "打开明文文件时发生错误!" << endl;
				break;
			}

cout << "输入密文输出文件的绝对路径" << endl;
			getline(cin, cipher_path);

out.open(cipher_path, ios::binary);

if (!out.is_open())
			{
				cout << "打开输出文件时发生错误!" << endl;
				break;
			}

// 一次读入整个文件，之后再分组加密
			string plain((istreambuf_iterator<char>(file)), istreambuf_iterator<char>());

auto begin = std::chrono::system_clock::now();

string cipher;

cipher = rc4.encrypt(plain);

auto end = std::chrono::system_clock::now();
			auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - begin);

out.write(cipher.c_str(), cipher.length());

file.clear();
			file.close();
			out.clear();
			out.close();

break;
		}
		case '2':
		{
			cout << "输入密文所在文件的绝对路径" << endl;
			cin.get();
			getline(cin, cipher_path);

file.open(cipher_path, ios::binary);

if (!file.is_open())
			{
				cout << "打开明文文件时发生错误!" << endl;
				break;
			}

cout << "输入明文输出文件的绝对路径" << endl;
			getline(cin, plain_path);

out.open(plain_path, ios::binary);

if (!out.is_open())
			{
				cout << "打开输出文件时发生错误!" << endl;
				break;
			}

string cipher((istreambuf_iterator<char>(file)), istreambuf_iterator<char>());

auto begin = std::chrono::system_clock::now();

string plain;

plain = rc4.decrypt(cipher);

auto end = std::chrono::system_clock::now();
			auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - begin);

out.write(plain.c_str(), plain.length());

file.clear();
			file.close();
			out.clear();
			out.close();

break;
		}
		case '3': goto CHANGE_KEY;
		case '4': return 0;
		default: cout << "不要瞎按!" << endl; break;
		}

system("pause");
		system("cls");
	}

return 0;
}
```

RC4加密算法学习记录

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【转】提问的智慧

【枫燃异闻录】利用python爬取Bangumi评分

BUUCTF-web writeup (更新中)

Typecho附件上传大小限制修改

记录一道卡了我好几天的题目

[计算机网络] 数据链路层

2019 中关村CTF 部分 writeup

[马原] 马克思主义的创立与发展

tesseract 初尝试

WIN10中搭建FTP服务器

RC4加密算法学习记录

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

RC4加密算法学习记录

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款