Random Unique alphanumeric generator using Java

[Krist]

Hi gurus,

To implement e-ticket system (user do reservation and print the ticket
by himself), we need to generate a alphanumeric reservation number ,
with these requirement :
- Unique
- Can be validated that it is a valid number

What are the possible approaches to this ?

Thank you,
Krist

 

[Screamin' Lord Byron]

But if you're looking for a number that is practical to read to a
customer over the phone (e.g. as backup for the online system), or for
the customer to enter by hand later into some system, encrypting the
reservation data probably isn't feasible.

It could be if the data are small enough. Say you're encrypting
something like reservation serial number (which could be a database key
that starts from 1 and is incremented by 1 with every new reservation)
along with some control number. That data should fit inside a single DES
block, ie. it should not be longer that 64 bits. If you encode the
resulting cyphertext with base-32, you get a reasonably short
alphanumeric output - 13 chars (the padding chars can be ignored, of
course).

When decrypting, if you get the correct control number then the
reservation code is OK and that could be done completely offline.
Furthermore, if you need additional info about the reservation you'll
also have the serial number decrypted which you can use to query the
database.

 

[markspace]

Hi gurus,

To implement e-ticket system (user do reservation and print the ticket
by himself), we need to generate a alphanumeric reservation number ,
with these requirement :
- Unique
- Can be validated that it is a valid number

I just happened to purchase a ticket online this weekend. It included a
bar code on the print out that was scanned with a bar code reader when
we entered the museum. So that's another thing you might think about:
something unique but short enough that it will fit on a bar code.

I think I would be tempted to just generate a sequence and then hash or
otherwise lightly encrypt the sequence to generate a number that was
hard to guess. This process would have to be reversible (symmetric
encryption?) and you might think about some sort of "salt" to make it a
little harder to crack.

 

[Jean-Baptiste Nizet]

If you require uniqueness then you cannot usse a random number because
you cannot guarantee non-repetition with random numbers.  What you
need is a permutation into a random seeming order.

The easiest way to do that is encryption.  Take a set of internal ID
numbers: 0001, 0002, 0003, 0004, ...  Encrypt those numbers using DES,
AES or whatever to generate a random seeming sequence of unique
numbers that can be decrypted back to give the original ID number.

You do not describe the threats you are protecting against but to
validate you could just include the plaintext.  So if 0001 encrypts to
60AC on 2010-12-06 then the issued ticket number is:
60AC-0001-2010-12-06.  If the first part decrypts to give the second
part using the key appropriate for the date then the number is valid,
otherwise not.

I fail to see how encryption helps in your method.
If the verification of the reservation number is decentralized, then
you need to distribute the secret keys to all the verificators in a
safe way, which is not necessarily an easy task.
If it's centralized, a random number associated with the sequence
number and stored in database is sufficient for the verification, and
safer than symmetric encryption, since no secret key might be
compromized.

JB.

 

[Screamin' Lord Byron]

Not a random number. You cannot guarantee uniqueness with a random
number.

True but in your case it don't have to be. You're not using a random
number by itself. Let's say we have (an unlikely) situation when we get
two random numbers that are the same. The codes would look like:

CAFE-0001-2010-12-06
CAFE-0042-2010-12-06

They look unique enough to me.

 

[Martin Gregorie]

On Mon, 6 Dec 2010 07:41:05 -0800 (PST), Jean-Baptiste Nizet

Not a random number. You cannot guarantee uniqueness with a random
number. A block cypher is a permutation and so can guarantee uniqueness
for unique inputs. By all means include a random salt in the system
somewhere but it must not affect the uniqueness requirement.

In this case a non-duplicated random number would be good enough provided
that the random number is significantly larger than the sequence number
range it validates. Do something like this:

create sequence seqlist;
create table t ( long checknumber prime key, int seqno);

seqno = select nextval('seqlist');
r = random number;
while (select count(*) from table t where t.checknumber = r)
r = random number;

insert into table (seqno, checknumber) values (seqno, r);
print ticket using r;


If the checknumber has, say, twice the number of digits in the sequence
number, collisions should be quite rare, so the while loop will almost
never be used.

I'd also consider using Date.getTime() with an added sequence number and
a Luhn check digit as the ticket number. If sale volumes are low enough
to be certain that multiple tickets never be sold with identical Date
values then the sequence number can be omitted. If Luhn check digits are
good enough for credit card account numbers they are probably good enough
for this application and have the advantage of removing the dependency on
a central database.

 

[Roedy Green]

- Unique
- Can be validated that it is a valid number

A very simple way would be to just have a central counter you
increment, then multiply by some large prime. If the ticket number is
a multiple of the prime it is ok. Add a constant or other reversible
tweak to disguise what you are doing.

Also just encrypt integers with any JCE method.

see also http://mindprod.com/jgloss/unique.html

 

[Tom Anderson]

In this case a non-duplicated random number would be good enough provided
that the random number is significantly larger than the sequence number
range it validates.

It would. Both of those approaches are equally good in practice, really.
The counter + cipher approach is more elegant, because it guarantees
non-collision by design, and only requires a single number be stored, not
all the numbers generated so far. I does, however, require more - gasp! -
programming.

Unless you're working in java and trust me, in which case you can just
steal it (see HastyPuddingDemo.java in particular):

http://urchin.earth.li/~twic/Code/HastyPudding/

I'd also consider using Date.getTime() with an added sequence number and
a Luhn check digit as the ticket number. If sale volumes are low enough
to be certain that multiple tickets never be sold with identical Date
values then the sequence number can be omitted. If Luhn check digits are
good enough for credit card account numbers

There are better algorithms:

http://en.wikipedia.org/wiki/Verhoeff_algorithm

I don't know why cards use Luhn instead of Verhoeff (maybe the standard
comes from before it was invented or widely known, or maybe its authors
felt the checksum should be calculable by hand), but there's no reason for
anyone else to do the same.

To be honest, if you're going to compute, you might as well look into
using a 4-bit CRC, and encoding the result in a hex digit. I don't know
that this gives better protection against human error than a Verhoeff
checksum, though.

tom

--
For the first few years I ate lunch with he mathematicians. I soon found
that they were more interested in fun and games than in serious work,
so I shifted to eating with the physics table. There I stayed for a
number of years until the Nobel Prize, promotions, and offers from
other companies, removed most of the interesting people. So I shifted
to the corresponding chemistry table where I had a friend. At first I
asked what were the important problems in chemistry, then what important
problems they were working on, or problems that might lead to important
results. One day I asked, "if what they were working on was not important,
and was not likely to lead to important things, they why were they working
on them?" After that I had to eat with the engineers! -- R. W. Hamming

 

[Martin Gregorie]

I don't know why cards use Luhn instead of Verhoeff (maybe the standard
comes from before it was invented or widely known, or maybe its authors
felt the checksum should be calculable by hand), but there's no reason
for anyone else to do the same.

