# Complex RSA
> Things in this world sometimes are different than they appear!
> nc 167.71.62.250 14559
## Challenge
```Challenge loading... be patinet :)|-------------------------------------|| Options: 	  	              ||	[E]ncrypted message           ||	[K]ey generation function     ||	[S]end the decrypted message  ||	[T]ry encryption              ||	[Q]uit                        ||-------------------------------------|```
The key gen function:
```def gen_key(e, nbit):	p = getPrime(nbit << 2)	q = getPrime(nbit >> 2)	print 'p =', p	print 'q =', q	n = p * q	return (e, n)```
Here one prime would be small, so factorization should be quite easy
```Send your Options:TSend your input as a pair (a, b):(2,0)((a + b √-1) ** e) (mod n) = (123370139733460288741582133541967208151544163810581515437516558669972425636530931666673004837858749022601996874821486288752958977088089060539584311969624273734612352083467285311016219043536527442528687720647804943357024821973693691292035336507137095064124150626846570159166238804148372798356772669L, 0L)Send your Options:TSend your input as a pair (a, b):(0,1)((a + b √-1) ** e) (mod n) = (0L, 1L)Send your Options:TSend your input as a pair (a, b):(-1,0)((a + b √-1) ** e) (mod n) = (337390295386784062735892530953812027731217626577827868683652203476748859812364337575664693191200613632654265062075499825596838397609731917692839810645496096834742890659029158682118916487432458937074956757871632389547383580967613523944154703997016734902928913508657661928209328770940675037982298198L, 0L)```
Trying some inputs, we see that this basically extends RSA into the gaussian integers, and negative numbers works too.
Since negative numbers works, finding `n` is trivial `n = (n-1)+1`
Assuming `e` is small, finding `e` is simple by discrete log
Now we need a way to do complex modular arithmetic
## Complex modular arithmetic
Adding amd multiplying is trivial, exponentiation is done by square and multiply:
```def cadd(a,b,n):    return (a[0]+b[0]%n,a[1]+b[1]%n)
def cmul(a,b,n):    return ((a[0]*b[0]-a[1]*b[1])%n,(a[0]*b[1]+a[1]*b[0])%n)
def cpow(a,k,n):    if(k==0):        return (1,0)    if(k==1):        return a    if(k%2==0):        a=cmul(a,a,n)        return cpow(a,k/2,n)    else:        return cmul(a,cpow(cmul(a,a,n),(k-1)/2,n),n)```
## Order of multiplicative group
Usually in RSA, we simply compute `phi(n)` then invert `e` under `phi(n)`, but now it's with complex numbers, so this may not work
We first consider the order of `C/pC*` where `p` is a prime. The real and imaginary parts ranges from `0` to `p-1`, so a valid assumption is that the order is a multiple of `p*p-1`(since `0,0` can't be in the group). The order is exactly `p*p-1` for `p=3 mod 4` since it cannot be expressed as the sum of `2` squares, but for `p=1 mod 4` it is less, and it is a multiple of `p*p-1`.
Thus if we want to find `g` given `g^e=a mod p`, we simply invert `e` under `p*p-1`.
For `n=pq`, the order is a multiple of `lcm(p*p-1,q*q-1)`, then it's trivial
For factoring `n` we simply use yafu
> Flag : `CCTF{_____e^(i*PI)=-1_____}`