首页 > 其他分享 >NewStarCTF-WEEK1-Crypto-ezrsa复现

NewStarCTF-WEEK1-Crypto-ezrsa复现

时间:2022-12-14 22:34:03浏览次数:54  
标签:phi gmpy2 NewStarCTF hint pow Crypto ezrsa WEEK1 import

2022-NewStar-Week1-ezrsa复现

题干

assert len(flag) % 5 == 0

cnt = len(flag) // 5

flags = [flag[cnt*i:cnt*(i+1)] for i in range(5)]

可知flag分五段。

第一段

m = bytes_to_long(message)
c = 22160015525054597533062795679117215923801827397299805735087138192137742945881204146337349060934854888054628153923021387981306839951210090523829296521835965212118849043671673133979884712755090374758002677916820953359774554825569218497687506468472278309097929775388010403607769802840990547048001743970754496905
p = 6962443023774446497102092246794613339314677593117417573764609329949026862782472380488956732038459060928443992561763464365758383525259954798321350043810351
q = 9631855759661411029901156175243744760977799976661519182223576693685069000499866459636568713055906075171480855575061732016121299027658733834671035383233163
e = 0x10001

level1 就是常规的RSA解密

import Crypto.Util.number
import gmpy2
n = p*q
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e, phi_n)
m = pow(c, d, n)

第二段

c = 17250922799297131008803303235771955129
n = 134097988095851988085603926250918812377
e = 0x10001
m = bytes_to_long(message)

level2 p,q没给出,我们就是通过网站分解质因数得到p,q.

import Crypto.Util.number
import gmpy2
n = p*q
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e, phi_n)
m = pow(c, d, n)

第三段

c = 2776571135646565181849912433877522437622755332262910824866791711
n = 85793694792655420934945863688968944466300304898903354212780512650924132933351787673979641944071634528676901506049360194331553838080226562532784448832916022442020751986591703547743056267118831445759258041047213294368605599719242059474324548598203039032847591828382166845797857139844445858881218318006747115157
e = 3

level3 e比较小,是低加密指数攻击

import gmpy2
import binascii
i = 0
while True:
    if gmpy2.iroot((c+i*n), e)[1]:
        m = gmpy2.iroot((c+i*n), e)[0]
        break
    i += 1

第四段

c = 68588738085497640698861260094482876262596289469248772328560280530093163764972313090939471997156632421517452790632223565521726590730640805290182026911025142051864898712501214753986865172996090706657535814234291235489829621372021092488300236623525366939477695283380634188510950335639019458758643273802572617191
e = 51999725233581619348238930320668315462087635295211755849675812266270026439521805156908952855288255992098479180003264827305694330542325533165867427898010879823017054891520626992724274019277478717788189662456052796449734904215067032681345261878977193341769514961038309763898052908572726913209883965288047452751
n = 68816697240190744603903822351423855593899797203703723038363240057913366227564780805815565183450516726498872118491739132110437976570592602837245705802946829337567674506561850972973663435358068441037127926802688722648016352967768929007662772115485020718202683004813042834036078650571763978066558718285783045969

level4 e很大,是低解密指数攻击

import gmpy2
import binascii
import RSAwienerHacker
d = RSAwienerHacker.hack_RSA(e, n)
m = gmpy2.powmod(c, d, n)

第五段

c = 1135954814335407362237156338232840769700916726653557860319741136149066730262056907097728029957898420630256832277578506404721904131425822963948589774909272408535427656986176833063600681390871582834223748797942203560505159946141171210061405977060061656807175913366911284450695116982731157917343650021723054666494528470413522258995220648163505549701953152705111304471498547618002847587649651689203632845303117282630095814054989963116013144483037051076441508388998829
hint = 611144874477135520868450203622074557606421849009025270666985817360484127602945558050689975570970227439583312738313767886380304814871432558985582586031211416586296452510050692235459883608453661597776103386009579351911278185434163016083552988251266501525188362673472772346212970459561496301631587043106524741903627979311997541301471894670374945556313285203740782346029579923650160327646876967315182335114575921178144825057359851607166387868294019144940296084605930
n = 1232865496850144050320992645475166723525103370117149219196294373695624167653495180701004894188767069545579706264513808335877905149818445940067870026924895990672091745229251935876434509430457142930654307044403355838663341948471348893414890261787326255632362887647279204029327042915224570484394917295606592360109952538313570951448278525753313335289675455996833500751672463525151201002407861423542656805624090223118747404488579783372944593022796321473618301206064979
n = p * p * q
e = 0x10001
d = inverse(e, p * (p-1) * (q-1))
assert m < n
c = pow(m, e, n)
hint = pow(d, e, n)

level5 p q无法啊直接通过n分解出来. 但仔细分析n和phi(n)我们可以发现公约数是p,那么我们的突破点就在这. 通过题目可以发现直接求出phi(n)是不切实际的,那我们只需要让phi(n)存在于某一个式子即可.

推导:

\(n=p\times p\times q\)

