Cryptography Reference
In-Depth Information
Returning to our numerical example, if the plaintext is
P
=
31 then encrypting
using public key (2773
,
17) results in:
31
17
C
=
=
587mod 2773
.
Recall from Table 3.3 that exponentiation (raising a number to a power) has
polynomial complexity, which means that it is efficient to compute. Note also,
however, that Table 3.3 illustrates that exponentiation is not
as efficient
as
processes such as addition and multiplication. This means that encryption is fast,
but not as fast as simpler operations, such as those that form the basis for most
symmetric encryption algorithms. This observation has important implications,
which we return to in Section 5.5.
RSA DECRYPTION
The decryption process for RSA is just as straightforward. Suppose that the holder
of public-key pair (
n
e
) has just received a ciphertext
C
. All the receiver does is
to raise
C
to the power of their private key
d
. The result will be the plaintext
P
.In
other words:
,
C
d
mod
n
P
=
.
Returning again to our numerical example, the ciphertext
C
=
587 can be
decrypted using private key 157 to obtain:
587
157
P
=
=
31mod 2773
.
The million dollar question is, of course,
why does this work
? We suggest that you
either choose just to accept that it works, or alternatively read the Mathematics
Appendix for an explanation.
5.2.3
Security of RSA
There are two obvious ways of trying to break RSA. Indeed, these apply to any
public-key cryptosystem. An attacker can either attempt to:
1. decrypt a ciphertext without knowledge of the private key;
2. determine the private key directly from the public key.
Clearly the second attack is more powerful than the first, since an attacker who
can perform the second attack can then decrypt subsequent ciphertexts. We now
consider these two attack strategies.
DECRYPTING A CIPHERTEXT WITHOUT KNOWLEDGE
OF THE PRIVATE KEY
Consider trying to decrypt an RSA ciphertext without the private key. Recall that
we specified in Section 5.1.4 that a public-key encryption function should be a
trapdoor one-way function. By assuming that we do not know the private key, we
