2022DASCTF Apr X FATE 防疫挑战赛

easy_real

import random
import hashlib

flag = 'xxxxxxxxxxxxxxxxxxxx'
key = random.randint(1,10)
for i in range(len(flag)):
	crypto += chr(ord(flag[i])^key)
m = crypto的ascii十六进制
e = random.randint(1,100)
print(hashlib.md5(e))
p = 64310413306776406422334034047152581900365687374336418863191177338901198608319
q = xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
n = p*q
c = pow(m,e,n)
print(n)
print(c)

签到题。由于key和e的范围都比较小，无脑爆破就行了。

import gmpy2
from Crypto.Util.number import *

e_hash = '37693cfc748049e45d87b8c7d8b9aacd'
n = 4197356622576696564490569060686240088884187113566430134461945130770906825187894394672841467350797015940721560434743086405821584185286177962353341322088523
c = 3298176862697175389935722420143867000970906723110625484802850810634814647827572034913391972640399446415991848730984820839735665233943600223288991148186397
p = 64310413306776406422334034047152581900365687374336418863191177338901198608319
q = n//p
assert p*q == n
for i in range(1,101):
	if hashlib.md5(str(i).encode()).hexdigest() == e_hash:
		e = i
		print(f'e = {e}')
		break

d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
crypto = long_to_bytes(m)
for cnt in range(1,11):
	txt = ''
	for i in range(len(crypto)):
		txt += chr(crypto[i]^cnt)
	print(txt)

special_rsa

from Crypto.Util.number import *

def getPrime1(bitLength, e):
    while True:
        i = getPrime(bitLength)
        if (i - 1) % e ** 2 == 0:
            return i
