当前位置: 首页 > news >正文

2022_easyRSA

Tags:RSA,二项式,模运算

0x00. 题目

task.py

from Crypto.Util.number import *
from secret import flagp = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p * q * r
e = 2 * 65537
m = bytes_to_long(flag)
hint1 = (p ** e - q ** e) % n
hint2 = ((2022 * p - q) ** e) % n
c = pow(m, e, n)print('hint1=', hint1)
print('hint2=', hint2)
print('n=', n)
print('c=', c)'''
hint1= 52281369398119567600662410538274474517133545222909276138391564372588246951556629434770221234458474257377439969412704841500791846456027747748203669565548168914696425764936947122334706087984219346335163813276457066769423286733899273378368331536658499951445074723593154096302551355270335147373146189656941967028635503538514210591235797153127984090571130062808740480476891179648059623308845204047386245441238990490866887541280568559745952068080120249721728494529636
hint2= 812269801039413894591278079358829428758036232534135221906772873437636744333426585293727772709659955393324539345478442177306013153481675848440757037566170549490328554607077425823712672804058633402840402515101422958294631642070495372150426904944019441161167313930360440965481038384894804006149168592608984721191275623676598184353692459825319078000352713036259410561499975902803368237100174518148748647427461636349234848907856305248267315083901505095210729966773183
n= 882982249031535548330341246528720199440543946466957383057449513412150447193779757566762076728954117460898887428970617025549995668574636502129794163201567120705719942956794531213763808011596771145684829464604133585457655671694348466503187597400178190815156787162601224605024975743048127298195836665757113897601684518911541677609207386837648455363901768673522248501745633727556776748089329944749837984699389705838494543515399498025589804347229817239564237664909983
c= 175198543718411501549855635400850806059246384562505102614089769131268222450487690256679800266279485952557651309227097624656742869561093126023345189879810915190851567171378500242734898632986941052386989869840615936880252213276789842406696336114243246106091230988556639836826748025596025629542690565576037754055447000774583245251787101189971189153349018453500714541907146003648880552573318011434078436075687038897589887765173313894962578176499867707815372313130165

0x01. WP

1. 分析

是对于二项式定理+模运算的运用
我们的hint2是$$(2022*p-q)^e$$

这个第一项为$$ (2022*p)^e $$

最后一项是$$ q^e $$

中间的项都会有 $$p*q = n$$

然后我们又模上了n所以我们的除了第一项和第二项其他项都变成0了,所以我们化简得到$$hint2 = (2022^e * p^e + q^e) \ mod \ n$$

而$$hint1 = (p^e - q^e) \ mod \ n$$

所以此时我们就可以通过hint1+hint2消去了我们的qe,也就是得到$$hint1+hint2 \ = \ (p^e * (2022^e + 1)) \ mod \ n$$

然后此时我们与n求公约数,就可以得到我们的p

同理求q,

\[\begin{align*} hint1 * (2022^e \ mod \ n) - hint2 &= ((2022^e * p^e - 2022^e * q^e) \ mod \ n) - ((2022^e * p^e + q^e) \ mod \ n) \\&= - (2022^e + 1) * q^e \ mod \ n \end{align*}\]

那么此时就可以再次与n求公约数就可以得到q,然后我们p和q都能够得到,r也能够得到,就是基本的rsa解密即可。

2. 解题脚本

rsa_exp.py

from Crypto.Util.number import *
from gmpy2 import iroote = 2 * 65537
n= 882982249031535548330341246528720199440543946466957383057449513412150447193779757566762076728954117460898887428970617025549995668574636502129794163201567120705719942956794531213763808011596771145684829464604133585457655671694348466503187597400178190815156787162601224605024975743048127298195836665757113897601684518911541677609207386837648455363901768673522248501745633727556776748089329944749837984699389705838494543515399498025589804347229817239564237664909983
c= 175198543718411501549855635400850806059246384562505102614089769131268222450487690256679800266279485952557651309227097624656742869561093126023345189879810915190851567171378500242734898632986941052386989869840615936880252213276789842406696336114243246106091230988556639836826748025596025629542690565576037754055447000774583245251787101189971189153349018453500714541907146003648880552573318011434078436075687038897589887765173313894962578176499867707815372313130165
hint1= 52281369398119567600662410538274474517133545222909276138391564372588246951556629434770221234458474257377439969412704841500791846456027747748203669565548168914696425764936947122334706087984219346335163813276457066769423286733899273378368331536658499951445074723593154096302551355270335147373146189656941967028635503538514210591235797153127984090571130062808740480476891179648059623308845204047386245441238990490866887541280568559745952068080120249721728494529636
hint2= 812269801039413894591278079358829428758036232534135221906772873437636744333426585293727772709659955393324539345478442177306013153481675848440757037566170549490328554607077425823712672804058633402840402515101422958294631642070495372150426904944019441161167313930360440965481038384894804006149168592608984721191275623676598184353692459825319078000352713036259410561499975902803368237100174518148748647427461636349234848907856305248267315083901505095210729966773183
p = GCD(hint2 + hint1, n)
q = GCD(pow(2022,e,n)*hint1 - hint2, n)
r = n//p//q
print(p)
print(q)
print(r)# e和phi_n不互素
d = inverse(e//2, (p-1)*(q-1)*(r-1))
m = pow(c,d,n)
m = iroot(m, 2)
print(m)
print(long_to_bytes(m[0]))'''
9951851693926734122204885773440606711225146718418816630948014628251654669566935310890011180360685809386930879429133384666673283554214583913815724275938051
7030660157484773380116614561054346882089481536450893122555110279684781394375939332209487058879079838868654293601696448575381595159076960524521837483498403
12619785453570495374065523344444796126905094383485861073203532738997237786783550021232802382619177408410525411941402829367881010898541086580457280030762311
(mpz(56006392793427939732268117824970988440550584336175941119946527412330890939459882377157957948129108861), True)
b'flag{b710a7fc-0c92-b542-6d54-4dcf1cd02d3c}'
'''

最终得到flag为flag{b710a7fc-0c92-b542-6d54-4dcf1cd02d3c}

http://www.hskmm.com/?act=detail&tid=24917

相关文章:

  • 2025电缆厂家最新推荐排行榜:深度解析青岛一缆等六家优质企业实力,助力精准选购
  • 1 洛谷题解修正器
  • 防止语言模型性能倒退的新方法
  • Delphi 解决IniFiles中文乱码
  • Tarjan详解
  • RAG入门 - Retriever(1) - 指南
  • 分布式微服务系统架构第142集:全栈构建
  • 2025 年电永磁吊具制造厂家 TOP 企业品牌推荐排行榜全新发布,含大型电永磁吊具,全覆盖,起重,小型,钢板,钢板电永磁吊具公司推荐!
  • QBXT2025S刷题 Day4题
  • 实用指南:云原生时代 Kafka 深度实践:03进阶特性与最佳实践
  • 【VM虚拟机】VM新版本,虚拟机中键盘输入延迟卡顿
  • 2025石灰源头厂家最新推荐榜单:深度解析生石灰,熟石灰物流效率与综合实力
  • AtCoder Beginner Contest 426 游记
  • 如何把MCP服务集成到智能体?手把手教学(含视频教程)
  • bootimg.exe检查验证备份导出的img镜像文件是否正常
  • 华为云Flexus+DeepSeek征文|华为云Flexus服务器dify高效的平台通过自然语言转sql并执行搭建电商数据分析
  • 《独立开发者精选工具》第 019 期
  • 活着,就像明天就要死去一样
  • vue漏洞
  • 网站第一开在浏览器中打开慢的原因
  • [JVM] JVM内存调优 - 教程
  • 全面解析DoS攻击防护与应对策略
  • day16 课程(面向对象三大特性:继承 多态 属性)
  • C++ Vector算法精讲与底层探秘:从经典例题到性能优化全解析 - 指南
  • 大数据分析基础及应用案例:第二周学习报告 —— 初探 NumPy 与 Pandas
  • 强化学习人类反馈训练新方法解析
  • 在MyBatis中collection属性的命名规则主要取决于传入参数的类型
  • 20250919_QQ_ICMP
  • 2025CSP-S模拟赛59 比赛总结