Shor's algorithm

Peter Shor proposed in 1994 an algorithm that can factor large numbers in polynomial time. Below is a list of quantum unsafe algorithms and what problem they rely on for security. Each section explains how it works in a simplified way and what it would take to break it.

Prerequisites: [Key Generation, Public Key, Private Key, Prime Numbers]

RSA (Rivest-Shamir-Adleman) #

RSA relies on the IFP (integer factorization problem).

The security of RSA relies solely on the integer factorization problem. To crack RSA, you will have to understand how to do key generation in RSA, the output {d, n} is the private key. To do this, take a look at these steps:

How RSA works (Steps for Key generation in RSA) #

• Select p and q. They should be chosen at random, be both large and have a large difference.
• Calculate n = p x q
• ϕ(n)=(p−1)×(q−1). (Note: we’re following the original Euler totient function - the recent standards use the Charmichael function λ(n)=lcm(p−1,q−1))
• Select integer e. Formulas: gcd(e,ϕ(n))=1; 2<e<ϕ(n). e and ϕ(n) are coprime.
• Compute the secret exponent d. 1<d<ϕ, such that ed≡1modϕ
• Public key KU = {e,n};
• Private key KR = {d,n};

Here is a RSA calculator you can try out yourself.

How to break RSA 101 #

Integer factorization > 512-bit is very difficult.

If you can find factor big number n then given (public key) KU = {n, e}, you can find secret component d. You can get the (private key) KR = {d, n} by:

• having p and q - such that, n = p x q.
• Followed by computing ϕ(n)=(p−1)×(q−1).
• Now you should have d such that e x d = 1 mod ϕ(n)

Congratulations you have made it this far! Now lets move on to the next algorithm - ECC.

ECC (Elliptic curve cryptography) #

ECC relies on DLP (discrete logarithms problem). To be able to crack ECC, just like we did with RSA earlier - we’re going to have to understand how ECC works.

First lets look at the advantages of ECC.

Advantages of ECC in comparison to RSA:

• Less computer power needed so it is more efficient
• Same level of security as RSA
• Smaller key sizes
• Versatile - it can be used in digital signatures and key exchanges

How ECC works #

Signatures in bitcoin are made using the Elliptic Curve Digital Signature Algorithm based on the secp256k1 curve. The security of this system is based on the hardness of the Elliptic Curve Discrete Log Problem (ECDLP)¹.

ECC is based on this equation:

y2=x3+ax+b

ECC has a Trapdoor function. To simplify the concept:

Multiplying a point on the curve by a number will produce another point on the curve, but it is very difficult to find what number was used, even if you know the original point and the result². If you’re interested in diving deeper into how ECC works, take a look at this video.

How many qubits to break ECC? #

As mentioned in the following paper:

“Finally, we calculate the number of physical qubits required to break the 256-bit elliptic curve encryption of keys in the Bitcoin network within the small available time frame in which it would actually pose a threat to do so. It would require 317 × 106 physical qubits to break the encryption within one hour using the surface code, a code cycle time of 1 μs, a reaction time of 10 μs, and a physical gate error of 10-3. To instead break the encryption within one day, it would require 13 × 106 physical qubits³.”