Thursday, March 19, 2015

It's a secret (20)

So the question is - given that there is a specific mathematical relationship between n, x and y, if you know n and y (and anyone can find this out - it's your public key) can you work out what x is?  Because if you can then obviously the system is insecure. And the surprising answer is - yes you can, and it isn't even that complicated a process.  BUT to do so, you need to find out what p and q (which you will remember are the two prime numbers we started with) are, and this involves factorising n.  Now current thinking (it tends to change as computers get more powerful) is that your "n" number should be at least some 600 digits long.  Now that's a BIG number. Something like this - 
25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357
 - and you now have to find the two numbers which were multiplied together to produce that number.  Because they were prime numbers, there is only one answer. How long will this take you?  Well it's been estimated that if you could hook up all the computing power in the world and have it working 24/7 on this problem to the exclusion of everything else, you might get the answer in around 2000 years.  Yes, I did say 2000 years - which is why it's only an estimate.  Nobody's ever tried it or would dream of trying it, and therein lies the security of the system.  Have we reached the end of the story?  Not quite...

No comments: