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 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_____}

Original writeup (https://github.com/Ariana1729/CTF-Writeups/blob/master/2019/CryptoCTF/Complex%20RSA/README.md).