\(则\phi (n)=p\times (p-1)\times (q-1)\)
\(p=gcd(n,\phi (n))\)
\(由题干知:\)
\(ed\equiv 1(\bmod \phi (n))\Leftrightarrow ed=1+K_{1}\phi (n)\)
\(hint=d^{e}\bmod n \Leftrightarrow d^{e}=hint +K_{2}n\)
\(经代换可得:\)
\((ed)^{e}\equiv 1\bmod \phi (n)\Leftrightarrow e^{e}\times d^{e}=1+K_{3}\phi (n)\)
\(两边同时对n取模,化简得:\)
\(e^{e}\times hint\equiv 1+K_{3}\phi (n)(\bmod n)\)
\(最后得到:\)
\(K\phi(n)=(x\times hint -1)\bmod n,\)
\(其中x=e^{e}\bmod n\)

import math
import gmpy2
import Crypto.Util.number
# 求出e**e模n
x = pow(e, e, n)

a = (x*hint-1) % n
p = math.gcd(a, n)
q = n//p**2
phi = (p - 1) * (q - 1)*p
d = gmpy2.invert(e, phi)
m = pow(c, d, n)

完整exp

'''
assert len(flag) % 5 == 0

cnt = len(flag) // 5

flags = [flag[cnt*i:cnt*(i+1)] for i in range(5)]
'''
def sent1():
    # 正常的RSA解密
    # 公钥私钥都有了
    c = 22160015525054597533062795679117215923801827397299805735087138192137742945881204146337349060934854888054628153923021387981306839951210090523829296521835965212118849043671673133979884712755090374758002677916820953359774554825569218497687506468472278309097929775388010403607769802840990547048001743970754496905
    p = 6962443023774446497102092246794613339314677593117417573764609329949026862782472380488956732038459060928443992561763464365758383525259954798321350043810351
    q = 9631855759661411029901156175243744760977799976661519182223576693685069000499866459636568713055906075171480855575061732016121299027658733834671035383233163
    e = 0x10001
    import Crypto.Util.number
    import gmpy2
    n = p*q
    phi_n = (p-1)*(q-1)
    d = gmpy2.invert(e, phi_n)
    m = pow(c, d, n)
    return Crypto.Util.number.long_to_bytes(m)

def sent2():
    # 没有p,q,但是n比较小
    # 可以先分解n得到p,q
    c = 17250922799297131008803303235771955129
    p = 10094271714305059493
    q = 13284562957208247589
    e = 0x10001
    import Crypto.Util.number
    import gmpy2
    n = p*q
    phi_n = (p-1)*(q-1)
    d = gmpy2.invert(e, phi_n)
    m = pow(c, d, n)
    return Crypto.Util.number.long_to_bytes(m)

def sent3():
    # 低指数加密攻击-->爆破
    # 常见的低指数加密是e=3
    # ①当 m^3 < n 时 , c = m^3 , 直 接 将 c 开 三 次 方 即 可 得 到 m
    # ②当 m^3 > n 时 , c = m^3 - i ∗ n , 只 要 找 到 i ,
    # 使 得 c + i n 能 够 开 三 次 方 即 可 得 到m
    c = 2776571135646565181849912433877522437622755332262910824866791711
    n = 85793694792655420934945863688968944466300304898903354212780512650924132933351787673979641944071634528676901506049360194331553838080226562532784448832916022442020751986591703547743056267118831445759258041047213294368605599719242059474324548598203039032847591828382166845797857139844445858881218318006747115157
    e = 3
    import gmpy2
    import binascii
    i = 0
    while True:
        if gmpy2.iroot((c+i*n), e)[1]:
            m = gmpy2.iroot((c+i*n), e)[0]
            break
        i += 1
    return binascii.unhexlify(hex(m)[2:])

def sent4():
    # 题中e很大,故可知是低解密指数攻击
    # hacker模块利用
    c = 68588738085497640698861260094482876262596289469248772328560280530093163764972313090939471997156632421517452790632223565521726590730640805290182026911025142051864898712501214753986865172996090706657535814234291235489829621372021092488300236623525366939477695283380634188510950335639019458758643273802572617191
    e = 51999725233581619348238930320668315462087635295211755849675812266270026439521805156908952855288255992098479180003264827305694330542325533165867427898010879823017054891520626992724274019277478717788189662456052796449734904215067032681345261878977193341769514961038309763898052908572726913209883965288047452751
    n = 68816697240190744603903822351423855593899797203703723038363240057913366227564780805815565183450516726498872118491739132110437976570592602837245705802946829337567674506561850972973663435358068441037127926802688722648016352967768929007662772115485020718202683004813042834036078650571763978066558718285783045969
    import gmpy2
    import binascii
    import RSAwienerHacker
    d = RSAwienerHacker.hack_RSA(e, n)
    m = gmpy2.powmod(c, d, n)
    return binascii.unhexlify(hex(m)[2:])

