分類: 演算法

實作RSA + AES 的檔案加密算法POC

實作RSA + AES 的檔案加密算法POC

為了做到檔案的加密(後來才知道其實用GPG就可以了)

一開始我只是想說用現成套件不同的 金鑰key值作為參數,結合ChatGpt就開始做POC看看了

大不了是換演算法的問題,結果其實數位簽章 除了格式、作業系統管理的模式、公私鑰檔案其實也有不同的規定

但大至上心得是一開始想說讓 檔案加密,而且是透過Public Key進行,然後對方用 Private Key解密,所以我出發點就是用RSA演算法去進行加密,結果發現怎麼都會發生長度錯誤的問題。

後來深究後才發現RSA的加密無法對長度太大的東西進行,所以後來換成短字串果然就可以了

因此思考了加解密該做的事情後,就做了一個AES + RSA的POC,RSA主要用來加密 AES的Key

後來果然發現這個跟GPG的作法有點像~~

實作POC如下∶
using System.Security.Cryptography;

string keyBase64 = string.Empty;
using (Aes aesAlgorithm = Aes.Create())
{
aesAlgorithm.KeySize = 256;
aesAlgorithm.GenerateKey();
keyBase64 = Convert.ToBase64String(aesAlgorithm.Key);
Console.WriteLine($”Aes Key Size : {aesAlgorithm.KeySize}”);
Console.WriteLine(“Here is the Aes key in Base64:”);
Console.WriteLine(keyBase64);
Console.ReadKey();
}

string filePath = “/Users/paul_huang/Desktop/FileEncryptTest”;
GenerateKeys(filePath);

// 設定公鑰和私鑰檔案路徑
string publicKeyPath = Path.Combine(filePath, “publicKey.pem”);
string privateKeyPath = Path.Combine(filePath, “privateKey.pem”);

// 設定金鑰的位元數
var keyString = keyBase64;

// 檢查檔案是否存在
if (!File.Exists(publicKeyPath) || !File.Exists(privateKeyPath))
{
Console.WriteLine(“找不到金鑰檔案。請確保金鑰檔案存在。”);
return;
}

// 讀取公鑰
string publicKey = File.ReadAllText(publicKeyPath);

// 讀取私鑰
string privateKey = File.ReadAllText(privateKeyPath);

// 設定要加密的檔案路徑

// 加密檔案
var keyFileName = “key.txt”;
var keyFilePath = Path.Combine(filePath, keyFileName );
if (File.Exists(keyFilePath) == false)
{
File.WriteAllText(keyFilePath, keyString);
}
else
{
keyString = File.ReadAllText(keyFilePath);
}

EncryptKeyFile(keyFilePath, publicKey);

DecryptKeyFile($”{keyFilePath}.encrypted”, privateKey);


// var encryptedKey = $”{keyFilePath}.encrypted”;

var encryptFile = “paul.jpg”;
var encryptFilePath = Path.Combine(filePath, encryptFile);


var encryptedFileContentString = Encrypt(Convert.ToBase64String(File.ReadAllBytes(encryptFilePath)), keyString);
File.WriteAllText(encryptFilePath+”.encrypted”, encryptedFileContentString);

File.WriteAllBytes(encryptFilePath + “decrypted”, Convert.FromBase64String(Decrypt(encryptedFileContentString, keyString)));

static void EncryptKeyFile(string filePath, string publicKey)
{
try
{
byte[] dataToEncrypt = File.ReadAllBytes(filePath);

using var rsa = new RSACryptoServiceProvider(2048);
rsa.FromXmlString(publicKey);

byte[] encryptedData = rsa.Encrypt(dataToEncrypt, false);

// 寫入加密後的檔案
File.WriteAllBytes($”{filePath}.encrypted”, encryptedData);

Console.WriteLine(“檔案已成功加密。”);
}
catch (Exception ex)
{
Console.WriteLine($”加密時發生錯誤: {ex.Message}”);
}
}

