• Varun Rao

Encryption: A Primal Need

by Varun Rao, Rahul Rao and Yasir Aheer


Summary:

  • The simplest form of encryption is with private key cryptography, but this method suffers from security shortcomings.

  • With public-key cryptography, anybody can encrypt and transmit to the receiver using only public information, while decryption requires the receiver’s private key.

  • The most ubiquitous of all public-key encryption methods is the RSA algorithm, which relies on the principle that the algorithm is easy to compute in one direction, but practically impossible in the reverse.

  • Although our current encryption methods are believed to be reasonably safe, it is possible that quantum computers will be able to crack today’s codes in our lifetimes.

"Three may keep a secret, if two of them are dead."

Benjamin Franklin



Mention prime numbers in polite company and eyes tend to glaze over, while one’s prospects of future social invitations dim. To what then can we attribute the breathless coverage given to the 2018 discovery of the largest prime number (2^(77,232,917)-1 , for the nerds among us)? Esoteric debates by mathematicians aside, there is a very real-world application of prime numbers that affects us to a large degree - encryption. These curious numbers hold the key (pardon the pun) to the security of the vast majority of internet traffic.


The requirement to transmit secret messages is an age-old problem. As with many revolutionary inventions, it appears that the impetus to encrypt messages came largely from armed conflict. Rudimentary encryption machines were first used by the Spartans as far back as 700 BC, and subsequently by the Romans circa 44 BC (see Caesar cipher below). Bizarrely, encryption is even mentioned in the Kamasutra, dating back to the 4th century.


Arguably the most famous of all was the Enigma machine, which generated encrypted code for the German military effort in WWII. Detailed histories of the events leading up to the cracking of Enigma by the brilliant mathematician Alan Turing can be found here and here. Thanks to Turing’s Bombe machine, many of the thousands of messages transmitted every day by the German armed forces landed in Allied hands. Among other things, Britain was at the time heavily reliant on essential supplies transported on merchant convoys from North America, but these ships were easy prey for German U-boats skulking under dark Atlantic waters. The situation was so dire that Churchill was advised that Britain would soon be literally starving. Cracking Enigma allowed the merchant convoys to dodge the lurking U-boats, and deliver crucial supplies of ammunition, fuel, food and troops. It is believed that the war was shortened by an incredible 2 full years, with a resultant saving of a staggering 14-21 million lives, because of Turing’s pioneering decryption work.


Encryption is clearly a vital element of modern life. While early applications of encryption focussed on military uses, the overwhelming conversion of services - banks, business, healthcare and work - from brick-and-mortar stores to online portals has resulted in a great deal of our professional and personal lives being transmitted as 1s and 0s, and ripe for plucking by the ill-intentioned. As a result, messages on VPNs, email servers, hard drives, smartphones and chat applications are routinely encrypted to prevent data breaches; it is estimated that over 72% of all network traffic is encrypted.


Like many other applications of our digital world, the basis of encryption is mathematics. The simplest form of encryption is with private key cryptography. This method applies an encryption rule that is known to both sender and receiver. One early example is the Caesar cipher, where each alphabet is simply shifted by a specified number of places. For example, using a key of 2, A would be encrypted as C, B as D, and so on. This form of encryption is also referred to as symmetric encryption, because the same key is used for encryption and decryption. The most obvious problem with this method of encryption is that there is no secure method of sharing a private key. There is also the risk of the enemy discovering the key, like in the case of Enigma, thereby rendering all encryption efforts pointless.


First introduced in 1976, public-key cryptography is an imaginative solution to these problems. It allows for a receiver to publish a public key, while retaining a secret private key. Using this public key, anybody can encrypt and transmit a message to the receiver, but it can only be decrypted using the receiver’s private key.


The most ubiquitous of all public-key encryption methods is the RSA algorithm, which relies heavily on prime numbers. The acronym comes from the last names of the three inventors, Rivest, Shamir and Adleman, all academics at MIT, who together won the A.M. Turing Award in 2002 for this pioneering work.


The detailed mathematics of why prime numbers are critical to the security of RSA are beyond the scope of this article, but is described in an excellent article by ABC Science, and in the pair of videos below by the wonderfully enthusiastic Eddie Woo.


The overarching principle of RSA is that the algorithm is easy to compute in one direction, but practically impossible in the reverse. Briefly the public key is simply the multiple of two numbers that are kept secret. Decryption is a convoluted process, but it requires knowledge of the factors of the prime number. It follows that the public key must be sufficiently large in magnitude to prevent calculation of its factors by brute force using powerful computers. For example, in 1999 it took 35 years of CPU-time (7 months running 300 computers in parallel) to factorise 512-bit RSA keys. The researchers determined that that the 155-digit long prime number n has prime factors p and q where:

  • n = 10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897

  • p = 102639592829741105772054196573991675900716567808038066803341933521790711307779

  • q = 106603488380168454820927220360012878679207958575989291522270608237193062808643.

By way of comparison, a current 2048-bit RSA system would have numbers with over 600 digits, resulting in an infeasibly long calculation time to find the prime factors.


The quantum challenge


In a previous article, we discussed the quantum computing revolution, and touched on its implications for encryption. As mentioned above, factorising a 2048-bit system with a conventional computer, or even clusters of computers, is currently thought to be impossible. Researchers have shown that a 20 million qubit quantum computer could crack this in just 8 hours. While 20 million qubits is a long way off the 70 qubits today’s quantum computers hold, it is not inconceivable that this milestone will be achieved within our lifetimes. When this happens, any data that is encrypted with today’s methods could be susceptible to data breaches. It is worth noting that there is plenty of sensitive data that governments seek to classify for periods as long as 50 years - what embarrassments lie in store for future politicians and mandarins when this treasure trove of secret information is exposed to prying eyes?


Finally, readers who arrived here from our LinkedIn post have likely realised that our cryptic message Rfymx nx zxjkzq fsi kzs! can be decoded to Maths is useful and fun! using a Caesar cipher with a shift of 5, a tribute to the generations of mathematicians who made secure communication in our modern world possible.

Co-Authors:















Disclaimer: This article is based on our personal opinion and does not reflect or represent any organisation that we might be associated with.