# 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))

## 實作

#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)

#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;
}