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.
Digital signatures
Digital signatures can be used to assure the integrity of a signature over a piece of data without any need for confidentiality.
As we learned previously, message authentication codes (MAC) solve the same problem, but they need a shared private key. Instead, when using digital signatures we want to generate signatures using a private key that can then be verified by anyone who has access to our public key. We can build it on top of trapdoor functions in a similar way as described before, but the trapdoor function is used in the opposite way.
For example, asymmetric encryption uses the trapdoor function when encrypting a message and the inverse trapdoor function when decrypting a message. On the other hand, digital signatures use the inverse trapdoor function when signing a message and the forward trapdoor function when validating a signature.
Evaluate your understanding of security in distributed systems by engaging with our AI Mentor in the widget provided below. The AI Mentor will ask a total of six questions. To get started, say hello to Edward in the widget below, and it will lead the way.
In the next chapter, we will look at some examples of protocols and standards used for security purposes and we will relate them to the principles and techniques learned in the previous chapters.
Get hands-on with 1400+ tech skills courses.