Question

A few years from now, you are a teaching assistant for Computer Networks. You explain to the students that in RSA cryptography, the public and private keys consist of \((e, n)\) and \((d, n)\) respectively. The possible values of \(e\) and \(d\) depend on a value \(z\),whose possible values depend in turn on \(n\). One of the students comments that this scheme is unnecessarily complicated, and proposes to simply it. Instead of selecting \(d\) as a relative prime to \(z, d\) is selected as a relative prime to \(n\). Then \(e\) is found such that \(e \times d=1\) modulo \(n\). This way, \(z\) is no longer needed. How does this change affect the effort required to break the cipher?

Short answer

The change weakens the encryption, making it easier for attackers to break the cipher.

Step-by-step solution

Understanding RSA Cryptography

In RSA cryptography, the public key consists of \(e, n\) and the private key consists of \(d, n\). The security of RSA is based on the difficulty of factoring the product \(n\), where \(n = p imes q\) with \(p\) and \(q\) being large prime numbers. \(e\) is chosen such that it is relatively prime to \((p-1)(q-1)\), and \(d\) is the modular inverse of \(e\) modulo \((p-1)(q-1)\). This ensures that messages encrypted with \(e\) can be decrypted with \(d\), which relies on Euler's theorem.

Proposed Change Explanation

The proposal modifies the condition for selecting \(d\), suggesting that \(d\) be relatively prime to \(n\) instead, and then finding an \(e\) such that \(e imes d = 1 \pmod{n}\). This eliminates the need for calculating \((p-1)(q-1)\) or \(z\).

Exploring Impact of the Change

Selecting \(d\) relatively prime to \(n\) alters the key property of RSA wherein encrypted data requires factorization of \(n\) for decryption without the private key. By changing \(d\)'s modular connection from \((p-1)(q-1)\) to \(n\), the relation loses the Euler's theorem support, weakening security properties.

Impact on Cryptanalysis Effort

In theory, if \(d\) is chosen to be relatively prime to \(n\), it could decrease the strength of the cryptosystem because \(d\) becomes more predictable and unrelated to the factorization of \(n\). This may simplify adversarial efforts to deduce \(d\) since \(d\) would not be dependent on the unknown primes \(p\) and \(q\).

Conclusion

This change reduces the strength of the encryption, making it possibly easier for an attacker to guess or compute \(d\) without factoring \(n\), thereby reducing the effort required to break the cipher.

Key concepts

Public Key

In RSA cryptography, the public key is made up of two numbers: \(e\) and \(n\). This key is used to encrypt messages. The number \(n\) is the product of two large prime numbers, \(p\) and \(q\) (i.e., \(n = p \times q\)).
This multiplication process is a critical component because the difficulty in factoring the large number \(n\) is what keeps RSA secure.
In addition:

• \(e\) is chosen to be a small integer that is coprime with \((p-1)(q-1)\), meaning \(e\) and \((p-1)(q-1)\) share no common factors other than 1.

The public key \((e, n)\) is safely distributed to anyone who wishes to send an encrypted message.
Once they have this key, they can encrypt their message by transforming each piece of data into a number, then applying the function \(C = M^e \,\text{mod}\, n\), where \(M\) is the original message and \(C\) is the encrypted message.

Private Key

The private key in RSA cryptography consists of the pair \(d, n\). This key is essential for decrypting the messages that were encrypted using the public key \((e, n)\).
The component \(d\) is particularly crucial, as it is the modular inverse of \(e\) with respect to \((p-1)(q-1)\). The computation of \(d\) ensures that while it is easy to encrypt messages with the public key, decrypting them without \(d\) is computationally difficult.
The role of the private key includes:

• Decrypting messages: When an encrypted message \(C\) is received, the private key is used in the operation \(M = C^d \,\text{mod}\, n\) to retrieve the original message \(M\).
• Ensuring security: Because \(d\) relies on \((p-1)(q-1)\), which is not known to anyone who doesn't know the primes \(p\) and \(q\), cracking the encryption requires lengthy computations.

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, which considers numbers "wrap around" once they reach a certain value, known as the modulus. It's like a clock where, after reaching 12, it goes back to 1.
In RSA cryptography:

• The modulus \(n\), computed as \(p \times q\), determines the wrap-around point.
• The operations use mod, a fundamental aspect of how RSA processes encryption and decryption.

For instance, if an encrypted message \(C\) is performed under mod \(n\), it's as if numbers higher than \(n\) wrap around back to smaller values. This property is crucial:

• It allows large integers to be processed more efficiently, avoiding overflow in computations.
• It plays a central role in ensuring the encryption and decryption functions are inverses of each other, i.e., operating under mod \(n\) means \((M^e)^d \equiv M \,\text{mod}\, n\).

Euler's Theorem

Euler's theorem is a key mathematical concept used in RSA cryptography. It states that if two numbers, \(a\) and \(n\), are coprime, then \(a^{\phi(n)} \equiv 1 \pmod{n}\). Here, \(\phi(n)\), known as Euler's totient function, is the product \((p-1)(q-1)\) for our RSA moduli.
The application of Euler's theorem provides us the mathematical basis to assure:

• If \(e\) and \((p-1)(q-1)\) are coprime, then there must be some \(d\) such that \((e \times d) \equiv 1 \pmod{\phi(n)}\).
• This ensures that an encrypted message with \(e\) can be reversed (decrypted) using \(d\).

Euler’s theorem gives RSA its secure structure, attributing the difficulty in breaking the cipher to solving for \(d\), which relies heavily on knowing \(\phi(n)\). The proposal to change to \(n\) significantly reduces the dependency on Euler's complex, hard-to-factor algorithms, hence the suggestion is less secure.