At some point, I read a description of how RSA works (I think in Simon Singh's book). In the first term of university, we did some simple modular arithmetic.
But only when I reread those notes did I realise that they met handily in the middle. I'd thought the RSA algorithm complicated, but from my notes, it seemed that it could be explained to an intelligent person with any knowledge of modular arithmetic in one page.
(Of course, the ways to use it are complicated.)
Lemma: Fermat's Little Theorem
This says that a^(p-1)==a mod p. I mentioned this before in the description of my example sheet. The proof says:
a.2a.3a...(p-1)a=(a^p-1).(1.2.3...p-1) mod p
But a,2a,3a... and 1,2,3... are each all distinct (else some 9a-7a is a multiple of p, so p divides 2 or a, contradiction). So they're simply a rearrangement and the products are the same. Cancel them from both sides and get:
1 = a^p-1
However, if you consider p not prime, but instead, say, mod pq, then the proof works the same if instead of considering all multiples of a, you just consider those that are a multiple of neither p nor q, ie. coprime to pq. There are pq-p-q+1 of these: pq numbers, less p multiples of q, less q multiples of p, plus one because we counted pq itself twice.
Then you get a^(pq-p-q+1)=a^(p-1)(q-1) which is what you need.
Wikipedia has a nice description and an explanation of the modular arithmetic necessary, if you want to be complete.
The algorithm
You do everything mod pq, the point being that it's easy to *do* it, but hard to *undo* it. (Like taking a square is easier than taking a square root, but lots more so, which is a feature of modular arithmetic.)
However, knowing p and q gives you an easy shortcut to undo it, so you tell everyone else the product, but keep the primes themselves secret.
Specifically, you treat the message as a number, a. You raise it to some power, e mod pq. (It doesn't matter what this is, so long as it's fairly big and coprime to everything. Wikipedia suggests just always use 2^16+1.)
That's encryption.
To decrypt, you raise it to *another* power, such that the total becomes a^(p-1)(q-1)+1, which is now a again.
In fact, you take e mod (p-1)(q-1). It's coprime so it has an inverse d, ed==1 mod (p-1)(q-1). Then a^ed==a^((p-1)(q-1)*lots+1)==1^lots*a=a.
Only you can do this, because finding the inverse used (p-1)(q-1) which only you know. Everyone else needs to work out what p and q are from pq, which is hard (tm), and why factorising large numbers is so important.
Addenum
1. That's all a bit informal. The wikipedia page is actually quite well written, and a good place to go if you want to see it properly.
2. I haven't touched on how to use it for cryptography, why it's hard to reverse it, how to avoid lots of clever lateral thinking attacks that bad people think of. That's all beyond me, cryptography requires more conscientiousness than I can bring to bear.
3. Fermat's Little Theorem is *also* used to *find* these large prime numbers. Just pick a probable prime, p. And apply a^p-1 to lots of different a's. If it ever fails, p isn't prime. If it never fails, it probably is. (In fact, this always fails for some notprimes, other tests do it differently. Wikipedia on primality tests gives details, which are really interesting.)
But only when I reread those notes did I realise that they met handily in the middle. I'd thought the RSA algorithm complicated, but from my notes, it seemed that it could be explained to an intelligent person with any knowledge of modular arithmetic in one page.
(Of course, the ways to use it are complicated.)
Lemma: Fermat's Little Theorem
This says that a^(p-1)==a mod p. I mentioned this before in the description of my example sheet. The proof says:
a.2a.3a...(p-1)a=(a^p-1).(1.2.3...p-1) mod p
But a,2a,3a... and 1,2,3... are each all distinct (else some 9a-7a is a multiple of p, so p divides 2 or a, contradiction). So they're simply a rearrangement and the products are the same. Cancel them from both sides and get:
1 = a^p-1
However, if you consider p not prime, but instead, say, mod pq, then the proof works the same if instead of considering all multiples of a, you just consider those that are a multiple of neither p nor q, ie. coprime to pq. There are pq-p-q+1 of these: pq numbers, less p multiples of q, less q multiples of p, plus one because we counted pq itself twice.
Then you get a^(pq-p-q+1)=a^(p-1)(q-1) which is what you need.
Wikipedia has a nice description and an explanation of the modular arithmetic necessary, if you want to be complete.
The algorithm
You do everything mod pq, the point being that it's easy to *do* it, but hard to *undo* it. (Like taking a square is easier than taking a square root, but lots more so, which is a feature of modular arithmetic.)
However, knowing p and q gives you an easy shortcut to undo it, so you tell everyone else the product, but keep the primes themselves secret.
Specifically, you treat the message as a number, a. You raise it to some power, e mod pq. (It doesn't matter what this is, so long as it's fairly big and coprime to everything. Wikipedia suggests just always use 2^16+1.)
That's encryption.
To decrypt, you raise it to *another* power, such that the total becomes a^(p-1)(q-1)+1, which is now a again.
In fact, you take e mod (p-1)(q-1). It's coprime so it has an inverse d, ed==1 mod (p-1)(q-1). Then a^ed==a^((p-1)(q-1)*lots+1)==1^lots*a=a.
Only you can do this, because finding the inverse used (p-1)(q-1) which only you know. Everyone else needs to work out what p and q are from pq, which is hard (tm), and why factorising large numbers is so important.
Addenum
1. That's all a bit informal. The wikipedia page is actually quite well written, and a good place to go if you want to see it properly.
2. I haven't touched on how to use it for cryptography, why it's hard to reverse it, how to avoid lots of clever lateral thinking attacks that bad people think of. That's all beyond me, cryptography requires more conscientiousness than I can bring to bear.
3. Fermat's Little Theorem is *also* used to *find* these large prime numbers. Just pick a probable prime, p. And apply a^p-1 to lots of different a's. If it ever fails, p isn't prime. If it never fails, it probably is. (In fact, this always fails for some notprimes, other tests do it differently. Wikipedia on primality tests gives details, which are really interesting.)