The importance of trapdoor functions
If you and I were to meet with no possibility of being overheard, we could agree upon the secret encryption key we would use in our public communications. One of the NIST-recognized encryption schemes would be nearly impossible to compromise as long as neither of us disclosed the key to anyone else. In symmetric encryption, you and I would use the same key to encrypt the plaintext message as to decrypt it. There is only one key, and each time we wanted to change it securely, we would need to meet again.
In contrast, asymmetric encryption has both a public and a private key. There is no attempt made to hide the public key, which is used to encrypt the plaintext message. Knowing the public key and the encryption method, you and I can securely derive private keys but no one else can. Cyphertext decryption uses the private key.
A so-called trapdoor function typically lies at the heart of modern encryption algorithms. Trapdoor functions are mathematical operations that are easy to perform in the forward direction but much more difficult to execute in the reverse sense.1 Algorithms often are based on modular arithmetic, and a simple example illustrates the idea. The modulus or mod function returns the remainder 4 when the modulus is 11 and you sum addends 9 and 6: 15/11 = 1 with remainder 4.
The numbers 0 through 10 form the cyclic group or commutative ring upon which summation (mod 11) and multiplication (mod 11) are defined. The remainder or residue always will be equal to one of these values. In another example, modularly summing 22 and 18 is equivalent to 7: (22 – 2 x 11 = 0) + (18 – 11 = 7) = 7, or 22 +18 = 40: (40 – 3 x 11) = 7. The modulus can be any non-zero integer; 11 arbitrarily is used here. Quantities that are equivalent on the ring of numbers are said to be congruent. For example, 22 + 18 ≡ 18 = 7 mod 11.
As mathematical theory has evolved and computing capabilities have improved, what initially seemed to be an adequately difficult trapdoor later was deemed not to be. This point is illustrated by the progression from the RSA algorithm that relies on factoring very large integers. Next came work by Diffie, Hellman, and Merkle that involves computing discrete logarithms. More recently, a cryptography algorithm based on the mathematics of elliptic curves has become popular. Each move to a different algorithm was made because the mathematical trapdoor was thought to be more difficult to solve than the previous one while still remaining relatively easy to implement in the forward direction.
(Tom Lecklider, EE-Evaluation Engineering)
RSA algorithm
RSA is named for Rivest, Shamir, and Adleman, the first researchers to publicly describe the approach. To begin, two prime numbers P1 and P2 are randomly chosen and multiplied together to find the maximum value or modulus max. A new number pub is selected (0<pub<max) as the public key. Anyone can know the values of pub and max but not P1 and P2.
RSA performs encoding by raising each element in a numerically coded version of a plaintext message to the pub power (modmax). For example, with P1 = 13 and P2 = 7, max = 91. With pub = 5, a letter encoded as 67 is encrypted as 67^pub (mod 91): 67 x 67 = 4,489, which is larger than 91, so 4,489 (mod 91) = 30. Using the congruent value 30 for the next multiplication, 30 x 67 = 2,010, and 2,010 (mod 91) = 8. And so on for a total of four times, until 67^5 (mod 91) is found to equal 58. Mathematically, the mod operation can be performed after all the multiplications, but in a real application that uses extremely large numbers, it may be more practical to use congruent values for the intermediate multiplications.
This type of modular multiplication is closely related to the Euclidean algorithm that determines the greatest common divisor between two integers by a process of successive division by the remainder from the previous operation. The Extended Euclidean algorithm calculates an associated factor at each step. It is the final value of this factor, the modular multiplicative inverse, that is the private key—29 in this case. Multiplying 58 by itself 29 times (mod 91) will result in the original 67 being recovered.1
The modular multiplicative inverse exists if and only if P1 and P2 are coprime—they have no common factors. Because P1 and P2 are chosen to have hundreds of digits, factoring the product to find P1 and P2 is computationally very difficult. Nevertheless, with RSA, I can choose a public key and a pair of prime numbers and tell you and anyone else the resulting max and pub values. You can send me encrypted messages that only I can decode with my private key. Similarly, you can choose your own pub′ and P1′ and P2′ values, telling me only the values of pub′ and max′, so that I can send messages that you can decode with your private key. We never have to meet again.
DHM key exchange method
Moving up a level in difficulty, the Diffie-Hellman-Merkle (DHM) method also uses modular arithmetic but involves discrete logarithms instead of factoring. You and I agree to use a certain prime number n as well as a separate base number g, which is specially chosen as a primitive root mod n. This means that for every integer b<n, there is an integer k such that gk ≡ b (mod n): k is called the discrete logarithm of b to the base g modulo n.
I choose a secret number A and compute gA mod n, which I send to you using a public communications link. You choose a secret number C and compute gC mod n, which you send to me also without regard for security. I compute gCA mod n using my secret integer A, and you compute gAC mod n using your secret interger C. We both get the same value [(gA mod n)C mod n = (gC mod n)A mod n = gCA mod n = gAC mod n] that we use as a shared symmetric encryption key.2
Knowing n, g, gA mod n, and gC mod n, anyone trying to decrypt messages needs to solve a difficult discrete logarithm problem to determine A or C. In practice, n may have 200 to 300 digits and both A and C at least 100.
Elliptic cryptography
Rather than using relatively straightforward modular multiplication or exponentiation to relate the values within a cyclic group, elliptic curve cryptography (ECC) is based on the group of modulo n points that lie on a curve typically described as Y2 = X3 + AX + B. When evaluated as a straightforward algebraic equation using real numbers, a curve similar to that in the figure results. However, for cryptographic purposes, the equation is modularly evaluated, resulting in a field of discrete X,Y points.
A straight line drawn through points X1,Y1 and X2,Y2 will intersect the curve only at one other point X3,Y3 (or at infinity, which is included in the set of allowed points). By definition, X1,Y1, + X2,Y2 = X3,-Y3; that is, the sum is defined to be on the side of the curve opposite to the intersection. Doubling a point is defined in the same way as addition, but because only one point is given, the straight line is assumed to be tangent to the curve at that point.
For the curve Y2 = X3 + 2x + 2 mod 17, and starting with the point P1 = (5,1), find P3 = 2 x P1. The slope at P1 is given by s = 3X12 + 2/(2Y1) mod 17. The new X3 = s2 -X1 -X2 mod 17, and Y3 = s(X1 – X2) -Y1 mod 17 where X1 = X2 = 5 and Y1 = 1.
The slope s is evaluated as (3 x 52 + 2)/(2 x 1) mod 17 ≡ 9/2 mod 17. Modular division is not straightforward: 9/2 = 9 x 2-1. The multiplicative inverse of a number Z (mod m) is a value that when multiplied mod m by Z = 1. In this case, the multiplicative inverse exists because 2 and 17 are coprime: 2 x 9 mod 17 ≡ 1, so 9/2 mod 17 ≡ 9 x 9 mod 17 ≡ 13. Similarly evaluating the expressions for X3 and Y3 gives P3 = (6,3): so, 2 x (5,1) = (6,3). In general, the number of discrete points on a curve is close to the modulus value. For this curve, there are 19 points including the point at infinity.3
Similarly, multiplication and exponentiation can be defined on an elliptic curve. And, following the same type of public/private key exchange as used in the DHM method, two parties can establish secure communications. However, when elliptic curve cryptography is used, the much harder problem of finding the discrete logarithm of a random elliptic curve element results—and nobody actually has figured out how to do that in a practical sense. Just how much more difficult this method is can be seen by noting that the RSA algorithm would need a 2,380-bit key to be as secure as a 228-bit ECC key.1
Other schemes
Rather than rely on modular arithmetic, the family of advanced encryption standard (AES) algorithms uses substitution-permutation operations. Exclusive ORing, swapping rows for columns in arrays, shifting array rows by different amounts, substituting lookup table values, and similar actions are repeated a number of times depending on the length of the key. Decryption runs the steps in the reverse order.
AES is based on work by Rijndael and Rijmen, two Belgian cryptographers, and the NIST specification dates from 2001-2002. The Rijndael algorithm allows key lengths in multiples of 32 bits up to 256, but only lengths of 128, 192, and 256 are implemented in AES. The method is a symmetric key algorithm, so it has the usual problem of secure key distribution. All three key lengths have been approved by the NSA for secret information and the 192-bit and 256-bit key lengths for top secret.4
Summary
Encryption algorithms are available at various levels of complexity and security. Discussing a few of the more popular ones has demonstrated the principles underlying them, although necessarily at a very basic level. Those algorithms adopted as government specifications have been extensively studied and often standardized. For example, NIST recommends a series of elliptic curves for government work.5
References
1. Sullivan, N., “A (relatively easy to understand) primer on elliptic curve cryptography,” ars technica, October 2013.
2. Rouse, M., “Diffie-Hellman key exchange (exponential key exchange),” TechTarget, August 2007.
3. “Elliptic curve cryptography,” University of California at Santa Barbara, Computer Science Department.
4. “CNSS Policy No. 15 Fact Sheet No. 1,” Committee on National Security Systems, National Institute of Standards and Technology, June 2003.
5. “Recommended Elliptic Curves For Federal Government Use,” National Institute of Standards and Technology, July 1999.