There exists a $RSA$ cryptosystem with $e=2$ , where $e$ is the encryption exponent ?(In general $e>2$)
-
1What is required from an RSA exponent for the decryption to work (for the legitimate reader who knows the private key)? How does that help here? – Jyrki Lahtonen Dec 12 '15 at 08:47
-
The relation gcd(e,phi(n))=1 is useful just for encryption? – ale Dec 12 '15 at 08:55
-
Correct. A good start! What do you know about $\phi(n)$? – Jyrki Lahtonen Dec 12 '15 at 08:56
-
n=pq , p,q primes .So phi(n)=(p-1)(q-1). – ale Dec 12 '15 at 09:01
-
Correct again. What can you say about $p$ and $q$, if $\gcd(2,(p-1)(q-1))=1$? – Jyrki Lahtonen Dec 12 '15 at 09:07
-
Then p=q=2.Actually I have to apply in a numerical problem. – ale Dec 12 '15 at 09:10
2 Answers
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.
- 133,153
-
Why must
emeet this condition? I'm looking for an answer, but I cannot find it anywhere. I would appreciate a hint. Thanks! – Patrick Aug 24 '19 at 14:28 -
@Patrick Otherwise decryption will not be injective. Distinct plaintexts would share the same ciphertext. This is undesirable. – Jyrki Lahtonen Aug 24 '19 at 14:37
-
1Thank you! In the meantime I also found another post titled as Why in RSA, the public exponent must be coprime with () about that. – Patrick Aug 24 '19 at 14:39
-
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.
- 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
-