체크섬

Checksum
일반적인 체크섬 함수(Unix)의 효과cksum유틸리티)

체크섬은 전송 또는 저장 중에 발생할 수 있는 오류를 검출하기 위해 다른 디지털 데이터 블록에서 파생된 작은 크기의 데이터 블록입니다.체크섬은 데이터 무결성을 검증하는 데 자주 사용되지만 데이터 신뢰성을 [1]검증하는 데는 의존하지 않습니다.

이 체크섬을 생성하는 절차를 체크섬 함수 또는 체크섬 알고리즘이라고 합니다.설계 목표에 따라서는 보통 양호한 체크섬알고리즘은 [2]입력에 대한 작은 변경에도 크게 다른 값을 출력합니다.이는 많은 데이터 파손 오류를 검출하고 전체적인 데이터 무결성을 확인하기 위해 사용할 수 있는 암호화 해시 함수에 특히 해당됩니다.현재 데이터 입력의 계산된 체크섬이 이전에 계산된 체크섬의 저장된 값과 일치할 경우 데이터가 실수로 변경되거나 손상되지 않았을 가능성이 매우 높습니다.

체크섬 함수는 해시 함수, 지문, 랜덤화 함수 및 암호화 해시 함수와 관련되어 있습니다.그러나 이러한 개념들은 각각 다른 적용분야를 가지며 따라서 설계목표가 다르다.예를 들어 문자열의 시작을 반환하는 함수는 일부 응용 프로그램에 적합한 해시를 제공할 수 있지만 결코 적절한 체크섬이 되지 않습니다.체크섬은 대규모 인증 알고리즘에서 암호화 프리미티브로 사용됩니다.이러한 두 가지 특정 설계 목표가 있는 암호화 시스템의 경우 HMAC를 참조하십시오.

체크 디짓과 패리티 비트는 체크섬의 특수한 경우로, 작은 데이터 블록(사회보장번호, 은행 계좌번호, 컴퓨터 워드, 싱글바이트 등)에 적합합니다.일부 오류 수정 코드는 일반적인 오류를 탐지할 뿐만 아니라 특정 상황에서 원래 데이터를 복구할 수 있는 특수 체크섬을 기반으로 합니다.

알고리즘

패리티 바이트 또는 패리티 워드

가장 간단한 체크섬 알고리즘은 이른바 세로 패리티 체크로, 데이터를 고정 비트수 n의 "워드"로 분할한 다음 모든 워드의 배타적 또는 (XOR)을 계산합니다.결과는 추가 단어로 메시지에 추가됩니다.간단히 말하면, 이는 단어 끝에 비트를 추가하여 짝수인 '1'이 있음을 보증하는 것을 의미합니다.메시지의 무결성을 확인하기 위해 수신자는 체크섬을 포함한 모든 워드의 배타적 또는 배타적 값을 계산합니다.결과가 n개의 0으로 구성된 워드가 아닌 경우 수신자는 전송 오류가 [3]발생했음을 인식합니다.

이 체크섬을 사용하면 메시지의 1비트 또는 홀수 비트를 플립하는 모든 전송 오류가 잘못된 체크섬으로 검출됩니다.단, 두 비트가 서로 다른 두 단어로 같은 위치에 있을 경우 두 비트에 영향을 미치는 오류가 검출되지 않습니다.또, 2개 이상의 워드의 스왑은 검출되지 않습니다.영향을 받는 비트가 독립적으로 랜덤으로 선택되면 2비트 오류가 검출되지 않을 확률은 1/n입니다.

합보

이전 알고리즘의 변형은 모든 "words"를 부호 없는 이진수로 추가하고 오버플로 비트를 폐기하고 체크섬으로 두 개의 보완을 추가하는 것입니다.메시지를 검증하기 위해 수신자는 체크섬을 포함한 모든 단어를 동일한 방법으로 추가합니다.결과가 0으로 채워진 단어가 아닌 경우 오류가 발생했을 수 있습니다.이 모델도 싱글비트 오류를 검출하지만 SAE J1708에서는 [4]프로 모듈러 합계가 사용됩니다.

