Image for post
Image for post

Cracking The Internet With Waves

In research, we get excited about problems, and in cyber security there’s no greater problem than the whole of the Internet being comprised. So will it a new vulnerability like Heartbleed? Or a new hacking team? Nope … it is likely to be caused by methods defined by Prof Peter Shor.

On the Internet we use public key encryption for two main things:

  • Providing identity (signing). The first is to prove the identity of something, where the entity signs with its private key, and the others can prove this signing with the associated public key.

So what’s the problem?

Currently we use difficult problems to create these keys, such as where N is equal to the product of two prime numbers (P and Q), as used in RSA. If the prime numbers are large, it is a difficult process to actually find the factors of P and Q. If we use relatively small prime numbers, it is relativity inexpensive to factorize N [here].

We also use discrete logarithms, such as Y = Gˣ mod P, and where is difficult to determine x, even if we know Y, G and P. This is used in the Diffie-Hellman key exchange method, and also in the El Gamal method of public key encryption.

We also increasing use elliptic curves of public key methods, and where we take a point on an elliptic curve Q(x,y), and then generate a large random number (n), so that P = n x Q. Then, even though we know P and Q, it is extremely difficult to determine the value of n. This is used in lots of places, including with blockchain methods, IoT, smart cards, and so on. Typical methods are Elliptic Curve Diffie-Hellman (ECDH) and in ECDSA (Elliptic Curve Digitial Signature Algorithm).

There are existing methods which allow us to factorize, including the difference of squares [here], and quadratic residues [here], but the sizes of common prime numbers are great enough for this to be an extremely costly process (often involving the energy to boil the oceans in order to crack a single key).

Enter Shor

Shor imagined two sine waves, one of length P and other of length Q. Assuming that P and Q are co-prime (that they do not share a common factor), he proposed a question of finding the point at which the harmony of P overlaps with Q, and then repeats itself. For this we can project to a point N, and then find the point at which the phase of P and Q will be 0. In a quantum computer, this phase checking is a fairly easy task, and we can thus factorize N in terms of P and Q.

So let’s say I pick P=2 and Q=3 (which are two prime numbers), and where I generate two sine wave with a length of 2 and a length of 3. When I plot the two together, you can see that the point at which they are in-phase is at 6 [link]:

Image for post
Image for post

And here are two wave of length 11 and 13 [here] and we see they are in-phase at 143 (which is 11x13):

Image for post
Image for post

In this way, we crack RSA, but generating two waves of different lengths, and then looking at the point at which they synchronize. The hard problem that we had before, has just become a relatively easy one within a quantum computer.

So how do we overcome this?

We overcome this by creating problems which are still hard to solve within a quantum computing era. The main contenders for quantum robust methods are:

  • Lattice-based cryptography — This classification shows great potential and is leading to new cryptography, such as for fully homomorphic encryption, and code obfuscation.

In order for you to understand some of the methods, I’ve created demonstrations here.

Code-based cryptography:

  • McEliece cryptosystem. mce. Outlines McEliece cryptosystem.

Multivariate polynomial cryptography:

  • Unbalanced Oil and Vinegar (UOV). UOV. Outlines Unbalanced Oil and Vinegar (UOV) cryptosystem.

Supersingular elliptic curve isogeny cryptography:

  • Supersingular Isogeny Diffie-Hellman for Key Generation. SIDH. Outlines SIDH.

Lattice cryptography:

  • Lattice Encryption. Lattice. This outlines Lattice encryption.

Hash-based signatures:

  • Lamport Signatures. Lamport. Outlines Lamport signatures.

Conclusions

Enjoy learning!

Cryptography is the most wonderful thing … it is the true respecter of privacy, identity and trust, but it can be fragile, if not handled properly. Our greatest risk to the Internet is a large scale trust infrastructure breach, so watch the crypto!

Here’s one of our favouriate Professors telling it like it is …

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store