Question

Consider an RSA cryptosystem using \(p=23, q=\) 41 and \(g=3 .\) Encipher the message \([847]_{943}\).

Short answer

The encrypted message using the RSA key pair (943, 3) and the message 847, is obtained by carrying out the encryption \(c = 847^{3} \mod 943 \).

Step-by-step solution

Find the Modulus

The modulus \(n\) is obtained by multiplying the primes \(p\) and \(q\). So, \(n = p \cdot q = 23 \cdot 41 = 943 \)

Calculate the Totient

Next, the Euler's totient function \(\phi(n)\) must be calculated, which is \((p-1) \cdot (q-1)\). Here, \(\phi(n) = (23 - 1) \cdot (41 - 1) = 880 \)

Determine the public key

The next part of the public key is \(g = 3\), which is already given in the problem. Therefore, the public key is \((n,g) = (943, 3) \)

Encipher the message

The final step is to encrypt the message. The given message is [847]_{943}. Using the RSA encryption formula \(c = m^{g} \mod n \), the encrypted message \(c\) is calculated as follows: \(c = 847^{3} \mod 943 \)

Key concepts

Modulus Calculation

In the RSA cryptosystem, the modulus plays a crucial role in both encryption and decryption processes. It is denoted by \( n \), and in this context, it is calculated as the product of two prime numbers, \( p \) and \( q \). These primes are vital to ensure the security of the RSA system.

• To find the modulus \( n \), simply multiply the two primes: \( n = p \times q \).
• For instance, in our exercise, \( p = 23 \) and \( q = 41 \), so \( n = 23 \times 41 = 943 \).

The modulus \( n \) is part of the public key and will be used to encrypt and decrypt messages. Keeping these values prime is essential because prime factors are difficult for computers to factorize, ensuring the strength of the encryption.

Euler's Totient Function

Euler's Totient Function, denoted as \( \phi(n) \), is a fundamental element of RSA encryption. It calculates how many integers up to \( n \) are coprime with \( n \). For RSA, this value is determined using the selected prime numbers.

• The formula for calculating the Euler's Totient is \( \phi(n) = (p-1) \times (q-1) \).
• In our example, \( \phi(n) = (23 - 1) \times (41 - 1) = 22 \times 40 = 880 \).

This function is crucial for understanding the encryption and decryption process because it influences the choice of the encryption exponent and the decryption key. It provides the range of valid choices for the exponent used in the RSA algorithm.

Public Key

The public key in an RSA cryptosystem contains two essential components: the modulus \( n \) and the encryption exponent \( g \). Together, they form the public key \((n, g)\).

• In the given problem, the public key is \((943, 3)\).
• The modulus \( n = 943 \) was calculated earlier by multiplying the primes.
• The exponent \( g = 3 \) was provided directly in the exercise.

This public key is shared with anyone interested in encrypting messages to be sent securely. The exponent \( g \) is chosen such that it is typically small and an integer that is coprime to the totient \( \phi(n) \), ensuring efficient and secure encryption processes.

Message Encryption

Encrypting a message using RSA involves transforming a plain message \( m \) into an encrypted message \( c \) using the public key. This transformation uses the expression \( c = m^{g} \mod n \).

• The given message is \([847]_{943}\), which means \( m = 847 \).
• Using the formula, we compute the ciphertext: \( c = 847^{3} \mod 943 \).

The computation of \( 847^3 \mod 943 \) requires careful handling to avoid significant computational overhead and maintain accuracy. This process is a core aspect of keeping messages secure as computing large powers modulo \( n \) ensures that decryption is challenging without the right key, thereby maintaining privacy.