flag=b'DASCTF{????????????????????}'
m = bytes_to_long(flag)
lenth = ((len(bin(m)) - 2) // 2) + 9
e=113
p = getPrime1(lenth, e)
q = getPrime1(lenth, e)
n=p*q
print(f"n = {n}")
c1 = pow(m, e, n)
for i in range(26):
    lenth = ((len(bin(c)) - 2) // 2) + 9
    p = getPrime1(lenth, e)
    q = getPrime1(lenth, e)
    n=p*q
    print(f"n = {n}")
    c=pow(c,e,n)
print(f"e = {e}")
print(f"c = {c}")

尝试将n进行分解，发现所有n都可以分解。但是主要问题来了，发现$gcd(e,p_i-1)=e,gcd(e,q_i-1)=1$，这让我想到了BUU上的一道题[NCTF2019]easy rsa。利用AMM算法进行开根。由于每次开根会得到113*113种情况，需要进行筛选（利用$ c_i < p_{i-1}q_{i-1}$）。

真没想到可以直接用small_root代替AMM算法（再次看了之前的参考文章，发现里面有说这个的）。

当然应该还有另一种方法（比赛时想到的方向，但是不会写代码，淦！）。

117.pdf (iacr.org)

进行了测试，发现，$p,q$都符合该情况（即 $(q-1)%r=0$ ）。不过我并没有成功实现。(如有不对的地方，烦请斧正)

#sage
from libnum import n2s

e = 113
c = 1028324919038104683475485759234995158466543298184637219012354053883391759172761125802189697762778242175407876548832454351014064525118465877297277847501477586955680645311999174005606833294172830817159
ps = [953730950786751671162019537171974567, 232079231415308325450092906880606082069, 88067722275537586769787599991567203589751, 24335212484189159197840692460327461505035059, 7832299017937880395583715032476962329929226581, 1656848589754467667368312855929759764100120657831, 385788223643735590500185001710758495904528462058461, 135813272566456906193934636644217527100917542578856697, 37185691759470013533730603170661686570987787098353146897, 6623023178993627032758350846838617937710601663528839184727, 954412804126450754097808991490470782833291028309980575506163, 350121371461894793578110243222665782247737840410076591434903787, 66882708962198932251728043152245270662769508317424500666902658099, 43449898447639409732732812916430042263570178747794530133229640125923, 11136261905010083405430254612464029672882837025885682392810368001188527, 2623629589005115152329094552749299711026240699896424120660145647226563547, 262775599542220820608778738911414710660835549772895468394761119434220071003, 102366458668689911004027849640392002821642295855327735994412634235696717329671, 15874438801602936764330936047390981280096007684699625987478211613419079727910193, 4479430800690915874719403516331677127806963529247809966024777708496270901092401687, 1328165608715012145707239303399129070657427496129541416861187541092152796676371237057, 368461902207817023013078031477042541053987571003677386333567043030477451518424731838173, 206721456778089912780641186795393376537372828449722520397829606593267585681448641482345737, 43870497594014737833600078975099212558645315030912084285417550950854483979406797450479252891, 14702310219802004876082313481498680940324963613770096574742182597840558294030859405666549879531, 5952590790902091635268726673538951527433355660839816621733964706901441977862333411532558667717227, 978009050697262759337388871320370165458800566798280419667959552859180906066907114053826258140106617]
qs = [1189933229053113361422958527792232151, 295185057334340451492588650872876746227, 88380889077762105057154017276462714444697, 43974782968656404951924524450501283426052127, 10726403821316775206273675267109184566904426261, 2714357008989072105081411295741540337141142641741, 576581905150085393327734090419529952232186498060949, 140758317578347635848563045232314610161039815135897421, 41680117092754807988080699273322244961911189757589699867, 9419832152875820180139633405089278278408407453522978357309, 1567597041534155679238655992215022394597376421096298363211067, 367712839396521757736384350030802803477965822058616833553305103, 103424977238409568447978495499643051307907366367259219393937014631, 46014074200352892806829193743016415423205917845271691428043440245531, 12445294229358634680867170058509842935273054334385354032543323581223253, 3200631836176555526009533059891690177091538103904679780020639896015937897, 317277895959173163347650321012213555955385929418622006880521870012130207557, 104379442774418262390337411577160146519860415840398189010112686742489182665577, 26984206512970181742033712455904984758134288864531714209886622060356697128804201, 5467527956822382309398095704409409074818664888285375307055715842283183939297839923, 1692196606246085729483398884059069884182535824953762329164855466589577530953493347747, 428750921047556327595864876619292414694543668237320723518704707914310601565770504401619, 212549643149353357950643557614966235999942509894271006476145929120541407503538644651435909, 59471978701477648587546053450213894562580907285714122639903144859545186463681183925646967041, 15115713372931874518523751684548940147062395364112500028355694776530968944848166318295947674571, 7541333580839789645678699855290145212677767915429008863004397257213367753100058966625356835737037, 1086686910531802445146659484012613083647370307628438760118376029969836222533970554565751069314622539]
ns = [1134876149917575363176366704410565158549594427794901202977560677131703617, 68506321231437453734007374706367120760326482177047006099953454136095248103663, 7783503593765446343363083302704731608384677185199537317445372251030064778965500447, 1070135687488356161164202697449500843725645617129661751744246979913699130211505096520493, 84012402115704505952834528733063574032699054524475028392540927197962976150657887637275643641, 4497278582433699034700211877087309784829036823057043402314297478185216205338241432310114079123771, 222438508972972285373674471797570608108219830357859030918870564627162064662598790037437036093579139489, 19116847751264029874551971240684579996570601026679560309305369168779130317938356692609176166515369250878437, 1549903986709797721131070830901667744892392382636347158789834851868638863292232718716074359148785900673192362699, 62387766690725996279968636478698222263235233511074646032501495855928095611796694112573478405813305623307157261619643, 1496134688150941811618178638810353297864345150241986530472328508974364124440160181353848429438725939837967063441528305921, 128744123633657656499069966444992201456797762973822340505291131642660343436783413140023509983315177426811890315424928661125061, 6917342652058596217869122177298094984415751234677039849514181349685079073411591975537016273056773954075238307918266361998553646469, 1999306851167477770905800721615579416365273707414308684419794311809177595829473632853128686208533753019224536487399393397120864878000113, 138594056023048386926766329537127538558164718841925506735112367176642328352257472034381662493666299220910783237918231719166519833124529218331, 8397272388904583425531462714999219642572091279898695377838194583995214737828538895164195817973441184775814069396690436662985593377966417476040659, 83372889332166088651413254885376085265561130214754686361784964744744711092668473281132249352040520639092871294276293287744276919265091479681667169671, 10684953914628370830889219903654707140968094024767031366624595731918523435466123514094659595357231410471738736952266383928737163485550013190959149252435167, 428359134899960532964729749713513106760306719712194950954567619156985067322564731294653991204666853689688900339268764469280769569535109069729404621290809120793, 24491413133428851306933688733518898516890217803647806829002775935975741568422047344206442746983871735723486865901743352102305801200224958166496937663406627341150101, 2247517335600310176909964109060502815240207684510918447209767597511414934626668616704865548059751008841620288545344598917362752622130186820039265603312354963258673860579, 157978379942536176944325875241196121764116712487226808271002140500926678942090491383544034591205964958130852055691446362753906164711087278555153881606839791499207025307202087, 43938571869497484913682975192955012614794498816057204091016374302341854100775132924321569876797699342959191646206571444845883942305710956894334106963321644724361549027630634869933, 2609065298534470914730686454716224905333131812890643378630636043224255484662185236061585264231004975072801053316107165770342161619265243081616632312934742288262985830181883449780965531, 222235907202454132555071455958700740228567465616560859711214102245461514428187391909176054661864893645713338391509536653547350134615807194339839952004333949540567943568810413945779642106201, 44890472824427626252451120059527486677662371033945481542195354255473403815853320591468917295474578271680865394304946847791535710766947049195816261224382109115684638995528332538466194474846836399, 1062789633774349417938788353001516763303743389381120380522262327123099728631034935663418832664265833959487018276693680850987382421521055508477988016246558095545925414048663082368488342633334571240563]

def solve(ii, ci):
    pi, qi = ps[ii], qs[ii]
    R.<x> = Zmod(pi)[]
    f = x ^ e - ci
    f = f.monic()
    mp = f.roots()

    R.<x> = Zmod(qi)[]
    f = x ^ e - ci
    f = f.monic()
    mq = f.roots()

    solution = []
    for x in mp:
        for y in mq:
            mi = crt([int(x[0]), int(y[0])], [pi, qi])
            if ii != 0 and mi < ns[ii - 1]:
                solution.append(mi)
                print(f'No.{ii} x = {x}, y = {y}')
            elif n2s(int(mi)).startswith(b'DASCTF'):
                print(n2s(int(mi)))
                return
                
    if not solution:
        return
    for cc in solution:
        solve(ii - 1, cc)

solve(len(ns)-1, c)

(为了做这道题，花了一晚上搞清楚如何使用sagemath以及调用python库，不过下了Crypto库但还是调用不了😣，不过挺值得的😁)

---

一些开根算法：

• Tonelli-Shanks algorithm（开平方根）

  Tonelli-Shanks algorithm - Rosetta Code(代码)

  Tonelli–Shanks algorithm - HandWiki（理论）

  https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm（理论）

• Rabin

  Rabin加密算法_Dragon Liu的博客-CSDN博客_rabin算法

• AMM

  1111.4877.pdf (arxiv.org)(理论)

  [RSA/rth-root extraction at master · mad-jcbx/RSA (github.com)](https://github.com/mad-jcbx/RSA/blob/master/rth-root extraction)(代码)

• 以及上面介绍的那个本人未实现开根算法。

CVE OF RSA

from Crypto.Util.number import *
import socketserver


class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'[-] '):
        self.send(prompt, newline=False)
        return self._recvall()

    def special_rsa(self):
        kbits = 37
        abit = 62
        M = 962947420735983927056946215901134429196419130606213075415963491270
        while True:
            k = getRandomNBitInteger(kbits)
            a = getRandomNBitInteger(abit)
            p = k * M + pow(0x10001, a, M)
            if isPrime(p):
                break
        while True:
            l = getRandomNBitInteger(kbits)
            b = getRandomNBitInteger(abit)
            q = l * M + pow(0x10001, b, M)
            if isPrime(q):
                break
        n = p * q
        self.send(b'n = ' + str(n).encode())
        flag = open('flag', 'rb').read()
        m = bytes_to_long(flag)
        c = pow(m, 0x10001, n)
        self.send(b'c = ' + str(c).encode())
        self.request.close()

    def handle(self):
        self.special_rsa()


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 9999

    print("HOST:POST " + HOST + ":" + str(PORT))
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

$p,q$生成方式如下
$$
p = k * M + 65537^a\ %M\
q = l * M + 65537^b\ %M
$$
找到了相应的论文，嗯……写不出代码来😅。

The Return of Coppersmith’s Attack:Practical Factorization of Widely Used RSA Moduli (acmccs.github.io)

复现后才知道这是ROCA(Return of Coppersmith’s Attack)漏洞。简单转述一下就是，一些硬件采用以上方法快速产生RSA的私钥，这样产生的公钥$n$会带有一个指纹，但由于$M$是光滑数，这个指纹可以很快被攻击者确定，从而分解$n$。（from 4xwi11）

同样也找到了一个密码攻击脚本的仓库jvdsn/crypto-attacks（挺不错的，有时间得好好拜读）

运行过程就参考4xwi11师傅的吧，我并没有搞定在python中使用sage库。

---

总结：

• 能确定攻击方式，但却写不出好的脚本，有待提高。
• 发现一些大佬的博客我都有收藏，但却几乎不怎么阅读过。
• 找到了有关密码攻击脚本的仓库，太棒了。
• python上使用sage库还是没有解决😑

---

参考：

20220423-DAS-FATE-CryptoSec | 4XWi11的博客