[EKOPARTY PRE-CTF 2015] [Cry100 – RSA 2070] Write Up

Description

Recover the private key and the flag.

Hints: Check your padding 🙂

Attachment: crypto100.zip

Resolution

It was a RSA public key, with a non common size of 2070 bits:
$ openssl rsa -noout -text -inform PEM -in public.key -pubin

Public-Key: (2070 bit)
Modulus:
25:b1:8b:f5:f3:89:09:7d:17:23:78:66:bb:51:cf:
f8:de:92:24:53:74:9e:bc:40:3b:09:95:c9:7c:0e:
38:6d:46:c1:61:ca:df:f7:7c:69:86:0d:ae:47:91:
c2:14:cf:84:87:aa:aa:9f:26:e9:20:a9:77:83:49:
06:03:8a:ef:b5:c3:08:27:df:cf:3f:c9:e9:76:95:
44:f9:4e:07:cd:fe:08:72:03:9a:3a:62:62:11:66:
78:b2:61:fb:2d:6b:9d:32:53:9e:92:a1:53:b3:67:
56:29:ba:b3:94:2e:7d:35:e3:0f:7e:ef:5a:bf:1c:
50:d7:97:d0:cc:88:e1:bd:cc:fd:1a:12:ea:6f:7e:
f7:5c:37:27:db:df:2e:78:0f:34:28:ae:8f:7a:4f:
b7:a8:9f:18:4a:36:50:32:b1:53:f8:42:5e:84:57:
50:eb:2b:7a:bc:02:dc:15:ce:02:07:50:7a:a9:50:
86:3b:b8:48:0a:78:02:8d:d6:29:79:94:4d:6c:63:
3f:af:a1:03:e4:db:28:ce:87:f5:a0:c6:ed:4a:2f:
26:64:42:7f:56:5c:77:81:ab:61:91:45:6d:97:1c:
7f:fa:39:52:72:37:4c:ec:01:55:e5:f9:11:89:db:
74:2e:4c:28:b0:3a:0f:a1:1c:ff:b0:31:73:d2:a4:
cc:e6:ae:53
Exponent: 65537 (0x10001)

The public key only contains the modulus N and the exponent e.
N could be factorized in 2 prime numbers p and q, so N = p x q.
Based on those 2 numbers we will be able to generate the private key.

As the modulus above is in a hexadecimal form, we converted it in a decimal form:

python -c "print int('25b18bf5f389097d17237866bb51cff8de922453749ebc403b0995c97c0e386d46c161cadff77c69860dae4791c214cf8487aaaa9f26e920a977834906038aefb5c30827dfcf3fc9e9769544f94e07cdfe0872039a3a6262116678b261fb2d6b9d32539e92a153b3675629bab3942e7d35e30f7eef5abf1c50d797d0cc88e1bdccfd1a12ea6f7ef75c3727dbdf2e780f3428ae8f7a4fb7a89f184a365032b153f8425e845750eb2b7abc02dc15ce0207507aa950863bb8480a78028dd62979944d6c633fafa103e4db28ce87f5a0c6ed4a2f2664427f565c7781ab6191456d971c7ffa395272374cec0155e5f91189db742e4c28b03a0fa11cffb03173d2a4cce6ae53', 16)"

79832181757332818552764610761349592984614744432279135328398999801627880283610900361281249973175805069916210179560506497075132524902086881120372213626641879468491936860976686933630869673826972619938321951599146744807653301076026577949579618331502776303983485566046485431039541708467141408260220098592761245010678592347501894176269580510459729633673468068467144199744563731826362102608811033400887813754780282628099443490170016087838606998017490456601315802448567772411623826281747245660954245413781519794295336197555688543537992197142258053220453757666537840276416475602759374950715283890232230741542737319569819793988431443

We used the website FactorDB to check if 2 primes exists for this number.
This time we had some chance 🙂
Result: 7983218175…43 = 3133337 x 2547832606…39

Using those values and the RSA tool we generated the private key.
The syntax is : ./rsatool.py -p primeP -q primeQ -o outputFile

./rsatool.py -p 3133337 -q 25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939 -o priv.key

Using (p, q) to initialise RSA instance

n =
25b18bf5f389097d17237866bb51cff8de922453749ebc403b0995c97c0e386d46c161cadff77c69
860dae4791c214cf8487aaaa9f26e920a977834906038aefb5c30827dfcf3fc9e9769544f94e07cd
fe0872039a3a6262116678b261fb2d6b9d32539e92a153b3675629bab3942e7d35e30f7eef5abf1c
50d797d0cc88e1bdccfd1a12ea6f7ef75c3727dbdf2e780f3428ae8f7a4fb7a89f184a365032b153
f8425e845750eb2b7abc02dc15ce0207507aa950863bb8480a78028dd62979944d6c633fafa103e4
db28ce87f5a0c6ed4a2f2664427f565c7781ab6191456d971c7ffa395272374cec0155e5f91189db
742e4c28b03a0fa11cffb03173d2a4cce6ae53

e = 65537 (0x10001)

