Encryption, the transformation of data into a form that prevents anyone unauthorized from understanding that data, is a fundamental technology that enables online commerce, secure communication, and the protection of confidential information.
Encryption algorithms are the mathematical formulae for performing these transformations. You provide an encryption algorithm with a key and the data you want to protect (the plaintext), and it produces an encrypted output (the ciphertext). To read the output, you need to feed the key and the ciphertext into a decryption algorithm (sometimes these are identical to encryption algorithms; other times they are closely related but different).
Encryption algorithms are designed so that performing the decryption process is unfeasibly hard without knowing the key.
The algorithms can be categorized in many different ways, but perhaps the most fundamental is the distinction between symmetric and asymmetric encryption.
Before 1973, every known encryption algorithm was symmetric. What this means is that the key used to encrypt the plaintext is the same key used to decrypt the ciphertext; if you know the key, you can decrypt any data encrypted with it. This means that the key must be kept secret—only people authorized to read the messages must know it, and those people who do know it can read every single message that uses it.
This in turn makes symmetric algorithms tricky to use in practice, because those keys must be securely transported somehow. Key transport wasn't so difficult in the 6th century BC, when the first encryption algorithm, called the Caesar cipher, was invented. If you wanted to share a key with someone, you could just tattoo the key onto the shaved head of a slave, wait for his hair to grow back, and then send the recipient of your message the slave.
Unfortunately, that approach doesn't scale very well. If you want to buy something from Amazon or do some online banking, you probably don't have the time to wait for your slave's hair to grow back, and given the multitude of e-commerce sites out there, you may not even have enough slaves to go around.
It took 2,500 years of on-and-off cryptography invention and research for a solution to be found to this problem. That solution is asymmetric encryption. With asymmetric encryption there is not one key, but two related keys. Messages encrypted with one of the keys can't subsequently be decrypted with that same key. Instead, you have to use the other key for decryption. Typically, one key is designated as the public key and is published widely. The other is designated the private key and is kept secret.
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.
Since RSA's invention, other asymmetric encryption algorithms have been devised; like RSA, they're all built on the assumption that a particular mathematical problem is hard to solve, usually either integer factorization or the discrete logarithm. Surprisingly, the assumption of difficulty is not actually proven in the case of either integer factorization or the discrete logarithm, and there is a possibility that a "fast" algorithm will be devised, which could render some kinds of public key cryptography insecure.
Public key cryptography in practice
Given a public key algorithm, what's it actually good for?
Perhaps surprisingly, one of the things it's not good for is general-purpose encryption. Those exponentiation operations used in RSA's encryption and decryption (or similar operations in other algorithms) are slow and expensive to compute; as a result, RSA isn't well-suited to encrypting large chunks of data. What it is good for, however, is encrypting small pieces of data—such as the encryption keys for symmetric algorithms, which are good for encrypting large amounts of data.
An example of this is the PGP program, first released in 1991. PGP, standing for "Pretty Good Privacy," is a program for sending secure messages using a combination of symmetric and asymmetric encryption algorithms. Everyone who wants to receive PGP-secured messages publishes their PGP public key. Traditionally, this is an RSA public key, though nowadays other algorithms are also supported.
To send a secure message, you first generate a random key for use with a symmetric algorithm. You use that key and the symmetric algorithm to encrypt your message. The original PGP implementation used an algorithm called IDEA for this purpose, though modern versions offer a variety of options for this, too. You then encrypt that random key with the RSA public key and bundle the two things—symmetrically encrypted message, asymmetrically encrypted random key.
To decrypt the message, the recipient uses his private key to decrypt the random key, and then uses the random key to decrypt the message itself.
Similar schemes are used for the S/MIME secure e-mail standard: public key cryptography is used to secure keys, and symmetric cryptography is used for the bulk encryption.
Disk encryption systems like Microsoft's BitLocker also uses a similar approach on systems equipped with TPM (Trusted Platform Module) chips. These chips securely store encryption keys and in principle only allow authorized software to access them. The bulk encryption of the data on the disk uses the AES symmetric algorithm; that key is then encrypted using RSA.
The ssh network protocol widely used for remote connections to Unix-like operating systems can also use public key cryptography for logging in. Users connecting to systems by ssh generate their own key pairs and associate their public keys with their user accounts on every server they want to connect to. Each time a user connects to the server, the server verifies that they're in possession of the corresponding private key by exploiting the fact that only the private key can decrypt messages encrypted with the public key
No comments:
Post a Comment