首先要向教我們信安數學基礎的老師道個歉，我記得當初碰到難題的時候抱怨過："真搞不懂學這個東西有什麼用？"
------現在看來，當時還是太年輕了哈哈哈。
RSA基礎
有基礎後還是好啊，基本定理随便掃一眼就行
------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------
來舉個例子
用python腳本解CTF中有關RSA的題目
上題
n=73069886771625642807435783661014062604264768481735145873508846925735521695159
c=28767758880940662779934612526152562406674613203406706867456395986985664083182
e=65537
思路
n=pq
phi =(p-1)(q-1)
ed=1 mod phi
公鑰：(n,e)
私鑰：(n,d)
用到的兩個子產品
import libnum
'''
libnum.n2s(n) 數字轉字元串(10進制和16進制)
libnum.s2n(s) 字元串轉數字(10進制和16進制)
libnum.b2s(s) 二進制數字轉字元串
libnum.s2b(s) 字元串轉二進制數字數字
libnum.generate_prime(n) 随機生成n位二進制内的質數
libnum.factorize(n) 因數分解，數字太大的話就很慢，下面附上線上分解大素數的位址
'''
線上分解大素數：
http://www.factordb.com/index.php?query=
import gmpy2
'''
gmpy2.invert(e,phi) 求模反元素d
pow(c,d,n) 求c^d mod n，也就是RSA解密結果
gmpy2.iroot(x,n) x開n次根
gmpy2.gcdext(a,b) 擴充歐幾裡得算法
gmpy2.gcd(a,b) 歐幾裡得算法，最大公約數
'''
解題代碼
import libnum
import gmpy2
# 題目資訊
c=28767758880940662779934612526152562406674613203406706867456395986985664083182
n=73069886771625642807435783661014062604264768481735145873508846925735521695159
e=65537
# 線上分解出p和q
p = 386123125371923651191219869811293586459
q = 189239861511125143212536989589123569301
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(libnum.n2s(m))