How Public Key Cryptography (PKC) Works

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys... (2) A message can be 'signed' using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key... - Rivest, Shamir, Adleman; A method for obtaining digital signatures and public-key cryptosystems; Communications of the ACM; Feb. 1978.

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:

• Public key. One of the keys allocated to each person is called the "public key", and is published in an open directory somewhere where anyone can easily look it up, for example by email address.

• Private key. Each person keeps their other key secret, which is then called their "private key".

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:

• Geography. The sender and the recipient no longer need to meet or use some other potentially insecure method to exchange a common secret key. Since everyone has their own set of keys, then anyone can securely communicate with anyone else by first looking up their public key and using that to encrypt the message, enabling secure communication even across great distances over a network (like the Internet).

• Digital signatures. A sender can digitally sign their message by encrypting their name (or some other meaningful document) with their secret key and then attaching it to a message. The recipient can verify that the message came from the sender by decrypting their signature with their public key. If the decryption works and produces a readable signature, then the message came from the sender because only they could have encrypted the signature with their private key in the first place.

• Security. The disclosure of a key doesn't compromise all of the communications on a network, since disclosure of public keys is intended, and only messages sent to one person are affected by the disclosure of a private key.

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:

Product		Primes
15	=	3 x 5
77	=	7 x 11
221	=	13 x 17

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:

Encryption:    C = M^e ( modulo n )
Decryption:    M = C^d ( modulo n )

where:

M = the plain-text message expressed as an integer number.
C = the encrypted message expressed as an integer number.
n = the product of two randomly selected, large primes p and q.
d = a large, random integer relatively prime to (p-1)*(q-1).
e = the multiplicative inverse of d, that is:
        ( e * d ) = 1 ( modulo ( p - 1 ) * ( q - 1 ) )

The public key is the pair of numbers ( n, e ).
The private key is the pair of numbers ( n, d ).

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

340,282,366,920,938,000,000,000,000,000,000,000,000

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 ) =
3,835,341,275,459,350,000,000,000,000,000,000,000

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.