static void DecryptKeyFile(string encryptedFilePath, string privateKey)
{
try
{
byte[] encryptedData = File.ReadAllBytes(encryptedFilePath);

using (RSACryptoServiceProvider rsa = new RSACryptoServiceProvider(2048))
{
rsa.FromXmlString(privateKey);

byte[] decryptedData = rsa.Decrypt(encryptedData, false);

// 寫入解密後的檔案
File.WriteAllBytes($”{encryptedFilePath}.decrypted”, decryptedData);

Console.WriteLine(“檔案已成功解密。”);
}
}
catch (Exception ex)
{
Console.WriteLine($”解密時發生錯誤: {ex.Message}”);
}
}

static string Encrypt(string plainText, string key)
{
using (Aes aesAlg = Aes.Create())
{
aesAlg.KeySize = 256; // Set key size to 256 bits
aesAlg.Key = Convert.FromBase64String(key);
aesAlg.IV = new byte[16]; // AES uses a 128-bit IV

ICryptoTransform encryptor = aesAlg.CreateEncryptor(aesAlg.Key, aesAlg.IV);

using (MemoryStream msEncrypt = new MemoryStream())
{
using (CryptoStream csEncrypt = new CryptoStream(msEncrypt, encryptor, CryptoStreamMode.Write))
{
using (StreamWriter swEncrypt = new StreamWriter(csEncrypt))
{
swEncrypt.Write(plainText);
}
}

return Convert.ToBase64String(msEncrypt.ToArray());
}
}
}

static string Decrypt(string cipherText, string key)
{
using (Aes aesAlg = Aes.Create())
{
aesAlg.KeySize = 256; // Set key size to 256 bits
aesAlg.Key = Convert.FromBase64String(key);
aesAlg.IV = new byte[16];

ICryptoTransform decryptor = aesAlg.CreateDecryptor(aesAlg.Key, aesAlg.IV);

using (MemoryStream msDecrypt = new MemoryStream(Convert.FromBase64String(cipherText)))
{
using (CryptoStream csDecrypt = new CryptoStream(msDecrypt, decryptor, CryptoStreamMode.Read))
{
using (StreamReader srDecrypt = new StreamReader(csDecrypt))
{
return srDecrypt.ReadToEnd();
}
}
}
}
}

static void GenerateKeys(string path)
{
try
{
using (RSACryptoServiceProvider rsa = new RSACryptoServiceProvider(2048))
{
// 公鑰
string publicKey = rsa.ToXmlString(false);
Console.WriteLine(“公鑰:”);
Console.WriteLine(publicKey);

// 私鑰
string privateKey = rsa.ToXmlString(true);
Console.WriteLine(“\n私鑰:”);
Console.WriteLine(privateKey);

// 將金鑰寫入檔案
File.WriteAllText(Path.Combine(path, “publicKey.pem”), publicKey);
File.WriteAllText(Path.Combine(path, “privateKey.pem”), privateKey);

Console.WriteLine(“\n金鑰已成功生成並保存至檔案。”);
}
}
catch (Exception ex)
{
Console.WriteLine($”生成金鑰時發生錯誤: {ex.Message}”);
}
}

static string GenerateRandomKey(int length)
{
// 使用 RNGCryptoServiceProvider 產生安全的亂數
using (var rng = new RNGCryptoServiceProvider())
{
// 建立位元組陣列來存放隨機資料
byte[] randomBytes = new byte[length];

// 將亂數填入位元組陣列
rng.GetBytes(randomBytes);

// 將位元組轉換成十六進位字串
string randomKey = BitConverter.ToString(randomBytes).Replace(“-“, “”);

return randomKey;
}
}

[資訊安全] 在Mac上用GPG套件將檔案加密(231108 更新)

[資訊安全] 在Mac上用GPG套件將檔案加密(231108 更新)

Gpg是一個數位簽章的檔案加密套件

其原理可以從他的祖先PGP去略知一二

利用了RSA的演算法與各種雜湊演算法對檔案進行處理,但若直接 使用RSA演算法無法對檔案大小的長度(我的照片6xx kb)內容加密,所以RSA主要是用在對檔案進行對稱加密的金鑰進行保護加密。
其原理可以再自行看一下相關連結。

下載 GPG套件

https://sourceforge.net/projects/gpgosx/

https://formulae.brew.sh/formula/gnupg

