TetCTF-commonfactor

roger

题目描述如下：

What if each modulus has a prime factor that close to each other?

分析一下源码，发现我们的任务是已知e, n1, n2, n3, n4, c1, c2, c3, c4的值，满足：

c1 ≡ flag^e (mod n1)
c2 ≡ flag^e (mod n2)
c3 ≡ flag^e (mod n3)
c4 ≡ flag^e (mod n4)

其中ni可以写为：

ni = (p0+ai)*qi

p0,ai,qi均为未知数，但是我们知道这几个参数的比特数（分别为2048 bit、512 bit和1024 bit）。

根据ni的表达式，我们有：

 q1*n2 - q2*n1 
= q1*(p0+a2)*q2 - q2*(p0+a1)*q1
= q1*p0*q2 + q1*a2*q2 - q2*p0*q1 - q2*a1*q1
= q1*q2*(a2 - a1)

根据该表达式，我们可以建立如下方程组：

q1*n2 - q2*n1 = q1*q2*(a2 - a1)
q1*n3 - q3*n1 = q1*q3*(a3 - a1)
q1*n4 - q4*n1 = q1*q4*(a4 - a1)
q2*n3 - q3*n2 = q2*q3*(a3 - a2)
q2*n4 - q4*n2 = q2*q4*(a4 - a2)
q3*n4 - q4*n3 = q3*q4*(a4 - a3)

设s[i,j] = qi*qj*(ai - aj)，整理得：

n2*q1 - n1*q2 - s[1,2] = 0
n3*q1 - n1*q3 - s[1,3] = 0
n4*q1 - n1*q4 - s[1,4] = 0
n3*q2 - n2*q3 - s[2,3] = 0
n4*q2 - n2*q4 - s[2,4] = 0
n4*q3 - n3*q4 - s[3,4] = 0

该方程组共q1,q2,q3,q4,s[1,2],s[1,3],s[1,4],s[2,3],s[2,4],s[3,4]这10个未知数，通过观察发现，s[i,j]大约为2560比特（1024+1024+512），而ni大约为3072比特（2048+1024），即s[i,j]同ni相比较小，因此我们可以考虑采用LLL算法，利用格基规约的思想来计算出格中向量（即q1,q2,q3,q4,s[1,2],s[1,3],s[1,4],s[2,3],s[2,4],s[3,4]），将上推导过程写成SageMath代码如下（注意，矩阵中前4列K设为2**1536是鉴于qi约为1024比特，而s[i,j]约为2560比特，因此计算得K约为2560-1024=1536比特）：

from Crypto.Util.number import *

