CRC(Cyclic Redundancy Check) 알고리즘

한글로는 순환 반복 체크 알고리즘이라고 정의되어 있다. 순환하면서 반복하는 알고리즘 쯤으로 상상이 된다. 그런데 순환과 반복? 이건 같은 말 아닌가?

 

이름으로는 이 알고리즘은 어떤 것이라는 그림이 그려지지 않는다.

 

먼저 체크섬부터 이야기 하자. (CRC의 C는 체크섬이 아니다)

체크섬은 전송받은 데이타 값 + 체크섬값이 영이 되면 전송 데이타가 원본과 일치한다는 알고리즘이다. 체크섬값은 원데이타의 합을 모두 더한 후, 그 값의 2의 보수를 체크섬 값으로 한다. 송신측은 원데이타와 체크섬값을 수신측에 전송하면, 수신측에서는 원데이타와 체크섬값을 모두 더해주면 0이 되는 원리를 이용한다. 더한 값의 2의 보수를 취한 이유는 더하는 값을 음수로 만들기 위해서이다.

 

음수의 보수표현

 

그런데 체크섬은 사실 에러 및 보안에 취약하다. 또한 에러발생 시, 원래의 데이타를 복원하기도 어렵다. (어려운지 불가능한지는 모른다.)

 

그래서 여러가지 방법을 찾으려고 했는데 아마도 본인이라면 이런 방법을 썼을 것 같다.

 

본인의 방법:

원 데이타를 특정 값으로 나눈 나머지(RC:Remainder Check)를 원 데이타와 함께 원격지로 전송한다. 원격지에서는 전송받은 수신데이타(원 데이타와 RC)에서 RC값을 원 데이타에서 빼준다. 이 후 앞에서 사용한 약속된 특정 값으로 나누어서 나머지가 0이면 전송된 데이타(원 데이타와 RC)가 오류없이 전송되었을 확인해주는 알고리즘이다.

왜 이러한 방법을 고안했을까? 수신측에서 특정값을 모르면 원래의 데이타를 복원할 수 없어서이다. (암호학에서 이리 말하는데 머 그런가 보다)

 

위 알고리즘을 3자리의 십진법에서 설명하면,

 

송신 측:

401을 전송하려한다. 약속된 특정 값은 내 맘이다. 101로 하자.

401을 101로 나눈 나머지를 구한다. 

=>401 mod 101=98

그럼 나머지=98

401과 98을 전송한다.

 

수신측:

401과 98을 수신했다.

401에서 98을 뺀다.

=>401-98=303

303을 내 맘 101로 나눈다. 

=>40097 mod 101 = 0

당연히 0이 된다. 왜냐하면 나머지를 빼 주었으니까.

 

그러나, 표준 CRC 알고리즘 설명에서는 위 방법과 전혀 다른 방법을 사용한다.

CRC알고리즘은 XOR연산을 통해서 원래의 데이타를 모두 숨기고 싶어한다. (요 해석이 맞는지는 모르나 하여튼 하는 방법이 이렇다). 

 

1. 데이타를 나누는 수를 정한다. (요건 같다)

마음대로 정하면 나중에 데이타를 복구 할 수 없다. 그래서 특정프로토콜에서는 이런 암호키는 정해 놓았다. 약속된 수(암호키)를 아래 처럼 다항식으로 표시해보자.

 

CRC-8 = $x^{8} + x^2 + x + 1$

 

왜 이런 다항식으로 쓸까? 아래처럼 쓰기 싫어서이다.

1 0000 0111으로 쓰기 싫어서이다.

또한 다항식으로 쓰면 나눈 후 데이타를 조작하기 위한 차수를 바로 알 수 있다. 여기서는 8임을 바로 알 수 있다.

 

그리고 차수의 1을 달나라로 보내면(왜 보내는가? 모른다. 아마도 최고 차수가 몇인지를 알려주려는 용도로 뿐이 안보인다.) 윗 값은 0x07이고 이것이 약속된 수이며 다항식 값 및 암호키 값이다. (아래에서는 다항식값, 암호키를 종종 섞어서 사용하나 같은 값이다.)

 

2. 원데이타의 최상위 비트부터 암호키와 XOR연산한다.

(XOR 연산은 원래 데이타를 숨기는 것에 목적이 있다.)

 

하나의 예를 들어보면서 계산해 보자. 11001이 데이타이고 1011이 암호키라고 가정하자. XOR을 이용하여 마치 나누기 연산하듯이 해준다. 그런데 여기서 주목! 원데이타의 차수를 다항식 차수 만큼 증가시킨 후 계산한다. 왜냐면, 원 데이타의 모든 정보를 감추기 위해서라고 생각하자.

