...a signing algorithm which is resistant to Quantum Computers ...
I keep reading it, but also keep not understanding it. Is this relevant for today's implementations ? Google seems to have something like an QC in the corner, NSA maybe too.
Having it conceptual in mind is good, but need to spend efforts on it ? Can it be tested/validated ? Does it scares people off as techie-talk ?
But again, I keep not understanding it. Can you explain it in simple terms to me ?
Basically, modern signature schemes are based off of the multiplication of large prime numbers, and Shor's algorithm allows quantum computers to find the prime factorization of large numbers. Shor's algorithm requires a quantum computer to run, and thus factoring large numbers into their source prime numbers becomes practical.
I'll give an example of RSA because it's much more straight-forward, but keep in mind a similar issue exists in a more complex form inside of ECDSA. (The following steps are information-only, you can skip them if you wish. If you want an example of creating/breaking an RSA key, you're in the right place. Summary at the bottom!)
For public/private key cryptography, you need to generate a private key, and from this private key you can create or derive your public key. In the case of RSA, you generate a public key in the following manner:
1.) Choose two unique, large prime numbers. (p and q)
2.) Multiply these unique primes together (result = n)
3.) Compute: (p-1)*(q-1) (result = φ)
4.) Pick an integer between 1 and φ which doesn't share a prime factor with φ (result = e)
5.) Figure out what number (d) when multiplied by (e/φ) gives 1. In other words, the remainder of (d*e)/φ is 1.
So, let's do an example! :)
1.) My two primes (obviously waaaay to small to ever be practical for actual cryptography): p=7 and q=13
2.) Multiply them(n=91)
3.) Multiply (p-1) with (q-1): (6*12)φ=72
4.) Pick an integer sharing no prime factor with φ:e=11
5.) Number which when multiplied by (e/φ) gives us a remainder of one:d=51
-->Check: d*(e/φ)=649/72=9 + 1/72 or 9 remainder 1. YAY!
Now, your public key is the two numbers 'e' and 'n', so our public key is (11, 91).
Your private key is the two numbers 'd' and 'n', so our private key is (51, 91).
Now, of course these numbers are ridiculously small and not practical for encryption, but let's demonstrate breaking this simple RSA key given the availability of a 'function' B(x) which, when fed a number, would return the prime factorization. Example: B(391) returns two numbers: 17 and 23. THIS FUNCTION B(x) is what quantum computers would provide.
Given only the public key, we have two variables initially:
e = 11
n = 91
As you can see above, if we could calculate both p and q (the initial starting prime numbers), we could re-calculate the private key d. Given the starting primes, finding 'd' is deterministic. So, our only goal here is to calculate p and q. We already know pq, and we know p and q are both primes. To this effect, calling B(n) or B(91) yields {7, 13}. However, if we were unable to easily find the prime factorization of 91, we would be stuck brute-forcing:
2*x=91 (x not integer)
3*x=91 (x not integer)
5*x=91 (x not integer)
7*x=91 (x is an integer)
For very large values of n, brute-forcing becomes computationally-infeasible. Another means of attacking RSA keys is the number field sieve, which is significantly more effective, and was used to crack a 768-bit RSA key. For a key of size 3072-bit, it would take all the computing power on Earth today longer (by orders of magnitude) than the age of the known universe to factor this number 'e' back into parts 'p' and 'q'.
Or, with a quantum computer of large enough (around 6144 'qubits' or quantum bits, a unit of quantum information which can exist in a superposition where it is both 1 AND 0), you'd just use Shor's algorithm (which has been demonstrated in factoring '15' into '3' and '5' (not impressive in itself of course, but the technology exists and Shor's algorithm is provably feasible) to call B(n).
RSA is vulnerable to quantum computers. A component of the public RSA key (n) is simply the product of two very large prime numbers. The infeasibility of factoring n into the two original primes p and q is an essential property of RSA's integrity. If a method were created which, when given a number, was able to efficiently calculate the prime factorization, it would break RSA. Shor's algorithm can factor extremely large numbers into a prime factorization in a practical timeframe.
If quantum computers were stable and were scalable to a desired size, Shor's algorithm would be able to factor an RSA public key to an RSA private key. Bitcoin doesn't use RSA, it uses ECDSA. However, Shor's 2nd algorithm from 1994 allows for solving discrete logarithms could attack ECDSA. Additionally, a smaller quantum computer would be required to attack a classically-similar security of ECDSA than for RSA (Breaking a 2048-bit RSA key needs around 4096 qubits, breaking a 224-bit ECDSA key would need somewhere between 1300 and 1600 qubits). If you're interested in reading a very dense document on quantum computers applied to Elliptical Curve Crypto, check out
http://arxiv.org/pdf/quant-ph/0301141v2.pdf.
One of Shor's proposed algorithms from 1994 allows for quantum computers to "easily" solve discrete logarithms. So, what does this mean?
(You can skip this section as well)The discrete logarithm problem is another mathematical entity believed to be easy one way, hard the other.
For example:
q^b mod n ≡ x
Where n is a primitive root of q (basically, for all possible values of r, the chances of getting any result (1, 2, 3, 4, 5, 6) from (q^b MOD n) is equal)
Solve for x.
Knowing n, q, and b, this can be calculated very easily. Let's say n = 13. 6 is a primitive root.
How we know 6 is a primitive root of 13:
6^1 MOD 13 = 6
6^2 MOD 13 = 10
6^3 MOD 13 = 8
6^4 MOD 13 = 9
6^5 MOD 13 = 2
6^6 MOD 13 = 12
6^7 MOD 13 = 7
6^8 MOD 13 = 3
6^9 MOD 13 = 5
6^10 MOD 13 = 4
6^11 MOD 13 = 11
6^12 MOD 13 = 1
6^13 MOD 13 = 6
6^14 MOD 13 = 10
6^15 MOD 13 = 8
etc... You can see a pattern. 6^1 MOD 13 is the same as 6^13 MOD 13 is the same as 6^25 MOD 13 is the same as 6^37 MOD 13. Using this looping pattern, we can predict 6^1994833 MOD 6 as being 6. Why? Because (1994833-1)/12 is an integer. We don't have to calculate 6^1994833, we just use a pattern. Cool, huh? 6^1994834 MOD 13 is 10. 6^1994835 MOD 13 is 8. Etc. Not really important to what we're doing right now, it's just awesome. :D
Aaaanyhow, back to what we were doing.
q^b mod n ≡ x
Let's set q as 6, n as 13, and b as 119. We could either use our pattern above or resort to asking a calculator, but x is easy to calculate. x = 11.
That's easy. Now, try calculating:
6^b mod 13 = 119.
For such a small modulus 13, this problem is trivial trial-and error. However, this problem becomes far more difficult with extremely large moduli, similar to a prime factorization.
So, let's summarize what we know so far.
Bitcoin uses ECDSA
ECDSA relies on the hardness of Discrete Logarithms.
Discrete Logarithms can be easily solved by an algorithm by Peter Shor on quantum computational devices.
So, if quantum computers can break ECDSA, how vulnerable is Bitcoin?
The above image explains the basic process for generating a Bitcoin address. The address itself cannot be reversed to the public key of the ECDSA keypair, because it is protected by a hash. However, when you create and sign a transaction (spend Bitcoins, namely), your public key is revealed. Peers re-calculate your address based on the public key you revealed to the network, and if the produced address matches the source address, and the signature matches the public key, the transaction is accepted.
So, coins sent to a Bitcoin address that has never sent a transaction can not be spent by someone with a Quantum computer. However, any address on the Bitcoin network that has previously made a transaction can be reversed to its private key, and an attacker can then empty the address.
As such, Bitcoin addresses would have to be one-time-use, which isn't exactly practical.
No quantum computers are available today which can crack ECDSA. Nor will they be here next year.
Quantum-resistant signing algorithms are proven effective. They rely only on the existence of a hashing function that is one-way by design, which is fulfilled perfectly fine by SHA256, SHA3, RIPE160, Grostel, etc. etc. Quantum computers can't brute-force deterministic circuit-logic operations in a cost-effective manner.
Hopefully that all made sense, I didn't expect to write a novella >.> Let me know if you have any other questions!
Quite nice volume now and still highly volatile.
Since they have taken over MintPal, let's just say that I won't be doing business with them unless there is a radical improvement in their customer service. So please ignore that part of my message. There are plenty of other payment processors.
