Is it possible to apply RSA on complex numbers?

RSA is a popular public-key cryptography algorithm. It has some mathematical assumptions. I mean, one cannot apply RSA on elements of any algebraic structure. Elements from certain algebraic structures are only eligible for utilization in RSA.

I want to know whether complex numbers fall into those particular algebraic structures or not. If no, due to the lack of which property complex numbers became ineligible at least theoretically?

The set of complexes $\mathbb C$ is unsuitable for RSA. That's because RSA (as all cryptography) maps plaintext and ciphertext to finite sets (e.g. $\mathbb Z_n$ or it's subset $\mathbb Z_n^*$), and $\mathbb C$ is infinite.

Any effort to exhibit a finite subset of $\mathbb C$ suitable for RSA and using the native multiplication fails. Within the detail of including $0$ or not, the necessity for this set to be closed under multiplication leaves us with the set $\{e^{2i\pi/n}\text{ for }i\in\mathbb N\text{ with }i<n\}$ as the only possibility. This set is trivially isomorphic to the group $(\mathbb Z_n,+)$, and thus does not lead to a secure cryptosystem.

^{On the other hand, we can make an equivalence relation $\sim$, compatible with multiplication in (a subset of) $\mathbb C$ [that is: for any $a$, $a'$, $b$, $b'$ in $\mathbb C$ (or said subset), $a\sim a'$ and $b\sim b'$ implies $a\,b\sim a'\,b'$ ], such that the set of equivalence classes is finite, and the resulting multiplication is internal on the quotient group. A trivial example considers $\mathbb Z_n\subset\mathbb R\subset\mathbb C$, and $\sim$ defined as equivalence modulo $n$ for that subset of $\mathbb C$. This answer gives a more interesting example. There are even more possibilities if we further redefine multiplication, including an Elliptic Curve analog of RSA, which can easily be remapped to $\mathbb C$. I don't see these match the original question, since we change both the set (by restriction) and the operation (to keep it internal).}

Given $p,q$ of the form $4k+3$, we can define complex numbers mod $p$ or mod $q$. The form guarantees that $-1$ has no square root there, so we are working with a quadratic extension of $GF(p)$ and $GF(q)$, i.e. $$GF(p^2) \simeq GF(p)[i]/(i^2+1)$$ and $$GF(q^2) \simeq GF(q)[i]/(i^2+1).$$

Combining them, we can define RSA over $(\mathbb{Z}/n\mathbb{Z})[i]/(i^2+1)$, $n=pq$, i.e. complex numbers where real and imaginary parts are defined mod $n$. The arithmetic (multiplication, addition, etc.) is done similarly to complex numbers. E.g. $$(a+bi)(c+di)\equiv (ac-bd) + (ad+bc)i \pmod{n}$$ (values stored as pairs $(a,b)$ and $(c,d)$).

The order of the multiplicative group is $\mathrm{lcm}(p^2-1, q^2-1)$, so we need $$e\cdot d \equiv 1 \pmod{\mathrm{lcm}(p^2-1, q^2-1)}.$$

Of course, factoring $n$ breaks the scheme, so there's no increase in security.

Another possible issue is that complex numbers have the (squared) norm, which is multiplicative and easy to compute without knowing $p$ and $q$: $$N(a+bi) \equiv a^2+b^2 \pmod{n},$$ $$N(c) \equiv N(m^e) \equiv N(m)^e \pmod{n}.$$ Since the norm lives in $GF(p)\times GF(q)$, we reduce to basic RSA mod $n$. If an attacker can somehow break RSA mod $n$, the attacker recovers then the norm of the message.

Summary:

It is possible to define RSA over complex numbers modulo primes, however the advantages of doing this are not clear, as the security does not increase compared to basic RSA, and efficiency drops a bit.

I don't see any other significant attacks on this scheme, I would be glad to know if there are any.

Upd: Instead of $\sqrt{-1}$ we can use any other $\sqrt{d}$ that does not lie in the base field, i.e. work with $\mathbb{Z}[\sqrt{d}]/n\mathbb{Z}$. This was done in a variant of OSS signatures. (OSS was broken but only because it's weak itself, RSA defined over quadratic integers should be ok.)

Elements from certain algebraic structures are only eligible for utilization in RSA.

I'm not exactly certain what you mean by that. RSA encryption can be (and usually is) viewed as:

• Take a plaintext bitstring (up to some maximum length somewhat smaller than the modulus size)

• Run it through a padding function to convert it (plus some randomness) into a number between 0 and N-1

• Run the underlying RSA public operation to convert it into another number between 0 and N-1

• Convert that number into the ciphertext bitstring.

(and the decryption and signature operations are similar).

As such, any values that can be represented by the (bounded size) bitstring can be handled by RSA.

Now, this does break up the homomorphic properties of RSA (not an accident; those are rarely useful to the user and may be useful for an attacker, so we want them broken up); on the other hand, it's not clear how useful they'd be to complex numbers anyways.

Of course RSA encryption can be applied to complex numbers since complex numbers are mapped to arbitrary data, represented as two real numbers (either magnitude and phase or real and imaginary). If RSA can be applied to real numbers then it is readily extended to complex numbers. In the end both are represented as data that can be encrypted.