I know what you’re saying. “Whoa! What’s going on with that title? Has Rob gone mad?”
No, I’m not mad. I mean, I am now writing a math blog, so maybe I have lost my mind a bit in a certain sense, but no. This isn’t madness. This is math. It’s actually pretty exciting math.
Cryptography and encryption are the cool, pretentious, whiskey-drinking hipsters of the applied math world. A few of us have decided to embrace these subjects, become these people, and now we see ourselves as better than everyone else. The rest of us can’t stand those damn, dirty hipsters.
What I’m going to be talking about tonight is a branch of encryption known as RSA encryption. RSA encryption was first publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman, with the mathematicians’ last names used to form the RSA acronym. Leonard Adleman is actually one of my math heroes, a California Bay Area mathematician who in the 1970s had some interest and participation in just about everything, from math to banking to science to computers, but little specialization in anything. Nevertheless, his creativity and cleverness led to him helping come up with this form of encryption which has become the backbone of our theory behind encrypting data. Without these three guys, your emails would be readable by all, internet payments would be impossible, and even this little blog could be hacked in a heartbeat. And Snapchat…Snapchat would be a nightmare. Luckily, our modern encryption techniques do a great job at keeping us safe. Only recently have hackers been starting to gain success in beating encryption, not because they were able to crack the RSA code, but because they have become better at phishing, keeping track of the time it takes to encrypt data, and finding back doors.
While a full understanding of the RSA encryption algorithm is not needed for what it is I want to talk about, the algorithm involves exploiting modular arithmetic to create two different keys to data. The first key, called the public key, is a modular calculation that encrypts data. Now, normally when it comes to keys, you don’t want to give a copy of the key to the entire world. Yet, the beauty of RSA encryption is that, because modular arithmetic is being used, if a person tries to “unlock” the data with the same public key used to “lock” the data, he or she will get nowhere. The modulus will simply loop. Instead, a private key, retained by the recipient of the message, is needed to properly unlock the message. The private key is a second modular calculation that decrypts the data. The only way data is going to be properly and formally decrypted is through use of that private key.
So where do these public and private keys come from? Well, they come from prime numbers. Namely, two prime numbers, p and q, with their product, n=p*q representing the public key. The private key is then obtained from a second calculation involving p and q into what I have sometimes heard called the “totient” or “totient product.” A summary of the actual math involved is provided in the featured image for this post.
At this point, you may say, “but Rob, why can’t a hacker just factor n into its base primes? Wouldn’t that immediately let the hacker then use the base primes to calculate the private key and decrypt whatever he or she wants?”
To which I will respond, “Yes. You are absolutely correct, which is why the p and q chosen tend to be monstrously huge numbers. Basically, our entire global encryption system depends on the fact that ‘it’s hard to divide big numbers.’ That’s kind of a scary thought. If a way to quickly and efficiently factor any number is devised, then most if not all of our encryption technology will fall apart.”
“Yeah, but Rob, what kind of heinous people would spend their days actively trying to come up with ways to take down our interweb technology?”
Mathematicians, that’s who! The problem of coming up with a theory of division that makes it as simple to use as addition or multiplication is known as the RSA Problem, and it’s a popular problem in the applied math world. Even I find it fascinating, encryption be damned!
The problem basically boils down to factoring n. Thus, if our public key is n=p*q, where p and q are both odd primes, then the RSA Problem involves isolating the primes p and q. So, we have p, we have q, and we can start having thoughts about an x right in the middle of p and q, namely x=(p+q)/2. If this is starting to sound a lot like it has some relationship to Goldbach’s Conjecture, you’re absolutely right.
Enjoy the paper!
Update: It looks like the attached paper has a few typos in the form of missing parenthesis (you’ll notice them when you read). My apologies for the typos. In my defense, I’ve posted 4 pretty awesome math papers in a little over a week. Hope you’re enjoying the blog, the proofs of Legendre’s and Brocard’s conjectures, and the insights on prime numbers!