BLOG ARTICLE Algorithm 궁금하니? | 4 ARTICLE FOUND

  1. 2009.10.22 해쉬 알고리즘
  2. 2009.03.10 대칭키 암호화 이야기
  3. 2008.01.15 CRC : CRC-16, CRC-32에 대한 설명과 구현
  4. 2008.01.15 CRC란 무엇인가?

해쉬 알고리즘

Algorithm 궁금하니? 2009. 10. 22. 21:18

출처: http://blog.naver.com/eunyeop?Redirect=Log&logNo=130008937107

 

해쉬 알고리즘

해쉬함수($ H$혹은 Hash로 표기)는 임의의 길이의 입력 메세지를 고정된 길이의 출력값으로 압축시키는 함수이다. 데이타의 무결성 검증, 메세지 인증에 사용한다. 해쉬함수는 다음의 성질을 만족해야 한다.

  • 일방향성 : 주어진 해쉬값 $ h$에 대해서 $ H(x)=h$를 만족하는 $ x$를 찾는것이 계산적으로 불가능
  • 강한 충돌 회피성 : 주어진 $ x$에 대해 $ H(x)=H(y)$를 만족하는 임의의 입력 메세지 $ y( ne x)$를 찾는 것이 계산적으로 불가능

일반적으로 널리 쓰이는 해쉬함수로는 MD5, SHA1, RMD160, TIGER 등이 있다.


표 4: 해쉬 알고리즘
알고리즘 출력길이 블럭의 크기 라운드 수 Endianness
MD5 128 512 64 Little
SHA1 160 512 80 Big
SHA256 256 512 64 Big
SHA384 384 1024 80 Big
SHA512 512 1024 80 Big
RMD128 128 512 128 Little
RMD160 160 512 160 Little
RMD256 256 512 128 Little
RMD320 320 512 160 Little
HAS160 160 512 80 Little
TIGER 192 512 56 Little

  • MD5는 널리 사용된 해쉬 알고리즘이지만, 충돌 회피성에서 문제점이 있다는 분석이 있으므로 기존의 응용과의 호환으로만 사용하고 더 이상 사용하지 않도록 하고 있다.
  • SHA1은 DSA에서 사용하도록 되어 있으며 많은 인터넷 응용에서 default 해쉬 알고리즘으로 사용된다.
  • SHA256, SHA384, SHA512는 AES의 키 길이인 128, 192, 256 비트에 대응하도록 출력길이를 늘인 해쉬알고리즘이다.
  • RMD128, RMD160는 RIPE 프로젝트의 RIPEMD나 MD4, MD5를 대신하기 위하여 디자인된 해쉬 알고리즘이다. 128 비트의 출력을 내는 RMD128은 역시 충돌 회피성에서 문제점이 있다. RMD160은 효율성은 떨어지지만 안전성을 높인 것으로 많은 인터넷 표준들에서 널리 채택되고 있다.
  • RMD256과 RMD320은 각각 RMD128과 RMD160을 확장한 것이다.
  • HAS160은 국내 표준 서명 알고리즘 KCDSA를 위하여 개발된 해쉬 함수이다. MD5와 SHA1의 장점을 취하여 디자인 되었다. 현재 TTA 표준으로 제정중에 있다.
  • TIGER는 64 비트 프로세서에 최적화되어서 64 비트 프로세서에서는 매우 빠르다.

MAC 알고리즘

MAC(Message Authentication Code)은 파일내용의 변경 유무나 통신상에서 오가는 데이타의 무결성을 체크하는데 이용된다.

  • 해쉬함수 기반 : HMAC, KMAC
  • 블럭 암호 기반 : CBC-MAC(ISO 9797-1), RIPE-MAC, XCBC
  • 모듈라 곱셈 기반 : UMAC

HMAC

HMAC (RFC 2104)은 해쉬함수를 사용하여 MAC을 생성하는 방법이다

