Is Encryption secure? Or just need to have a perfect guess !
In Today’s scenario data security is one of the key aspect for every one. And not anyone here is unaware of how it is being achieved at digital level to secure data.
When the data security is concerned the first method is come into mind is “Encryption-Decryption”.The most popular Encryption method in recent scene is RSA(Rivest–Shamir–Adleman) which is mainly concerned with factorization of very big non-prime number, and the key idea of it is to wrap/scrumble the data with the factors of that non-prime number and make the key available to recipient so he/she can efficiently decrypt it.
Here we are manily focused on how the Encryption is being penetrated so we yet to discuss about RSA in more deep, but you can check out that by link given below.
Now our main goal is to find the way that how to penetrate encryption. sounds like more hacker type stuff but it’s not that easy because the numbers used to encrypt data is enormously huge and unlike multiplication which intern faster than factorization , factorization of such huge number is very much difficult for even some super computers too.just for an example…
To find the factors of this number on computer it nearly takes 2000 years. And here we are concerned with co-prime(Relatively prime) factors of this number because not every factors are used for the encryption.In recent scene our best method is to guess the random number which can be factor of it, if it isn’t then try again and again and again…..
But encrypting the data doesn’t mean to have unbreakable security it’s just to make the data harder to access ,but with non-Quantum computers it takes non polynomial time to find factors.And it’s still thrieves us from thinking whether the ‘NP’(Non determinastic Polynomial time problem) is ‘P’ (Polynomial time problem)or not. You can get more into this problem by reading my article on NP vs. P problem by clicking on the link given below.
What makes NP vs. P problem “MILLENNIUM!”
Encryption is like to lock your house doesn’t mean to make it theaftproof but make it harder to be theaft.
The key idea behind the penetration of encryption is to make good guess of co-prime factors that can intern into find the data which is encrypted. So here Shor’s algorithm come into picture.
Shor’s Algorithm
As we know to find co-prime factors of huge non-prime number takes non polynomial time but it’s not the case for Quantum computers. Quantum computers can easily penetrate through encryption due to their intrinsic properties like Superposition and Interference. Peter Shor took the advantage of this properties and made an efficient algorithm that turn your creepy random guess into better guess for factors.
There is no intrinsically Quantum mechanical about this algorithm you can infact run the version of this algorithm in your computer but perhaps as part of the process it takes enormous time to convert your guess into better one but on the other hand this key step happens to be ridiculously fast on Quantum computer.
So our task is to know how Shor’s algorithm turns our creepy guess into better guess which is more over mathematical stuff and how Quantum computers do it fast where the physics come into picture.
Shor's algorithm consists of two parts:
- A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding.
- A quantum algorithm to solve the order-finding problem.
It all starts with the interger N which we want to factorize into it’s factors so the best way to guess some integer (1<g<N) such that it’s factor of it but it’s not compulsory to guess g which is pure factor of N but instead you can guess the integer which shares factor with N (gcd(g,N)), thanks to Euclide who has found the algorithm to find share factor.
So unlikely the random guess, just make guess of an integer which has share factors with N, but for very large numbers it’s difficult to guess that number which has shared factors so now shor made very clever move by using mathematical fact that if two numbers does’nt share factors than, some p times multiple of one number with itself will be some multiple of other number + 1.
So it’s not worry to guess a pure factor or a number which shares factor with N we could guess any number and make better guess from it by finding some multiple of it to have some multiple of N + 1 as shown in figure.so cleverly we have found the N or multiple of N is something into something form which interns mean to have factors of N ofcourse since we are dealing with multiple of N it indeed means that the factors we got also multiple of factors rather than factors itself but that’s not problem as we can find share factors using Euclide’s algorithm.so we are done but wait is this the shor’s algorithm then why don’t we use it? Where is the Quantum mechanics?
Well indeed this algorithm has three problems with it.
- If one the factor among (g^(p/2)±1) is multiple of N then other one is multiple of m then it never turns out to be use full for us.
- If the order P is odd number then both factors gives us fractional numbers and we don’t get the actual factors of N. But hopefully there is at least 37.5% chance on any initial guess that P leads to factors of N so it’s worth repeating that less than 10 chance we can reach to factors of N.
- Third problem is bigger one that
How to find P?
Remember to convert creepy guess into good guess we need to find some p times the multiple of our initial guess,but how to find it because using conventional method it can take more time than to find direct factors of N so how to speed up this.Well here the Quantum computers come into picture.
Because unlike conventional computers Quantum computers can simultaneously calculate a bunch of numbers with using superpositioning phenomena, But you get only one output at the end of the procedure according to the probability.
So the key idea behind is to set all possible guess in a superposition such that after computation all the non P answers distructively interfere with each other and cancle out.
However to set up all possible superpositioning inputs to get answer with all other wrong answers get distructively interfer with each other is somewhat difficult task but that’s what the shor’s algorithm does in this case.
Shor’s algorithm takes the number x as input to the quantum computer and takes to the power of our guess g. And then it checks how much it’s bigger than multiple of N and tracks the record of both x and the reminder(r) we that we got by checking.
So far it is not different from conventional computer but as it’s Quantum computer it can simultaneously takes all possible inputs and keep track of all inputs and their reminder with some multiple of N in form of superposition. Now as we know that direct measurement of superposition state lead us to have a single outcome which is not different then conventional one so here we have to take clever step by only measuring the superpositioned states that are greater than or less than some reminder r and by doing indirect measurements of this type we got advantage of superposition property and we just endup with having only those outcome which intern in range of specified reminder without disturbing superposition state.
Actually measuring related terms(Indirect measurement) like the states which are in superposition that having some greater or lesser property(reminder) then specified reminder rather than measuring the direct required reminder is key step of shor’s algorithm or we can say it’s crucks of this algorithm. And as we have said earlier that this algorithm doesn’t have any intrinsic Quantum mechanics then how it’s the key step as it follows the Quantum rules, actually we have used Quantum principles as a tool to achieve very simple but most impactful mathematical observation shown as below.
As shown in figure P is resposible for turn our guess into some multiple of N + 1 and so far the mathematical observation is concerned we can easily say that if any other power to our guess holding reminder r then adding any multiple of P with that power and raised to our guess can still answers equal to some other multiple say m2 of N and reminder r remains the same. This key step however helps us to set the possible guesses for order P to arrange in such way that they stays in superposition with remarkable way that all the wrong answers distructively interferes with each other.
Now the order P of our creepy guess has some kind of repeating property that we can say by observing the mathematical observation that we just discussed and this property you can’t identify by adding just one power to the P but it is the structural relation of adding or substracting one or more power to P and make sequence and their by you can observe this property.Infact in this case Quantum superpositioning helps us a lot as by just observing some amount greater or lesser than the specified reminder so as we left with only that amount of reminder with the superposition that is sequence of the states which has P as their period.
Now we are left with the states which are repeating with frequency of 1/P.
Now we just have to find frequency of this superposition state and we know so far that the best tool to find the frequencies of things is Fourier transformation. Quantum mechanics also have this type of tool called Quantum Fourier Transform(QFT). Now as we are now only left with the states that has common frequency 1/P , QFT operates on these states such way that all other repeating frequency (higher frequency) cancelled out and we are only left with the single harmonic frequency which happens to be 1/P.
Now Question may arise that how QFT performs this magic like by only taking superposition states repeating with frequency 1/P and canclled out all other repeating frequency without disturbing by measurement? Well idea behind this is far more simple unlike the normal fourier transform if we give any frequency to QFT it converts it into all of it’s superposition states but not any superposition instead all the states are weighted with different amounts that roughly look like sine wave, so as you give higher frequency as input it gives superposition of states that interns into sine wave with higher frequency.And as the idea of interference suggests, if we give more than one input frequencies than the resultant superpositioning sine waves interferers with each and cancle out some frequencies and only left with those frequencies which are constructively interfers means the frequencies which are same in phase.
Now you can connect that with our give super positioned input and you can understand how our given superpositioned input of frequency 1/P can be cancled out by distructive interference of all other existing frequencies after QFT and output turns into single frequency 1/P.
So we are now just left with P and finally we can rais it to our guess g and add or subtract one from it (g^(P/2)±1) to get factors that has share factors with N as long as P is even and so by using Euclid’s algorithm we can find the actual factors and can able to break the Encryption to get the massage.ooghh!!!😅
As much as complicated it sounds but on the other hand getting help of some intrinsic properties of Quantum computers we can do this ridiculously fast.
And as much as complicated this algorithm in practice as we have discussed tons of details but on the other hand it’s so surprising to me that how simple the Core structure of shor’s algorithm is….
- Guess g that can be direct or share factors with N.
- Turn problem of guessing factor in guessing order P of g.
- And (g^(p/2)±1) can be better guess.
Now you might be worried about the current development of quantum computer as it turns out to be the security issues. But not to worry about that now because current quantum computers can’t solve the order-problem for non prime numbers that are currently used because it requires the space complexity in order of…
So not to worry about that at least now.
I’ve tried my best way to simplify the working of this algorithm.but if you still not get the point then checkout this amazing video from which i’ve taken the reference.link is given below…
Quantum Computers break through security!/@Minute_Physics
If you want to get into more detail description of Quantum procedure of superpositioning to turn our guess into better one then go through all these formulas…
And always, Thanks for reading😊
