参考

低指数加密攻击（低指数广播攻击）_低加密指数广播攻击-CSDN博客

原理

1. 中国剩余定理 (CRT) 简述

给定一组同余方程：

$ x \equiv a_1 \pmod{m_1} $

$ x \equiv a_2 \pmod{m_2} $

$ \cdots $

$ x \equiv a_k \pmod{m_k} $

如果这些模数 $ m_i $ 两两互素（即 $ \gcd(m_i,m_j)=1 $），则存在唯一解 $ x $（模 $ M=m_1 m_2 \cdots m_k $）。

2. sympy.ntheory.modular.crt 用法

1
2
3
4
5
6
from sympy.ntheory.modular import crt

moduli = [m1, m2, m3]     # 模数列表
remainders = [a1, a2, a3] # 余数列表

x, M = crt(moduli, remainders)

返回值：

crt 的返回值是一个 二元组 (x, M)：

  • x：解出来的最小非负整数（满足所有同余条件）。
  • M：所有模数的乘积 $ m_1 m_2 \cdots m_k $。

这意味着，方程的通解是：

$ X \equiv x \pmod{M} $

$ 即X=x+k·M $

例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
from sympy.ntheory.modular import crt

# 模数（互不相同）
n1 = 10142789312725007
n2 = 10142789312725009
n3 = 10142789312725013
e = 3
m = 123456  # 明文

# 加密
c1 = pow(m, e, n1) #c1=1881640295202816
c2 = pow(m, e, n2) #c2=1881640295202816
c3 = pow(m, e, n3) #c3=1881640295202816

$ c_1 \equiv m^{e} \pmod{n_1} $

$ c_2 \equiv m^{e} \pmod{n_2} $

$ c_3 \equiv m^{e} \pmod{n_3} $

先确认ni之间是互素的，在此之后用crt算出来之后开方即可：

$ m = \sqrt[e]{x} $

以下是代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2
from sympy.ntheory.modular import crt

#m = 123456
n_list=[10142789312725007,10142789312725009,10142789312725013]
e = 3
c_list=[1881640295202816,1881640295202816,1881640295202816]
#示例代码中的数字比较小，所以模下来数字一样，不过无所谓，重在示例

#先要检验n各个数字之间是否是互素的
for i in n_list:
    for j in n_list:
        if i != j:
            if gmpy2.gcd(i, j) == 1:
                continue
            else:
                print(i, j)
                print(gmpy2.gcd(n_list[i-1], n_list[j-1]))

c, N = crt(n_list, c_list) 
root, exact = gmpy2.iroot(c, e)
print(root)