def sent5():
    # 这一道题目需要进行模运算。p q无法啊直接通过n分解出来,
    # 但仔细分析n和phi(n)我们可以发现公约数是p,那么我们的突破点就在这。
    # 通过题目可以发现直接求出phi(n)是不切实际的,那我们只需要让phi存在于某一个式子即可
    n = 1232865496850144050320992645475166723525103370117149219196294373695624167653495180701004894188767069545579706264513808335877905149818445940067870026924895990672091745229251935876434509430457142930654307044403355838663341948471348893414890261787326255632362887647279204029327042915224570484394917295606592360109952538313570951448278525753313335289675455996833500751672463525151201002407861423542656805624090223118747404488579783372944593022796321473618301206064979
    hint = 611144874477135520868450203622074557606421849009025270666985817360484127602945558050689975570970227439583312738313767886380304814871432558985582586031211416586296452510050692235459883608453661597776103386009579351911278185434163016083552988251266501525188362673472772346212970459561496301631587043106524741903627979311997541301471894670374945556313285203740782346029579923650160327646876967315182335114575921178144825057359851607166387868294019144940296084605930
    c = 1135954814335407362237156338232840769700916726653557860319741136149066730262056907097728029957898420630256832277578506404721904131425822963948589774909272408535427656986176833063600681390871582834223748797942203560505159946141171210061405977060061656807175913366911284450695116982731157917343650021723054666494528470413522258995220648163505549701953152705111304471498547618002847587649651689203632845303117282630095814054989963116013144483037051076441508388998829
    e = 0x10001
    import math
    import gmpy2
    import Crypto.Util.number
    # 求出e**e模n
    x = pow(e, e, n)
    a = (x*hint-1) % n
    p = math.gcd(a, n)
    q = n//p**2
    phi = (p - 1) * (q - 1)*p
    d = gmpy2.invert(e, phi)
    m = pow(c, d, n)
    return Crypto.Util.number.long_to_bytes(m)

print(sent1()+sent2()+sent3()+sent4()+sent5())
# flag:
# b'flag{W0w_U_ar3_re4L1y_g0Od_4t_m4th_4nD_RSA!!}'

标签:phi,gmpy2,NewStarCTF,hint,pow,Crypto,ezrsa,WEEK1,import
From: https://www.cnblogs.com/Lovechan/p/16983843.html

相关文章

  • HNCTF [Week1]Interesting_http
    HNCTF[Week1]Interesting_http五毛钱翻译:请用post给我一个wantBurpSuite抓包传参<want>参数更改传参方式发送到'重发模块'---->五毛钱翻译:你还要告诉我你......
  • 2022NewStarCTF新生赛一些比较有意思的题目wp
    Misc_蚁剑流量分析Pcap的文件可以直接使用工具 编辑器打开目录,一个一个看,可以找到eval危险函数 看到n3wst4r,直接使用linux正则匹配,找出相关内容Url解码,了解一下蚁......
  • 0xgame2022 PWN week1-4
    0xgameweek1pwn1签到的nc,catflagpwn2ret2backdoor,一个栈溢出#encoding=utf-8frompwnimport*importosimportsysimporttime#fromae64importAE64#fro......
  • NewStarCTF-WEEK4-周报
    目录WEEK4周报canary常见的Canary绕过方式泄露程序地址/栈地址buupwn1_sctf_2016思路jarvisoj_level0思路[第五空间2019决赛]PWN5思路ciscn_2019_n_8思路jarvisoj_level2......
  • [NPUCTF2020]EzRSA
    [NPUCTF2020]EzRSA题目:fromgmpy2importlcm,powmod,invert,gcd,mpzfromCrypto.Util.numberimportgetPrimefromsympyimportnextprimefromrandomimpo......
  • NewStarCTF 2022
    NewStarWEB我真的会谢提示:Flaghasthreepart,qsdzhidthemindifferentfiles.Bytheway,thesefilesaresensitive.<!--IusedVIMtowritethisfile,b......
  • NewStarCTF WEEK3
    WEEK3目录WEEK3catflag竞态条件和数据竞争sheepaflagread&writereturntocsubuurip题解思路warm_up思路ciscn_2019思路catflag竞态条件和数据竞争​ 竞态条件:强......
  • BUUCTF [NewStarCTF] Week1 WEB NotPHP 详解
    NotPHP<?phperror_reporting(0);highlight_file(__FILE__);if(file_get_contents($_GET['data'])=="WelcometoCTF"){if(md5($_GET['key1'])===md5($_GET['k......
  • NewStarCTF Week3 Blockchain
    前言:最近学了点blockchain,正好NewStarCTF这周上了题,赶紧来练练手,出题人很友好,代码都很简单,适合刚了解区块链的新手入门Checkin先安装Metamask,再去Goerli水龙头领币然后n......
  • NewStarCTF学习笔记-WEEK1
    WEEK1returntotext[text区域]​ 通过向栈上堆砌长度足够且合适的"垃圾信息"改写ret指令指向的地址,执行对应函数​ 注意点:保护,遇上Canary要进行绕过常见的Cana......