This weekend was 0CTF 2016 Quals and I had fun with two crypto challenges:

I have to say that I really liked the 0CTF challenges, although I only focused on those two crypto challenges.

Equation

Here is a RSA private key with its upper part masked. Can your recover the private key and decrypt the file?

http://dl.0ops.net/equation.zip

After downloading and extracting the file, we see a partially masked private key:

I didn't think that OCR will work properly, so I typewrote all characters manually:

The next step was to somehow recover as much data as possible. Private key files are usually PKCS#1 formatted:

RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

A hexdump of our key looks like this:

$> echo -n 'Os9mhOQRdqW2cwVrnNI72DLcAXpXUJ1HGwJBANWiJcDUGxZpnERxVw7s0913WXNt
        V4GqdxCzG0pG5EHThtoTRbyX0aqRP4U/hQ9tRoSoDmBn+3HPITsnbCy67VkCQBM4
        xZPTtUKM6Xi+16VTUnFVs9E4rqwIQCDAxn9UuVMBXlX2Cl0xOGUF4C5hItrX2woF
        7LVS5EizR63CyRcPovMCQQDVyNbcWD7N88MhZjujKuSrHJot7WcCaRmTGEIJ6TkU
        8NWt9BVjR4jVkZ2EqNd0KZWdQPukeynPcLlDEkIXyaQx' | base64 -d | hexdump 
