Re: Random Unique alphanumeric generator using Java
On Tue, 7 Dec 2010, Martin Gregorie wrote:
I'm no crypto geek: is there a problem in finding a secure system that
can generate a reasonably short ticket ID given that most of the popular
ones (SHA, DES, etc.) pad the plaintext to a minimum length before
encrypting it?
Yes, but it can be solved using the Hasty Pudding Trick. Look it up.
Although if you do look it up, you mostly find posts mentioning it and
saying 'look it up'. So see the section 'Encrypting Numbers and Dates' in:
http://richard.schroeppel.name:8015/hpc/hpc-spec
First, you need a cipher with a small block size - if you have a domain
with N elements (eg 1000 for 3-digit numbers), then you want an n-bit
cipher, with n being the smallest number such that 2**n is larger than N.
That paper uses Hasty Pudding, but you can also construct a simple, slow,
but i believe fairly secure one using a Feistel structure with a truncated
cryptographic hash as the round function.
Second - and this bit is the Trick - to encrypt an element of your domain,
you write it as an n-bit number smaller than N, and encrypt it. The
ciphertext is also an n-bit number; if it's smaller than N, you're done.
If it isn't, you encrypt again. Repeat until done.
For homework, prove that this trick will eventually terminate. Because i'd
be very interested to see a proof!
tom
--
A revolution without dancing is a revolution not worth having. -- V