'CRC-32'에 해당되는 글 1건

  1. 2009.11.06 What is CRC?

2009.11.06 09:53 Etc../Encryption


순환 중복 검사(巡環重復檢査), CRC(cyclic redundancy check)는 네트워크 등을 통하여 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크값을 결정하는 방식을 말한다.

데이터를 전송하기 전에 주어진 데이터의 값에 따라 CRC 값을 계산하여 데이터에 붙여 전송하고, 데이터 전송이 끝난 후 받은 데이터의 값으로 다시 CRC 값을 계산하게 된다. 이어서 두 값을 비교하고, 이 두 값이 다르면 데이터 전송 과정에서 잡음 등에 의해 오류가 덧붙여 전송된 것 임을 알 수 있다.

CRC는 이진법 기반의 하드웨어에서 구현하기 쉽고, 데이터 전송 과정에서 발생하는 흔한 오류들을 검출하는 데 탁월하다. 하지만 CRC의 구조 때문에 의도적으로 주어진 CRC 값을 갖는 다른 데이터를 만들기가 쉽고, 따라서 데이터의 무결성을 검사하는 데는 사용될 수 없다. 이런 용도로는 MD5 등의 함수들이 사용된다.


CRC는 가환환(commutative ring)의 나눗셈에 기반한다. 여기서 쓰이는 환은 법 2 (modulo 2) 정수에서 정의된 다항식의 환이다. 쉽게 말하면, 이는 한 비트의 계수를 갖는 다항식의 집합이고, 이 다항식들간의 사칙연산은 다시 계수들을 가장 아래 비트만 따도록 정의하여 한 비트 계수의 다항식으로 표현하도록 정의된다. 예를 들면:

(x2 + x) + (x + 1) = x2 + 2x + 1 = (x + 1)2

위 식에서 2는 이진수로 10이고, 따라서 정의에 의해서 가장 아랫자리 수(또는, 가장 아래 비트)인 0을 취하고 그 이상의 자리수는 버린다. 다음은 곱셈의 예이다:

(x2 + x)(x + 1) = x3 + 2x2 + x = x3 + x

더하기와 곱하기 말고 나누기도 정의할 수 있다. 예를 들어, x3 + x2 + xx + 1 로 나눈다고 해 보자.

x3 + x2 + x = (x + 1)(x2 + 1) − 1 = (x + 1)(x2 + 1) + 1.

으로 정리할 수 있다. 다시 말하면, 나눗셈의 몫은 x2 + 1 이고 나머지는 -1 이고, -1은 홀수이기 때문에 1이 된다.

모든 데이터 비트 스트림은 이러한 다항식의 계수로 상상할 수 있다. 즉, 101 은 0번자리가 1, 1번자리가 0, 2번자리가 1이므로, 다항식 x2 + 1에 해당한다고 볼 수 있다. CRC 값은, 정해진 특정 다항식으로 데이터 스트링으로 주어진 다항식을 나누어 그 나머지를 나타내는 특정 길이의 비트 스트링이 된다. 이 나머지를 구하는 간단하고 빠른 알고리즘은 잘 알려져 있다. CRC는 종종 체크섬(checksum)으로 불리는데, 엄밀히 말하면 나눗셈을 통해 얻어지는 CRC 값에는 옳지 않은 이름이다.

CRC의 중심을 이루는 알고리즘은 의사코드로 다음과 같이 쓸 수 있다:

function crc(bit array bitString[1..len], int polynomial) {
    shiftRegister := initial value // 보통 00000000 또는 11111111
    for i from 1 to len {
        if (shiftRegister의 최상위 비트) xor bitString[i] = 1
            shiftRegister := (shiftRegister left shift 1) xor polynomial
        else
            shiftRegister := shiftRegister left shift 1
    }
    return shiftRegister
}

(참고: 실제로는 여러 개의 최상위 비트들에 해당하는 shiftRegister의 표를 만들어서 한꺼번에 여러 비트를 처리해 속도를 높이는 방법을 쓰며, 특히 8비트 단위로 처리하는 방법이 많이 사용된다.)

위의 구현은 다음과 같은 두 가지 방법으로 고칠 수 있으며, 따라서 둘 중 하나를 적용하거나 둘 다 적용할 경우 CRC 값을 계산하는 네 가지 동등한 방법이 존재한다:

  1. shiftRegister를 비트 단위로 뒤집고, 각 단계에서 최하위 비트를 테스트한 뒤 오른쪽으로 1비트 쉬프트한다. 이 경우 polynomial의 값을 비트 단위로 뒤집어야 하고, 결과물 역시 비트 단위로 뒤집어진다.
  2. shiftRegister의 한 비트와 bitString의 한 비트를 xor하는 대신에, shiftRegisterbitString에서 polynomial에 설정된 비트에 해당하는 모든 비트들을 xor한 1비트 결과를 shiftRegister에 더한다. polynomial을 적당히 고치면 같은 나머지를 얻을 수 있다. 이 방법은 소프트웨어에서 구현하기는 힘들지만 하드웨어 구현에서는 종종 사용되며, CRC와 깊은 관련이 있는 선형 피드백 쉬프트 레지스터를 설명하는 데 자주 사용된다.

특정한 CRC는 사용되는 다항식으로 정의한다. n비트 CRC를 만드는 데는 xn + ... + 1 꼴의 n차 다항식이 필요하다. 이 다항식은 기본적으로 (n+1)비트 문자열로 나타낼 수 있지만, 차수가 가장 높은 xn 항의 계수는 항상 1이기 때문에 이 항을 빼고 n비트 문자열로 나타낼 수 있다. 예를 들어 CRC-16 표준에 사용되는 다항식인 x16 + x15 + x2 + 1은 비트 순서에 따라서 16진수 숫자 0x8005나 0xa001로 나타낼 수 있으며, 이더넷, FDDI, PKZIP, WinZip, PNG 등에서 널리 사용되는 CRC-32의 경우 0x04C11DB7 또는 0xEDB88320으로 쓸 수 있다.


출처: http://ko.wikipedia.org/wiki/%EC%88%9C%ED%99%98_%EC%A4%91%EB%B3%B5_%EA%B2%80%EC%82%AC

'Etc.. > Encryption' 카테고리의 다른 글

Cryptography!  (0) 2010.06.16
What is CRC?  (0) 2009.11.06
What is Padding?  (0) 2009.10.31
Posted by LinkC
 TAG , ,
이전버튼 1 이전버튼

블로그 이미지
LinkC

태그목록

Tistory Cumulus Flash tag cloud by BLUEnLIVE requires Flash Player 9 or better.

공지사항

Yesterday48
Today12
Total328,654

달력

 « |  » 2019.5
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  

최근에 받은 트랙백

글 보관함


. .