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 then invert under , but now it's with complex numbers, so this may not work

We first consider the order of where is a prime. The real and imaginary parts ranges from to , so a valid assumption is that the order is a multiple of since can't be in the group. The order is exactly for since it cannot be expressed as the sum of two squares, but for it is less, and it is a divisor of .

Thus if we want to find given , we simply invert under .

For , the order is a multiple of , then it's trivial

For factoring we simply use yafu