d =
312d72661f0c1b71469ca4c84c48a5b21dc5388f8f63591682b2accf3aee11b1833593ac4b604c27
ad831740c54d78737856d0aab26dc830d3aee4277c7e883a91a78a09bd40f8ee370a068bef8d2f4a
8e9535eadd5eb01d2ca87d5640c41a18165c37fd90a0f749f3c4a6cf2c1fe5ed50e281de10d02278
5db42572167e645b52a8c77f5dec54e22449280db498e8f30086bfc89929749cc28f8addfe22b10c
30d1ef408417f853d26778672bfc27a82c8b01af206de2d86386b7bfc7c0bfd240461f84d92a9e23
37b65b713fdb55bbd29ed7d6f025143c17d1ae6aec5820e08d69a762eef07ac99409e1c087d8e96e
d7f754bf7ae4968c998455de94ec63a6af21

p = 3133337 (0x2fcf99)

q =
c9d3c4a578f6e7bf616941c23100b45fdb49bcb2b03e4475f9140406e52a787fc65fedd5ae864f02
012917bd9f469b60508d7330b35b62448f3fc4ada3c094f5ff09bdd7686d519bb7f93ac6c6868f85
8f0aadb27dc429695f08fdf8a4300292336ee5e6ecf38e6b33f02e2ffb8371c245c6fa04a45cf8ec
c76c019da3f59962006894847ad46bd038b85bfc3d425b759ab55f01699b214173fca6abd286ec6d
ca82bd626a7d3d51f41eb476ce57fd96becb20e23a08a6aecc4e1cce378f443e9dfbc0154a27ebd0
b63fbefce4bce1fe2ec65777cb78ff8b020febb63c2579b007d16e112fc0732fbc447d456d451ed5
935f41ac6a8cda2e5d345d65824f90cb

Saving PEM as priv.key

We checked if the private key was written correctly:

$ cat priv.key

With this private key it will be easy to decode the message ! 😀

We checked the format of the flag.enc file:

$ cat flag.enc

CQGd9sC/h9lnLpua50/071knSsP4N8WdmRsjoNIdfclrBhMjp7NoM5xy2SlNLLC2
yh7wbRw08nwjo6UF4tmGKKfcjPcb4l4bFa5uvyMY1nJBvmqQylDbiCnsODjhpB1B
JfdpU1LUKtwsCxbc7fPL/zzUdWgO+of/R9WmM+QOBPagTANbJo0mpDYxvNKRjvac
9Bw4CQTTh87moqsNRSE/Ik5tV2pkFRZfQxAZWuVePsHp0RXVitHwvKzwmN9vMqGm
57Wb2Sto64db4gLJDh9GROQN+EQh3yLoSS8NNtBrZCDddzfKHa8wv6zN/5znvBst
sDBkGyi88NzQxw9kOGjCWtwpRw==

Base64? Yes, but with some \n (carriage return) inside…so we had to remove those !

You can open the file and put the string on a single manually
OR use this:

cat flag.enc | tr -d '\n'

Which gave us:

CQGd9sC/h9lnLpua50/071knSsP4N8WdmRsjoNIdfclrBhMjp7NoM5xy2SlNLLC2yh7wbRw08nwjo6UF4tmGKKfcjPcb4l4bFa5uvyMY1nJBvmqQylDbiCnsODjhpB1BJfdpU1LUKtwsCxbc7fPL/zzUdWgO+of/R9WmM+QOBPagTANbJo0mpDYxvNKRjvac9Bw4CQTTh87moqsNRSE/Ik5tV2pkFRZfQxAZWuVePsHp0RXVitHwvKzwmN9vMqGm57Wb2Sto64db4gLJDh9GROQN+EQh3yLoSS8NNtBrZCDddzfKHa8wv6zN/5znvBstsDBkGyi88NzQxw9kOGjCWtwpRw==

Finally we used the following python script to decode the flag:

def decrypt_RSA(privkey, message):
    from Crypto.PublicKey import RSA 
    from Crypto.Cipher import PKCS1_OAEP 
    from base64 import b64decode 
    key = open(privkey, "r").read() 
    rsakey = RSA.importKey(key) 
    rsakey = PKCS1_OAEP.new(rsakey) 
    decrypted = rsakey.decrypt(b64decode(message)) 
    return decrypted

flag = "CQGd9sC/h9lnLpua50/071knSsP4N8WdmRsjoNIdfclrBhMjp7NoM5xy2SlNLLC2yh7wbRw08nwjo6UF4tmGKKfcjPcb4l4bFa5uvyMY1nJBvmqQylDbiCnsODjhpB1BJfdpU1LUKtwsCxbc7fPL/zzUdWgO+of/R9WmM+QOBPagTANbJo0mpDYxvNKRjvac9Bw4CQTTh87moqsNRSE/Ik5tV2pkFRZfQxAZWuVePsHp0RXVitHwvKzwmN9vMqGm57Wb2Sto64db4gLJDh9GROQN+EQh3yLoSS8NNtBrZCDddzfKHa8wv6zN/5znvBstsDBkGyi88NzQxw9kOGjCWtwpRw=="
print decrypt_RSA('priv.key', flag)

We executed it:

$ python decryptflag.py

EKO{classic_rsa_challenge_is_boring_but_necessary}

Flag was : EKO{classic_rsa_challenge_is_boring_but_necessary}

0x90r00t

[EKOPARTY PRE-CTF 2015] [Cry100 – RSA 2070] Write Up

Description

Resolution

Leave a Reply Cancel reply

0x90r00t, 0x90r00f