Symmetric/Asymmetric Encryption and Digital Signatures

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.