随着互联网技术的飞速发展 ,尤其在棱镜门事件曝光之后,人们会越来越多的在媒体上听到或看到一个词组叫做“网络安全”(Cyber Security)。其实最近几年,这个概念也开始在汽车领域被重视,毕竟随着车联网时代的到来,汽车ECU也可能成为黑客们(特指Cracker)攻击的对象,轻则可能丢失车辆,重则可能会对乘车人安全造成严重威胁。
本文笔者将介绍SHA即安全散列算法(Secure Hash Algorithm),可以将其用于27服务中以保护汽车ECU中重要数据不会轻易泄露或被篡改。
SHA其实是一个算法家族,由美国国家安全局(NSA)开发,有SHA1、SHA2、SHA3三类,目前SHA1已经被破解,使用比较广泛的是SHA2类。
图1 SHA各类算法对比(图源:维基百科)
本文以SHA256算法为例进行说明。
SHA256算法原理
安全散列算法,即是将一段接收到的message通过哈希算法将其转换成固定位数的哈希值(也称消息摘要)。SHA256就是将message通过哈希算法计算得到一个256位的哈希值。
根据笔者理解,将SHA256计算分成两个大的步骤:
1.信息预处理(Preprocessing)
分两个小的步骤:
第一步,填充比特位,在填充的时候遵循以下公式:
(消息原始长度 + 1 + k) mod 512 = 448
下面来解释一下这个公式:
1:指在原始数据的后面添加1个比特位“1”
k:指使上述公式成立的最小的整数k,在之前填充的“1”后面填充k个“0” mod:取模运算
读者一定会有疑问,为什么最后取模结果要是448,这就涉及到第二步,请继续往下看。
第二步,填充附加长度
这里的附加长度是指原始message的长度,用64位的二进制数来进行位填充,这样总的长度加上之前的448正好是512的整数倍,将这每512位为一组的数据块称作一个消息分块,对一个原始message进行这样的填充之后,可能分出n个512位的消息分块来。
需要注意的是,即使原始message的长度已经满足上述公式,还是要进行位填充,这里填充512位,1位二进制“1”,511位二进制“0”。所以可以知道,填充的位数在1~512之间。
原始message的长度用64位二进制表示,所以知道这个原始message的长度最长为(2^64 - 1)位。
示例:
假设有一条ASCII码表示的原始消息为“abc",将其化为二进制数则一共有3*8=24位,这时就需要在24位二进制数后面补充1位“1”和423位“0”,然后再将数据长度24转换为64位的二进制数填充在末尾,就完成了对原始消息的填充,如下图所示:
图2 信息预处理示意
2.计算摘要
计算摘要前,先来了解两个概念。
(1)消息分块
上面讲过每512位比特位组成的一个消息分块,我们将其记为M(i),然后将每个M(i)又分成16个32位比特位组成的小分块,将其记为Mj(i),j取值为0~15,如下图所示:
图3 消息分块示意
之所以这样做是因为在后面计算哈希值的时候,要用这样的数据结构(16个32位的数据)进行迭代以完成哈希值的计算。
(2)扩展消息块
用Wj来表示,Wj遵循以下公式:
哈希值计算过程:
(1)计算公式
上式为一个递推公式,当前哈希值H(i)由上一次计算的H(i-1)得到。
函数C:SHA256压缩函数
+:表示每一个运算单元字(word,SHA256中一个字为32位)取模之后做加法运算
(2)逻辑函数
在迭代计算过程中要用到这6个函数。
(3)计算
Step 1:对哈希值进行初始化
上述8个32位的数据级联起来长度有8*32=256,所以可知,哈希值的最终值是由这8个数据组成的。
至于这8个初始值怎么来的,如果不去探讨其背后的数学含义只拿来用的话,读者可以忽略。
Step 2:哈希值计算的中间过程
根据上述公式计算出a~h的值。
Step 3:进行迭代运算,计算中间散列值
根据Step 2公式中的Kj和Wj,可知迭代计算要进行64轮。
以下为算法中主要部分代码,完整代码请移步文章末尾链接。
static const WORD k[64] =
{
0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5,
0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174,
0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da,
0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,0x06ca6351,0x14292967,
0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85,
0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,0xd192e819,0xd6990624,0xf40e3585,0x106aa070,
0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3,
0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2
};
void sha256_init(SHA256_CTX *ctx)
{
ctx->datalen = 0;
ctx->bitlen = 0;
ctx->state[0] = 0x6a09e667;
ctx->state[1] = 0xbb67ae85;
ctx->state[2] = 0x3c6ef372;
ctx->state[3] = 0xa54ff53a;
ctx->state[4] = 0x510e527f;
ctx->state[5] = 0x9b05688c;
ctx->state[6] = 0x1f83d9ab;
ctx->state[7] = 0x5be0cd19;
}
void sha256_transform(SHA256_CTX *ctx, const BYTE data[])
{
WORD a, b, c, d, e, f, g, h, i, j, t1, t2, m[64];
for (i = 0, j = 0; i < 16; ++i, j += 4)
m[i] = (data[j] << 24) | (data[j + 1] << 16) | (data[j + 2] << 8) | (data[j + 3]);
for ( ; i < 64; ++i)
m[i] = SIG1(m[i - 2]) + m[i - 7] + SIG0(m[i - 15]) + m[i - 16];
/* Step 1 :Hash initialize */
a = ctx->state[0];
b = ctx->state[1];
c = ctx->state[2];
d = ctx->state[3];
e = ctx->state[4];
f = ctx->state[5];
g = ctx->state[6];
h = ctx->state[7];
for (i = 0; i < 64; ++i) {
t1 = h + EP1(e) + CH(e,f,g) + k[i] + m[i];
t2 = EP0(a) + MAJ(a,b,c);
h = g;
g = f;
f = e;
e = d + t1;
d = c;
c = b;
b = a;
a = t1 + t2;
}
ctx->state[0] += a;
ctx->state[1] += b;
ctx->state[2] += c;
ctx->state[3] += d;
ctx->state[4] += e;
ctx->state[5] += f;
ctx->state[6] += g;
ctx->state[7] += h;
}
密匙相关的HMAC算法也是基于SHA,利用密匙和明文进行两轮哈希运算,笔者有空会继续和大家分享。
参考资料:http://www.iwar.org.uk/comsec/resources/cipher/sha256-384-512.pdf
源码路径:https://github.com/B-Con/crypto-algorithms