Question

Consider RSA with p = 5 and q = 11. a. What are n and z? b. Let e be 3. Why is this an acceptable choice for e? c. Find d such that de = 1 (mod z) and d < 160. d. Encrypt the message m = 8 using the key (n, e). Let c denote the corresponding ciphertext. Show all work. Hint: To simplify the calculations, use the fact: [(a mod n) • (b mod n)] mod n = (a • b) mod n

Short answer

n = 55, z = 40; e = 3 is acceptable; d = 27; ciphertext c = 17.

Step-by-step solution

Calculate n and z

First, we need to calculate the values of \( n \) and \( z \). The value of \( n \) is obtained by multiplying \( p \) and \( q \), and \( z \) is calculated as \( (p-1)(q-1) \).Thus, \( n = 5 \times 11 = 55 \).For \( z \), we have:\[ z = (5-1)(11-1) = 4 \times 10 = 40 \].So, \( n = 55 \) and \( z = 40 \).

Verify e = 3

To determine if \( e = 3 \) is an acceptable choice, \( e \) must be such that it is relatively prime to \( z \). This means the greatest common divisor (GCD) of \( e \) and \( z \) should be 1.Using the Euclidean algorithm, we find:\[ \text{GCD}(3, 40) = 1 \]Therefore, \( e = 3 \) is an acceptable choice since it is coprime with \( z = 40 \).

Find d such that de = 1 (mod z)

We need to find a \( d \) such that \( d \cdot e \equiv 1 \pmod{z} \), or more explicitly:\[ d \cdot 3 \equiv 1 \pmod{40} \]Using the Extended Euclidean Algorithm, we find that\[ 3 \times 27 \equiv 1 \pmod{40} \]Thus, \( d = 27 \) satisfies the condition and is less than 160.

Encrypt message m = 8

To encrypt the message \( m = 8 \), we use the public key \( (n, e) = (55, 3) \). The ciphertext \( c \) is calculated as follows:\[ c = m^e \mod n \]Substitute in the values:\[ c = 8^3 \mod 55 \]First calculate \( 8^3 = 512 \).Now, compute \( 512 \mod 55 \):Divide 512 by 55, which gives a quotient of 9 and a remainder:\[ 512 \div 55 = 9 \text{ remainder } 17 \]Hence, \( 512 \equiv 17 \pmod{55} \).So, the ciphertext \( c = 17 \).

Key concepts

Public Key Cryptography

Public key cryptography is a crucial part of secure communication in the digital world. It relies on a pair of keys: a public key, which can be shared with anyone, and a private key, which is kept secret. The beauty of this system is that it allows secure exchanges without the need for a pre-shared secret code.
In the context of RSA encryption, the public key consists of two numbers: \( n \) and \( e \). The private key is derived from these, but critical numbers and should remain confidential. This ensures that while the public can encrypt messages using the public key, only the holder of the private key can decrypt them.
This method makes public key cryptography highly effective for ensuring privacy and authenticity in digital exchanges, such as sending encrypted emails or securely accessing websites.

Modular Arithmetic

Modular arithmetic is like a clock. Imagine it as a number system where everything wraps around after reaching a certain value, called the modulus. In the RSA algorithm, a lot of calculations happen modulo \( n \), meaning they are wrapped around at \( n \).
For example, when we find \( 512 \mod 55 \), we're asking, "What remainder do we get if we divide 512 by 55?". In our specific exercise, the remainder is 17. It's like saying there are 17 hours after full cycles of 55 hours on a clock.

• When you perform calculations in modular arithmetic, you'll always deal with values less than the modulus, making computations more feasible.
• This property is particularly useful in cryptography because it helps maintain numbers within predictable bounds.

Thus, understanding modular arithmetic is essential for working with any cryptographic algorithms like RSA.

Euclidean Algorithm

The Euclidean algorithm helps us find the greatest common divisor (GCD) of two numbers. It is a series of division operations. This method is the backbone for ensuring numbers used in cryptography are coprime, meaning their GCD is 1.
In our RSA exercise, we used the Euclidean algorithm to check that \( e = 3 \) is relatively prime to \( z = 40 \). This was achieved by showing that \( \text{GCD}(3, 40) = 1 \). To find it, you repetitively reduce the larger number by dividing it with the smaller number and taking the remainder, until the remainder is 0.
This process not only helps in verifying suitable values for \( e \) but also plays a role in finding the multiplicative inverse \( d \). This inverse is crucial for decrypting messages encrypted with the public key.

Encryption and Decryption

Encryption and decryption are the keys to securely transmitting and interpreting messages in RSA. Encryption turns plain text into unreadable 'ciphertext,' and decryption works in reverse to reveal the original message.
In our example, using the public key \((n, e) = (55, 3)\), we encrypted the message \( m = 8 \) by computing \( c = m^e \mod n \). This results in a ciphertext \( c \) of 17, which appears random to anyone intercepting it.

• Only the intended recipient, using their private key, can correctly decipher this ciphertext back to the original message \( m \).
• This transformation ensures that communications remain confidential and secure.

Understanding how these transformations occur is important for anyone wanting to master RSA and its real-world applications in secure communications.