常见校验算法原理与应用指南
UART有一个奇偶校验，CAN通信有CRC校验。Modbus、USB等通信协议也有校验信息。在自定义数据存储时，有经验的工程师一般都会添加一定校验信息。
一、校验和
核心思想：将数据视为一系列字节或字（例如16位整数），将它们全部加起来，然后取结果的补码或截断到固定长度，作为校验值。
算法流程（以8位校验和为例）：
求和： 将数据包中的所有字节相加。
模运算（溢出处理）： 如果和超过了8位（即 > 0xFF），则将溢出部分加回低位（循环进位）。例如，0x1A3 会被处理为 0xA3 + 0x1 = 0xA4。
取补码： 对最终的和取反（按位取反），得到校验和。
示例：
数据： 0x01, 0x02, 0x03, 0x04
求和： 0x01 + 0x02 + 0x03 + 0x04 = 0x0A
取补码： ~0x0A = 0xF5
校验和即为 0xF5。
深入理解：
优点： 计算极其简单，速度快，资源消耗少。广泛应用于网络协议（如IP、TCP、UDP头部的校验和）和快速数据完整性检查。
缺点：
检错能力弱： 对字节顺序的交换不敏感。例如，交换两个字节的位置，校验和不变。如果某一位出错，而另一位在相反的位置出错，错误可能会被抵消，导致校验和仍然正确。
本质： 一种基于加法的线性运算，其检错能力源于加法溢出的非线性特性，但这种非线性很弱。
实现的方式方法很多，不同的编程语言，不同的应用有所不同，下面以C语言8位校验和为例：
uint8_t CheckSum(uint8_t *Buf, uint8_t Len)
{
uint8_t i = 0;
uint8_t sum = 0;
uint8_t checksum = 0;
for(i=0; i<Len; i++)
{
sum += *Buf++;
}
checksum = sum & 0xff;
return checksum;
}二、奇偶校验 (Parity Check)
核心思想： 在数据位后添加一个额外的位（奇偶位），使得整个数据单元中“1”的个数为奇数（奇校验）或偶数（偶校验）。
算法流程：
- 统计数据位中“1”的个数。
- 奇校验： 如果“1”的个数是偶数，则奇偶位置1；如果是奇数，则置0。（最终“1”的总数为奇数）
- 偶校验： 如果“1”的个数是偶数，则奇偶位置0；如果是奇数，则置1。（最终“1”的总数为偶数）
示例（偶校验）：
数据： 1011001 （有4个“1”，是偶数）
奇偶位： 0 （保持偶数个“1”）
发送： 10110010
深入理解：
优点： 实现最简单，硬件成本极低。
缺点： 只能检测出奇数个位的错误。如果发生两个位（或任意偶数个位）的错误，则“1”的个数的奇偶性不变，校验会通过，无法发现错误。
应用： 常用于内存（RAM）的简单错误检测、串口通信等对可靠性要求不高的场景。它可以被组织成二维形式（行和列都做奇偶校验），以增强检错和纠错能力。
三、循环冗余校验 (CRC)
核心思想： 将数据位串视为一个庞大的二进制多项式，然后用一个预定义的“生成多项式”去除它，将得到的余数作为校验码（CRC码）。这是一种基于模2除法的强大校验方法。
关键概念：
模2运算： 即异或运算，没有进位和借位。
生成多项式： 一个双方约定的除数，决定了CRC的强度和名称。例如：
- CRC-8:
x^8 + x^2 + x + 1(二进制表示为100000111) - CRC-16-CCITT:
x^16 + x^12 + x^5 + 1(二进制表示为10001000000100001) - CRC-32: 用于以太网、ZIP、PNG等。
算法流程：
- 附加0： 在原始数据帧的末尾附加
n个0，n是生成多项式的最高次幂（即CRC码的位数）。 - 模2除法： 用附加0后的数据帧除以生成多项式（使用模2除法）。
- 得到余数： 除法的余数（一定比除数短）就是CRC校验码。
- 组成发送帧： 用这个CRC校验码替换掉第一步中附加的
n个0，然后发送。 - 接收端验证： 接收方用同样的生成多项式去除接收到的整个帧。如果余数为0，则认为数据正确；否则，数据有误。
深入理解：
优点：
- 检错能力极强： 能检测所有奇数个错误、所有双位错误、所有长度小于等于生成多项式阶数的突发错误。
- 硬件实现高效： 可以通过移位寄存器和异或门轻松实现，速度非常快。
缺点： 不是加密哈希，不能用于防篡改，只能用于检错。
四、CRC校验的应用
本质： CRC的本质是将数据映射到一个有限域（伽罗瓦域）上的多项式，然后进行多项式除法。其强大的检错能力来自于生成多项式的精心设计。不同的生成多项式具有不同的错误检测特性。
CRC校验属于冗余校验中的一种，大学学计算机相关专业的同学都应该学过CRC校验。
CRC有多种变体，比如：CRC-1、 CRC-5-USB、 CRC-8、 CRC-16、 CRC-32、 CRC-64等。其中，在嵌入式领域，CRC-16用的比较多。
CRC校验不同场景实现方式不同，网上也有很多公开的库和源码，比如：
C语言中的开源CRC库 网上还有在线计算CRC校验值以及代码生成工具
不同的编程语言，不同的应用有所不同，下面以C语言为例：
uint16_t Crc16(uint8_t *data,uint16_t len)
{
uint16_t crc16 = 0xFFFF;
uint32_t uIndex ; //CRC查询表索引
while (len --)
{
uIndex = (crc16&0xff) ^ ((*data) & 0xff) ; //计算CRC
data = data + 1;
crc16 = ((crc16>>8) & 0xff) ^ crc16_tab[uIndex];
}
return crc16 ;//返回CRC校验值
}应用： 以太网帧、USB数据传输、磁盘存储、压缩文件（ZIP/RAR）、图像格式（PNG）等几乎所有需要高可靠性数据传输的领域。
五、加密散列函数 (Cryptographic Hash Function) - MD5, SHA家族
核心思想： 这些算法设计上不仅仅是检错，更是为了确保数据的完整性和不可篡改性。它们接收任意长度的输入，产生一个固定长度（如128位、256位）的、看似随机的“指纹”或“摘要”。
核心特性：
- 确定性： 相同的输入永远产生相同的输出。
- 快速计算： 给定输入，能快速计算出散列值。
- 抗碰撞性： 很难找到两个不同的输入，它们具有相同的散列值。
- 雪崩效应： 输入的微小改变（即使只改1个比特）会导致输出的散列值发生巨大且不可预测的改变。
- 不可逆性： 从散列值反向推算出原始输入在计算上是不可行的。
常见算法：
- MD5： 产生128位散列值。已被证明不安全，可以人为制造碰撞，不应用于安全目的，但仍可用于简单的文件完整性校验（如检查文件下载是否完整）。
- SHA-1： 产生160位散列值。同样被发现存在理论上的弱点，已被大多数安全应用淘汰。
- SHA-2家族（如 SHA-256, SHA-512）： 目前广泛使用的安全标准。SHA-256产生256位散列值。
- SHA-3： 最新的SHA标准，采用与SHA-2不同的设计结构，作为未来的备选。
深入理解：
与CRC的区别：
- 目的： CRC是为了检测无意的、信道引入的错误；散列函数是为了检测有意的、恶意的篡改。
- 强度： 散列函数的数学复杂性远高于CRC。CRC的碰撞是相对容易发生的，而找到加密散列函数的碰撞在计算上是极其困难的。
- 输出： CRC输出长度较短（16/32位），而散列函数输出较长（128位以上）。
应用：
- 数据完整性验证： 软件发布商提供文件的SHA-256校验和，用户下载后计算并对比，确保文件未被篡改。
- 数字签名： 对数据的散列值进行签名，而非数据本身，效率更高。
- 密码存储： 在数据库中存储密码的散列值，而非明文。
- 区块链： 区块链的每个区块都包含前一个区块的散列值，形成不可篡改的链条。
MD5的源码在网上都能找到现成的，而且有不同编程语言（C、 C++、 JAVA）版本。
六、SM3算法
随着变成技术越来越发达，校验算法也越来越多，有通用的算法，也有特殊领域特定的算法。
比如我之前开发使用由密码管理局发布的SM3密码杂凑算法。其安全性及效率与SHA-256相当。
包括SM2、SM3、SM4、SM9，杂凑值算法也可称为摘要算法或者哈希算法。实现原理：通过对数据资料的填充、分组、扩展压缩等方式计算成特定长度的数值，来作为数据指纹或者数据特征使用。
常见的MD5算法长度为128bit（16字节），SHA1算法计算长度为160bit（20字节），SHA256算法计算长度256bit（32字节），SHA512算法计算长度512bit（64字节），SM3算法计算长度为256bit（32字节）。
lk_sm3.h文件定义了一些函数宏和数据结构
#ifndef __lk_sm3_h__
#define __lk_sm3_h__
#ifdef __cpluscplus
extern "C" {
#endif
#include <strings.h>
#ifdef __cpluscplus
}
#endif
#define LK_GVALUE_LEN 64
#define LK_WORD_SIZE 32
#define LK_GVALUE_BITLEN 256
#define LK_HASH_NMEMB 8
typedef unsigned int UINT;
#ifdef i386
typedef unsigned long long UWORD;
#else
typedef unsigned long UWORD;
#endif
typedef unsigned char UCHAR;
//常量
// 0 <= j <= 15
#define LK_T0 0x79cc4519
// 16 <= j <= 63
#define LK_T1 0x7a879d8a
//循环左移
#define LOOPSHFT(a, n) ( ((a) << (n)) | ((a) >> (LK_WORD_SIZE - (n))))
//布尔函数
#define LK_FF0(x, y, z) ((x)^(y)^(z))
#define LK_FF1(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
#define LK_GG0(x, y, z) ((x)^(y)^(z))
#define LK_GG1(x, y, z) (( (x) & (y) ) | ((~x) & (z)))
//置换函数
#define LK_P0(x) (\
(x)^(LOOPSHFT((x), 9))^(LOOPSHFT((x), 17)) )
#define LK_P1(x) (\
(x)^(LOOPSHFT((x), 15))^(LOOPSHFT((x), 23)) )
//标准中给出的IV初始值
#define LK_INIT_VALUE(t) {\
lk_sm3_context_t *x = (t);\
x->v[0] = 0x7380166f;\
x->v[1] = 0x4914b2b9;\
x->v[2] = 0x172442d7;\
x->v[3] = 0xda8a0600;\
x->v[4] = 0xa96f30bc;\
x->v[5] = 0x163138aa;\
x->v[6] = 0xe38dee4d;\
x->v[7] = 0xb0fb0e4e;\
bzero(x->data, LK_GVALUE_LEN);\
x->total = 0;\
x->len = 0;}
#define LK_LE_ONE(t) {\
lk_sm3_context_t *x = (t);\
UINT l_z, l_d;\
for (l_z = 0; l_z < LK_HASH_NMEMB; l_z++) {\
l_d = x->v[l_z];\
x->output[l_z*4] = ((l_d >> 24) & 0x000000ff);\
x->output[l_z*4 + 1] = ((l_d >> 16) & 0x000000ff);\
x->output[l_z*4 + 2] = ((l_d >> 8) & 0x000000ff);\
x->output[l_z*4 + 3] = (l_d & 0x000000ff);\
}}
//大端转化
#define LK_GE_ONE(c) (\
((c&0x00000000000000ffUL) << 56) | (((c&0x000000000000ff00UL) << 40)) |\
((c&0x0000000000ff0000UL) << 24) | (((c&0x00000000ff000000UL) << 8)) |\
((c&0x000000ff00000000UL) >> 8) | (((c&0x0000ff0000000000UL) >> 24)) |\
((c&0x00ff000000000000UL) >> 40) | (((c&0xff00000000000000UL) >> 56)) )
#define LK_GE(w, c) \
int j2;\
for (j = 0; j <= 15; j++) {\
j2 = j*4;\
w[j] = ((c[j2] << 24) | ((c[j2+1] << 16)) |\
(c[j2+2] << 8) | (c[j2+3]));\
}
//压缩计算摘要函数
#define LK_MSG_CF(t) {\
UINT j;\
lk_sm3_context_t *x = t;\
UCHAR *data = x->data;\
UINT W1[68];\
UINT W2[64];\
UINT a,b,c,d,e,f,g,h;\
a = x->v[0];\
b = x->v[1];\
c = x->v[2];\
d = x->v[3];\
e = x->v[4];\
f = x->v[5];\
g = x->v[6];\
h = x->v[7];\
LK_GE(W1, data)\
for ( j = 16; j <= 67; j++ ) {\
W1[j] = LK_P1(W1[j-16]^W1[j-9]^(LOOPSHFT(W1[j-3], 15))) ^ LOOPSHFT(W1[j-13], 7) ^ W1[j-6];\
}\
for ( j = 0; j <= 63; j++ ) {\
W2[j] = W1[j] ^ W1[j+4];\
}\
for ( j = 0; j <= 63; j++ ) {\
UINT T, ss1, ss2, tt1, tt2;\
if ( j >= 0 && j <= 15 )\
T = LK_T0;\
else\
T = LK_T1;\
ss1 = LOOPSHFT( (LOOPSHFT(a, 12) + e + LOOPSHFT(T, j)), 7 );\
ss2 = ss1 ^ LOOPSHFT(a, 12);\
if ( j >= 0 && j <= 15 ) {\
tt1 = LK_FF0(a, b, c) + d + ss2 + W2[j];\
tt2 = LK_GG0(e, f, g) + h + ss1 + W1[j];\
} else {\
tt1 = LK_FF1(a, b, c) + d + ss2 + W2[j];\
tt2 = LK_GG1(e, f, g) + h + ss1 + W1[j];\
}\
d = c;\
c = LOOPSHFT(b, 9);\
b = a;\
a = tt1;\
h = g;\
g = LOOPSHFT(f, 19);\
f = e;\
e = LK_P0(tt2);\
}\
x->v[0] = a ^ x->v[0];\
x->v[1] = b ^ x->v[1];\
x->v[2] = c ^ x->v[2];\
x->v[3] = d ^ x->v[3];\
x->v[4] = e ^ x->v[4];\
x->v[5] = f ^ x->v[5];\
x->v[6] = g ^ x->v[6];\
x->v[7] = h ^ x->v[7];\
x->len = 0;\
}
typedef struct lk_sm3_context_s
{
UINT len;
UINT total;
UCHAR data[LK_GVALUE_LEN];
UINT v[LK_HASH_NMEMB];
UCHAR output[LK_WORD_SIZE];
} lk_sm3_context_t;
#ifdef __cpluscplus
extern "C" {
#endif
extern void lk_sm3_final(lk_sm3_context_t *context);
extern void lk_sm3_update (lk_sm3_context_t *context, UCHAR *data, UINT len);
#ifdef __cpluscplus
}
#endif
#endiflk_sm3.c文件实现了update和final两个函数
#include <stdio.h>
#include <string.h>
#include "lk_sm3.h"
static void lk_sm3_cf(lk_sm3_context_t *context)
{
LK_MSG_CF(context)
}
void lk_sm3_update (lk_sm3_context_t *context, UCHAR *data, UINT len)
{
int real_len, free, offset = 0;
real_len = len + context->len;
if (real_len < LK_GVALUE_LEN) {
//本次数据不够一个分组大小,先缓存起来
memcpy(context->data + context->len, data + offset, len);
context->len = real_len;
context->total += len;
return;
}
free = LK_GVALUE_LEN - context->len;
memcpy(context->data + context->len, data + offset, free);
context->total += free;
offset += free;
len -= free;
//进行迭代压缩
lk_sm3_cf(context);
while (1) {
if (len < LK_GVALUE_LEN) {
//本次数据不够一个分组大小,先缓存起来
memcpy(context->data + context->len, data + offset, len);
context->len = len;
context->total += len;
return;
}
memcpy(context->data + context->len, data + offset, LK_GVALUE_LEN);
offset += LK_GVALUE_LEN;
len -= LK_GVALUE_LEN;
context->total += LK_GVALUE_LEN;
//进行迭代压缩
lk_sm3_cf(context);
}
}
void lk_sm3_final(lk_sm3_context_t *context)
{
UINT tk, k, free, i, len;
UCHAR tmp[LK_GVALUE_LEN] = {0};
tk = context->total * 8 % 512;
if (tk < 448) {
k = 448 - tk;
} else {
k = 448 -tk + 512;
}
//计算需要填充的字节
k = k / 8 + 8;
free = LK_GVALUE_LEN - context->len;
k--;
context->data[context->len] = 0x80;
len = context->total * 8;
for (i = context->len + 1; i < LK_GVALUE_LEN; i++, k--) {
if (k != 8)
context->data[i] = 0x00;
else {
bzero(context->data + i, 8);
UWORD *pdata = (UWORD *)&(context->data[i]);
*pdata = LK_GE_ONE(len);
break;
}
}
//进行迭代压缩
lk_sm3_cf(context);
if (64 == k) {
for (i = 0; i < LK_GVALUE_LEN; i++, k--) {
if (k != 8)
context->data[i] = 0x00;
else {
bzero(context->data + i, 8);
UWORD *pdata = (UWORD *)&(context->data[i]);
*pdata = LK_GE_ONE(len);
break;
}
}
//进行迭代压缩
lk_sm3_cf(context);
}
//get result
LK_LE_ONE(context)
}七、总结与对比
| 算法 | 核心原理 | 检错能力 | 计算开销 | 主要应用场景 |
|---|---|---|---|---|
| 奇偶校验 | 统计“1”的个数奇偶性 | 弱，只能检奇数位错 | 极低 | 内存、低速串口 |
| 校验和 | 字节/字累加取补 | 较弱，线性错误可能漏检 | 低 | 网络协议头部（IP, TCP, UDP） |
| CRC | 模2多项式除法 | 极强，适合检测信道突发错误 | 中等（硬件高效） | 网络帧（以太网）、存储、压缩 |
| 加密散列 | 复杂的压缩函数和位操作 | 极强，能抵抗恶意碰撞 | 高 | 数据完整性、数字签名、密码学 |
如何选择？
追求极致速度和简单性，错误后果不严重： 用奇偶校验或校验和。
需要高可靠性检错，对抗通信/存储中的随机错误： 用CRC。这是工程上的最佳实践。
需要验证数据来源真实性，防止恶意篡改： 用加密散列函数（如SHA-256）。
更多推荐
8
0- 0
已为社区贡献2条内容
所有评论(0)