The first public key encryption algorithm: RSA
The first algorithms using asymmetric keys were devised in secret by the British government's SIGINT agency, GCHQ, in 1973. That work was not made public, however, until 1997, when the British government declassified it.
The first published, commercially available algorithm (which happened to work in much the same way as GCHQ's worked, albeit in a more generalized form) was invented in 1977, and it was called RSA after the names of its three inventors (Ron Rivest, Adi Shamir and Leonard Adleman).
Symmetric algorithms essentially depend on jumbling up the plaintext in complex ways and doing so lots of times; the key is what specifies the exact jumbling up pattern that was used. Asymmetric algorithms take a different approach. They depend on the existence of hard mathematical problems. The keys here are solutions to these mathematical problems.
The problem that RSA is built around is that of integer factorization. Every integer has a unique prime factorization; that is, it can be written as a multiplicative product of prime numbers. For example, 50 is 2×52. While factorization is something that we all learn at school, it's actually a hard problem, especially when dealing with large numbers.
The naive algorithm you learn in school is called "trial division"; you divide the number you are trying to factorize by each prime number in turn, starting at 2 and working your way up, and check to see if it's wholly divisible. If it's wholly divisible then you then factorize the number that's left over, starting at the same prime as you just divided by. If it isn't, you try the next prime number. You only stop when you've tried every prime number less than or equal to the square root of the number you're trying to factorize.
This is easy enough for small numbers, but for big numbers it's very time-consuming. There are various algorithms that are a bit quicker than trial division, but only incrementally so.
RSA key pairs (that is, the pair of private and public keys) are generated in the following way:
Choose two large, distinct prime numbers, called p and q.
Compute p × q, and call this n. The size of this number in bits is the key length, and it gives an indication of how strong the key is: the longer, the better.
Compute (p - 1) × (q - 1), and call this φ(n).
Pick an integer e that is coprime with φ(n). That is to say, a prime factorization of e should have no factors shared by a prime factorization of φ(n).
Calculate d such that d × e = 1 (mod φ(n)). This multiplication uses modulo arithmetic (also known as clock arithmetic). Modulo arithmetic wraps around. It counts normally from 0 to mod φ(n) - 1, then wraps around back to 0 again. This is much the same as the way that on a clock, the number after 12 isn't 13; it's 1.
The public key is the pair of numbers (e, n). The private key is the pair (d, n). p, q, and φ(n) must also be kept secret.
Encryption and decryption are both quite simple. A ciphertext c is generated from a plaintext m as follows:
c = me (mod n)
Decryption is similar:
m = cd (mod n)
Here's where the difficulty of integer factorization is important: if n could easily be factorized then anyone could determine p and q, hence φ(n), and hence d. If d were known to everyone then they could decrypt the messages encrypted with e with ease.
Conventionally, e, the public key, is chosen to be a smaller number than d, typically 65,537.
Link
The first algorithms using asymmetric keys were devised in secret by the British government's SIGINT agency, GCHQ, in 1973. That work was not made public, however, until 1997, when the British government declassified it.
The first published, commercially available algorithm (which happened to work in much the same way as GCHQ's worked, albeit in a more generalized form) was invented in 1977, and it was called RSA after the names of its three inventors (Ron Rivest, Adi Shamir and Leonard Adleman).
Symmetric algorithms essentially depend on jumbling up the plaintext in complex ways and doing so lots of times; the key is what specifies the exact jumbling up pattern that was used. Asymmetric algorithms take a different approach. They depend on the existence of hard mathematical problems. The keys here are solutions to these mathematical problems.
The problem that RSA is built around is that of integer factorization. Every integer has a unique prime factorization; that is, it can be written as a multiplicative product of prime numbers. For example, 50 is 2×52. While factorization is something that we all learn at school, it's actually a hard problem, especially when dealing with large numbers.
The naive algorithm you learn in school is called "trial division"; you divide the number you are trying to factorize by each prime number in turn, starting at 2 and working your way up, and check to see if it's wholly divisible. If it's wholly divisible then you then factorize the number that's left over, starting at the same prime as you just divided by. If it isn't, you try the next prime number. You only stop when you've tried every prime number less than or equal to the square root of the number you're trying to factorize.
This is easy enough for small numbers, but for big numbers it's very time-consuming. There are various algorithms that are a bit quicker than trial division, but only incrementally so.
RSA key pairs (that is, the pair of private and public keys) are generated in the following way:
Choose two large, distinct prime numbers, called p and q.
Compute p × q, and call this n. The size of this number in bits is the key length, and it gives an indication of how strong the key is: the longer, the better.
Compute (p - 1) × (q - 1), and call this φ(n).
Pick an integer e that is coprime with φ(n). That is to say, a prime factorization of e should have no factors shared by a prime factorization of φ(n).
Calculate d such that d × e = 1 (mod φ(n)). This multiplication uses modulo arithmetic (also known as clock arithmetic). Modulo arithmetic wraps around. It counts normally from 0 to mod φ(n) - 1, then wraps around back to 0 again. This is much the same as the way that on a clock, the number after 12 isn't 13; it's 1.
The public key is the pair of numbers (e, n). The private key is the pair (d, n). p, q, and φ(n) must also be kept secret.
Encryption and decryption are both quite simple. A ciphertext c is generated from a plaintext m as follows:
c = me (mod n)
Decryption is similar:
m = cd (mod n)
Here's where the difficulty of integer factorization is important: if n could easily be factorized then anyone could determine p and q, hence φ(n), and hence d. If d were known to everyone then they could decrypt the messages encrypted with e with ease.
Conventionally, e, the public key, is chosen to be a smaller number than d, typically 65,537.
Link