How public-key cryptography works
Public-key or asymmetric cryptography is one of the two main types of encryption algorithms. Its names come from the fact that it uses two different encryption keys: a public one and a private one.
Public and private keys
The private key used in public-key cryptography is a random number with certain properties (length, primality and so on). The public key is derived from the private key.
The security of public-key cryptography is based upon a mathematically “hard” problem. This is an operation that is “easy” (polynomial complexity) to perform and “hard” (exponential complexity) to reverse. Commonly used “hard” problems include:
- Factoring problem: Multiplication of two prime numbers is “easy,” factoring is “hard”
- Discrete logarithm problem: Exponentiation is “easy,” logarithms are “hard”
The hardness of the problem is vital to the balance of security and usability. Since certain operations are easier than others, it is possible to design an algorithm that allows legitimate users to perform the “easy” operation while forcing attackers to perform the “hard” one. By increasing the size of the values used, the difficulty of the problems can be adjusted so that the system is usable but immune to attack.
Encryption and digital signatures
The use of two different keys in public key cryptography also enables it to be used in a couple of different ways:
- Encryption: Someone with knowledge of a user’s public key can encrypt a message with it. This message can then be decrypted using the corresponding private key
- Digital signatures: A message can be digitally signed using a private key and the signature can be verified with the associated public key
These two operations can use the same algorithm. The important fact in both cases is that one key makes it possible to undo what the other does, producing the (Read more…)