$ H(  (K oplus {rm opad}) vertvert  H( (K oplus {rm ipad}) vertvert  text ) ).$
  • $ H$ : 해쉬함수. MD5, SHA1, RMD160, HAS160, TIGER 등을 이용.
  • $ K$ : 비밀키. 키의 길이에는 제한이 없다.
  • opad : 0x5C를 블럭의 크기(바이트)만큼 연접한것.
  • ipad : 0x36를 블럭의 크기(바이트)만큼 연접한것.
  • 출력의 일부만을 MAC으로 사용하는 truncation을 사용하기도 한다.

KMAC

해쉬함수를 이용한 MAC으로 HMAC이 나온 이후 잘 사용되지 않는다. 예를들어 MD5에 대한 KMAC은 다음과 같다.

$displaystyle K'$ $displaystyle = K vertvert$   (MD5 padding)$displaystyle ,$    
$displaystyle Data'$ $displaystyle = K' vertvert Data vertvert K ,$    
$displaystyle {rm MAC}$ $displaystyle = {rm MD5}(Data')$    



CBC-MAC

CBC-MAC은 $ n$-비트 블럭 암호의 CBC 모드를 이용한 MAC이다.

  • ISO 9797-1의 CBC-MAC-MAC1, MAC2, MAC3, MAC4, MAC5, MAC6.
  • RIPE-MAC (RIPE 프로젝트)
  • XCBC (Crypto 2000)

ISO/IEC 9797-1의 CBC-MAC

ISO 9797-1의 CBC-MAC 알고리즘의 순서는 다음과 같다.

  1. Padding
  2. Splitting
  3. Initial transformation
  4. Iteration
  5. Output transformation
  6. Truncation
  • Padding:
    • PAD1 - zero padding
    • PAD2 - one-zero padding
    • PAD3 - PAD1을 한 뒤, 최상위 블럭에 데이터 길이를 추가
  • splitting:
    • 패딩된 데이타를 블럭의 크기로 나누어서 $ D_1, cdots, D_{q}$의 데이타 블럭을 만든다.
  • Initial transformation:
    • IniTrans1 - $ H_{1}=e_{K}(D_{1})$
    • IniTrans2 - $ H_{1}=e_{K''}(e_{K}(D_{1}))$
  • iteration: $ i=2, cdots,q$ 에 대해서 $ D_{i}$에 CBC 모드의 블럭 암호를 적용한다.
    $ H_{i}=e_{K}(D_{i}oplus H_{i-1}) quad$ for $ i=2, cdots,q$.
  • Output transformation:
    • OutTrans1 - $ G=H_{q}$
    • OutTrans2 - $ G=e_{K'}(H_{q})$
    • OutTrans3 - $ G=e_{K}(d_{K^{prime}}(H_{q}))$
  • truncation: $ G$의 상위 $ m$ 비트를 truncate하여 MAC값으로 한다.

여기서 initial transformation과 output transformation을 조합하는 방법에 따라서 여러가지의 MAC 알고리즘으로 나뉜다.

  • MAC 1 : IniTrans1 + OutTrans1.
    그림 6: MAC 1

    MAC 1이 안전성측면에서 가장 취약하지만 현재 대부분의 표준에서는 zero padding(Pad1)을 한 뒤의 MAC 1을 사용하고, 다른 모드는 실제로 쓰이는 표준이 별로 없다.

  • MAC 2 : IniTrans1 + OutTrans2
    그림 7: MAC 2
  • MAC 3 : IniTrans1 + OutTrans3
    그림 8: MAC 3
  • MAC 4 : IniTrans2 + OutTrans2
    그림 9: MAC 4
  • MAC 5

    MAC 5는 MAC 1을 parallel하게 두번 사용하여 얻는다. 주어지는 key는 $ K$ 하나이며 $ K$로 부터 각각의 MAC 1 알고리즘에서 사용할 두 개의 키 $ K_{1}$과 $ K_{2}$를 유도해서 사용하는데, $ K_{1}$과 $ K_{2}$는 서로 달라야 한다. 구체적인 MAC값은 $ K_{1}$을 사용한 $ {rm MAC_{1}}$의 값과 $ K_{2}$을 사용한 $ {rm MAC_{2}}$의 값을 XOR하여 구한다.

    $ {rm MAC:=MAC_{1} oplus MAC_{2}}$.
  • MAC 6

    MAC 6은 MAC 4를 parallel하게 두번 사용하여 얻는다. 주어지는 키는 ($ K$, $ K'$)이고 이로부터 각각의 MAC 4 알고리즘에서 사용한 두쌍의 키 $ (K_{1},K_{1}')$과 $ (K_{2},K_{2}')$을 유도한다.

    $ (K_{1},K_{1}')$를 사용한 MAC 4 알고리즘으로 $ {rm MAC_{1}}$을 구하고, $ (K_{2},K_{2}')$를 사용한 MAC 4 알고리즘으로 $ {rm MAC_{2}}$을 구하여 XOR하여 MAC을 구한다.

    $ {rm MAC:=MAC_{1} oplus MAC_{2}}$.

RIPE-MAC

RIPE-MAC은 RIPE 프로젝트의 하나로 디자인된 CBC-MAC이다.

  • ISO 9797-1을 바탕으로 디자인
  • DES와 2-key 3DES를 사용
  • 패딩방법 : PAD2를 한 뒤, 최하위 블럭에 데이타 길이를 추가
  • 변형된 CBC 모드를 사용
  • 키 유도 방법을 명확히 하였다.
  • truncation을 하지 않음.

패딩된 데이터를 블럭의 크기대로 $ D_1, D_2, cdots, D_q$로 나누고 다음과 같은 변형된 CBC 모드를 사용하여 $ H_q$를 구한다.

그림 10: RIPE-MAC

$ H_q$를 구하면 $ K'$을 다음과 같이 구한다.

begin{displaymath} K' = begin{cases} K oplus {tt0x F0F0F0F0 F0F0F0F0}, & mb... ...(K_1' vertvert K_2'), & mbox{ if } e={rm 3DES}. end{cases}end{displaymath}

단 여기서 $ K_i' = K_i oplus {tt0x F0F0F0F0 F0F0F0F0}$ 이다. 그러면 MAC은 다음과 같다.

$displaystyle {rm MAC} = e_{K'}(H_q).$

XCBC-MAC

  • 불필요한 패딩을 없앰.
  • 암호화 키를 1개만 사용하여 key scheduling 시간을 줄임.

데이터에 패딩할때, 데이터 블럭의 수가 증가하지 않도록 데이터의 길이가 $ n$ 비트의 배수일 때와 아닐 때로 나누어서 $ n$ 비트의 배수가 아닌 경우에만 최소길이의 ` $ {tt 10cdots 0}$'를 덧붙여서 데이터의 길이를 $ n$ 비트의 배수로 만든다.

XCBC-MAC은 세개의 키 $ (K_1, K_2, K_3)$가 필요한데, $ K_1$은 암호화할 때 필요한 암호화 키이고 $ K_2, K_3$는 데이터의 마지막 블럭에만 적용되는 Input whitening 키로서 데이터의 패딩방법에 따라서 $ K_2$ 혹은 $ K_3$가 선택된다.

그림 11: XCBC-MAC

패딩된 데이터를 블럭의 크기로 나누어 $ D_1, D_2, cdots, D_q$로 만들면 $ H_{q-1}$까지는 $ IV=0$인 보통의 CBC 모드로 구해진다. 마지막 $ H_q (={rm MAC})$은 패딩이 일어난 경우와 일어나지 않은 경우로 나누어 다음과 같이 구한다.

begin{displaymath} H_q = begin{cases} e_{K_1}(H_{q-1} oplus D_q oplus K_2), ... ...& mbox{데이터의 길이가 $n$ 비트의 배수가 아닐 때}. end{cases}end{displaymath}

UMAC

  • J. Black et el.에 의해서 설계(Crypto'99)
  • 16 비트/32 비트 곱셈을 사용한 universal hash 함수를 이용
  • 곱셈이 빠르게 구현되는 프로세서 환경에서는 기존의 HMAC이나 CBC-MAC보다 매우 빠르게 구현될 수 있다.
  • 워드의 길이만큼 차례로 연접하여 구해짐. UMAC의 출력의 길이가 길어질수록 길이에 비례하여 안전해지고 UMAC을 구하는데 걸리는 시간도 길이에 비례하여 증가하게 된다.


표 5: UMAC의 파라미터
  파라미터 가능한 값 Default 설명
$ w$ WORD-LEN 2, 4 4 word의 길이(바이트)
$ l$ UMAC-OUTPUT-LEN 1, 2, $ cdots$, 31, 32 8 UMAC의 출력 길이(바이트)
$ n$ L1-KEY-LEN 32, 64, 128, $ cdots$, $ 2^{28}$ 1024 Layer1의 NH에서 처리되는 메세지 단위(바이트)
$ k$ UMAC-KEY-LEN 16, 32 16 사용자 키 길이(바이트)
$ s$ L1-OPERATION-SIGN SIGNED, UNSIGNED UNSIGNED  
$ e$ ENDIAN-FAVORITE BIG, LITTLE LITTLE  


각 파라미터는 주어진 word의 길이($ w$)에 대하여 임의로 정해질 수 있으며 그 때의 UMAC의 버젼은 UMAC- $ w/l/n/k/s/e$로 나타내고 특히 default UMAC은 UMAC32라고 한다. 그리고 UMAC16은 UMAC-2/8/1024/16/SIGNED/LITTLE을 의미한다.


표 6: UMAC의 안전성
UMAC-OUTPUT-LEN(bytes) UMAC의 위조 확률
2 $ 2^{-15}$
4 $ 2^{-30}$
8 $ 2^{-60}$
16 $ 2^{-120}$


그러면 UMAC은 다음과 같은 과정으로 구한다.

  • INPUT :

    $ K$ : key string of length UMAC-KEY-LEN bytes.
    $ M$ : message string of length less than $ 2^{64}$ bytes.
    $ Nonce$ : nonce string of length 1 to 16 bytes.

  • OUTPUT :

    $ AuthTag$ : string of length UMAC-OUTPUT-LEN bytes.

  • STEPS :
    1. begin{displaymath}HashedMessage = begin{cases} mbox{UHASH-32}(K,M), & mbox{i... ...UHASH-16}(K,M), & mbox{if } mbox{tt WORD-LEN}=2. end{cases}end{displaymath}
    2. $ Pad = {rm PDF}(K, Nonce)$.
    3. $ AuthTag = Pad oplus HashedMessage$.

UHASH함수는 임의의 길이의 입력 메세지에 대하여 사용자 키 $ K$를 가지고 UMAC-OUTPUT-LEN의 길이로 출력하는 함수(UHASH-32는 32 비트 word size 프로세서에 적용되며 UHASH-16은 16 비트 word size 프로세서에 적용되는 함수). 다음의 3 계층으로 이루어진다.

  • L1-HASH
  • L2-HASH
  • L3-HASH

키 $ K$로 부터 새로운 키 블럭을 유도하여 3 계층을 거치면 word size만큼의 결과를 출력한다. 원하는 UMAC-OUTPUT-LEN 바이트의 길이가 될때까지 새로운 키 블럭을 유도하여 3 계층이 반복적으로 적용한 결과를 연접한다.

L1-HASH-32는 메세지 $ M$을 L1-KEY-LEN 바이트 단위로 나누어 각 단위 메세지를 NH-32(아래 그림 참조)에 적용 8 바이트를 얻고 이것을 차례로 연접시킨다.

그림 12: NH-32

L1-HASH-32가 여전히 상대적으로 긴 출력을 가지므로 L2-HASH-32는 'polynomial hash function' POLY를 이용하여 16 바이트의 고정된 길이로 압축한다.

L2-HASH-32 함수를 통하여 16 바이트의 고정된 길이로 압축되면 L3-HASH-32를 거쳐서 마지막으로 32 비트의 최종 결과를 얻는다.

이와같이 UMAC은 MAC을 생성할 때, UHASH-32에서 $ HashedMessage$가 32 비트 단위로 차례로 구해지므로 MAC의 앞부분만을 이용하여 검증할 수도 있다.

UHASH-16은 WORD-LEN=2이므로 UHASH-32와는 기본단위가 다르므로 알고리즘이 차이가 나지만 기본적인 알고리즘의 구조는 거의 유사하다

L1-HASH-16은 NH-16 함수를 이용하여 메세지 $ M$을 압축하는 단계로 UMAC-OUTPUT-LEN보다는 긴 길이로 압축한다. NH-16 역시 NH-32와 같이 32 바이트의 배수가 되는 메세지 $ M$을 입력으로 하지만 8 바이트가 아니라 4 바이트의 출력을 내는 함수이다.

그림 13: NH-16

L2-HASH-16도 L2-HASH-32에서와 같은 `polynomial hash function' POLY를 이용하여 16 바이트의 고정된 길이로 압축한다. L3-HASH-16은 L2-HASH-16의 출력인 16 바이트로부터 16 비트를 출력하는 함수이다.



=--------------------------------------------------------------------------------------=

This document was generated using the LaTeX2HTML translator Version 99.2beta8 (1.43)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html summary

The translation was initiated by 이동훈 on 2001-06-07
AND

대칭키 암호화 이야기

Algorithm 궁금하니? 2009. 3. 10. 09:52
출처: http://blog.paran.com/blog/detail/postBoard.kth?pmcId=javacipher&blogDataId=28779104

지금부터는 대칭키 암호화에 관련하여 지난번에 소개한 소수에 대한 설명을 하도록 하겠다.
SEED 알고리즘으로 암호화한 샘플에서 맨 먼저 주목해야 할 부분은 키(KEY)부분이다.

 

byte[] key = {(byte)0x01,(byte)0x02,(byte)0x03,(byte)0x04,(byte)0x05,(byte)0x06,(byte)0x07,(byte)0x08,
             (byte)0x09,(byte)0x10,(byte)0x11,(byte)0x12,(byte)0x13,(byte)0x14,(byte)0x15,(byte)0x16}; 
      
대칭키 암호화 알고리즘은 암호화에 사용한 키와 복호화에도 동일하게 사용하게 되는데 중요한 것은
키의 길이다.

 

SEED 알고리즘은 키의 길이를 128비트(16바이트)를 사용한다. 키의 길이가 128비트라는 이야기는 암호화된
키를 찾아내기 위해서는 2의 128승의 키 중에서 하나를 찾는 작업인데 불가능하지는 않지만 오랜 노력과
시간이 필요하다는 것을 의미한다.

 

과거에 만들어진 DES 알고리즘의 경우 키의 길이가 64비트(8바이트)였다. 전산 환경의 발달은 2의 64승의
연산은 굳이 슈퍼 컴퓨터를 통하지 않더라고 키를 알아내는데 그다지 긴 기간이 필요하지 않기 때문에 현대에
만들어진 대칭키 알고리즘은 128비트 256비트 등 긴 키 길이를 지원한다.

 

키길이가 길면 길수록 암호화의 속도는 떨어지기 때문에 128비트의 키길이가 현재 수준에서 가장 적정하다고
받아들여지고 있다.

 

중요 알고리즘별 키길이는 다음과 같다.

- SEED: 128비트
- DES: 64비트
- Blowfish:64비트
- TripleDES(DESede): 192비트
- AES: 128, 192. 256 비트

 

국내간에는 SEED가 보편적으로 사용되지만 외국기관간 암호화 통신에는 아직도 DES와 TripleDES을 많이 사용하기
때문에 우선 암호화할 알고리즘이 결정되면 거기에 맞는 키길이로 키를 만들어 주어야 한다.

즉 SEED 알고리즘에서는 128비트 이지만 만약 다른 알고리즘으로 암호화한다고 했을 때
위에 정의한 키의 길이는 8바이트로 만들어 주고 다음과 같이 알고리즘을 호출해 주어야 한다.


//DES시 8바이트 키설정 및 알고리즘 선언
byte[] key = {(byte)0x01,..};
...
PaddedBufferedBlockCipher blockcipher = new PaddedBufferedBlockCipher(new DESEngine());


//TripleDES시 24바이트 키설정 및 알고리즘 선언
byte[] key = {(byte)0x01,..};
...
PaddedBufferedBlockCipher blockcipher = new PaddedBufferedBlockCipher(new DESedeEngine());

//AES시 16 또는 24 또는 32 바이트 키설정 및 알고리즘 선언
byte[] key = {(byte)0x01,..};
...
PaddedBufferedBlockCipher blockcipher = new PaddedBufferedBlockCipher(new AESEngine());

 

그 이후에 나머지 소스는 동일하다.


AND

CRC : CRC-16, CRC-32에 대한 설명과 구현

Algorithm 궁금하니? 2008. 1. 15. 17:15
출처:http://blog.naver.com/programsite?Redirect=Log&logNo=140006735194


CRC-16/32

CRC(Cyclic Redundancy Check)는 시리얼 전송에서 데이타의 신뢰성을 검증하기 위한 에러 검출 방법의 일종이다.

간단한 에러 검출방법으로는 parity 비트에 의한 방법과 check-sum에 의한 에러 검출 방법이 있지만 parity 비트에 의한 방법은 데이타 중에 한꺼번에 2비트나 4비트가 변하게 되면 검출을 할 수 없고, check-sum에 의한 방법은 한 바이트에서 +1, 다른 바이트에서는 -1로 에러가 생기는 경우만 해도 에러는 검출 되지 않는다. 즉, 이들 방법으로는 에러를 검출해 낼 수 있는 확률이 대단히 낮다.

CRC에 의한 방법은 높은 신뢰도를 확보하며 에러 검출을 위한 오버헤드가 적고, 랜덤 에러나 버스트 에러를 포함한 에러 검출에 매우 좋은 성능을 갖는 것을 특징으로 한다.

이러한 CRC 방법으로 보통 2가지 종류가 사용 되는데, 원칩 마이크로 프로세서와 같이 간단한 용도에서는 CRC-16 이 사용되고, 이보다 더욱 정확한 에러 검출이 필요한 경우에는 CRC-32를 사용한다.

ZIP,ARJ,RAR 과 같은 압축 프로그램이나 플로피 디스크 등의 데이터 검증 용도에 널리 사용되고 있다.

　

기본 원리

n 비트의 주어진 정보가 있을때, 이를 k 비트 만큼 자리를 올리고 미리 약속한 k 비트의 키 값으로 나누면 r 비트의 나머지가 남게 된다. 송신측에서는 원래의 정보 비트를 k 비트 자리 올린 것에 r 비트의 나머지를 더해서 n+r 비트의 데이타를 만들어 보낸다.
수신측에서는 수신된 n+r 비트의 데이타를 키 값으로 나누어 보고 나머지가 정확히 0 이 되는지를 검사하면 된다.

이 때 k 가 16 비트이면 CRC-16, 32비트이면 CRC-32 가 되고 키 값으로는 수학자 들에 의해 정해진 값을 주로 사용한다.
CRC-16 에는 0x8005, CRC-32 에는 0x04c11db7 이 많이 사용된다. 그리고 r 비트의 나머지를 Frame Check Sequence(FCS)라고 부른다.

여기서 CRC 계산에 사용되는 modulo-2 연산의 세계를 살펴보자.

CRC 계산시의 사칙연산은 carry를 고려하지 않는다.
1 + 1 = 0 (carry는 생각하지 않음)
0 - 1 = 1
덧셈 연산은 뺄셈 연산과 결과가 같으며 XOR 연산과도 같다.

다항식 표현 방법을 통해 CRC 계산 방법을 살펴보자.

(1) 2진 다항식으로 표시

예) 비트열 101 --> 다항식 x2 + 1

정보 다항식: 데이터 비트열의 다항식으로 P(x) = pn xn-1 + ... + p3x2 + p2x1 + p1
CRC 다항식: CRC 생성을 위한 다항식으로 G(x) (미리 정해진 키 값)
몫: Q(x)
나머지: R(x)
전송 데이타: T(x)

(2) CRC 계산 방법

P(x)를 k 비트 만큼 자리를 올리고( P(x)에 xk를 곱하는 것과 동일) G(x)로 나누면

xk P(x) = Q(x)*G(x) +/- R(x) 이다.

(k는 CRC 다항식의 최고 차수)

R(x) = dk xk-1 + .. + d2x1 + d1 ( R(x)의 최고 차수는 k-1)

비트열 dk ... d2 d1 을 FCS(Frame Check Sequence) 라 함

위 식에서 xk P(x) + R(x) 는 Q(x)*G(x) 와 같다.

즉, xk P(x) + R(x) 는 G(x)의 배수이므로 G(x) 로 나누면 나머지가 0 임을 알 수 있다.

결과적으로 전송되는 데이터 비트열 : pn ... p3 p2 p1 dk ... d2 d1

즉, 전송 T(x) = xk P(x) + R(x)

　

예) 데이터 비트열 110011 즉 P(x) =x5+x4+x1+x0, CRC 다항식G(x) = x4+x3+1, 즉 11001일 경우 FCS와 전송되는 비트열은?

xkP(x) = x4 (x5 + x4 + x1 + 1) = x9 + x8 + x5 + x4, 비트열로 표시하면 1100110000

                   100001
          ____________
11001 | 1100110000
            11001
          ____________
                     10000
                     11001
          ____________
                       1001    

xkP(x) = Q(x)G(x) - R(x)에서

Q(x) = x5 + x0 이므로,

R(x) = x3 + x0, ---> FCS는1001

따라서 전송되는 비트열 1100111001

　

연산의 최적화

CRC의 계산은 일반 나눗셈 명령을 이용해 구현할 수 없다. 1비씩 shift 하면서 XOR 연산을 통해 나머지를 구해야 한다.
하지만 정보 비트에 대해 하나하나씩 연산을 하는 것에는 분명 속도 개선의 여지가 있다.
실제 계산 시에는 모든 바이트에 대해 CRC 다항식에 대한 CRC값을 계산해 표로 만들어 두고 들어오는 데이타를 인덱스로 삼아 계산값을 바로 얻는 방법을 사용 한다.

AND

CRC란 무엇인가?

Algorithm 궁금하니? 2008. 1. 15. 17:14

※ CRC란 무엇인가?

Cyclic Redundancy Code(순환 오류 검사 )

CRC는 파일이 전송되는 도중에 손상되지 않았는가를 검사해 주는 것입니다.
CRC 에러가 났다는 것은 파일의 일부 내용이 손상되었다는 것입니다.


CRC 의 기본 원리
n 비트의 주어진 정보가 있을때, 이를 n 비트 만큼 자리를 옮기고 미리 약속한 k(n+1) 비트의 키 값으로 나누면 r 비트의 나머지가 남게 된다. 송신측에서는 원래의 정보 비트를 k 비트 자리 올린 것에 r 비트의 나머지를 더해서 n+r 비트의 데이타를 만들어 보낸다.

AND

티스토리툴바