基本上,若是採用這個協定進行加密,應該會提供pgp檔案,pgp通常為對方可公開的公鑰檔案。匯入我們這端的系統後,就可以讓我們以gpg指定對方公鑰作為收件者進行檔案加密。照上圖,檔案加密的RandomKey就是由對方的公鑰做加密,以確保只有對方解的開。


然而對方應該不會提供自己的私鑰,通常是會用於加簽(後面指令中的參數為–sign),若你用自己的私鑰加簽,就要提供自己的公鑰,對方才能做驗簽,可以透過gpg –list-secret-key檢查自己的系統是否有私鑰,若沒有的話,可以上網申請一組。

ex:透過RSA對私鑰進行簡易密語設定,格式也可以指定,匯入時gpg套件都會幫你封裝好這些細節

這邊我們在mac上實際 用 gpg一樣可以匯入pgp的檔案,所以基本上應該是有向下支援了。

gpg import xxxx.asc或skr (注意,是兩個減號) => 此為私鑰檔案,通常只有一份要管理/備份好,若都沒有的話,可以透過指令/金鑰工具產生。

gpg import yyyy.pgp (注意,是兩個減號) => 此為公鑰檔案,每個訊息交換端都可以散佈公鑰檔提供對方做加密傳給自己,而只有自己的私鑰可以解開。

匯入yyyy.gpg的時候會需要輸入password

匯入後,使用以下指令就可以進行檔案加密

gpg –output “/Users/paul_huang/Desktop/{加密後的檔案}.encrypted” -u “paul(Test)” –pinentry-mode loopback –always-trust -r “收檔案者(收件者)的公鑰ID” –s2k-digest-algo “SHA1” –sign –passphrase “加簽章時使用的私鑰密語” –encrypt “/Users/paul_huang/Desktop/{欲加密的檔案}.xml”

成功加密的話,就會有以下的檔案產生  因為涉及加簽,加簽關係到驗簽,證明發送端是我進行的,因此還需要我的公鑰進行驗簽。

註:  

-u, –local-user 使用者-ID,拿指定使用者 ID 來簽署或解密 , 這一步置關重要,要帶入這個參數,對方 才知道你是用 這個人的私key加簽,對方在驗簽的時候,需要你的公鑰進行驗證簽章 ,代表保證檔案的合法性

-r 可以多組 ,代表這個加密檔案,有在收件者當中的人都可以用他的私鑰解密 

可以透過以下指令進行匯出提供接收端做驗簽

gpg –armor –export {公鑰ID} > PublicKey.pgp ( -a, –armor  會以建立以 ASCII 封裝過的輸出)

公鑰ID可以用gpg –list-keys查詢一下私鑰對應的公鑰是哪個  (因為是公鑰,所以不怕公開)

公私鑰使用上的原理如下

加密者,以RamdonKey進行對稱式加密檔案,接著以 解密端(收件者)的 “公鑰” 將Random Key進行檔案加密,對方可以用自己的私鑰解密randomkey,進行檔案解密。其中加密者會在加密後,再用私鑰進行一次簽章,此簽章只能用加密者的公鑰進行驗簽,此驗證就是確保,是加密 者進行上述加密行為,無其他人篡改過。

Reference

https://blog.miniasp.com/post/2022/05/11/gnupg

https://xeodou.me/how-pgp-works/

演算法-常見的排序演算法與其平均時間複雜度

演算法-常見的排序演算法與其平均時間複雜度

氣泡排序法(Bubble Sort)

氣泡排序法的一個常見口訣是「相鄰比較,交換位置」。每個詞都代表了氣泡排序的一個關鍵步驟:

  1. 相鄰比較(Compare Adjacent):比較相鄰的兩個元素,並根據排序規則確定它們的順序。
  2. 交換位置(Swap):如果相鄰的兩個元素的順序不符合排序規則,則交換它們的位置。
  3. 重複上述步驟,對數列中的所有元素進行相鄰比較和位置交換,直到整個數列排序完成。

平均時間複雜度為: O(n²)

選擇排序法(Selection Sort)

