A question about a small step in the proof of RSA encryption

In summary, RSA encryption is a form of public key cryptography that ensures secure communication and data transmission over the internet. The small step in the proof of RSA encryption involves using the Chinese Remainder Theorem to simplify calculations and make the encryption process more efficient. This encryption method uses two keys, a public key and a private key, to encrypt and decrypt data, making it difficult for unauthorized parties to access the information. However, potential weaknesses of RSA encryption include the possibility of someone guessing or obtaining the private key, as well as the use of non-random numbers in generating the keys. Despite these vulnerabilities, RSA encryption is widely used in real-world applications such as secure messaging, e-commerce, online banking, and data authentication.
  • #1
Leo Liu
353
156
1638205070973.png

From the paper https://people.csail.mit.edu/rivest/Rsapaper.pdf
Can someone explain the green highlight to me please? Sorry that I can't type much because this is the final week. Thanks.
 
Mathematics news on Phys.org
  • #2
It should be evident from equation 5
 
  • Like
Likes mfb
  • #3
From ##(5)## we have
\begin{align*}
ed\equiv 1 \mod \phi(n) &\Longleftrightarrow \phi(n)\,|\,(ed-1) \\
&\Longleftrightarrow \phi(n)\cdot k = ed-1 \text{ for some } k \in \mathbb{Z}\\
&\Longleftrightarrow \phi(n)\cdot k +1 = ed \text{ for some } k \in \mathbb{Z}\\
&\Longrightarrow M^{\phi(n)\cdot k +1} =M^{ed}
\end{align*}
 
Last edited:
  • Like
Likes Leo Liu

Related to A question about a small step in the proof of RSA encryption

1. What is RSA encryption?

RSA encryption is a form of public key cryptography that is widely used for secure communication and data encryption. It was developed in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman, and is named after their last names.

2. What is the small step in the proof of RSA encryption?

The small step in the proof of RSA encryption is the calculation of the private key, which is used to decrypt the encrypted message. This step involves finding the modular inverse of a number using the extended Euclidean algorithm.

3. Why is this small step important in the proof of RSA encryption?

This small step is important because it ensures that the private key is unique and can only be calculated by someone who knows the factors of the public key. This makes it difficult for an attacker to decrypt the message without the private key.

4. How does the small step in the proof of RSA encryption make it secure?

The small step in the proof of RSA encryption makes it secure by ensuring that the private key is difficult to calculate without knowing the factors of the public key. This means that even if an attacker intercepts the encrypted message, they will not be able to decrypt it without the private key.

5. Are there any weaknesses in this small step of RSA encryption?

While the small step in the proof of RSA encryption is generally considered secure, there have been some weaknesses identified in certain implementations. For example, if the public key is not generated properly, it can make it easier for an attacker to calculate the private key. It is important to use a secure implementation of RSA encryption to avoid these weaknesses.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
Replies
4
Views
1K
  • Programming and Computer Science
Replies
1
Views
520
  • General Math
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
250
  • General Math
Replies
22
Views
2K
Replies
1
Views
2K
Replies
33
Views
5K
Back
Top