CODEWITHSUNDEEP
xor
Chia
Chia

Reputation: 122

XOR to switch between two numbers, how about mod?

I want to find an alternative index of an item, and the item can be switched back to its original index. For now, the solution is not perfect -

Say an item's tag is in index1 originally, and I want to move it to index2

So index2 = (index1 ^ tag) % max_index

And if I want to move it back to index1

Just index1 = (index2 ^ tag) % max_index

The above equality only holds when max_index is the power of 2.

ex:

( 15 ^ 123 ) % 64 == 52

( 52 ^ 123 ) % 64 == 15

but

( 15 ^ 123 ) % 60 == 56

( 56 ^ 123 ) % 60 == 7 (!= 15)

I wonder if there is other math operations that allows max_index to be any number.

EDIT:

I need to use the same operation to achieve switching between two index.

My scenario is - I have a hash table that each bucket can store at most 4 items, and it stores only an item's fingerprint (say 8 bit). If the bucket is full, I need to move an item's fingerprint to its alternative position without knowing its original representation. And once moved to the alternative position, the fingerprint can be moved back to its original position using the same operation as the previous one (Because I don't know if a fingerprint's current position is original or alternative).

Now - index = (index1 ^ Hash(tag)) % max_index

Upvotes: 0

Views: 128

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 153162

Addition and subtraction work fine; if

index2 = (index1 + tag) % max_index

then

index1 = (index2 - tag) % max_index

In some languages, % is implemented strangely for negative numbers; if this is a concern for you, you may use

index1 = (index2 + max_index - tag) % max_index

to avoid issues.

After some shower thinking, I propose the following protocol. First choose your favorite symmetric block cipher; constraints on the cipher are:

  • plaintext space must have at least max_index elements
  • ciphertext space should not be too much bigger than max_index elements
  • key space should probably be larger than your tag space (not a hard requirement)

Then you follow the following procedure to swap indices:

do { index = encrypt(tag, index); } while(index >= max_index);
do { index = index ^ 1;           } while(index >= max_index);
do { index = decrypt(tag, index); } while(index >= max_index);

If the size of the ciphertext space is c*max_index, this will take c encryptions and c decryptions in expectation. The index you get out the other end will be the same as it started with low probability -- it can only happen when either the index encrypts to max_index-1 (and max_index is odd) or the encryption maps two adjacent values to two adjacent values.

Upvotes: 1

Related Questions