encryption - tipos - Función Hash que produce hash cortos?
tipos de funciones hash (8)
Necesita manipular los contenidos para obtener un resumen. Hay muchos hashes disponibles, pero 10 caracteres es bastante pequeño para el conjunto de resultados. Hace mucho tiempo, la gente usaba CRC-32, que produce un hash de 33 bits (básicamente 4 caracteres más un bit). También hay CRC-64 que produce un hash de 65 bits. MD5, que produce un hash de 128 bits (16 bytes / caracteres), se considera roto con fines criptográficos porque se pueden encontrar dos mensajes que tienen el mismo hash. No hace falta decir que cada vez que crea un compendio de 16 bytes de un mensaje de longitud arbitraria va a terminar con duplicados. Cuanto más corto es el resumen, mayor es el riesgo de colisiones.
Sin embargo, su preocupación de que el hash no sea similar para dos mensajes consecutivos (sean enteros o no) debe ser cierto con todos los hashes. Incluso un cambio de un solo bit en el mensaje original debería producir un resumen enormemente diferente.
Por lo tanto, usar algo como CRC-64 (y el resultado de base-64'') debería llevarte al vecindario que estás buscando.
¿Existe un cifrado de una sola dirección que pueda tomar una cadena de cualquier longitud y producir un hash de menos de 10 caracteres? Quiero producir identificaciones razonablemente únicas pero basadas en el contenido del mensaje, en lugar de hacerlo al azar.
Sin embargo, puedo vivir restringiendo los mensajes a valores enteros si las cadenas de longitud arbitraria son imposibles. Sin embargo, el hash no debe ser similar para dos enteros consecutivos, en ese caso.
Necesitaba algo parecido a una simple función de reducción de cuerda recientemente. Básicamente, el código se veía algo así (código C / C ++ adelante):
size_t ReduceString(char *Dest, size_t DestSize, const char *Src, size_t SrcSize, bool Normalize)
{
size_t x, x2 = 0, z = 0;
memset(Dest, 0, DestSize);
for (x = 0; x < SrcSize; x++)
{
Dest[x2] = (char)(((unsigned int)(unsigned char)Dest[x2]) * 37 + ((unsigned int)(unsigned char)Src[x]));
x2++;
if (x2 == DestSize - 1)
{
x2 = 0;
z++;
}
}
// Normalize the alphabet if it looped.
if (z && Normalize)
{
unsigned char TempChr;
y = (z > 1 ? DestSize - 1 : x2);
for (x = 1; x < y; x++)
{
TempChr = ((unsigned char)Dest[x]) & 0x3F;
if (TempChr < 10) TempChr += ''0'';
else if (TempChr < 36) TempChr = TempChr - 10 + ''A'';
else if (TempChr < 62) TempChr = TempChr - 36 + ''a'';
else if (TempChr == 62) TempChr = ''_'';
else TempChr = ''-'';
Dest[x] = (char)TempChr;
}
}
return (SrcSize < DestSize ? SrcSize : DestSize);
}
Probablemente tenga más colisiones de las que podrían desearse, pero no está diseñado para ser utilizado como función hash criptográfica. Puede intentar varios multiplicadores (es decir, cambiar el 37 a otro número primo) si obtiene demasiadas colisiones. Una de las características interesantes de este fragmento es que cuando Src es más corto que Dest, Dest termina con la cadena de entrada tal como está (0 * 37 + valor = valor). Si quiere algo "legible" al final del proceso, Normalize ajustará los bytes transformados a costa de aumentar las colisiones.
Fuente:
https://github.com/cubiclesoft/cross-platform-cpp/blob/master/sync/sync_util.cpp
Podría usar un algoritmo hash existente que produzca algo corto, como MD5 (128 bits) o SHA1 (160). Luego puedes acortar eso más adelante mediante secciones XORing del resumen con otras secciones. Esto aumentará la probabilidad de colisiones, pero no tan malo como simplemente truncar el resumen.
Además, podría incluir la longitud de los datos originales como parte del resultado para hacerlo más único. Por ejemplo, XORing la primera mitad de un resumen MD5 con la segunda mitad resultaría en 64 bits. Agregue 32 bits para la longitud de los datos (o menor si sabe que la longitud siempre cabe en menos bits). Eso daría como resultado un resultado de 96 bits (12 bytes) que luego podría convertirse en una cadena hexagonal de 24 caracteres. Alternativamente, puede usar la codificación base 64 para hacerlo aún más corto.
Puede utilizar cualquier algoritmo hash comúnmente disponible (por ejemplo, SHA-1), que le dará un resultado ligeramente más largo que el que necesita. Simplemente trunque el resultado a la longitud deseada, que puede ser lo suficientemente bueno.
Por ejemplo, en Python:
>>> import hashlib
>>> hash = hashlib.sha1("my message".encode("UTF-8")).hexdigest()
>>> hash
''104ab42f1193c336aa2cf08a2c946d5c6fd0fcdb''
>>> hash[:10]
''104ab42f11''
Puede utilizar la biblioteca de hashids que tiene implementaciones para PHP, Javascript, Python, etc. Para más detalles, consulte este enlace
Si necesita "sub-10-character hash" puede usar el algoritmo Fletcher-32 que produce hash de 8 caracteres (32 bits), CRC-32 o Adler-32 .
CRC-32 es más lento que Adler32 en un factor de 20% - 100%.
Fletcher-32 es ligeramente más confiable que Adler-32. Tiene un costo computacional menor que la suma de comprobación Adler: comparación Fletcher vs Adler .
A continuación, se proporciona un programa de ejemplo con algunas implementaciones de Fletcher:
#include <stdio.h>
#include <string.h>
#include <stdint.h> // for uint32_t
uint32_t fletcher32_1(const uint16_t *data, size_t len)
{
uint32_t c0, c1;
unsigned int i;
for (c0 = c1 = 0; len >= 360; len -= 360) {
for (i = 0; i < 360; ++i) {
c0 = c0 + *data++;
c1 = c1 + c0;
}
c0 = c0 % 65535;
c1 = c1 % 65535;
}
for (i = 0; i < len; ++i) {
c0 = c0 + *data++;
c1 = c1 + c0;
}
c0 = c0 % 65535;
c1 = c1 % 65535;
return (c1 << 16 | c0);
}
uint32_t fletcher32_2(const uint16_t *data, size_t l)
{
uint32_t sum1 = 0xffff, sum2 = 0xffff;
while (l) {
unsigned tlen = l > 359 ? 359 : l;
l -= tlen;
do {
sum2 += sum1 += *data++;
} while (--tlen);
sum1 = (sum1 & 0xffff) + (sum1 >> 16);
sum2 = (sum2 & 0xffff) + (sum2 >> 16);
}
/* Second reduction step to reduce sums to 16 bits */
sum1 = (sum1 & 0xffff) + (sum1 >> 16);
sum2 = (sum2 & 0xffff) + (sum2 >> 16);
return (sum2 << 16) | sum1;
}
int main()
{
char *str1 = "abcde";
char *str2 = "abcdef";
size_t len1 = (strlen(str1)+1) / 2; // ''/0'' will be used for padding
size_t len2 = (strlen(str2)+1) / 2; //
uint32_t f1 = fletcher32_1(str1, len1);
uint32_t f2 = fletcher32_2(str1, len1);
printf("%u %X /n", f1,f1);
printf("%u %X /n/n", f2,f2);
f1 = fletcher32_1(str2, len2);
f2 = fletcher32_2(str2, len2);
printf("%u %X /n",f1,f1);
printf("%u %X /n",f2,f2);
return 0;
}
Salida:
4031760169 F04FC729
4031760169 F04FC729
1448095018 56502D2A
1448095018 56502D2A
Está de acuerdo con los vectores de prueba :
"abcde" -> 4031760169 (0xF04FC729)
"abcdef" -> 1448095018 (0x56502D2A)
Adler-32 tiene una debilidad por los mensajes cortos con pocos cientos de bytes, porque las sumas de comprobación para estos mensajes tienen una cobertura pobre de los 32 bits disponibles. Mira esto:
Si no necesita un algoritmo que sea fuerte contra la modificación intencional, he encontrado un algoritmo llamado adler32 que produce resultados bastante cortos (~ 8 caracteres). Elija de la lista desplegable aquí para probarlo:
Solo resumí una respuesta que fue útil para mí (tomando nota del comentario de @ erasmospunk sobre el uso de la codificación base-64). Mi objetivo era tener una cadena corta que fuera en su mayoría única ...
No soy un experto, así que por favor corrige esto si tiene algún error evidente (en Python nuevamente como la respuesta aceptada):
import base64
import hashlib
import uuid
unique_id = uuid.uuid4()
# unique_id = UUID(''8da617a7-0bd6-4cce-ae49-5d31f2a5a35f'')
hash = hashlib.sha1(str(unique_id).encode("UTF-8"))
# hash.hexdigest() = ''882efb0f24a03938e5898aa6b69df2038a2c3f0e''
result = base64.b64encode(hash.digest())
# result = b''iC77DySgOTjliYqmtp3yA4osPw4=''
El result aquí es usar más que solo caracteres hexadecimales (lo que obtendría si usara hash.hexdigest() ) por lo que es menos probable que tenga una colisión (es decir, debería ser más seguro truncar que un resumen hexadecimal).
Nota: Usar UUID4 (aleatorio). Ver http://en.wikipedia.org/wiki/Universally_unique_identifier para los otros tipos.