引言
无
[NPUCTF2020]共 模 攻 击
题目给了两个加密程序
一个是加密hint：
from gmpy2 import *
from Crypto.Util.number import *
from secret import hint
m = bytes_to_long(hint)
p = getPrime(256)
c = pow(m, 256, p)
print(p)
p, q = getPrime(256), getPrime(256)
n = p * q
e1, e2 = getPrime(32), getPrime(32)
c1, c2 = pow(c, e1, n), pow(c, e2, n)
print(n)
print(e1, c1)
print(e2, c2)
'''
107316975771284342108362954945096489708900302633734520943905283655283318535709
6807492006219935335233722232024809784434293293172317282814978688931711423939629682224374870233587969960713638310068784415474535033780772766171320461281579
2303413961 1754421169036191391717309256938035960912941109206872374826444526733030696056821731708193270151759843780894750696642659795452787547355043345348714129217723
2622163991 1613454015951555289711148366977297613624544025937559371784736059448454437652633847111272619248126613500028992813732842041018588707201458398726700828844249
'''
另一个是加密flag：
from gmpy2 import *
from Crypto.Util.number import *
from secret import flag
flag = flag.strip(b"npuctf{").strip(b"}")
m = bytes_to_long(flag)
p, q = getPrime(512), getPrime(512)
n = p * q
e1, e2 = p, q
c1, c2 = pow(m, e1, n), pow(m, e2, n)
print(n)
print(c1)
print(c2)
'''
128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149
96860654235275202217368130195089839608037558388884522737500611121271571335123981588807994043800468529002147570655597610639680977780779494880330669466389788497046710319213376228391138021976388925171307760030058456934898771589435836261317283743951614505136840364638706914424433566782044926111639955612412134198
9566853166416448316408476072940703716510748416699965603380497338943730666656667456274146023583837768495637484138572090891246105018219222267465595710692705776272469703739932909158740030049375350999465338363044226512016686534246611049299981674236577960786526527933966681954486377462298197949323271904405241585
'''
乍一看，确实很像共模攻击，但是一看这个加密指数是p和q并且未知，就知道没那么简单
首先来解密hint
第一步容易想到用共模攻击解密被加密的hint
代码如下：
import gmpy2
from Crypto.Util.number import *
# hint
e1 = 2303413961
e2 = 2622163991
c1 = 1754421169036191391717309256938035960912941109206872374826444526733030696056821731708193270151759843780894750696642659795452787547355043345348714129217723
c2 = 1613454015951555289711148366977297613624544025937559371784736059448454437652633847111272619248126613500028992813732842041018588707201458398726700828844249
p1 = 107316975771284342108362954945096489708900302633734520943905283655283318535709
n = 6807492006219935335233722232024809784434293293172317282814978688931711423939629682224374870233587969960713638310068784415474535033780772766171320461281579
gcd, s, t = gmpy2.gcdext(e1, e2)
if s < 0:
s = -s
c1 = gmpy2.invert(c1, n)
if t < 0:
t = -t
c2 = gmpy2.invert(c2, n)
c = gmpy2.powmod(c1, s, n) * gmpy2.powmod(c2, t, n) % n
print(c)
但下一步发现，加密hint的过程为
c = pow(m, 256, p)
原本是想类似于经典的RSA解密
p的欧拉函数为p-1，然后参考
[De1CTF2019]babyrsa
或者
EzRSA
，利用
g
c
d
(
256
,
p
−
1
)
gcd(256,p-1)
g
c
d
(
2
5
6
,
p
−
1
)
解出d然后求解
但是发现
g
c
d
(
256
,
p
−
1
)
=
4
gcd(256,p-1)=4
g
c
d
(
2
5
6
,
p
−
1
)
=
4
，无法用这种方法
只好找
wp
原来直接用sympy库的nthroot_mod方法就行，该方法可以用来求解
x
n
≡
a
m
o
d
p
x^n \equiv a\space mod\space p
x
n
≡
a
m
o
d
p
，其中
n
,
a
,
p
n,a,p
n
,
a
,
p
为已知数
那么，有这么好的方法，能不能直接用来求解RSA问题呢？当然是不行的
因为求解本题的
m
256
≡
c
m
o
d
p
m^{256} \equiv c\space mod\space p
m
2
5
6
≡
c
m
o
d
p
都要花上好几秒，求解RSA问题基本上不可能
这里附上
nthroot_mod的源代码
，感兴趣的师傅可以研究研究
完整解密代码如下：
import gmpy2
import sympy
from Crypto.Util.number import *
# hint
e1 = 2303413961
e2 = 2622163991
c1 = 1754421169036191391717309256938035960912941109206872374826444526733030696056821731708193270151759843780894750696642659795452787547355043345348714129217723
c2 = 1613454015951555289711148366977297613624544025937559371784736059448454437652633847111272619248126613500028992813732842041018588707201458398726700828844249
p1 = 107316975771284342108362954945096489708900302633734520943905283655283318535709
n = 6807492006219935335233722232024809784434293293172317282814978688931711423939629682224374870233587969960713638310068784415474535033780772766171320461281579
gcd, s, t = gmpy2.gcdext(e1, e2)
if s < 0:
s = -s
c1 = gmpy2.invert(c1, n)
if t < 0:
t = -t
c2 = gmpy2.invert(c2, n)
c = gmpy2.powmod(c1, s, n) * gmpy2.powmod(c2, t, n) % n
print(c)
m = sympy.nthroot_mod(c, 256, p1)
print(long_to_bytes(m))
结果为：
提示m的位数小于400，有什么用吗？
wp中说可以由此联想到Coppersmith
确实，在一些高位或低位泄露的题目中，Coppersmith是常用的手段，但是只知道位数小于400怎么用呢？
wp一下的解题过程也确实没有用到Coppersmith
不过，wp给了Coppersmith定理一个比较通俗的解释：在一个
e
e
e
阶的以
n
n
n
为模的多项式
f
(
x
)
f(x)
f
(
x
)
中，如果有一个根小于
n
1
/
e
n^{1/e}
n
1
/
e
，就可以运用一个O(log n)的算法求出这些根。其中的“阶”大概就是指（循环）群的阶
在这里重新推导一遍解题思路
由加密程序可得：
c
1
≡
m
p
m
o
d
n
≡
m
p
m
o
d
p
q
c
2
≡
m
q
m
o
d
n
≡
m
q
m
o
d
p
q
c_1 \equiv m^{p}\space mod\space n \equiv m^{p}\space mod\space pq\\ c_2 \equiv m^{q}\space mod\space n \equiv m^{q}\space mod\space pq
c
1
≡
m
p
m
o
d
n
≡
m
p
m
o
d
p
q
c
2
≡
m
q
m
o
d
n
≡
m
q
m
o
d
p
q
故
∃
t
1
∈
Z
\exists t_1\in \mathbb{Z}
∃
t
1
∈
Z
，
s
.
t
.
c
1
=
m
p
+
t
1
p
q
s.t. c_1 = m^p + t_1pq
s
.
t
.
c
1
=
m
p
+
t
1
p
q
于是有
c
1
≡
m
p
m
o
d
p
c_1 \equiv m^{p}\space mod\space p
c
1
≡
m
p
m
o
d
p
由
费马小定理
有
m
p
≡
m
m
o
d
p
m^{p}\equiv m\space mod\space p
m
p
≡
m
m
o
d
p
故
c
1
≡
m
m
o
d
p
c_1 \equiv m\space mod\space p
c
1
≡
m
m
o
d
p
同理，有
c
2
≡
m
m
o
d
q
c_2 \equiv m\space mod\space q
c
2
≡
m
m
o
d
q
故
∃
k
1
,
k
2
∈
Z
\exists k_1,k_2\in \mathbb{Z}
∃
k
1
,
k
2
∈
Z
，
s
.
t
.
s.t.
s
.
t
.
{
c
1
=
m
+
k
1
p
c
2
=
m
+
k
2
q
\begin{cases} c_1=m+k_1p\\ c_2=m+k_2q \end{cases}
{
c
1
=
m
+
k
1
p
c
2
=
m
+
k
2
q
则
{
(
c
1
+
c
2
)
m
=
2
m
2
+
(
k
1
p
+
k
2
q
)
m
⋯
①
c
1
c
2
=
m
2
+
(
k
1
p
+
k
2
q
)
m
+
k
1
k
2
p
q
⋯
②
\begin{cases} (c_1+c_2)m=2m^2+(k_1p+k_2q)m \cdots ①\\ c_1c_2=m^2+(k_1p+k_2q)m+k_1k_2pq \cdots ② \end{cases}
{
(
c
1
+
c
2
)
m
=
2
m
2
+
(
k
1
p
+
k
2
q
)
m
⋯
①
c
1
c
2
=
m
2
+
(
k
1
p
+
k
2
q
)
m
+
k
1
k
2
p
q
⋯
②
①
−
②
①-②
①
−
②
得：
(
c
1
+
c
2
)
m
−
c
1
c
2
=
m
2
−
k
1
k
2
p
q
=
m
2
−
k
1
k
2
n
(c_1+c_2)m-c_1c_2=m^2-k_1k_2pq=m^2-k_1k_2n
(
c
1
+
c
2
)
m
−
c
1
c
2
=
m
2
−
k
1
k
2
p
q
=
m
2
−
k
1
k
2
n
移项，等式两边模
n
n
n
，得：
m
2
−
(
c
1
+
c
2
)
m
+
c
1
c
2
=
k
1
k
2
n
≡
0
m
o
d
n
m^2-(c_1+c_2)m+c_1c_2=k_1k_2n \equiv 0\space mod \space n
m
2
−
(
c
1
+
c
2
)
m
+
c
1
c
2
=
k
1
k
2
n
≡
0
m
o
d
n
所以只要在模
n
n
n
的情况下（或者说是在整数模
n
n
n
加法群中），求方程的根
参照wp，sage代码如下：
得到m直接long_to_bytes即可
结果为：
结语
摸了一天鱼，好累哦[doge]
关于sagemath的学习，官方文档看得挺累人的，推荐一个翻译的比较好的
中文教程
油管上还找到一个
入门教程
，今年一月份的，用的是9.2版本，还比较新
希望继续坚持