Unique code for every user

[Barry]

HI,

I'm building a system where I wish to give my users a unique code each
time they perform a transaction. On returning to my system, they can
then enter this code to retreive the data associated with it.

I number my transactions in assending order, 0, 1, 2 and so on, so I
need a function that will transform this value to a unique nine digit
number. I also need a function that will transform this value back
again to the transaction number.

Something like this -

long codeTransactionNumber(long transactionNumber)
{
return transactionNumber + 100000000;
}

long uncodeTransactionNumber(long transactionNumber)
{
return transactionNumber - 100000000;
}


Thie problem with this though is that the user with the code
100-000-003 can easily guess that 100-000-004 is also a code for
another transaction. What would be a better way to generate this
number?

Also, I should point out that the number of clients that this system
has is very low - 5 per day max. Also, they enter the code using a
touch screen interface so entering many codes is difficult.

Thanks for your advice,

Barry

 

[Barry]

Is there any reason why you can't just add a password and only allow
users to retrieve data for their own transactions?

Yes, there is a reason. I will print a receipt with the unique code on
it, which they will enter when they return to the system via a touch
screen keypad. Asking the user to enter their own Id is not an option.
Also, my system has no way of knowing if two transactions belong to
the same user or not. Infact, my system has no knowlege of users only
transactions.

Thanks,

Barry

 

[Barry]

Yes, there is a reason. I will print a receipt with the unique code on
it, which they will enter when they return to the system via a touch
screen keypad. Asking the user to enter their own Id is not an option.
Also, my system has no way of knowing if two transactions belong to
the same user or not. Infact, my system has no knowlege of users only
transactions.

Thanks,

Barry

A simple way to think of the system is that of a safety deposit box.
The user gets a unique id when they enter they belongings in it, and
use this key to open it again. The thing is, I don't want people
opening other peoples boxes.

 

[Ross]

Is there any reason why you can't just add a password and only allow
users to retrieve data for their own transactions?

This does sound the more robust solution.

But returning to the original question, if you really want a non-
linear sequence of numbers, I would put the bits of the transaction
number into some bits of a long, say the even bits, and then put
random data into the other (say odd) bits. Then to convert back, just
extract the proper bits, shifting them down into their proper
positions. I'm not going to post exact code as the idea is simple, but
would take me a bit of debugging before I got the bits shifted around
correctly. But it shouldn't be that hard.

 

[Lew]

But returning to the original question, if you really want a non-
linear sequence of numbers, I would put the bits of the transaction
number into some bits of a long, say the even bits, and then put
random data into the other (say odd) bits. Then to convert back, just
extract the proper bits, shifting them down into their proper
positions. I'm not going to post exact code as the idea is simple, but
would take me a bit of debugging before I got the bits shifted around
correctly. But it shouldn't be that hard.

Or you could just use
<http://java.sun.com/javase/6/docs/api/java/util/UUID.html>

"It shouldn't be that hard" contradicts "I'm not going to post exact code as
.... [it] would take me a bit of debugging before I got the bits shifted around
correctly."

 

[Eric Sosman]

HI,

I'm building a system where I wish to give my users a unique code each
time they perform a transaction. On returning to my system, they can
then enter this code to retreive the data associated with it.

I number my transactions in assending order, 0, 1, 2 and so on, so I
need a function that will transform this value to a unique nine digit
number. I also need a function that will transform this value back
again to the transaction number.

Something like this -

long codeTransactionNumber(long transactionNumber)
{
return transactionNumber + 100000000;
}

long uncodeTransactionNumber(long transactionNumber)
{
return transactionNumber - 100000000;
}


Thie problem with this though is that the user with the code
100-000-003 can easily guess that 100-000-004 is also a code for
another transaction. What would be a better way to generate this
number?

Also, I should point out that the number of clients that this system
has is very low - 5 per day max. Also, they enter the code using a
touch screen interface so entering many codes is difficult.

With such a low rate, you could use something simple like
System.currentTimeMillis() or Random#nextLong(). For the inverse,
use a Map<Long,Transaction>; this can also serve as a "memo pad"
to guard against the remote possibility of generating duplicates.

It seems to me that entering a nine-digit authentication code
on a touchscreen will be burdensome no matter what you do. Also,
it sounds like the users might interact with your system, get a
code, and then be expected to re-enter that code some substantial
time later. Do you print the number on a ticket they can carry
around, or do you just expect them to memorize it, or what? (If
you print tickets at a kiosk or something, I foresee a litter
problem.)

 

