NKCTF
Crypto
baby_RSA
题目连接
https://pan.baidu.com/s/1gHXugkve5NbHg0n7Zd5KPg?pwd=2023
通过dp求出P,Q,即c1,c2关键是公式变换,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| RSA
n = p*q
c1 = m^p mod (p*q)
c2 = m^p mod (p*q)
费马小定理
m^p ≡ m mod (p)
m^q ≡ m mod (p)
/*个人感觉这里是m<p,那么m^p<p*q,才能有下面的结果*/
c1 = m + k1*p + k2*p*q=m+k3*p
同理
c2 = m +k4*q
c1*c2 = m^2 +m(k3*p+k4*q)+ k3*k4*n
(c1+c2)m =2(m^2) + m(k3*p+k4*q)
所以m^2 - (c1+c2)m + c1 * c2 = k3 * k4 * m ≡ 0 mod (n)
即构建关于m的多项式,使用coppersmith方法即可
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| n = 114101396033690088275999670914803472451228154227614098210572767821433470213124900655723605426526569384342101959232900145334500170690603208327913698128445002527020347955300595384752458477749198178791196660625870659540794807018881780680683388008090434114437818447523471527878292741702348454486217652394664664641
N = 1159977299277711167607914893426674454199208605107323826176606074354449015203832606569051328721360397610665453513201486235549374869954501563523028914285006850687275382822302821825953121223999268058107278346499657597050468069712686559045712946025472616754027552629008516489090871415609098178522863027127254404804829735621706042266140637592206366042515190385496909533329383212542170504864473944657824502882014292528444918055958758310544435120502872883857209880723535754528096143707324179005292445100655695427777453144657819474805882956064292780031599790769618615908501966912635232746588639924772530057835864082951499028
dP = 33967356791272818610254738927769774016289590226681637441101504040121743937150259930712897925893431093938385216227201268238374281750681609796883676743311872905933219290266120756315613501614208779063819499785817502677885240656957036398336462000771885589364702443157120609506628895933862241269347200444629283263
e=65537
P=0
e=65537
temp=dP*e
for i in range(1,e):
if(temp-1)%i==0:
x=(temp-1)//i+1
y=N%x
if y==0:
P=x
break
P=37269067352457630263351774206178494913957088859822110344334922741582406663357663275001777826744534556652993452577088773275825539553907027527722045884489297259984687894496505265384077983882580247333972954704644517469999916574893996324149548980338301147983367163067556434434982470623587914250041142380667816331
Q=N//P
Q,P=(31124398373258967647259273958463995255448332282733968391096762136494537693158180734634142626374694999391960402681114664140356232930100613919064790135723294710984789809295862966052914533841176463683069225072916170624016363164528353386087305805869313783193076760778433672011918504199905552973276891160558444988, 37269067352457630263351774206178494913957088859822110344334922741582406663357663275001777826744534556652993452577088773275825539553907027527722045884489297259984687894496505265384077983882580247333972954704644517469999916574893996324149548980338301147983367163067556434434982470623587914250041142380667816331)
n = 114101396033690088275999670914803472451228154227614098210572767821433470213124900655723605426526569384342101959232900145334500170690603208327913698128445002527020347955300595384752458477749198178791196660625870659540794807018881780680683388008090434114437818447523471527878292741702348454486217652394664664641
R.<m>=Zmod(n)[]
f=m**2-(P+Q)*m+P*Q
m=f.monic().small_roots()
print(m)
|
这段代码是用SageMath进行的多项式操作
1
2
3
4
| R.<m>=Zmod(n)[]#定义了一个在模n下的多项式环，m是环中的元素
f=m**2-(P+Q)*m+P*Q#定义了一个二次多项式，monic()方法返回该多项式的首项系数为1的首一多项式，
m=f.monic().small_roots()
|
monic()方法返回该多项式的首项系数为1的首一多项式，small_roots()方法返回多项式的所有小根，即在模n下使多项式等于0的所有整数解。