data = [((65537, 1569550063055353702062251622140405741164543885895263716006311290669305518774643620241669255260173008709010777432822095605109572129277181116066934393938913194634071173571789450658930352812799017920168864490575696448185577689815549941469079131071103077726355198947488827984628323233221969365714243695334163539732217581013202447968200349694743372108785700167811700154461822011593758838103682584293207390265904896690779335861085789680612320987714538790079517857825517341064238474276090581570268680801110977426713251313985654692074627771968221263628566577663292273864788031693728920793663002764518270439846047430644492176906880059059757415785299265568994209893143584242526018633538624991827790348379585727698363216989988605329417015614749367997396020210490795394806634640415760285432494176804052664955540791844765635239921663181473515232520585476564852497075855687754109417808350181599443473343426564161709223282835203442809017719), '2a3635ef543e23b8890c3c7fb9dc0035cb76e72fbcd4388b1362ae47c66a2f84a19895d769fb32a43aca96059c03cfa0ddee1285ae53f6e3cd3abfaa2b2d4efe025f02b0a2ed9ab69801b53f1f78c631ddd5b3a50c696132af348b988ba055bb1506555e1a9b64f7ef9725addabca6b2cff4fe9622a0f22710f2c3bb7a0b5975fe5bba6576b5a5a47261d149fc8450aa548d70873480cfdc760574593b7fccd2e0d4a3aa862b731c2042a2353f974e7602106117de91949c755bb1b2ebfde0c7ecc33f78fd7ad3c4174b85f50ada6e56caf9a84761489fddbfcb9920cd500d3c2bf99b80cb3339f609659763ff90cd98fa4e4b76059316d69300ff581b1b7339e33784665fdc32d471a45bcc9e64b52308fd610356f1f7845dca3cf8ca50415e3b355a31f8e6e28c6f55ea48afc64518366ee37374ad0de07ae0dd72a9777f99fa38fed2efaf5a1adb8347753aded0c63495ec5645286814f6fb65e80b388028be91948e8fcc3e9725f59ef6c3aa3347b1114f50b6f246c409d7345a95e27c9a'), ((65537, 2730283999793749264071994226279314691204895377404209565102825207699012231964571371393565413047501757446096028236098715505064861045733353396025801293513027886331405786693625981806024261090773960211723151228583932366854870779329338093342110116239823692446625908148569295349026098714317035693497738564674630046858940758268904883253130893434520330702974774740936668070921709593901397140514831064190173236110424772839521534745874746094149570949799151876580658630054731546971832113713586531173316705765487046247502189588416101732562581007651101065666702695240388669899916625981732500919162710884254165127397187535845159165998232131583784946310754662937729402163425101195112360330284894990617298955741961418495852029683443729778504126937607369357318043051374289892542351932602544495709781266606022658359744825356895011618431466585793664964295808363804430145778026353089508091611151785476160457795461698721421465059644656840014600041), '026d719accd581bf22171ac26ea1f7cbe8e260cd24450ff59f85b8421d9a779fbaf36e1acbd67d41280ccf439de5b5f8027a9d18b1e938156682f3bf9f761cafbecfc23c39abc82f6d5e7a4c66e6f435e7d42a5e1ed77fddcbb3a239bba506f23a92f6f57a2657b4b2deb1fef1c1058ba823786679e2e9c3ed7f59c1a6caf7a9fb21c3ab85f09c18dc2ae70676c73e75db6db3b92f5ac60f500582977d3ed496ef0453c5af849c553b7fe19aee6b93d1ca2e8476b53a6b97a03d499b58a2f1b93d4517d703cebba82ddc716410d973bc5321c10d2a8c7303218a2c74bec545b17c13a82deea95b23d691b34f48660e2d870da8db94be02f648f1659cd498d6fd3e3045aa4dd95edbceb401d4a91c135ddfa3d4663e2ebebc4e95f4e9c2b35abfe8b6b602ad6c325f7683e999573cfbe207e0eb8c03d8e36c6f05aa830b3a7ebd9ed8bdd398684187df412ce314954fb5dafe70968dd4f8ae5013853748154c4d3da3d98f9a38f0861bbf17901335771ccb20d5459a24d9d3c79fb6c1e476e255'), ((65537, 1657924959258427226307055128056402549049658652459789576664039012048766540305618951414934786898658966332588809718413923122757875484373037540477722388638858840553898318448626423532633906716310030105130220972278335649446578557159040826543453673941238724891568284827700166830419306376245310916788207429484546008057506662687383202131145958184896298361743446184460904711938203945290001030935479432306677809636841024967980503938216612051167394878501381482352098157599786486983098492823924154622607669864184134461471518206144965857276719217971497293243585472164850309399795206985218997770181188717957316358992357240612579079388186461595164275424746021207041500591749112264695684877167817330714551838424537679384766153692744343813935326599234507761125601864336402749915632919491226732249503422131540162743886991909428277721627830367633020694730720233889895699382127886525607643971481037152168998649018674269175967386808314905895314197), '0f468c7cb9bd432f3646babfa669613b83d6bf2db8ec905f10ad1b9c5f7fd75d842036235b714f86a1b7198f8f973f12c270728ae8591687627525c1e54acf9382c13db98892ec7050dd099527e84835e9890122ef22e1b879236c2f0e26efe1589436d12554fce271ea91e11edbe4c2357eca55c63ecc8e2b23e6d66d9f4a841810d633bf3e4ccb988ceffacedfacb7901f6dab2efcacd95044b0e4e217949c84438310808afa1dfface3adf1dd266e7d9381878227c6040c266d69e71283c23f7864b48bdcf7a964744581575b1cb97213fee4e4071b9b1d0c58611a8934dec1e03f3a9ed981be5403b464e8f4419b823e38bf91f11b023ccc2e01a73def95b990c19c5d2eae9b687f9ab6a704591b3bd9e72addacbefc88fe05ae2c752ebb02895ee105fe74911352ed7bee2a7fb228f1d54fdaef84bd35a67f2f2304017cb83552b2907378ad7c66c7deafb99b0f9d2ce773e1356740844a9911a1e6f253b37cfe6ee16cbae039cfb6749e37bfded30d9baf59b8885d90417c377a147ee0'), ((65537, 3110983727661077937376483862188516844290042596812999305612957161800816904909443569902815766791831716284243968496162996466265930191168784893609334033188775609333281859333753210203804896424511597949940464238543873038000953406791059640295024235321865958267828973182348676239507210900448468842637639173505565493171932934892943628388379309785199843742769621576222396095887453166229610793369913897213948204383648981616627432221090548043925906077201237965560335631118150165890050551079019918702281461877104615212668635883055429384473604595031546202824294553045455954363988428330149396318900050555119058365566287024446487265976507415428817694045660559396737370223118169785779836592977584710981448734152325507656805905400453259442794406092886306392902382083271202964538178390354974828834963375811565387903407912909084458524154107388099011117741856972886184901943539374501035824626968500926567510870331630818145831137375610941414399811), '7f1c2ef0982ee47fea224465ac11c723ed16cd05b204119276e9f2a62eda32f997f47ce0dc7561a7d0d9c6552ecceb8d4b6c85644dfe543553168b4642affbcdd43efb8e9dfe2edeb47f16404cca166386eb4e335c69eaafc81b45993ce177c608f9dbaa8b68278a9288ba8cf98dbca111daa5271bd47dac3edf29d04331dc65a3b5a131b582b4be1410bd6145211225f8ff51bbcfd131fb8698233cd9d92d63adc6dcdb1a7e27e6064f5c6275476832ef57564425057ae72e84cf718a91cbe47c6d2c14ca4bd6b9595e003cf4f3cbbe65af93ad6acee5e8ef31f07bd801831089cdc34593c1fd3bef4a04ffc3024d06b674effa25af9a540897fcf02ff94caab41a4cb7eaa40cc111b72d5e361e51b9b583571cfd051468887f1a9cf264fa6fdc7f342e0d146650fdb96b8a9085fc4493af877fb6ff886dc36b8bd1b02b72fdde03aa02a92b5ec921e51fe379d76103b845e12630639d3f542e65a105924c83f8cc58c3f15c477be6d36433ad8bcb6897189b8f9b95a71f8ef674c7e8a9e9a8')]

e = 65537
c1 = int(data[0][1], 16)

nlist = [x[1] for x, _ in data]
n1, n2, n3, n4 = nlist

n = 3072
t = 2048 - 512 - 1
K = 2^1536
M = Matrix(ZZ, [[K, 0, 0, 0, n2, n3, n4, 0, 0, 0],
                [0, K, 0, 0, -n1, 0, 0, n3, n4, 0],
                [0, 0, K, 0, 0, -n1, 0, -n2, 0, n4],
                [0, 0, 0, K, 0, 0, -n1, 0, -n2, -n3]])

q1 = M.LLL()[0][0] / K
p1 = n1 / q1
phi = (p1-1)*(q1-1)
d1 = inverse_mod(e, phi)

print long_to_bytes(pow(c1, d1, n1))

执行脚本即可得到flag：

TetCTF{_0oops____th3_tw0_pr1m3_f4ct0rs_sh0uld_b3_0f_th3_s4m3_s1z3____4r3n't_th3y_?}

monkeyman

支持学逆向论坛，资源不错！