In RSA cipher, does Alice need Bob’s public key to encrypt a message to Bob?

by Emmanuel Udofia / Saturday, 10 August 2024 / Published in Cybersecurity, EITC/IS/CCF Classical Cryptography Fundamentals, Introduction to public-key cryptography, The RSA cryptosystem and efficient exponentiation

In the context of the RSA cryptosystem, Alice indeed requires Bob's public key to encrypt a message intended for Bob. The RSA algorithm is a form of public-key cryptography, which relies on a pair of keys: a public key and a private key. The public key is used for encryption, while the private key is used for decryption. This system ensures that only the intended recipient, who possesses the corresponding private key, can decrypt the message.

To understand why Alice needs Bob's public key, it is essential to consider the mechanics of the RSA algorithm. RSA, named after its inventors Rivest, Shamir, and Adleman, is based on the mathematical properties of large prime numbers and modular arithmetic. The security of RSA relies on the difficulty of factoring the product of two large prime numbers.

The RSA key generation process involves the following steps:

1. Key Generation:
– Select two distinct large prime numbers, $p$ and $q$ .
– Compute $n = p \times q$ . The number $n$ is used as the modulus for both the public and private keys.
– Compute the totient $\phi(n) = (p-1) \times (q-1)$ .
– Choose an integer $e$ such that $1 < e < \phi(n)$ and $e$ is coprime to $\phi(n)$ . The integer $e$ is the public exponent.
– Determine $d$ as the modular multiplicative inverse of $e$ modulo $\phi(n)$ , i.e., $d \times e \equiv 1 \mod \phi(n)$ . The integer $d$ is the private exponent.

The public key consists of the pair $(n, e)$ , and the private key consists of the pair $(n, d)$ .

2. Encryption:
– To encrypt a message $m$ for Bob, Alice converts the message into an integer $m$ such that $0 \leq m < n$ .
– Alice then computes the ciphertext $c$ using Bob's public key $(n, e)$ with the formula: $c \equiv m^e \mod n$ .

3. Decryption:
– Bob, upon receiving the ciphertext $c$ , uses his private key $(n, d)$ to decrypt it. He computes the original message $m$ using the formula: $m \equiv c^d \mod n$ .

The fundamental principle here is that while the public key $(n, e)$ is known to everyone, only Bob knows the private key $(n, d)$ . This ensures that even if an adversary intercepts the ciphertext, they cannot decrypt it without Bob's private key.

For example, suppose Bob selects $p = 61$ and $q = 53$ . The modulus $n$ is $61 \times 53 = 3233$ . The totient $\phi(n)$ is $(61-1) \times (53-1) = 3120$ . Bob chooses $e = 17$ , which is coprime to 3120. He then computes $d$ such that $d \times 17 \equiv 1 \mod 3120$ . The value of $d$ is found to be 2753. Bob's public key is $(3233, 17)$ , and his private key is $(3233, 2753)$ .

If Alice wants to send the message "HELLO" to Bob, she first converts the message into a numerical format. Suppose "HELLO" is represented as $m = 12345$ . She then computes the ciphertext $c$ using Bob's public key:

$c \equiv 12345^{17} \mod 3233$

After performing the modular exponentiation, Alice obtains the ciphertext $c$ . She sends $c$ to Bob, who then decrypts it using his private key:

$m \equiv c^{2753} \mod 3233$

Bob retrieves the original message $m = 12345$ , which he then converts back to "HELLO".

This example illustrates the necessity of Bob's public key for Alice to encrypt the message securely. Without the public key, Alice cannot perform the encryption, and the RSA cryptosystem would not function as intended.

The RSA algorithm's security hinges on the computational difficulty of factoring large numbers. While the public key $(n, e)$ is shared openly, the private key $(n, d)$ remains confidential. The factorization of $n$ into its prime components $p$ and $q$ is a hard problem, making it practically infeasible for an adversary to derive the private key from the public key.

In practice, RSA keys are typically 2048 bits or longer to ensure security. The larger the key size, the more secure the encryption, but this also increases the computational overhead. Efficient exponentiation techniques, such as the use of the Chinese Remainder Theorem (CRT) for decryption, can help mitigate some of the computational costs.

The RSA cryptosystem relies on the use of public and private keys to ensure secure communication. Alice needs Bob's public key to encrypt a message for Bob, enabling only Bob, with his private key, to decrypt and read the message. This mechanism forms the foundation of public-key cryptography, providing a secure method for transmitting information over potentially insecure channels.

EITCA Academy

In RSA cipher, does Alice need Bob’s public key to encrypt a message to Bob?

Other recent questions and answers regarding The RSA cryptosystem and efficient exponentiation:

More questions and answers:

EITCA Academy is a part of the European IT Certification framework

EITCA Academy

LOG IN TO YOUR ACCOUNT

FORGOT YOUR PASSWORD?

CREATE AN ACCOUNT

In RSA cipher, does Alice need Bob’s public key to encrypt a message to Bob?

Other recent questions and answers regarding The RSA cryptosystem and efficient exponentiation:

More questions and answers: