RSA加密基本原理
加密過程
選擇兩個大素數p和q，計算出模數N= p * q
計算φ= (p−1) * (q−1) 即N的歐拉函數，然後選擇一個e(1 取e的模反數為d，計算方法:e * d ≡ 1 (mod φ) 對明文A進行加密：B≡A^e(mod n) 或B= pow(A,e,n)，得到的B即為密文 對密文B進行解密，A≡B^d(mod n) 或A= pow(B,d,n)，得到的A即為明文 p 和q：大整數N的兩個因子（factor） N：大整數N，我們稱之為模數（modulus） e 和d：互為模反數的兩個指數（exponent） c 和m：分別是密文和明文，這裡一般指的是一個十進制的數 一般有如下稱呼： （N，e）：公鑰 （N，d）：私鑰 加密分析 RSA算法是一種非對稱密碼算法，所謂非對稱，就是指該算法需要一對密鑰，使用其中一個加密，則需要用另一個才能解密。 RSA的算法涉及三個參數，n、e、d。 其中，n是兩個大質數p、q的積，n以二進制表示時所佔用的位數，就是所謂的密鑰長度。 e和d是一對相關的值，e可以任意取，但要求e與(p-1)*(q-1)互質；再選擇d，要求(e*d)≡ 1(mod(p-1)×(q-1))。 令φ= (p-1)(q-1) 上式即 d*e= 1 mod φ 即：(d*e- 1)% φ = 0 （n，e),(n，d)就是密鑰對。其中(n，e)為公鑰，(n，d)為私鑰。RSA加解密的算法完全相同，設A為明文，B為密文，則：A≡B^d(mod n)；B≡A^e(mod n)；（公鑰加密體制中，一般用公鑰加密，私鑰解密） e和d可以互換使用，即： A≡B^e (modn)；B≡A^d(mod n); 附加解釋 同餘符號“ ≡ ” 數論中的重要概念。給定一個正整數m，如果兩個整數a和b滿足（a-b）能夠被m整除，即（a-b）/m得到一個整數，那麼就稱整數a與b對模m同餘，記作a≡b(modm)。對模m同餘是整數的一個等價關係
比如26≡14(mod12)
互質
公約數只有1的兩個數，稱為互質
RSA常見攻擊及分解方法
RSA的非對稱體制是建立在大整數分解難題上的，所以最基本的攻擊方法就是當模數N過小時，直接計算它的因子。但是大部分情況下稍微有點難度的rsa題目都不會是直接暴力分解N，而是需要一定的攻擊手法。
N如果是256bits可以直接分解，如果超過了就基本別想暴力分解了，需要用到下面的一些攻擊手法，下面列舉一下一些攻擊手法。
Wiener’sattack
當d < (1/3)N^(1/4)時，我們可以通過Wiener’sattack分解得到d
費馬分解
當大整數N的兩個因子p和q相近時，我們可以通過費馬分解的辦法很快分解大整數
Smallq
當q較小時，即|p-q|較大時，我們可以直接爆破因子
BonehDurfee Method
當d滿足d ≤ N^0.292時，我們可以利用該方法分解N，理論上比wienerattack要強一些。
yafu
yafu使用最強大的現代算法去自動化的分解輸入的整數。大多數的算法都實現了多線程，讓yafu能充分利用多核處理器（算法包括SNFS, GNFS,SIQS, 和ECM）。
factordb
如果對一個大整數用一些特殊算法也分解不了的時候，我們可以在 http://factordb.com/ 中查詢一下數據庫，說不定就能找到其因子
看完攻擊手法，我們拿例題來更好的認識一下攻擊手法。
mediumRSA
下載地址：
https://dn.jarvisoj.com/challengefiles/mediumRSA.rar.07aab25c9c54464a8c9821ca28503330
給出兩個文件：
flag.enc
pubkey.pem
可以看到一個公鑰，一個加密後的文件
正常分解的解決方法
openssl分解公鑰得到N、E
可以看到N(256bits)很短直接分解即可(幾分鐘之內)
python代碼生成私鑰
openssl 解密
RSActfTOOL
下載地址：
https://github.com/Ganapati/RsaCtfTool
可以用公鑰直接生成私鑰
私鑰解密：
低加密指數攻擊
Extremelyhard RSA
題目信息：沒想到RSA4096都被你給破了，一定是我的問題，給了你太多信息，這次我只給你一個flag的加密值和公鑰，仍然是RSA4096，我就不信你還能解出來。
題目鏈接：
https://dn.jarvisoj.com/challengefiles/extremelyhardRSA.rar.8782e822c895a2af3d8ba4ffbb3e280b
解題思路：openssl 解碼一下piblic.pem可以看到E=3（一般情況下E=0x10001），典型的低加密指數攻擊
注：flag.enc以十六進制方式來讀取，因為文件中含有很多不可打印字符。
破電腦跑了快半個小時，期間以為卡了，還好跑出來了&……
另一道ctf
正常e的值通常情況下是0x10001，上面這個e明顯值過小，而且是3，所以還是低加密指數攻擊
腳本如下：
共模攻擊
VeryHard RSA
題目鏈接：
https://www.jarvisoj.com/challenges
題目給出加密代碼如下：
注：N後面的L是為了強制編譯器把常量作為長整數來處理，只需在後邊加上一個字母L（或l）
首先看這個N長度（4096bit）就別想暴力分解了。
代碼可以看到是相同的N，不同的E加密的，那就使用共模攻擊
解密代碼如下：
rabin算法
hardRSA
題目鏈接：
https://www.jarvisoj.com/challenges
也是給了和上面一樣的兩個文件pubkey.pem和flag.enc
提取公鑰發現e=2，N與上面mediumrsa例題一樣，用rabin算法(該算法只適合e=2的情況)
N在上面已經用yafu分解出來p,q了，直接用就可以了。
python腳本如下：
閱讀更多 合天網安實驗室 的文章
