RSA是一種非對稱加密算法，它由 公鑰（n/e），私鑰(n/d)，明文M和密文C組成。我們做CTF題目時，一般題目中會給出公鑰和密文讓我們推出對應(yīng)的私鑰或者明文。RSA的相關(guān)公式都寫在上面腦圖中，在正式講解RSA加密算法前我們先來普及一波數(shù)學(xué)的基本知識。

一、相關(guān)數(shù)學(xué)基礎(chǔ)

1.1素數(shù)和互質(zhì)數(shù)

素數(shù)也稱質(zhì)數(shù)，它的定義為除本身和 1 的乘積外，不能表示其他數(shù)的乘積。比如2，3，5，7，11，13，17……等都是素數(shù)。
互素數(shù)也稱互質(zhì)數(shù)，定義是公約數(shù)只有1的兩個自然數(shù)，如：
1和任何自然數(shù) 1 & 2
任意 2個質(zhì)數(shù) 2 & 3
相鄰2個自然數(shù) 4 & 5
3 & 10 、7 & 10 、5 & 26等等

1.2模指數(shù)運算

模運算就是取余數(shù)，如5 mod 3 =2。而模指數(shù)就是，先做指數(shù)運算在做mod運算。
如：53 mod 7 = 125 mod 7 =6
我們可以使用python的pow()來求解模指數(shù)運算。

1.3同余運算

兩個整數(shù)a,b，它們除以整數(shù)M所得的余數(shù)相等：a ≡ b(mod m)，比如說5除3余數(shù)為2，11除3余數(shù)也為2，于是可寫成11 ≡ 5(mod 3)。

二、RSA加密算法

2.1 加解密算法

前面已經(jīng)說過，RSA是一種非對稱加密算法，這個算法的特點就是明文使用公鑰進(jìn)行加密得到密文，而密文解密使用私鑰來解。

所需的密鑰對為n,d,e。密鑰對是如何生成的？

2.2生成密鑰對

密鑰對的生成步驟如下：n ? L?e?d （L作為生成過程中的中間數(shù)）

cc

收藏 海報分享