SECCON CTF online 2017 write-up

SECCON CTF 2017にチームint0x80にて参加しました。ほかのメンバーが頑張ってくれたのであまり活躍してない。結局1問だけ。

Ps and Qs (Crypto 200)

-rw-r--r-- 1 yu yu 800 Dec 9 01:33 pub2.pub
-rw-r--r-- 1 yu yu 800 Dec 9 01:33 pub1.pub
-rw-r--r-- 1 yu yu 512 Dec 9 01:33 cipher

公開鍵っぽいもの2つとcipher。問題名から、秘密鍵1 と秘密鍵2に公約数sがあるものと想定。 とりあえず公開鍵に含まれる積を取り出す。

$ openssl rsa -noout -text -pubin -in pub1.pub Public-Key: (4096 bit)
Modulus:
    00:cf:cf:bb:ee:a7:df:14:3a:8a:c2:08:b1:aa:1d:
    2f:86:54:5a:c4:cb:58:8c:94:a3:fb:1c:14:ad:91:
    a4:f0:b9:36:15:7c:5a:4b:86:9c:18:a8:b8:64:f4:
    72:6b:f8:fc:dc:02:0c:b4:10:42:ba:c9:67:84:ab:
    7d:03:f9:37:49:47:ef:b0:bc:3d:66:58:31:97:43:
    40:15:9f:fc:3d:b7:c8:e7:4b:63:90:fd:a6:ee:c3:
    0b:81:c6:ff:62:4e:8d:3f:5b:17:bf:b7:a5:c7:ff:
    d8:ec:f4:e6:51:8b:39:3a:be:fd:dd:0f:ae:ba:43:
    08:74:6b:a6:3f:81:06:b5:9d:7e:05:89:43:a0:01:
    31:a7:d4:e5:38:c4:64:b2:70:57:76:47:ed:bc:47:
    8c:c1:ce:95:85:ef:e8:77:30:5b:3a:7c:2e:7c:44:
    db:54:75:ed:da:dc:34:5a:2c:90:a9:46:77:1c:ac:
    0a:45:4c:db:cb:46:1f:28:40:e7:61:3c:83:e9:ce:
    cc:94:03:7f:a0:9b:b9:da:a3:f1:80:56:2c:01:df:
    0b:e6:c5:1f:0c:06:e8:f0:e2:d6:e1:a5:e5:0d:0a:
    28:c3:88:11:40:77:0a:9f:45:93:41:46:b7:f3:59:
    b9:39:ce:23:f0:fa:50:7a:6f:4e:45:45:71:43:09:
    52:00:3c:20:f1:d9:7a:67:14:0b:6e:5f:cb:fb:3b:
    37:6e:4e:24:96:9a:eb:1d:48:9c:fc:72:af:4f:15:
    a4:78:8a:1a:a9:7c:89:75:6d:1d:4d:94:aa:47:e7:
    cd:3a:81:ae:cb:92:44:8c:c9:2c:77:d2:ef:57:6a:
    a0:db:c1:35:08:62:ac:cd:da:dd:bc:e8:03:57:f0:
    cd:5b:85:4d:d0:f8:c4:62:7f:e4:b7:18:b2:4e:cf:
    e1:1e:d2:4c:3b:e2:2f:00:64:3b:be:d4:ee:5e:34:
    5a:f1:76:e5:b7:6d:23:a2:f8:0e:0e:c6:f3:4e:57:
    18:c6:2a:70:fe:55:70:c2:8b:80:7b:44:f2:2e:ad:
    eb:d9:b5:ff:90:6f:6a:85:be:88:c0:c8:f6:e5:f8:
    80:a5:1f:17:f8:4d:b1:c2:ee:fe:a8:af:34:04:04:
    44:ce:d1:a3:7d:f0:e4:f5:f7:2c:c3:f5:0b:7e:42:
    7c:8c:2d:8b:61:86:ea:d7:62:f0:c4:44:b3:ca:3a:
    01:03:ed:12:a9:3b:ce:9c:ae:74:79:a2:29:eb:bc:
    0a:64:8e:aa:6f:97:e5:05:1a:66:eb:09:eb:d7:34:
    8e:92:f7:5f:12:5e:bd:c3:67:e2:a7:d1:da:77:59:
    d4:1f:ae:2e:26:35:bf:4b:7a:7f:91:be:ca:b3:ac:
    7d:05:bd
