Función hash simple para implementar en un microcontrolador

6

Estoy buscando una función hash muy simple para implementar en un microcontrolador. El microcontrolador muestra una identificación de sesión alfanumérica de 4 dígitos en una pantalla. Quiero darle un recuento a la función hash y recuperar un número, que luego se convertiría en un número alfanumérico de 4 dígitos. ¿Alguna sugerencia para una función hash ligera?

    
pregunta alexbb

5 respuestas

5

¿Qué tan seguro quiere que sea esta cosa, y cuál es el tamaño de su código en comparación con las compensaciones de espacio? ¿Necesitará solo números secuenciales o valores en secuencia arbitraria?

Dos enfoques simples de generación de hash son:     // Obtener un bit aleatorio a través de un generador lineal congruente:     int random_bit1 (void)     {       semilla larga sin firma estática;       semilla = semilla * magicConstant + 12345;       retorno (semilla > > 31); // ¡Usa el bit superior - no el bit inferior!     }

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);
}

Para generar un número de cuatro dígitos, use algo como lo siguiente:

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();
}

Tenga en cuenta que los dos algoritmos de generación de bits anteriores pueden adaptarse para devolver el valor n para cualquier n arbitrario en un tiempo razonable, aunque el código para hacerlo será un poco más complicado. Por otro lado, ningún algoritmo será difícil de aplicar ingeniería inversa.

Si solo va a necesitar valores en secuencia (lo que significa que después de que haya emitido la novena cosa, nunca tendrá que generar ninguna cosa con un número menor, y no le importará si se calcula un valor más alto) La cosa numerada requiere el cálculo de todos los valores intermedios) es posible desarrollar algo de seguridad mediante el uso de seis o más generadores de bits pseudoaleatorios independientes (quizás desplazar registros con diferentes períodos), y luego usar algo como:

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

Tenga en cuenta que para obtener buenos resultados, debe haber alguna mezcla de cómo se utilizan los generadores aleatorios (tenga en cuenta que random3 se utiliza en dos lugares diferentes), pero se debe evitar las rutas de retroalimentación (ninguno de los generadores aleatorios afecta el cambio de nada que pueda afectar it) a menos que uno tenga las herramientas para analizarlas completamente.

    
respondido por el supercat
7

CRC32 haría el trabajo si no necesita seguridad criptográfica. Le proporciona un valor de salida de 32 bits y solo requiere operaciones simples. Un montón de implementaciones para la mayoría de las micro familias importantes, también. Dividir a 4 bytes y hacer módulo en un alfabeto de 32 caracteres (1-9 A-Z, saltando algunos caracteres como I y J) para cada uno, y ahí está su código.

    
respondido por el Polynomial
4

Es posible que esté interesado en esta biblioteca de Crypto . Su lanzamiento bajo la GPL v3.

  

Crypto-avr-lib es un conjunto de implementaciones de diferentes primitivas criptográficas. Debido a las limitaciones especiales de los microcontroladores (muy poco espacio, la memoria RAM y la memoria flash van desde unos pocos bytes a unos pocos KiB) o las implementaciones optimizadas "normales" no son utilizables. Por lo tanto, intentamos proporcionar implementaciones especiales que respeten los recursos extremadamente limitados de las aplicaciones de microcontroladores.

Hay varios algoritmos hash disponibles:

  • Blake
  • BlueMidnightWish
  • Grøstl
  • MD5
  • SHA-256
  • SHA-1
  • SHA-3 (Keccak)
  • SHABAL
  • Skein
  • Twister
  • Bañera de hidromasaje

Puede acceder al código completo a través de su repositorio de Subversion en enlace .

    
respondido por el Rev1.0
3
  • Si realmente no te preocupa la seguridad
  • Si todo lo que quieres hacer es 'arruinar' un número

Luego hay un montón de formas realmente simples de hacer esto, aquí hay dos que puedo pensar:

void really_simple_hash(uint16_t x)
{
    SWAP_NIBBLES(FIRST_BYTE(x));
    SWAP_NIBBLES(SECOND_BYTE(x));
    x ^= 0xAAAA;
    return x;
}

En un PIC18, esto se traduce en un código muy simple:

SWAPF  x,   f
SWAPF  x+1, f
movlw  0xAA
xorwf  x,   f
xorwf  x+1, f

Es bastante liviano con un tiempo de ejecución de solo 5uS en un PIC18 que se ejecuta en 10MIPS. Si eso no es suficiente de un lío, puedes barajar los bits en el número. De nuevo, en un PIC18:

rrcf   x,   f        ; Then we take each bit of the source word
rlcf   y+1, f        ; and shift it into one of the destination bytes
rrcf   x+1, f
rlcf   y,   f        ; There are:
rrcf   x,   f        ; - eight right shifts of x,
rlcf   y+1, f        ; - eight right shifts of x+1,
rrcf   x+1, f        ; - eight left shifts of y,
rlcf   y+1, f        ; - eight left shifts of y+1,
rrcf   x,   f
rlcf   y,   f        ; You can do them in whatever sequence you want
rrcf   x+1, f
rlcf   y,   f
rrcf   x,   f
rlcf   y+1, f
rrcf   x,   f
rlcf   y,   f
rrcf   x,   f
rlcf   y,   f
rrcf   x,   f       
rlcf   y+1, f       
rrcf   x+1, f
rlcf   y,   f
rrcf   x,   f
rlcf   y+1, f
rrcf   x+1, f
rlcf   y+1, f
rrcf   x,   f
rlcf   y,   f
rrcf   x+1, f
rlcf   y,   f
rrcf   x,   f
rlcf   y+1, f
rrcf   x,   f
rlcf   y,   f
rrcf   x,   f
rlcf   y,   f        ; Finally, the result is stored in y

Todavía es bastante liviano, con un tiempo de ejecución de solo 37 uS para el mismo PIC18.

    
respondido por el Rocketmagnet
1

Si no necesita ser criptográfico fuerte:

  • elija una clave aleatoria de la misma longitud en bits;
  • comparte la clave entre el remitente y el destinatario;
  • remitente -side: crypto-text = clave EOR de texto simple (puede hacer esto byte a byte).

Opcional:

  • receptor , junto a texto claro = clave EOR de texto criptográfico.
respondido por el jippie

Lea otras preguntas en las etiquetas