Rock Paper Scissor

I guess if you insist I could go into a method to solve one of the greatest problems facing mankind today, playing Rock Paper Scissors by email.  This is something I thought about a while ago, when I was reading lots of crypto books.  It's deff possible to send your choice in a way that locks you into what it is, but at the same time doesn't reveal what it is until you give additional information.  The challenge was for me to come up with an actual method of doing it.

I'm not sure how much you know about public key encryption, or NP complete problems, but modern public key encryption works by doing something that is very easy to do in one direction, but very hard in the other.  The most common method used today is to generate a pair of large prime numbers, then multiply them together.  The resulting number is huge almost prime number (almost prime because it is made up of two primes).  Figuring out what two numbers make it up (factoring) though is very hard.  However, if you reveal one of the numbers then you can easily figure out what the other is.

So back to RPS.  I know I could encrypt my choice using public key encryption, and send it to you, but like I said, I wanted a method that I could do myself.  So my method would work as follows.  I generate a list of large primes, each of which takes about a minute or so to come up with.  I then pick two and multiply them together, then send the result number to you.  My choice is stored in one of the numbers.  The format for storing it could be this.  I'm pretty sure you are familiar with the concept of adding a number's digits, then adding that number's digits again and again until you have a single digit number (ex 94184, 9 + 4 + 1 + 8 + 4 = 26, 2 + 6 = 8).  You do that with the larger number, and then you take the result and divide it mod 3, as in you divide by 3 and then take the remainder, if it's 0 though it's invalid (0 mod 3 is 0, but for our game it's an invalid choice).  So if the digits add to 7, then that mod 3 would be 1.  They would all be either 0, 1, or 2, 3 each for each choice, makes 9 digits (and you ignore 0).  0=R, 1=P, 2=S.

Here's an example using not so large primes.  I send you my choice as 9030233.  You then send your choice back as plain text, say 'rock'.  Now I reveal that my primes that make up that choice are: 3391 and 2663.  You can verify that they are in fact prime, and that they do in fact multiply to give the larger number.  Both of those will be rather quick to check.  Using the above format, 3391 is the larger, and thus you add it's digits 3 + 3 + 9 + 1 = 16, 1 + 6 = 7.  7 mod 3 is 1, 1 = Paper, so I win.  Actually upon doing this I realize it would probably be better to add all the digits of both primes together.  I would need someone that was better at math to verify that giving you the results of the sum of the digits of a number (or both numbers) doesn't give you any information about the product of those numbers.

Now let's analyze how this worked.  The key is that I have to send you some sort of info that locks me into a choice, but doesn't reveal that choice to you.  It should be clear that sending you the product of the two primes does in fact tell you what numbers I used.  The question is whether you could have figured out my choice before I revealed the key (the composite primes). To do that you'd need to factor a large almost prime number.  Factoring the above number wouldn't be that hard, but it would be much harder than coming up with the 4 digit primes that make it up.  For that scale imagine we had to do this all by hand, hundreds of years ago, (playing by paper mail). Coming up with a 4 digit prime would be hard, but not that hard.  However, factoring a 7 digit number would take much longer.  With computers we can generate much larger primes, and as the size of the primes increase the length of time to factor a number that is the product of two of them grows even faster.  Thus in a real life example I'd send a number hundreds of digits long, which would take years to factor.  It would only take a few seconds or minutes though, to confirm that the composite primes are in fact prime, or to generate them in the first place.

I was going to end with an actual number, but upon trying this I realized that any prime big enough to make factoring difficult would be absurdly large (think of that binder), and the product of two of them would be even larger.  Thus I'd have to send several mbytes of text to you.  I suppose I could get by with using a prime that was only a few hundred digits long, but that would probably be factorable by some specialty program.  Plus it'd still be very difficult to add all the digits.  I could write a program to do all this stuff, but it's probably not worth it just for a closing line in this email.