# Really Secure Algorithm

## Description

I heard about RSA, so I took a go at implementing it.

[Secure.txt](Secure.txt)

## Solution

The n is actually a sqaure number.

```
***factors found***

P386 = 16225510719965861964299051658340559066224635411075742500953901749924501886090804067406052688894869028683583501052917637552385089084807531319036985272636554557876754514524927502408114799014949174520357440885167280739363628642463479075654764698947461583766215118582826142179234382923872619079721726020446020581078274482268162477580369246821166693123724514271177264591824616458410293414647
P386 = 16225510719965861964299051658340559066224635411075742500953901749924501886090804067406052688894869028683583501052917637552385089084807531319036985272636554557876754514524927502408114799014949174520357440885167280739363628642463479075654764698947461583766215118582826142179234382923872619079721726020446020581078274482268162477580369246821166693123724514271177264591824616458410293414647
```

If n = p * p, phi(n) = p * (p-1)

Perform mod inverse on e and decrypt the message.

```
d=modinv(e,(p-1)*p)
import codecs
print(codecs.decode(hex(pow(c,d,n))[2:],'hex'))
```

The flag is

```
hsctf{square_number_time}
```

Original writeup (https://github.com/kuruwa2/ctf-writeups/tree/master/HSCTF%206/Really%20Secure%20Algorithm).