20210529-DASCTFxBUUOJ五月大联动-CryptoSecPartWrtieUp

Posted on 2021-10-08 Edited on 2022-09-10 In CTF-Crypto , WriteUp Views: Symbols count in article: 24k Reading time ≈ 21 mins.

Fibonacci

题目描述

# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from gmpy2 import *
flag='flag{*************************}'
m=bytes_to_long(flag)


def F(n):
    if n == 1 or n == 2:
        return 1
    return F(n - 1) + F(n - 2)


for _ in range(3):
    p=getPrime(8)
    q=getPrime(1024)
    n=p*q
    F=F(n)
    c=pow(m,65537,F)
    print ('n = %d'%(n))
    print ('F(n) = %d'%(F))
    print ('c = %d'%(c))

'''
n = 30039002188673063651200304724856649750424855614713561659816258454033925531379709006718595334296516241593158998074215212142272196270365664747873959581114872378007750905526355257967620809790424857457592189785708634246739647422565451143815984036502331156971328504879840492056807034649796388685443055568787638373563
F(n) = 36700337315478358423302463804643502364132894595387679831392170242048570294154137205916046749632259595443511772051005890145681246611711817441148722686433058905309178967626876196428817911402628279151882749816176290631663850711266005570519120688501046610172118214633159846090742563888545000820131558915392759986137704413717356161549696109102298045171982651759736931461029700093546074544216714411268154766313965335118439291477901688458760307733751977411099481922798986947005456033024215394531788003343093192780270571980899284495530589488614458267489897774350955741276841747926401364869628844871476483816139224540693572750083532852690939679488779770278121521966166639184387859708670915429469804929002101080867694318638835470062005769336931710061708165085286293560882862673863182161513175108975599928164057840378446866053785509135134250439675861761412916432659950998041079347609299108756058982586701419597870024243472621875398244582253182771532237956030075796524234449649579003219049
c = 5149579488901718498256373861975221458889060262051324713153792274531569740959338672159468511041469512968513162060650323314015111729630790249929764405001469068728832250672432536655958494683225528045534739312500520653653926107616626321646038503307002215682827882897681738805565989931916973526625237494508575698650414426281874530049741540818321302625573676530536769431267223818807952634410781018835593002628264062168865877875709419051886274533984009771861504132373726000546543208681246415153517353772565209140561174813777886487077708362479762600413004602240042298109893816953817393105259401510845057279294044756541864350957113952935658077279981571022227194710269040317178329523984989277421087981594122731035549685470894608888049815174440061043045638797036874542111575347820490125255592416295645107767029867230219384632544284156692872055786752135888144873738488840255388898851551453544530082551649823629868841430161794325580654855230486824210856918330348898081161664747016870749921
n = 20756277616755836861796337131683494338352701206928094011019872107808330954223862907177555525893261715593610455375647872190101833907080699823790147515155417500649420182409578349022597139001229776650770207829659368291648098353474620323733162983388953788239424626462428488411835382477744747369092196172727799468129
F(n) = 73745878045934636387896195274069826551569516766963182339313590908194755029865664679120132471843611642027469204171633501721641080925317635658799561477123939207311526297390646712571316606381873782191178958234889168599083479590822672109275622907151415552207811665808203751267410151224170154736841450903230193274146578562848780223022725054392389915985290416059522271191922854734627854849084277940339695243325424932830011581455271309868481867791848671985869262214017536640985196012788793460756899871516178490553441223897250090614367273308559864669269965578509523152119870676641602044879271520652270508502838994825168113044092631541016378753797168654004397854528716878554680966919397339024634461107466963998140873416841269245629405227723896214356538994142798927935847118081299628628813983021407779086407107873835131175157418129203731497042769363491200520978441329400751265966093987214492433690588592278950077342020700742819163199408329926294779182691364743193734488228719
c = 5893676968379648852677257584942191109596695953257511502221493623707657958793151928063695511404323761502093871747314475680963368412056002167272056988434183588136518540030328900237814175026374170035752147457944130025788557913749495512316872731640598728203711834687604349623497761823630666336599012384701148134898626277451946739191645056229526840490101366707716010899628734677395956010814780086058428182227433879240458756480238286363782312887091585752283137070930652073681891561066188131229432708558323016170835880200185835314330898745048592325798107333894598294876001536344275083054913481975007098183772410065580414486344966276992142840553960291265334551415769700709112077959058690472699228393932778693676888105307493544864165340738016954896582284163878309410561472175085522432252484026380738098291004277354471010420592137620174716251226560188793137038378169674648650109100511358090004029326014324282641470675210622193652390362972072927753788251933923336522541020538
n = 23691611795512881548876576490920777356012500842496810447368465555253207159934330531730113872431842020621324344446142448954349963332039143377219840904377051014940314330764948944111930704132580375788932310940376348012980840541573284360163056070088226098587825855247120630453584914813593602869923553994121677913829
F(n) = 9354120234373821188002721174172376187851074553842250946994966454521076364770447254561289329644492544492363073660918209867635665556179493971516453831575577085229601305613934033279832212516762995062790158649731235328923025944567754094837437882988453755837757140503680845082446605924488438186342529892438539978025244619294478667640323307281530468578326413724432442367286795555698768396763148070646067431485983937912884160277380848384622618517411849896779104223556934427313741222400162647303864273804545658096365574243669367638797710979775090679277794669009497301787205587916669811596486681600927221914751277959719025890975947906807551671033707046998050580404291266129815613731776357171701993365320613177014644670728884401252046842886254766791009584832861321307145962353061550438485818190867215102212015602783104130507243211654301408379888922865198634687009616395466846020452426608653076648665616711357303753242673389482755201639605067581161306428053985480749
c = 5527295227051355798054266434992298352109856653351231751774366060474987674395801103779017995136358984850596693033786379284945829600181195650018576473832122123689374306357799469703873467631828582340852591088516097040696492555053370228278729688979599727840615379716837557947979105109295383721874687464666950312431293310758869315198932080703658526964530199675712576963592684818247111162090363056774275409164410925950049724140156220797817319956734605599349828169364123443161210061751433895202659075589086208524908238147473041649043519688635549021052796213275288198028578858764052136199721656697612607002863436475864686744976361468007786764828741313027638038039869019572535344397813504142312113571484580538973034322648843004665888312135523153988203801290669186909018156540165112741651436700837185946879899717245458101182522362705139925914797396797181901663790903646171709744845258954151859189108531243389446981087547490853432279034430995853488274409450850672046
'''

