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 the methods defined by Prof Peter Shor, and in the cracking of public key encryption. On the Internet we use public key encryption for two fundamental 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.
• Generating a shared key (key generation). We use public key encryption within shared key generation — where two sides communicate and end up with the same encryption key. Symmetric key encryption is then used to secure the channel between the sides … let’s call them Bob and Alice. Every time you connect to Google, this is the basic operation used. Normally we use a key sharing method — such as Diffie-Hellman — and then both sides generate the same encryption key, and then we agree to use it with a robust symmetric method such as AES.

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^x 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]:

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

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.
• Code-based cryptography — This method was created in 1978 with the McEliece cryptosystem but has barely been using in real applications. The McEliece method uses linear codes that are used in error correcting codes, and involves matrix-vector multiplication. An example of a linear code is Hamming code.
• Multivariate polynomial cryptography — These focus on the difficulty of solving systems of multivariate polynomials over finite fields. Unfortunately, many of the methods that have been proposed have already been broken.
• Hash-based signatures — This would involve created digital signatures using hashing methods. The drawback is that a signer needs to keep a track of all of the messages that have been signed, and that there is a limit to the number of signatures that can be produced.
• Isogenies — These method fits in well with current implementations, and can be used to replace existing Diffie-Hellman based methods. Methods include Supersingular elliptic curve isogeny cryptography.

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.
• Very simple LWE. LWE. Outlines Learning With Errors.
• Public Key Encryption with Learning With Errors (LWE). LWE. Outlines public key encryption with Learning With Errors (LWE).
• Multibit Encryption with Learning With Errors (LWE). LWE. Outlines multibit Encryption encryption with Learning With Errors (LWE).
• Homomorphic Encryption with Learning With Errors (LWE). LWE. Outlines homomorphic encryption with Learning With Errors (LWE).
• Ring Learning With Errors for Key Exchange (RLWE-KEX). LWE. Outlines RLWE-KEX.
• NewHope for Key Exchange. NewHope. Outlines NewHope for shared key generation.
• Lattice Encryption: NTRU (Python). NTRU. Outlines how NTRU operates for key generation.
• Lattice Encryption: Mod P polynominal operations. Poly. Outlines Mod P polynomial operations.

Hash-based signatures:

• Lamport Signatures. Lamport. Outlines Lamport signatures.
• Winternitz Signatures. Winternitz. Outlines Winternitz signatures.
• Merkle Signatures. Merkle Signature. Outlines Merkle signatures.
• Generalised Merkle Signature Scheme. GMSS. Outlines Generalised Merkle Signature Scheme.

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 …