Exponent: 65537 (0x10001)
$ openssl rsa -noout -text -pubin -in pub2.pub 
Public-Key: (4096 bit)
Modulus:
    00:bb:33:cc:7f:cc:8e:ca:f3:bf:9e:d9:5c:58:37:
    92:e1:ec:6b:80:ee:87:5e:c2:06:4d:bc:f0:75:95:
    c8:34:49:23:bf:53:65:24:d4:e0:a7:55:74:c7:79:
    8c:73:b1:97:dd:2b:1b:42:05:4b:1e:49:cb:45:fb:
    f0:4e:6f:11:4c:f8:a3:65:c3:df:36:45:52:4f:77:
    82:68:03:8a:3f:a2:68:02:e9:d1:ed:bf:bb:5e:df:
    b5:a0:c3:75:37:0d:7f:10:f5:7d:ab:bd:4f:77:1d:
    ad:36:32:f0:1b:9b:ce:10:48:99:66:ee:88:2d:ab:
    17:a3:3b:78:6a:a5:f7:31:65:a5:40:51:30:0b:1d:
    f9:28:03:92:a3:ed:e9:d3:fc:9c:4d:8a:6a:06:35:
    1f:6e:f3:59:8e:8d:e2:b3:9d:3b:19:af:64:a1:71:
    6c:d1:58:26:c3:f2:4c:b1:3d:eb:72:2c:3a:03:ef:
    1d:2b:e2:d0:a5:a6:e2:10:ff:5d:01:83:67:be:3b:
    f9:9e:a2:6b:a0:06:e5:16:4a:4d:d5:5a:ab:cd:44:
    9d:e5:ce:18:64:82:5d:c1:60:e5:0d:50:9e:b0:e6:
    fe:72:3e:f1:82:68:1e:dd:b9:40:84:b8:3e:c9:e2:
    e9:43:e8:7c:b8:75:09:ab:0f:d9:b1:ca:22:c1:ce:
    af:f3:9f:ca:cf:67:29:fc:0e:05:78:67:0d:87:d7:
    f0:f9:cc:be:09:cb:3e:12:ce:b8:95:57:2a:99:79:
    d1:0b:fd:bf:af:a2:60:56:8d:8d:b1:84:be:12:b3:
    e3:19:3e:07:72:9c:e3:c1:d9:cd:82:83:ed:69:83:
    a0:63:88:03:6a:0a:70:29:4f:23:39:29:44:77:82:
    80:e7:de:9f:60:16:3a:81:50:e3:0f:f4:a4:ea:02:
    79:2c:be:83:05:ba:a2:e9:9a:fe:51:e1:7d:af:c5:
    6b:e0:d3:84:14:7b:cd:38:e9:d1:29:34:ec:71:26:
    22:21:77:73:a4:b3:85:1a:9b:0c:6c:7c:3e:01:f6:
    11:1a:1e:1a:55:7f:4e:2a:e4:a2:47:ce:9b:75:cc:
    cc:b1:81:98:25:f3:05:4a:a1:c0:55:bd:3e:23:40:
    09:3a:e2:ef:1d:0f:a5:a1:76:82:5e:fd:f7:95:07:
    02:7f:51:04:08:00:09:14:2f:0d:43:e2:f1:0c:fa:
    d2:20:81:3b:bb:90:14:d4:f4:32:5e:da:c5:38:fb:
    5e:82:b7:53:e2:ad:3b:24:60:7d:73:80:aa:64:fc:
    b9:8b:59:ea:8b:5a:73:6b:80:93:83:24:8c:ec:e0:
    b1:72:55:ea:55:9e:90:12:7f:77:8a:f6:d7:e8:a6:
    6d:ad:91
