# Tiny Bytes: Breaking Encryption

**Published by:** [ldnovak](https://paragraph.com/@ldnovak/)
**Published on:** 2022-07-19
**URL:** https://paragraph.com/@ldnovak/tiny-bytes-breaking-encryption

## Content

Hey There, Following up from yesterday’s post, I wanted to jump into pk, sk encryption. Why agreeing to the same shared secret and standard encryption breaks down. The tldr is quantum computers make factoring large numbers easy. For classical computers this is hard and the basis of lots of encryption. This isn’t a very satisfying answer so I wanted to dig up more.Shor’s algorithmI learned what this was in school but it flew over my head. Luckily MinutePhysics has a great video explaining it at a high level. tldr:We guess are random number g and do quantum stuff to generate a better guess p. p has a much higher chance (~37.5%) to be a number that can help us factor N.How do we find the better guess? We find it’s periodg^period mod N = 1If g and N are coprime (largest common factor is 1)Euler-Fermat Theoremg^p = m*N+1→ (g^(p/2)+1)(g^(p/2)-1)=m*N3/8s of the time (g^(p/2)+1) or (g^(p/2)-1) is N AND p is evenShor’s algorithm helps us find the periodHow? (I’m not quite sure, it’s confusing)so g^(x+ip) mod N = r for all integers ig^(x+ip) mod N → g^x * g^ip mod N(wN+r) (mN+1) = wmNN+wN+rmN+r= number*N + r = r mod NThis is where quantum computers get weirdWe make a quantum circuit that takes a guess g and returns the remainder r of g (g^r mod N)| 1, g^1 mod N>, |2 , g^2 mod N> …we measure the remainder output and get rBy superposition and quantum magic this means everything we measure from here on out will have a remainder of r| x, g^x mod N = r>, |y, g^y mod N =r> ...We know that x, y, … differ by some factor of pg^x * g^ip = g^yWe use a quantum fourier transformation to find pfourier transformations find underlying wave relationsthere’s good quantum versions of fourier and inverse fourier that are used in everything because everything can be broken down into a waveIf p is even, we check if g^(p/2)+/-1 is N. If not repeat. I spent much longer trying to understand Shor’s than I thought I would. I wanted to spend more time trying to understand why the factoring of large numbers breaks key generation / pk sk (more than it factors large numbers and RSA). I’ll do that another day. I’ll probably have to understand what an elliptical curve is. Bye, Lucas update: wanted to include shor’s algorithm has a ~O(log^3 n) quantum cost https://quantumcomputing.stackexchange.com/questions/16421/classical-algorithm-with-complexity-similar-to-shors-discovered-are-there-more

## Publication Information

- [ldnovak](https://paragraph.com/@ldnovak/): Publication homepage
- [All Posts](https://paragraph.com/@ldnovak/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@ldnovak): Subscribe to updates