한글로는 순환 중복 검사 알고리즘이라고 정의되어 있다. 순환하면서 중복된 것(아마도 리던던시를 해석)을 체크하는 알고리즘 쯤으로 상상이 된다. 그런데 순환과 중복? 이건 무슨 말인가?
이름으로는 이 알고리즘은 어떤 것이라는 그림이 그려지지 않는다.
먼저 체크섬(Checksum) 알고리즘부터 이야기 하자.
체크섬 알고리즘은 전송받은 원데이타 값의 합과 체크섬 값을 바이트 단위로 더해서 합이 영(0)이 되면 전송 데이타가 원본과 일치함을 확인해주는 알고리즘이다.
상세히는 원데이타(보내고자 하는 데이타)의 합을 모두 더한 후, 그 값의 2의 보수를 체크섬 값(Checksum)으로 만들고 원데이타에 덧붙여 가칭 데이타섬을 송신한다. 그러면, 수신측에서는 데이타섬을 모두 더해서(바이트 단위) 그 합이 0이 되면 통신 과정에서 이상이 발생하지 않았다고 판정, 원데이타를 정상수신으로 판정한다.
더한 값의 2의 보수를 취한 이유는 당연히 더해진 값을 영(0)으로 만들기 위해서이다
그런데 체크섬 알고리즘은 에러 및 보안에 취약하다. 자릿수의 순서 바뀜과 같은 에러도 검출할 수 없으며, 그리고 체크섬 값을 알면 원 데이타가 쉽게 노출되기 때문이다.
그러면 어떻케 에러검출률을 올릴 수 있을까? 그리고 CRC라는 기술은 어디서 부터 발전된 것일까?
먼저 저 기술에는 수학적 지식 위에서 만들어졌다.
CRC를 설명하려면, 다항식이라는 용어가 등장한다.
다항식은 여러 항들이 있고 이러한 항들의 합으로 구성된다. 그리고 이러한 다항식의 덧셈, 곱셈, 나눗셈에 대해서는 이미 그 방법을 알고 있다고 가정한다.
그리고 갈루아필드(GF(2)). 이것은 2진수의 세계에서의 연산인 덧셈 및 곱셈은 항상 0 또는 1로 나타난다는 것이다.
$0+0=0\text{ } \text{ } \text{ } \text{ } 0*0=0$
$0+1=1\text{ } \text{ } \text{ } \text{ } 0*1=0$
$1+0=1\text{ } \text{ } \text{ } \text{ } 1*0=0$
$1+1=0\text{ } \text{ } \text{ } \text{ } 1*1=1$
윗 GF(2)의 덧셈은, XOR 연산이고 곱셈은 AND(&) 연산임을 알 수 있다.
다음 단계로는 암호화 기술이 등장하게 되었는데, 1회용 암호표를 이용하면 원래의 데이타를 이 암호표 없이는 복원할 수 없는 방법이 있음을 알아냈다. 그것은 XOR연산을 이용하는 것이다.
https://ko.khanacademy.org/computing/computer-science/cryptography/ciphers/a/xor-and-the-one-time-padKhan Academy
ko.khanacademy.org
그리고 암호화 알고리즘에서 나타난 것이 LFSR(Linear Feedback Shift Register)이다. 이를 위한 다항식(암호키/암호표)은 원데이타의 차수와 같은 다항식을 사용한다. 이러한 연구는 1940년대에 주로 이루어 졌다.
그리고 이러한 LFSR 기반 암호 기술은 데이터 전송 오류 검출을 위한 기술에 적용되는데, 이것이 CRC 기술이다. 이것은 체크섬(Checksum) 알고리즘과 비슷하게 원데이타에 CRC라는 것을 덧붙여, 수신단에서 이것을 이용하여 원데이타의 무결성을 검사하는 알고리즘이다. 또한 이 기술은 컴퓨터 네트워크 및 스토리지와의 통신을 위한 수단이기 때문에 암호학 알고리즘에서 출발한 기술이지만 암호키는 미리 정해진 값을 사용하게 된다.
즉, 암호화와 다른점은 다항식의 최대 차수 및 다항식의 탭(2 진 코드로 보면 값이 1, 다항식에서는 차수가 존재하는 항)은 통신선로에 따라 최대에러감지를 위해서 조정된 표준의 다항식을 사용한다는 점이다.
그러므로 CRC(Cyclic Redundancy Check)기술은 수학적 정의 및 암호학 이후에 나온 최신 기술이라고 볼 수 있다.
(CRC 코드는 해밍코드와 달리 에러정정은 할 수 없다고 하는데 위키를 보면 또 할 수 있는 방법이 있다고 한다. 아마도 이 기술이 계속해서 발전하고 있기 때문인 듯 하다.)
이상의 내용을 가지고 본인의 CRC를 만들어 보겠다.
먼저 아주 원시적인 방법, 이렇케 하면 될 것 같다라는 느낌으로 적어본다.
본인의 후진 방법
(요약: 암호키로 나누고, 나머지를 전송한 후 이 나머지 값을 이용해서 전송된 데이타가 올바른지 검증한다.)
원 데이타를 특정 값(암호키)로 나눈 나머지(RC:Remainder Check) 값을 찾은 후 이를 같이 전송한다. 원격지에서는 전송받은 수신데이타에서 나머지 값을 빼준다. 이 후 앞에서 사용한 약속된 특정 값(암호키)로 나누어서 나머지가 0이면 전송된 데이타(원 데이타와 나머지 값)이 오류없이 전송되었을 확인해 준다.
이 방법과 체크섬과의 공통점은 체크섬 방식과 같이 더해주는 값을 사용한다는 점이다. 즉, 나머지 값을 더해서 원 데이타의 올바른 전송 유무를 확인할 수 있다는 점이다. (체크섬은 이 값을 더해서 오류를 체크한다는 의미로 해석되니 용어가 잘 만들어진 것 같다.)
그러나, “본인의 후진 방법”이 체크섬 알고리즘과 다른 이유는 데이타의 값을 바이트 단위로 더한 후, 체크섬 값을 구하지 않고, 암호키를 사용해서 원 데이타를 나눈 후 그 나머지(Remainder) 값을 가지고서 원 데이타의 오류를 체크한다는 점이다. 이렇케 하면 그 암호키를 모르면 암호키의 차수가 커질수록 원래의 데이타 값이 어떤 건지 알아내기 어려워진다는 장점도 가지고 있다.
위 알고리즘을 3자리의 십진법에서 설명하면,
송신 측:
401을 전송하려한다. 약속된 특정 값은 내 맘(암호키)이다. 101로 하자. 401을 101로 나눈 나머지를 구한다.
=>401 mod 101=98
그럼 나머지=98
401과 98을 전송한다.
수신측:
401과 98을 수신했다. 401에서 98을 뺀다.
=>401-98=303
303을 약속된 암호키(101)로 나눈다.
=>303 mod 101 = 0
즉, 영(0)이 되면, 원 데이타의 값이 401였고 받은 데이타도 401이라 전송중 에러가 발생하지 않았다고 말할 수 있다.
그런데 요렇케 하는 것이 아니라고 한다.
손으로 하는 CRC 알고리즘
(요약: 암호키와 XOR 연산을 진행한 후 리던던시를 찾고 이 리던던시를 이용해서 원 데이타의 완결성을 체크하는 것을 손으로 한 번 해봄.)
컴퓨터 암호화 알고리즘은 XOR 연산을 통해서 원래의 데이타를 모두 숨기고 싶어한다. 그리고 CRC 기술은 이것을 기반으로 발전되었다라고 했으므로 XOR 연산을 해보자.
(나누기는 장제법을 이용해서 차수를 맞추어 빼주는 작업을 하는데 이 2진수에서는 뺄셈연산은 덧셈과 같다.)
1. 데이타를 나누는 다항식을 정한다. 암호키(다항식)를 정한다.
앞에서 언급했듯이 특정선로에서는 특정 암호키를 사용한다고 했다. 약속된 수(암호키)의 하나인 다항식으로 하나 가져왔다.
CRC-8 = $x^{8} + x^2 + x + 1$
2. CRC-8의 차수가 8이므로 원데이타의 차수에 더해준다.
다항식에서는 $x^8$을 원 데이타에 곱해주라는 말이며 이렇케 되면 2 진수 원데이타에는 영(0)이 8개 추가된다.
여기서 원데이타를 $1011_{(2)}$라고 하면, 원 데이타는 1011 0000 0000 값으로 변형된다. (추가된 0의 위치에 무언가 들어갈 것이다.)
1011 0000 0000
XOR 1000 0011 1
—————————–
0011 0011 1000
XOR 10 0000 111
—————————–
0001 0011 0110
XOR 1 0000 0111
—————————–
0 0011 0001
여기서 XOR의 결과를 나머지(Remainder)라고 하면 나눗셈의 결과로 해석할 수 있으므로 리던던시(Redundancy)라고 하자. 리던던시는 중복의 의미도 있지만 덤 또는 여유분 이라는 뜻도 있다.
(나머지 연산을 수행한 것이 아니라 XOR연산을 해주었기 때문에 리메인더라고 하기 싫었을 것 같다.)
3. 차수가 증가된 데이타에 리던던시를 덧붙여 전송한다.
더해서 전송한다는 의미와도 같다. 왜냐면 차수가 증가되었었기 때문이다.
(원데이타의 총 차수를 다항식 차수만큼 늘려준 이유이다. 여기에 리던던시를 넣어주게 된다.)
그러므로 전송되는 정보는 아래와 같을 것이다.
1011 0011 0001
4. 수신된 데이타를 다시 CRC-8 암호키와 XOR연산한다.
1011 0011 0001
XOR 1000 0011 1
—————————–
0011 0000 1001
XOR 10 0000 111
—————————–
0001 0000 0111
XOR 1 0000 0111
—————————–
0000 0000 0000
XOR을 반복했더니 영(0)이 되었다. (1이 아닌 0의 자릿수에 대해서는 그냥 넘겼다.)
위 과정을 살펴보니,
최상위비트부터 XOR을 진행, 0으로 만들어 가면서 후단으로 정보를 이동하면서 진행한다고 생각된다. 그리고 마지막에 남은 것은 그 정보 리던던시(Redundancy)라 할 수 있겠다.
먼가 남은 쪼가리. 그리고 이게 R(리던던시)다. 즉, CRC에서 R은 Remainder의 약자가 아니라 Redundancy(이하 ‘리던던시’)의 약자이다.
원래의 표준 CRC 알고리즘 방법
표준 CRC 알고리즘은 “손으로 하는 CRC 알고리즘”에 순환시프트레지스터(linear Shift Feedback Register)라는 하드웨어로 구현된다. 물론 소프트웨어로도 구현이 되지만 처리속도가 많이 걸린다고 한다.
여기서는 LSFR에 대한 설명은 그냥 넘기고(잘 모른다) 왜 Cyclic이라는 용어가 추가되어서 Cyclic Redundancy Check 알고리즘이라 불리게 되었는지 설명만 하려고 한다.
CRC-8도 너무 커서 CRC-4에서 설명하자면, LSFR로 구현하면 아래의 위키의 설명처럼 원형의 순환되는 리던던시 값을 가지게 된다.
그리고 위 알고리즘을 소프트웨어로 구현하면, CRC-16, CRC-32 이상으로 갈 수록 그 연산시간은 매우 크게 증가하게 될 것이다. 그러므로 소프트웨어로 구현할 때는, 테이블표를 만들어 놓고 입력데이타의 CRC-16 또는 CRC-32의 리던던시 값을 바로 읽어와서 처리해주는 방식을 사용한다.
(그래서 가끔 통신관련 C코드를 보면 16진수 배열을 직접 입력해 놓을 것을 볼 수 있던 이유이다.)
그리고 드디어 CRC의 첫 번째 C가 보인다. C는 Cyclic의 약자이다. 원형회전을 가지는 코드로 구성되는 리던던시를 이용한 에러검출 알고리즘으로 CRC라 한 것 같다.
(솔직히 100% 맞는 이야기인지는 모르겠다. 포스팅을 작성하다가 보니 매우 오래전에 이렇케 설명하는 것을 들어본 것 같아서 써 놓았을 뿐이다. 틀린 정보이면 댓글로 설명을 부탁드린다.)
그래서 CRC 알고리즘에 대해서 다시 정리해 보자면,
원형회전을 가지는 코드로 구성되는 리던던시(덤)을 이용한 에러검출 알고리즘이다. 줄여서는… “순환성 덤코드 체크” 알고리즘이라 말하고 싶다.
CRC를 계산하는 프로그램을 보면, 초깃값을 자꾸 이야기 하는데 그 이유는:
데이타가 연속적으로 들어와 초깃 값을 마지막 CRC 값으로 해서 이어서 진행할 지, 아니면 초기화 시켜서 진행할지에 따라서 달라지므로 초깃값을 물어보는 것으로 이해했다.
끝으로, 아래에는 자주 사용하는 CRC-16 다항식 2 개가 정의되어 있다.
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 다항식으로 CRC-16-ModBus 다항식을 주로 접해 보았다.
그런데 구글링을 해서 찾은 CRC체크 프로그램을 보면 CRC-16-ModBus의 다항식 값을 0xA001로 사용한 것을 보게된다. 이것은 신호를 차수가 낮은 것부터 높은 것으로 전송할 때 이 값을 사용한다고 되어 있는데 아래의 이유 때문이다.
1000 0000 0000 0101 (0x8005)
lsb를 msb가 되도록 순서를 모두 바꾸어 놓는다. 이유는 데이타를 머리부터 줄까? 꼬리부터 줄까? 하다가 꼬리부터 준 것이다.
1010 0000 0000 0001 (0xA001)