Write-Ups

EasyCTF IV – RSA V

Description

Bob is extremely paranoid, so he decided that just one RSA encryption is not enough. Before sending his message to Alice, he forced her to create 5 public keys so he could encrypt his message 5 times! Show him that he still is not secure…

Here are the 5 public keys that Bob used, each in the format of (N, e):
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 11)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 41)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 67623079903)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 5161910578063)
(9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469, 175238643578591220695210061216092361657427152135258210375005373467710731238260448371371798471959129039441888531548193154205671)

Here is his encrypted message:
7117565509436551004326380884878672285722722211683863300406979545670706419248965442464045826652880670654603049188012705474321735863639519103720255725251120

Resolution

First thing I tried is to see if n have known factors.
It doesn’t… would have been too easy 🙂

When encrypting a message using textbook RSA, we compute :

    \[c = m^e [n]\]

Where c is the ciphertext, m the plaintext converted to a number, e the public exponent and n the modulus.

Bob encrypted his message five times, so the equation is the following :

    \[c = m^{e_1^{e_2^{e_3^{e_4^{e_5}}}}} = m^{e_1*e_2*e_3*e_4*e_5} = m^E\]

To recover the plaintext we don’t need to find d_1 to d_5 but only D as the decryption process is :

    \[m = c^{d_1^{d_2^{d_3^{d_4^{d_5}}}}} = c^{d_1*d_2*d_3*d_4*d_5} = c^D\]

To recover D, we must think of an appropriate approach.  First I computed E :

>>> 11*41*67623079903*5161910578063*175238643578591220695210061216092361657427152135258210375005373467710731238260448371371798471959129039441888531548193154205671
27587468384672288862881213094354358587433516035212531881921186101712498639965289973292625430363076074737388345935775494312333025500409503290686394032069L

Seeing that E is quite close to n, I decided to run a Wiener attack because the private exponent D would be relatively small compared to n. I used attackrsa for this.

$ attackrsa -t wiener -n 9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469 -e 27587468384672288862881213094354358587433516035212531881921186101712498639965289973292625430363076074737388345935775494312333025500409503290686394032069
====== Cracked! =======
d is 0x80e51c075ffcbe945903af2e1075fb6dL
p is 0xebdd1fcde3674f5d74156a27138756718f8d51c9eae9911a3a3ac50f18019485
q is 0xbfa44dca18f4843dffeb3969cdb4e20cc0369ed1d3c2016cc12e0b3e347386d9

Bingo ! Now I got everything needed to decrypt the flag.

>>> d = 0x80e51c075ffcbe945903af2e1075fb6d
>>> c = 7117565509436551004326380884878672285722722211683863300406979545670706419248965442464045826652880670654603049188012705474321735863639519103720255725251120
>>> n = 9247606623523847772698953161616455664821867183571218056970099751301682205123115716089486799837447397925308887976775994817175994945760278197527909621793469
>>> t = pow(c,d,n)
>>> hex(t)
'0x656173796374667b6b65626c667466747a696261746473716d716f74656d6d74797dL'
>>> "656173796374667b6b65626c667466747a696261746473716d716f74656d6d74797d".decode('hex')
'easyctf{keblftftzibatdsqmqotemmty}'

The flag was easyctf{keblftftzibatdsqmqotemmty} 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *