Moderators: gmalivuk, Prelates, Moderators General
German Sausage wrote:This may seem like a pretty silly question, but the more I think about it the less sense it makes.
How does it work?
According to my understanding of maths, any process you undergo can be pretty simply undone by doing the opposite.
For example, if 2+8=10, then 10-8=2 should follow logically.
But this seems to not be the case with modern encryption systems. Surely if a message (2) was encoded with a public key (8 ), the encrypted message (10) should be able to be decrypted with the same public key. Now, I assume that the maths is slightly more complex than arithmetic, but maths the way I understand it cannot explain this.
I know that this example represents a symmetrical key system, but i can't for the life of me (40 minutes or so of asking wikipedia and howstuffworks, as well as the week it took me to read Cryptonomicon mulling over it) find a mathematical explanation for it. I understand the 'Alice uses one key to lock the package and Bob uses another one to unlock the package' thing, but while I can see the mechanical metaphor, but fail to translate it across into maths. And the willing suspension of disbelief can only see me so far.
Please help me, this is slowly sending me out of my mind.
German Sausage wrote:i vaguely recall, but it was a few years ago now.
but you could do matix division, yes?
German Sausage wrote:i vaguely recall, but it was a few years ago now.
but you could do matix division, yes?
GBog wrote:actually, jestingrabbit, that would not be a very secure public key algorithm. And the RSA doesn't work that way, either.
Alky wrote:Here is an operation which is hard to undo (relies on the subset sum problem: http://en.wikipedia.org/wiki/Subset_sum )
Operation: ... Time: O(n)
Reverse Operation: ... Time: O(4^n)
Alky wrote:Here is an operation which is hard to undo...
Operation:
Given an array of size n in which none of the subsets add up to 0, create a array which does contain such a subset by appending up to n numbers with values which do sum to 0 and shuffle the array. Time: O(n)
Reverse Operation:
Given an array of size 2n in which there is a subset that adds up to 0, remove subsets which add up to 0 until there are none left. Time: O(4^n)
Notice that I don't even require that the reverse operation return the original array, making it easier than it needs to be.
Cosmologicon wrote:Alky wrote:Here is an operation which is hard to undo...
Operation:
Given an array of size n in which none of the subsets add up to 0, create a array which does contain such a subset by appending up to n numbers with values which do sum to 0 and shuffle the array. Time: O(n)
Reverse Operation:
Given an array of size 2n in which there is a subset that adds up to 0, remove subsets which add up to 0 until there are none left. Time: O(4^n)
Notice that I don't even require that the reverse operation return the original array, making it easier than it needs to be.
How would you rephrase it so that the reverse operation is a true inverse? You can't just replace the requirement of finding some subset with finding the original subset, because it might not be unique, right? The only ways I can think of that would work would also make the operation harder than O(n).
Alky wrote:Cosmologicon wrote:Alky wrote:Here is an operation which is hard to undo...
Operation:
Given an array of size n in which none of the subsets add up to 0, create a array which does contain such a subset by appending up to n numbers with values which do sum to 0 and shuffle the array. Time: O(n)
Reverse Operation:
Given an array of size 2n in which there is a subset that adds up to 0, remove subsets which add up to 0 until there are none left. Time: O(4^n)
Notice that I don't even require that the reverse operation return the original array, making it easier than it needs to be.
How would you rephrase it so that the reverse operation is a true inverse? You can't just replace the requirement of finding some subset with finding the original subset, because it might not be unique, right? The only ways I can think of that would work would also make the operation harder than O(n).
Maybe if you included additional information about the set, such as the squared sum? Then they would need to (in the worst case) find all the solutions and check if the squared sum matches. Surely there is some property that would work...
Users browsing this forum: f5r5e5d and 6 guests