题目解析

看了题目，发现是将Fibonacci数列中的三个数作为模数了，第一时间想到的就是典型论文题，于是我直接baidu，发现了题目的出处

摘要里说，这样子RSA加密是很容易被攻击的

第一点是说，如果用来作为模数n的斐波那契数在斐波那契序列中是排偶数位，那么这个n就可以分解成一个斐波那契数和一个卢卡斯数

但这不是我们所需要的，因为题目里的n都是奇数

唯一找到有用一点的信息就是，

第$r$位置的斐波那契数$U_r$和第$s$位置的斐波那契数$U_s$，如果$r$整除$s$，则$U_r$整除$U_s$

题目所给的数据也确实能$P_i$被整除，但若是要完全分解还是不太行

这里还说上面那个是充要条件

然后发现题目给的斐波那契数是错误的，和正确的数差太多

看了wp后发现这道题简单应用下中国剩余定理就能出

推理如下

已知（注意这里的$F(q_i)$并不是完全分解）
$$
\begin{cases}
c_1=\ m^e\ mod\ F(p_1)\times F(q_1)\\
c_2=\ m^e\ mod\ F(p_2)\times F(q_2)\\
c_3=\ m^e\ mod\ F(p_3)\times F(q_3)
\end{cases}\notag
$$
由同余的性质可知，在模$F(p_i)$的情况下也是成立的
$$
\begin{cases}
c_1=\ m^e\ mod\ F(p_1)\\
c_2=\ m^e\ mod\ F(p_2)\\
c_3=\ m^e\ mod\ F(p_3)
\end{cases}\notag
$$
这时的解密就是，为了避免混淆，我这里完全分成三个加密了，它们都是类似的，举第一个为例
$$
m_1=\ c_1^{d_1}\ mod\ F(p_1)\notag
$$
而$m_1$都满足
$$
m\equiv\ m_1\ mod\ F(p_1)\notag
$$
但是因为$m_1$求出来太小啦（毕竟是在模$F(p_1)$下，原来可是在模$F(p_1)\times F(q_1)$下的），如果m比任意的$F(p_i)$都大，那么求出来的$m_i$都只不过是m在模各自$F(p_i)$的一个剩余类罢了，这样解出来的$m_i$就是不对的

那应该怎么办呢？

中国剩余定理