Agreed. I'm certain I used to know and use better checksum back when mag
tape and cards were the flavour of the day. Modulo 10, which is the
weaker but allows any possible number string to be checksummed, was IIRC
pretty much the same as Luhn but without even position weighting, while
modulo 12, especially with a weighting matrix, catches more transcription
errors but with the disadvantage that not all numeric strings will
generate an acceptable checksum.

Given that the OP seems to want security rather than checks against
transcription errors, I think I prefer my suggestion for using random
numbers - that or using an encrypted sequence number.

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?

 

[Tom Anderson]

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

 

[Martin Gregorie]

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

Intriquing. Does the 'keep doing it until the result is the original
length' also work for decryption? Presumably it does.

I did wonder if the (precomputer) Playfair code would be good enough in
these circumstances, possibly extended to a 6x6 matrix to allow digits to
be encrypted, because it also generates an equal length cypher text and
shouldn't be very computationally intensive. I'm also not crypto-literate
enough to know how often the code pad would need to be changed when the
plain text is short compared with the code pad and how much this would
impact the system.

However, I imagine this is a hopelessly simplistic idea.

 

[steph]

Hi gurus,

To implement e-ticket system (user do reservation and print the ticket
by himself), we need to generate a alphanumeric reservation number ,
with these requirement :
- Unique
- Can be validated that it is a valid number

What are the possible approaches to this ?

Thank you,
Krist

You may have a look at
http://download.oracle.com/javase/6/docs/api/java/util/UUID.html