Keybroke
This is part of Round 1 of the OPENECSC.NO
After downloading the 2 files, we can see that the key.pem is partially redacted
-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEAx0JsV2KgfnHPLEaOV771Te+gIL/tBJGYaOaaZUDPynpn4SFk
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
fZJwsXdcbXFwvocS9ym9LtQjzM9ZzEEkN2SIqUZhxnpvdfenLf/gIFNNMKvU50b8
NF1Z4xK5l7Cs/RHMlAe66rclQa6VQ347rRr+qWMummccvK1BaCT+Tac6VnTg7GxL
ZI/tTR1yEKjs3OecYurSzn3/ASHcPKtJUgLzAwIDAQABAoIBABgtZxfzT6YICStG
JF9hPEKIoNVYdFnpkKSp1nISuyPGVnRqqN5R1nDDi8GAFzvbMMfYHdnGRMEqYDrt
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
54mAYBKdRoE0TgmldF5Z89vYOesXYNPn2V2ZvsyYMnDxqEcXCoNUK9yJdfqsgqaD
86Eo3v+tS0zr479MT7gv4WbZTeT8vzgtZJs+hgSXBd5jc06l2CMcrJGZgJd1uVuC
yyj+b4ECgYEA7Ur1WTOQkpEL/ZZYS1t/hV1NeCpRuXx4JCm3TF6HRY8Ez5BQid6o
WJ3IZv1+BS9xzh5R+celxUmhwEKosJjhPBl1OHQb3KMmOnVYFGMZRQ3KIi3mVpVB
Dm17kB/dtpHKTlS9YQbtg4j1xF4r2e/1BFkp1BViGRqfN+BZkNhSvrUCgYEA1vfg
0000000000000000000000000000000000000000000000000000000000000000
S2RgIYez934bQzE3uVop+OlM6K3nu4t9ZGuZq/C1Bm3RG0yB3VRM66TxigEauhiQ
oPHhNqwKfyo0ZD4JjfaKZ9tsslxDQnQjJc9mRdcCgYB6MHYkZ8QTZPNKsqdmrof8
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
ssIyPoyUJrxEFpeoWWxKXQKBgQDMLT2CO0MYC8q3OddnsqpIQiOI17UN44VOu/tZ
W/5XVeD1RfrlBVX+x1NnB84OhP22cHwwpJLl5gWaUc3FIS9DPo9VGwpwihTrPg8I
XWblN8hI5e9R1XYXaaVxwAWmxWvES+a652K40elaZRTEDWR30S4efPwd4KIFsVdc
50PFmw0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
-----END RSA PRIVATE KEY-----
Luckily for us, we can find some useful information in the asn.1 header
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponentINTEGER, -- e
privateExponent INTEGER, -- d
prime1INTEGER, -- p
prime2INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
❯ openssl asn1parse -in key.pem
0:d=0 hl=4 l=1187 cons: SEQUENCE
4:d=1 hl=2 l= 1 prim: INTEGER :00
7:d=1 hl=4 l= 257 prim: INTEGER :C7426C5762A07E71CF2C468E57BEF54DEFA020BFED04919868E69A6540CFCA7A67E12164D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D347D9270B1775C6D7170BE8712F729BD2ED423CCCF59CC4124376488A94661C67A6F75F7A72DFFE020534D30ABD4E746FC345D59E312B997B0ACFD11CC9407BAEAB72541AE95437E3BAD1AFEA9632E9A671CBCAD416824FE4DA73A5674E0EC6C4B648FED4D1D7210A8ECDCE79C62EAD2CE7DFF0121DC3CAB495202F303
268:d=1 hl=2 l= 3 prim: INTEGER :010001
273:d=1 hl=4 l= 256 prim: INTEGER :182D6717F34FA608092B46245F613C4288A0D5587459E990A4A9D67212BB23C656746AA8DE51D670C38BC180173BDB30C7D81DD9C644C12A603AEDD34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34E7898060129D4681344E09A5745E59F3DBD839EB1760D3E7D95D99BECC983270F1A847170A83542BDC8975FAAC82A683F3A128DEFFAD4B4CEBE3BF4C4FB82FE166D94DE4FCBF382D649B3E86049705DE63734EA5D8231CAC9199809775B95B82CB28FE6F81
533:d=1 hl=3 l= 129 prim: INTEGER :ED4AF559339092910BFD96584B5B7F855D4D782A51B97C782429B74C5E87458F04CF905089DEA8589DC866FD7E052F71CE1E51F9C7A5C549A1C042A8B098E13C197538741BDCA3263A7558146319450DCA222DE65695410E6D7B901FDDB691CA4E54BD6106ED8388F5C45E2BD9EFF5045929D41562191A9F37E05990D852BEB5
665:d=1 hl=3 l= 129 prim: INTEGER :D6F7E0D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D344B64602187B3F77E1B433137B95A29F8E94CE8ADE7BB8B7D646B99ABF0B5066DD11B4C81DD544CEBA4F18A011ABA1890A0F1E136AC0A7F2A34643E098DF68A67DB6CB25C4342742325CF6645D7
797:d=1 hl=3 l= 128 prim: INTEGER :7A30762467C41364F34AB2A766AE87FCD34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34D34B2C2323E8C9426BC441697A8596C4A5D
928:d=1 hl=3 l= 129 prim: INTEGER :CC2D3D823B43180BCAB739D767B2AA48422388D7B50DE3854EBBFB595BFE5755E0F545FAE50555FEC7536707CE0E84FDB6707C30A492E5E6059A51CDC5212F433E8F551B0A708A14EB3E0F085D66E537C848E5EF51D5761769A571C005A6C56BC44BE6BAE762B8D1E95A6514C40D6477D12E1E7CFC1DE0A205B1575CE743C59B
1060:d=1 hl=2 l= 52 prim: <ASN1 13>
1114:d=1 hl=2 l= 52 prim: appl [ 13 ]
Error in encoding
140623807173952:error:0D07209B:asn1 encoding routines:ASN1_get_object:too long:../crypto/asn1/asn1_lib.c:91:
This is the information we’re given:
| offset | length | |
|---|---|---|
| n (modulus) | 7 | 257 |
| e (public exponent) | 268 | 3 |
| d (private exponent) | 273 | 256 |
| p (first prime) | 533 | 129 |
| q (second prime) | 665 | 129 |
| dp (first exponent) | 797 | 128 |
| dq (second exponent) | 928 | 129 |
Keeping in mind that D34 is the redacted part:
At offset 7 we have n which is 257 in length but most of it is redacted by 0s.
e is 0x010001 which is 65537 as an integer
we have the full p at offset 533 and part of the q at offset 665, the rest being redacted.
dp and dq can be found at the bottom. We can’t use dp as it is redacted too, but dq is shown to us in full.
We can deduce that
N_upper_bits=0xC7426C5762A07E71CF2C468E57BEF54DEFA020BFED04919868E69A6540CFCA7A67E12164
p=0xED4AF559339092910BFD96584B5B7F855D4D782A51B97C782429B...6ED8388F5C45E2BD9EFF5045929D41562191A9F37E05990D852BEB5
e = 65537
dq = 0xCC2D3D823B43180BCAB739D767B2AA48422388D7B50DE3854E...2B8D1E95A6514C40D6477D12E1E7CFC1DE0A205B1575CE743C59B
By defnition we know that dq = d mod (q-1) therefore e*dq = kq * (q-1) + 1
kq shouldn’t take too long to bruteforce, so i wrote a quick python script
# we know that e*d = 1 mod (phi) => e*dq = 1 mod (q-1)
# since e = 65537, we can rearaange the equation to get q = ((e*dq - 1)/kp) + 1
N_upper_bits= 0xC7426C5762A07E71CF2C468E57BEF54DEFA020BFED04919868E69A6540CFCA7A67E12164
e = 65537
p = 0xED4AF559339092910BFD96584B5B7F855D4D782A51B97C782429B74C5E87...DDB691CA4E54BD6106ED8388F5C45E2BD9EFF5045929D41562191A9F37E05990D852BEB5
dq = 0xCC2D3D823B43180BCAB739D767B2AA48422388D7B50DE3854EBBFB595BF...05A6C56BC44BE6BAE762B8D1E95A6514C40D6477D12E1E7CFC1DE0A205B1575CE743C59B
for kq in range(1, e):
q = (e*dq - 1) // kq + 1
if q % 2 == 1:
if isPrime(q):
N = p*q
if(hex(N).startswith(hex(N_upper_bits))):
print(f"Found q: {q}\n\n\n\n")
print(hex(q))
Now we can use the 0x value for q and the p from before to re-generate the key using rsatool.py
❯ ./rsatool/rsatool.py -p 0xED4AF559339092910BFD96584B5B7F855D4D782A51B97C782429B74C5E87458F04CF905089DEA8589DC866FD7E052F71CE1E51F9C7A5C549A1C042A8B098E13C197538741BDCA3263A7558146319450DCA222DE65695410E6D7B901FDDB691CA4E54BD6106ED8388F5C45E2BD9EFF5045929D41562191A9F37E05990D852BEB5 -e 65537 -q 0xd6f7e0506179a744e6fec3aeb0e8f2d2a07b9f3c082a82bcdecbb10aecb2b76ab21517f0bf0674f8ef8fff6358719ecd7949734b64602187b3f77e1b433137b95a29f8e94ce8ade7bb8b7d646b99abf0b5066dd11b4c81dd544ceba4f18a011aba1890a0f1e136ac0a7f2a34643e098df68a67db6cb25c4342742325cf6645d7
Save the new key to a file and decrypt flag.enc using:
~/CTF/openECSCNO/rsa 22:32:10
❯ openssl rsautl -decrypt -inkey ./rsa_restored -in flag.enc -out flag.txt
~/CTF/openECSCNO/rsa 22:32:13
❯ cat flag.txt
ecsc{REDACTED}
I found this challenge fun, and a great opportunity to learn more about cryptography.