这就要引入中国剩余定理CRT这个概念了，它的原本是用来解同余方程的，但是求出来的解是在模所有模数之积的情况下的，所以假设所有模数之积为N，只要明文m是在$\mathbb{Z_N}$中的，就可以做到——完全求解；但是如果不成立只能求出一个与m在模N同余的剩余类，并不是真的解

这就是我们的思路，因为我们手头上就只有三组解，可能将模数给扩大到$F(p_1)\times F(p_2)\times F(p_3)$，如果凑巧，m比这个乘积要小，就能求出来了，如果还不行，说明题目给的m比较大，也就是flag比较长，只能继续分解$F(N_i)$，构造更多同余方程，直到模数之积大于flag转变成的m

也就是用这个
$$
\begin{cases}
m_1=\ c_1^{d_1}\ mod\ F(p_1)\\
m_2=\ c_2^{d_2}\ mod\ F(p_2)\\
m_3=\ c_3^{d_3}\ mod\ F(p_3)
\end{cases}\notag
$$
推导出的
$$
\begin{cases}
m\equiv\ m_1\ mod\ F(p_1)\\
m\equiv\ m_2\ mod\ F(p_2)\\
m\equiv\ m_3\ mod\ F(p_3)
\end{cases}\notag
$$
解同余方程，看看出来的是不是flag

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from gmpy2 import *
from libnum import *


def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)


def fibonacci_2(n):
    if n == 1 or n == 2:
        return 1
    else:
        a = 1
        b = 1
        c = 0
        for i in range(n - 2):
            c = a + b
            a = b
            b = c
        return c

def crt(ci, ni):
    # 检查是否有解，有解的条件，ni都互质
    for i in range(len(ni)):
        for j in range(i + 1, len(ni)):
            assert gcd(ni[i], ni[j]) == 1
    assert len(ci) == len(ni)

    _N = reduce(lambda a, b: a * b, ni)
    x = 0
    for i, j in zip(ci, ni):
        _Ni = _N // j
        _Ni1 = invert(_Ni, j)
        x += i * _Ni * _Ni1
    return x % _N


e = 65537
n1 = 30039002188673063651200304724856649750424855614713561659816258454033925531379709006718595334296516241593158998074215212142272196270365664747873959581114872378007750905526355257967620809790424857457592189785708634246739647422565451143815984036502331156971328504879840492056807034649796388685443055568787638373563
F1 = 36700337315478358423302463804643502364132894595387679831392170242048570294154137205916046749632259595443511772051005890145681246611711817441148722686433058905309178967626876196428817911402628279151882749816176290631663850711266005570519120688501046610172118214633159846090742563888545000820131558915392759986137704413717356161549696109102298045171982651759736931461029700093546074544216714411268154766313965335118439291477901688458760307733751977411099481922798986947005456033024215394531788003343093192780270571980899284495530589488614458267489897774350955741276841747926401364869628844871476483816139224540693572750083532852690939679488779770278121521966166639184387859708670915429469804929002101080867694318638835470062005769336931710061708165085286293560882862673863182161513175108975599928164057840378446866053785509135134250439675861761412916432659950998041079347609299108756058982586701419597870024243472621875398244582253182771532237956030075796524234449649579003219049
c1 = 5149579488901718498256373861975221458889060262051324713153792274531569740959338672159468511041469512968513162060650323314015111729630790249929764405001469068728832250672432536655958494683225528045534739312500520653653926107616626321646038503307002215682827882897681738805565989931916973526625237494508575698650414426281874530049741540818321302625573676530536769431267223818807952634410781018835593002628264062168865877875709419051886274533984009771861504132373726000546543208681246415153517353772565209140561174813777886487077708362479762600413004602240042298109893816953817393105259401510845057279294044756541864350957113952935658077279981571022227194710269040317178329523984989277421087981594122731035549685470894608888049815174440061043045638797036874542111575347820490125255592416295645107767029867230219384632544284156692872055786752135888144873738488840255388898851551453544530082551649823629868841430161794325580654855230486824210856918330348898081161664747016870749921

