Simple hash function to implement on a microcontroller

microcontroller

I'm looking for a very simple hash function to implement on a microcontroller. The microcontroller displays a 4 digit alphanumeric session id on a display. I want to give the hash function a count and get back a number, which would later be turned into a 4-digit alphanumeric number. Any suggestions for a lightweight hash function?

Best Answer

How secure do you want this thing to be, and what are your code size versus space trade-offs? Are you going to be needing sequential numbers only, or values in arbitrary sequence?

Two simple hash-generation approaches are: // Get a random bit via linear congruential generator: int random_bit1(void) { static unsigned long seed; seed = seed*magicConstant + 12345; return (seed >> 31); // Use upper bit--not lower bit! }

int random_bit2(void)
{
  // Get a 'random' bit via linear feedback shift register
  unsigned long shifter;
  if (!shifter)
    shifter = 1;
  else if (shifter & 1)
    shifter = (shifter>>1);
  else
    shifter = (shifter>>1);
  return (shifter & 1);
}

To generate a four digit number, use something like the following:

int result = 0;
int i;
for (i=0; i<30; i++) // The higher the count, the less biased the results
{
  result *= 2;
  if (result >= 10000)
    result -= 10000;
  result += randomBit();
}

Note that both of the above bit-generation algorithms can be adapted to return the nth value for any arbitrary n in a reasonable amount of time, though the code to do that will be a fair bit more complicated. On the other hand, neither algorithm will be hard to reverse-engineer.

If you're only going to need values in sequence (meaning that after you've outputted the nth thing, you'll never need to output any lower-numbered thing, and you won't mind if computing a higher-numbered thing requires computing all intervening values) it is possible to build up some security by using six or so independent pseudo-random-bit generators (perhaps shift registers with different periods), and then use something like:

int reallyrandombit(void)
{
  if (randombit1())
  {
    if (randombit2())
      return randombit3();
    else
      return randombit4();
  }
  else
  {
    if (randombit3())
      return randombit5();
    else
      return randombit6();
  }
}

Note that for good results there should be some mixing of how random generators get used (note that random3 is used in two different places) but one should avoid feedback paths (none of the random generators affects the shifting of anything which would affect it) unless one has the tools to fully analyze them.

Related Topic