위치에 의존하다

위에서 설명한 단순한 체크섬에서는 데이터 워드의 순서를 변경하거나 모든 비트가 0으로 설정된 워드를 삽입 또는 삭제하는 등 여러 비트에 동시에 영향을 미치는 몇 가지 일반적인 오류를 감지하지 못합니다.Fletcher의 체크섬, Adler-32 및 Cyclic Redundancy Check(CRC; 순회용장검사) 등 실제로 가장 많이 사용되는 체크섬알고리즘은 각 워드의 값뿐만 아니라 시퀀스 내에서의 위치도 고려함으로써 이러한 약점을 해결합니다.이 기능을 사용하면 일반적으로 체크섬 계산 비용이 증가합니다.

퍼지 체크섬

퍼지 체크섬의 개념은 스팸으로 의심되는 여러 ISP에서 공동 데이터베이스를 구축하여 전자 메일 스팸을 탐지하기 위해 개발되었습니다.이러한 스팸의 내용은 종종 세부 사항이 다를 수 있으며, 이로 인해 일반 체크섬이 비활성화됩니다.반면 "퍼지 체크섬"은 본문 텍스트를 특성 최소값으로 줄인 다음 일반적인 방법으로 체크섬을 생성합니다.따라서 약간 다른 스팸 이메일이 동일한 체크섬을 생성할 가능성이 크게 높아집니다.ISP와 협력하고 있는 ISP의 스팸 검출 소프트웨어(SpamAssin 등)는 모든 전자 메일의 체크섬을 DCC 등의 집중형 서비스에 송신합니다.전송된 퍼지 체크섬의 수가 특정 임계값을 초과하면 데이터베이스는 이것이 스팸을 나타낼 수 있음을 확인합니다.ISP 서비스 사용자는 마찬가지로 각 전자 메일에 퍼지 체크섬을 생성하고 스팸 [5]가능성을 서비스에 요구합니다.

일반적인 고려 사항

m비트 길이의 메시지는 m차원 하이퍼큐브의 코너로 볼 수 있습니다.n비트 체크섬을 생성하는 체크섬알고리즘의 효과는 각 m비트메시지를 m + n 차원으로 큰 하이퍼큐브의 모서리에 매핑하는 것입니다.이 하이퍼큐브의 두 모서리는 수신 가능한m + n 모든 메시지를 나타냅니다.유효한 수신 메시지(체크섬이 올바른 메시지)는 모서리가 2개뿐인 작은m 세트로 구성됩니다.

단일 비트 전송 오류는 유효한 코너(올바른 메시지 및 체크섬)에서 m개의 인접 코너 중 하나까지의 변위에 해당합니다.k비트에 영향을 미치는 오류는 메시지를 올바른 코너에서 k단계 떨어진 코너로 이동합니다.양호한 체크섬알고리즘의 목적은 유효한 코너를 서로 가능한 한 멀리 두고 "일반적인" 전송 오류가 유효하지 않은 코너로 끝날 가능성을 높이는 것입니다.

「 」를 참조해 주세요.

일반적인 토픽

오류 정정

해시 함수

파일 시스템

  • ZFS – 체크섬을 사용하여 자동 파일 무결성 검사를 수행하는 파일 시스템

관련 개념

레퍼런스

  1. ^ "Definition of CHECKSUM". www.merriam-webster.com. Archived from the original on 2022-03-10. Retrieved 2022-03-10.
  2. ^ Hoffman, Chris. "What Is a Checksum (and Why Should You Care)?". How-To Geek. Archived from the original on 2022-03-09. Retrieved 2022-03-10.
  3. ^ Fairhurst, Gorry (2014). "Checksums & Integrity Checks". Archived from the original on April 8, 2022. Retrieved March 11, 2022.
  4. ^ "SAE J1708". Kvaser.com. Archived from the original on 11 December 2013.
  5. ^ "IXhash". Apache. Archived from the original on 31 August 2020. Retrieved 7 January 2020.

외부 링크

Wikibook Algorithm Implementation에는 다음 항목에 대한 페이지가 있습니다.체크섬