Damn Randomware!

Category: Crypto
300 points
Solved by JCTF Team

Description

problem description

Solution

We first get the modulus N and public exponent e from pubkey.pem:

$ openssl asn1parse -in pubkey.pem
    0:d=0  hl=4 l= 546 cons: SEQUENCE
    4:d=1  hl=2 l=  13 cons: SEQUENCE
    6:d=2  hl=2 l=   9 prim: OBJECT            :rsaEncryption
   17:d=2  hl=2 l=   0 prim: NULL
   19:d=1  hl=4 l= 527 prim: BIT STRING
$ openssl asn1parse -in pubkey.pem -strparse +19
    0:d=0  hl=4 l= 522 cons: SEQUENCE
    4:d=1  hl=4 l= 513 prim: INTEGER           :C9AF32366FDA9F3B6870DA3CA487D065F15D201DAB5F8F9CB56B8FBC60248578FDC3FB6CFAA74CB3187E77E9B473B5E91C613461C3EB5891AC90E4F89A18069FC138E72B8A976B341EB021CF9B71DD84C2A35DB00667495525EE5960A477984AA9138F86E50E32AFA3A1FE0E0C0852B61B6BE8EAC67F4F0E047748E2DDB12695888AFD119C6A9D0ECA35E6854352C7B9FF3AAB373405DB905BB3CA916A573E148D1234094AAB3E6EBEBA150FE0CA201DEE644EAB20153D17800C6337B127289174FFCFE61E3B7275F367C7A6D39C4FF5BEE47177D691491E61A8C08FDF99A5F8DC0488C75516C9DFBF7EDD7EF069C23538D2EA8E8C8A791D1129527E8DA0234DC802776C5D1EF86191029F3A066DB74AD69574D0C6D5F1B6393C079790F6B90DA5D55EA9CD7A6C6C438A8BB5DA32BCC950F694680788F4D7B9860A9E378A8B05B56A2AC1691C5A2042EB5D2D2FA760F5981D75932411D4A4113FA55573D0FC3A707FC99AD29244245C73479430332A6B5F682923B124D37169086E8F357A3F9005DAA28AFA886740239220017E3042B53E61A8FF32AAE6C090B3836AA63C7C40EE7FC267AD7302DA079E5CC1AC8C5DC47A8791D8CE69214C801C2CEEBA16546AB13FB4798231947032B83E848DE94033B19B4564519C43F6A78410E3D7AA4730449AA54C19D44A9558BA0D1C7619B47DD3DC5911B01F8ECC1D70A0DC32657913
  521:d=1  hl=2 l=   3 prim: INTEGER           :010001

So N is the long hexadecimal and e is 010001 in hexadecimal big-endian. Next we look for either d, p, q, dp, dq or parts of them in the private key:

$ xxd -ps -c 50 recovered_prv_key.pem | sed 's/\(0282010[01]\)/*\1*/g'
308209280201000282020100c9af32366fda9f3b6870da3ca487d065f15d201d000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000366097f5f442e47670ad
882f4967ef79*02820101*00dbb80e62e88f9ea33fc3d88c4c58d2a5900610c01e6395fddc6f5f93eb4f90da153a6e3d79171e
9e4300b0c183a32b3559b09aa1e3d48b0aed53d227867dc36b00b8dfb7a797e93818a2a2db910a80ef5ff5dc746ce7115199
1fd3b670a1ebc0af1b77ef415a6f243c1946f2cf6a7883beb159cebc45de600988cd509088981d04e65fd29a2db475c5ac2c
5c1163d47245f27209e344b7240e50c0aed750ade9715d156028a31eb2e5dbabb3cf25e57a58c19d2e6ff93f93e62e5e09e0
c3159e0effaeeb294a64c70457cea948ace721770b39973a582360c1da78ce6238150de9428c174496a8b4b52065af07ebc6
9129f8a2ae1290eea4e0b6fee3910f8deb*02820100*478a0dae0bbed93bd26f7fcb915a51c67c345f3445d8d4a65dbc45329d
f9107050f4c61e3f5197afd6b72634d62e7ccac3cdc38ac52ae79195bcba9f71b88e9ae247696ca6fd0983a5c11896e9bccd
c304c193ceda44b63e165641dd5aae1b05dece3c6d88df3fa8d98f9335031b272d54701ef9e67a604c6949b739ab29c053c2
f64d0ca0fd46d5d0e93ad298ae691e51fe25ebaab817fe9cf820bf61e6c8675a2d438a61fc93ca375a36e4c8eb7104b1f3a5
1191939f24a622d3beed7ba8e400dbfc11258fd83cd26cc63684ef78beb9f6c6a622bca0da6b0a374f66f52dcc8dcba5c698
0cb00761b0b6eed20cdaf450e9b759b9b363ba6b3369727bf69881*02820101*00818b53701d8e100a505e381f00249e000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

