素数：素数又称质数，指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。 互质数：公因数只有1的两个数，叫做互质数 模运算：两个整数a，b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余，记作: a ≡ b (mod m)；读作：a同余于b模m，或者，a与b关于模m同余。例如：26 ≡ 14 (mod 12)。 欧拉函数：在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。 模反元素：如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。这时，b就叫做a的"模反元素"。 1.找到两个的不同大素数p&q,N=p q。 2.根据欧拉函数得到 r=(p-1)(q-1) 3.选择一个小于r的整数e，求e关于模r的模反元素d。 4.销毁p，q。 这样就得到了公钥(N,e),私钥(N,d) 加密只需要公钥(N,e)，对于明文x进行如下运算 x^e ≡ c (mod N) 得到密文c。 解密只需要知道私钥(N,d),对于密文c进行如下运算 c^d ≡ x （mod N） 还原明文x。 用公钥和密文解密出明文，这建立在N可分解的基础上，我们可以通过pq得到秘钥。 # coding: utf-8 from Crypto.PublicKey import RSA import gmpy2 import codecs pub=RSA.importKey(open("/Users/a1tm4nz/Downloads/RSA/public.pem").read()) n=pub.n #n e=pub.e #e p=258631601377848992211685134376492365269 # 通过http://factordb.com/分解N q=286924040788547268861394901519826758027 #d=gmpy2.invert(e,(p-1)*(q-1)) d=23071769375111040425287244625328797615295772814180109366784249976498215494337 c=int(codecs.encode(open('/Users/a1tm4nz/Downloads/RSA/flag.enc','rb').read(),'hex_codec'),16) m=hex(pow(c,d,n))[2:].replace("L","") if(len(m)%2==1):#16进制解密要求密文不能为奇数，在头部填0即可 m='0'+m print m.decode('hex') 当N或e都很大时，我们可以使用wiener攻击 github上有利用脚本: https://github.com/pablocelayes/rsa-wiener-attack 南邮平台上的一道题 #coding:utf-8 from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_v1_5 as Cipher_pkcs1_v1_5 import base64 flag=raw_input('flag:') key=RSA.construct((1063045321283844468344531168992778520651192162100948533991539097447031440090068191835838938460807260866872379834796862916118785271062209281267667069640000501698142693389209275376843382863579650119977059768375028586326490055087394631528241983631462471709913758728591459476799115050977493979613545056736162868049L ...