Public-Key Cryptography and One-Way Functions

Microsoft Corporation

September 10, 1996

Public-key cryptography (as opposed to symmetric key cryptography) relies on one-way functions, functions which are easy to calculate but hard to invert or reverse without prior knowledge. One example is factorization: it's often difficult to factor large numbers, but easy to verify a factorization. For example, it's harder to factor 4,399 than to verify that 53*83 = 4,399. Public-key cryptography exploits this asymmetry of effort to create one-way functions: functions where anyone can perform one operation (encryption or verification of signature), but it is extremely difficult to invert the operation (decryption or creation of signature) without having full information.

This is accomplished cryptographically through the use of two related, but different keys - a key pair. These keys are created at the same time. They are mathematically related in that the private key is required to invert operations performed with the public key, and the public key is required to invert operations performed with the private key.

If the public key is widely distributed, and the private key kept private, then there is a many to one function: anyone can use the public key to perform cryptographic operations, but only the person holding the private key can invert it - and a one-to-many function: the person holding the private key can perform an operation, which anyone holding the public key can invert. These two functions are used for encryption (many people can encrypt, only one can decrypt), and signature (only one can sign, many people can verify signature).