Cryptography in Q# - Is it possible?

Question

Title says it all.

Since Quantum Computers are said to be the next big thing, I figured the speed at which these systems operate on should be enough to decrypt files/applications in a 'Brute Force' manner. Is it possible? When will it be possible?

Answer 1

Quantum computers operate differently from classical computers, rather than faster or slower. For some problems they're much faster than the best known algorithms, while for others they'd be slower if they would work at all.

For decrypting, there are quantum algorithms for attacking some specific ciphers. Probably the best known is Shor's Algorithm, which on a large enough quantum computer would allow you to factor large numbers efficiently, thus breaking RSA. Breaking RSA would require many thousands of high-quality qubits, and so is not something that's going to be available in the next few years. Longer term, I myself wouldn't try to guess when such a quantum computer will be available, although others may have more confidence.

There are quantum attacks on other ciphers as well, including elliptic curve cryptography. The good news is that post-quantum cryptography is an active field of research, and there are some promising developments already. Also, most symmetric ciphers in use today are quantum-resistant; while brute force search time on a quantum computer would in theory scale with the square root of the number of possible keys, doubling the key size addresses this neatly.

There are good resources for this on Wikipedia: https://en.wikipedia.org/wiki/Shor%27s_algorithm and https://en.wikipedia.org/wiki/Post-quantum_cryptography. The Microsoft Quantum samples repository includes a Q# implementation of Shor's algorithm.