Chip123 科技應用創新平台
標題:
关于循环冗余校验CRC
[打印本頁]
作者:
windflowerz
時間:
2007-6-17 01:10 AM
標題:
关于循环冗余校验CRC
CRC(Cyclic redundancy check)也就是循环冗余校验，是一种检验错误的方法，尤其在数据传输的时候，在发送端和接收端用同样的方法得到一个数字，然后接受端用该值和接收到的校验和进行比较。如果相同，则表示传送无误，可以处理数据。否则就是传送失败，并采取相应措施。
9 i# }1 S5 m# q0 k7 T
) X, I7 j8 \' i! _! D- q U; K" j9 E
我一直以为CRC就是简单的用相加的方法得到一个校验和（checksum)，就像我们原来计算BIOS的校验和一样。crc8就是把所有的字节相加，得到一个8位的结果，crc16就是把所有的short相加，得到一个16位的结果，crc32就是把所有的整数相加，……以此类推。
U# D$ ^* @3 \' _
# E6 g( P, |1 ^, E$ }% K; F1 ]
但是，直到我真正开始做这个，才发现根本没有这么简单。这只是最基本的做法，虽然广泛使用（比如tcp标准校验和采用的就是该方法），但是却有着其本身不可克服的局限性。比如在传输数据时，如果数据本身和校验和都产生一位错误，就极有可能导致接受端发出错误的判断。所以crc才有很多变种，而且其最基本的数学原理也不是加法，而是除法，而且是多项式除法并取余。也就是用精心挑选的除数去除原数据，剩下的N位余数就是crc的结果。
U8 j0 _7 L, y0 |3 s
" T( R! L+ H& }2 `' [( { ~
crc也不是以字节或整数为操作单位的，而是以比特为单位，只是人们为了简化运算，才有了以字节为单位的运算，才有了XOR，而非DIV的做法。而且为了对每一个原数据的位进行操作，才有了我们今天的查表法，也就是根据当前已得到的crc值和新输入的字节，产生一个索引，从表中查出相应数据，再和变化过的crc值进行异或，产生新的crc值。如此循环，直至所有的输入字节都处理完毕。
6 M+ [9 v- E0 ]6 K( d
* R6 f2 d0 h1 R9 u; P* k
crc虽然广泛用于全球标准化通讯系统中，但是并没有真正被标准化。大部分目前使用的crc都根据其长度和结构有着或多或少的弱点。现在主要用到的crc16采用的是CCITT的标准，而crc32用的是IEEE 802.3的标准。另外alder算法也非常流行，有兴趣的可以参考维基的英文网页，以crc为关键字查询，将得到非常详细的答案和参考书目。
! N) y7 |7 ^0 a" n: j
, W6 B3 r' W \ @+ n
因为crc是一个线形运算，所以易于破解，很难用于数据保护。一个比crc更有效地保护数据的方法就是one-way hash算法，也就是根据输入数据做运算，最后产生一段固定的输出。而其过程是非逆的。也就是说，你可以根据该算法轻易地得到输出，却几乎不可能根据输出来推断你的输入。比较流行的hash算法有MD5和SHA1以及SHA的各种变形。但随着技术的日新月异，MD5已经被证明不够安全，SHA1也被中国的教授发现了其弱对撞性。看来安全的路未来还很长。
作者:
masonchung
時間:
2007-6-17 03:45 PM
標題:
A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS
不知這個錯誤偵測的方法如何~:o
1 C3 I" j R2 l+ V' `3 ~% e# J
Table of Contents
- C! H& S0 s6 C( n( f P; M
1. Preface
/ o' v1 R, U9 T$ I: c
1.1) About the Author & Copyright
/ ^! x- h; C% G. K# |
1.2) Abstract
- p; ~! I+ p- j
2. Introduction: Error Detection
4 h4 q s8 `$ R X- H- X! a& t
3. The Need For Complexity
) j `- n, y* W. O& O- H
4. The Basic Idea Behind CRC Algorithms
+ c- X. y1 T* |/ X6 U
5. Polynomical Arithmetic
# B3 w: H# x3 ~6 N( r
Chapter 6) Binary Arithmetic with No Carries
1 v( X- ? ^ i4 w" N& D7 l
Chapter 7) A Fully Worked Example
2 H8 \, Z( @. o: j
Chapter 8) Choosing A Poly
, U$ U7 d2 @( W, R# a2 K8 ?
Chapter 9) A Straightforward CRC Implementation
) O* B2 X6 x$ v' l K9 T
Chapter 10) A Table-Driven Implementation
3 J# V q/ C U; a) A3 ~% c' N
Chapter 11) A Slightly Mangled Table-Driven Implementation
2 C: M7 Y. O" F1 Y3 r; J: s
Chapter 12) "Reflected" Table-Driven Implementations
) W! [# M; m5 [; b+ c, G
Chapter 13) "Reversed" Polys
8 C8 F) l$ i& ?
Chapter 14) Initial and Final Values
+ T9 R. n" A* v
Chapter 15) Defining Algorithms Absolutely
8 j( W. X* m' R3 i) O) Y
Chapter 16) A Parameterized Model For CRC Algorithms
! Y% `. d! W9 g
Chapter 17) A Catalog of Parameter Sets for Standards
( Q- B! V1 ?# r1 o# l }
Chapter 18) An Implementation of the Model Algorithm
) P; L1 s& C# F- w3 A. |
Chapter 19) Roll Your Own Table-Driven Implementation
% o% Y7 @- D) }
Chapter 20) Generating A Lookup Table
. T* a9 j# L: \7 V
Chapter 21) Summary
! w: P: t. @. }1 v3 d3 t
Chapter 22) Corrections
3 ]1 { K. E L8 F: _: ]/ C
Chapter 23) Glossary
8 d! P0 k! b% b$ F3 A# z
Chapter 24) References
/ ]2 i, y2 h4 m" K
Chapter 25) References I Have Detected But Haven't Yet Sighted
- \3 D% {( o' \* x" ]
# k$ u$ h+ D9 t
http://www.repairfaq.org/filipg/LINK/F_crc_v3.html
作者:
windflowerz
時間:
2007-6-18 07:32 PM
哎呀，太复杂了，不过原理应该是一样的。我这里有一个不错的文档，让我试试看上传
歡迎光臨 Chip123 科技應用創新平台 (http://www.chip123.com.tw/)
Powered by Discuz! X3.2