摘要
1. 实验要求
现有一个RSA加解密软件，给出了它的算法描述和可以被截获的数据，要利用对RSA的多种攻击方式，从加密数据中恢复通关密语及RSA体制参数。
2. 实验目的
在对RSA的破解实战中，深入体会RSA的参数选取和加解密过程，加深对公共模数攻击、Pollard攻击、低加密指数攻击、因数碰撞攻击等常见攻击方法的理解。
题目描述
现有一个RSA加解密软件，每次最多加密8个明文字符，超过8则要分片。分片明文要按指定规则填充，在填充过程中需要加入通信序号。我们可以截获加密数据帧，数据帧包括模数N、加密指数e和密文c。我们要仅利用加密数据恢复出明文和RSA体制系数。
Alice发送了21个加密数据帧，但有的明文分片被重复加密，有的参数选取不当，我们可以针对这些缺陷进行攻击。
过程
1. 数据提取
先从数据帧中提取出模数N，加密指数e和密文c。
N_list = []
c_list = []
e_list = []
for i in range(21):
with open("frame_set/Frame" + str(i), "r") as f:
tmp = f.read()
N_list.append(tmp[0:256])
e_list.append(tmp[256:512])
c_list.append(tmp[512:768])可以看到加密指数e的取值有以下几种
当e较小时，存在广播攻击，经过尝试，发现当e=5的时候存在广播攻击，对应的帧为Frame3，Frame8，Frame12，Frame16和Frame20。
2. 广播攻击
原理如下
在RSA中e被称为加密指数。由于e是可以随意选取的，选取小一点的e可以缩短加密时间，但是如果选取不当，就会带来安全问题。
代码如下
def chinese_remainder_theorem(items):
N = 1
for a, n in items:
N *= n
result = 0
for a, n in items:
m = N // n
d, r, s = gcd(n, m)
if d != 1:
N = N // n
continue
result += a * s * m
return result % N, N
def small_e_5():
sessions = [{"c": int(c_list[3], 16), "n": int(N_list[3], 16)},
{"c": int(c_list[8], 16), "n": int(N_list[8], 16)},
{"c": int(c_list[12], 16), "n": int(N_list[12], 16)},
{"c": int(c_list[16], 16), "n": int(N_list[16], 16)},
{"c": int(c_list[20], 16), "n": int(N_list[20], 16)}]
data = []
for session in sessions:
data = data + [(session['c'], session['n'])]
x, y = chinese_remainder_theorem(data)
# 直接开五次方根
plaintext3_8_12_16_20 = gmpy2.iroot(gmpy2.mpz(x), 5)
return binascii.a2b_hex(hex(plaintext3_8_12_16_20[0])[2:])结果为
3. 公共模数攻击
进一步分析，发现Frame0和Frame4的模数N相同，根据题意我们假设它们是对同一明文分片的重复加密。
原理如下
代码如下
# 公共模数攻击
def same_modulus():
# 寻找公共模数
index1 = 0
index2 = 0
for i in range(21):
for j in range(i + 1, 21):
if N_list[i] == N_list[j]:
print('Same modulus found!' + str((N_list[i], N_list[j])))
index1, index2 = i, j
e1 = int(e_list[index1], 16)
e2 = int(e_list[index2], 16)
n = int(N_list[index1], 16)
c1 = int(c_list[index1], 16)
c2 = int(c_list[index2], 16)
s = gcd(e1, e2)
s1 = s[1]
s2 = s[2]
# 求模反元素
if s1 < 0:
s1 = - s1
c1 = gmpy2.invert(c1, n)
elif s2 < 0:
s2 = - s2
c2 = gmpy2.invert(c2, n)
m = pow(c1, s1, n) * pow(c2, s2, n) % n
print(m)
print(binascii.a2b_hex(hex(m)[2:]))
result = binascii.a2b_hex(hex(m)[2:])
return result结果为
4. 因数碰撞攻击
之后剩余的均是e=65537的数据帧，要安全很多。继续分析模数N。
在不同的加密过程中，选择的p，q不能一样，否则利用最大公约数可以轻易分解n。在这里Frame1和Frame18的模数N具有公共因子，可以通过因数碰撞法恢复明文。
代码如下
def same_factor():
plaintext = []
index = []
for i in range(21):
for j in range(i + 1, 21):
if int(N_list[i], 16) == int(N_list[j], 16):
continue
prime = gmpy2.gcd(int(N_list[i], 16), int(N_list[j], 16))
if prime != 1:
print((N_list[i], N_list[j]))
print((i, j))
index.append(i)
index.append(j)
p_of_frame = prime
q_of_frame1 = int(N_list[index[0]], 16) // p_of_frame
q_of_frame18 = int(N_list[index[1]], 16) // p_of_frame
print(p_of_frame)
print(q_of_frame1, q_of_frame18)
phi_of_frame1 = (p_of_frame - 1) * (q_of_frame1 - 1)
phi_of_frame18 = (p_of_frame - 1) * (q_of_frame18 - 1)
d_of_frame1 = gmpy2.invert(int(e_list[index[0]], 16), phi_of_frame1)
d_of_frame18 = gmpy2.invert(int(e_list[index[1]], 16), phi_of_frame18)
plaintext_of_frame1 = gmpy2.powmod(int(c_list[index[0]], 16), d_of_frame1, int(N_list[index[0]], 16))
plaintext_of_frame18 = gmpy2.powmod(int(c_list[index[1]], 16), d_of_frame18, int(N_list[index[1]], 16))
final_plain_of_frame1 = binascii.a2b_hex(hex(plaintext_of_frame1)[2:])
final_plain_of_frame18 = binascii.a2b_hex(hex(plaintext_of_frame18)[2:])
plaintext.append(final_plain_of_frame1)
plaintext.append(final_plain_of_frame18)
return plaintext结果为
5. Fermat攻击
不仅仅是在加密过程中选择的p，q不能一样，还有p，q的取值不能相差太近或太大，否则利用Pollard p-1算法可以快速分解出p，q相差太大的n，利用Fermat算法可以快速分解p，q相差太近的n。
原理如下
代码如下
def pq(n):
B = math.factorial(2 ** 14)
u = 0;
v = 0;
i = 0
u0 = gmpy2.iroot(n, 2)[0] + 1
while (i <= (B - 1)):
u = (u0 + i) * (u0 + i) - n
if gmpy2.is_square(u):
v = gmpy2.isqrt(u)
break
i = i + 1
p = u0 + i + v
return p
def fermat_resolve():
for i in range(10, 14):
N = int(N_list[i], 16)
p = pq(N)
print(p)
def get_content_of_frame10():
p = 9686924917554805418937638872796017160525664579857640590160320300805115443578184985934338583303180178582009591634321755204008394655858254980766008932978699
n = int(N_list[10], 16)
c = int(c_list[10], 16)
e = int(e_list[10], 16)
q = n // p
phi_of_frame10 = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi_of_frame10)
m = gmpy2.powmod(c, d, n)
final_plain = binascii.a2b_hex(hex(m)[2:])
return final_plain结果为
6. Pollard p-1分解法
正如上文所说利用Pollard p-1算法可以快速分解出p，q相差太大的n。
原理如下
给定：整数n（已知是合数）
目标：找到一个因子d|n
步骤：
代码如下
def pp1(n):
B = 2 ** 20
a = 2
for i in range(2, B + 1):
a = pow(a, i, n)
d = gmpy2.gcd(a - 1, n)
if (d >= 2) and (d <= (n - 1)):
q = n // d
n = q * d
return d
def pollard_resolve():
index_list = [2, 6, 19]
plaintext = []
for i in range(3):
N = int(N_list[index_list[i]], 16)
c = int(c_list[index_list[i]], 16)
e = int(e_list[index_list[i]], 16)
p = pp1(N)
print("p of " + str(index_list[i]) + " is : " + str(p))
q = N // p
phi_of_frame = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi_of_frame)
m = gmpy2.powmod(c, d, N)
plaintext.append(binascii.a2b_hex(hex(m)[2:]))
return plaintext结果为
至此，还剩下几个数据帧没有恢复出明文。可以利用暴力破解，猜测攻击，字典攻击等手段解决。事实上这是一句名言，我们可以根据语言本身的意义得到通关密钥。
明文如下
"My secret is a famous saying of Albert Einstein. That is \"Logic will get you from A to B. Imagination will take you everywhere.\""
总结
在对RSA的破解实战中，深入体会了RSA的参数选取和加解密过程，加深了对公共模数攻击、Pollard攻击、低加密指数攻击、因数碰撞攻击等常见攻击方法的理解。认识到了即使是RSA也是有缺陷的，我们要严格选取RSA体制参数，提高安全性。
参考文献
【技术分享】CTF中RSA的常见攻击方法 - 安全客，安全资讯平台