n2 = 20756277616755836861796337131683494338352701206928094011019872107808330954223862907177555525893261715593610455375647872190101833907080699823790147515155417500649420182409578349022597139001229776650770207829659368291648098353474620323733162983388953788239424626462428488411835382477744747369092196172727799468129
F2 = 73745878045934636387896195274069826551569516766963182339313590908194755029865664679120132471843611642027469204171633501721641080925317635658799561477123939207311526297390646712571316606381873782191178958234889168599083479590822672109275622907151415552207811665808203751267410151224170154736841450903230193274146578562848780223022725054392389915985290416059522271191922854734627854849084277940339695243325424932830011581455271309868481867791848671985869262214017536640985196012788793460756899871516178490553441223897250090614367273308559864669269965578509523152119870676641602044879271520652270508502838994825168113044092631541016378753797168654004397854528716878554680966919397339024634461107466963998140873416841269245629405227723896214356538994142798927935847118081299628628813983021407779086407107873835131175157418129203731497042769363491200520978441329400751265966093987214492433690588592278950077342020700742819163199408329926294779182691364743193734488228719
c2 = 5893676968379648852677257584942191109596695953257511502221493623707657958793151928063695511404323761502093871747314475680963368412056002167272056988434183588136518540030328900237814175026374170035752147457944130025788557913749495512316872731640598728203711834687604349623497761823630666336599012384701148134898626277451946739191645056229526840490101366707716010899628734677395956010814780086058428182227433879240458756480238286363782312887091585752283137070930652073681891561066188131229432708558323016170835880200185835314330898745048592325798107333894598294876001536344275083054913481975007098183772410065580414486344966276992142840553960291265334551415769700709112077959058690472699228393932778693676888105307493544864165340738016954896582284163878309410561472175085522432252484026380738098291004277354471010420592137620174716251226560188793137038378169674648650109100511358090004029326014324282641470675210622193652390362972072927753788251933923336522541020538

n3 = 23691611795512881548876576490920777356012500842496810447368465555253207159934330531730113872431842020621324344446142448954349963332039143377219840904377051014940314330764948944111930704132580375788932310940376348012980840541573284360163056070088226098587825855247120630453584914813593602869923553994121677913829
F3 = 9354120234373821188002721174172376187851074553842250946994966454521076364770447254561289329644492544492363073660918209867635665556179493971516453831575577085229601305613934033279832212516762995062790158649731235328923025944567754094837437882988453755837757140503680845082446605924488438186342529892438539978025244619294478667640323307281530468578326413724432442367286795555698768396763148070646067431485983937912884160277380848384622618517411849896779104223556934427313741222400162647303864273804545658096365574243669367638797710979775090679277794669009497301787205587916669811596486681600927221914751277959719025890975947906807551671033707046998050580404291266129815613731776357171701993365320613177014644670728884401252046842886254766791009584832861321307145962353061550438485818190867215102212015602783104130507243211654301408379888922865198634687009616395466846020452426608653076648665616711357303753242673389482755201639605067581161306428053985480749
c3 = 5527295227051355798054266434992298352109856653351231751774366060474987674395801103779017995136358984850596693033786379284945829600181195650018576473832122123689374306357799469703873467631828582340852591088516097040696492555053370228278729688979599727840615379716837557947979105109295383721874687464666950312431293310758869315198932080703658526964530199675712576963592684818247111162090363056774275409164410925950049724140156220797817319956734605599349828169364123443161210061751433895202659075589086208524908238147473041649043519688635549021052796213275288198028578858764052136199721656697612607002863436475864686744976361468007786764828741313027638038039869019572535344397813504142312113571484580538973034322648843004665888312135523153988203801290669186909018156540165112741651436700837185946879899717245458101182522362705139925914797396797181901663790903646171709744845258954151859189108531243389446981087547490853432279034430995853488274409450850672046

p1 = 251
q1 = 119677299556466389048606791732496612551493448664197456812016965952326396539361390465014324041021977058140075689538706024471203969204644082660852428610019411864572712771021335689114027130639142858396781632612384996998962738735320522485322645563754307398292145437768288812975326831274089197949972332943377045313
p2 = 197
q2 = 105361815313481405389829122495855301209912188867655299548324223897504218041745496990749012821793206678140154595815471432437065146736450252912640342716524961932230559301571463700622320502544313587059747247866291209602274610931343250374280015144106364407306723992195068469095611078567232220147676122704202027757
p3 = 149
q3 = 159004106010153567442124674435709915141023495587226915754150775538612128590163292159262509210951959869941774123799613751371476263973417069645770744324678194731143049199764758014174031571359599837509612825103196966530072755312572378256127893087840443614683395001658527721164999428279151697113580899289407234321

assert p1 * q1 == n1
assert p2 * q2 == n2
assert p3 * q3 == n3

p = [fibonacci_2(p1), fibonacci_2(p2), fibonacci_2(p3)]
f = [F1, F2, F3]

