RSA encryption is one of the most commonly used public encryption methods today. RSA encryption contains elegance and complication of number theory. Initially, the encryption method had been classified, however private individuals have rediscovered the encryption method, thus becoming public. The function of the RSA encryption can first seem confusing, but when comprehended the beauty can be seen.
For example, Sammy wants to send a secure message to Mark. However, Dan is always intercepting the message when sent. Thus, Mark and Sammy decide to encrypt the message so Dan can’t see the private message. First, Sammy converts his message, “hi”, into numbers using a padding scheme, and the result was 89. Let’s call this number m. Now it is Mark’s turn to start the encryption. Mark chooses two prime numbers of similar size. He chooses P1, the first prime number, as 23 and P2, the second prime number, as 19. Then, he calculates the product of P1 and P2 that results as 437. Let’s call this number n.
Now, Mark needs to use a Phi function. Phi function tests the breakability of a number. ϕ(n) — where n is a prime number — is always n-1. Also, ϕ(P1*P2) is always equal to ϕ(P1)*ϕ(P2). n for Mark is 437, and we know both of the prime numbers that Mark used: 23 and 19. Thus, ϕ(437)=ϕ(23)*ϕ(19) which is 22*18=396. Now we need to choose e, a number that is odd and not a factor of ϕ(n). In this case, e can be 7. Now, we are going to set a key called d. The equation for this key is (k*ϕ(n)+1)/e. The integer k must make the quotient integer and can be any kind of positive integer. In Mark’s case, k is 5. Now, when everything is plugged in, the result of d is 283.
Now, Mark hides everything except n and e. This way, when Dan intercepts the message sent by Mark, he only gets the information on n and e. Sammy received the encrypted numbers from Mark, and now it is his turn to encrypt the message he wants to send to Mark. The function that Sammy uses is (m^e) mod (n). Let’s call the resulting value as c. When the numbers are plugged in, the result for c will be 67. Now, Sammy sends c to Mark for decryption. The only information that Dan has is n, e, and c.
For decryption, Mark uses the function c^d mod n to see what m is. This is because c^d = m mod n, and m^(k*ϕ(n)+1) = m mod n which derives from m^(k*ϕ(n)) = 1 mod n. Thus, Mark plugs in the numbers and get (67^283) mod (437). This will decrypt the message and allow Mark to see the number 89 without Dan knowing what the secret message is.
Unless Dan knows the two prime numbers chosen by Mark, it will take Dan lots of time to figure out the factors by brute force method. The example used uses a small number, however, if the two prime numbers chosen by Mark is extremely big, then it will take hundreds or thousands of years to figure out the factor of n. This is what keeps the RSA encryption secure. Today’s computer cannot crack the RSA encryption in a reasonable amount of time because of the beauty of prime number. There are an infinite amount of prime numbers, and the only method that is the fastest is the brute force method only. Modern encryption uses the beauty of number theory, and it may seem to be hard to comprehend everything. However, all online communications are safe because of these type of encryption.
Source: https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/rsa-encryption-part-4
*(All the videos from the Modern Cryptography section in Khan Academy are used)*