2.2 公鑰密碼學
在密碼學中，公開密鑰密碼學，簡稱公鑰密碼學，又稱非對稱密碼學，是使用一對公鑰和私鑰的密碼學，與只用一個秘密密鑰的密碼學相對應。
2.2.1 公鑰加密算法原理與特點
在公鑰密碼出現前，幾乎所有的密碼體制都是基于替換和置換這些初等方法。輪轉機和DES是密碼學發展的重要標志，但還是基于替換和置換。公鑰密碼學與其之前的密碼學完全不同。首先，公鑰算法是基于數學函數而不是基于替換和置換，更重要的是公鑰密碼是非對稱的，它使用兩個獨立的密鑰。使用兩個密鑰在消息的保密性、密鑰分配和認證領域有著重要的意義。
1.公鑰加密算法的原理
用抽象的觀點來看，公鑰密碼就是一種陷門單向函數（trapdoor one-way function）。在公鑰密碼中，加密密鑰和解密密鑰是不一樣的，加密密鑰為公鑰，解密密鑰為私鑰。在公鑰密碼機制之中，破譯已經加密后的密碼應該是一個難解問題。一個問題是難解的，直觀上講，就是不存在一個計算該問題的有效算法，也可稱之為按照目前的計算能力，無法在一個相對的短時間內完成，即解決這個問題所付出的成本遠遠超過了解決之后得到的結果。計算一個難解的問題所需要的時間一般是以輸入數據長度的指數函數形式遞增的，所以隨著輸入數據的增多，復雜度會急劇增大。對于一個問題，如果存在一個求其解的有效算法，則稱其為有效問題，否則稱為無效問題。
公鑰密碼的理論基礎是陷門單向函數：設f是一個函數，如果對于任意給定的x，計算y=f(x)是容易的，但對于任意給定的y，計算f(x)=y是難解的，則稱f是一個單向函數。
另外，設f是一個函數，t是與f有關的一個參數，對任意給定的x，計算y使得y=f(x)是容易的。如果當不知道參數t時，計算f的逆函數是難解的，但當知道參數t時，計算f的逆函數是容易的，則稱f是一個陷門單向函數，參數t稱為陷門。
在公鑰密鑰中，加密變換是一個陷門單向函數，只有帶陷門的人可以容易地進行解密變換，而不知道陷門的人則無法有效地進行解密變換。
2.公鑰加密算法的特點
傳統對稱密碼存在的主要問題有兩個：一個是密鑰分配問題（加密之后，如何把密鑰告訴對方才是安全的？）；另一個是數字簽名問題，否則會出現抵賴和偽造。公鑰加密算法正好可以進行秘鑰交換和數字簽名。
通常對公鑰密碼有兩種誤解。
（1）認為公鑰密碼比傳統密碼更加安全。事實上，任何加密方法都依賴于密鑰的長度和破譯密文所需要的計算量，所以公鑰密碼并不比傳統密碼更加安全。
（2）認為公鑰密碼是一種通用密碼，傳統密碼已經過時了。其實正相反，由于現在公鑰密碼的計算量大，所以取消傳統密碼似乎不太可能，公鑰密碼的發明者也認為“公鑰密碼學僅用在密鑰管理和簽名這類應用上”。
2.2.2 公鑰加密算法舉例
常見的公鑰加密算法包括RSA、ElGamal、背包算法、Rabin（Rabin加密法是RSA方法的特例）、Diffie-Hellman（D-H）密鑰交換協議中的公鑰加密算法、Elliptic Curve Cryptography（ECC，橢圓曲線加密算法）等。
當前最著名、應用最廣泛的公鑰系統RSA是在1978年由美國麻省理工學院的Rivest、Shamir和Adleman提出的。RSA正是這三個人名的首字母。RSA是一個基于數論的非對稱密碼體制，是一種分組密碼體制。RSA算法是第一個既能用于數據加密也能用于數字簽名的算法。
RSA使用一個公鑰（public key）和一個私鑰（private key）。公鑰加密，私鑰解密，密鑰長度從40 bit到2048 bit可變，加密時也把明文分成塊，塊的大小可變，但不能超過密鑰的長度。RSA算法把每一塊明文轉化為與密鑰長度相同的密文塊。密鑰越長，加密效果越好，但加密和解密的開銷也大，所以要在安全與性能之間折中考慮，一般64位是較合適的。RSA的一個比較知名的應用是SSL[1]，在美國和加拿大，SSL用128位RSA算法，由于出口限制，在其他地區（包括中國）通用的則是40位版本。
RSA的安全性基本大于大整數的因子分解，其基礎是數論中的歐拉定理。因子分解可以破解RSA密碼系統，但是目前尚無人證明RSA的解密一定需要分解因子。
RSA密鑰生成過程如下。
（1）選擇一對不同的、足夠大的素數p、q。
（2）計算n=pq。
（3）計算f（n）=（p-1）（q-1），同時對p、q嚴格保密，不讓任何人知道。
（4）找一個與f（n）互質的數e，且1<e<f（n）。
（5）計算d，使得de≡1 mod f（n）。這個公式也可以表達為d≡e-1 mod f（n）。
（6）公鑰PU=（e,n），私鑰PR=（d,n）。
（7）加密時，先將明文變換成0至n-1的一個整數M。若明文較長，可先分割成適當的組，然后再進行交換。設密文為C，則加密過程為C=Me（mod n）。
（8）解密過程為M=Cd（mod n）。
在RSA密碼應用中，公鑰PU是公開的，即e和n的數值可以被第三方竊聽者得到。破解RSA密碼的問題就是從已知的e和n的數值，求出d的數值，這樣就可以得到私鑰來破解密文。密碼破解的實質問題是：只要求出p和q的值，就能求出d的值，從而得到私鑰。
一個RSA算法加密和解密的例子如下。
加密生成密文：
比如甲向乙發送漢字“中”，就要使用乙的公鑰來加密漢字“中”，以UTF-8方式編碼為［e4 b8 ad］，轉為十進制為［228, 184, 173］。要想使用公鑰(n,e)=(4757,101)加密，要求被加密的數字必須小于n，被加密的數字必須是整數，字符串可以取ASCII值或Unicode值，因此將“中”字拆為三個字節［228, 184, 173］，分別對三個字節加密。
假設a為明文，b為密文，則按下列公式計算出b
ae mod n=b
計算［228, 184, 173］的密文：
228101 mod 4757 = 4296
184101 mod 4757 = 2458
173101 mod 4757 = 3263
即［228, 184, 173］加密后得到密文［4296, 2458, 3263］，如果沒有私鑰d，很難從［4296, 2458, 3263］中恢復［228, 184, 173］。
解密得到密文：
乙收到密文［4296, 2458, 3263］，并用自己的私鑰（n,d）=（4757,1601）解密。解密公式如下：
ad mod n=b
密文［4296, 2458, 3263］的明文如下：
42961601 mod 4757 = 228
24581601 mod 4757 = 184
32631601 mod 4757 = 173
即密文［4296, 2458, 3263］解密后得到［228, 184, 173］，將［228, 184, 173］再按UTF-8解碼為漢字“中”，至此解密完畢。