피어슨 해시

Pearson hashing

Pearson 해시는 8비트 레지스터가 있는 프로세서에서 빠르게 실행되도록 설계된 해시 함수입니다.임의의 바이트 수로 구성된 입력이 주어지면 입력의 모든 바이트에 크게 의존하는 단일 바이트를 출력으로 생성합니다.이 구현에는 몇 가지 명령과 0 [1]~255 값의 순열을 포함하는 256바이트 룩업테이블이 테이블이 필요합니다.

이 해시 함수는 치환 테이블을 통해 구현된8비트 치환 암호를 사용하는 CBC-MAC 입니다.8비트 암호는 암호화 보안이 무시되기 때문에 Pearson 해시 함수는 암호화적으로 강력하지 않지만 해시 테이블을 구현하거나 데이터 무결성 검사 코드로 사용할 수 있으므로 다음과 같은 이점이 있습니다.

  • 그것은 매우 간단하다.
  • 리소스가 제한된 프로세서에서 빠르게 실행됩니다.
  • 충돌(동일 출력) 가능성이 특히 높은 단순한 입력 클래스는 없습니다.
  • 작은 특권 입력 세트(예를 들어 컴파일러용으로 예약된 단어)가 주어지면, 이러한 입력이 별개의 해시 값을 생성하도록 치환 테이블을 조정할 수 있으며, 이를 완벽한 해시 함수라고 한다.
  • 정확히 한 글자씩 다른 두 입력 문자열은 [2]충돌하지 않습니다.예를 들어, 문자열 ABC와 AEC에 알고리즘을 적용하면 동일한 값이 생성되지 않습니다.

8비트 프로세서를 위해 설계된 다른 해시 알고리즘과 비교할 때 단점 중 하나는 권장되는 256바이트 룩업 테이블입니다.이것은 프로그램 메모리 크기가 수백바이트인 소형 마이크로컨트롤러에서는 엄청나게 클 수 있습니다.이를 회피하기 위한 방법은 프로그램 메모리에 저장된 테이블 대신 간단한 치환 함수를 사용하는 것입니다.단, 다음과 같은 단순한 기능을 사용하는 경우T[i] = 255-i에서는 해시함수와 같은 해시함수로서의 유용성이 부분적으로 배제됩니다.반면 너무 복잡한 함수를 사용하면 속도에 부정적인 영향을 미칩니다.테이블이 아닌 함수를 사용하여 블록 크기를 확장할 수도 있습니다.이러한 함수는 테이블 변형과 같이 당연히 객관적이어야 합니다.

알고리즘은 다음 의사 코드로 설명할 수 있습니다.이 의사 코드는 치환 테이블T를 사용하여 메시지 C의 해시를 계산합니다.

알고리즘 피어슨 해시는 C 루프h := T [ h xor c ]엔드 루프 리턴h의 각 c에 대해h : = 0 입니다.

해시 변수(h데이터 길이에 따라 ( )를 다르게 초기화할 수 있습니다.Cmodulo 256. 이 특정 선택사항은 아래의 Python 구현 예에서 사용됩니다.

구현 예시

Python, 8비트 출력

'table' 매개 변수에는 의사 임의 혼합 범위 목록이 필요합니다 [0..255].python의 빌트인을 사용하면 쉽게 생성될 수 있습니다.range기능 및 사용random.shuffle치환:

부터 랜덤 수입품 섞다  example_table = 목록.(범위(0, 256)) 섞다(example_table)  방어하다 해시 8(메세지: 스트레이트, 테이블) -> 인트:     피어슨 해싱."""     해시 = 렌(메세지) % 256     위해서 i 에서 메세지:         해시 = 테이블[해시 ^ 주문하다(i)]     돌아가다 해시

C#, 8비트

일반의 학급 피어슨 해싱 {     일반의 바이트 해시(스트링 입력)     {         컨스턴트 바이트[] T = { /* 치환율 0 ~255 */ };                  바이트 토레트 = 0;         바이트[] 바이트 수 = 부호화.UTF8.GetBytes(입력);          앞지르다 (변화하다 b 에서 바이트 수)         {             토레트 = T[(바이트)(토레트 ^ b)];         }          돌아가다 토레트;     } }

「 」를 참조해 주세요.

레퍼런스

  1. ^ Pearson, Peter K. (June 1990), "Fast Hashing of Variable-Length Text Strings" (PDF), Communications of the ACM, 33 (6): 677, doi:10.1145/78973.78978, archived from the original (PDF) on 2012-07-04, retrieved 2013-07-13
  2. ^ Lemire, Daniel (2012), "The universality of iterated hashing over variable-length strings", Discrete Applied Mathematics, 160 (4–5): 604–617, arXiv:1008.1715, doi:10.1016/j.dam.2011.11.009