Symmetric/Asymmetric Encryption and Digital Signatures
Let's explore the categories of public-key encryption schemes and how digital signatures assure the integrity of a signature.
As we have already explained, symmetric cryptography is mainly based on randomization. On the other hand, asymmetric cryptography does not rely only on randomization because it allows an easy computation in the forward direction (e.g., generating the key pair), but makes the inverse computation extremely hard (e.g. discovering the private key from the public key). The main building block for asymmetric cryptography is so-called intractable problems.
Intractable problems
Intractable problems are problems for which there is no known efficient algorithm to solve.
Types
There are two main types of intractable problems:
The discrete logarithm problem
The discrete logarithm problem is about calculating the logarithm of a number, which is relatively easy for real numbers, but an extremely hard problem in modular arithmetic.
The factoring problem
The factoring problem of distinguishing prime numbers from composite numbers and resolving the composite numbers into their prime factors.
Categories of public-key encryption systems
There are two basic categories of public-key encryption systems:
- those based on trapdoor functions
- those based on Diffie-Hellman key exchange
Trapdoor function
A trapdoor function is a function that is easy to calculate one way but has a secret that is required to calculate in the opposite direction.
RSA (Rivest-Shamir-Adleman) is one of the most widely used trapdoor functions. Its security hardness relies on the properties of modular arithmetic. To invert the RSA function, an attacker must factor a number, known to be an intractable problem.
With a trapdoor function, a symmetric authentication encryption scheme, and a hash function, we can build a public key encryption system that provides authenticated encryption.
Diffie-Helman key exchange
Diffie-Helman is a protocol used for key exchange based on the discrete logarithm problem. The two sides can use Diffie-Helman to exchange securely a private key that can then be used to perform symmetric encryption.
Get hands-on with 1200+ tech skills courses.