我是悟出一个道理了，搞安全的逃不过各种密码算法，密码学一定要给我捡起来！！本来想在这里上传我的密码学笔记的，但是图片太多不想搞，放在CSDN博客也有一些兼容性问题。

1. 算法描述

（此处暴力摘抄百度百科）

RSA算法的具体描述如下：
（1）任意选取两个不同的大素数p和q计算乘积

$n=pq,\ \phi(n)=(p-1)(q-1)$

（2）任意选取一个大整数e，满足，整数e用做加密钥（注意：e的选取是很容易的，例如，所有大于p和q的素数都可用，通常取65537）；

（3）确定的解密钥d，满足，即是一个任意的整数；所以，若知道e和，则很容易计算出d；

（4）公开整数n和e，秘密保存d；

（5）将明文m（m<n是一个整数）加密成密文c，加密算法为

$c = Enc(m)=m^e\mod n$

（6）将密文c解密为明文m，解密算法为

$m = Dec(c) = c^d\mod n$

然而只根据n和e（注意：不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。总之，RSA总离不开n、e、d、p、q五个数。(n,e)组成公钥，d为私钥。

五个数之间的关系：

p和q：大整数n的两个因子（factor）
n：大整数n，我们称之为模数（modulus）
e和d：互为模反数的两个指数（exponent）

2. 算法攻击

2.1 模数分解

解决RSA题目最简单，最暴力，最好使的方法就是分解模数n。如果能够将n分解，成功得到p，q的取值，那么可求。

那么如何分解模数呢？这里有几种方法。

2.1.1 直接分解

利用 http://factordb.com/ 直接分解模数n，但这种方法只适用于n比较小的情况(512bit-768bit以内，即长度为64-96之间)，其实也有特殊情况，我就成功分解过一个长度为511的大整数。

2.1.2 利用公约数

如果在两次公钥的加密过程中使用的和具有相同的e，那么可以利用欧几里得算法直接将和分解。

通过欧几里得算法可以直接求出和的最大公约数p：

可以得出：，

def gcd(a, b):
   if a < b:
     a, b = b, a
   while b != 0:
     temp = a % b
     a = b
     b = temp
   return a

if __name__ == '__main__':
    n1 = input("n1:")
    n2 = input("n2:")
    p = gcd(n1, n2)
    print (p)
    q1 = n1 // p
    print (q1)

2.1.3 yafu分解

在p，q的取值差异过大，或者p，q的取值过于相近的时候，Format方法与Pollard rho方法都可以很快将n分解成功。

此类分解方法有一个开源项目yafu将其自动化实现了，不论n的大小，只要p和q存在相差过大或者过近时，都可以通过yafu很快地分解成功。(我怎么知道p、q相差大不大，相不相近，反正如果上面两种方法都不行，就可以试试这种方法)

1	用法：factor(n)

D:\CTF\tools\yafu-1.34>yafu-x64.exe
factor(23333333333333)


fac: factoring 23333333333333
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
Total factoring time = 0.0050 seconds


***factors found***

P2 = 31
P12 = 752688172043

ans = 1

2.1.4 成功分解模数后

成功求出p、q的值后就可以用脚本进行解密求得私钥d了。

import gmpy2
n = 103461035900816914121390101299049044413950405173712170434161686539878160984549
p = 282164587459512124844245113950593348271
q = 366669102002966856876605669837014229419
e = 65537

d = gmpy2.invert(e,(p-1)*(q-1))
print ("d = " + str(d))
#d为私钥
c = 0xad939ff59f6e70bcbfad406f2494993757eee98b91bc244184a377520d06fc35
m = gmpy2.powmod(c,d,n)
print("m = " + str(m))
'''
d = 91646299298871237857836940212608056141193465208586711901499120163393577626813
m = 185534734614696481020381637136165435809958101675798337848243069
'''

2.2 低加密指数分解

当e=3时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文三次开方，即可得到明文。

在中m是要求的，e，n，c已知，需要爆破n。在开e次方得到整数的时候这时候的k和m是需要的值。

#!/usr/bin/python
# coding=utf-8
import gmpy
from Crypto.PublicKey import RSA


def calc(j):

    a, b = gmpy.root(cipher + j * N, 3)
    if b > 0:
        m = a
        print '{:x}'.format(int(m)).decode('hex')
        # pool.terminate()

# 读入公钥
with open('pubkey.pem', 'r') as f:
    key = RSA.importKey(f)
    N = key.n
    e = key.e

# 读入密文
with open('flag.enc', 'r') as f:
    cipher = f.read().encode('hex')
    cipher = int(cipher, 16)

# 暴力破解
inputs = range(0, 118720000)
result = []
map(calc, inputs)
print len(result)

除了低加密指数攻击，还有低解密指数攻击，也就是密钥d比较小的情况，密钥d小意味着e很大，所以e很大的可以用低解密指数攻击。

低解密指数攻击工具：https://github.com/pablocelayes/rsa-wiener-attack

将整个文件打包解压放在主机，这里要将破解脚本放在rsa-wiener-attack目录下，否则导入包时会发生错误。

#python2
import hashlib
import RSAwienerHacker
N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
d =  RSAwienerHacker.hack_RSA(e,N)
print(d)
flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}"
print(flag)
#8920758995414587152829426558580025657357328745839747693739591820283538307445
#flag{47bf28da384590448e0b0d23909a25a4}

python3环境下会报编码错误，是因为python3里hex(d)的结果和python2里hex(d)的结果相差了一个末尾的L，所以再计算md5的结果也就不一样，可以手动加上L再放到md5函数里面。

1	print(hashlib.md5(b'0x13b8f87d588e2aa4a27296cf2898f56ab4c8deb5a1222ec080e23afecaf7f975L').hexdigest())

2.3 共模攻击

如果在RSA加密中使用了不同的e而使用了相同的n对相同的明文m进行加密，那么就可以在不分解n的情况下还原出明文m的值，其中和互素。

$c_1=m^{e_1}\mod n$ $c_2=m^{e_2}\mod n$

证明：

因为，即存在使得：

$s_1*e_1+s_2*e_2=1$

又因为：

$c_1= m^{e_1}\mod n$ $c_2= m^{e_2} \mod n$

通过代入化简可以得出：

$c_1^{s_1}*c_2^{s_2}= m \mod n$

#coding=utf-8
#python2
import gmpy2
from libnum import n2s,s2n
n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L
e1 = 17
e2 = 65537
fo1 = open("flag.enc1",'rb')
fo2 = open("flag.enc2","rb")

datafo1 = fo1.read()
message1 = s2n(datafo1)
fo1.close()
datafo2 = fo2.read()
message2 = s2n(datafo2)

gcd,s,t = gmpy2.gcdext(e1,e2)
print (message1)
print (gcd,s,t)


#s和t一定有一个位负数，若s<0,求a^s <=> (1/a)^(-s)

plain = gmpy2.powmod(message1, s, n) * gmpy2.powmod(message2, t, n) % n

print (plain)

print (n2s(plain))

#gcdext(...) gcdext(a, b) returns a 3-element tuple (g, s, t) such that
#g == gcd(a, b) and g == a * s + b * t


#invert(...) invert(x, m) returns y such that x * y == 1 modulo m, or 0 if no such y exists.