0

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

ale
  • 1,744

2 Answers2

3

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.

Jyrki Lahtonen
  • 133,153
2

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.

Henno Brandsma
  • 242,131
  • Actually my problem is:Alice wants to send the message $m$-a natural number , $m<8$ to Bob.She encrypts the message $9*m$ using a "version" of the $RSA$ cryptosystem with the exponent of encryption $e=2$.We suppose that Bob has the private key $p=7$ , $q=11$.How can decrypt Bob the message $c=23$ received from Alice? – ale Dec 12 '15 at 10:04
  • 2
    @matt You should have asked that instead.... Compute the square roots of $23$ modulo 77 (using the link I gave you), you get 10, 32, 45, 67 (check!). Multiply these with the inverse of 9 modulo 77 (which is 60, check!) to get possible $m$ values, only one of them is $< 8$. – Henno Brandsma Dec 12 '15 at 10:14
  • Why you compute the inverse of 9 modulo 77?Why not the inverse of 81 modulo 77? – ale Dec 12 '15 at 10:28
  • 1
    @matt After the square root we have $9m$. – Henno Brandsma Dec 12 '15 at 10:30
  • Thank you!I am sorry but I am begginer.. – ale Dec 12 '15 at 10:31