Encryption and Asymmetric Encryption
Symmetric encryption: The same key is used for both encryption and decryption, such as the AES algorithm.Asymmetric encryption: Uses a pair of keys (public key + private key), where the public key is used for encryption and the private key is used for decryption. RSA is a typical representative.
RSA Algorithm
-
Select prime numbers p and q
Choose two distinct large prime numbers (usually greater than 1024 bits in practical applications), for example, p=3, q=5.
-
Calculate n and the Euler’s function
n=p*q=3*5=15
The Euler’s function φ(n)=(p-1)*(q-1)=8
Definition of the Euler’s function: The number of positive integers less than n that are coprime to n. If n is prime, then φ(n)=n-1.
-
Select public key exponent e
Choose an integer e that is coprime to φ(n), satisfying 1<e<φ(n), for example, e=3 (3 is coprime to 8).
-
Calculate the private key exponent d (modular multiplicative inverse)
e is coprime to φ(n), and ed-1 is divisible by φ(n),or the remainder of ed divided by φ(n) is 1, i.e., ed=kφ(n)+1, thend is the modular multiplicative inverse of e.
Example: 3d-1 is divisible by 8, d=3.
-
Generate key pair
Public key: (e,n)=(3,15), publicly used for encryption.
Private key: (d,n)=(3,15), kept strictly confidential for decryption.
-
Encryption process
Plaintext M is encrypted with the public key to obtain ciphertext C, C=M^e mod n
Example: M=2, C=8
-
Decryption process
Ciphertext C is decrypted with the private key to obtain plaintext M, M=C^d mod n
Example: C=8, M=2.
RSA Security
The security of RSA is based on the difficulty of factoring large numbers. If n is the product of two large prime numbers, reversing the factorization of n to obtain p and q is computationally infeasible (for example, factoring a 2048-bit n would require over a hundred billion years of computational power). Therefore, the public key being public does not affect the security of the private key.
Conclusion
RSA constructs an asymmetric encryption system of public key encryption and private key decryption through mathematical tools such as prime products, Euler’s function, and modular multiplicative inverses, becoming one of the foundational algorithms in modern cryptography, widely used in data transmission, digital signatures, and other scenarios.