嵌入式基礎(chǔ)知識-RSA非對稱加密基本原理

之前的文章：嵌入式基礎(chǔ)知識-信息安全與加密，介紹過數(shù)據(jù)加密的一些基本概念，對稱加密的原理比較簡單，加密和解密的密鑰相同，而非對稱加密，兩個密鑰不同，本篇就來具體介紹RSA這種非對稱加密的密鑰計算原理。

1 RSA算法基本原理

RSA加密算法是由羅納德·李維斯特（Ronald Linn Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德爾曼（Leonard Adleman）于1977年共同發(fā)明的。它的密鑰計算規(guī)則可由下圖所示。

公鑰和私鑰的基本特點為：

公鑰和私鑰中都有兩個數(shù)字構(gòu)成，并且其中一個數(shù)字是相同的，即圖中所示的N，示例為33公鑰有自己特有的數(shù)字，即圖中所示的E，示例為3私鑰有自己特有的數(shù)字，即圖中所示的D，示例為7

公鑰加密的過程為（對明文中的每個字符分別解密，示例為加密其中一個字符）：

先對明文求E次冪再將結(jié)果對N取余

私鑰解密的過程與加密過程類似：

先對密文求D次冪再將結(jié)果對N取余

2 RSA密鑰計算規(guī)則

上面介紹了RSA加密解密的基本過程，那RSA的密鑰（公鑰和私鑰），怎么計算得到呢？

RSA的密鑰計算，需要用到質(zhì)數(shù)和歐拉函數(shù)的知識。

質(zhì)數(shù)的概念如果忘了，后面會再介紹。

歐拉函數(shù)暫不展開講解，記住公式即可。

下面就來看下RSA密鑰的計算步驟。

2.1 計算步驟

RSA密鑰（公鑰和私鑰）的計算步驟可分為如下五步：

第一步：取兩個質(zhì)數(shù)，如p=3，q=11

第二步：質(zhì)數(shù)相乘，N=pxq=3x11=33

第三步：歐拉函數(shù)，T=(p-1)x(q-1)=2x10=20

第四步：選公鑰E，需滿足以下條件：

可以從小開始選，選E=3，因此公鑰為(3, 33)

• • 是一個質(zhì)數(shù)1<公鑰<T不是T的因子

第五步，計算私鑰D，公式為**(DxE)%T=1**，解得D=7，因此私鑰為(7,33)

RSA密鑰的計算規(guī)則是公開的，那破譯的難點在哪里呢？

其實，在實際使用時，兩個質(zhì)數(shù)盡量取大，轉(zhuǎn)換成二進(jìn)制后1024個二進(jìn)制位或者更多，位數(shù)越多越難破解。

對于RSA的破解難度分析：

公鑰(E，N)是公開的，要想破解密鑰，就是求出D根據(jù)公式(DxE)%T=1，E是已知的，下一步就是要獲取到T，而T=(p-1)x(q-1)，與兩個質(zhì)數(shù)有關(guān)雖然N=pxq，N也是已知的，但如果這兩個質(zhì)數(shù)設(shè)置的非常大，N和T也就會很大而對于大數(shù)的質(zhì)數(shù)分解，是很難計算的，這就是RSA算法難破解的原理了

2.2 質(zhì)數(shù)簡介

上面說到，RSA密鑰的計算，需要用的質(zhì)數(shù)，那質(zhì)數(shù)的概念，是否還熟悉呢？

質(zhì)數(shù)是小學(xué)數(shù)學(xué)中就學(xué)過的知識點，不過平時用的不多，這里再簡單回顧以下。

質(zhì)數(shù)（也叫素數(shù)），指在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)的自然數(shù)。

質(zhì)數(shù)的一些性質(zhì)：

質(zhì)數(shù)p的約數(shù)只有兩個：1和p算術(shù)基本定理：任一大于1的自然數(shù)，要么本身是質(zhì)數(shù)，要么可以分解為幾個質(zhì)數(shù)之積，且這種分解是唯一的質(zhì)數(shù)的個數(shù)是無限的若n為正整數(shù)，在n^2到(n+1)^2之間至少有一個質(zhì)數(shù)若n為大于等于2的正整數(shù)，在n到n!之間至少有一個質(zhì)數(shù)

可以寫一段代碼，求取一定范圍的質(zhì)數(shù)，感受一下質(zhì)數(shù)有哪些。

代碼怎么寫呢？還是可以看下小學(xué)課本：

用Python編寫的打印5000以內(nèi)質(zhì)數(shù)的代碼如下：

#判斷是否是質(zhì)數(shù)：大于1，不等于2，是否為奇數(shù)，是否有約數(shù)'''
def isPrime(num):
    if num > 1:
        if num>2:
            if num%2==1:
                for i in range(2, int((num-1)/2)): 
                    if num%i == 0:
                        return False #有約數(shù)
                return True #無約數(shù)
            return False #3以上的偶數(shù)
        return True #等于2
    return False #小于2

if __name__ == '__main__':
    prime_list = []
    for i in range(5000):
        if isPrime(i):
            prime_list.append(i)
    print(prime_list)

這里列舉5000以內(nèi)的質(zhì)數(shù)：

3 RSA密鑰計算實例

題目：RSA算法中，選擇兩個質(zhì)數(shù)，p=11，q=17，加密密鑰為e=23，且求解密密鑰。

分析：按照RSA算法的基本原理，N=pxq=11x17=187，T=(p-1)x(q-1)=10x16=160，而E=23，

根據(jù)(DxE)%T=1，即(Dx23)%160=1，解得D=7

4 總結(jié)

本篇介紹了RSA這種非對稱加密算法的加密解密基本過程，以及公鑰和私鑰的計算基本步驟，并補(bǔ)充介紹了質(zhì)數(shù)的相關(guān)概念，最后通過一個實例來簡單體會下RSA密鑰的計算。