簡介

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

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

使用方法：

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

數論基礎

歐拉函數

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

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

歐拉函數的原理這里就不介紹了，只需要知道素數的歐拉函數等于它-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}modN$$

也就是$c=m^{e}modN$,m為明文，c為密文

解密

$$明文=密{文}^{d}modN$$

也就是$m=c^{d}modN$

RSA解密的正確性證明

總結

以上是生活随笔為你收集整理的RSA加密过程详解 | 公钥加密| 密码学| 信息安全的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。