Random Unique alphanumeric generator using Java

Discussion in 'Java' started by Krist, Dec 6, 2010.

  1. Krist

    Krist Guest

    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
     
    Krist, Dec 6, 2010
    #1
    1. Advertising

  2. On 6. 12. 10. 9:13 AM, Peter Duniho wrote:

    > 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.
     
    Screamin' Lord Byron, Dec 6, 2010
    #2
    1. Advertising

  3. Krist

    markspace Guest

    On 12/5/2010 8:58 PM, Krist wrote:
    > 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.
     
    markspace, Dec 6, 2010
    #3
  4. On 6 déc, 16:10, rossum <> wrote:
    > On Sun, 5 Dec 2010 20:58:50 -0800 (PST), Krist <>
    > wrote:
    >
    > >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

    >
    > 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.
     
    Jean-Baptiste Nizet, Dec 6, 2010
    #4
  5. On 6. 12. 10. 5:26 PM, rossum wrote:

    >> 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.

    > 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.
     
    Screamin' Lord Byron, Dec 6, 2010
    #5
  6. On Mon, 06 Dec 2010 16:26:10 +0000, rossum wrote:

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


    >>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.

    > 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.


    --
    martin@ | Martin Gregorie
    gregorie. | Essex, UK
    org |
     
    Martin Gregorie, Dec 6, 2010
    #6
  7. Krist

    Roedy Green Guest

    On Sun, 5 Dec 2010 20:58:50 -0800 (PST), Krist <>
    wrote, quoted or indirectly quoted someone who said :

    >- 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
    --
    Roedy Green Canadian Mind Products
    http://mindprod.com

    In programming, and documenting programs, keep vocabulary consistent and precisely defined! Variation in vocabulary to relieve the tedium is for novels.
     
    Roedy Green, Dec 7, 2010
    #7
  8. Krist

    Tom Anderson Guest

    On Mon, 6 Dec 2010, Martin Gregorie wrote:

    > On Mon, 06 Dec 2010 16:26:10 +0000, rossum wrote:
    >
    >> On Mon, 6 Dec 2010 07:41:05 -0800 (PST), Jean-Baptiste Nizet
    >> <> wrote:
    >>
    >>> 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.

    >>
    >> 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.


    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
     
    Tom Anderson, Dec 7, 2010
    #8
  9. On Tue, 07 Dec 2010 13:18:07 +0000, Tom Anderson wrote:

    > 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?


    --
    martin@ | Martin Gregorie
    gregorie. | Essex, UK
    org |
     
    Martin Gregorie, Dec 7, 2010
    #9
  10. Krist

    Tom Anderson Guest

    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
     
    Tom Anderson, Dec 7, 2010
    #10
  11. On Tue, 07 Dec 2010 20:25:36 +0000, Tom Anderson wrote:

    > 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
    >

    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.


    --
    martin@ | Martin Gregorie
    gregorie. | Essex, UK
    org |
     
    Martin Gregorie, Dec 7, 2010
    #11
  12. Krist

    steph Guest

    On 06/12/2010 05:58, Krist wrote:
    > 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
     
    steph, Dec 7, 2010
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. globalrev
    Replies:
    4
    Views:
    771
    Gabriel Genellina
    Apr 20, 2008
  2. ToshiBoy
    Replies:
    6
    Views:
    850
    ToshiBoy
    Aug 12, 2008
  3. Jonathan Woodward

    PasswordRecovery Control, Limiting Random Password to Alphanumeric

    Jonathan Woodward, Apr 27, 2006, in forum: ASP .Net Web Controls
    Replies:
    0
    Views:
    194
    Jonathan Woodward
    Apr 27, 2006
  4. VK
    Replies:
    15
    Views:
    1,174
    Dr J R Stockton
    May 2, 2010
  5. Token Type
    Replies:
    9
    Views:
    359
    Chris Angelico
    Sep 9, 2012
Loading...

Share This Page