Problem statement:
> The hacker Th3 Pr0f3ss0r figured out a new way to use RSA encryption to sendflags to his CTF group.
> Will you be able to decipher the message and retrieve the flag?
Two files were attached, flag.enc and pub.key.
Well, first things first. Let's look at pub.key first since flag.enc likelywon't be very useful.
```sh$ openssl rsa -in pub.key -pubin -noout -textPublic-Key: (1683 bit)Modulus:    04:13:cf:27:35:04:00:75:00:68:00:05:5b:0e:c2:    19:83:8d:e2:3c:00:00:01:86:00:00:00:68:00:00:    03:93:80:f2:3d:5b:ea:1d:ed:1b:15:db:a0:47:76:    35:45:dc:fc:75:e9:4c:71:d7:81:fd:b0:bb:b6:53:    7a:2f:41:88:1e:89:8d:3d:e7:df:50:3d:37:28:a8:    45:e9:df:6d:7c:60:36:68:13:cf:5b:68:19:83:8d:    e2:3c:00:00:01:86:00:00:04:13:cf:0d:1b:93:01:    04:00:75:00:68:00:05:5b:0e:c2:19:83:8d:e2:3c:    00:00:01:86:00:00:00:68:01:d4:00:00:00:00:00:    00:01:a0:00:00:00:00:00:00:03:93:80:f2:3d:5b:    ea:1d:e4:82:01:a0:00:00:00:00:00:0d:01:38:00:    b6:85:6f:6d:2b:51:aa:0d:02:71:6e:94:3d:44:aa:    0f:53:c0:50:39:75:51:aa:11:13:cf:41:4e:00:00:    00:00:0d:00:0d:04:92:00:00:04:fa:00:00:00:df:    e5Exponent: 65537 (0x10001)```
The exponent looks normal at least. But there's an awful lot of 00s in thatpublic key. It doesn't seem to be very random. And that's certainly an unusualnumber of bits in the key. Never hurts to try to factor it!
```python#!/usr/bin/env python3
# File: factor.py
import sympy
key = '''04:13:cf:27:35:04:00:75:00:68:00:05:5b:0e:c2:    19:83:8d:e2:3c:00:00:01:86:00:00:00:68:00:00:    03:93:80:f2:3d:5b:ea:1d:ed:1b:15:db:a0:47:76:    35:45:dc:fc:75:e9:4c:71:d7:81:fd:b0:bb:b6:53:    7a:2f:41:88:1e:89:8d:3d:e7:df:50:3d:37:28:a8:    45:e9:df:6d:7c:60:36:68:13:cf:5b:68:19:83:8d:    e2:3c:00:00:01:86:00:00:04:13:cf:0d:1b:93:01:    04:00:75:00:68:00:05:5b:0e:c2:19:83:8d:e2:3c:    00:00:01:86:00:00:00:68:01:d4:00:00:00:00:00:    00:01:a0:00:00:00:00:00:00:03:93:80:f2:3d:5b:    ea:1d:e4:82:01:a0:00:00:00:00:00:0d:01:38:00:    b6:85:6f:6d:2b:51:aa:0d:02:71:6e:94:3d:44:aa:    0f:53:c0:50:39:75:51:aa:11:13:cf:41:4e:00:00:    00:00:0d:00:0d:04:92:00:00:04:fa:00:00:00:df:    e5'''key = int(key.replace('\n','').replace(' ','').replace(':',''), 16)
for div in sympy.ntheory.factor_.divisors(key):    print('divisor:', hex(div))```
Run it and see what happens...
```shdivisor: 0x1divisor: 0xddivisor: 0x504b03041400090008000069774a01f66d602c0000001e00000008000000466c61672e747874b350735b19307a407375e1af7c08c1ceec2149842dce5267809fe3323fd6c268a23f51e58f395ff4bacc52f4504b070801f66d602c0000001e000000504b01021f001400090008000069774a01f66d602c0000001e000000080024000000000000002000000000000000466c61672e7478740a00200000000000010018000e0a43a5efa3d20100301c32c9a2d2012dd3b766e1a3d201504b050600000000010001005a000000620000001139divisor: 0x413cf2735040075006800055b0ec219838de23c00000186000000680000039380f23d5bea1ded1b15dba047763545dcfc75e94c71d781fdb0bbb6537a2f41881e898d3de7df503d3728a845e9df6d7c60366813cf5b6819838de23c0000018600000413cf0d1b9301040075006800055b0ec219838de23c000001860000006801d400000000000001a0000000000000039380f23d5bea1de48201a000000000000d013800b6856f6d2b51aa0d02716e943d44aa0f53c050397551aa1113cf414e000000000d000d0492000004fa000000dfe5```
That was quick! I guess they picked such a small prime to make it easy on us.
We factored out `p` and `q`. But we still have to figure out how to use theseto decrypt the message. Thankfully I found a quick writeup on how to do this:
https://0day.work/how-i-recovered-your-private-key-or-why-small-keys-are-bad/
Using the code from there, I was able to write a quick script to create priv.key,a private key formatted for OpenSSL usage.
Now let's use it to decrypt the flag and we'll be done!
```sh$ openssl rsautl -decrypt -inkey priv.key <flag.encTry harder!!!```
What?! All this way and still no flag :( But where could the flag be? There'sno way the encrypted bytes decrypt to two different values somehow.
It was at this point that one of my teammates made a very astute observation.Remember this divisor?
    divisor: 0x504b03041400090008000069774a01f66d602c0000001e00000008000000466c61672e747874b350735b19307a407375e1af7c08c1ceec2149842dce5267809fe3323fd6c268a23f51e58f395ff4bacc52f4504b070801f66d602c0000001e000000504b01021f001400090008000069774a01f66d602c0000001e000000080024000000000000002000000000000000466c61672e7478740a00200000000000010018000e0a43a5efa3d20100301c32c9a2d2012dd3b766e1a3d201504b050600000000010001005a000000620000001139
Notice anything about the beginning of the number? Maybe converting it totext will help you see what he saw...
```python>>> import codecs>>> s = codecs.decode('504b03041400090008000069774a01f66d602c0000001e00000008000000466c61672e747874b350735b19307a407375e1af7c08c1ceec2149842dce5267809fe3323fd6c268a23f51e58f395ff4bacc52f4504b070801f66d602c0000001e000000504b01021f001400090008000069774a01f66d602c0000001e000000080024000000000000002000000000000000466c61672e7478740a00200000000000010018000e0a43a5efa3d20100301c32c9a2d2012dd3b766e1a3d201504b050600000000010001005a000000620000001139', 'hex')>>> sb'PK\x03\x04\x14\x00\t\x00\x08\x00\x00iwJ\x01\xf6m`,\x00\x00\x00\x1e\x00\x00\x00\x08\x00\x00\x00Flag.txt\xb3Ps[\x190z@su\xe1\xaf|\x08\xc1\xce\xec!I\x84-\xceRg\x80\x9f\xe32?\xd6\xc2h\xa2?Q\xe5\x8f9_\xf4\xba\xccR\xf4PK\x07\x08\x01\xf6m`,\x00\x00\x00\x1e\x00\x00\x00PK\x01\x02\x1f\x00\x14\x00\t\x00\x08\x00\x00iwJ\x01\xf6m`,\x00\x00\x00\x1e\x00\x00\x00\x08\x00$\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x00\x00\x00\x00\x00Flag.txt\n\x00 \x00\x00\x00\x00\x00\x01\x00\x18\x00\x0e\nC\xa5\xef\xa3\xd2\x01\x000\x1c2\xc9\xa2\xd2\x01-\xd3\xb7f\xe1\xa3\xd2\x01PK\x05\x06\x00\x00\x00\x00\x01\x00\x01\x00Z\x00\x00\x00b\x00\x00\x00\x119'```
That's a zip file magic value at the beginning! Plus we see 'Flag.txt' severaltimes. Let's save it so we can take a look.
```python>>> with open('optimus.zip', 'wb') as f:...   f.write(s)...210```
Now unzip it and we're done!
```sh$ unzip optimus.zipArchive:  optimus.zip
caution:  zipfile comment truncated[optimus.zip] Flag.txt password:```
...
...
...
All hope's not lost yet! Zips are usually pretty easy to crack. Let's feed itto john (the ripper).
```sh$ zip2john -a Flag.txt out.zip >zip.hashUsing file Flag.txt as an 'ASCII' quick check filever 14  out.zip->Flag.txt PKZIP Encr: cmplen=44, decmplen=30, crc=606DF601$ john zip.hashLoaded 1 password hash (PKZIP [32/64])Will run 16 OpenMP threadsPress 'q' or Ctrl-C to abort, almost any other key for status123123           (out.zip)1g 0:00:00:00 DONE 2/3 (2017-12-18 02:06) 16.66g/s 1289Kp/s 1289Kc/s 1289KC/s 123456..gbbyUse the "--show" option to display all of the cracked passwords reliablySession completed```
That wasn't bad at all. Now let's unzip it and get the flag:
```sh$ unzip optimus.zipArchive:  optimus.zip
caution:  zipfile comment truncated[optimus.zip] Flag.txt password:  inflating: Flag.txt$ cat Flag.txt3DS{Pr1m3_numb3rs_4re_c00l!!!}```