If comparing with a similar private key we know that the first occurrence is q. Now we have everything we need:

N = 0xC9AF32366FDA9F3B6870DA3CA487D065F15D201DAB5F8F9CB56B8FBC60248578FDC3FB6CFAA74CB3187E77E9B473B5E91C613461C3EB5891AC90E4F89A18069FC138E72B8A976B341EB021CF9B71DD84C2A35DB00667495525EE5960A477984AA9138F86E50E32AFA3A1FE0E0C0852B61B6BE8EAC67F4F0E047748E2DDB12695888AFD119C6A9D0ECA35E6854352C7B9FF3AAB373405DB905BB3CA916A573E148D1234094AAB3E6EBEBA150FE0CA201DEE644EAB20153D17800C6337B127289174FFCFE61E3B7275F367C7A6D39C4FF5BEE47177D691491E61A8C08FDF99A5F8DC0488C75516C9DFBF7EDD7EF069C23538D2EA8E8C8A791D1129527E8DA0234DC802776C5D1EF86191029F3A066DB74AD69574D0C6D5F1B6393C079790F6B90DA5D55EA9CD7A6C6C438A8BB5DA32BCC950F694680788F4D7B9860A9E378A8B05B56A2AC1691C5A2042EB5D2D2FA760F5981D75932411D4A4113FA55573D0FC3A707FC99AD29244245C73479430332A6B5F682923B124D37169086E8F357A3F9005DAA28AFA886740239220017E3042B53E61A8FF32AAE6C090B3836AA63C7C40EE7FC267AD7302DA079E5CC1AC8C5DC47A8791D8CE69214C801C2CEEBA16546AB13FB4798231947032B83E848DE94033B19B4564519C43F6A78410E3D7AA4730449AA54C19D44A9558BA0D1C7619B47DD3DC5911B01F8ECC1D70A0DC32657913
e = 0x010001
q = 0x00dbb80e62e88f9ea33fc3d88c4c58d2a5900610c01e6395fddc6f5f93eb4f90da153a6e3d79171e9e4300b0c183a32b3559b09aa1e3d48b0aed53d227867dc36b00b8dfb7a797e93818a2a2db910a80ef5ff5dc746ce71151991fd3b670a1ebc0af1b77ef415a6f243c1946f2cf6a7883beb159cebc45de600988cd509088981d04e65fd29a2db475c5ac2c5c1163d47245f27209e344b7240e50c0aed750ade9715d156028a31eb2e5dbabb3cf25e57a58c19d2e6ff93f93e62e5e09e0c3159e0effaeeb294a64c70457cea948ace721770b39973a582360c1da78ce6238150de9428c174496a8b4b52065af07ebc69129f8a2ae1290eea4e0b6fee3910f8deb
assert N % q == 0
p = N // q
from Crypto.Util.number import inverse
d = inverse(e, (p-1)*(q-1))
ct = 0xa5c975a911be2f445016c9bf21309af98431c704d20fe95f0c401940177b946a1ba64cf024bb8d21184206ca30995727b216745e84a47afb1540b3538025ad04ee130f099a2658ca5b5e5d471ff85300bc155bbc52727f83af2e682bedf6ed8008f0d6a032e3fc53e4c191041e5e2594769af486bd3451070267cb8b7da928763144b91441579013c96ae17f8322b33e0f5008d6060eff874122cea5cdeb12f533edde43b675f470bd3e64e347739fcda4ec427159b2780b88f97e700548cadc32c3a6fc5fc294eb81792e3e1e59c14bc5b69151afd76a8be36e59fdbba3a2fe762253a994c828a33d0f62841257971cbee536c26419f2c5057fcdf25e63ad5a95784bf74488473158cff47e7f6e19f06cd03d0f1e2f58900e116d60bb0bc21ac92f34322c9a2b8ecec36b3debe4b00f0287eb648f12970bed5a2476747508e46bc5e7b50eebf8ede2e23f5dbc78f7696b6a7fa8d96b2af47688238bf63c5ac39fd455ff710f49e5d79c32462773cf94232642eb72d0f00b215c0eee8cb19b066e2c2a628d30f849ae3204f3951caab2dd92c4bc1bf0f095123489baa260c11d32246b3a6ea40d631b331d9c383721d96ec4fa7d04437368d6d2e5bfbb16d1a705ae6bf512f6d3a2fc477829872bed7c3dd35f28d35aa054b5fdcae669ddecb9f4a1b62eb4cfb963e54474f73ceb5e53894d1e92ec71733356e132abdac028dc
m = pow(ct, d, N)
print(m.to_bytes(512))
# b'\x00\x02\xc1\xa7\x98\xdbE\x8d\xbd\xcc\x1cGU\x91\xa8\x16\x8f\x1d\x99\xc5\x8e\xdd\xf2\x01Y7_E\xfa\xea\x07\xb6<ORv\xc82/zm^CV\x8fY\x15\r\xba\x97\x8e\x8d\xd8Q\xfe\x7f\x12\x98\xb6\xf2\x80\xb4p\xaab\xd7\x81G\xb14\xec:[~8\xb3,e\xef3\xd8\xc8\xac\t\xce\x80\x0c\x80;\xb46\xf1\xd4\xa0\x18\xd5\xf51\xd5. \x8d.\xa5\xb8\x91\xa5\x98\xd0\xcck\x99\x9f\x01\xe8i\x0f\xa8h\xd7*\x8a\xb0\xf4oy\xfc&\x18k\xb7f\xc5.\xe4\xc0\tJ\x10\x99\xd8%g$!\x91\x7fG\tT\x01-\xb9\x95\x06\xb3\x1c\x909\x1f*\xca/[\x11\xd2-`FL\x8b\x02\x02,:_.\x17\x0c\x05lu\x8b\x01q}\xdc \xd0\x93\x9c>\x97\xfa\xc0\x84\xba\x85\x1b\x90\xc3\xbd2\xcd\xd1\'\x83d\x06An\xdd\xb6\xf3\xc41\xcf4C\x90B \x11\xf2I\x92_\xaa\xeaSn\xd3\xa6F\xac\n\xab"]\xde\x9b\xd3;\xa1Jz\x08\xc5\xc45a\xca\x14\xca\xf3\xa7\x04>2uw=\x0c\xc1p?\x92<\x96z\x7fi\xfc\xed\x8cKS\x84\xac\xeep\xea+\xaf\x113\x84"\x92\xbc\xe8\x9eC9"]\x05?\xb5\x9d\xfaSe\x0em)d\x1f\xe99\x07a\xab\xfb09\x8e\xc7j\xaa\xa9B<T\xf7\x1b\xd0l\xbcxf\xb5\x14\xb1S \tj:[<\x1c\xb56\xe8`\xaa\xe0\xd5\xf4\xca\x03wE\xce\x9a\xa0\xbbf\xf4\x07\x19\xa8x_J7\x84\xd0\x11\x10;;\xd1\x9d\xd6\\%\xfc\x02Y\x99G=\xc4\xed\x04\xc9\xc2\x93\xec\xe29\xa2EU\xf1\x9e\xe0\x91c\xb0\xd4\xbc\xa3\xc7\xfa\xd9r\x89M\xc2\x11g\x98GF\xf8AN#p\x0f2\xfa[\x8dkD\xf9\xcd\xe2M%(\x84\xfa\xac\xc9\xe9Rt\xf9<\x08l\x8b9j\x91\xd5J\x00BSidesTLV2021{05sdRZoQp4PjasHHffYpAJlDdI5XNyz5CY9jepg8k0k}\n'

The flag is BSidesTLV2021{05sdRZoQp4PjasHHffYpAJlDdI5XNyz5CY9jepg8k0k}.