Exponent: 65537 (0x10001)

それぞれを手元のsublimetextでスペースコロン無しの16進数に加工し、公約数を求めるためにwxmaximaに食わせる。公開鍵をxとyとした。

ibase: 16;
set_display('ascii)$
x: 00cfcfbbeea7df143a8ac208b1aa1d2f86545ac4cb588c94a3fb1c14ad91a4f0b936157c5a4b869c18a8b864f4726bf8fcdc020cb41042bac96784ab7d03f9374947efb0bc3d665831974340159ffc3db7c8e74b6390fda6eec30b81c6ff624e8d3f5b17bfb7a5c7ffd8ecf4e6518b393abefddd0faeba4308746ba63f8106b59d7e058943a00131a7d4e538c464b270577647edbc478cc1ce9585efe877305b3a7c2e7c44db5475eddadc345a2c90a946771cac0a454cdbcb461f2840e7613c83e9cecc94037fa09bb9daa3f180562c01df0be6c51f0c06e8f0e2d6e1a5e50d0a28c3881140770a9f45934146b7f359b939ce23f0fa507a6f4e454571430952003c20f1d97a67140b6e5fcbfb3b376e4e24969aeb1d489cfc72af4f15a4788a1aa97c89756d1d4d94aa47e7cd3a81aecb92448cc92c77d2ef576aa0dbc1350862accddaddbce80357f0cd5b854dd0f8c4627fe4b718b24ecfe11ed24c3be22f00643bbed4ee5e345af176e5b76d23a2f80e0ec6f34e5718c62a70fe5570c28b807b44f22eadebd9b5ff906f6a85be88c0c8f6e5f880a51f17f84db1c2eefea8af34040444ced1a37df0e4f5f72cc3f50b7e427c8c2d8b6186ead762f0c444b3ca3a0103ed12a93bce9cae7479a229ebbc0a648eaa6f97e5051a66eb09ebd7348e92f75f125ebdc367e2a7d1da7759d41fae2e2635bf4b7a7f91becab3ac7d05bd;
y: 00bb33cc7fcc8ecaf3bf9ed95c583792e1ec6b80ee875ec2064dbcf07595c8344923bf536524d4e0a75574c7798c73b197dd2b1b42054b1e49cb45fbf04e6f114cf8a365c3df3645524f778268038a3fa26802e9d1edbfbb5edfb5a0c375370d7f10f57dabbd4f771dad3632f01b9bce10489966ee882dab17a33b786aa5f73165a54051300b1df9280392a3ede9d3fc9c4d8a6a06351f6ef3598e8de2b39d3b19af64a1716cd15826c3f24cb13deb722c3a03ef1d2be2d0a5a6e210ff5d018367be3bf99ea26ba006e5164a4dd55aabcd449de5ce1864825dc160e50d509eb0e6fe723ef182681eddb94084b83ec9e2e943e87cb87509ab0fd9b1ca22c1ceaff39fcacf6729fc0e0578670d87d7f0f9ccbe09cb3e12ceb895572a9979d10bfdbfafa260568d8db184be12b3e3193e07729ce3c1d9cd8283ed6983a06388036a0a70294f23392944778280e7de9f60163a8150e30ff4a4ea02792cbe8305baa2e99afe51e17dafc56be0d384147bcd38e9d12934ec712622217773a4b3851a9b0c6c7c3e01f6111a1e1a557f4e2ae4a247ce9b75ccccb1819825f3054aa1c055bd3e2340093ae2ef1d0fa5a176825efdf79507027f5104080009142f0d43e2f10cfad220813bbb9014d4f4325edac538fb5e82b753e2ad3b24607d7380aa64fcb98b59ea8b5a736b809383248cece0b17255ea559e90127f778af6d7e8a66dad91;
    g: gcd(x,y);
    p: x / g;
    q: y /g;

Shift-Enterで解を得る。予想通り公約数が1以外に存在することが分かる。

(ibase)  16
(%o3) 847796795638781450678718708
664542960446354226336422534142899480441478781\
747168340722544245493739168125415291376063352480076469305992008517388366298914\
970810765149321160596112226917023146371080685458239747986992197343482255681414\
590678694753885521068656675164266739274608505094927725285868801825
144058835115\
051061857233824816176186349372737400492228548130718029270482313906040935333159\
681273527671359469173939861889228505791626525994180917670701909816457560622922\
219797109618405842358250940062127841301193206255543580550667149741357342408703\
680375118252445296600962244008043713708516004025217199954286478272550961283413\
053789743740774140439284662596273452124779590753836094450154459078034659421366\
584354005421566290862244000178569163732971816333961711759000171156293724203334\
889496589376907683142167883476184246287660764821622298961378903818077158234683\
927321823293466245584486980446609569799420950073036635602004293246754252079757\
527610246223280774592566063422181158810677919909523144033543195999214800559998\
598003329294711989868113423468536273984117507008756542731210465222475943122324\
672467669623079721727526348599823126409108190030551584092950358235465140166515\
452377475799157617227362838246912839086733412861436353117994501342653
(%o4) 76371891247516048790280
4749669814117361530270298225094625871588939939773\
892509348006077810445741086683427253000695920011673348476297973798322806091336\
777405584801442639626925406721932533140226556519019440300864340670199686368307\
1558604936150651983194900605985872020519426387929196485962885762948045497381
35\
969737494734307362891313864027749187674251692407867312885251279302785352318725\
391842117065840058358065676707016006124478822206302825992616559261930620693061\
673348139416033418864269248381876692676529410115745518353146254670349865568255\
213560376368953292931958006941630719304442332912813624543600126197554727832190\
226632919876204677667384620275620336951964833888599634720101911051166398907898\
747710391394105753614253527704990658698844796442515669670816004761855554187277\
637871343595647487793209271354240148469085627742503649786300484610102224828274\
384484809539697728008552925590472129497180290668277790132130824141651399551803\
499770513576176720509094833332201946177880267399933460994496277590932311628302\
240154240967341858152145815276163397709272690500041597393678630136932574450837\
982593210399370333578887450410911663220219423601973078501237709613593311133945\
501455828164291429228495931943107997137587307522565029820756690578833
(%o5) 284913512680212653855266513865386078073096599862766883430646700738910134\
0082516441523
06013387824730257424020493948306306758057258850884301121494978692\
423461844365014982506562524786543661869253594964276221406581073455465432577139\
196943024870499547613221012541884442078884274519798649846353235229010727057828\
355530101191155299601996161344265180903247070557309089781820754010700442764439\
579294038745123916988133061396918981675497567581891224323730030192066306113773\
192441603153120080842140385160080268045489258767335778431393536972274336459261\
763324222538
80445694249081777712571005410284034477749618735562684652311433029
(%o6) 29756285957217824990174038832451778402099067307810847648290595
7850584316\
469769083223041479591124271401597928889149232362001674900112018112504327421349\
550764671615123999570773139646300711417355041545696721914603896976339564385555\
48934921730829103416692214221897316036431719854
7270621220707112529242378599816\
508390821279476192467163117285073505212608317620178792114086711948835216991078\
859952277600521902685611723772884946474874075783577957683680616997608353053552\
223132066497479879804034800558304093546545069950900370055324807049618301832369\
22268938782515705140754745094708066416483123932606937140087049605071066540057
(%o7) 268052892714976182888249574098409000879217373642470620179546530953506059\
96401170903273670545713193946727301443
7792256550091854421243013036188024690038\
437419581472670246778687938059324493296589209828480634846887003333992041067331\
492304815274261716101078896818759926176473155393020477940584376489082126459712\
111767869575177314947237298893540754357640976586021397801435693376364574528933\
866909385223926096855561094162338051541492626634160508146847148502135500632311\
100897874915409449457122977108447359309772349703738265190424700468671371860547\
40672979017101637673890382547484646195101031561338945685511605286410830656477

得られた数値を前回で使った genpriv.pyを少し改造して貼り付ける。 yuppy.hatenablog.com

得られる値は3つなので場当たりコメントアウトしつつ実行し、privkeyを3種作成する。

import sys

ss= 28491351268021265385526651386538607807309659986276688343064670073891013400825164415230601338782473025742402049394830630675805725885088430112149497869242346184436501498250656252478654366186925359496427622140658107345546543257713919694302487049954761322101254188444207888427451979864984635323522901072705782835553010119115529960199616134426518090324707055730908978182075401070044276443957929403874512391698813306139691898167549756758189122432373003019206630611377319244160315312008084214038516008026804548925876733577843139353697227433645926176332422253880445694249081777712571005410284034477749618735562684652311433029

pp= 29756285957217824990174038832451778402099067307810847648290595785058431646976908322304147959112427140159792888914923236200167490011201811250432742134955076467161512399957077313964630071141735504154569672191460389697633956438555548934921730829103416692214221897316036431719854727062122070711252924237859981650839082127947619246716311728507350521260831762017879211408671194883521699107885995227760052190268561172377288494647487407578357795768368061699760835305355222313206649747987980403480055830409354654506995090037005532480704961830183236922268938782515705140754745094708066416483123932606937140087049605071066540057
qq= 26805289271497618288824957409840900087921737364247062017954653095350605996401170903273670545713193946727301443779225655009185442124301303618802469003843741958147267024677868793805932449329658920982848063484688700333399204106733149230481527426171610107889681875992617647315539302047794058437648908212645971211176786957517731494723729889354075435764097658602139780143569337636457452893386690938522392609685556109416233805154149262663416050814684714850213550063231110089787491540944945712297710844735930977234970373826519042470046867137186054740672979017101637673890382547484646195101031561338945685511605286410830656477

# 以下3パターンでそれぞれ出力ファイルを作成
#p= pp
#q = qq
p = ss
q = pp
#p = ss
#q = qq

e = 65537
n = p*q

def exgcd(x,y):
    r0,r1 = x,y
    a0,a1 = 1,0
    b0,b1 = 0,1
    while r1>0:
        q1 = r0/r1
        r2 = r0%r1
        a2 = a0-q1*a1
        b2 = b0-q1*b1
        r0,r1 = r1,r2
        a0,a1 = a1,a2
        b0,b1 = b1,b2
    return a0,b0,r0

d = exgcd(e,(p-1)*(q-1))[0] + (p-1)*(q-1)
exp1 = d % (p-1)
exp2 = d % (q-1)
coef = pow(q,p-2,p)

def int2bin(d):
    t = "%x"%d
    return (t if len(t)%2==0 else "0"+t).decode("hex")

def enclen(l):
    if l<0x80:
        return chr(l)
    else:
        t = int2bin(l)
        return chr(0x80+len(t))+t

def encint(n):
    t = int2bin(n)
    return "\x02"+enclen(len(t))+t

t = "".join(map(encint,[0,n,e,d,p,q,exp1,exp2,coef]))
t = "\x30"+enclen(len(t))+t

print "-----BEGIN RSA PRIVATE KEY-----"
print t.encode("base64")[:-1]
print "-----END RSA PRIVATE KEY-----"

それぞれで以下を実行してみる。

$ openssl rsautl -decrypt -in cipher -inkey privkey-xx.pem

p = ss、q = ppとした定義で得られたprivkeyではエラーとならず成功する。（残り２組はエラーになる） 以下を得る。

SECCON{1234567890ABCDEF}