## Public/Private Key Encryption

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

German Sausage
3 of 5
Posts: 2933
Joined: Mon Jan 01, 2007 9:45 am UTC

### Public/Private Key Encryption

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.

<bakemaster> Only German Sausage can prevent forest fires
<felstaff> Hype is like a giant disappointment ray aimed squarely at the finished article.
<watson> Treat me like a criminal, Holmes!
TMT4L

zenten
Posts: 3799
Joined: Fri Jun 22, 2007 7:42 am UTC

### Re: Public/Private Key Encryption

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.

It doesn't actually use this method from my understanding, but have you learned about matrix multiplication yet?

German Sausage
3 of 5
Posts: 2933
Joined: Mon Jan 01, 2007 9:45 am UTC
i vaguely recall, but it was a few years ago now.

but you could do matix division, yes?
<bakemaster> Only German Sausage can prevent forest fires
<felstaff> Hype is like a giant disappointment ray aimed squarely at the finished article.
<watson> Treat me like a criminal, Holmes!
TMT4L

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London
German Sausage wrote:i vaguely recall, but it was a few years ago now.

but you could do matix division, yes?

Division only works if you have a multiplicative inverse for your matrix, which is not necessarily the case.

As far as why you can't just reverse the process, you can, it's just overwhelmingly hard. For example, RSA encryption. The (simplified) idea is that you pick 2 large prime numbers, p and q. You use both numbers to encrypt and decrypt, but the key is that you only need the product pq to encrypt, and not p and q seperately. This means that you reveal pq as your public key, and keep p and q as your private key. If p and q are large enough, it is very very hard to find them from pq. The security relies on the fact that you pick p and q large enough to be effectively immune from brute force factorisation by powerful computers.

The linked Wikipedia article contains a more mathematical description.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5957
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney
German Sausage wrote:i vaguely recall, but it was a few years ago now.

but you could do matix division, yes?

You can only divide by a matrix sometimes. Its got nothing to do with RSA encryption though.

In RSA encryption I give you two numbers. The first is the product of two prime numbers. Lets call it M (for massive). I also give you a number N, between 0 and M. When you want to send a message, you turn it into a number (or a bunch of numbers depending on how big the signal is), call it S, and then you multiply the number by N and you send the remainder of N*S divided by M.

Now, when I get your message, I multiply it by a special number, P (for private). The thing is that N*P leaves a remainder of 1 when you divide it by M, and by the magic of modular arithmetic, this means that N*S*P will leave a remainder of N when divided by M. We say that P is the inverse of N, as usual.

Now, theoretically, you could work out P all by yourself. You could, for instance, multiply N by all the numbers between 0 and M; very costly. If you factorise M, you can then get the inverse of N pretty quickly using some tricks, and that's how you actually generate the code. You start with the factorisation, and then you can make the inverse pretty easily.

But to get the factorisation is again a gigantically costly opperation. Not as bad as trying every possible number, but still pretty bad.

The term for a function that is hard, but not impossible, to undo is a trapdoor function and mathematicians right now are probably working on the problem of finding new ones and breaking old ones. Just about every cryptographic system is built around trapdoor functions. They are where its at as far as cryptography goes.

edit: Dammit, beaten to it. And sorry, my write up there is a bit buggy. Read the WP page. But the basic idea is what you read above.

GBog
Posts: 114
Joined: Fri Jun 01, 2007 4:57 pm UTC
actually, jestingrabbit, that would not be a very secure public key algorithm. And the RSA doesn't work that way, either.

In RSA, you have, as you say, an M which is a product of two large primes.

You den have to choose an encryption key e, and a decryption key d, such that the product ed leaves a remainder of 1 when divided by phi(M), where phi is Euler's totient function.

The 'magic' of the RSA is that n^(ed) leaves a remainder of n when divided by M (given that n < M and n is not a multiple of either of the two primes)

Now, for a mathematical explanation, I would first have to know what level you are on, German Sausage. Do you know group theory? (Saves a lot of time, but isn't necessary.) Failing that, do you know modular arithmetic?

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5957
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney
GBog wrote:actually, jestingrabbit, that would not be a very secure public key algorithm. And the RSA doesn't work that way, either.

The problem with it is that N*S might have a factor of one of the primes. You could tiptoe around it using padding, but its likely you could reverse engineer the padding to get the factorisation. RSA is cleaner because it uses powers, which don't have that problem.

Edit: hang on, RSA does have this problem!!

Edit2: No, no it doesn't.
Last edited by jestingrabbit on Wed Sep 12, 2007 8:12 pm UTC, edited 2 times in total.

Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC
Here is an operation which is hard to undo (relies on the subset sum problem: http://en.wikipedia.org/wiki/Subset_sum )

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.
Don't pay attention to this signature, it's contradictory.

Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC
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)

Actually, the operation is O(1) (just append a 0 to the array), and you can't be certain that the reverse operation is exponential, but you can say that (probably) no one is aware of a polynomial time algorithm for it, and it's unlikely one will be found.

But yes, this is a good example. The inverse of a function can be harder to compute than the function itself. RSA relies on, IIRC, that finding large primes and multiplying integers is fast, but factorising large numbers is slow (assumedly).

Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:
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).

Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC
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...
Don't pay attention to this signature, it's contradictory.

German Sausage
3 of 5
Posts: 2933
Joined: Mon Jan 01, 2007 9:45 am UTC
Thanks Guys!
i'm not sure whether i completely understand it, but it makes less non-sense, which is always a good thing.
<bakemaster> Only German Sausage can prevent forest fires
<felstaff> Hype is like a giant disappointment ray aimed squarely at the finished article.
<watson> Treat me like a criminal, Holmes!
TMT4L

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London
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...

It seems that that might not work, because any non-unique property would require you to check yourself that none of the other possible subsets could be mistaken for the original, and any unique property may open the reverse operation to an easier method of attack.