源自于密码学的一次大作业~
RSA破解
Alice使用的RSA密码体制，有以下事项需要说明：
1） 模数=规模为1024比特，其中，为素数；
2）每次加密最多8个明文字符；
3） 明文超过8个字符时，对明文分片，每个分片不超过8个字符；
4） 分片明文填充为512比特消息后再进行加密，填充规则为高位添加64比特标志位，随后加上32比特通信序号，再添加若干个0，最后64比特为明文分片字符对应的ASCII码（注：填充方式参见加密案例，但注意每次通信的标志位可能变化）；
5)分片加密后发送一个加密帧数据，帧数据文件名称为FrameXX，其中XX表示接收序号，该序号不一定等于通信序号；
6） 帧数据的数据格式如下，其中数据都是16进制表示，结构如下
1024bit模数N|1024bit加密指数e|1024bit密文。
7） 由于Alice初次使用该软件，可能会重复发送某一明文分片。
请您尝试恢复每个帧数据的p和q，以及明文M
输入：若干帧文件
文件的格式： 1024bit模数 N | 1024bit加密指数 e | 服务器托管网1024bit密文
一、低指数攻击——中国剩余定理
题目
给定五个密文，存在五个文件中，这5个密文（都是16进制）是同一明文m用RSA算法模不同N得到的，加密指数e=5(即公钥为5)，每个密文的格式： 1024bit模数 N | 1024bit加密指数 e | 1024bit密文。请利用中国剩余定理恢复明文m (求解5个同余方程的同余方程组)
from mpmath import mp
import gmpy2
import functools
def chinese_remainder_theorem(n, a):
# n 是模数列表，a 是同余方程组的余数列表
# 求模数的积
N = functools.reduce(gmpy2.mul, n) # 使用 functools.reduce 计算乘积
# 求每个模数 Ni 和 Ni 在模数 n 中的商 si 和余数 ti
x = 0
for ni, ai in zip(n, a):
si = N // ni
ti = gmpy2.invert(si, ni)
xi = gmpy2.mul(gmpy2.mul(si, ti), ai) # 分别计算 si * ti 和结果再与 ai 相乘
x = gmpy2.add(x, xi)
# 将 x 转化为模数为 N 的余数，作为最小非负整数解
return x % N
# 示例输入
a = []
n = []
f=[]
f.append(r'file1')
f.append(r'file2')
f.append(r'file3')
f.append(r'file4')
f.append(r'file5')
for file_path in f:
# 读取数据
with open(file_path, 'r') as f:
data = f.read().strip()
# 解析数据
hex_length = len(data) // 3
N = int(data[:hex_length], 16)
e = int(data[hex_length:2*hex_length], 16)
ct = int(data[2*hex_length:], 16)
# 打印数据
# print(f"Modulus N: {N}\n")
# print(f"Public exponent e: {e}\n")
# print(f"Ciphertext: {ct}\n")
n.append(N)
a.append(ct)
mp.dps=1000
nn = [gmpy2.mpz(i) for i in n] # 模数列表
aa = [gmpy2.mpz(i) for i in a] # 同余方程组的余数列表
m = chinese_remainder_theorem(n, a)
res,exa=gmpy2.iroot(gmpy2.mpz(m),5)
def parse_8_pairs_16_bytes(s):
# 将字符串截取为最后 16 个字节
bytes_16 = s[-16:]
# 定义一个空列表，用于保存解析出的字符对
pairs = []
# 分组解析每两个字节
for i in range(0, 16, 2):
byte1, byte2 = bytes_16[i], bytes_16[i + 1]
char1 = chr(int(byte1 + byte2, 16))
pairs.append((char1,))
# 将所有字符对连接起来，并返回字符串
return ''.join(char for pair in pairs for char in pair)
print(hex(res))
print(parse_8_pairs_16_bytes(hex(res)))
二、费马分解
摘自 RSA-p和q挨得很近(费马分解)_rsa费马分解_爱码蔡蔡子的博客-CSDN博客
1.p,q为邻居素数
p，q是两个素数，而且他俩在素数序列里面就是一前一后的关系。所以我们要把他俩的乘积开根号得到的结果一定是在p，q之间的一个数字，（而且一定不是素数，因为p，q就是紧邻的两个素数）。那我们找这个开方出来的数字的下一个素数，一定是q，因此我们再让n/q就可以得到两个素数
示例：
'''生成两个挨得近的素数p，q'''
p = getPrime(512)
q = gmpy2.next_prime(p)
n=p*q
print(p)
print(q)
print(n)
'''开始破解'''
# gmpy2的iroot函数，这个函数专门用来进行大数开根号，gmpy2.iroot(n,t)。
# n是大整数，t是幂次。
temp=gmpy2.iroot(n,2)[0]
p=gmpy2.next_prime(temp)
q=n//p
print(p)
print(q)
2.平方差遍历法
令a是n的”中间值”sqrt(n),然后让a以步长为1自增遍历，直到pow(a,2)-n的结果可以正好开方为止。那个结果开方就是b。
$$ p=a-b;q=a+b;n=pq=a^2-b^2 $$
$$ b^2=a^2-n $$
因此，可以令a的初始值为sqrt(n)，不断增大a直至满足上述条件即可
示例：
'''生成两个挨得近的素数p，q'''
p = getPrime(512)
q = gmpy2.next_prime(p)
n=p*q
print(p)
print(q)
print(n)
print('开始破解')
'''开始破解'''
a=gmpy2.iroot(n,2)[0]
while 1: #破解出来一组就行了，一般也就一组，挨得很近的话很快就出来了，如果长时间还没出来就可以换方法了，不要指望着他遍历所有的，到死也弄不完。
B2=pow(a,2)-n
a+=1
if gmpy2.is_square(B2):
b=gmpy2.iroot(B2,2)[0]
p=a+b
q=a-b
print(p)
print(q)
break
题目
给定密文的格式： 1024bit模数 N | 1024bit加密指数 e | 1024bit密文。已知密文产生的RSA算法中的pq很接近
import gmpy2
import gmpy2
def fermat_factorization(n):
a = gmpy2.isqrt(n) + 1 # 取 n 的平方根并向上取整
b2 = a * a - n
while not gmpy2.is_square(b2):
# 迭代计算直到 b2 是一个完全平方数
a += 1
b2 = a * a - n
p = a + gmpy2.isqrt(b2)
q = a - gmpy2.isqrt(b2)
return p, q
f=[]
f.append(r'file1')
f.append(r'file2')
for file_path in f:
# 读取数据
with open(file_path, 'r') as f:
data = f.read().strip()
# 解析数据
hex_length = len(data) // 3
n = gmpy2.mpz(int(data[:hex_length], 16))
e = int(data[hex_length:2*hex_length], 16)
ct = int(data[2*hex_length:], 16)
# # 打印数据
# print(f"================================\nModulus N: {n}\n")
# print(f"Public exponent e: {e}\n")
# print(f"Ciphertext: {ct}\n")
# input()
p, q = fermat_factorization(n)
if p is None or q is None:
print("无法分解质因数")
else:
print("质因数分解结果:")
print("p =", p)
print("q =", q)
d=gmpy2.invert(e,(q-1)*(p-1))
m=gmpy2.powmod(ct,d,n)
def parse_8_pairs_16_bytes(s):
# 将字符串截取为最后 16 个字节
bytes_16 = s[-16:]
# 定义一个空列表，用于保存解析出的字符对
pairs = []
# 分组解析每两个字节
for i in range(0, 16, 2):
byte1, byte2 = bytes_16[i], bytes_16[i + 1]
char1 = chr(int(byte1 + byte2, 16))
pairs.append((char1,))
# 将所有字符对连接起来，并返回字符串
return ''.join(char for pair in pairs for char in pair)
print(hex(m))
print(parse_8_pairs_16_bytes(hex(m)))
三、共模攻击
【密码学RSA】共模攻击原理详解_已知e1*e2的共模攻击题_rsa共模攻击原理-CSDN博客
RSA共模攻击(包括原理)-CSDN博客
共模是指：就是明文m,相同。用两个公钥e1,e2加密得到两个私钥d1,d2 和两个密文c1,c2
共模攻击，即当m不变的情况下，知道n,e1,e2,c1,c2, 可以在不知道d1,d2的情况下，解出m
利用条件为=> gcd(e1,e2)=1
def hack(n, c1, c2, e1, e2):
def egcd(a, b):
if b == 0:
return a, 0
else:
x, y = egcd(b, a % b)
return y, x - (a // b) * y
s = egcd(e1, e2)
s1 = s[0]
s2 = s[1]
# 求模反元素
if s1
from gmpy2 import invert
def hack(n, c1, c2, e1, e2):
def egcd(a, b):
if b == 0:
return a, 0
else:
x, y = egcd(b, a % b)
return y, x - (a // b) * y
s = egcd(e1服务器托管网, e2)
s1 = s[0]
s2 = s[1]
# 求模反元素
if s1 四、rho、rho p-1分解pq
【快速因数分解】Pollard’s Rho 算法 – Koshkaaa (cnblogs.com)
import gmpy2
from gmpy2 import mpz
import random
import time
# Rho算法
def rho(n, timeout=3):
if n % 2 == 0:
return 2
start_time = time.time()
while True:
if time.time() - start_time > timeout: # 超时处理,替换判环
return None
x, y, c, d = random.randint(1, n-1), random.randint(1, n-1), random.randint(1, n-1), 1
f = lambda x: (x * x + c) % n
while d == 1:
x = f(x)
y = f(f(y))
d = gmpy2.gcd(abs(x-y), n)
if d != n:
return d
f=[]
f.append(r'file1')
f.append(r'file2')
for file_path in f:
# 读取数据
with open(file_path, 'r') as f:
data = f.read().strip()
# 解析数据
hex_length = len(data) // 3
n = int(data[:hex_length], 16)
e = int(data[hex_length:2*hex_length], 16)
ct = int(data[2*hex_length:], 16)
p = rho(n)
while p is None: # 超时，重新选择随机数
p = rho(n)
q=n//p
d=gmpy2.invert(e,(q-1)*(p-1))
m=gmpy2.powmod(ct,d,n)
def parse_8_pairs_16_bytes(s):
# 将字符串截取为最后 16 个字节
bytes_16 = s[-16:]
# 定义一个空列表，用于保存解析出的字符对
pairs = []
# 分组解析每两个字节
for i in range(0, 16, 2):
byte1, byte2 = bytes_16[i], bytes_16[i + 1]
char1 = chr(int(byte1 + byte2, 16))
pairs.append((char1,))
# 将所有字符对连接起来，并返回字符串
return ''.join(char for pair in pairs for char in pair)
print(hex(m))
print(parse_8_pairs_16_bytes(hex(m)))
# rho p-1
import math
import random
import time
import gmpy2
def rho_pminus1(n, B, timeout=10):
a = 2
start_time = time.time()
# 计算 a^q-1
for q in range(2, B+1):
if (time.time() - start_time) > timeout: # 超时处理,替换判环
return None
a = pow(a, q, n)
# 计算 a^q-1 和 n 的最大公约数
d = math.gcd(a - 1, n)
if d > 1 and d 1:
p = rho_pminus1(n, B, timeout)
if p is None:
factors.append(n) # 无法找到质因数，将n作为一个质因数
break
else:
factors.append(p)
n //= p
return factors
# 指数的范围B和超时时间
B = 100000
timeout = 10
# 读取数据
with open(r'file1', 'r') as f:
data = f.read().strip()
# 解析数据
hex_length = len(data) // 3
n = int(data[:hex_length], 16)
e = int(data[hex_length:2*hex_length], 16)
ct = int(data[2*hex_length:], 16)
# 分解非常大的数
factors = factorize_large_number(n, B, timeout)
p,q=factors
d=gmpy2.invert(e,(q-1)*(p-1))
m=gmpy2.powmod(ct,d,n)
def parse_8_pairs_16_bytes(s):
# 将字符串截取为最后 16 个字节
bytes_16 = s[-16:]
# 定义一个空列表，用于保存解析出的字符对
pairs = []
# 分组解析每两个字节
for i in range(0, 16, 2):
byte1, byte2 = bytes_16[i], bytes_16[i + 1]
char1 = chr(int(byte1 + byte2, 16))
pairs.append((char1,))
# 将所有字符对连接起来，并返回字符串
return ''.join(char for pair in pairs for char in pair)
print(hex(m))
print(parse_8_pairs_16_bytes(hex(m)))
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
