staring into /dev/null

barrebas

Ekoparty - Cry100

We’re given a public key and a encrypted flag, with the task to get the private key. I’m not very good at crypto challenges so I wanted to see if I could break this one and learn something in the process.

The public key is an RSA key:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

$ openssl rsa -inform PEM -pubin -in public.key -text -noout
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)

It has a rather weird number of bits, not a multiple of 256. The modulus is converted to hex using python and yields:

1

n = 79832181757332818552764610761349592984614744432279135328398999801627880283610900361281249973175805069916210179560506497075132524902086881120372213626641879468491936860976686933630869673826972619938321951599146744807653301076026577949579618331502776303983485566046485431039541708467141408260220098592761245010678592347501894176269580510459729633673468068467144199744563731826362102608811033400887813754780282628099443490170016087838606998017490456601315802448567772411623826281747245660954245413781519794295336197555688543537992197142258053220453757666537840276416475602759374950715283890232230741542737319569819793988431443

Hmm. Since the modulus n is made from the product of two primes, we’d better find those primes. Luckily, I found another writeup and a website called factordb.com. Factordb does exactly what it says on the box and yields two factors, 3133337 and another large number. The first number made me think I was on the right way!

Now, we need to reconstruct the key. We have n, p and q which is all we need. I couldn’t decrypt the message in Python, as Python’s cryptolib requires the modulus to be a multiple of 256 bits. So I resorted to the voodoo magic that is openssl. I found this nice post on stackoverflow about creating specific rsa keys.

I followed that post, computing:

1
2
3

d mod(p-1) = e1
d mod(q-1) = e2
q^-1 mod p = coeff

for which I needed

1
2
3
4
5
6
7
8
9
10
11
12
13

def egcd(a, b):
  if a == 0:
      return (b, 0, 1)
  else:
      g, y, x = egcd(b % a, a)
      return (g, x - (b // a) * y, y)

def modinv(a, m):
  g, x, y = egcd(a, m)
  if g != 1:
      raise Exception('modular inverse does not exist')
  else:
      return x % m

Then I put everything in a file called newkey.der:

1
2
3
4
5
6
7
8
9
10
11
12

asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:0
modulus=INTEGER:79832181757332818552764610761349592984614744432279135328398999801627880283610900361281249973175805069916210179560506497075132524902086881120372213626641879468491936860976686933630869673826972619938321951599146744807653301076026577949579618331502776303983485566046485431039541708467141408260220098592761245010678592347501894176269580510459729633673468068467144199744563731826362102608811033400887813754780282628099443490170016087838606998017490456601315802448567772411623826281747245660954245413781519794295336197555688543537992197142258053220453757666537840276416475602759374950715283890232230741542737319569819793988431443
pubExp=INTEGER:65537  
privExp=INTEGER:406853230956379689450620815713768871010712825839536410687962650677800895818003893712259622281477453292088146173840036827322518131453630576229976208523593618949818777897059256426591560532784635697190752924923710375949616954069804342573867253630978123632384795587951365482103468722384133084798614863870775897915929475258974188300927376911833763105616386167881813301748585233563049693794370642976326692672223638908164822104832415788577945314264232531947860576966629150456995512932232264881080618006698700677529111454508900582785420549466798020451488168615035256292977390692401388790460066327347700109341639992159475755036449
p=INTEGER:25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939
q=INTEGER:3133337
e1=INTEGER:15320351458978192768467039741691432413958180349660930794740289485182452764579534136107456333762920952821710744567765011085892394594373698903583015958298729593743757394184665648601970820474550408544396720336394444082148339685815042712020243239641617201526913490150693257135882730015443734409342942381805505660243891614007699009146733904940642377373537806159587666380328759209553248526202577679304907571591265191240376778645354498599063176881375334380848007142765855272411310242667619720799140338871500103278100940728801960485534826631133256077779493381175185896255651752489800973249824932460228998596930117032675866465
e2=INTEGER:817841
coeff=INTEGER:0

The privExp was calculated like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import gmpy

def egcd(a, b):
  if a == 0:
      return (b, 0, 1)
  else:
      g, y, x = egcd(b % a, a)
      return (g, x - (b // a) * y, y)

def modinv(a, m):
  g, x, y = egcd(a, m)
  if g != 1:
      raise Exception('modular inverse does not exist')
  else:
      return x % m
      
p = 25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939
q = 3133337
totien = (p-1) * (q-1)
e = 65537
d = modinv(e,totien)
print d

I then ran $ openssl asn1parse -genconf newkey.der -out key.der. After mucking around with the flag, I verified I had the right private key by encrypting a test message with the public key. I noticed that the flag was base64 encoded whereas my encrypted message wasn’t…

1
2
3

$ cat flag.enc |base64 -d > test.enc
$ openssl rsautl -in test.enc -out /dev/tty -inkey private.key -decrypt -oaep
EKO{classic_rsa_challenge_is_boring_but_necessary}

That last openssl command was just tested with -raw and -oaep (options for padding). -oaep worked!

Flag was EKO{classic_rsa_challenge_is_boring_but_necessary}. I learned something \o/

Comments