5
$\begingroup$

I need to generate unique (random) numbers that I can trace back to a unique source number.

For example:

source number A can generate numbers A1, A1, A3 .... Am
source number B can generate numbers B1, B2, B3 .... Bm
...
source number N can generate numbers N1, N2, N3 .... Nm

All the source numbers A, B, .. N and generated numbers Ai, Bi, Ni should be unique and mutually exclusive.

Now for any generated number Ai, I should be able to compute unambiguously the source number A (and the same goes for Bi, Ci, ... Ni).

Can anybody help with the algorithm for this?

Use case: a user types a numeric code generated by this algorithm. The server should be able to identify this user, from the code alone. For others it should not be possible to identify the user, nor generate subsequent codes for that user.

Improve this question
$\endgroup$
11
  • $\begingroup$ Yes. $\;$ $\endgroup$
    – user991
    Sep 15, 2015 at 7:58
  • $\begingroup$ I mean can you help me with an algorithm for this? $\endgroup$
    – pee
    Sep 15, 2015 at 8:05
  • $\begingroup$ How big should the numbers be? $\endgroup$
    – CodesInChaos
    Sep 15, 2015 at 8:28
  • $\begingroup$ Best not too big. The numbers need to be entered in a (numeric) keypad. Six digits would be ideal. $\endgroup$
    – pee
    Sep 15, 2015 at 8:35
  • $\begingroup$ 10 digits would be easier, since then you could simply use a 32 bit block cipher like Skip32 instead of needing complicated format preserving encryption like FFX mode. $\endgroup$
    – CodesInChaos
    Sep 15, 2015 at 10:00

1 Answer 1

Reset to default
6
$\begingroup$

The numbers $n$ (coding source) and $m$ (coding index for a given source) can be combined into a single bitstring; e.g. with $0\le m<2^u$ and $0\le n<2^v$, as a bitstring of $\lceil u+v\rceil$ bits. Then, converting that single bitstring into a unique random-like number can be done by encryption with a secure block cipher with block width $w\ge u+v$ bits and a fixed secret key (prefixing input with $w-\lceil u+v\rceil$ zero bits in order to reach the width $w$ of the block cipher). The random-like number will be an integer corresponding to the ciphertext bitstring, thus in range $[0\dots2^w-1]$.

Distinct pairs $(n,m)$ inputs allways lead to distinct output, because a block cipher is a permutation of its block space. Decryption (requiring the key) allows recovering the original bitstring from the random-like number, and from that $n$ and $m$. If one checks that what's deciphered could have been obtained from a valid $(n,m)$ (including $w-\lceil u+v\rceil$ zero leading bits), residual odds that a random bitstring is acceptable are $2^{u+v-w}$.

Using AES ($w=128$, regardless of key width) and $u=v=40$ ($n$ and $m$ up to about a trillion), these residual odds are $2^{-48}$. Problem is, the random-like number is up $2^{128}$ (about $39$ decimal digits). The classic 3DES ($w=64$) or the relatively unproven Speck ($w\in\{32,48,64,96,128\}$) are alternatives.

If you want a shorter unique random-like number (with as a counterpart higher residual odds that a random bitstring will be acceptable), or more choices for $w$, use format-preserving encryption; we have a number of questions about that.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Tx for your answer!. I am new to cryptography. So you basically propose that I glue the two numbers together and then randomize them with a block cipher like AES? What I don't understand is the sentence "(prefixing with w−⌈u+v⌉ zero bits)"?. * Is Skip32 as suggested by @CodesInChaos also useable? $\endgroup$
    – pee
    Sep 15, 2015 at 22:31
  • $\begingroup$ a) by using above method. wat is the chance that a duplicate number will be generated for a given source number? (I need to avoid this!) b) wat is the chance that a duplicate number will be generated accross all source numbers? $\endgroup$
    – pee
    Sep 16, 2015 at 0:33
  • $\begingroup$ @pee: The glued numbers might not be as wide as the AES input block (128-bit); so you need to add extra bits to reach 128-bit. No two distinct pairs of source number can generate a duplicate output value, if you keep the full width of the output. If $w=128$-bit of output is too much for you, you need a cipher with a narrower $w$. $\endgroup$
    – fgrieu ♦
    Sep 16, 2015 at 3:38
  • $\begingroup$ Thanks guys for the excellent answers! w+v should be no more than 32 bits. Can I use skip32 for this? How does this compare with speck? Or another algorithm that requires not much computing power and memory? I need this implemented in the firmware of a microcontroller. $\endgroup$
    – pee
    Sep 16, 2015 at 7:04
  • $\begingroup$ @pee: I guess you wanted to write "$u+v$ should be no more than 32 bits". Yes you can use skip32. It has the advantage over speck with $w=32$ that skip32's key is stronger (80-bit vs 64-bit), and that skip32 has been around for a longer time. On the other hand speck's design and security rationale might be more modern and thoroughly justified than that of skip32 (but I've not deeply studied either). As a minor drawback of skip32, it is an even permutation, implying that if you know the mapping of $2^{32}-2$ values, then you can easily determine the mapping of the other two. $\endgroup$
    – fgrieu ♦
    Sep 16, 2015 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.