公鑰密碼術是數學的一個越來越重要的領域，它構成了現代交流的基石。但是，由于此類系統的複雜性日益提高，即使開發人員和與此類系統進行互動的人員也常常不了解其數學和内部工作原理，而是依賴于進階抽象和預先存在的實作。由于實施自己的密碼算法存在固有的危險，是以這通常不是一件壞事。但是，如果您的目标是從頭開始了解這些系統并了解它們的共同缺點，那麼深入了解可能會非常有用。
RSA
RSA以其建立者Ron Rivest，Adi Shamir和Leonard Adleman的名字命名，是一種非對稱密碼系統，通過使用公鑰-私鑰對起作用。
在該系統中，希望接收消息的使用者生成公共密鑰和私有密鑰，這兩個密鑰分别用于加密和解密。公鑰由數字e和n組成，私鑰由數字d和n組成。
在此，n是模量，e是公共指數，d是私有指數。用于加密和解密消息m和相應密文c的算法使用稱為摸幂的技術，如下所示：
由于RSA是公共密鑰密碼系統，是以隻能使用相應的私有密鑰解密使用公共密鑰加密的消息。為了接收加密的消息，個人可以廣泛地共享和分發其公共密鑰，進而允許任何人對發送給他們的消息進行加密。但是，這些消息隻能由它們解密。
為滿足密碼定義，RSA遵循一緻性方程表示為：
這僅意味着，在使用公共密鑰（e，n）加密消息m之後，隻能使用相應的私有密鑰（d，n）對消息進行解密以恢複消息。這種工作方式的神奇之處在于非常仔細地生成了數字n，e和d，我将在稍後讨論。
另外，為了驗證數字消息來源的真實性，我們可以在消息中包含數字簽名。由于用公鑰加密的消息隻能用相應的私鑰解密，是以還認為用私鑰加密的消息隻能用相應的公鑰解密。是以，如果您可以使用某人的公共密鑰解密消息，則可以保證該消息是由擁有相應私鑰的人建立的。
執行此操作的典型方法是使用諸如SHA-512之類的加密哈希函數計算消息摘要，使用其私鑰對其進行加密，然後将其連接配接到要發送的密文中。
例如，如果愛麗絲想向鮑勃發送經過數字簽名的消息，則愛麗絲可以使用鮑勃的公鑰對消息進行加密，然後使用自己的私鑰對消息的哈希進行加密。
為了驗證此數字簽名，Bob可以使用他的私鑰解密消息，建立消息的哈希，使用Alice的公鑰解密簽名，然後将兩者進行比較以確定Alice是編寫消息的人。
現在忽略簽名，這是一個簡單的示例，其中包含一些預先計算的值。假設我們要使用公共密鑰（其中e = 17和n = 3233）加密數字42。（請注意，這些數字出于示範目的非常小，而實際上卻大得多）。
此操作的結果密文為數字2557。現在，我們可以使用相應的私鑰（d = 2753和n = 3233）解密此消息。
如所證明的，這使得RSA在大多數用例中都相當容易了解。但是，RSA如何工作的魔力來自于公鑰和私鑰的生成方式，這往往變得更加複雜。
RSA密鑰生成
RSA安全性背後的主要思想之一是易于計算但在反向操作中不切實際的操作，例如模幂運算技術，在最佳實作中幾乎不可能進行反向操作。是以，取模幂可以視為Trapdoor函數。
如前所述，可以使用索引法将解密算法重寫如下：
由于e是公鑰的一部分，而d是私鑰的一部分，是以我們可以将e視為加密的指數，将d視為解密的指數。為了使該系統正常工作，我們必須找到滿足兩個非常重要條件的一對數字e和d。
- 提高密文（ç或米 ᵉ）到的功率d必須撤消施加給消息原始操作，導緻原始明文消息（米）。
- 僅通過知道e和n，就（實際上）不可能計算d。
為了滿足這些條件，我們可以轉向另一個稱為門函數。
作為活闆門功能，沒有已知的快速有效的方法來找到大量的主要因素。但是，将兩個質數相乘并找到結果是微不足道的。例如，以下問題很難手工計算：
14078417是兩個質數的乘積。這些數字是多少？
但是，稍微改一下這個問題可以使手動解決問題變得容易得多：
1801×7817是什麼？
請注意，在這種情況下，“ 14078417”是24位數字，是以計算機可以将其分解。但是，找到以下2048位數字的主要因素：
出于所有目的和目的，使用我們目前的方法将花費無限的時間。以目前的技術水準，我可能是唯一會知道上述數字的主要因素的人。
是以，我們可以通過找到依賴于大量素數的函數來将素數分解用作此算法中的活闆門函數。我們可以通過使用Euler totient函數來做到這一點。
表示為φ（n）的歐拉totient函數計算相對于n素數的正整數的數量。即，在範圍内的整數的數目1≤ ķ ≤ Ñ其中最大公約數GCD（Ñ，ķ）= 1。例如：
此處，φ（8）為4，因為8相對于1、3、5和7質數。另外，φ（9）為6，因為9與1、2、4、5、7和9相對質數。 9。
為了使此功能有用，我們可以檢視兩個非常重要的屬性：
- 如果n為質數，則φ（n）= n- 1，因為質數沒有大于1的因數。例如，φ（7）= 6，因為7與1、2、3、4、5和6互質數。這對于任何質數都成立。
2.歐拉的求生函數是可乘的，是以：
是以，我們可以結合這些屬性來得出一個函數，該函數隻能在給定數字素數的情況下進行計算。是以，如果我們有一個很大的數n，它等于兩個質數p和q的乘積，則：
這樣，我們現在有了φ（n）的活闆門函數，該函數隻有在您知道n的素因子時才可計算。現在，我們需要找到一種将totient函數與子產品化指數相連結的方法。為此，我們指出對于兩個數字m和n，如果n和m是互質的，則：
重新排列後，我們現在可以使用以下方程式求解d：
在該等式中，k可以代替使得d是自然數的值。另外，必須選擇e使其為奇數，并且不與φ（n）共享因數。這個方程式的最大優點是找到d，唯一使用的變量是n和e。但是，對于大數，在不知道n素數的情況下是不可能計算的。
使用我們收集的内容，我們可以非常簡單地生成RSA公鑰-私鑰對（e，n）和（d，n）。
- 生成兩個大的随機質數p和q（在RSA-2048中，p和q是1024位數字）
- 乘以p × q并将結果存儲為n。
- 将φ（n）計算為（p -1）（q -1）
- 選擇e的值，使e和φ（n）為互質，并且1 <e < φ（n）。
- 對某個值k計算d =（k × φ（n）+1）/ e，使d為自然值。