# RC4加密算法(學習筆記)
## 簡介
RC4是一種串流加密法，密鑰長度可變。其屬於對稱式加密，且加解密過程一樣。
## 原理
### 初始化
1. 初始化S盒，其中包含所有0到255的元素(S[i] = i)
2. KSA——用一個密鑰進行一系列操作交換S盒，以根據密鑰混淆S盒。(因為不難，且code比中文好理解，故不詳述)
注:密鑰可以為任意長度，RC4會重複使用，直到將長度擴展到256字節
### 加密
1. 偽隨機算法PRGA(i,j從零開始，重複以下動作len(plaintext)次)
- i = (i + 1) mod 256
- j = (j + S[i]) mod 256
- 交換S[i]和S[j]的值。
- 根據交換後的S，計算k = (S[i] + S[j]) mod 256。
- 選擇S[k]作為密鑰流的下一個位元組。
2. 密文=明文xor由S[k]組成的密鑰流
## 解密
由於使用一樣的密鑰經過KSA和PRGA後會完全得到一樣的S盒和一樣的密鑰流
且A xor B xor B = A
故加密和解密的過程完全一樣
## 安全性
1. 由於RC4生成的密鑰流可以不斷延長的，所以每段明文都是由不同的部分加密。這就避免了單純使用異或加密時，密鑰長度小於明文的安全性問題。
2. 密鑰在經過密鑰調度算法(KSA)和偽隨機生成算法(PRGA)後，從密鑰流逆向反推密鑰變得極度困難，這也保證了安全性。
3. 但RC4仍有許多安全問題，現已逐漸被淘汰使用其他算法。例如AES(詳見[AES&伽羅瓦域/有限域](/2uEV2ydvTK6WjrcYm1DZ1A))
## 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
string key;
string plaintext;
string ciphertext;
unsigned char K[256];//一定要unsigned，範圍才是0~255
unsigned char S[256];
void KSA(){
for(int i = 0; i < 256; i++){//初始化S盒
S[i] = i;
}
for(int i = 0; i < 256; i++){//擴展密鑰
K[i] = key[i % key.size()];
}
int j = 0;
for(int i = 0; i < 256; i++){//置換，打亂S表
j = (j + S[i] + K[i]) % 256;
swap(S[i],S[j]);
}
return;
}
void PRGA_XOR(){//通過偽隨機算法PRGA
int i = 0, j = 0;
for(int p = 0; p < ciphertext.size(); p++){
i = (i + 1) % 256;
j = (j + S[i]) % 256;
swap(S[i], S[j]);
unsigned char k = (S[i] + S[j]) % 256;
ciphertext[p] = plaintext[p] ^ S[k];
}
return;
}
int main(){
cout << "請輸入明文(密文)\n";
cin >> plaintext;
cout << "請輸入密鑰\n";
cin >> key;
KSA();
ciphertext.resize(plaintext.size());
PRGA_XOR();
cout << ciphertext << '\n';
return 0;
}
```
### 加入Base64
寫完後我發現加密完後字元陣列裡面會出現超出ASCII碼規範範圍外的數字，會導致輸出的字元為亂碼，我認為這會造成使用和解密上的麻煩所以，我就決定其進行Base64編碼。加入Base64編碼後還可以讓輸入也更自由(不用再被ASCII碼限制)
>詳見:[Base64編碼](/Zs6Ltgm8QZ-LhbosB85C_Q)
```cpp=
#include<bits/stdc++.h>
using namespace std;
//--------------Base64---------------------
int sBase64[64] = {
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P',
'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f',
'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
'w', 'x', 'y', 'z', '0', '1', '2', '3',
'4', '5', '6', '7', '8', '9', '+', '/'
};
string Base64_encode(string str){
int len = str.size();
string res;
res.resize((len + 2) / 3 * 4);
int j = 0;
for(int i = 0; i < len / 3 * 3;i += 3){
int bits = ((str[i] & 0xff) << 16) | ((str[i+1] & 0xff) << 8) | (str[i+2] & 0xff);
res[j++] = sBase64[(bits >> 18) & 0x3f];
res[j++] = sBase64[(bits >> 12) & 0x3f];
res[j++] = sBase64[(bits >> 6) & 0x3f];
res[j++] = sBase64[bits & 0x3f];
}
if(len % 3 == 1){
int bits = (str[len - 1] & 0xff) << 4;
res[j++] = sBase64[(bits >> 6) & 0x3f];
res[j++] = sBase64[bits & 0x3f];
res[j++] = '=';
res[j] = '=';
}
else if(len % 3 == 2){
int bits = (str[len - 2] & 0xff) << 10 | (str[len - 1] & 0xff) << 2;
res[j++] = sBase64[(bits >> 12) & 0x3f];
res[j++] = sBase64[(bits >> 6) & 0x3f];
res[j++] = sBase64[bits & 0x3f];
res[j] = '=';
}
return res;
}
unsigned char BaseValue(char c){
if(c > 'a' - 1){
return c - 'a' + 26;
}
else if(c > 'A' - 1){
return c - 'A';
}
else if(c > '0' - 1){
return c - '0' + 52;
}
else if(c == '+'){
return 62;
}
else if(c == '/'){
return 63;
}
return -1;
}
string Base64_decode(string str){
int len = str.size();
string res;
for(int i = 0; i < len - 4; i+=4){
res.push_back((BaseValue(str[i]) << 2) | (BaseValue(str[i+1]) >> 4));
res.push_back((BaseValue(str[i+1]) << 4) | (BaseValue(str[i+2]) >> 2));
res.push_back((BaseValue(str[i+2]) << 6)| (BaseValue(str[i+3])));
}
res.push_back((BaseValue(str[len-4]) << 2) | (BaseValue(str[len-3]) >> 4));
if(str[len-2] != '='){
res.push_back((BaseValue(str[len-3]) << 4) | (BaseValue(str[len-2]) >> 2));
}
if(str[len-1] != '='){
res.push_back((BaseValue(str[len-2]) << 6) | (BaseValue(str[len-1])));
}
return res;
}
//--------------Base64---------------------
//---------------RC4-----------------------
string ciphertext;
unsigned char K[256];//一定要unsigned，範圍才是0~255
unsigned char S[256];
void KSA(string key){
for(int i = 0; i < 256; i++){//初始化S盒
S[i] = i;
}
for(int i = 0; i < 256; i++){//擴展密鑰
K[i] = key[i % key.size()];
}
int j = 0;
for(int i = 0; i < 256; i++){//置換，打亂S表
j = (j + S[i] + K[i]) % 256;
swap(S[i],S[j]);
}
return;
}
void PRGA_XOR(string plaintext){
int i = 0, j = 0;
for(int p = 0; p < plaintext.size(); p++){
i = (i + 1) % 256;
j = (j + S[i]) % 256;
swap(S[i], S[j]);
unsigned char k = (S[i] + S[j]) % 256;
ciphertext[p] = plaintext[p] ^ S[k];
}
return;
}
bool isASCII(string str){
for(int i = 0; i < str.size(); i++){
if(!isprint(str[i])){
return 0;
}
}
return 1;
}
//---------------RC4-----------------------
int main(){
string key;
string text;
cout << "注:RC4為對稱為對稱加密算法，加解密使用同一組密鑰" << '\n';
//cout << "注:RC4加密不支援string輸出，容易顯示亂碼(解密支援)" << '\n';
while(1){
cout << "要進行加密請輸入0，解密請輸入1" << '\n';
int flag1;cin >> flag1;
if(!flag1){//加密
cout << "輸入的明文以字節儲存(就是常見的1byte儲存一個)的請輸入0"<<'\n';
cout << "輸入的明文以Base64編碼的請輸入1" << '\n';
int flag2; cin >> flag2;
cin.ignore();
cout << "請輸入明文\n";
getline(cin, text);
if(flag2){
text = Base64_decode(text);
}
}
if(flag1){//解密
cout << "請輸入Base64編碼的密文" << '\n';
cin.ignore();
getline(cin,text);
text = Base64_decode(text);
}
cout << "請輸入密鑰(密鑰以字節儲存處理)\n";
getline(cin, key);
KSA(key);
ciphertext.clear();
ciphertext.resize(text.size());
PRGA_XOR(text);
if(!flag1){
cout << "密文的Base64編碼:" << Base64_encode(ciphertext) << '\n';
}
if(flag1){
cout << "明文為:" << ciphertext;
cout.clear();
cout << '\n';
cout << "明文的Base64編碼:" << Base64_encode(ciphertext) << '\n';
}
cout << "-------------" << '\n';
}
return 0;
}
```
Sign in with Wallet
Connect another wallet