Alex Rivera | Logout

Rot13 for numbers

Asked 2009-04-30T21:16:51.410
13

EDIT: Now a Major Motion Blog Post at http://messymatters.com/sealedbids

The idea of rot13 is to obscure text, for example to prevent spoilers. It's not meant to be cryptographically secure but to simply make sure that only people who are sure they want to read it will read it.

I'd like to do something similar for numbers, for an application involving sealed bids. Roughly I want to send someone my number and trust them to pick their own number, uninfluenced by mine, but then they should be able to reveal mine (purely client-side) when they're ready. They should not require further input from me or any third party.

(Added: Note the assumption that the recipient is being trusted not to cheat.)

It's not as simple as rot13 because certain numbers, like 1 and 2, will recur often enough that you might remember that, say, 34.2 is really 1.

Here's what I'm looking for specifically:

A function seal() that maps a real number to a real number (or a string). It should not be deterministic -- seal(7) should not map to the same thing every time. But the corresponding function unseal() should be deterministic -- unseal(seal(x)) should equal x for all x. I don't want seal or unseal to call any webservices or even get the system time (because I don't want to assume synchronized clocks). (Added: It's fine to assume that all bids will be less than some maximum, known to everyone, say a million.)

Sanity check:

> seal(7)
482.2382   # some random-seeming number or string.
> seal(7)
71.9217    # a completely different random-seeming number or string.
> unseal(seal(7))
7          # we always recover the original number by unsealing.
language-agnostic math encryption function
Edit
Report

4 Answers

2

Are you aware that you need a larger 'sealed' set of numbers than your original, if you want that to work?

So you need to restrict your real numbers somehow, or store extra info that you don't show.

answered 2009-04-30T21:24:23.950
2

One simple way is to write a message like:

"my bid is: $14.23: aduigfurjwjnfdjfugfojdjkdskdfdhfddfuiodrnfnghfifyis"

All that junk is randomly-generated, and different every time.

Send the other person the SHA256 hash of the message. Have them send you the hash of their bid. Then, once you both have the hashes, send the full message, and confirm that their bid corresponds to the hash they gave you.

This gives rather stronger guarantees than you need - it's actually not possible from them to work out your bid before you send them your full message. However, there is no unseal() function as you describe.

This simple scheme has various weaknesses that a full zero-knowledge scheme would not have. For example, if they fake you out by sending you a random number instead of a hash, then they can work out your bid without revealing their own. But you didn't ask for bullet-proof. This prevents both accidental and (I think) undetectable cheating, and uses only a commonly-available command line utility, plus a random number generator (dice will do).

If, as you say, you want them to be able to recover your bid without any further input from you, and you are willing to trust them only to do it after posting their bid, then just encrypt using any old symmetric cipher (gpg --symmetric, perhaps) and the key, "rot13". This will prevent accidental cheating, but allow undetectable cheating.

answered 2009-04-30T21:25:31.870
1

Pseudo code:

encode:

value = 2000
key = random(0..255); // our key is only 2 bytes

// 'sealing it'
value = value XOR 2000;

// add key
sealed = (value << 16) | key

decode:

key = sealed & 0xFF
unsealed = key XOR (sealed >> 16)

Would that work?

answered 2009-05-01T03:27:24.357
0

You could set a different base (like 16, 17, 18, etc.) and keep track of which base you've "sealed" the bid with...

Of course, this presumes large numbers (> the base you're using, at least). If they were decimal, you could drop the point (for example, 27.04 becomes 2704, which you then translate to base 29...)

You'd probably want to use base 17 to 36 (only because some people might recognize hex and be able to translate it in their head...)

This way, you would have numbers like G4 or Z3 or KW (depending on the numbers you're sealing)...

answered 2009-04-30T21:23:46.977

Your Answer