Initially, lets just look at a question.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #[鹤城杯 2021]BabyRSA
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724
hint2 = q % (2 ** 265)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)
|
In this question, we know high bite of p and low bite of q, and asked
to find all the bite of p and q
In the first step, we can access low bite of p by low bite of q,
because p*q=n
we get
This question has convert to how to get p(1024bit) by high bite of
p(1024-724=300) and low bite of p(256bit), totally 556 bites
官方文档：https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/polynomial_modn_dense_ntl.html
1
2
3
4
| n = 10001
PR.<x> = PolynomialRing(Zmod(n))#生成一个模n意义下的环
f = x^3 + 10*x^2 + 5000*x - 222 #多项式表达式
f.small_roots() #返回多项式的解
|
返回值为[4]，将x=4带回原式计算得20002，mod
n确实等于0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #[SWPUCTF 2021 新生赛]crypto3
from gmpy2 import *
from Crypto.Util.number import *
flag = '******************'
p = getPrime(512)
q = getPrime(512)
m1 = bytes_to_long(bytes(flag.encode()))
n = p*q
flag1 = pow(m1,p,n)
flag2 = pow(m1,q,n)
print('flag1= '+str(flag1))
print('flag2= '+str(flag2))
print('n= '+str(n))
#flag1=
#flag2=
#n=
|
顿悟猜到flag位数是191位，我们知道m的p和q次方分别是c1和c2，使用共膜攻击即可
1
2
3
4
5
6
7
8
| #sage
flag1=
flag2=
n=
PR.<m> = PolynomialRing(Zmod(n))
f = m^2-(flag1+flag2)*m+c1*c2
flag = f.small_roots(X=2^200)
print( flag[0] )
|
如果没有格，解方程得到的m的两个解分别是c1和c2，
补充：通过实测得到，如果X=的值过大也无法得到结果（400可以，500就不行了）
参考链接：
1
2
| https://www.cnblogs.com/mumuhhh/articles/17315349.html
https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/polynomial_modn_dense_ntl.html
|