Great explanation professor, I do have one question regarding producing the factors of a number originally from which the number was produced, is it really possible? Even if quantum computers gave us the computation power for doing all this computation but is not our solution space is infinite possible solution, so how do we find the exact factors which were used to produce the number in first place? I don't have knowledge of working of these ciphers so kindly do correct me if I'm approaching it in a wrong way, thanks.
Thanks for the question! The factoring solution space is not infinite, but it is exponential (or worse) with the number of bits in the keys. Here's an almost 2000 year old algorithm that will factor any number into its prime factors, given enough time to compute: en.wikipedia.org/wiki/Sieve_of_Eratosthenes. The challenge with conventional computers is that the key size for RSA today is 2048 or 4096 bits, so you are looking at O(2^2048) size search spaces, which is unsearchable in anyone's lifetime (and the reason no one is breaking the RSA keys directly). One of the foundational algorithms for quantum computers is Shore's algorithm (en.wikipedia.org/wiki/Shor%27s_algorithm), which in the best case can factor large numbers O(log 2^2048) which is roughly O(~600), a much more achievable complexity! Today's quantum computers are still too immature to factor large numbers, but as the technology improves, there may someday come a time when a quantum computer can brute force discover an RSA private key, which would be pure chaos for the internet because anyone with a quantum computer could pose as anyone else on the internet (and create their digital signatures, etc...), so cryptographers are busy at work today to develop asymmetric key ciphers that utilize one-way functions that are not amenable to any known quantum algorithms.
Another great discussion. Thanks Prof. Austin
Great explanation professor,
I do have one question regarding producing the factors of a number originally from which the number was produced, is it really possible? Even if quantum computers gave us the computation power for doing all this computation but is not our solution space is infinite possible solution, so how do we find the exact factors which were used to produce the number in first place? I don't have knowledge of working of these ciphers so kindly do correct me if I'm approaching it in a wrong way, thanks.
Thanks for the question! The factoring solution space is not infinite, but it is exponential (or worse) with the number of bits in the keys. Here's an almost 2000 year old algorithm that will factor any number into its prime factors, given enough time to compute: en.wikipedia.org/wiki/Sieve_of_Eratosthenes. The challenge with conventional computers is that the key size for RSA today is 2048 or 4096 bits, so you are looking at O(2^2048) size search spaces, which is unsearchable in anyone's lifetime (and the reason no one is breaking the RSA keys directly). One of the foundational algorithms for quantum computers is Shore's algorithm (en.wikipedia.org/wiki/Shor%27s_algorithm), which in the best case can factor large numbers O(log 2^2048) which is roughly O(~600), a much more achievable complexity! Today's quantum computers are still too immature to factor large numbers, but as the technology improves, there may someday come a time when a quantum computer can brute force discover an RSA private key, which would be pure chaos for the internet because anyone with a quantum computer could pose as anyone else on the internet (and create their digital signatures, etc...), so cryptographers are busy at work today to develop asymmetric key ciphers that utilize one-way functions that are not amenable to any known quantum algorithms.