그림 1. Redundancy를 만드는 과정

 

즉, 최상위비트부터 계속 0으로 만들어가면서 후단으로 정보를 이동하면서 진행한다고 생각한다. 그리고 마지막에 남은 것은 Redundancy라 할 수 있겠다. 먼가 남은 쪼가리. 그리고 이게 R이다.  CRC에서 R은 Remainder가 아니라 정보이다.

 

이것을 원데이타에 붙여서 시리얼로 전송한다. 

 

3. 함께 전송된 신호를 2단계에 했던 방식으로 다시 진행한다.

 

원데이타가 11001였다. 그리고 111이 들어올 것이다.

그러면 1100 1111로 보아도 될 것이다. 이것은 시리얼로 신호가 들어오기 때문에 하드웨어로 처리하기 쉽다고 한다.

 

들어온 데이타(원데이타+Redundancy)에 XOR연산자를 이용하여 나주기 하듯 계산해보자.

그림 2. Redundancy를 체크하는 과정

 

어렵쇼? Redundancy가 0이 되네! 왜 이럴까? 차수를 늘려주고 XOR연산을 한 후, 늘려진 차수에 Redundancy를 더해주는 것에 마법이 있는것 같다. 

 

그림 2에서 보니 연속된 XOR연산의 결과는 암호키 값을 만들어낸다. 왜 이러는 지는 모른다. 

       1011

xor  1011

--------------

       0000

 

정말 신기한데...  본인은 요 알고리즘으로 만든 CRC-16 ModBus 테이블을 이용해서 CRC체크를 이렇케 하는구나만 이해했을 따름이다.

 

그래도 위와 같이 설명하니, CRC(Cyclic Redundancy Check)의 Cyclic과 Check가 이해 될 것 같다. 반복해서 같은 연산을 진행하면 Redundancy가 체크되는 알고리즘이라는 것.

 

아래는 자주 사용하는 다항식이 정의되어 있다. 본 블로그에서는 CRC-16은 ModBus 다항식을 주로 사용한다. 

 

CRC-16-CCITT

• 다항식: $1x^{16} + 1x^{12} +1 x^5 + 1 (0x1021)$
• 특징: 통신 프로토콜에서 널리 사용되며, 연속적인 오류 검출에 효과적이다.

CRC-16-ModBus

• 다항식: $1x^{16} + x^{15} + x^2 + 1 (0x8005)$
• 특징: Modbus 프로토콜에서 사용되며, 산업 자동화 분야에서 널리 사용된다.

다항식으로 써 놓은 이유는 2진수의 진법을 고려한 것이다. 그리고 같은 CRC-16도 데이타 전송 시 적용받는 통신규약에 따라 다항식의 값을 여러가지로 나누어서 사용한다. 수학자들이 통신데이타를 올려 놓고, 이 중 주로 발생하는 특정 비트값에서의 에러를 감지하고자 가중치를 두어서 만든것 같은데 수학과가 아니라서 다행이다. 

 

구글링을 해서 CRC체크 프로그램을 보면 CRC-16-ModBus의 다항식 값을 0xA001로 사용한 것을 보게된다. 이것은 신호를 차수가 낮은 것부터 높은 것으로 전송할 때 이 값을 사용한다고 되어 있는데,

 

1000 0000 0000 0101 (0x8005)

lsb를 msb가 되도록 순서를 모두 바꾸어 놓는다. 이유는 데이타를 머리부터 줄까? 꼬리부터 줄까? 하다가 꼬리부터 준 것이다.

1010 0000 0000 0001 (0xA001)

 

끝으로, "본인의 방법"과 "표준CRC알고리즘"을 비교해 보았다.

	본인의 방법	표준 CRC 알고리즘
송신단	암호키로 나눈다	XOR연산을 나누기처럼 사용한다.
	나머지를 구한 후, 보수를 취해서 더해준다. (Remainder를 없애기 위해서)	차수 증가 후, 나머지를 구해서 더해준다. (Redundancy을 없애기 위해서)
수신단	수신데이타를 암호키로 나눈다.	XOR연산을 나누기처럼 사용한다.
	0임을 확인한다.	0임을 확인한다.

 

ChatGPT에 물어보니, 표준 CRC알고리즘에서는 갈루아필드를 만족하는 다항식을 사용한다고 한다. 가서 읽어 보았더니... 모르겠다. -_-;;;