Rating:

# VolgaCTF Quals 2015: Rsa

----------
## Challenge details
| Contest | Challenge | Category | Points |
|:---------------|:--------------|:----------|-------:|
| VolgaCTF Quals 2015 | Rsa | Crypto | 200 |

**Description:**
>*rsa*

>*The oldie but goodie.*

>*[script](challenge/decryptor.py)*

>*[key](challenge/key.public)*

>*[ciphertext](challenge/ciphertext.bin)*

----------
## Write-up
### First look

We start out by looking at the RSA public key provided

>```
>[+]n: [0x323fada9cfa3c3037e0b907d2cea83b9ad3655092cb04aeed95500bca4e366a06cb4d215c65bb3d630b779d27bdc8dcd907d655acbdcef465e411beb1be3dddaaba20fb058e7850aa355ec1b89358602fde7f8be59d4150770cacc1b77b775f7caa358167b3226515f15fca8a4659fea2c4efb0360e31993dde4d1c199832b89L] (1022 bits)
>
>[+]e: [0x1e4805a218009c7f779033e3378b07693f56b266786a295b32d7275ae2e2cd3449dac7468cdae9bb04f547ec759e560739e0d448ebba0ded244095fe1d9b900a885ae931ec760715dbdee4acddb6170b036753c8b572c8af9a02ef370d41a0f2009388bfa042b9f1d0d0847e2fd6fd7ac9e231b17cc95d1dec4540681262c919L] (1021 bits)
>```

As we can see, we are dealing with a very large public exponent. While this isn't necessarily always the case, this can be an indication of a corresponding small RSA private exponent. In a lot of (but [not all](https://www.cryptologie.net/article/265/small-rsa-private-key-problem/)) cases using [Wiener's attack](http://en.wikipedia.org/wiki/Wiener%27s_attack) will suffice to recover the private exponent.

### Attack

Running the [following code](solution/rsa_crack.py):

>```python
>#!/usr/bin/python
>#
># VolgaCTF Quals 2015
># Rsa (Crypto/200)
>#
># @a: Smoke Leet Everyday
># @u: https://github.com/smokeleeteveryday
>#
>
>import math
>from Crypto.PublicKey import RSA
>
>def number_of_bits(n):
> return int(math.log(n, 2)) + 1
>
>def isqrt(n):
> if n < 0:
> raise ValueError('[-]Square root not defined for negative numbers')
> if n == 0:
> return 0
>
> a, b = divmod(number_of_bits(n), 2)
> x = 2**(a+b)
>
> while True:
> y = (x + n//x)//2
> if y >= x:
> return x
> x = y
>
>def perfectSquare(n):
> h = n & 0xF
> if h > 9:
> return -1
>
> if (h != 2 and h != 3 and h != 5 and h != 6 and h != 7 and h != 8):
> t = isqrt(n)
> if (t*t == n):
> return t
> else:
> return -1
> return -1
>
># Fraction p/q as continued fraction
>def contfrac(p, q):
> while q:
> n = p // q
> yield n
> q, p = p - q*n, q
>
># Convergents from continued fraction
>def convergents(cf):
> p, q, r, s = 1, 0, 0, 1
> for c in cf:
> p, q, r, s = c*p+r, c*q+s, p, q
> yield p, q
>
># Wiener's attack ported from https://github.com/pablocelayes/rsa-wiener-attack
>def wienerAttack(n, e):
> cts = convergents(contfrac(e, n))
> for (k, d) in cts:
> # check if d is actually the key
> if ((k != 0) and ((e*d - 1) % k == 0)):
> phi = ((e*d - 1)//k)
> s = n - phi + 1
> # check if the equation x^2 - s*x + n = 0
> # has integer roots
> discr = s*s - 4*n
> if(discr >= 0):
> t = perfectSquare(discr)
> if ((t != -1) and ((s+t) % 2 == 0)):
> return d
> return None
>
>f = open("key.public", 'rb')
>externKey = f.read()
>f.close()
>
>pubkey = RSA.importKey(externKey)
>d = wienerAttack(pubkey.n, pubkey.e)
>if(d):
> print "[+]Recovered d: [%d]!" % d
> privkey = RSA.construct((pubkey.n, pubkey.e, d, ))
> with open('ciphertext.bin', 'rb') as f:
> C = f.read()
> print "[+]Flag: [%s]" % privkey.decrypt(C)
>```

Gives us the following output:

>```bash
>$ ./rsa_crack.py
>[+]Recovered d: [3742521278975183332886178478932181208106789375560965837781]!
>
>[+]Flag: [{shorter_d_is_quicker_but_insecure}]
>```

Original writeup (https://github.com/smokeleeteveryday/CTF_WRITEUPS/tree/master/2015/VOLGACTF/crypto/rsa).