[Joshua Cranmer]

Thie problem with this though is that the user with the code
100-000-003 can easily guess that 100-000-004 is also a code for
another transaction. What would be a better way to generate this
number?

One way to look at this is that you want a series of random numbers. A
simple pseudorandom number generator is the linear congruential
generator, which basically says: X[n+1] = (a*X[n] + c) mod m.
Eventually, this will cycle, but you can guarantee that it will go
through every number in the range [0, n-1] if you follow these three rules:
1. c and m are relatively prime
2. a - 1 is divisible by all prime factors of m
3. a - 1 is a multiple of 4 if m is a multiple of 4.

Suppose you choose m to be 1,000,000,000 (all nine-digit numbers). Then
you can choose c to be, oh, 784,234,543, and a to be, oh, 42,341.

Starting with 928,531,654, I get:
742-996-557
001-454-480
368-372-223
032-528-586
077-094-369
036-912-372
690-977-395
458-116-238
883-867-701
626-562-584
070-603-687
214-945-810

For bonus points, you can tack on more digits to the end and steal the
highest few digits, since you'll notice that the last few digits have a
good cycle going on.

 

[Ross]

Or you could just use
<http://java.sun.com/javase/6/docs/api/java/util/UUID.html>

I interpreted the original post to mean that the long number created
should incorporate the original transaction number in such a way that
it can be extracted.

 

[Lew]

One way to look at this is that you want a series of random numbers. A
simple pseudorandom number generator is the linear congruential
generator, which basically says: X[n+1] = (a*X[n] + c) mod m.
Eventually, this will cycle, but you can guarantee that it will go
through every number in the range [0, n-1] if you follow these three rules:

But it does *not* guarantee that you'll yield every number in [0, n-1]
exactly once with a cycle length of n.

In other words, there is always a chance of yielding the same value
more than once in fewer than n calls to the generator.

 

[Mike Amling]

HI,

I'm building a system where I wish to give my users a unique code each
time they perform a transaction. On returning to my system, they can
then enter this code to retreive the data associated with it.

I number my transactions in assending order, 0, 1, 2 and so on, so I
need a function that will transform this value to a unique nine digit
number. I also need a function that will transform this value back
again to the transaction number.

Something like this -

long codeTransactionNumber(long transactionNumber)
{
return transactionNumber + 100000000;
}

long uncodeTransactionNumber(long transactionNumber)
{
return transactionNumber - 100000000;
}

One way to do this is with a Ruby-Lackoff Cipher. If your maximum number
is a billion, I don't see why you would need longs, so I'm using ints.

/**
* This generates code numbers in the range 100000000..999999999,
* which I presume is good enough.
*/
private static final int MOD=30000;
public static int encode(int key, int tranNumber) {
int right=tranNumber%MOD;
int left=tranNumber/MOD; // Ha! Probably always 0.
right=(hash30(key, left)+right)%MOD;
left=(hash30(key, right)+left)%MOD;
right=(hash30(key, left)+right)%MOD;
left=(hash30(key, right)+left)%MOD;
return left*MOD+right+100000000;
}
public static int decode(int key, int codeNumber) {
codeNumber-=100000000;
int right=codeNumber%MOD;
int left=codeNumber/MOD;
left=(MOD+left-hash30(key, right))%MOD;
right=(MOD+right-hash30(key, left))%MOD;
left=(MOD+left-hash30(key, right))%MOD;
right=(MOD+right-hash30(key, left))%MOD;
return left*MOD+right;
}
private static int hash30(int key, int data) {
return ((((((6385004+key)
*16777619)
^(data ^ 0x1FF))
*16777619)
^((data>>9) & 0x1FF))
&0x3FffFF)
%MOD;
}


You can choose the key arbitrarily, changing it when you want a
different correspondence between the transaction number and the 9-digit
code. Choosing the key as 1, I got

enc(1, 1)=542638646
enc(1, 2)=900674795
enc(1, 3)=261379172
enc(1, 4)=762769918
enc(1, 5)=419272937
enc(1, 6)=266757288
enc(1, 7)=783673375
enc(1, 8)=599992012
enc(1, 9)=972941767
enc(1, 10)=284982539
enc(1, 11)=663016948
enc(1, 12)=315379905
enc(1, 13)=803750650
enc(1, 14)=302380407

