# Damn Randomware!

• Category: Crypto
• 300 points
• Solved by JCTF Team

## 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
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
882f4967ef79*02820101*00dbb80e62e88f9ea33fc3d88c4c58d2a5900610c01e6395fddc6f5f93eb4f90da153a6e3d79171e
9e4300b0c183a32b3559b09aa1e3d48b0aed53d227867dc36b00b8dfb7a797e93818a2a2db910a80ef5ff5dc746ce7115199
1fd3b670a1ebc0af1b77ef415a6f243c1946f2cf6a7883beb159cebc45de600988cd509088981d04e65fd29a2db475c5ac2c
c3159e0effaeeb294a64c70457cea948ace721770b39973a582360c1da78ce6238150de9428c174496a8b4b52065af07ebc6
9129f8a2ae1290eea4e0b6fee3910f8deb*02820100*478a0dae0bbed93bd26f7fcb915a51c67c345f3445d8d4a65dbc45329d
f9107050f4c61e3f5197afd6b72634d62e7ccac3cdc38ac52ae79195bcba9f71b88e9ae247696ca6fd0983a5c11896e9bccd
c304c193ceda44b63e165641dd5aae1b05dece3c6d88df3fa8d98f9335031b272d54701ef9e67a604c6949b739ab29c053c2
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:

e = 0x010001
assert N % q == 0
p = N // q
from Crypto.Util.number import inverse
d = inverse(e, (p-1)*(q-1))
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}.