How Does Public Key Encryption Work?

Public key encryption enforces Internet security.

Encryption makes text unintelligible, but the system used must be reversible. Most encryption systems apply a formula to characters. This formula has a variable, or key, that influences the outcome of encryption. If people learn the formula, they still cannot decrypt the text without the key. Key distribution is a major issue in encryption systems. The sender and receiver of an encrypted message need to share the key without anyone else discovering it. Public key encryption systems are one solution.

Public Key

In public key systems, two formulas are used: one to encrypt and one to decrypt. The relationship between these two formulas is such that one value of the decrypting key decodes text encoded with the encrypting key. It is impossible to deduce the decrypting key even if you know the encryption and decryption formulas and the encryption key. For this reason, people can publicize their encryption key without fearing the encrypted text will be decrypted -- hence the name "public key."

Private Key

A public key's corresponding decryption key cannot be released to others. A trusted correspondent does not need to know the decryption key to send encrypted messages. Third parties should not be told the decryption key. For this reason, the decryption key is called the "private key."

Procedure

Suppose that Andrea and Bobby want to engage in a private conversation over the Internet. They are nuclear scientists and have sensitive information to share. Andrea sends Bobby her public key, and Bobby sends Andrea his public key. Anyone can intercept these two messages and learn these public keys, but it would do them no good. Bobby writes a message to Andrea, encrypts is using Andrea's public key and then sends it to Andrea. Andrea knows her own private key and uses it to decrypt Bobby's message. She then composes a reply and encrypts that using Bobby's private key. When Bobby receives Andrea's reply, he decrypts it using his own private key.

Formulas

One of the most common public key encryption systems is called RSA. This acronym stands for Rivest, Shamir and Adleman, named after the three people who invented they system. The private key is actually two numbers. The first (n) is the product of two large prime numbers (p and q). The second number in the public key (e) is a random prime number between 1 and the Euler's totient function of n(T), which is (p -- 1) (q -- 1). The chosen number should be a coprime with T. This means that these numbers have no common positive divisor other than 1. The private key (d) is calculated as e-1 mod T.

Implementation

The public key is n and e, the private key is n. The cipher C of text M is calculated by C = (M to the power of e) mod n. This encrypted message is decrypted by M = (C to the power of d) mod n.

References

• University of Edinburgh: Introduction to Public Key Encryption
• Living Internet: How Public Key Cryptography (PKC) Works
• Muppet Labs: How Prime Number Hide-and-Seek: How the RSA Cipher Works