# PolyRSA
We're given a file [`out.txt`](out.txt) where we're given `p` a prime number. `n` a polynome, and m^65537, a polynome (the ciphertext).
Anyway, after searching we can find this paper that talks about the specifications of polynomial RSA.
https://laur.lau.edu.lb:8443/xmlui/bitstream/handle/10725/5497/Modified.pdf
We can see the algorithm for key generation in the paper:```Algorithm 4: (RSA polynomials key generation).1. Generate a random odd prime integer p.2. Generate two irreducible polynomial h(x) and g(x)in Zp[x].3.Reduce the polynomial f(x) = h(x)g(x) in Zp[x].4.Compute φ(f(x)) = (p^s− 1)(p^r− 1) the order of U(Zp[x]/<f(x)>).5. Select an integer e in the interval [2, φ(f(x))−1]such that (e, φ(f(x))) = 1.6. Use the extended Euclidean algorithm to determineits inverse d modulo φ(f(x)).7.A's public-key is (p, f(x), e), A's private-key is(p, d, g(x), h(x)). ```
We already have the prime integer `p`. Our `n` is the polynome, we need to factorize it to get 2 irreducible polynomes `h(x)` and `g(x)`.
Using Sage:```Sagesage: p=2470567871sage: R.<x> = PolynomialRing(Zp(p,1))sage: n = #too long, retrieve it from the file out.txtsage: n.factor()```
We find 2 irreducible polynomes, with degree 127 and the other with degree 128.
Going on with the next step, we can calculate phi(n) which is (p^r -1)(p^s-1), `s` and `r` are the degree of the 2 irreducible polynome respectively.
In our case `s=127` and `r=128`, after calculating phi, we can compute the inverse of `e` (which is 65537) modulo phi.
```Pythonfrom Crypto.Util.number import inversephi = (p**r - 1) * (p**s - 1)d = inverse(e,phi)```
Now that we have the private exponent `d`, we can decrypt the cipher. (let's consider c =  m^65537)
We can recover the plaintext (or more like, the plaintext-polynome ?) by computing `c^d mod n`
With Sage, we can recover the polynome. (It takes a lot of time to compute)```Sagesage: p=2470567871sage: R.<x> = PolynomialRing(Zp(p,1))sage: RES = pow(c, d, n)```
We find the original polynome, and we can notice that the coefficients are < 255, so each coefficient is a character of the flag.
```Sagesage: RES.coefficients()[105, 110, 99, 116, 102, 123, 97, 110, 100, 95, 105, 95, 52, 109, 95, 105, 114, 48, 110, 95, 109, 52, 110,125]```
We can then get the flag```Pyprint(''.join(chr(c) for c in coefficients))```
### flag`inctf{and_i_4m_ir0n_m4n}`