00000000  3a cf 66 84 e4 11 76 a5  b6 73 05 6b 9c d2 3b d8  |:.f...v..s.k..;.|
00000010  32 dc 01 7a 57 50 9d 47  1b 02 41 00 d5 a2 25 c0  |2..zWP.G..A...%.|
00000020  d4 1b 16 69 9c 44 71 57  0e ec d3 dd 77 59 73 6d  |...i.DqW....wYsm|
00000030  57 81 aa 77 10 b3 1b 4a  46 e4 41 d3 86 da 13 45  |W..w...JF.A....E|
00000040  bc 97 d1 aa 91 3f 85 3f  85 0f 6d 46 84 a8 0e 60  |.....?.?..mF...`|
00000050  67 fb 71 cf 21 3b 27 6c  2c ba ed 59 02 40 13 38  |g.q.!;'l,..Y.@.8|
00000060  c5 93 d3 b5 42 8c e9 78  be d7 a5 53 52 71 55 b3  |....B..x...SRqU.|
00000070  d1 38 ae ac 08 40 20 c0  c6 7f 54 b9 53 01 5e 55  |.8...@ ...T.S.^U|
00000080  f6 0a 5d 31 38 65 05 e0  2e 61 22 da d7 db 0a 05  |..]18e...a".....|
00000090  ec b5 52 e4 48 b3 47 ad  c2 c9 17 0f a2 f3 02 41  |..R.H.G........A|
000000a0  00 d5 c8 d6 dc 58 3e cd  f3 c3 21 66 3b a3 2a e4  |.....X>...!f;.*.|
000000b0  ab 1c 9a 2d ed 67 02 69  19 93 18 42 09 e9 39 14  |...-.g.i...B..9.|
000000c0  f0 d5 ad f4 15 63 47 88  d5 91 9d 84 a8 d7 74 29  |.....cG.......t)|
000000d0  95 9d 40 fb a4 7b 29 cf  70 b9 43 12 42 17 c9 a4  |..@..{).p.C.B...|
000000e0  31                                                |1|

Okay, that doesn't immediately help me to recover our variables. Therefor I generated a new 1024 bit key and pasted it into an ASN.1 parser.

$> openssl genrsa 1024 > my.key
Generating RSA private key, 1024 bit long modulus
.....................++++++
........................++++++
e is 65537 (0x10001)

$> cat my.key 
-----BEGIN RSA PRIVATE KEY-----
MIICXQIBAAKBgQC+VckTaj3o9gMstX7nYlfQktB9SO9cVqxvCSF/2/KsdS16gGUd
qzExozAXiVrq2KU4cNz274i7heqBa9QAUbB1KhHydhMM98DQuRGLMpS+zEYCSauC
mkytOifVMuSC9CetBVAA3WWKDR5nhSS3b3/Okn2gWyycVN40FNlGXvY6TwIDAQAB
AoGAHOB5BEgPIoQIkUTr/wDtn8hWd1uUbSb9PE9fVL2zALU6dCZ8sNajPQusJTYC
pDTARGLjM1e+H+0+WepZHL9IDQtfadFVnm0Rsr/Fs8S7S1DiV3npagnJRplzZH1L
dqRw77SupAG+s9823HLbuQSF4G+0FGbl1mlkxKiomDfzJmECQQDwQfyslSww/jeH
eJUAoFhZJmTtl5+5po4YwSXZs4sUGEwr8fgiIxj9cvGiY4FhGSh2hqkQtCuMyU2U
bYsBB7n/AkEAys5pD9ITetRreyuMwEFhu8OPjYo+0GUGHJYwc2B/lr6BBECjqmCM
qfOCMy7lQbD0fkCmhh6aJpFOsBJRC2dfsQJBAJ3U65XApXhF+NqxF0mDDKb8Nv9y
RQaj6ONQN3pNnYcE8z1HRxe98NPHJ//i2IKeEVvT2MrVYWqqb6GbWN7DYacCQQCJ
gv2f2YyVy3R5VqUgMvTm0IoEqck/mlBTj86YXMUGXHO0g3O18bNPBSqyM8kFCsws
0v9Wj2dsYThekHzdY6FxAkAWuxSlakZuexyazm7XoIZrEqqzlYs0bcbPm9gwF5IL
sqMS35m/AFloRmFbeY+eHQb8K0FScXORR8JE12kQuwtY
-----END RSA PRIVATE KEY-----

I noticed that all lower values have hl=2 l= 64 or hl=2 l= 65. Can we find this information in a hexdump of our generated key?

 cat my.key | grep -v "RSA"  |base64 -d | hexdump -C 
00000000  30 82 02 5d 02 01 00 02  81 81 00 be 55 c9 13 6a  |0..]........U..j|
00000010  3d e8 f6 03 2c b5 7e e7  62 57 d0 92 d0 7d 48 ef  |=...,.~.bW...}H.|
00000020  5c 56 ac 6f 09 21 7f db  f2 ac 75 2d 7a 80 65 1d  |\V.o.!....u-z.e.|
00000030  ab 31 31 a3 30 17 89 5a  ea d8 a5 38 70 dc f6 ef  |.11.0..Z...8p...|
00000040  88 bb 85 ea 81 6b d4 00  51 b0 75 2a 11 f2 76 13  |.....k..Q.u*..v.|
00000050  0c f7 c0 d0 b9 11 8b 32  94 be cc 46 02 49 ab 82  |.......2...F.I..|
00000060  9a 4c ad 3a 27 d5 32 e4  82 f4 27 ad 05 50 00 dd  |.L.:'.2...'..P..|
00000070  65 8a 0d 1e 67 85 24 b7  6f 7f ce 92 7d a0 5b 2c  |e...g.$.o...}.[,|
00000080  9c 54 de 34 14 d9 46 5e  f6 3a 4f 02 03 01 00 01  |.T.4..F^.:O.....|
00000090  02 81 80 1c e0 79 04 48  0f 22 84 08 91 44 eb ff  |.....y.H."...D..|
000000a0  00 ed 9f c8 56 77 5b 94  6d 26 fd 3c 4f 5f 54 bd  |....Vw[.m&.<O_T.|
000000b0  b3 00 b5 3a 74 26 7c b0  d6 a3 3d 0b ac 25 36 02  |...:t&|...=..%6.|
000000c0  a4 34 c0 44 62 e3 33 57  be 1f ed 3e 59 ea 59 1c  |.4.Db.3W...>Y.Y.|
000000d0  bf 48 0d 0b 5f 69 d1 55  9e 6d 11 b2 bf c5 b3 c4  |.H.._i.U.m......|
000000e0  bb 4b 50 e2 57 79 e9 6a  09 c9 46 99 73 64 7d 4b  |.KP.Wy.j..F.sd}K|
000000f0  76 a4 70 ef b4 ae a4 01  be b3 df 36 dc 72 db b9  |v.p........6.r..|
00000100  04 85 e0 6f b4 14 66 e5  d6 69 64 c4 a8 a8 98 37  |...o..f..id....7|
00000110  f3 26 61 02 41 00 f0 41  fc ac 95 2c 30 fe 37 87  |.&a.A..A...,0.7.|
00000120  78 95 00 a0 58 59 26 64  ed 97 9f b9 a6 8e 18 c1  |x...XY&d........|
00000130  25 d9 b3 8b 14 18 4c 2b  f1 f8 22 23 18 fd 72 f1  |%.....L+.."#..r.|
00000140  a2 63 81 61 19 28 76 86  a9 10 b4 2b 8c c9 4d 94  |.c.a.(v....+..M.|
00000150  6d 8b 01 07 b9 ff 02 41  00 ca ce 69 0f d2 13 7a  |m......A...i...z|
00000160  d4 6b 7b 2b 8c c0 41 61  bb c3 8f 8d 8a 3e d0 65  |.k{+..Aa.....>.e|
00000170  06 1c 96 30 73 60 7f 96  be 81 04 40 a3 aa 60 8c  |...0s`.....@..`.|
00000180  a9 f3 82 33 2e e5 41 b0  f4 7e 40 a6 86 1e 9a 26  |...3..A..~@....&|
00000190  91 4e b0 12 51 0b 67 5f  b1 02 41 00 9d d4 eb 95  |.N..Q.g_..A.....|
000001a0  c0 a5 78 45 f8 da b1 17  49 83 0c a6 fc 36 ff 72  |..xE....I....6.r|
000001b0  45 06 a3 e8 e3 50 37 7a  4d 9d 87 04 f3 3d 47 47  |E....P7zM....=GG|
000001c0  17 bd f0 d3 c7 27 ff e2  d8 82 9e 11 5b d3 d8 ca  |.....'......[...|
000001d0  d5 61 6a aa 6f a1 9b 58  de c3 61 a7 02 41 00 89  |.aj.o..X..a..A..|
000001e0  82 fd 9f d9 8c 95 cb 74  79 56 a5 20 32 f4 e6 d0  |.......tyV. 2...|
000001f0  8a 04 a9 c9 3f 9a 50 53  8f ce 98 5c c5 06 5c 73  |....?.PS...\..\s|
00000200  b4 83 73 b5 f1 b3 4f 05  2a b2 33 c9 05 0a cc 2c  |..s...O.*.3....,|
00000210  d2 ff 56 8f 67 6c 61 38  5e 90 7c dd 63 a1 71 02  |..V.gla8^.|.c.q.|
00000220  40 16 bb 14 a5 6a 46 6e  7b 1c 9a ce 6e d7 a0 86  |@....jFn{...n...|
00000230  6b 12 aa b3 95 8b 34 6d  c6 cf 9b d8 30 17 92 0b  |k.....4m....0...|
00000240  b2 a3 12 df 99 bf 00 59  68 46 61 5b 79 8f 9e 1d  |.......YhFa[y...|
00000250  06 fc 2b 41 52 71 73 91  47 c2 44 d7 69 10 bb 0b  |..+ARqs.G.D.i...|
00000260  58                                                |X|
00000261

Yes, we can. For example 02 40 16 bb ...:

00000210  d2 ff 56 8f 67 6c 61 38  5e 90 7c dd 63 a1 71 02  |..V.gla8^.|.c.q.|  
00000220  40 16 bb 14 a5 6a 46 6e  7b 1c 9a ce 6e d7 a0 86  |@....jFn{...n...|

We see:

0x02 is the same as our hl value
0x40 is the same as 64 and our l value
0x16bb is the beginning of q's inverse.

So it matches

543:d=1  hl=2 l=  64 prim:  INTEGER           :16BB...

pretty well! We learned that our values are formatted like this 02[length][data].

The next thing I did was to look for 0x02 in the chal's key hexdump and copy the hex numbers until I find another one. I started at the end of the hexdump and worked my way up.

This is were I made my first mistake, because I ignored the [length] value and forgot that 0x02 can be a part of the number, so I first ended up with these:

p = 0x?????...????3acf6684e41176a5b673056b9cd23bd832dc017a57509d471b
q = 0x00d5a225c0d41b16699c4471570eecd3dd7759736d5781aa7710b31b4a46e441d386da1345bc97d1aa913f853f850f6d4684a80e6067fb71cf213b276c2cbaed59
dp= 0x1338c593d3b5428ce978bed7a553527155b3d138aeac084020c0c67f54b953015e55f60a5d31386505e02e6122dad7db0a05ecb552e448b347adc2c9170fa2f3
dq= 0x00d5c8d6dc583ecdf3c321663ba32ae4ab1c9a2ded67
qi= 0x1993184209e93914f0d5adf415634788d5919d84a8d77429959d40fba47b29cf70b943124217c9a431

But after taking a small break, I noticed the mistake and found the correct numbers:

q = 0x?????...????3acf6684e41176a5b673056b9cd23bd832dc017a57509d471b
dp = 0x00d5a225c0d41b16699c4471570eecd3dd7759736d5781aa7710b31b4a46e441d386da1345bc97d1aa913f853f850f6d4684a80e6067fb71cf213b276c2cbaed59
dq = 0x1338c593d3b5428ce978bed7a553527155b3d138aeac084020c0c67f54b953015e55f60a5d31386505e02e6122dad7db0a05ecb552e448b347adc2c9170fa2f3
qi = 0x00d5c8d6dc583ecdf3c321663ba32ae4ab1c9a2ded6702691993184209e93914f0d5adf415634788d5919d84a8d77429959d40fba47b29cf70b943124217c9a431

Okay, we have the following now:

q or at least the last bytes of it
dp: p's CRT exponent
dq: q's CRT exponent
qi: CRT coefficient

We need to recover:

q: 2nd prime
p: 1st prime
e: public exponent
d: private exponent
n: modulus

Since the title is equation I looked up the RSA math again. RFC3447 did help.

The given data can be put in the following equations:

e * dp === 1 (mod (p-1)) = d mod (p-1)
e * dq === 1 (mod (q-1)) = d mod (q-1)
q * qi === 1 (mod p) = q^-1 mod p

I focused on the equations without d or q^-1 and started to rearrange the terms by rewriting the modular inverse:

e * dp === 1 (mod (p-1))
e * dq === 1 (mod (q-1))
q * qi === 1 (mod p)
=> 
e * dp - k*(p-1) == 1
e * dq - j*(q-1) == 1
q * qi - l*(p) == 1
=> 
e * dp == 1 + k*(p-1)
e * dq == 1 + j*(q-1)
q * qi == 1 + l*(p)
=>
e * dp -1 == k*(p-1)
e * dq -1 == j*(q-1)
q * qi -1 == l*(p)
=>
(e * dp -1)/k == (p-1)
(e * dq -1)/j == (q-1)
(q * qi -1)/l == (p)
=>
(e * dp -1)/k +1 == (p)
(e * dq -1)/j +1 == (q)
(q * qi -1)/l == (p)

At this point I assumed that e=0x10001 because flag.enc is 128 bytes in size and the values are at least 64 bytes, so that the private key is probably a standard 1024 bit key.

As we have the last part of q we can use the second equation to iterate over j until we find a prime q:

N = 100000
M = 1

for j in range(N,1,-1):
	q_ = (e * dq -1)/j +1
	if "3acf6684e41176a5b673056b9cd23bd832dc017a57509d471b" in str(hex(q_)):
		print q_, j

#=> q:
#12502893634923161599824465146407069882228513776947707295476805997311776855879024002289593598657949783937041929668443115224477369136089557911464046118127387 5277

Yafu tells us that the number is probably a prime:

$> yafu "isprime(12502893634923161599824465146407069882228513776947707295476805997311776855879024002289593598657949783937041929668443115224477369136089557911464046118127387)"

probably prime
ans = 1

and it is also 64 bytes in size: YES!

q = 0xeeb8defdf9f0aec0036116ac9d84ab925e7606e9ba4618bfc50d7fa42d3ecf7901aa5867c782ea3acf6684e41176a5b673056b9cd23bd832dc017a57509d471bL
e = 0x10001

With q and equation I and III we can recover p. I use the first equation to calculate a p and the third equation to verify it.

import sys
M = 1
N = 100000
for k in range(M,N,1):
    if k % 1000 == 0:
        print k 
    p1 = (e * dp -1)/k +1
    try:
        m = modinv(q, p1)
        if m == qi:
            print p1, k
            sys.exit(1)
    except Exception as e:
        print e
# => p
#12883429939639100479003058518523248493821688207697138417834631218638027564562306620214863988447681300666538212918572472128732943784711527013224777474072569 56917

And again, Yafu assures us that p is prime.

p = 0x0xf5fce4ce6b9d0acfb1431c0ce69c0a5aeeba68cd417a8ab4ac05d43e2b49fcb734de9d120ed735f8774124bf3ce650905e8e0b61a721da94c15322a700cf5ff9L

Now we have recovered all important RSA parts. I used my script to create a PEM formatted key from p , q , e:

We can use this key to decrypt the flag:

$> cat flag.enc  | openssl rsautl -decrypt -inkey test-output.key 
0ctf{Keep_ca1m_and_s01ve_the_RSA_Eeeequati0n!!!}

RSA?

It seems easy, right?

Tip: openssl rsautl -encrypt -in FLAG -inkey public.pem -pubin -out flag.enc

Link: http://dl.0ops.net/rsa.zip

Unfortunately, I didn't solve this one, but I still want to outline my idea. We're given a public.pem and flag.enc.

$> openssl rsa -inform PEM -text -noout -pubin < public.pem 
Public-Key: (314 bit)
Modulus:
    02:ca:a9:c0:9d:c1:06:1e:50:7e:5b:7f:39:dd:e3:
    45:5f:cf:e1:27:a2:c6:9b:62:1c:83:fd:9d:3d:3e:
    aa:3a:ac:42:14:7c:d7:18:8c:53
Exponent: 3 (0x3)

We notice that the modulus is quite small (314 bit) and the public exponent is small too (3).

My first idea was to run Yafu and factor the modulus:

$> yafu "factor(0x02caa9c09dc1061e507e5b7f39dde3455fcfe127a2c69b621c83fd9d3d3eaa3aac42147cd7188c53)"
[snip]
Total factoring time = 45.9349 seconds
***factors found***

P32 = 26440615366395242196516853423447
P32 = 27038194053540661979045656526063
P32 = 32581479300404876772405716877547

Oh, wait, stop! Why are there 3 factors? Usually only two primes are used for RSA. Googling for multiple primes rsa leads to a stackexchange thread and it looks like this system is called RSA-MP. Nice!

Quoting RFC3447

This specification supports so-called "multi-prime" RSA where the
modulus may have more than two prime factors. The benefit of multi-
prime RSA is lower computational cost for the decryption and
signature primitives, provided that the CRT (Chinese Remainder
Theorem) is used. Better performance can be achieved on single
processor platforms, but to a greater extent on multiprocessor
platforms, where the modular exponentiations involved can be done in
parallel.

From page 45 of the RFC we learn that additional primes can be specified in the OtherPrimeInfo Sequence:

     OtherPrimeInfos ::= SEQUENCE SIZE(1..MAX) OF OtherPrimeInfo

    OtherPrimeInfo ::= SEQUENCE {
        prime             INTEGER,  -- ri
        exponent          INTEGER,  -- di
        coefficient       INTEGER   -- ti
    }
The fields of type OtherPrimeInfo have the following meanings:

prime is a prime factor r_i of n, where i >= 3.

exponent is d_i = d mod (r_i - 1).

coefficient is the CRT coefficient t_i = (r_1 * r_2 * ... * r_(i-1))^(-1) mod r_i.

As I already have the primes, I thought that this would be straight forward, but with e=0x3 I wasn't able to compute d, because I couldn't find a modular inverse for modinv(e,phi) with phi=lcm(r1-1,r2-1,r3-1). So I assumed maybe 0x3 is wrong, because with e=0x10001 I was able to calculate it.

import pyasn1.codec.der.encoder  
import pyasn1.type.univ  
import base64

# SRC https://gist.github.com/endolith/114336
def gcd(*numbers):
    """Return the greatest common divisor of the given integers"""
    from fractions import gcd
    return reduce(gcd, numbers)

# SRC https://gist.github.com/endolith/114336
def lcm(*numbers):
    """Return lowest common multiple."""    
    def lcm(a, b):
        return (a * b) // gcd(a, b)
    return reduce(lcm, numbers, 1)

# SRC: https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

# SRC: https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
def modinv(a, m):
    gcd, x, y = egcd(a, m)
    if gcd != 1:
        return None  # modular inverse does not exist
    else:
        return x % m

r1 = 26440615366395242196516853423447L
r2 = 27038194053540661979045656526063L
r3 = 32581479300404876772405716877547L

e = 0x10001 #0x3
n = r1 * r2 * r3

phi = lcm(r1-1,r2-1,r3-1)
d = modinv(e, phi)
dr1 = modinv(e, r1-1)
dr2 = modinv(e, r2-1)
r2i = modinv(r2, r1)
dr3 = modinv(e, r3-1) 
r3i = modinv(r1*r2,r3)

from pyasn1_modules.rfc3447 import *

oo = OtherPrimeInfo()
oo.setComponentByName('prime',pyasn1.type.univ.Integer(r3))
oo.setComponentByName('exponent',pyasn1.type.univ.Integer(dr3))
oo.setComponentByName('coefficient',pyasn1.type.univ.Integer(r3i))

o = OtherPrimeInfos()
o.setComponents(oo)

pk = RSAPrivateKey()
pk.setComponentByName('version',pyasn1.type.univ.Integer(1))
pk.setComponentByName('modulus',pyasn1.type.univ.Integer(n))
pk.setComponentByName('publicExponent',pyasn1.type.univ.Integer(e))
pk.setComponentByName('privateExponent',pyasn1.type.univ.Integer(d))
pk.setComponentByName('prime1',pyasn1.type.univ.Integer(r1))
pk.setComponentByName('prime2',pyasn1.type.univ.Integer(r2))
pk.setComponentByName('exponent1',pyasn1.type.univ.Integer(dr1))
pk.setComponentByName('exponent2',pyasn1.type.univ.Integer(dr2))
pk.setComponentByName('coefficient',pyasn1.type.univ.Integer(r2i))
pk.setComponentByName('otherPrimeInfos',o)

der = pyasn1.codec.der.encoder.encode(pk)
key = template.format(base64.encodestring(der).decode('ascii'))
print key

This should create a valid multi prime key:

$> python2 create-key.py > test.key

$> cat test.key 
-----BEGIN RSA PRIVATE KEY-----
MIHeAgEBAigCyqnAncEGHlB+W3853eNFX8/hJ6LGm2Icg/2dPT6qOqxCFHzXGIxTAgMBAAECJwhc
sx8awUESjQqcsvxmm0D0hDBMU8bXaChRWu1Oubdfg53dkZtWzQIOAU26PGpA93et4X/unVcCDgFV
RR3rZqvxnC6pK/zvAg4Amj4jQjC4r7XL7WcJjQIOAOIvCQF37wYXaaWeDekCDgDl1BdR7hYB0VE/
Uy4HMDEwLwIOAZs8cAFuheUbY2PugOsCDQSGMLFDVwPDPl+uEwsCDgFaK3wodECgvAVQ2zob
-----END RSA PRIVATE KEY-----

$>  openssl asn1parse -inform PEM -in test.key 
    0:d=0  hl=3 l= 222 cons: SEQUENCE          
    3:d=1  hl=2 l=   1 prim: INTEGER           :01
    6:d=1  hl=2 l=  40 prim: INTEGER           :02CAA9C09DC1061E507E5B7F39DDE3455FCFE127A2C69B621C83FD9D3D3EAA3AAC42147CD7188C53
   48:d=1  hl=2 l=   3 prim: INTEGER           :010001
   53:d=1  hl=2 l=  39 prim: INTEGER           :085CB31F1AC141128D0A9CB2FC669B40F484304C53C6D76828515AED4EB9B75F839DDD919B56CD
   94:d=1  hl=2 l=  14 prim: INTEGER           :014DBA3C6A40F777ADE17FEE9D57
  110:d=1  hl=2 l=  14 prim: INTEGER           :0155451DEB66ABF19C2EA92BFCEF
  126:d=1  hl=2 l=  14 prim: INTEGER           :9A3E234230B8AFB5CBED67098D
  142:d=1  hl=2 l=  14 prim: INTEGER           :E22F090177EF061769A59E0DE9
  158:d=1  hl=2 l=  14 prim: INTEGER           :E5D41751EE1601D1513F532E07
  174:d=1  hl=2 l=  49 cons: SEQUENCE          
  176:d=2  hl=2 l=  47 cons: SEQUENCE          
  178:d=3  hl=2 l=  14 prim: INTEGER           :019B3C70016E85E51B6363EE80EB
  194:d=3  hl=2 l=  13 prim: INTEGER           :048630B1435703C33E5FAE130B
  209:d=3  hl=2 l=  14 prim: INTEGER           :015A2B7C287440A0BC0550DB3A1B

However, it looks like openssl's rsa doesn't like multi prime keys, or at least I always got an error like this:

$> cat flag.enc  | openssl rsautl -decrypt -inkey test.key 
unable to load Private Key
140439350462104:error:0D078094:asn1 encoding routines:ASN1_ITEM_EX_D2I:sequence length mismatch:tasn_dec.c:467:Type=RSA
140439350462104:error:04093004:rsa routines:OLD_RSA_PRIV_DECODE:RSA lib:rsa_ameth.c:119:
140439350462104:error:0D0680A8:asn1 encoding routines:ASN1_CHECK_TLEN:wrong tag:tasn_dec.c:1199:
140439350462104:error:0D07803A:asn1 encoding routines:ASN1_ITEM_EX_D2I:nested asn1 error:tasn_dec.c:374:Type=X509_ALGOR
140439350462104:error:0D08303A:asn1 encoding routines:ASN1_TEMPLATE_NOEXP_D2I:nested asn1 error:tasn_dec.c:697:Field=pkeyalg, Type=PKCS8_PRIV_KEY_INFO
140439350462104:error:0907B00D:PEM routines:PEM_READ_BIO_PRIVATEKEY:ASN1 lib:pem_pkey.c:141:

Neither rsa -inform was helpful:

openssl rsa -inform PEM -text -noout < test.key 
unable to load Private Key
140582949205656:error:0D078094:asn1 encoding routines:ASN1_ITEM_EX_D2I:sequence length mismatch:tasn_dec.c:467:Type=RSA
140582949205656:error:04093004:rsa routines:OLD_RSA_PRIV_DECODE:RSA lib:rsa_ameth.c:119:
140582949205656:error:0D0680A8:asn1 encoding routines:ASN1_CHECK_TLEN:wrong tag:tasn_dec.c:1199:
140582949205656:error:0D07803A:asn1 encoding routines:ASN1_ITEM_EX_D2I:nested asn1 error:tasn_dec.c:374:Type=X509_ALGOR
140582949205656:error:0D08303A:asn1 encoding routines:ASN1_TEMPLATE_NOEXP_D2I:nested asn1 error:tasn_dec.c:697:Field=pkeyalg, Type=PKCS8_PRIV_KEY_INFO
140582949205656:error:0907B00D:PEM routines:PEM_READ_BIO_PRIVATEKEY:ASN1 lib:pem_pkey.c:141:

This is were I gave up. Even though this might not be the solution to the challenge, I wonder what I did wrong that openssl can't parse the multi-prime key. However, I learned something new and that are the kind of challenges I really enjoy and don't mind failing. I'm looking forward to other writeups, though.
Update: I've found a correct solution for RSA?. Cube roots and CRT had to be used.

-=-