5

I'm working in C#. I have an unsigned 32-bit integer i that is incremented gradually in response to an outside user controlled event. The number is displayed in hexadecimal as a unique ID for the user to be able to enter and look up later. I need i to display a very different 8 character string if it is incremented or two integers are otherwise close together in value (say, distance < 256). So for example, if i = 5 and j = 6 then:

string a = Encoded(i); // = "AF293E5B"
string b = Encoded(j); // = "CD2429A4"

The limitations on this are:

  1. I don't want an obvious pattern in how the string changes in each increment.
  2. The process needs to be reversible, so if given the string I can generate the original number.
  3. Each generated string needs to be unique for the entire range of a 32-bit unsigned integers, so that two numbers don't ever produce the same string.
  4. The algorithm to produce the string should be fairly easy to implement and maintain for both encoding and decoding (maybe 30 lines each or less).

However:

  1. The algorithm does not need to be cryptographically secure. The goal is obfuscation more than encryption. The number itself is not secret, it just needs to not obviously be an incrementing number.
  2. It is alright if looking at a large list of incremented numbers a human can discern a pattern in how the strings are changing. I just don't want it to be obvious if they are "close".

I recognize that a Minimal Perfect Hash Function meets these requirements, but I haven't been able to find one that will do what I need or learn how to derive one that will.

I have seen this question, and while it is along similar lines, I believe my question is more specific and precise in its requirements. The answer given for that question (as of this writing) references 3 links for possible implementations, but not being familiar with Ruby I'm not sure how to get at the code for the "obfuscate_id" (first link), Skipjack feels like overkill for what I need (2nd link), and Base64 does not use the character set I'm interested in (hex).

10
  • "I don't want an obvious pattern in how the string changes in each increment." - Well, creating your own obfuscating pattern is obviously not a good idea too, unless you will heavily test it. Have you tried looking for any libraries/API that are available out there? Commented Sep 9, 2013 at 15:45
  • The only libraries I've seen are cryptographic in nature and don't generally deal well with numbers as small as 32-bit integers. A 32-bit block cypher would work but seems to be overkill for what I need, and I'd rather implement it myself since security is not an issue and I am trying to keep external dependencies down.
    – hatch22
    Commented Sep 9, 2013 at 15:49
  • FWIW, the actual algorithm used by "obfuscate_id" is here: github.com/namick/scatter_swap/blob/master/lib/scatter_swap/… Commented Sep 9, 2013 at 15:53
  • Thanks. I'll see if I can port it if other answers don't end up working for me.
    – hatch22
    Commented Sep 9, 2013 at 15:56
  • 1
    @hatch22 What is the point of obfuscating the ids if you don't also want it to be secure (i.e. that it's hard to reverse the encoding)? I mean what is an "obvious pattern"? At which point does it become "non-obvious". To me, these ambiguities are why it's not worth doing. If you need to make decoding difficult then make it actually difficult (i.e. cryptographically secure). I may just be naive as to what the requirements are though. edit Ah if you are just trying to prevent stuff like JimMischel's web-scraping example, then the simple modular arithmetic trick MSalter has makes sense.
    – rliu
    Commented Sep 9, 2013 at 16:22

1 Answer 1

3

y = p * x mod q is reversible if p and q are co-primes. In particular, mod 2^32 is easy, and any odd number is a co-prime of 2^32. Now 17,34,51,... is a bit too easy, but the pattern is less obvious for 2^31 < p < 2^32-2^30 (0x8000001-0xBFFFFFFF).

3
  • 1
    This pretty much looks like RSA encryption, check stuvel.eu/rsa for a pure-Python implementation. The core is in rsa.prime and rsa.core, you should be able to follow it enough to convert it into C# ;-)
    – dr. Sybren
    Commented Sep 9, 2013 at 16:16
  • Modular arithmetic is quite close to normal arithmetic. How do you solve y = p*x for x? You multiply both sides by 1/p. In this case your domain isn't the reals, it's the integers up to q-1. So what is 1/p? Well it's 1/p = z such that z*p = 1 mod q, which leads to z*p - 1 = kq => z*p - kq = 1 for some integer k. This equation has an integer solution because p and q are co-prime and because of Bezout's identity: en.wikipedia.org/wiki/B%C3%A9zout%27s_identity. The short answer is... just find the inverse z = 1/p for mod q. Example: q = 5, p = 2, 1/p = 3.
    – rliu
    Commented Sep 9, 2013 at 16:18
  • Looks like I may have created a duplicate, and the answer linked there uses a 32-bit block cypher, but MSalters answer seems to be working for me, so I'll go ahead and accept it.
    – hatch22
    Commented Sep 9, 2013 at 17:00

Your Answer

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

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