Living in a world in which technology is becoming more and more integrated with our daily lives, it is necessary that we ensure the algorithms that protect us online are secure. In this blog, we will look into how cryptography has changed and the underlying principles of all modern cryptosystems. We will also discuss how quantum computers pose a threat to commonly employed cryptosystems.
If I were to make a bet, I would say that you are currently reading this article on your phone or computer, having accessed it through the internet. With this, let me pose a question: how are you certain your data is safe? Sure, you might not care much for your online security when searching for this blog post, but what about the numerous other resources you access on a daily basis including social media, emails, and bank accounts? You might be quick to respond with “cryptography”, but this only begs more questions. How do we know that cryptography is safe? Why are the encryption and decryption keys secure? How do we protect ourselves against implementation and hardware attacks like side-channel analysis and man-in-the-middle-attacks? Are our key agreement procedures secure? To answer these questions, we must look at the algorithms used.
Perhaps the most basic cryptosystem is the caesar cipher — a cipher that simply rotates the symbols of the Latin alphabet. With a mere 26 possibilities, this cipher, and others like it, are overwhelmingly easy to crack through computer-assisted brute force, and techniques including frequency analysis. Try it yourself with: “frqjudwxodwlrqv rq brxu iluvw fubswr dwwdfn”.
With the security of simple ciphers compromised, a different approach is required when designing cryptosystems. We need some algorithm that allows for easy decryption when authorised, but very hard (practically impossible) otherwise. Furthermore, it might be beneficial to allow anyone to encrypt data, while only those authorised can view the data (alleviating the risk associated with sharing keys). As a result of these requirements, cryptographers have taken to building cryptosystems off hard mathematical problems. To exemplify this, factorise the number 28 into primes. Easy! Now, using technology, try factorising
79702305932339030715434528427607831654557637546777286831898518598081262637289724427988536543316532850424001907323486293815253581055129489923531197112849149633280739699414903903633357791626942048408181.
You will find that while this number is composite, it is impossible for any computer to factorise this within a practical period of time. Despite this, I can easily say that the prime factors are
8606852157128365400473513253149017136902976152525158616161899392748968644629779362263014902021080289
and
9260331707490525740569536112999192475344694049460593407076723406257342328683308451052166838994398229.
Yes. I cheated. I generated these two primes and multiplied them. However, cheating aside, this illustrates how finding and multiplying large primes can be very easy, meanwhile factorising their product can be exceedingly hard — exponentially hard! With this example in mind, cryptographers have successfully designed cryptosystems that exploit exponentially complex problems in mathematics. Examples of these cryptosystems are RSA and AES.
Despite the overwhelming success of these cryptosystems, they are under the threat of quantum computers. It was shown by Peter Shor that there exists a theoretical computer (quantum computer) that can utilise quantum mechanics to parallelise certain calculations, thereby reducing the time complexity from exponential time to polynomial time — thus breaking these cryptosystems. However, it is not all bad news as the National Institute of Standards and Technology recently approved four quantum-resistant algorithms which utilise interesting mathematics including lattice theory.
So, when you send your friends a picture of your banana milkshake at the beach on Instagram, just remember you have mathematicians to thank for your data security.
Lachlan Schilling
University of Adelaide
