짧은 해시를 생성하는 해시 함수?
임의의 길이의 문자열을 가져 와서 10 자 이하의 해시를 생성 할 수있는 암호화 방법이 있습니까? 무작위가 아닌 메시지 내용을 기반으로 합리적으로 고유 한 ID를 생성하고 싶습니다.
그러나 임의 길이 문자열이 불가능한 경우 메시지를 정수 값으로 제한하여 살 수 있습니다. 그러나이 경우 해시는 두 개의 연속 정수에 대해 유사하지 않아야합니다.
일반적으로 사용 가능한 해시 알고리즘 (예 : SHA-1)을 사용하면 필요한 것보다 약간 더 긴 결과를 얻을 수 있습니다. 결과를 원하는 길이로 자르기 만하면 충분할 수 있습니다.
예를 들어 Python에서 :
>>> import hashlib
>>> hash = hashlib.sha1("my message".encode("UTF-8")).hexdigest()
>>> hash
'104ab42f1193c336aa2cf08a2c946d5c6fd0fcdb'
>>> hash[:10]
'104ab42f11'
의도적 인 수정에 대해 강력한 알고리즘이 필요하지 않은 경우 꽤 짧은 (~ 8 자) 결과를 생성하는 adler32 라는 알고리즘을 찾았습니다 . 여기 드롭 다운에서 선택하여 사용해보세요.
다이제스트를 만들려면 콘텐츠를 해시해야합니다. 많은 해시를 사용할 수 있지만 결과 집합에 대해 10 개의 문자는 매우 작습니다. 과거에 사람들은 33 비트 해시 (기본적으로 4 자 + 1 비트)를 생성하는 CRC-32를 사용했습니다. 65 비트 해시를 생성하는 CRC-64도 있습니다. 128 비트 해시 (16 바이트 / 문자)를 생성하는 MD5는 동일한 해시를 가진 두 개의 메시지를 찾을 수 있으므로 암호화 목적으로 손상된 것으로 간주됩니다. 임의의 길이 메시지에서 16 바이트 다이제스트를 만들 때마다 중복으로 끝날 것이라는 것은 말할 필요도 없습니다. 다이제스트가 짧을수록 충돌 위험이 커집니다.
그러나 두 개의 연속 메시지 (정수 여부에 관계없이)에 대해 해시가 유사하지 않다는 우려는 모든 해시에서 참이어야합니다. 원본 메시지에서 한 비트 만 변경해도 매우 다른 결과 다이제스트가 생성됩니다.
따라서 CRC-64와 같은 것을 사용하면 (그리고 결과는 base-64'ing) 당신이 찾고있는 이웃에 도착할 것입니다.
나에게 도움이 된 답변을 요약하면 (base-64 인코딩 사용에 대한 @erasmospunk의 의견에 주목). 내 목표는 대부분 독특한 짧은 줄을 만드는 것이 었습니다 .
나는 전문가가 아니므로 눈에 띄는 오류가 있으면 수정하십시오 (Python에서 다시 수락 된 답변과 같습니다).
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='
result여기가 (당신이 사용하는 경우 당신이 얻을 것 무엇 단지 진수 문자보다 더 많은 사용 hash.hexdigest()이 (즉, 헥스 소화보다 잘라내는 안전해야한다) 충돌을 가지고 덜 그래서).
참고 : UUID4 (무작위) 사용. 다른 유형 은 http://en.wikipedia.org/wiki/Universally_unique_identifier 를 참조하십시오 .
MD5 (128 비트) 또는 SHA1 (160)과 같이 짧은 것을 생성하는 기존 해시 알고리즘을 사용할 수 있습니다. 그런 다음 다이제스트 섹션을 다른 섹션과 XORing하여 더 짧게 만들 수 있습니다. 이렇게하면 충돌 가능성이 증가하지만 단순히 다이제스트를 자르는 것만 큼 나쁘지는 않습니다.
또한 원본 데이터의 길이를 결과의 일부로 포함하여 더 고유하게 만들 수 있습니다. 예를 들어, MD5 다이제스트의 전반을 후반과 XOR하면 64 비트가됩니다. 데이터 길이에 대해 32 비트를 추가합니다 (또는 길이가 항상 더 적은 비트에 맞는다는 것을 알고있는 경우 더 낮음). 그러면 96 비트 (12 바이트) 결과가 생성되어 24 자 16 진수 문자열로 변환 할 수 있습니다. 또는 base 64 인코딩을 사용하여 더 짧게 만들 수 있습니다.
필요한 경우 8 문자 해시 (32 비트), CRC-32 또는 Adler-32 를 생성 "sub-10-character hash"하는 Fletcher-32 알고리즘을 사용할 수 있습니다 .
CRC-32는 Adler32보다 20 %-100 % 느립니다.
Fletcher-32는 Adler-32보다 약간 더 안정적입니다. Adler 체크섬 : Fletcher 대 Adler 비교 보다 계산 비용이 낮습니다 .
몇 가지 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;
}
산출:
4031760169 F04FC729
4031760169 F04FC729
1448095018 56502D2A
1448095018 56502D2A
테스트 벡터에 동의합니다 .
"abcde" -> 4031760169 (0xF04FC729)
"abcdef" -> 1448095018 (0x56502D2A)
Adler-32는 수백 바이트의 짧은 메시지에 대해 약점이 있습니다. 이러한 메시지에 대한 체크섬은 사용 가능한 32 비트의 범위가 좋지 않기 때문입니다. 이것을 확인하십시오 :
Adler32 알고리즘은 비교 가능한 체크섬과 경쟁 할만큼 복잡하지 않습니다 .
터미널 (MacOS 또는 Linux)에서 실행하기 만하면됩니다.
crc32 <(echo "some string")
8 자입니다.
최근에 간단한 문자열 감소 기능이 필요했습니다. 기본적으로 코드는 다음과 같습니다 (C / C ++ 코드 앞).
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);
}
It probably has more collisions than might be desired but it isn't intended for use as a cryptographic hash function. You might try various multipliers (i.e. change the 37 to another prime number) if you get too many collisions. One of the interesting features of this snippet is that when Src is shorter than Dest, Dest ends up with the input string as-is (0 * 37 + value = value). If you want something "readable" at the end of the process, Normalize will adjust the transformed bytes at the cost of increasing collisions.
Source:
https://github.com/cubiclesoft/cross-platform-cpp/blob/master/sync/sync_util.cpp
참고URL : https://stackoverflow.com/questions/4567089/hash-function-that-produces-short-hashes
'programing' 카테고리의 다른 글
| 덮어 쓰지 않고 vim 레지스터에 줄을 추가하는 방법 (0) | 2020.10.10 |
|---|---|
| 어셈블리를로드하고 클래스를 찾고 Run () 메서드를 호출하는 올바른 방법 (0) | 2020.10.10 |
| System.getenv ()와 System.getProperty ()의 차이점 (0) | 2020.10.09 |
| Perl에서 변수에 숫자 값이 있는지 어떻게 알 수 있습니까? (0) | 2020.10.09 |
| 하위 쿼리의 여러 결과를 단일 쉼표로 구분 된 값으로 결합 (0) | 2020.10.09 |