--Mike Amling

 

[Roedy Green]

For smaller numbers use the Hasty Pudding cypher which allows variable
block sizes, as many bits as you want.

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

--
Roedy Green Canadian Mind Products
http://mindprod.com

Smart data structures and dumb code works a lot better than the other way around.
~ Eric S. Raymond The Cathedral and the Bazaar

 

[Mike Amling]

One way to do this is with a Ruby-Lackoff Cipher.

My apologies to Michael Luby and Charles Rackoff for mangling their
names. Of course I meant to write "Luby-Rackoff" Cipher. (Note: I am far
from the first to make exactly this error.)

--Mike Amling

 

[Daniel Pitts]

HI,

I'm building a system where I wish to give my users a unique code each
time they perform a transaction. On returning to my system, they can
then enter this code to retreive the data associated with it.

I number my transactions in assending order, 0, 1, 2 and so on, so I
need a function that will transform this value to a unique nine digit
number. I also need a function that will transform this value back
again to the transaction number.

Something like this -

long codeTransactionNumber(long transactionNumber)
{
return transactionNumber + 100000000;
}

long uncodeTransactionNumber(long transactionNumber)
{
return transactionNumber - 100000000;
}


Thie problem with this though is that the user with the code
100-000-003 can easily guess that 100-000-004 is also a code for
another transaction. What would be a better way to generate this
number?

Also, I should point out that the number of clients that this system
has is very low - 5 per day max. Also, they enter the code using a
touch screen interface so entering many codes is difficult.

Thanks for your advice,

Barry

You could try encrypting the transactionId and a hash-code. Its
important to store the hash-code and check it on decrypting, otherwise
they may still be able to find other transactions.

Psuedo-code:

public String calcSecureCode(long transactionId) {
return transactionId + "-" + calcHash(transactionId) ;
}
String encodeTransactionNumber(long transactionId) {
String toEncrypt = calcSecureCode(transactionId);
return encrypt(toEncrypt);
}

Long decodeTransactionNumber(String encrypted) {
String decrypted = decrypt(encrypted);
long transactionId =
Long.valueOf(StringUtils.substringBefore(decrypted, "-"));
if (calcSecureCode(transactionId).equals(decrypted)) {
return transactionId;
}
// Failed validation.
return false;
}


make sure "encrypt" and "decrypt" use secure encryption, as the
transaction+hash is still vulnerable if the outside user figures out
your hash algorithm.

 

[Eric Sosman]

One way to look at this is that you want a series of random numbers. A
simple pseudorandom number generator is the linear congruential
generator, which basically says: X[n+1] = (a*X[n] + c) mod m.
Eventually, this will cycle, but you can guarantee that it will go
through every number in the range [0, n-1] if you follow these three rules:

[0, m-1]

But it does *not* guarantee that you'll yield every number in [0, n-1]
exactly once with a cycle length of n.

Um, er, yes it does (replacing n by m). See, for example,
TAOCP section 3.2.1.2, Theorem A.

In other words, there is always a chance of yielding the same value
more than once in fewer than n calls to the generator.

Yes -- and that chance is exactly zero.

The drawback for the O.P.'s "non-predictability" goal is
that an observer needs only a knowledge of m and any two
consecutive X[] values to discover a and c, and therefore to
be able to predict the entire sequence. Even without knowing
m in advance, a shortish subsequence of X[] is enough to fuel
some pretty good guesses. This is one reason linear congruential
PRNG's are not much used in cryptography.

 

[Eric Sosman]

[...]
The drawback for the O.P.'s "non-predictability" goal is
that an observer needs only a knowledge of m and any two
consecutive X[] values to discover a and c, and therefore to
be able to predict the entire sequence. [...]

"Upon further review," as they say in American football,
two X[] values might not be enough. I'm pretty sure three
would suffice, though.

 

[Lew]

One way to look at this is that you want a series of random numbers. A
simple pseudorandom number generator is the linear congruential
generator, which basically says: X[n+1] = (a*X[n] + c) mod m.
Eventually, this will cycle, but you can guarantee that it will go
through every number in the range [0, n-1] if you follow these three rules:

     [0, m-1]

