# Re: Secure permutation of a 1e8 element set

*From*: Maaartin <grajcar1@xxxxxxxxx>*Date*: Tue, 28 Oct 2008 11:32:22 -0700 (PDT)

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.

.

**References**:**Secure permutation of a 1e8 element set***From:*Maaartin

**Re: Secure permutation of a 1e8 element set***From:*Joseph Ashwood

**Re: Secure permutation of a 1e8 element set***From:*David Malone

- Prev by Date:
**Re: ADVERT: C12** - Next by Date:
**Re: Effect of non random nonce in AES counter mode.** - Previous by thread:
**Re: Secure permutation of a 1e8 element set** - Next by thread:
**Re: Secure permutation of a 1e8 element set** - Index(es):