Hello! For those of you keeping track, I am not Universal Enveloping Algebra. However, I am an undergraduate computer science student with a fondness for numbers, and since my topics of study (theory and cryptography) are mostly math anyway, I thought I'd give making one of these a shot. If the response is positive enough, I might go about making more of these with a focus on the theory of cryptography. But enough about me - let's get to the math.
Way back when, in the comments of the first Mathspin! post, Theodore Donald Kerbatsos wondered why people might care about prime numbers so much, to which Steve U replied that they are used quite commonly in cryptography, including "one of the most important crypto algorithms". But which algorithm is that, and how important can it really be?
WHY THE FUCK YOU SHOULD CARE
Let's begin by taking a look at the Internet - specifically the secure parts. Whenever you check your Gmail inbox, talk to someone using some secure VoIP services or send a guy money via Paypal so he'll keep quiet about that thing that happened in Tulsa last year, you are doing so using a protocol called Transport Layer Security, or TLS for short . TLS is the Internet's method of establishing a secure connection between two computers (commonly a server and client, which I will call them from here on) so you can give your credit card details out over the Internet for porn and Kickstarter pledges without giving someone else the ability to capture said details and use them for nefarious purposes (probably just some other, more twisted porn). Without getting too deep into the bowels of TLS (which would require a series of its very own), one of the initial setup steps of TLS requires the client and server to exchange some random data that only they know in order to establish a shared secret which they will use to derive encryption keys used for the rest of the connection.
"But Cardiac Linfarction," you probably aren't exclaiming, "if they just send the data over the Internet, then everyone will know it!" That's true, which is why they don't just send the data, they encrypt it first. "B-but Cardiac Linfarction, you're telling me that you have to encrypt things before you can generate the keys to encrypt things? But where do you get the keys to encrypt those things? Do you have to encrypt something else first? Oh God, it's encryptions all the way down! Nothing is real! Repent! Repent!" you might now be screaming deliriously - and you'd be right if the client and server had to establish a shared secret before they could encrypt things, but fortunately they don't have to. You see, one of the earlier setup steps for TLS is when the server sends the client its certificate, which contains its public key - and it is this key that allows me, at a little over 500 words, to finally begin talking about math...after a little history.
A (VERY) BRIEF HISTORY OF PUBLIC-KEY CRYPTOGRAPHY
A long, long time ago - back when Erg was just kinda old - mathematicians the world over were wondering how to solve this very problem. They were wondering if public-key cryptography - where you could encrypt a message to a person using their globally-available "public key", safe in the knowledge that only your intended recipient could read it because only they held the corresponding "private key" that would allow for successful decryption - was possible. Then - a revolution; in 1977 Ron Rivest, Avi Shamir and and Leonard Adleman created an algorithm based on the hardness of factoring numbers that is the basis of almost every secure communication today .
FINALLY, SOME FUCKING MATH
To begin, note that factoring a number is really hard. Maybe with a pen, some paper and a lot of time you might be able to figure out that 152557 is the product of 409 and 373, but what about a number greater than 1 with 300 zeroes behind it? To this date, nobody has published an algorithm that factors an ordinary number at a rate faster than the exponential of its bit length - for those of you who haven't studied complexity theory, when the fastest algorithm that answers your question includes the word "exponential" you better be ready to wait a while. Besides factoring, Rivest, Shamir and Adleman's algorithm (called the "RSA algorithm") relies on modular arithmetic, Euler's totient function and Euler's totient theorem.
Modular arithmetic is simple enough: if you want to find the value of an integer a modulo (or mod) another number n you subtract multiples of n from a until you get an integer smaller than n, which I'll call b. Then you would say that a is congruent (read: equal) to b modulo n, or:
Euler's totient function, φ(n), counts the number of integers less than n that are coprime to it - coprime meaning that the biggest number that divides the two integers without a remainder is one.
Finally, Euler's totient theorem states that if two positive integers are coprime to each other, then we have the congruency:
GET TO THE FUCKING ALGORITHM ALREADY
To generate your keypair, first choose two prime numbers, p and q - be sure to make them big and random, since their size and uniqueness determines how hard it is to read messages encrypted to you .
Next, multiply them together to get N and find the totient of N - however, since p and q are prime, every integer less than them is coprime to them making their totients p-1 and q-1, respectively and the totient of their product the product of their totients - (p-1)(q-1).
Next, find an integer both less than and coprime to φ(N), and call it e.
Finally, find the multiplicative inverse of e modulo φ(N) - that is, find an integer that, when multiplied with e equals 1 (mod φ(N)) - and call that integer d.
And you're done with setup! you can give N and e out as your public key and keep p, q and d to yourself as your private key.
HOW THE FUCK DO I USE THIS
If we go back to our TLS example, when the client wants to send its random data to the server it will turn it into a number less than N - let's call that number m - and turn m into ciphertext c using the formula:
And that's it! The client sends its data to the server and can be satisfied knowing that no devious hackers will be able to discover their randomness, derive the shared secret, and steal the dick pics they sent via Snapchat.
On the other end, the server regains m from c using the formula:
This works because e and d are multiplicative inverses mod φ(N), and when combined will reduce to some multiple of φ(N) plus one. This means that the result reduces to multiplying the original message with a message raised to a multiple of φ(N), and when we bring in Euler's totient theorem, we see that the latter term goes away, leaving only the original message:
And lo, everything is right in the world. Like many other theories it fails completely when put directly into practice (the "vanilla RSA" I've described here is vulnerable to replay attacks, malleability attacks and a bunch of other shit I can't remember), but after close to 40 years in service we've figured out a way to make RSA not suck.
: There is an older version of the protocol called SSL, but it uses incredibly insecure ciphers and the only reason you wouldn't use anything newer is because someone's messing with you or you are living in 1998. If it's the latter case - buy Apple, sell Enron and terrorists are going to attack New York.
: Later we found that an English mathematician named Clifford Cocks created a variant of RSA while working for GCHQ, the British NSA, in 1973; He also created the Diffie-Hellman algorithm before Diffie and Hellman. However his work was classified and knowledge of his work wasn't released until the late 1990s, to which I can only say: TOUGH BREAK
: What happens if your primes aren't big enough? Then it is easier to factor your modulus N into its primes, find d, and read your posts on your secret My Little Pony forum for Illuminati. What happens if your primes aren't unique? Well, if you can find another key with a modulus using one of your primes you can use the GCD function to factor both moduli at the same time, and so on. But primes are pretty plentiful, as UEA showed, so two keys sharing a prime is unlikely. Unless you use randomness that isn't to generate your primes, as Taiwan allegedly did.