But it does *not* guarantee that you'll yield every number in [0, n-1]
exactly once with a cycle length of n.

     Um, er, yes it does (replacing n by m).  See, for example,
TAOCP section 3.2.1.2, Theorem A.

In other words, there is always a chance of yielding the same value
more than once in fewer than n calls to the generator.

     Yes -- and that chance is exactly zero.  

Right - replacing n by m, I stand corrected.

 

[Mike Schilling]

HI,

I'm building a system where I wish to give my users a unique code
each
time they perform a transaction. On returning to my system, they can
then enter this code to retreive the data associated with it.

I number my transactions in assending order, 0, 1, 2 and so on, so I
need a function that will transform this value to a unique nine
digit
number. I also need a function that will transform this value back
again to the transaction number.

Something like this -

long codeTransactionNumber(long transactionNumber)
{
return transactionNumber + 100000000;
}

long uncodeTransactionNumber(long transactionNumber)
{
return transactionNumber - 100000000;
}


Thie problem with this though is that the user with the code
100-000-003 can easily guess that 100-000-004 is also a code for
another transaction. What would be a better way to generate this
number?

Also, I should point out that the number of clients that this system
has is very low - 5 per day max. Also, they enter the code using a
touch screen interface so entering many codes is difficult.

Figure out the number of unqiue transactions IDs you'll need before
you can re-use numbers. At five users a day, I'd guess 10,000 is
sufficient. Now:

1. Generate a short transaction ID 1-9999 (i.e. a four-digit number).
2. Write these digits into your long transaction code in some
non-obvious way, e.g. WXYZ -> nYnnWZnnX
3. Generate 4 more random digits PQRS.
4. Let T = 9 - ((4*P + 3*Q + 2*R + S ) % 10)

Your long transaction code is now PYQRWZSTX. You can recover the
short transaction ID by extracting W, X, Y, and Z, and you can check
that a transaction code is valid by seeing whether (4*P + 3*Q + 2*R +
S ) % 10 == 9

This was off the top of my head; some reflection will probably suggest
improvements.

 

[Tom Anderson]

You need something reversible, so a cypher is indicated. For 128 bit
numbers use AES, for 64 bit numbers use 3DES.

For smaller numbers use the Hasty Pudding cypher which allows variable
block sizes, as many bits as you want.

Alternatively, build your own simple block cypher using the Feistel
structure. The NSA will be able to break it but you may not need
something that secure.

Curses! Someone beat me to it! Hasty Pudding lets you have non-integer
number of bits, BTW.

This post:

http://stackoverflow.com/questions/...-been-viewed-are-not-seen-again/966822#966822

Is fundamentally about "a function which maps the combination of an
integer in the range 0...N and a key to another integer in the range
0...N, such that for any value off the key, the mapping between integers
is bijective", which is precisely what you need. You put your internal
count in, and get a cryptic number out - and you can turn that cryptic
number back into a count. The linked thread on sci.crypt is perhaps more
informative for you.

Here's a small implementation:

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

Which sits on top of a little Feistel cipher i cooked up:

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

Using the demo to encrypt and decrypt the first twenty integers, we get
(encrypted counter in the middle):

0 247322710 0
1 397471032 1
2 265460931 2
3 116603216 3
4 789076229 4
5 118350116 5
6 061011385 6
7 093714976 7
8 871443473 8
9 949200669 9
10 257431838 10
11 614149477 11
12 902471066 12
13 541231587 13
14 403434035 14
15 486488836 15
16 741761752 16
17 925791929 17
18 767002650 18
19 256853025 19

Would that suit you?

If you want you use the code itself, the license is here:

http://urchin.earth.li/~twic/Code/license.txt

tom

 

[Tom Anderson]

My apologies to Michael Luby and Charles Rackoff for mangling their names.
Of course I meant to write "Luby-Rackoff" Cipher. (Note: I am far from the
first to make exactly this error.)

Aha! I'm glad i gave up googling so quickly!

tom

 

[Arne Vajhøj]

A simple way to think of the system is that of a safety deposit box.
The user gets a unique id when they enter they belongings in it, and
use this key to open it again. The thing is, I don't want people
opening other peoples boxes.

This problem is very similar to session id in secured web applications.

Based on that I will suggest:
- hash the sequential key
- store the hash value server side and lookup based on that

Hashes is designed to make it difficult to go from hash to
original value.

Arne