Tags: rsa openssl asymmetric

Rating:

First let's get the Modulus N.

console
$openssl rsa -in public.pem -text -inform PEM -pubin -text Public-Key: (256 bit) Modulus: 00:be:5f:67:0c:7c:df:cc:0b:d3:41:12:d3:bd:71: 22:9f:d3:e4:46:e5:31:bf:35:16:03:6c:12:58:33: 6f:6c:51 Exponent: 65537 (0x10001) writing RSA key -----BEGIN PUBLIC KEY----- MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAL5fZwx838wL00ES071xIp/T5EblMb81 FgNsElgzb2xRAgMBAAE= -----END PUBLIC KEY-----  Now convert that into integer. console$ python3 -c "print(int(('00:be:5f:67:0c:7c:df:cc:0b:d3:41:12:d3:bd:71:22:9f:d3:e4:46:e5:31:bf:35:16:03:6c:12:58:33:6f:6c:51'.replace(':', '')), 16))"

86108002918518428671680621078381724386896258624262971787023054651438740237393


Since N is small, so it can be factorised easily. By using [FactorDB](http://factordb.com) we can get p and q.

p = 286748798713412687878508722355577911069
q = 300290718931931563784555212798489747397

Now we have N, p, q and e we can calculate the private exponent d easily.

d = (e**-1) mod (p-1)*(q-1)

python
e = 65537
p = 286748798713412687878508722355577911069
q = 300290718931931563784555212798489747397
d = pow(e, -1, (p-1)*(q-1))
print(d)


which outputs

 52563235496868154743721179285926106867856121268586368115409795819089744895137.

Now we have to make a PEM file out of this. After searching for a long time I can't get a way through it (I tried RSA.construct() method several times but it gave me an error). So I decided to make this into a DER file and then convert it to a PEM and then decrypt the flag.

One way to do this is to generate a DER encoded key using OpenSSL's asn1parse command's -genconf option. But first we need to make an input file and calculate some more values, specifically, d mod (p-1) called e1, d mod (q-1) know as e2 and (q**-1) mod p called as coeff (short for coefficient).

python
e = 65537
p = 286748798713412687878508722355577911069
q = 300290718931931563784555212798489747397
d = pow(e, -1, (p-1)*(q-1))

print('e1 =', d % (p-1))
print('e2 =', d % (q-1))
print('coeff =', pow(q, -1, p))



e1 = 158375364557874163650127107177698912781
e2 = 13741426462561038188960145920360571165
coeff = 43340310015875206124799642386915239847


Now the input file will be :

console
asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:0
modulus=INTEGER:86108002918518428671680621078381724386896258624262971787023054651438740237393
pubExp=INTEGER:65537
privExp=INTEGER:52563235496868154743721179285926106867856121268586368115409795819089744895137
p=INTEGER:286748798713412687878508722355577911069
q=INTEGER:300290718931931563784555212798489747397
e1=INTEGER:158375364557874163650127107177698912781
e2=INTEGER:13741426462561038188960145920360571165
coeff=INTEGER:43340310015875206124799642386915239847


I named it as derfile.txt. Now to make a DER file, run :

console
$openssl asn1parse -genconf derfile.txt -out private.der  Let's convert DER to PEM : console$ openssl rsa -inform DER -outform PEM -in private.der -out private.pem

writing RSA key


Now finally decrypt the flag :

console
\$ openssl rsautl -decrypt -inkey private.pem -in encrypted.txt

AFFCTF{PermRecord}

Voila ! We get the flag !

Flag : AFFCTF{PermRecord}

Original writeup (https://medium.com/@originalyankeedoodle/affinity-ctf-2020-breakme-writeup-4928b31d0d87).