**Tags:** polynomials rsa

Rating: 4.5

## Decent RSA

### Challenge

> RSA can be decent as well!

> **Note** Although this task is very decent and solvable with focusing on the module number, you may use any tools, guessing, or whatever you know to solve it!

### Solution

TD;DR

- See that when written in base 11, the modulus is mainly zeros

- Write the modulus as a polynomial in base 11 and factor the polynomial

- Solve RSA

All we are given is a RSA public key

```

-----BEGIN PUBLIC KEY-----

MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA/Ug8rlEPci1UXMsT+UDo

y8DfxbTHX/3BK2oU+FPWiJf+EiUBM2x4ep04qZ1SO9Pmqj/WH9skMrF1J/LXuY3l

fjvJCh0DXa9VUyX2dAJidja9Ior7GpFwwjYdKh+OETNV+2/CcX4RiPvj+8ApmedW

gn4Fxaeivki+f/UwDa+ws1fTUzmI325v8yvcryHhbgeUWiF85EP6HFAavTsVPlxb

LikVMAB1fuzDbqqJvW2u138w6b2FH3WrezYF6tbAyZej2HX46phwDm9C7MXYJ/sU

oS+E8P7S1jMTCWjfwMCOKU3SFGrkWtXuTaoMZ2nZ+HVfJV8xJOjWez1OxQ5P3F1w

GQIDAQAB

-----END PUBLIC KEY-----

```

and some encrypted data.

From the `.pem` we get

```

Algo RSA

Format X.509

ASN1 Dump

RSA Public Key [21:5d:61:5d:7e:ef:d0:58:12:d0:dc:14:bd:7c:e1:69:eb:77:01:f0]

modulus: fd483cae510f722d545ccb13f940e8cbc0dfc5b4c75ffdc12b6a14f853d68897fe122501336c787a9d38a99d523bd3e6aa3fd61fdb2432b17527f2d7b98de57e3bc90a1d035daf555325f67402627636bd228afb1a9170c2361d2a1f8e113355fb6fc2717e1188fbe3fbc02999e756827e05c5a7a2be48be7ff5300dafb0b357d3533988df6e6ff32bdcaf21e16e07945a217ce443fa1c501abd3b153e5c5b2e29153000757eecc36eaa89bd6daed77f30e9bd851f75ab7b3605ead6c0c997a3d875f8ea98700e6f42ecc5d827fb14a12f84f0fed2d633130968dfc0c08e294dd2146ae45ad5ee4daa0c6769d9f8755f255f3124e8d67b3d4ec50e4fdc5d7019

public exponent: 10001

```

where the modulus is some `2048` bit integer. As we are given a `X.509` key, esrever suggested looking at a database of [predictable RSA keys](https://github.com/g0tmi1k/debian-ssh), which contains 30k public keys which were insecure. We downloaded these and looked for a common factor between our common modulus and one of these known, weak keys. We didnt have any luck though.

Another idea was that maybe this would be solved with Fermat factorisation, with "Decent RSA" being a pun for the infinite decent method. I let the algorithm run for a while but eventually killed it.

The solution came from looking at the modulus in various bases. My initial hope was that the primes might be Mersenne primes, which would be exposed by looking at the modulus in base 2, but it turns our the right base for the solve is base 11.

```py

sage: N.str(base=11)

'10010000000000000000000000000000020000000000010000000000000000000000000000000000000000000002002000002000000000000000020020004000000000002000000000004040000000000020000000002000000000000000000400000000000000000000000004000000000000000000000800000000000000000000000408000000000000000200000004000000600200000000000000000000000000000400000000000200000000000000000000000000000040000000000000080000000040400000000000000800000000000000000000000000000080000000000000000000000040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004000000000000008'

```

We can then write `N` as a polynomial in the following way

```

sage: poly = sum(e * x^i for i,e in enumerate(N.digits(11)))

sage: poly

x^592 + x^589 + 2*x^559 + x^547 + 2*x^501 + 2*x^498 + 2*x^492 + 2*x^475 + 2*x^472 + 4*x^468 + 2*x^456 + 4*x^444 + 4*x^442 + 2*x^430 + 2*x^420 + 4*x^401 + 4*x^375 + 8*x^353 + 4*x^329 + 8*x^327 + 2*x^311 + 4*x^303 + 6*x^296 + 2*x^293 + 4*x^263 + 2*x^251 + 4*x^220 + 8*x^205 + 4*x^196 + 4*x^194 + 8*x^179 + 8*x^148 + 4*x^124 + 4*x^15 + 8

```

Which sage very quickly can factor

```

sage: poly.factor()

(x^296 + x^293 + 2*x^263 + x^251 + 2*x^196 + 4*x^148 + 2*x^124 + 2*x^15 + 4)*(x^296 + 2*x^205 + 2*x^179 + 2)

```

Setting `x = 11` will return the primes `p*q = N`, solving the challenge.

### Implementation

```py

from Crypto.PublicKey import RSA

from Crypto.Util.number import long_to_bytes, bytes_to_long

flag = bytes_to_long(open("flag.enc","rb").read())

key = RSA.import_key(open("mykey.pem").read())

n = Integer(key.n)

poly = sum(e * x^i for i,e in enumerate(Integer(key.n).digits(11)))

(p, _), (q, _) = poly.factor_list()

p, q = p(x=11), q(x=11)

assert p*q == n

d = inverse_mod(key.e, (p-1)*(q-1))

print(long_to_bytes(pow(flag, d, n)))

```

### Flag

`CCTF{___RSA___1n_D3cEn7_W0rLd_cRyPtO5!!!}`

Original writeup (https://blog.cryptohack.org/cryptoctf2020#decent-rsa).