Alex Rivera | Logout

Algorithm for incrementing a String in a non-obvious manner

Asked 2011-07-06T13:38:24.500
17

I want to create random-looking 5 or 6 character alpha-numeric strings, something like:

Vg78KY

Creating (pseudo-)random Strings has been answered, but I am wondering if there is an algorithm for incrementing a String in a non-obvious manner. A simple increment of the above String might yield:

Vg78KZ

But I don't want this next String to be guessable, I want it to look completely different. Of course, successive increments should not yield a previous result as each should be unique.

Any thoughts on how to achieve this much appreciated!

Thanks

java string algorithm random
Edit
Report

2 Answers

27

An easy approach that avoids the need for lookup tables would be:

  • Increment an integer normally
  • Permute the bits in a non-obvious way (a fixed permutation is probably fine, but if you want something more sophisticated you could use something like George Marsaglia's XORShift algorithm that produces a psuedorandom sequence of integers that only repeats after a very long cycle)
  • Convert to Base64 encoded strings
answered 2011-07-06T13:48:02.520
3

If we assume there must be a 1:1 mapping from "sequence number" to "random-looking string", then the truncated hash approach will not work as there is no guarantee that the truncated hash won't be subject to collisions.

I'd do something like this:

  • Take the next integer in sequence.
  • Xor with a fixed number.
  • Permute the bits.
  • Encode the number using Base64, Base36, or whatever.

Note that this will be subject to easy analysis by a determined attacker with access to a sufficiently large set of sequence numbers.

answered 2011-07-06T13:53:22.373

Your Answer