$RSA$ cryptosystem with $e=2$

2.5k Views Asked by At

There exists a $RSA$ cryptosystem with $e=2$ , where $e$ is the encryption exponent ?(In general $e>2$)

2

There are 2 best solutions below

4
On BEST ANSWER

The encryption exponent $e$ should meet the condition $$ 1=\gcd(e,\phi(n))=\gcd(e,(p-1)(q-1)). $$ In RSA the primes $p,q$ are distinct, so at least one of them is odd (in all useful cases both are). Therefore the encryption exponent $e$ can never be an even integer.

5
On

The basic system where $n=pq$,$p,q$ distinct primes, $1 < x < n$ is some message, and $x^2 (n)$ is used as the ciphertext, is called the Rabin cryptosystem. This is not RSA, because in RSA the secret key is the exponent $d$, but for $e=2$ no valid $d$ can be found (see Jyrki's answer). For Rabin we need to know $p$ and $q$ to perform a square root on the ciphertext, but then we get (almost always) $4$ possible messages $x$, so decryption is ambiguous.

Of course, in practice we use padding on $x$ to ensure only one of the 4 candidates obeys the padding rules (and encryption is randomised, and always "big" w.r.t. $n$, just like we do in RSA in practice). See the linked page for details on decryption (i.e. to find the 4 candidates). AFAIK no standard system has been agreed upon, the system never became even remotely as popular as RSA.

It's mostly of theoretical interest: getting the message $x$ from the ciphertext $x^2 (n)$ is provably as hard as factoring $n$, and this has not been proved for RSA.