Security Issues > Encryption >
Public Key Cryptography (PKC) >
How Public Key Cryptography (PKC) Works
The security of the standard Public Key Cryptography (PKC) algorithm RSA is founded on the mathematical difficulty of finding two prime factors of a very large number.
Historically, most encryption systems depended on a secret key that two or more parties used to decrypt information encrypted by a commonly agreed method. The main idea of PKC is the use of two unique keys for each participant, with a bi-directional encryption mechanism that can use either key to decrypt information encrypted with the other key, as described below:
If John wants to send an encrypted email to Mary, he encrypts his message with Mary's public key, and then sends it to her. He doesn't need to be worried about interception or eavesdropping since the only person that can read the message is Mary, because she is the only one that has the corresponding private key that can decrypt it. This powerful architecture has three profound consequences:
Details. The algorithms on which both RSA's and Cock's algorithms are based uses a mathematical expression built on the multiplication of two large prime numbers (a number that is the product of only 1 and itself). For example, the following numbers are the product of two prime numbers:
While RSA's and Cock's algorithm are similar, RSA's is described in the following because it is the more general case and was published first. Essentially, the public key is the product of two randomly selected large prime numbers, and the secret key is the two primes themselves. The algorithm encrypts data using the product, and decrypts it with the two primes, and vice versa. A mathematical description of the encryption and decryption expressions is shown below:
This algorithm is secure because of the great mathematical difficulty of finding the two prime factors of a large number, and of finding the private key d from the public key n. This is difficult because the only known method of finding the two prime factors of a large number is to check all the possibilities one by one, which isn't practical because there are so many prime numbers. For example, a 128 bit public key would be a number between 1 and
Now, first Euclid proved that there are an infinite number of primes. Then, the work of Legendre, Gauss, Littlewood, Te Riele, Tchebycheff, Sylvester, Hadamard, de la Vallée Poussin, Atle Selberg, Paul Erdös, Hardy, Wright, and von Koch showed that the number of prime numbers between one and n is approximately n / ln(n). Therefore, there are about:
2^128 / ln( 2^128 ) =
different prime numbers in a 128 bit key. That means that even with enough computing power to check one trillion of these numbers a second, it would take more than 121,617,874,031,562,000 years to check them all. That's about 10 million times longer than the universe has existed so far.
Therefore, unless someone makes a very large and unexpected mathematical breakthrough, it's practically impossible to find out the private key from a public key with RSA encryption, making it one of the most secure methods ever invented. However, please note that like almost all encryption systems, the RSA algorithm is still vulnerable to plain-text attacks, when a third party can repeatedly choose (or otherwise knows) some of the text to be encrypted and can examine the result. In addition, the promised development of quantum computers over the next several decades that can effectively perform many calculations simultaneously may be able to break the RSA algorithm relatively quickly.