常見口訣是「尋找最小,交換位置」。每個詞都代表了選擇排序的一個關鍵步驟

  1. 尋找最小(Find Minimum):從未排序部分的數列中尋找最小的元素。
  2. 交換位置(Swap):將找到的最小元素與未排序部分的第一個元素交換位置。
  3. 重複上述步驟,繼續尋找最小元素並進行交換,直到整個數列排序完成。

平均時間複雜度為: O(n²)

插入排序法(Insertion Sort)

插入排序法的一個常見口訣是「一一插入,保有順序」。每個詞都代表了插入排序的一個關鍵步驟:

  1. 一一插入(Insert One by One):從未排序部分的數列中逐一選取元素,並將其插入到已排序部分的正確位置。
  2. 保有順序(Maintain Order):在插入元素時,確保已排序部分的元素仍保持升序或降序的順序。
  3. 重複上述步驟,繼續逐一插入元素,直到整個數列排序完成。
    public static void InsertionSortAlgorithm(int[] arr)
    {
        int n = arr.Length;

        for (int i = 1; i < n; i++)
        {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = key;
        }
    }

平均時間複雜度為: O(n²)

合併排序法(Merge Sort)

合併排序法的一個常見口訣是「分而治之」。

合併排序的主要思想是通過分治的策略,將數列不斷分割成更小的部分,然後將這些部分按照順序合併起來,形成一個有序序列。合併排序具有穩定性和較好的時間複雜度,特別適用於處理較大規模的數列排序。

    public static void MergeSortAlgorithm(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int middle = (left + right) / 2;

            MergeSortAlgorithm(arr, left, middle);
            MergeSortAlgorithm(arr, middle + 1, right);

            Merge(arr, left, middle, right);
        }
    }

    private static void Merge(int[] arr, int left, int middle, int right)
    {
        int n1 = middle - left + 1;
        int n2 = right - middle;

        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        for (int i = 0; i < n1; i++)
        {
            leftArr[i] = arr[left + i];
        }

        for (int j = 0; j < n2; j++)
        {
            rightArr[j] = arr[middle + 1 + j];
        }

        int k = left;
        int p = 0;
        int q = 0;

        while (p < n1 && q < n2)
        {
            if (leftArr[p] <= rightArr[q])
            {
                arr[k] = leftArr[p];
                p++;
            }
            else
            {
                arr[k] = rightArr[q];
                q++;
            }

            k++;
        }

        while (p < n1)
        {
            arr[k] = leftArr[p];
            p++;
            k++;
        }

        while (q < n2)
        {
            arr[k] = rightArr[q];
            q++;
            k++;
        }
    }

平均時間複雜度為: O(n log n)

快速排序法(Quick Sort)

常見口訣是「選基、劃分、遞迴」。每個詞都代表了快速排序的一個關鍵步驟

  1. 選基(Choose Pivot):從數列中選擇一個基準點(pivot)。
  2. 劃分(Partition):將數列劃分為兩個部分,一部分是小於等於基準點的元素,另一部分是大於基準點的元素。
  3. 遞迴(Recursion):對劃分後的兩個部分進行遞迴排序,重複上述步驟,直到排序完成。
    public static void QuickSortAlgorithm(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int partitionIndex = Partition(arr, left, right);

            QuickSortAlgorithm(arr, left, partitionIndex - 1);
            QuickSortAlgorithm(arr, partitionIndex + 1, right);
        }
    }

    private static int Partition(int[] arr, int left, int right)
    {
        int pivot = arr[right];
        int i = left - 1;

        for (int j = left; j < right; j++)
        {
            if (arr[j] < pivot)
            {
                i++;
                Swap(arr, i, j);
            }
        }

        Swap(arr, i + 1, right);
        return i + 1;
    }

    private static void Swap(int[] arr, int i, int j)
    {
        (arr[i], arr[j]) = (arr[j], arr[i]);
    }

平均時間複雜度為: O(n log n)


其他少聽/用過的排序

希爾排序法(Shell Sort)

插入排序法的改良,幾乎所有狀況都能比O(n²)來得快

堆積排序法(Heap Sort)

平均時間複雜度為: O(n log n)

桶排序法(Bucket Sort)

非比較排序,平均時間複雜度為: O(n+k)

基數排序法(Radix Sort)

同屬非比較排序