If Xiao Hong wants to send a message to Xiao Ming, and she hopes that only Xiao Ming can understand it, then the first step is to select two prime numbers, for example:

p=53,q=41

Next, calculate the product of these two numbers, denoted as n

n=53*41=2173

Then comes the crucial part of encryption, we need to find a number d that is easy to obtain for someone who knows the values of p and q, but hard for someone who does not know p and q. Here we need to use the Carmichael function (denoted as λ(n)), defined as the smallest integer m satisfying the following condition:

a^m= 1 (mod n) gcd(a,n)=1

For a general n, calculating its Carmichael function λ(n) is not an easy task, but for a semiprime— the product of two primes, it becomes quite easy. We can obtain this function value as follows:

λ(n)=lcm(p-1,q-1)=lcm(41-1,53-1)=520

Next, we need to choose a number e that is greater than 1 and coprime to λ(n). Here, Xiao Hong chooses e=11, which is used to calculate the number d mentioned above:

d=e^(-1) mod(λ(n))

The above equation can be written as

1=11×d(mod 520)

That is, what number multiplied by 11, when divided by 520, leaves a remainder of 1? Xiao Hong calculates the answer: d=331.

In cryptography, d is called the private key (not public, known only to Xiao Hong and Xiao Ming), while e and n are the public keys (known to everyone in advance). Now let’s restore the process of sending messages.

Xiao Hong wants to send a number, say 101, to Xiao Ming. Under the effect of RSA encryption, she needs to obtain the encrypted text as follows (public key n=2173, e=11):

Therefore, from an outsider’s perspective, Xiao Hong sent 1305 to Xiao Ming. After receiving 1305, Xiao Ming needs to perform the following operation to decrypt it (public key n=2173, e=11):

Note that p, q, and d are private keys. Here, the private key d needed during the decryption process is known only to Xiao Ming and Xiao Hong. The RSA algorithm completes the transmission of encrypted information through such operations.