Re: Secure permutation of a 1e8 element set



Thanks to everybody for the answers.

You simply will not find a secure permutiation, as you noted any permutation
could be simply stored in memory making it inherently weak. Based on that I
would choose RSA, it won't be secure,

Ok, I know it can't be secure in the usual sense.
But if I do any better, there would be no working database anymore.
RSA would be fine, but very slow, wouldn't it?

but it is not easy to implement efficiently, due to the computation of a
probability distribution with enough precision. In my own tests, I got
to the speed of about 0.3s per encryption, which is pathetic.

Quite unusable, but interesting reading.

I think you have to decide on one maximum. If it does not reallymatter then
choose some RSA number and use his suggestion.

I'like to be able to encrypt any customer number I get,
and it must fit into the range.

You could always cook up a
Feistel cypher based on digits, not bits (use base 10 modulus addition as
the combiner).

Yes, I've got already a plan for it, maybe the addition, maybe some
lookup table with a precomputed permutation of 0..9 in each row.
Additionaly I could permute the digits.

There is a well known trick used in Schroeppel's Hasty Pudding Cipher
for permuting arbitrary integer ranges. The basic idea is that
you map to within the nearest higher power of two using bit twiddling,
and if the result falls outside the desired range, iterate the map
til you get within range. Since the map has a unique inverse you
can get the original number back by iterating the inverse map, again
until the result is within range.

A really nice idea. On the average I need to iterate less than twice,
right?

I posted some code here a while back for permuting 10 digit SSN's but
you should be able to adapt it straightforwardly to 8 digit numbers:

That's really easy, thank you.

The table would only be about 380MB.

There's an account number with two more digits.

That's probably a little unfair to permutations that one can store.
A arbitary permutation of 1e8 numbers is equivelent to a key size
of about 2513272986 bits, if you count the number of possible
mappings. If I gave you the values of (say) P[0], ... p[999], you
couldn't say much about p[1000], other than it wasn't any of the
previous values I'd given you.

Yes, this is exactly what I want.

OTOH, if you tried to use it as a more general block cipher, I guess
that might not be a very good idea because the block size would be
a bit small.

I'm really not going to do anything like this.

Once again, thanks to everybody.
.