当前位置:网站首页>[CISCN 2021 华南赛区]rsa Writeup
[CISCN 2021 华南赛区]rsa Writeup
2022-07-06 09:33:00 【bestkasscn】
[CISCN 2021 华南赛区]rsa
题目描述
from flag import text,flag
import md5
from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime
assert md5.new(text).hexdigest() == flag[6:-1]
msg1 = text[:xx]
msg2 = text[xx:yy]
msg3 = text[yy:]
msg1 = bytes_to_long(msg1)
msg2 = bytes_to_long(msg2)
msg3 = bytes_to_long(msg3)
p1 = getPrime(512)
q1 = getPrime(512)
N1 = p1*q1
e1 = 3
print pow(msg1,e1,N1)
print (e1,N1)
p2 = getPrime(512)
q2 = getPrime(512)
N2 = p2*q2
e2 = 17
e3 = 65537
print pow(msg2,e2,N2)
print pow(msg2,e3,N2)
print (e2,N2)
print (e3,N2)
p3 = getPrime(512)
q3 = getPrime(512)
N3 = p3*q3
print pow(msg3,e3,N3)
print (e3,N3)
print p3>>200
通过审计代码可知,flag == md5(text),text = msg1 + msg2 + msg3
所以只要能解出msg1,2,3就能解出flag
part1
p1 = getPrime(512)
q1 = getPrime(512)
N1 = p1*q1
e1 = 3
print pow(msg1,e1,N1)
print (e1,N1)
小明文攻击,e过小导致明文的三次方依然比n小,直接对c1开三次方
part2
p2 = getPrime(512)
q2 = getPrime(512)
N2 = p2*q2
e2 = 17
e3 = 65537
print pow(msg2,e2,N2)
print pow(msg2,e3,N2)
print (e2,N2)
print (e3,N2)
典型的共模攻击,推导过程如下:
首先,两个加密指数互质:
gcd(e1,e2)=1
即存在s1、s2使得:
s1 * e1+s2 * e2=1
又因为:
c1≡m^e1 mod n
c2≡m mod n
代入化简可得:
c1^s1 * c2^s2 ≡ m mod n
即可求出明文
part3
p3 = getPrime(512)
q3 = getPrime(512)
N3 = p3*q3
print pow(msg3,e3,N3)
print (e3,N3)
print p3>>200
题目将p3右移200位,而p3原本有512位,所以我们用Coppersmith partial information attack算法求p3的低位即可解出p3,q3
其中,Coppersmith partial information attack基于sage实现。
完整exp
from Crypto.Util.number import *
import gmpy2
from hashlib import md5
import sys
sys.setrecursionlimit(1000000)
def egcd(a, b):
if a == 0:
return b, 0, 1
else:
g, y, x = egcd(b % a, a)
return g, x - (b // a) * y, y
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def CommonMode(e1, e2, c1, c2, n):
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
if s1 < 0:
s1 = - s1
c1 = modinv(c1, n)
elif s2 < 0:
s2 = - s2
c2 = modinv(c2, n)
m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
return long_to_bytes(m)
c1 = 19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
e1 = 3
n1 = 123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009
msg1 = long_to_bytes(gmpy2.iroot(c1, e1)[0])
c2 = 54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
c3 = 91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
e2 = 17
e3 = 65537
n2 = 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977
msg2 = CommonMode(e2, e3, c2, c3, n2)
c4 = 59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
n3 = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
p3_high = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
#这部分代码用sage去跑
# n=113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
# p4=7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902#已知P的高位
# e=65537
# pbits=512 #P原本的位数
#
# kbits=pbits - p4.nbits()
# print (p4.nbits())
# p4 = p4 << kbits
# PR.<x> = PolynomialRing(Zmod(n))
# f = x + p4
# roots = f.small_roots(X=2^kbits,beta=0.4)
# # 经过以上一些函数处理后,n和p已经被转化为10进制
# if roots:
# p= p4 + int(roots([0]))
# print ("n",n)
# print ("p",p)
# print ("q",n/p)
p3 = 11437038763581010263116493983733546014403343859218003707512796706928880848035239990740428334091106443982769386517753703890002478698418549777553268906496423
q3 = 9918033198963879798362329507637256706010562962487329742400933192721549307087332482107381554368538995776396557446746866861247191248938339640876368268930589
d = gmpy2.invert(e3, (p3 - 1) * (q3 - 1))
msg3 = long_to_bytes(pow(c4, d, n3))
text = msg1 + msg2 + msg3
print(md5(text).hexdigest())
最终就得到了flag。
边栏推荐
- Data transfer instruction
- Only learning C can live up to expectations top5 S1E8 | S1E9: characters and strings & arithmetic operators
- Mongodb learning notes
- Take you hand-in-hand to do intensive learning experiments -- knock the level in detail
- 8086 segmentation technology
- 唯有学C不负众望 TOP5 S1E8|S1E9:字符和字符串&&算术运算符
- Flink 解析(六):Savepoints
- Conception du système de thermomètre numérique DS18B20
- Akamai浅谈风控原理与解决方案
- 面试集锦库
猜你喜欢
8086 CPU 内部结构
Take you hand-in-hand to do intensive learning experiments -- knock the level in detail
Program counter of JVM runtime data area
Wu Jun's trilogy experience (VII) the essence of Commerce
Flink 解析(四):恢复机制
JVM class loading subsystem
TCP's three handshakes and four waves
Coursera cannot play video
IDEA断点调试技巧,多张动图包教包会。
Resume of a microservice architecture teacher with 10 years of work experience
随机推荐
Coursera cannot play video
关于Stream和Map的巧用
连接局域网MySql
在 vi 编辑器中的命令模式下,删除当前光标处的字符使用 __ 命 令。
Activiti directory (IV) inquiry agency / done, approved
Only learning C can live up to expectations TOP4 S1E6: data type
JVM运行时数据区之程序计数器
算数运算指令
Shawshank's sense of redemption
vscode
JVM garbage collector part 1
Thank you for your invitation. I'm in the work area. I just handed in the code. I'm an intern in the next ByteDance
Login to verify the simple use of KOA passport Middleware
PostgreSQL 14.2, 13.6, 12.10, 11.15 and 10.20 releases
Fdog series (VI): use QT to communicate between the client and the client through the server (less information, recommended Collection)
Activiti目录(四)查询代办/已办、审核
Flink 解析(二):反压机制解析
唯有学C不负众望 TOP1环境配置
Fdog series (4): use the QT framework to imitate QQ to realize the login interface, interface chapter.
TCP's three handshakes and four waves