p11 = 582416774750273
q11 = 21937080329465122026187124199656961913

p22 = 15761
q22 = 25795969
r22 = 227150265697
s22 = 717185107125886549

p33 = 110557
q33 = 162709
r33 = 4000949
s33 = 85607646594577

phi1 = (p11 - 1) * (q11 - 1)
phi2 = (p22 - 1) * (q22 - 1) * (r22 - 1) * (s22 - 1)
phi3 = (p33 - 1) * (q33 - 1) * (r33 - 1) * (s33 - 1)

d1 = invert(e, phi1)
d2 = invert(e, phi2)
d3 = invert(e, phi3)

m1 = pow(c1, d1, p[0])
m2 = pow(c2, d2, p[1])
m3 = pow(c3, d3, p[2])

print(long_to_bytes(crt([m1, m2, m3], p)))

1	flag{40491b82090cc75e56ce5196dc1b91e8}

参考[DASCTF X BUUOJ 五月大联动] 个人（or团队）writeup

一个简单的性质及证明

若$(m, n)=1$，则
$$
a\equiv b\ (mod\ m),a\equiv b\ (mod\ n)\Leftrightarrow\ a\equiv b\ (mod\ mn)\notag
$$
证明：

$\because a\equiv b\ (mod\ m),\ a\equiv b\ (mod\ n)$

$\therefore m|(a-b)且n|(a-b)\notag$

由FTA（算数基本定理）可知，m可以唯一分解成
$$
m=m_1\times m_2\times\ …\times m_i\notag
$$
同理，
$$
n=n_1\times n_2\times\ …\times n_i\notag
$$

而且$(m,n)=1$，也就是说集合${m_1,\ m_2,\ …,\ m_i}$和集合${n_1,\ n_2,\ …,\ n_i}$中的元素，两两不相同
$$
\therefore mn|(a-b)即a\equiv b\ (mod\ mn)\notag
$$

这里还用到了同余关系的等价表达式

其实不需要三组，两组也行，不过必须是$F(p_i)$想乘大于m的情况，因为中国剩余定理的一种用法，我的理解是扩大模数，只能求出$m\ mod\ F(p_1)F(p_2)F(p_3)$是吧，但如果m本身就比$F(p_1)F(p_2)$小，当然可以只用CRT求解前面两个组成的同余方程；这就和模数不够再分解构造反过来了

据结果返回，我们发现

misc

彭总给的一道misc，最后一步是rsa

这个网站可以对这个文件的格式进行解析，https://www.ssleye.com/priv_get.html

解析出来是

n = 19298383934402303776125763032487034395837290787269136241860929371666322803767005809256376467251747337544207987651243732876788723589391443122139006291670739679671881793995062117862054219773720641070620393257280059636631655606299095240092759065646066472874883103079707806412908225076882298697592818427957280248310545565886424283345305315588905456274845835539850117078894827271423187201674309901517200507605514506810554986443591457553871395991374493663775609810305552059745143075621932565847065010052223136631616841830344641425039696588885154977303322142305642341212151656150304867047412766712682132001889777020524791973
e = 65537
d = 3137235186797109181543919913150081090883783146124561354971792140710331616511797608859383781407450999194287072957815443643580070206469268276290781894677206166703148277053014202720636062948704086393432559771778716684753248681348101998686974611065401104750125952976352395891223648167738895743231363772089916593108326960368256904683762740112717950191378373879647606045501882017215733660352686694405659463412799487222511524326086693134712754258387193963090680988416969472940644308784344753494344590799813350562816191244386991480741139476116903925249873160845868063446516486452687657008647635622012862948358441702637219329
p = 139731890355244444444481193351254240382046157745753107784168081259905132570466329632284952677745944718796408024129423905064872080575084258263419439079106234950631002219878620094334031716695105950708580750238041143435139361782342237330225211801270672585910851695391826655791509425136418067722676156822188664897
q = 138110089868099985112598225976416346201381948401336998275010504058986842232246648573037043751233266052881639193423727942204630085471488139402695765255520423890781964577838337616082316055958265340997629227918247719815192989410797326080614722191761865261768884814085886604594016717232369095342986175683061540709

然后猜测data就是密文，然后常规解密只出来一半，另一半应该是与sign有关

看了套神的博客

其实就是用$e$验签了
$$
m=sign^e\ mod\ n\notag
$$
20210529 DASCTFXBUUOJ五月大联动-d388a46f.png