RSA加密程序詳解 | 公鑰加密| 密碼學| 資訊安全

簡介

RSA加密演算法是一種非對稱加密演算法，所謂非對稱，就是指該演算法加密和解密使用不同的密鑰，即使用加密密鑰進行加密、解密密鑰進行解密，分別稱為公鑰和私鑰

在RAS演算法中，公鑰是公開的，而私鑰是需要保密的，加密演算法和解密演算法也都是公開的，雖然私鑰是由公鑰決定的，但由于無法計算出大數n的歐拉函式phi(N)，所以不能根據公鑰計算出私鑰，這就是RSA的安全性

使用方法：

• 乙方生成兩把密鑰(公鑰和私鑰)，公鑰是公開的，任何人都可以獲得，私鑰則是保密的，
• 甲方獲取乙方的公鑰，然后用它對資訊加密，
• 乙方得到加密后的資訊，用私鑰解密，

數論基礎

歐拉函式

φ(n)表示小于n且與n互素的正整數

• 對于素數來說，φ(n) = n - 1
• 對于不是素數的數來說，可以將n進行質因數分解，再套用 φ ( n ) = n ? ( 1 ? 1 p 1 ) ( 1 ? 1 p 2 ) . . . . . . ( 1 ? 1 p c ) φ(n)=n*(1-\frac{1}{p_1})(1-\frac{1}{p_2})......(1-\frac{1}{p_c}) φ(n)=n?(1?p1?1?)(1?p2?1?)......(1?pc?1?)

歐拉函式的原理這里就不介紹了，只需要知道素數的歐拉函式等于它-1即可

歐拉定理

a^φ(n) % n = 1

乘法逆元

(a*b)%n=1，就稱b是a在模n下的乘法逆元，求逆元的方法有兩種，如果n是素數，那利用費馬小定理可以知道逆元b = a ^n-1%n,如果不是素數，就只能用擴展歐幾里得計算了，這里就不展開

RSA演算法流程

密鑰的產生

• 取兩個保密的大素數p和q
• 計算n = p * q, n的歐拉函式值為φ(n) = (p - 1) * (q - 1)
• 任取一個整數 e， 1<e<n，且與φ(n)互素
• 計算e在模φ(n)意義下的乘法逆元
• 公鑰為(e, n), 私鑰為(d, n)

加密

密 文 = 明 文 e m o d N 密文=明文^emodN 密文=明文emodN

也就是 c = m e m o d N c = m^emodN c=memodN,m為明文，c為密文

解密

明 文 = 密 文 d m o d N 明文 = 密文^{d}modN 明文=密文dmodN

也就是 m = c d m o d N m = c^dmodN m=cdmodN

RSA解密的正確性證明