Asymmetric Cryptography

August 25, 2020 by

Howard Poston

Introduction to asymmetric cryptography

Asymmetric cryptography differs from symmetric cryptography in that it uses two encryption keys: a public key and a private key. These keys are related by a mathematically “hard” problem, making it possible to derive a public key from a private key but not vice versa. This structure makes asymmetric cryptography more versatile than symmetric cryptography.

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

“Hard problems” in asymmetric cryptography

The security of asymmetric cryptography is based on mathematical “hard” problems. These are mathematical functions that are easy to perform but difficult to reverse.

Imagine paint colors being mixed by Alice and Bob to illustrate a key exchange algorithm based upon a “hard” problem. In this example, mixing two colors of paint is easy but separating the result to the original two colors is difficult. The asymmetry of these two operations creates a situation where two parties can securely agree on a common secret over a public channel.

While Alice and Bob can mix the correct proportions of the yellow, red and green colors to produce the final (brown) color, an eavesdropper does not have access to the same set of colors. Attempting to mix the blue and orange colors to produce the final shared secret produces a final color with twice as much yellow in it. To attack this key exchange algorithm, an eavesdropper either needs to learn one of the parties’ secrets (red or green colors), either by theft or paint separation.

Asymmetric cryptography uses mathematically-based “hard” problems. These problems have polynomial complexity for legitimate users, but eavesdroppers must solve a problem with exponential complexity. This asymmetry makes it possible to create a secure but usable algorithm that allows keys to be created or sent over public channels.

The factoring problem

One example of a hard problem used in asymmetric cryptography is the factoring problem. Given two large prime numbers, it is relatively easy to multiply them together but much harder to factor the result into the two original primes.

The reason why factoring is so difficult is that it requires a brute-force search of the set of possible primes. An attacker starts at zero and works their way up to the square root of the number being factored, checking each option to determine if it evenly divides the number.

This reliance on brute-force searching is why the factoring problem is exponentially complex. Adding a single digit to the length of the two primes has a minimal impact on the complexity of multiplication (polynomial). However, adding a single digit to a number increases the number of values it can contain by a factor of two (for binary), ten (for base 10) and so on, making it much harder to perform the brute-force search needed for factoring.

RSA, an asymmetric encryption algorithm that uses the factoring problem for its security. The public and private keys are related by a mathematical operation that combines two secret primes to form the public modulus. Knowledge of either prime enables the calculation of the private key from the public one. The public key is used for encryption and a private key is used for decryption.

RSA uses the principles of exponentiation for encryption. With exponents, (pm)n=pm*n=(pn)m. In RSA, the values of m and n in this example are chosen so that n is the inverse of m in the chosen modulus. This means that (pm)n=p1=p, as shown in the example above. However, an eavesdropper with access to only m, pm and the public modulus cannot determine p, since logarithms are also a hard problem … 

The discrete logarithm problem

Another of the mathematically hard problems used in asymmetric cryptography is the discrete logarithm problem. This problem says that it is “easy” to perform exponentiation within a given modulus but “hard” to reverse this exponentiation using logarithms.

The reason for this is the same as with the factoring problem. Exponentiation is essentially repeated multiplication, so performing an extra multiplication due to increased key length is not a major problem. However, logarithms are only solvable via brute-force search, whose complexity rises exponentially with the length of the keys used.

Elliptic curve cryptography

Elliptic curve cryptography (ECC) deals with implementing traditional cryptographic algorithms on elliptic curves. This is possible since certain operations on elliptic curves are equivalent to operations on the integers:

• Point addition is equivalent to integer multiplication
• Point multiplication is equivalent to integer exponentiation

Since multiplication and exponentiation are the “legitimate” operations for our two mathematically hard problems, it is possible to write the same asymmetric cryptography algorithms using elliptic curves. This is beneficial since elliptic curve cryptography is more efficient than integer-based variants and can achieve the same level of security with shorter keys.

Post-quantum hard problems

While the “hard” problems described above work great for now, they are not a long-term solution. The security of asymmetric cryptography depends on the “hardness” of its problems.

Shor’s algorithm, which can only be run on a quantum computer, is capable of factoring the product of two prime numbers in polynomial time. This is the same complexity as multiplication, breaking the asymmetrical difficulty of the factoring problem (and the discrete logarithm problem as well).

However, this does not mean that asymmetric cryptography will die with quantum computing. New asymmetric encryption algorithms — based on problems that are “hard” for quantum computers as well — are currently under development and testing.

Beyond encryption

Symmetric encryption algorithms, which use the same key for encryption and decryption, are mainly useful only for encryption. The same is not true of asymmetric encryption.

Since asymmetric cryptography uses two different keys, it is possible to differentiate between the person generating the message and the one receiving it. Additionally, some asymmetric encryption algorithms can be used in reverse, swapping the private and public keys and getting the same result. This makes it possible to use asymmetric cryptography for digital signatures, proving the identity of the sender since they are the only one with knowledge of the private key.

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

Sources

1. Understanding Diffie-Hellman key exchange, security.stackexchange.com
2. How does RSA work?, Hacker Noon
3. Post-Quantum Cryptography, NIST