2023 江苏省首届数据安全竞赛

WriteUp 9个月前 admin
246 0 0
昨儿下午参加了一下首届江苏省数据安全竞赛,虽然密码学的题目有缝合怪之嫌,但涉及的知识点却也并不算简单。但这是第一届比赛,面向的对象还是全省范围内的职工、学生、教师,CTF现在真卷啊。。。


  • 题目内容

  • 解题步骤

  • 解题脚本


题目内容

from Crypto.Util.number import *

def pad(msg):
    return msg + b'x00' * (2048 // 8 - len(msg))


def day():
    print("# == Day Time == #")
    A = [getRandomRange(1 << 301 << 40for _ in '01234']

    from notebook import pubkeys
    hint = str(A)[1:-1].replace(', ''||').encode()
    hint = bytes_to_long(pad(hint))
    package = []
    for pubkey in pubkeys:
        e, n = pubkey
        package.append(pow(hint, e, n))
    print(f"{package = }")

    return A


def night(A):
    print("# == Night Time == #")
    from secrets import secret

    p, q = [getPrime(1024for _ in '01']
    e, n = 0x10001, p * q
    message = bytes_to_long(pad(secret))
    ciphertext = pow(message, e, n)
    print(f"{e = }")
    print(f"{n = }")
    print(f"{ciphertext = }")

    core = getRandomRange(1 << 701 << 80)
    box = (A[4] * p ** 4 + A[3] * p ** 3 + A[2] * p ** 2 + A[1] * p ** 1 + core) % n
    shell = (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0]) % n
    print(f"{shell = }")

A = day()
night(A)

题目输出

# notebook.pubkeys
pubkeys = [
    [1316966923273393034574368601955241184391111444785998466710722972275633988040568029224272430397635357872449163107278928804572765398970752644900568552514020294813546024733050135082024292481598322682990045855877556853392263676715734911232910368712575738786450510156105046776600566496799942574786503183241332740784997363514285857446938222302824964396227964711868412832852194845619628366554904150230665043909281603861298992421759553638135733037244888585600075655017766713763334284974682754159767494437867386464788270392548503256135412609157993954349845981674000072937143857040970855382655304911806719316346552101453584266121],
    [1313636547774903694433910615288816366243965221147245493790443257513469643051508482519945160993497983268746607032666514024577996510214003878851754244812785830861056511467944880656887067183093022088006603023892079757597903932697728395729605528467171403935076011715369931494813762896302405865063013876978950952553183445737415893862580946529557997177862386840671940665891984463553509323759394863514802662045074793125218445076375294720405008157895103559623204523371691063630903658360461001806917018298844432738514873530829540084732665560723768831816785580126848217585494349751859982707295270194451027637908966488433591336079],
    [1313422209706853784863425138450444393536114566510977689013118842078064352816867606066548879016746689784867031499069217146653949323203507755857385123653072875573743110808787259755688613540214185294636104765964080842615717180413731820679997453377899736419007193552970900617704671115646941207925636014254352661937769415565529244046272257822921740649781322893596978112103176487718960676212380426151079825140922318909470514158027009961239217428522970405297292867815726509360369236095377704967444339421311749405316999191339677904499413281713365474466679134722393111495793887387332928227905039036942450742103526490509249576159],
    [1321746430662648628292439055708644436184530740821098010749514133474681581832957631729292681550968108122182841907644832479495695011213810971334153360397292385819609198743433956578966857749821825621262178208409227379634952172419748956184624505995106932133301461499473823229623656490844764958301835433668618062743327682117611417235819168865744757242990985069648255779083246816509593018812991050741917153961245784296647661659339041115118272068392627299499703962645966495325055378652176922700072734325787550811454984878236039742147547963385471101805136506286953288566035101103034341742923072819774753918471775281464739904101],
    [1316012920802348742413202394765537959589119609441428117329692661212660781149297315973073063954731746455220386673231725950116051390914388279415796378305381377822621647264088603927560119754278978906758212463937071494263575443156089509654950881813861479449401068535285885349738367249035960528895049222211387021733152221289202030407416118814341241382479971018611239102343929419190892133819275458474489856666791981711793637127167775551296403296397810821548297674986394286293380472089135564385129140069501205054853729781710604489652713172579677128036322403868618295553335257593973027194532512596143733434234439677513237984107]
]


# == Day Time == #
package = [113482755921727894308026323987153978319294565921297271483503416958220979227455466341038953971142407801194920978797098743417339981893147012208196020869891703956656942161446114516952107767882087255173217104964011096149897297832802098065132988517744007058222745700421282973366796155355692957250370510092219668829076067419106719838118353533105536795546563225102470124656128420555835303548251644405567250663514292418353945793928921219377444443247235090395933205200737624794054876786142356580101093438687722110708745008348200055579249447661754452275920869977866016001411727295433260220398972792153602104752222053141997523581181704751408375002844330657316129196030300245827671668820158728499267585417825018569561334260339645149505349602101894361868409619377485151337734378552337306663742215652984335664043851491714700766298936643295134007324757334709142247834367568787252410245281239196385617941221491410681741562061388682740552670933412215721826425341213894797885977145778813538119439614438661162793551999033030915461280326437327647252386377675712448950720674489587870913633918955142281475292038369771921226182094311337006742311879487157059658323269406711930393651649183019074679828192369313690126822098229262672881505158783968273350158299731314276956390740076466256878275236320446242001677250017312467314633692008900452507388981554258738225814057234459262160994532764706553075132444786132482533979413628488907290918756158936432881811263532942710639129912080296288963809288780983205098910447284145427055829967749911481160511621578484216430822108678492066277579415962030467996551230064062844980094241076379709277711327063998892890858114473339807447673678894643645195719650144352817184953387528965217770702858803278617781563984246430332884800563229284492104255853809754867592878818776361873642996662077628287052362360710454507672539465240674401385279529963043345060634868343217881273515503289974894457362066685037297545772310131198850220025672843957153107490874807599311288876818421468275658855183857485067696603798636556327070411528170381402923911922437076616994460720931230980991440337397730061039967493443152767007916713160518618697678791358770766857737217910848181657393760417031865203943283074078341988117567851667858026108335625589177179258992930648353570238327435125409871028669479754623782967450462280802423233657422873275069133939005033872391235288329468886849808534906305377008408076775145268714146937205940659708210819711903273898505450411746796296074348301840443689229715602713064347690095007369004049337459458047359544160409565437783924368962797071453687950582019132146435134269723546824657132278724115055713024437048832952574546581164678912794341156478859615959289720931333010836265396177238403118182219901102453660596556053537987705012972371809213618745302576874122654094213771963420178465724399112964705426548207838941065298709968044913923423922781681311806180694571535910059881703228238538782302346351472443730399075812346657046097375387076507982673848430573754749554553794234945423901111974280859817600907619255722739374513108613738135872066592727564964404002462119084702]
# == Night Time == #
e = 65537
n = 19628814650078845889624476490795800811418703155298421183649751922179289373872110164946485468758965499898659860381452920316689731813466611171330082419646032975535828938381971760997472673267667258345915647828047467420412766203712358122436358120743184983881044132767579608354023899206025747277296489890315455139161247982158229333619416375842911027431739437723838483131248360727904613423834627213036877579164949084954352768932164210879329537266501942223360207803513487189832308290555832923018589686990981697562750385892888271329399531648035355662276186237232094775404084845357101354614900716614704579902047366473325519851
ciphertext = 18231770979476945075115454933498285687471248736331968136534439886998853983159878091479109027681230666670001308495054141682281492473521819495259722942633525843224223138121210743435008344491182811096997837681349401919300801071760448609909297020846949507707329708251861866061443743942558286917774317607571379516986051564317860557772153943821431899226380831989795907857566336085097807330399388077758869632230636727348278392968946952484442630549599469645903047917899063746000458656292320802815605327181346234519795519772619774175495201258591571744214020509439053957080210165266709953654561600989486386199867341092142358249
shell = 7450311459083436799013470526820816670296314417175130490433500468646960366746415074085735399822973890608046359739147553438015771999419943640758794686461655503899174274852006852675273759918109697488252918038788275865249305840107266839320745067341253227218580768443831238305064450748932813304412926315551102620477056031794884272260575749720364002093756539399717557808977458033683588388899534871439955606629530406662400672087729944642496842353084711242911328651341343429685261174338868058208644730980459845089948243884209259777439653298562832822410224626781415627048867272937969823329086437858777995321438386601575065665
简单分析一下,题目是由两个部分组成的,首先函数 day 生成了含有五个参数的数组 ,这个参数会用到函数 night 里面参与 的计算,而 shell 与 模数的因子 相关。因此解题思路就很明确了,根据函数 day 的输出 恢复数组 ,根据 分解模数 ,最后解密 获得明文 flag。

解题步骤

首先我们看到 函数,其首先生成了 5 个大小为 的数,然后用 符号做拼接得到 。如果觉得绕,可以本地跑一下
from Crypto.Util.number import *

def day():
    print("# == Day Time == #")
    A = [getRandomRange(1 << 301 << 40for _ in '01234']

    #from notebook import pubkeys
    hint = str(A)[1:-1].replace(', ''||').encode()
    print(hint)
    # hint = bytes_to_long(pad(hint))
    # package = []
    # for pubkey in pubkeys:
    #     e, n = pubkey
    #     package.append(pow(hint, e, n))
    # print(f"{package = }")

    return A
day()
得到 b'146239978572||823596471040||1052171479378||849547394504||50672655347',多试几次可以发现字符串的长度大约为 ,对应的最多也就是 560 个比特。
随后函数下面是将 填充至 2048 比特后,使用 notebook 中的公钥对其进行加密。看到 notebook 中的公钥
pubkeys = [
    [1316966923273393034574368601955241184391111444785998466710722972275633988040568029224272430397635357872449163107278928804572765398970752644900568552514020294813546024733050135082024292481598322682990045855877556853392263676715734911232910368712575738786450510156105046776600566496799942574786503183241332740784997363514285857446938222302824964396227964711868412832852194845619628366554904150230665043909281603861298992421759553638135733037244888585600075655017766713763334284974682754159767494437867386464788270392548503256135412609157993954349845981674000072937143857040970855382655304911806719316346552101453584266121],
    [1313636547774903694433910615288816366243965221147245493790443257513469643051508482519945160993497983268746607032666514024577996510214003878851754244812785830861056511467944880656887067183093022088006603023892079757597903932697728395729605528467171403935076011715369931494813762896302405865063013876978950952553183445737415893862580946529557997177862386840671940665891984463553509323759394863514802662045074793125218445076375294720405008157895103559623204523371691063630903658360461001806917018298844432738514873530829540084732665560723768831816785580126848217585494349751859982707295270194451027637908966488433591336079],
    [1313422209706853784863425138450444393536114566510977689013118842078064352816867606066548879016746689784867031499069217146653949323203507755857385123653072875573743110808787259755688613540214185294636104765964080842615717180413731820679997453377899736419007193552970900617704671115646941207925636014254352661937769415565529244046272257822921740649781322893596978112103176487718960676212380426151079825140922318909470514158027009961239217428522970405297292867815726509360369236095377704967444339421311749405316999191339677904499413281713365474466679134722393111495793887387332928227905039036942450742103526490509249576159],
    [1321746430662648628292439055708644436184530740821098010749514133474681581832957631729292681550968108122182841907644832479495695011213810971334153360397292385819609198743433956578966857749821825621262178208409227379634952172419748956184624505995106932133301461499473823229623656490844764958301835433668618062743327682117611417235819168865744757242990985069648255779083246816509593018812991050741917153961245784296647661659339041115118272068392627299499703962645966495325055378652176922700072734325787550811454984878236039742147547963385471101805136506286953288566035101103034341742923072819774753918471775281464739904101],
    [1316012920802348742413202394765537959589119609441428117329692661212660781149297315973073063954731746455220386673231725950116051390914388279415796378305381377822621647264088603927560119754278978906758212463937071494263575443156089509654950881813861479449401068535285885349738367249035960528895049222211387021733152221289202030407416118814341241382479971018611239102343929419190892133819275458474489856666791981711793637127167775551296403296397810821548297674986394286293380472089135564385129140069501205054853729781710604489652713172579677128036322403868618295553335257593973027194532512596143733434234439677513237984107]
]
可以看到,公钥指数都是 13,但是模数不同,因此对应 RSA 低加密指数广播攻击。不过直接攻击是不行的,因为 被填充到了 2048 比特,如果公钥指数是 13,那么就需要 13 对公钥对,以及对应的密文。这里的切入点在于 pad 函数
def pad(msg):
    return msg + b'x00' * (2048 // 8 - len(msg))
pad 函数只是单纯的在 尾部加了 x00,因此根据 RSA 加密公式 ,而 可以写成 (这一部分没转过来的话可以看一下公众号文章密码学基础之进制与编码),其中  我们可以用本地生成数据测一下
from Crypto.Util.number import *

def pad(msg):
    return msg + b'x00' * (2048 // 8 - len(msg))



def day():
    A = [getRandomRange(1 << 301 << 40for _ in '01234']
    hint = str(A)[1:-1].replace(', ''||').encode()
    hint1 = bytes_to_long(hint)
    hint2 = bytes_to_long(pad(hint))
    print(hex(hint2//hint1))

    return A
day()
多测试几次,得到的结果大约 是 0x1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 左右,为了具有普适性,我们可以稍微地减少一点,比如去掉两个或者四个 0,设为
这样我们就可以先对密文进行处理
而由于 约为 560 比特, ,即可使用中国剩余定理恢复 ,(这一部分没转过来的话可以看一下公众号文章密码学基础之数论四大定理密码学攻击之RSA:初见)从而获取数组 的内容。
有了 之后,我们需要根据 恢复分解 ,其中
    core = getRandomRange(1 << 701 << 80)
    box = (A[4] * p ** 4 + A[3] * p ** 3 + A[2] * p ** 2 + A[1] * p ** 1 + core) % n
    shell = (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0]) % n
这里我们注意到,由于 ,因此
而由于 只有 比特,因此我们可以使用 copper 在模 p 下解出小根 ,有了 ,加上 ,根据

所以有

因此直接计算 即可分解模数 ,从而解密密文获得 flag 了。

解题脚本

sagemath

from Crypto.Util.number import *
from gmpy2 import *

package = [113482755921727894308026323987153978319294565921297271483503416958220979227455466341038953971142407801194920978797098743417339981893147012208196020869891703956656942161446114516952107767882087255173217104964011096149897297832802098065132988517744007058222745700421282973366796155355692957250370510092219668829076067419106719838118353533105536795546563225102470124656128420555835303548251644405567250663514292418353945793928921219377444443247235090395933205200737624794054876786142356580101093438687722110708745008348200055579249447661754452275920869977866016001411727295433260220398972792153602104752222053141997523581181704751408375002844330657316129196030300245827671668820158728499267585417825018569561334260339645149505349602101894361868409619377485151337734378552337306663742215652984335664043851491714700766298936643295134007324757334709142247834367568787252410245281239196385617941221491410681741562061388682740552670933412215721826425341213894797885977145778813538119439614438661162793551999033030915461280326437327647252386377675712448950720674489587870913633918955142281475292038369771921226182094311337006742311879487157059658323269406711930393651649183019074679828192369313690126822098229262672881505158783968273350158299731314276956390740076466256878275236320446242001677250017312467314633692008900452507388981554258738225814057234459262160994532764706553075132444786132482533979413628488907290918756158936432881811263532942710639129912080296288963809288780983205098910447284145427055829967749911481160511621578484216430822108678492066277579415962030467996551230064062844980094241076379709277711327063998892890858114473339807447673678894643645195719650144352817184953387528965217770702858803278617781563984246430332884800563229284492104255853809754867592878818776361873642996662077628287052362360710454507672539465240674401385279529963043345060634868343217881273515503289974894457362066685037297545772310131198850220025672843957153107490874807599311288876818421468275658855183857485067696603798636556327070411528170381402923911922437076616994460720931230980991440337397730061039967493443152767007916713160518618697678791358770766857737217910848181657393760417031865203943283074078341988117567851667858026108335625589177179258992930648353570238327435125409871028669479754623782967450462280802423233657422873275069133939005033872391235288329468886849808534906305377008408076775145268714146937205940659708210819711903273898505450411746796296074348301840443689229715602713064347690095007369004049337459458047359544160409565437783924368962797071453687950582019132146435134269723546824657132278724115055713024437048832952574546581164678912794341156478859615959289720931333010836265396177238403118182219901102453660596556053537987705012972371809213618745302576874122654094213771963420178465724399112964705426548207838941065298709968044913923423922781681311806180694571535910059881703228238538782302346351472443730399075812346657046097375387076507982673848430573754749554553794234945423901111974280859817600907619255722739374513108613738135872066592727564964404002462119084702]
pubkeys = [
    [1316966923273393034574368601955241184391111444785998466710722972275633988040568029224272430397635357872449163107278928804572765398970752644900568552514020294813546024733050135082024292481598322682990045855877556853392263676715734911232910368712575738786450510156105046776600566496799942574786503183241332740784997363514285857446938222302824964396227964711868412832852194845619628366554904150230665043909281603861298992421759553638135733037244888585600075655017766713763334284974682754159767494437867386464788270392548503256135412609157993954349845981674000072937143857040970855382655304911806719316346552101453584266121],
    [1313636547774903694433910615288816366243965221147245493790443257513469643051508482519945160993497983268746607032666514024577996510214003878851754244812785830861056511467944880656887067183093022088006603023892079757597903932697728395729605528467171403935076011715369931494813762896302405865063013876978950952553183445737415893862580946529557997177862386840671940665891984463553509323759394863514802662045074793125218445076375294720405008157895103559623204523371691063630903658360461001806917018298844432738514873530829540084732665560723768831816785580126848217585494349751859982707295270194451027637908966488433591336079],
    [1313422209706853784863425138450444393536114566510977689013118842078064352816867606066548879016746689784867031499069217146653949323203507755857385123653072875573743110808787259755688613540214185294636104765964080842615717180413731820679997453377899736419007193552970900617704671115646941207925636014254352661937769415565529244046272257822921740649781322893596978112103176487718960676212380426151079825140922318909470514158027009961239217428522970405297292867815726509360369236095377704967444339421311749405316999191339677904499413281713365474466679134722393111495793887387332928227905039036942450742103526490509249576159],
    [1321746430662648628292439055708644436184530740821098010749514133474681581832957631729292681550968108122182841907644832479495695011213810971334153360397292385819609198743433956578966857749821825621262178208409227379634952172419748956184624505995106932133301461499473823229623656490844764958301835433668618062743327682117611417235819168865744757242990985069648255779083246816509593018812991050741917153961245784296647661659339041115118272068392627299499703962645966495325055378652176922700072734325787550811454984878236039742147547963385471101805136506286953288566035101103034341742923072819774753918471775281464739904101],
    [1316012920802348742413202394765537959589119609441428117329692661212660781149297315973073063954731746455220386673231725950116051390914388279415796378305381377822621647264088603927560119754278978906758212463937071494263575443156089509654950881813861479449401068535285885349738367249035960528895049222211387021733152221289202030407416118814341241382479971018611239102343929419190892133819275458474489856666791981711793637127167775551296403296397810821548297674986394286293380472089135564385129140069501205054853729781710604489652713172579677128036322403868618295553335257593973027194532512596143733434234439677513237984107]
]

n = []
for each in pubkeys:
    n.append(each[1])

pads = 0x1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

c = []
for index in range(len(package)):
    c += [int(package[index] * pow(pads,-13,n[index]) % n[index])]

hint = crt(c,n)
hint = long_to_bytes(iroot(hint,13)[0])
A = [646919678902,598613162045,90472013741,917100488664,838250498519]
n = 19628814650078845889624476490795800811418703155298421183649751922179289373872110164946485468758965499898659860381452920316689731813466611171330082419646032975535828938381971760997472673267667258345915647828047467420412766203712358122436358120743184983881044132767579608354023899206025747277296489890315455139161247982158229333619416375842911027431739437723838483131248360727904613423834627213036877579164949084954352768932164210879329537266501942223360207803513487189832308290555832923018589686990981697562750385892888271329399531648035355662276186237232094775404084845357101354614900716614704579902047366473325519851
shell = 7450311459083436799013470526820816670296314417175130490433500468646960366746415074085735399822973890608046359739147553438015771999419943640758794686461655503899174274852006852675273759918109697488252918038788275865249305840107266839320745067341253227218580768443831238305064450748932813304412926315551102620477056031794884272260575749720364002093756539399717557808977458033683588388899534871439955606629530406662400672087729944642496842353084711242911328651341343429685261174338868058208644730980459845089948243884209259777439653298562832822410224626781415627048867272937969823329086437858777995321438386601575065665
ciphertext = 18231770979476945075115454933498285687471248736331968136534439886998853983159878091479109027681230666670001308495054141682281492473521819495259722942633525843224223138121210743435008344491182811096997837681349401919300801071760448609909297020846949507707329708251861866061443743942558286917774317607571379516986051564317860557772153943821431899226380831989795907857566336085097807330399388077758869632230636727348278392968946952484442630549599469645903047917899063746000458656292320802815605327181346234519795519772619774175495201258591571744214020509439053957080210165266709953654561600989486386199867341092142358249

R.<box> = Zmod(n)[]
f = (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0]) - shell
core = f.monic().small_roots(X=2^80,beta=0.4,epsilon=0.02)[0]


core = 72398025613557274548283
box = core
ff = shell - (A[4] * box ** 4 + A[3] * box ** 3 + A[2] * box ** 2 + A[1] * box ** 1 + A[0])
p = int(GCD(ff,n))
q = int(n//p)
phi = (p-1)*(q-1)
e = 65537
d = inverse(e,phi)
m = pow(ciphertext,d,n)
print(long_to_bytes(int(m)))

得到 b'Your flag is: flag{8d24d7d491106a7974d5afe9342b2834}



原文始发于微信公众号(Van1sh):2023 江苏省首届数据安全竞赛

版权声明:admin 发表于 2023年9月17日 上午11:22。
转载请注明:2023 江苏省首届数据安全竞赛 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...