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:
T
Send your input as a pair (a, b):
(2,0)
((a + b √-1) ** e) (mod n) = (123370139733460288741582133541967208151544163810581515437516558669972425636530931666673004837858749022601996874821486288752958977088089060539584311969624273734612352083467285311016219043536527442528687720647804943357024821973693691292035336507137095064124150626846570159166238804148372798356772669L, 0L)
Send your Options:
T
Send your input as a pair (a, b):
(0,1)
((a + b √-1) ** e) (mod n) = (0L, 1L)
Send your Options:
T
Send 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 \(\left(\frac{\mb Z[i]}{p\mb Z[i]}\right)^*\) 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+0i\) can’t be in the group. The order is exactly \(p(p-1)\) for \(p=3\pmod4\) since it cannot be expressed as the sum of two squares, but for \(p=1\pmod4\) it is less, and it is a divisor of \(p(p-1)\).

Thus if we want to find \(g\) given \(g^e\pmod 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_____}