How to solve “Introduction to Cryptography 1”

Whoever thought of Caeser-Encryption, ROT13 or Vigenere after seeing a crypto-challenge is stuck in the wrong Millennium -
modern cryptography mainly uses algebraic methods.
One of the most popular cryptosystems is for sure RSA. It is an asymmetric cipher: A person owns a public key and a private key. The public key can be given away to everybody and allows for the encryption of arbitrary messages.
However, only the private key enables a person to decrypt messages encrypted with the public key.

Usually, it is impossible to decrypt messages or computing the private key with only knowledge of the public key. However, this is exactly what this challenge asks us to do!

The challenge

We are given a public key (pubkey.pem) and a message (intercepted-message.txt) that was encrypted with this key. Our goal is to decrypt the intercepted message. While this is usually impossible, we will see some conditions where the goal can be achieved.

The RSA cryptosystem

The RSA cryptosystem is based on number theory. A detailed explanation of all mathematics behind RSA can be found for example on Wikipedia.

However, if we have a look at our given public key pubkey.pem, no numbers are visible. We can use OpenSSL to extract the numbers for us.

$ openssl rsa -pubin -in pubkey.pem -text -noout
RSA Public-Key: (2047 bit)
Modulus:
    51:cf:f4:6d:9e:e3:20:96:d6:c8:06:cb:c7:df:2d:
    1d:3b:ea:7e:7b:2f:c4:e8:26:d9:fc:5e:18:79:99:
    12:dc:a1:50:b2:9c:65:c0:f9:e6:64:53:39:6c:e7:
    de:63:1a:0f:9a:67:45:13:8b:61:25:bb:cd:18:5a:
    a1:2e:b0:9a:4a:1b:d8:06:11:8c:97:a8:de:05:ed:
    0b:e6:b4:5f:c1:c9:e9:93:71:92:f5:8b:c4:a5:cc:
    27:67:80:3c:0b:21:34:2a:f5:cb:8f:34:af:fb:1a:
    6e:c2:52:0c:76:5d:87:52:1c:68:48:db:d8:31:81:
    2e:cc:6d:8b:b3:d6:17:33:b0:eb:c3:52:cf:64:d4:
    44:5c:99:55:72:92:2f:49:3d:71:89:95:9d:b2:32:
    1e:1b:ac:59:25:fa:56:dc:69:f6:85:8e:fe:eb:a0:
    a5:a9:d7:6b:a1:98:18:71:53:92:74:24:e5:f7:b6:
    80:98:ab:8c:10:44:2b:73:d1:49:02:7c:fc:37:d0:
    30:05:63:37:c3:e0:f4:21:6c:f4:32:23:96:74:41:
    b6:08:ee:c2:a6:48:e8:ce:85:78:94:c6:65:03:0c:
    01:24:56:29:27:9b:38:7f:cd:bd:c3:5b:61:67:71:
    5b:54:bd:55:56:18:0d:9a:f2:50:4b:52:7a:90:fa:
    e7
Exponent: 65537 (0x10001)

This gives us the numbers we need to work with.

The attack

For now, we have extracted the parameters of the public key. Now, there are several attacks possible. To find out which attack is successful against this key, we have to run it.
Many attacks against RSA cryptosystems are listed in this whitepaper.

However, most of the times the attack that has to be used is hinted. In our case, we know that the prime generation may be flawed. Therefore, we can try factoring the public key:

We first have to convert the modulus N of our public key to decimal, which results in
10327849034940138613515485956077213322791085874638285662823764630659653931824178919168344401508423966366637831067655701114352106747323628144645384205073278784870804834942988268503504130770762781798270763453272421050209487483563600870343875197428105079394315585993355808937811229959083289653056248770988647762812998870912510238393368777882358059256678052653963583286245796285737035786447522814310717433588049686223718247661713594680120785280795132759253149754143640871380226770164628599577669124463514838464342769690232097283333816896581904763736283142031118073027496197756777460403007359764250621763279762041468943079

Now, we can try factoring this integer. There are many methods for factoring available, but we may just use trial division for the beginning

The following python script implements trial division and outputs a factor.

N = 10327849034940138613515485956077213322791085874638285662823764630659653931824178919168344401508423966366637831067655701114352106747323628144645384205073278784870804834942988268503504130770762781798270763453272421050209487483563600870343875197428105079394315585993355808937811229959083289653056248770988647762812998870912510238393368777882358059256678052653963583286245796285737035786447522814310717433588049686223718247661713594680120785280795132759253149754143640871380226770164628599577669124463514838464342769690232097283333816896581904763736283142031118073027496197756777460403007359764250621763279762041468943079

for i in range(2, 1000000):
    if N % i == 0:
        print("Factor found: " + str(i))
        break

Now, knowing a factor p it is easy to compute the other factor q. From p and q on it should be easy to compute the RSA private key - but this is now left as an exercise to the reader.

After we have computed the RSA decryption exponent d, we can now proceed with decrypting our intercepted message.

d = 7312XXXXXXX
m = 4522827319495133992180681297469132393090864882907734433792485591515487678316653190385712678072377419115291918844825910187405830252000250630794128768175509500175722681252259065645121664124102118609133000959307902964132117526575091336372330412274759536808500083138400040526445476933659309071594237016007983559466411644234655789758508607982884717875864305554594254277210539612940978371460389860098821834289907662354612012313188685915852705277220725621370680631005616548237038578956187747135229995137050892471079696577563496115023198511735672164367020373784482829942657366126399823845155446354953052034645278225359074399

decrypted = pow(m, d, N)
print(decrypted)

However, we can clearly see that our result is just another number. To convert this number to ASCII, we can use the long_to_bytes function from the pycryptodome package.

from Crypto.Util.number import long_to_bytes
print(long_to_bytes(decrypted))

This code should print our flag!

Some useful tips