ぺんぎんさんのおうち

日本語勉強中のドイツ産ペンギンがいろんなことを書く

Breakin CTF 2018 [Write-up]

Breakinctf 2018に Harekaze として参加しました。
最終的にチームで800P取得し、24位(点数取得97チーム)でした。
そのうち、僕は1問解いて200P取得しました。
Write-upです

[Crypto] Tayank and RSA (200)

暗号文とPEM形式の公開鍵が与えられました。

c = 3031565869307464860403024541415247329921400250939123942749838395951200906195912098273697094933173563915051800683854083535648696521225134188640597146291320940306966023022527795737939105353678041425121810336578029788678728492689897038902105263858426539175922247349958763874337794284582670373078371157478043666766632153165907104750922694389568508447019649539327738569521014874389971079086085667484095870696491620298576070689613747667174491562698225806160336130658485907211579204879419891734676846279171428451540120652619063097708660581027587603112924444447427892909901600125581441244483163410758972483726889907120692461
-----BEGIN PUBLIC KEY-----
MIIBITANBgkqhkiG9w0BAQEFAAOCAQ4AMIIBCQKCAQB2iWikFrN13/ukdviWfDjy
Bm++gjV8/8aG9+kDoIDDHCPZCidH7v74kDnk1jpRX5QqereOsuAoOMflET+MaU2R
B6dz+oLdAmy57tziw4yCt0JXwDct3hBCFwocUDFmu1mvdzsSLD8yNh+ohQ8WaYBn
6rTXJ7YMgIHmoOHcuzBZOXMjpHNDhY9puOx+Z9VE312rMIbQ/uXi4D7uLPn1hh8c
ajDE/LyHOfcrHhuva/MZRqruCzzcRhAB0TM+dlMUb3O5TtaMUohHhzUvDeGVn2jp
WcHELhWjfA/YwZAe9nLqbW/aTCMwFEGhQp2rBMEnpHit7mSTUKFOkrKFRuXiD4cn
AgMBAAE=
-----END PUBLIC KEY-----

$ openssl rsa -noout -text -inform PEM -in Xa5kNbw_Twins.pub -pubin

してみると

Public-Key: (2047 bit)
Modulus:
    76:89:68:a4:16:b3:75:df:fb:a4:76:f8:96:7c:38:
    f2:06:6f:be:82:35:7c:ff:c6:86:f7:e9:03:a0:80:
    c3:1c:23:d9:0a:27:47:ee:fe:f8:90:39:e4:d6:3a:
    51:5f:94:2a:7a:b7:8e:b2:e0:28:38:c7:e5:11:3f:
    8c:69:4d:91:07:a7:73:fa:82:dd:02:6c:b9:ee:dc:
    e2:c3:8c:82:b7:42:57:c0:37:2d:de:10:42:17:0a:
    1c:50:31:66:bb:59:af:77:3b:12:2c:3f:32:36:1f:
    a8:85:0f:16:69:80:67:ea:b4:d7:27:b6:0c:80:81:
    e6:a0:e1:dc:bb:30:59:39:73:23:a4:73:43:85:8f:
    69:b8:ec:7e:67:d5:44:df:5d:ab:30:86:d0:fe:e5:
    e2:e0:3e:ee:2c:f9:f5:86:1f:1c:6a:30:c4:fc:bc:
    87:39:f7:2b:1e:1b:af:6b:f3:19:46:aa:ee:0b:3c:
    dc:46:10:01:d1:33:3e:76:53:14:6f:73:b9:4e:d6:
    8c:52:88:47:87:35:2f:0d:e1:95:9f:68:e9:59:c1:
    c4:2e:15:a3:7c:0f:d8:c1:90:1e:f6:72:ea:6d:6f:
    da:4c:23:30:14:41:a1:42:9d:ab:04:c1:27:a4:78:
    ad:ee:64:93:50:a1:4e:92:b2:85:46:e5:e2:0f:87:
    27
Exponent: 65537 (0x10001)

eはよく用いられる数値、Modulus-Nが2047bitとかなり大きい値になっているのでとりあえずフェルマー法による素因数分解を考えます。

分解できました。

p = 122326933943001152038548393343419195487856722723330989237468716168702418948676536255652231577936729434437853695160408410339629158564032676906004524726502183269193562292833858752695452397938116683902518310541643644656286495041297849893401003686696094919792753252913166726228010550337394986809806335101353725559

q = 122326933943001152038548393343419195487856722723330989237468716168702418948676536255652231577936729434437853695160408410339629158564032676906004524726502183269193562292833858752695452397938116683902518310541643644656286495041297849893401003686696094919792753252913166726228010550337394986809806335101353724113

ここから平文を出力すると
m = 71877470807883123484848484849751061131101041101211007812075122115125

どうにもフラグっぽくありませんが、この数字をよく見ていると
71, 87, 74, 70, 80, 78, 83, 123, 48, 48, 48, 48, 48, 49, 75, 106, 113, 110, 104, 110, 121, 100, 78, 120, 75, 122, 115, 125
に分割できることに気づきました。
GWJFPNS{000001KjqnhnydNxKzs}

フラグ形式は BRAEKIN{...} なので、アルファベットを5ずつずらしてやると
BREAKIN{000001FelicityIsFun}
フラグが得られました。