RSA public key Encryption system includes the following three algorithms: KeyGen (key generation algorithm), encrypt (encryption algorithm) and Decrypt (decryption algorithm).
(PK, SK)\leftarrow KeyGen(\lambda). The key generation algorithm takes the security constant \ λ as input, and outputs the public key PK and the private key SK. The security constant is used to determine the security of the encryption algorithm, which is usually related to the size of the prime number p used in the encryption algorithm. \ The bigger \lambda is, the bigger the prime number p is, and the higher the security guarantee of the system is. In RSA, the key generation algorithm is as follows: firstly, the algorithm randomly generates two different large prime numbers P and Q, and calculates N=pq. Then, the algorithm calculates the Euler function \ varphi (n) = (p-1) (q-1). Next, the algorithm randomly selects an integer e less than \varphi(N) and calculates the modular inverse element d of e about \varphi(N). Finally, the public key is PK=(N, e) and the private key is SK=(N, d).
CT \leftarrow encryption (PK, M). The encryption algorithm takes the public key PK and the message M to be encrypted as inputs, and outputs the ciphertext CT. In RSA, the encryption algorithm is as follows: the ciphertext directly output by the algorithm is CT = m e \ mod \ varphi (n).
M \leftarrow Decrypt(SK, CT). The decryption algorithm takes the private key SK and ciphertext CT as inputs, and outputs the message m. In RSA, the decryption algorithm is as follows: the algorithm directly outputs plaintext as m = CT d \ mod \ varphi (n). Since e and d are reciprocal under \varphi(N), we have: CT d = m {ed} = m \ mod \ var phi (n).
Therefore, from the description of the algorithm, we can also see that the public key is used to encrypt data and the private key is used to decrypt data. Of course, this can also be intuitively understood: the public key is the public key, and only when it is made public can people use it to encrypt data. The private key is the private key, and whoever has this key can decrypt the ciphertext. Otherwise, everyone can see the decryption of the private key, which would be chaotic.
= = = = = = = = = = dividing line = = = = = = = = = = = = = = = = =
Let's review the RSA signature system again. The signature system also includes three algorithms: KeyGen (key generation algorithm), Sign (signature algorithm) and Verify (verification algorithm).
(PK, SK) \leftarrow KeyGen(\lambda). The key generation algorithm also takes the security constant \ λ as input, and outputs a public key PK and a private key SK. In RSA signature, the key generation algorithm is exactly the same as the encryption algorithm.
\sigma \ left arrow symbol (SK, m). The signature algorithm takes the private key SK and the message m to be signed as inputs, and outputs the signature \ sigma. In RSA signature, the signature algorithm directly outputs the signature as \ \ \sigma = M^d \mod \varphi(N (n n (n)). Note that the signature algorithm is very similar to the decryption algorithm in RSA encryption system.
B \leftarrow authentication (PK, \sigma, m). The authentication algorithm takes public key PK, signature \sigma and message m as inputs, and outputs a bit value b, where B= 1 indicates that the authentication is passed. B=0 means that the verification failed. In RSA signature, the verification algorithm first calculates m' = \ m m' = \ M'=\sigma^e \mod \varphi(N (n n (n)), then compares m' and m, and if they are equal, outputs b= 1, otherwise outputs b=0. Note: The authentication algorithm is very similar to the encryption algorithm in RSA encryption system.
Therefore, in the signature algorithm, the private key is used to sign the data and the public key is used to verify the signature. This can also be intuitively understood: to sign a file, of course, we must use the private key, because we hope that only we can complete the signing. Of course, I hope that everyone will carry out the verification process. When you see the signature, you can pass the verification and prove that I signed it myself.
= = = = = = = = = = dividing line = = = = = = = = = = = = = = = = =
Then, why did the subject ask such a question? We can see that RSA's encryption/verification, decryption/signature processes are too similar. At the same time, the RSA system itself is symmetrical: if we take E as the private key and D as the public key in turn, this system can also be well realized. I think it is for this reason that the subject will have this kind of confusion when learning RSA system. So what is the solution? It is suggested that the subject can learn from other public key encryption systems and signature systems. Other systems do not have this symmetry. For example, a public key encryption system can look at ElGamal encryption and more secure Cramer-Shoup encryption. For signature system, we can further look at elgar Mal signature, even BLS signature, which may help the theme to better understand the difference and potential relationship between encryption and signature.
As for how encryption and signature are combined. This system is called SignCrypt. In RSA, this signcrypt looks very special and it is easy to cause confusion. I don't want to introduce the scheme of combining encryption and signature in RSA in detail here. I want to remind the subject that when encryption and signature are combined, the two groups of public keys and private keys are different.