polyRSA - InCTF Internationals 2020

Crypto
, , ,

TL;DR

  1. Factor the modulus and Find phi.
  2. Find the inverse of e and Decrypt the ciphertext.

Challenge

Polynomial RSA

Challenge Points: 100

Description

All that warmup you need to get started. Challenge files: out.txt.

Challenge Author: pyr0

Attachment

- out.txt

given file

By looking at this, we can say that the challenge is about polynomial RSA, as mentioned in the name PolyRSA.

1
2
3
4
5
6
sage: p
2470567871
sage: n
1932231392*x^255 + 1432733708*x^254 + ... + 1045363399*x + 1809685811
sage: m^65537
1208612545*x^254 + 1003144104*x^253 + ... + 776654074*x + 886398299

We have all the public parameters.

decryption

If we see the n, it is a polynomial, and we have enough algorithms to factorise it, unlike integers.

Here if we notice, the totient function for the polynomials differs from the totient function for the integers.

1
2
3
4
5
6
#finding inverese
facs = n.factor()
p_,q = facs[0][0],facs[1][0]
phi = (p^p_.degree()-1)*(p^q.degree()-1)
d = inverse_mod(e,phi)
m = c^d

Moreover, here m is a polynomial. We can use bytes(m.list()) to change it to bytes.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#given:
load('given.sage')

#initialisation:
P.<x> = PolynomialRing(GF(p))
n = P(n)
R.<x> = P.quotient(n)
c = R(c)
    
#finding inverese
facs = n.factor()
p_,q = facs[0][0],facs[1][0]
phi = (p^p_.degree()-1)*(p^q.degree()-1)
d = inverse_mod(e,phi)

#decryption
m = c^d

flag =  bytes(m.list()[:24])
assert flag == b'inctf{and_i_4m_ir0n_m4n}'

Conclusion

Polynomials are easy to factorise, so we cannot use them for RSA.
I hope you enjoyed the challenge!