>Fortunately, we donʼt have an algorithm that can factor such large numbers in reasonable time. Unfortunately, we also havenʼt proven it doesnʼt exist. Even more unfortunate is that there is a theoretical algorithm, called Shorʼs algorithm, that would be able to factor such a number in reasonable time on a quantum computer. Right now, quantum computers are far from practical, but it does appear that if someone in the future manages to build one thatʼs sufficiently large, RSA becomes ineffective.
Can anyone comment on how close we are to having Shor's algorithm on a quantum computer? Is feasible like the moon landing was in 1962 when Kennedy announced that "We choose to go to the Moon" (hard, but possible with a lot of money).
Or is it still something that we have no clue how to get to?
I think cryptanalysis as a discipline is not massively funded. All of the cryptography is only as strong as the collective failure of all human intelligence so far to break it.
Most people consider cryptography as a "solved" problem, but I don't think it is. I am sure if enough cryptologists try algorithmic methods and are well compensated for it, they will likely find algorithmic weaknesses (and invent new kinds of mathematics) that can bring down complexity of solving such schemes, even before we have real and functional Shor machines.
I guess massively is the relative word. But I will stand by the claim that we can discover/invent new mathematical methods that can aid in cryptanalysis, if not directly by cryptographers, then by some adjacent field.
I disagree. While it's true that early cryptocurrencies were based on well established cryptography, a lot of the modern (post 2017-ish) cryptocurrency tech involves cutting-edge cryptography. Especially with respect to post-quantum setups, zero-knowlege proofs, and new devices like adaptor signatures.
One reason for this is that cryptocurrencies are highly bandwidth-limited. Cryptography developed for other applications (such as voting systems, etc.) needs to be specialized to meet the size and computational restraints inherent to cryptocurrency design. Efficiency is everything.
Thanks for the link.
You can download this entire Handbook of Applied Cryptography for free [1].
Recently the authors also provided online course and video namely:
- Cryptography 101: Building Blocks (fundamental cryptographic primitives) [2]
- Cryptography 101: Real-World Deployments (PKI, TLS, Bluetooth, AWS, Signal) [3]
Other courses and video includes:
- The Mathematics of Lattice-Based Cryptography (introductory course)
- Kyber and Dilithium (standardized lattice-based cryptosystems)
- Hash-based signature schemes (LMS, XMSS, SPHINCS+)
- Error-Correcting Codes (linear, Hamming, Golay, cyclic, BCH, Reed-Solomon codes
[1] Handbook of Applied Cryptography:
https://cacr.uwaterloo.ca/hac/
[2] Crypto 101: Building Blocks:
https://cryptography101.ca/crypto101-building-blocks/
[3] Crypto 101: Real-World Deployments:
https://cryptography101.ca/crypto101-deployments/
>Fortunately, we donʼt have an algorithm that can factor such large numbers in reasonable time. Unfortunately, we also havenʼt proven it doesnʼt exist. Even more unfortunate is that there is a theoretical algorithm, called Shorʼs algorithm, that would be able to factor such a number in reasonable time on a quantum computer. Right now, quantum computers are far from practical, but it does appear that if someone in the future manages to build one thatʼs sufficiently large, RSA becomes ineffective.
Can anyone comment on how close we are to having Shor's algorithm on a quantum computer? Is feasible like the moon landing was in 1962 when Kennedy announced that "We choose to go to the Moon" (hard, but possible with a lot of money).
Or is it still something that we have no clue how to get to?
https://pqcrypto2025.iis.sinica.edu.tw/slides/Invited3.pdf
edit: video if you prefer - https://www.youtube.com/watch?v=nJxENYdsB6c
So it’s not like the moon landing since the horizon is much longer than a decade.
I think cryptanalysis as a discipline is not massively funded. All of the cryptography is only as strong as the collective failure of all human intelligence so far to break it.
Most people consider cryptography as a "solved" problem, but I don't think it is. I am sure if enough cryptologists try algorithmic methods and are well compensated for it, they will likely find algorithmic weaknesses (and invent new kinds of mathematics) that can bring down complexity of solving such schemes, even before we have real and functional Shor machines.
> I think cryptanalysis as a discipline is not massively funded.
Really? That would be a change.
I guess massively is the relative word. But I will stand by the claim that we can discover/invent new mathematical methods that can aid in cryptanalysis, if not directly by cryptographers, then by some adjacent field.
About to finish reading "Real World Cryptograhy" by David Wong, would highly recommend for anyone curious about this subject.
I don't remember if it links to it, but this pairs well with https://cryptopals.com/, which are practical examples of many of these theories.
this is the type of crypto i like
[flagged]
Blockchains/cryptocurrencies are actually quite simple, from a cryptographic POV.
I disagree. While it's true that early cryptocurrencies were based on well established cryptography, a lot of the modern (post 2017-ish) cryptocurrency tech involves cutting-edge cryptography. Especially with respect to post-quantum setups, zero-knowlege proofs, and new devices like adaptor signatures.
One reason for this is that cryptocurrencies are highly bandwidth-limited. Cryptography developed for other applications (such as voting systems, etc.) needs to be specialized to meet the size and computational restraints inherent to cryptocurrency design. Efficiency is everything.
You wouldn't happen to be a cryptobro yourself, would you?
This looks to be really well written. After 25 odd pages, I'm saying to myself, can't wait to read the whole book.
Looks great, thanks for sharing