Encryption in groups of unknown order
One way of looking at RSA encryption, a way that generalizes to new methods, is that the method is based on group operations inside a group of unknown order, i.e. unknown to most people. Another way of putting it is that RSA encryption takes place in a group where everybody knows how to multiply but not everyone knows how to divide. This will be explained below.
RSA encryption starts by finding two large primes p and q. You compute the product
n = pq
and make it public, but keep the factors p and q secret. The RSA method lets anyone send you encrypted messages by doing certain operations in the multiplicative group of the integers mod n. (Details here.) Let's call this group G.
The elements of G are the integers from 1 to n-1 that are relative prime to n. The group operation is multiplication mod n, i.e. to multiply two elements of G, multiply them first as ordinary integers, then divide the result by n and keep the remainder.
The order of G, the number of elements in G, is
(n) = (p - 1)(q - 1).
You know p and q, and so you know (n), but the public does not. The security of RSA depends on the assumption that the public cannot compute (n). If someone could factor n, they could compute (n), but it is assumed that for large enough p and q it is not computationally feasible to factor n.
The public knows how to multiply in G but not how to divide. That is, anyone can carry out multiplication, but they cannot compute multiplicative inverses. Only you know how to divide in G, because you know (n) and Euler's theorem.
In some sense the public knows everything there is to know about G. It's the multiplicative group of integers mod n, and you tell them what n is. And that does tell them all they need to know to send you messages, but in practice it doesn't tell them enough to decrypt messages anyone else sends you.
When you're using RSA for public key cryptography, you're telling the world Here's an n. To communicate securely with me, carry out certain algorithms with the integers relatively prime to n."
Someone might object But how do we know whether an integer is relatively prime to n? You haven't told us its factors."
You could reply Don't worry about it. It's extremely unlikely that you'd run into a number that isn't relatively prime to n. In fact, if you did, you'd break my system wide open. But if you're worried about it, you can efficiently confirm that your numbers are relatively prime to n."
Let's unpack that last statement. We've already said that the number of positive integers less and n and relatively prime to n is (p - 1)(q - 1). So the number that are not relatively prime is
pq - (p - 1)(q - 1) = p + q - 1
and the probability of accidentally running into a one of these numbers is
(p + q - 1)/pq
Now if p and q are 300 digit numbers, for example, then this probability is on the order of one chance in 10300.
The Euclidean algorithm lets you find the greatest common factor of enormous numbers quickly. If you have a number k and you want to test whether it's relatively prime to n, you can compute gcd(k, n). If k was chosen at random, the gcd is extremely likely to be 1, i.e. relatively prime to n. But if the answer is not 1, then it's either p or q, in which case you've broken the encryption.
***
If you can factor large numbers, you can break RSA encryption. But it's conceivable that you may be able to break RSA without being able to factor large numbers. That is in fact the case when RSA is implemented poorly. But aside from implementation flaws, nobody knows whether breaking RSA is as hard as factoring. Michael Rabin came up with a variation on RSA that is provably as hard as factoring, though I don't know whether it has ever been used in practice.
More cryptography posts here.
The post Encryption in groups of unknown order first appeared on John D. Cook.