In recent years, computer network paralysis and hacking incidents have often made us feel uneasy. That is because, now more than ever, we are doing countless things and managing valuable assets through computers and the Internet. In most incidents, our property and accounts are safely secured by “the something”. That something is a “password”. Surprisingly, even as we enter passwords every day, most of us do not understand the notion of how passwords protect our information. Before going through the mechanisms of how passwords work, we need to first look at the following numbers:

Have you noticed the main feature of all the numbers above? These numbers are prime numbers. A prime number is a number that does not divide into any number except one and itself. As shown in picture below, the prime numbers seem to be distributed without any regularity among the natural numbers.

This is a mystery that many mathematicians have wanted to solve since the discovery of irregularity in prime number distribution. Prime number irregularity has been one of the greatest mysteries of the world since human mathematical inquiry began. Mathematicians have been enchanted by this mystery and have done their utmost to solve its riddle but these numbers still do not give us a definitive answer. However, mathematicians have found a way to use “the irregularity of the distribution of prime numbers” through an algorithm.
This algorithm is called the “RSA algorithm” and is named after the three scholars who helped to create it: R for Ronald Rivest, S for Adi Sahmir and A for Adleman. They prepared and discarded more than 40 algorithms before the results were published. Sometimes, they were skeptical about actually being able to implement this concept. It was a very tough process, but, since they did not give up, we can now use high-safety algorithms.

Unexpectedly, the RSA algorithm is simple. It is easy to multiply two prime numbers, but, conversely, it is much more difficult to divide them. RSA algorithms use this difficulty as a theoretical basis. Let us take a look at the following simple experiment.

The UOS Times asked two students at the University of Seoul (UOS) to divide two 4-digit numbers, and measured how long it took for them to do this. It took thirty seconds to solve the first 4-digit number. Next, we give them another 4-digit number to divide after changing the last digit on the previous 4-digit number. The result showed a big difference. The second attempt took 3 minutes. The first 4-digit number was the product of multiplying two numbers (not the prime number) and the second number was a composite of two prime numbers. Students said they had more difficulty in factoring last one than the first one. If these numbers are a composite of a larger prime number, it becomes even more difficult. Currently, the number of primes we use in the RSA algorithm is a composite of two prime numbers with a size of 2¹⁰²⁴ digits. If we were to factor these numbers with “Chundung”, the third fastest supercomputer in Korea, it would take approximately 1x1011 years.

All of this means that our information will be kept secure for as much time as it would take to solve the composite numbers in use. We have looked at the core concept of RSA algorithms. Next, let us see how three doctors have applied this concept to encryption.
The RSA algorithm involves three steps: key generation, encryption, and decryption. Initially, a public key and secret key are obtained by multiplying two large prime numbers and performing an additional operation. After the keys are generated, the first two prime numbers are no longer important and can be discarded. A public key is a key publicly available to everyone, but a secret key must not be disclosed to anyone. This is because the secret key is used to decrypt the message encrypted by the public key.

Bob encrypts the message he wants to send using Amanda’s public key and sends an encrypted message to her. The recipient decrypts the encrypted message using her private key. Even if the third party intercepts the encrypted message, it will not be decoded because the third party does not possess the secret key.

In addition, if Amanda encrypts her digital signature using her own private key and sends it along, she can be more certain that the message is from Bob. The recipient can decrypt the encrypted signature using the public key. In other words, by sending the message with a “sender’s seal” attached, you can feel a greater sense of trust.

The principle is simple, but the safety is robust. Not only have hackers hacked credit cards or information on the Internet, they have even breached the RSA algorithm itself. Would it not be reassuring to remember that my valuable information is protected by these algorithms?

Jo Geon-ho
edendh27@uos.ac.kr